Изменения

|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| = rgr(A)</tex>.

Пусть <tex>E</tex> {{---}} подмножество <tex>A</tex> такое, что <tex>rgr(A) = |E|, E \in I</tex> (по определению ранговой функции такое <tex>E</tex> всегда существует. Предположим, что это не так и максимальное независимое подмножество, которое мы можем получить из <tex>B</tex> добавляя элементы из <tex>A</tex> {{---}} это <tex>C</tex>, причем <tex>|C| < rgr(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> удовлетворяющее необходимым условиям.

Рассмотрим множество <tex>D_\cap \subset A \cap B : D_\cap \in I, |D_\cap| = r(A \cap B)</tex>, такое всегда существует по определению <tex>r</tex>. Дополним множество <tex>D_\cap</tex> элементами из <tex>B \setminus D_\cap</tex> до множества <tex>D_B : |D_B| = rg r (B), D_B \in I</tex> (по [[#lemma|лемме]] такое возможно).

Далее дополним <tex>D_B</tex> элементами из <tex>A \cup B \setminus D_B</tex> до множества <tex>D_\cup : |D_\cup| = rgr(A \cup B), D_\cup \in I</tex>. Заметим, что на последнем шаге будут добавляться только элемента из <tex>A</tex>, т.к. пусть на том этапе мы взяли <tex>x \in B</tex>, тогда <tex>\{x\} \cup D_B \subset D_\cup, D_\cup \in I </tex>, следовательно <tex>\{x\} \cup D_B \in I</tex> (по [[Определение матроида]]), а также<tex>|\{x\} \cup D_B| = |D_B| + 1 = r(B) + 1</tex>, что невозможно по определению <tex>r</tex>.