Изменения

|definition = Пусть <tex>M =\; <\langle X,I>\rangle</tex> {{-- -}} [[Определение матроида|матроид]]. Тогда '''замыкание ''' (англ. ''closure)''' ) множества <tex>A \subset subseteq X</tex> {{- --}} это множество <tex><\langle A> \subset rangle \subseteq X</tex> такое, что <tex><\langle A> \rangle = A \cup (\{x\in X \; |\; \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I \}</tex>}} <!---ну хз кто догадался так записать, я исправляю такое без разрешения.)))--->Другими словами, замыкание множества <tex> A </tex> {{---}} это все элементы из <tex> A, </tex> а также такие <tex> x \in X, </tex> которые при добавлении к некоторым независимым подмножествам <tex> A </tex> не оставляют их независимыми.  {{Лемма|statement = Пусть <tex>M =\; \forall langle X,I \rangle</tex> {{---}} матроид, <tex>A \subseteq X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> {{---}} [[Ранговая функция, полумодулярность|ранг]].|proof =Пусть существуют множества <tex>B , D \in I:\subset B \subseteq A ,\ D \subseteq \langle A \rangle,\ |B| = r(A) < r(\langle A \rangle) = |D|.</tex> Тогда по [[Определение матроида | 3-ей аксиоме]] <tex>\exists p \in D \setminus B : \ B \cup p \in I .</tex> Так как <tex>B</tex> {{---}} максимальное независимое множество из <tex> A </tex>, то <tex>p \notin A,</tex> то есть <tex> p \in \langle A \rangle \setminus A. </tex> Согласно определению замыкания возьмём максимальное по мощности множество <tex>H \subseteq A:\ H \in I,\ H\cup p \notin I.</tex> Поскольку <tex> |H| \leqslant |B| < |B \cup p|,</tex> то по аксиоме замены существует <tex>q \in (B \cup p)\setminus H :\ H \cup q \; in I.</tex>  Если <tex>q \in B ,</tex> то <tex>(H \cup x q) \subseteq A,\ </tex> но <tex> (H \cup q) \cup p \notin I </tex> в силу <tex> H \cup p \notin I}</tex> (противоречие с максимальностью множества <tex>H</tex>). Если <tex>q = p,</tex> то <tex>(H \cup p)\in I</tex> (противоречит выбору множества <tex>H</tex>).