308
правок
Изменения
м
Нет описания правки
|statement = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид, <tex>A \subseteq X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> {{---}} [[Ранговая функция, полумодулярность|ранг]].
|proof =
Пусть существуют множества <tex>B, C \in I:\ B \subseteq A, C \subseteq \langle A \rangle, |B| = r(A) < r(\langle A \rangle) = |C|.</tex> Тогда по аксиоме замен<ref>[[Определение матроида | Определение матроида]], 3-я аксиома</ref> <tex>\exists p \in C \setminus B :\ B \cup p \in I.</tex> Так как <tex>B</tex> {{---}} максимально, то <tex>p \in \langle A \rangle \setminus A.</tex> По определению замыкания существует множество <tex>D \subseteq A:\ D \in I, \ D\cup p \notin I.</tex> В силу аксиомы наследования<ref>[[Определение матроида | Определение матроида]], 2-я аксиома</ref> можно считать, что <tex>|D| = |B|.</tex> Тогда <tex>r(A) = |D| < |B \cup p|.</tex> По аксиоме замены существует <tex>q \in (B \cup p)\setminus D :\ D \cup q \in I.</tex>
Если <tex>q \in B,</tex> то <tex>(D \cup q) \subseteq A</tex> (противоречит максимальности множества <tex>D</tex>). Если <tex>q = p,</tex> то <tex>(D \cup p) \in I</tex> (противоречит выбору множества <tex>D</tex>).
# <tex>\langle \langle A \rangle \rangle = \langle A \rangle </tex>
|proof =
# <tex>x \in \langle A \rangle.</tex> Тогда по определению оператора замыкания <tex>\exists C \in I, C \subseteq A :\ C \cup x \notin I.</tex> Но <tex>C \subseteq B,</tex> поэтому <tex>x \in \langle B \rangle.</tex> Ч.т.д.
# Так как <tex>q \in \langle A \cup p \rangle </tex> и <tex>q \notin \langle A \rangle,</tex> то существует независимое множество <tex>B :\ B \subseteq A \cup p, B \cup q \notin I.</tex> Так как <tex>q \notin \langle A \rangle,</tex> то <tex>p \in B, (B \setminus p)\cup q \in I.</tex> Тогда <tex>((B \setminus p)\cup q) \cup p \notin I,</tex> то есть <tex>p \in \langle A \cup q \rangle.</tex>
# Пусть Из определения понятно, что <tex> \langle A \rangle \subseteq \langle \langle A \rangle \rangle </tex>. Предположим <tex>\exists p \in \langle \langle A \rangle \rangle \setminus \langle A \rangle.</tex> Возьмем максимальное по мощности множество <tex>B \in I :\ B \subseteq A.</tex> Так как <tex>p \notin \langle A \rangle,</tex> то по определению замыкания <tex>B \cup p \in I.</tex> СледовательноТогда, последовательно применив вышеуказанную лемму, дважды [[Ранговая функция, полумодулярность | определение ранга]] и снова лемму, получим <tex>r(\langle A \rangle) = r(\langle \langle A \rangle \rangle) \ge geqslant |B \cup p| = r(A) + 1 = r(\langle A \rangle) + 1,</tex> что невозможно.
}}
