Изменения

{{Теорема

|id=theorem

|proof=

Рассмотрим множество <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 (B), D_B \in I</tex> (по [[#lemma|лемме]] такое возможно). Далее дополним <tex>D_B</tex> элементами из <tex>A \cup B \setminus D_B</tex> до множества <tex>D_\cup : |D_\cup| = rg(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>. Заметим также, что <tex>(D_\cup \setminus D_B) \cup D_\cap \subset A</tex>, <tex>(D_\cup \setminus D_B) \cup D_\cap \in I</tex> (по [[Определение матроида]]), значит <tex>r(A) \ge |(D_\cup \setminus D_B) \cup D_\cap| = |D_\cup| - |D_B| + |D_\cap| = r(A \cup B) - r(B) + r(A \cap B) </tex>. Что и требовалось доказать.

}}