322
правки
Изменения
→Полумодулярность ранговой функции
|statement= Дан матроид <tex> M = \langle X, I \rangle</tex> и множество <tex>A \subset X</tex>. Пусть также <tex>B \subset A</tex>, <tex>B \in I</tex>, тогда существует <tex>D : B\subset D \subset A, D \in I, |D| = rg(A)</tex>.
|proof=
Пусть <tex>E</tex> {{---}} подмножество <tex>A</tex> такое, что <tex>rg(EA) = |E|, E \in I</tex> (по определению ранговой функции такое <tex>E</tex> всегда существует. Предположим, что это не так и максимальное независимое подмножество, которое мы можем получить из <tex>B</tex> добавляя элементы из <tex>A</tex> {{---}} это <tex>C</tex>, причем <tex>|C| < rg(A)</tex>. Тогда имеем: <tex>C \in I, E \in I, |C| > < |E|</tex>, следовательно существует элемент <tex>x \in E \setminus C: C \cup \{x\} \in I</tex>. Заметим также что <tex>|C \cup {x}| = |C| + 1 > |C|</tex> и <tex>x \in A</tex>, т.к. <tex>E \setminus C \subset A</tex>, <tex>B \subset C \subset C \cup \{x\}</tex>. Итак пришли к противоречию, мы получили множество большее по мощности, чем <tex>C</tex> такое, что <tex>B \subset C \subset A, C \in I</tex>, значит исходное предположение было не верно, и мы можем найти множество <tex>D</tex> удовлетворяющее необходимым условиям.
}}
