Изменения

|statement=Пусть <tex>r: 2^X \to \{0\} \cup \mathbb{N}</tex> удовлетворяет условиям теоремы ниже, <tex> B \subset A \subseteq in 2^X</tex>, <tex>r(B) = |B|</tex>, и <tex> A \setminus B = \{p_1, \ldots p_t\}</tex>. Если <tex>r(B \cup p_i) = |B|</tex> для любого <tex> i = 1, \ldots , t</tex>, то <tex>r(A) = |B|</tex>

:<tex>|B| = r(B) = r(B \cup p_1 \cup \ldots \cup p_j) \leqslant r(B \cup p_1 \cup \ldots \cup p_jp_{j+1}) \leqslant r(B \cup p_1 \cup \ldots \cup p_j) + r(B \cup p_jp_{j+1}) -r(B) = |B| + |B| - |B| = |B| </tex>. :Следовательно, <tex>r(B \cup p_1 \cup \ldots \cup p_jp_{j+1}) = |B|</tex>. Переход доказан, а значит, <tex>r(B \cup p_1 \cup \ldots \cup p_t) = |B|</tex>.

|statement= Пусть некоторая функция <tex>r: A \in 2^X \to \{0\} \cup \mathbb{N}</tex>, где <tex>2^X</tex> {{---}} конечное непустое множество, удовлетворяет условиям:

# <tex> A \subseteq B \implies Rightarrow r(A) \leqslant r(B) </tex>.

|proof= Подмножество <tex>I \subseteq in 2^X</tex> назовем <tex>r</tex>-независимым, если выполняется <tex>r(I) = |I|</tex>. Обозначим через <tex>\mathcal{I}\subseteq 2^X</tex> множество всех <tex>r</tex>-независимых подмножеств из <tex>2^X</tex>. Докажем, что <tex>\mathcal{I}</tex> удовлетворяет [[Определение матроида|аксиомам независимого множества]] 1, 2 и 3:

# В силу (1) выполняется <tex>r(\emptyset)=0</tex>, следовательно <tex> \emptyset \subseteq in \mathcal{I}</tex>.# Пусть <tex> I \subseteq in \mathcal{I}</tex> и <tex>J \subseteq I</tex>. Предположим от противного, что <tex>r(J) < |J|</tex>. Тогда, используя (1) и (3), получаем: <tex>|I| = r(I) = r(J \cup (I \setminus J)) \leqslant r(J) + r(I \setminus J) - r(\emptyset) < |J| + |I \setminus J| = |I|</tex>, что невозможно. Следовательно, <tex>r(J) = |J|</tex>, т.е. <tex> J \subseteq in \mathcal{I} </tex>

Все три аксиомы выполняются на <tex>\mathcal{I}</tex>, соответственно, семейство <tex>\mathcal{I}</tex> является семейством независимых множеств некоторого матроида <tex> M = \langle X, \mathcal{I} \rangle</tex>. Осталось проверить, что исходная функция <tex>r</tex> совпадает с ранговой функцией матроида <tex>M</tex>. Для Так как, по определению, ранговая функция равна мощности максимального независимого подмножества множества (мощности базы множества), для этого надо достаточно доказать, что для любой [[Теорема о базах|базы]] <tex>B</tex> произвольного множества <tex>A \subseteq in 2^X, B \subseteq A</tex> выполняется <tex> r(A) = |B| </tex>. Пусть <tex>B</tex> {{---}} [[Теорема о базах|база]] множества <tex>A \subseteq in 2^X</tex>. По определению <tex>r </tex> имеем <tex> r(B) = |B|</tex> и <tex>B</tex> {{---}} максимальное <tex>r</tex>-независимое подмножество из <tex>A</tex>. Если <tex>A=B</tex>, то, очевидно, <tex>r(A)=r(B).</tex> Поэтому пусть <tex>B \in A</tex>. Пусть <tex> A \setminus B = \{p_1, \ldots ,p_t\}</tex>. В силу максимальности <tex>B</tex> для любого <tex>i = 1, \ldots,t</tex> множество <tex>B \cup p_i</tex> не является <tex>r</tex>-независимым, т.е. <tex>r(B \cup p_i) < |B \cup p_i|</tex>. Тогда имеем: <tex> |B| = r(B) \leqslant r(B \cup p_i) < |B \cup p_i| = |B| + 1 </tex>,