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

Материал из Викиконспекты
Перейти к: навигация, поиск
Теорема (о базах):
Пусть [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]\triangleleft[/math]