205
правок
Изменения
м
Нет описания правки
|statement = <tex>M =\; \langle X,I \rangle</tex> - матроид, <tex>A \subset X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> - ранг множества <tex>A.</tex>
|proof =
Пусть существуют такие множества <tex>B, C \in I: B \subset A, C \subset \langle A \rangle, |B| = r(A) < r(\langle A \rangle) = |C|.</tex> Тогда по аксиоме замен <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 \subset A: D \in I, D\cup p \notin I.</tex> В силу аксиомы наследования можно считать, что <tex>|D| = |B|.</tex> Тогда <tex>r(A) = |D| < |B \cup p|.</tex> По аксиоме замены существует <tex>q \in (A \cup p)\setminus D : D \cup q \notin I.</tex> Если <tex>q \in B,</tex> то <tex>(D \cup q ) \subset A</tex>(противоречит максимальности множества <tex>D</tex>). Если <tex>q = p,</tex> то <tex>(D \cup p ) \in I</tex>(противоречит выбору множества <tex>D</tex>).
}}
|proof =
# Пусть <tex>\langle A \rangle \not\subset \langle B \rangle,</tex> тогда <tex>\exists x \notin \langle B \rangle, x \in \langle A \rangle.</tex> Следовательно, <tex>\exists C \in I, C \subset A : C \cup x \notin I.</tex> Но так как <tex>C \subset 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 \subset 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>
}}
