拟阵的所有最大独立集具有相同的基数
All maximal independent sets of a matroid have the same cardinality
如何证明拟阵的所有最大独立集都具有相同的基数
假设拟阵是二元组 (M,J)，其中 M 是有限集，J 是
M 的某些子集的族，满足以下条件
属性：
- 如果A是B的子集，B属于J，那么A属于J，
- 如果A，B属于J，|A| <= |B|，且 x 属于 A - B，
则存在 y 属于 B - A 使得 (B U {x})- {y} 属于 J。
J的成员称为独立集。
相反假设 |A| < |B|，并且 A 非 最大独立。
考虑以下维恩图
显然 B \ A（唯一的蓝色部分）是非空的，因为 B 的基数大于 A。此外，显然 A \ B（唯一的橙色部分）是非空的，否则 A ⊂ B，并且根据定义，A 不是最大 独立的。
因此，通过交换属性，有一些x ∈ A\B,y∈ B\A，使得B∪{x}\{y}∈ J 也是。我们称这个集合为 C。请注意，如果我们绘制 A 和 C 的维恩图（现在蓝色圆圈是 C ):
|B| = |C|（蓝色圆圈大小相同）
|(A\{x})\C| < |A \ B|（唯一的橙色部分比之前小）
现在我们可以重复关于A和C的争论，等等。但是请注意，我们不能无限期地重复它，因为假定 A 是有限的。因此，在某些时候我们会遇到橙色集完全包含在蓝色集中的矛盾，我们之前已经看到这是不可能的（根据定义，这意味着它不是最大独立的）。
我们将使用反证法来做到这一点。
假设拟阵的所有最大独立集不具有相同的基数。
因此必须有一些集合 A 和集合 B 使得它们都是最大独立集。没有
失去一般性让我们取 j A j < j B j 即 A 的基数小于 B 的基数。
设 j A j = P 和 j B j = Q , P < Q 。现在让 X 2 A-B 和 Y 2 B-A。 X和Y永远存在
因为 A 是最大的并且与 B 不同。使用 Matroid 的第二个 属性 我们可以制作 B1
= f B [ X g - f y g 也是独立集并且 j B1 j = Q 。我们可以继续选择一个
来自 X' 2 A-Bi 的元素和来自 Y' 2 Bi-A 的元素并插入 X' 并移除 Y' 以生成 a
具有基数 Q 的新独立集，直到 A-Bi 中没有元素。
因为 A-Bi = 因此 A Bi。但是 Bi 也是基数 Q 的独立集。现在我们可以
说 A 不是最大的，这是矛盾的，因此我们的假设是 wrong.Thus j A j
= j B j 这意味着不可能有两个具有不同基数的最大独立集。
所以拟阵的所有最大独立集都具有相同的基数。
如何证明拟阵的所有最大独立集都具有相同的基数
假设拟阵是二元组 (M,J)，其中 M 是有限集，J 是 M 的某些子集的族，满足以下条件 属性：
- 如果A是B的子集，B属于J，那么A属于J，
- 如果A，B属于J，|A| <= |B|，且 x 属于 A - B， 则存在 y 属于 B - A 使得 (B U {x})- {y} 属于 J。
J的成员称为独立集。
相反假设 |A| < |B|，并且 A 非 最大独立。
考虑以下维恩图
显然 B \ A（唯一的蓝色部分）是非空的，因为 B 的基数大于 A。此外，显然 A \ B（唯一的橙色部分）是非空的，否则 A ⊂ B，并且根据定义，A 不是最大 独立的。
因此，通过交换属性，有一些x ∈ A\B,y∈ B\A，使得B∪{x}\{y}∈ J 也是。我们称这个集合为 C。请注意，如果我们绘制 A 和 C 的维恩图（现在蓝色圆圈是 C ):
|B| = |C|（蓝色圆圈大小相同）
|(A\{x})\C| < |A \ B|（唯一的橙色部分比之前小）
现在我们可以重复关于A和C的争论，等等。但是请注意，我们不能无限期地重复它，因为假定 A 是有限的。因此，在某些时候我们会遇到橙色集完全包含在蓝色集中的矛盾，我们之前已经看到这是不可能的（根据定义，这意味着它不是最大独立的）。
我们将使用反证法来做到这一点。 假设拟阵的所有最大独立集不具有相同的基数。 因此必须有一些集合 A 和集合 B 使得它们都是最大独立集。没有 失去一般性让我们取 j A j < j B j 即 A 的基数小于 B 的基数。 设 j A j = P 和 j B j = Q , P < Q 。现在让 X 2 A-B 和 Y 2 B-A。 X和Y永远存在 因为 A 是最大的并且与 B 不同。使用 Matroid 的第二个 属性 我们可以制作 B1 = f B [ X g - f y g 也是独立集并且 j B1 j = Q 。我们可以继续选择一个 来自 X' 2 A-Bi 的元素和来自 Y' 2 Bi-A 的元素并插入 X' 并移除 Y' 以生成 a 具有基数 Q 的新独立集，直到 A-Bi 中没有元素。 因为 A-Bi = 因此 A Bi。但是 Bi 也是基数 Q 的独立集。现在我们可以 说 A 不是最大的，这是矛盾的，因此我们的假设是 wrong.Thus j A j = j B j 这意味着不可能有两个具有不同基数的最大独立集。 所以拟阵的所有最大独立集都具有相同的基数。