Теорема о базах

Теорема (о равномощности баз):

Пусть $B_1$ и $B_2$ — базы матроида $M$. Тогда $|B_1| = |B_2|$.

Доказательство:

$\triangleright$

Доказательство от противного. Пусть $|B_1| \gt |B_2|$. Тогда по третьей аксиоме определения матроида $\exists x \in B_1 \setminus B_2$ такой, что $B_2 \cup {x} \in I$. То есть $B_2$ — не максимальное по включению независимое множество, что противоречит определению базы. Случай $|B_2| \gt |B_1|$ разбирается аналогично.

$\triangleleft$

Теорема (о базах):

Пусть $M$ — матроид и $B_s$ — семейство его баз. Тогда: 1) $B_s \ne \varnothing$; 2) если $B_1, B_2 \in B_s$ и $B_1 \ne B_2$, то $B_1 \nsubseteq B_2$ и $B_2 \nsubseteq B_1$; 3) если $B_1, B_2 \in B_s$, то для $\forall b_1 \in B_1 \: \exists b_2 \in B_2$ такой, что $(B_1 \setminus b_1) \cup b_2 \in B_s$.

Доказательство:

$\triangleright$

1) Следует из первой аксиомы определения матроида; 2) Из теоремы о равномощности баз следует, что $B_1 \neg \subset B_2$ и $B_2 \neg \subset B_1$. А с условием $B_1 \ne B_2$ получаем $B_1 \nsubseteq B_2$ и $B_2 \nsubseteq B_1$; 3) Введем следующие обозначения: $A := B_2$ $B := B_1 \setminus b_1$ Заметим, что $A \setminus B = B_2 \setminus (B_1 \setminus b_1)$ содержит хотя бы один элемент $b_2 \in B_2$, то есть $\exists x \in A \setminus B$. $x := b_2$ По теореме о равномощности баз $|A|\gt |B|$, значит для них выполняется третья аксиома определения матроида. С учетом введенных обозначений аксиома принимает вид: $\exists b_2 \in B_2$ такой, что $(B_1 \setminus b_1) \cup b_2 \in I$. А так как $|(B_1 \setminus b_1) \cup b_2| = |B_1|$ и $B_1$ — база, то $(B_1 \setminus b_1) \cup b_2 \in B_s$, что и требовалось доказать.

$\triangleleft$