Изменения

Перейти к: навигация, поиск

Аксиоматизация матроида рангами

18 байт добавлено, 21:08, 19 мая 2015
Нет описания правки
# В силу (1) выполняется <tex>r(\emptyset)=0</tex>, следовательно <tex> \emptyset \in \mathcal{I}</tex>.
# Пусть <tex> I \in \mathcal{I}</tex> и <tex>J \subseteq I</tex>. Предположим от противного, что <tex>r(J) < |J|</tex>. Тогда, используя (1) и (3), получаем: <tex>|I| = r(I) = r(J \cup (I \setminus J)) \le leqslant r(J) + r(I \setminus J) - r(\emptyset) < |J| + |I \setminus J| = |I|</tex>, что невозможно. Следовательно, <tex>r(J) = |J|</tex>, т.е. <tex> J \in \mathcal{I} </tex> <br># Пусть <tex>I, J \in \mathcal{I}</tex> и <tex>|I| < |J|</tex>. Положим <tex>J \setminus I = \{p_1, \ldots,p_t\}</tex>. Пусть, от противного, <tex>I \cup p_i \notin \mathcal{I}</tex> для любого <tex>i = 1, \ldots,t</tex>. Тогда для <tex>i = 1, \ldots,t</tex> имеет место: <br> <tex> |I| = r(I) \le leqslant r(I \cup p_i) < |I \cup p_i| = |I| + 1</tex>, т.е. <tex> r(I \cup p_i) = |I|</tex>. <br> Отсюда, в силу доказанной раннее леммы, получаем <tex> r(I \cup J) = |I|</tex>. С другой стороны, <tex>|I| < |J| = r(J) \le leqslant r(I \cup J)</tex>. Противоречие. <br>
34
правки

Навигация