所有最大独立集的一个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集具有相同的基数。