Изменения

|statement=Пусть дан матроид <tex> M = \langle X, I \rangle</tex>, и <tex>r: 2^X \to \{0\} \cup \mathbb{N}</tex> {{- --}} его ранговая функция. Тогда для любых <tex>A, B \in 2^X</tex> выполняется следующее: <br>1) #<tex> 0 \le leqslant r(A) \le leqslant |A| </tex> <br>2) #<tex> A \in B \to r(A) \le leqslant r(B) </tex> <br>3) #Неравенство полумодулярности: <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \le leqslant r(A) + r(B)</tex>

1) #Очевидно из определения: максимальное независимое подмножество по мощности не может быть больше самого множества и меньше нуля. <br>2) #Пусть <tex>C \in A</tex> {{- --}} максимальное независимое подмножество. Т.к. <tex>A \in B</tex>, то <tex>C \in B</tex> {{- --}} независимое подмножество. Поэтому <tex>r(B) \ge geqslant |C|</tex> по определению, а значит <tex>r(B) \ge geqslant r(A)</tex> <br>3) #Доказано выше.}}