308
правок
Изменения
Нет описания правки
}}
{{Определение
|definition = <tex> span(A) = A \cup \mathcal {f} x \in X \; |\; \forall S \subseteq A\setminus x,\ S \in I,\ |S| = r(A) :\ S \cup x \notin I \mathcal {g} </tex>
}}
|proof=Понятно, что элементы из <tex> A </tex> подходят под оба определения. Для остальных же <tex> x </tex> равенство <tex> \ r(A) = r(A \cup x) </tex> означает, что не найдётся множеств <tex> S' \subseteq A \cup x :\ S' \in I,\ |S'| > r(A). </tex> Для такого <tex> S' </tex> обязательно будет выполнено <tex> x \in S', </tex> в противном случае <tex> S' \subseteq A, </tex> откуда следует <tex> r(A) \geqslant |S'|. </tex> Следовательно для <tex> S = S' \setminus x </tex> верно <tex> S \subseteq A,\ S \in I. </tex> Из последнего получается, что <tex> r(A) \geqslant |S|, </tex> и учитывая <tex> r(A) < |S'|,\ |S| + 1 = |S'| </tex> имеем <tex> r(A) = |S|. </tex>
Иначе говоря, не должно существовать множеств <tex> S \subseteq A,\ x \notin S,\ S \in I,\ |S| = r(A):\ S' = S \cup x \in I. </tex>
}}
{{Утверждение
|statement=Для множества <tex> A \in X </tex> выполнено <tex> span(A) \subseteq \langle A \rangle. </tex>
|proof=Покажем, что следующее определение замыкания равносильно тому, которое [[Оператор замыкания для матроидов | было дано]] ранее:
: <tex>\langle A \rangle = A \cup \mathcal {f} x \in X \; |\; \exists H \subseteq A \setminus x, \; H \in I , \; |H| = r(A) :\ H \cup x \notin I \mathcal {g}</tex>
По сравнению со старым определением появилось два ограничения, нужно убедится в том, что они не существены. Сначала рассмотрим <tex> |H| = r(A). </tex>
: Пусть <tex> \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I, </tex> но <tex> |H| < r(A). </tex> По [[Ранговая функция, полумодулярность | определению ранга]] <tex> \exists D \subseteq A ,\; D \in I :\ |D| = r(A). </tex> Поскольку <tex> |H| < |D| </tex>, можно применить 3-ю аксиому матроидов несколько раз и получить <tex> H' \subseteq A :\ H \subseteq H' ,\; H' \in I ,\; |H'| = r(A). </tex>
: <tex> H' \cup x \notin I </tex> также будет выполнено, поскольку в противном случае <tex> H \cup x \notin I </tex> будет неверно (в силу 2-ой аксиомы матроидов).
Второе ограничение {{---}} <tex> H \subseteq A \setminus x </tex> вместо <tex> H \subseteq A </tex> {{---}} подразумевается само собой, поскольку в случае <tex> x \in H </tex> не могут одновременно выполнятся <tex> H \in I </tex> и <tex> H \cup x \notin I. </tex>
}}
{{Теорема
|proof =
}}
== Закрытые множества ==
