所有最大獨立集的一個matriid具有相同的基數

Question

如何證明matriid的所有最大獨立集具有相同的基數。

提供的擬陣是一個2元組（M，j），其中M是一個有限集和J是 家族的一些M的滿足下述 屬性子集：

1. 如果A是A的子集，B屬於J，則A屬於J，
2. 如果A，B屬於J，則| A | < = | B |，和x屬於A - B， 則存在ÿ屬於乙 - A使得（BU {X}） - {Y}屬於J.

j的成員被稱爲獨立組。

Answer 1

假設恰恰相反| A | < | B |和A是而不是最大獨立。

考慮以下維恩圖

顯然乙\ A（唯一的藍色部分）非空，如乙的基數比的甲大。此外，清楚地A \ B（唯一的橙色部分）非空，否則甲⊂乙，並且，根據定義，甲不是最大限度獨立。

因此，通過交換性能，有一些X ∈ A \ B，Y ∈乙\ A，使得乙∪ {X} \ {Y} ∈Ĵ爲好。我們稱之爲C。需要注意的是，如果我們將繪製維恩圖的一個和Ç（即現在的藍色圓圈是Ç）：

1. | B | = | C |（藍圈的大小相同）

2. |（A \ {x}）\ C | < | A \ B |（唯一的橙色部分是比以前小）

現在我們可以重複的論點約一個和Ç，等等。但是，請注意，我們不能無限期地重複它，因爲假設A是有限的。因此，在某些時候，我們會達到這樣的矛盾，即橙色集合完全包含在藍色集合中，我們之前已經看到這是不可能的（根據定義，這意味着它不是最大獨立的）。

Answer 2

我們將做到這一點使用反證法。 讓我們假設一個matriid的所有最大獨立集都不具有相同的基數。 因此，必須有一個集合A和集合B，以使兩者都是最大獨立集合。不失一般性的 損失讓美國採取J AĴ<Ĵ乙Ĵ即基數低於基數B. 令j爲J = P和j乙J = Q，P < Q的。現在讓X 2 A-B和Y 2 B-A。 X和Y將一直存在 因爲A是最大的，並且從dierent B.使用擬陣的第二屬性我們可以使B1 = F B [X克 - ˚Fý克這也是獨立集和j B1 J = Q值。我們可以繼續挑選從X的 元素「2 A-Bi和來自Y的元素」 2雙A和插入X「和刪除Y」，使具有基數Q上 新的獨立設置，直到有在任何元素A-碧。由於A-Bi = A Bi。但畢也和獨立組與基數問：現在我們可以 說A是不是最大的是一對矛盾，因此我們的假設是wrong.Thus J AĴ = j的乙j，它意味着可以有沒有兩個最大的獨立設置不同的基數。 所以所有最大的獨立的一個matroid集具有相同的基數。