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

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]