143
правки
Изменения
м
русский язык
Пусть семейство <tex>\mathfrak C</tex> удовлетворяет условию теоремы. Множество <tex>\mathbb I \nsubseteq \mathbb E</tex> назовем <tex>\mathfrak C</tex>-независимым, если оно не содержит ни одного из множеств <tex>\mathbb C \in \mathfrak C</tex>. Через <tex>\mathfrak I</tex> обозначим семейство всех <tex>\mathfrak C</teX>-независимых множеств, содержащихся в <tex>\mathbb E</tex>. Проверим, что семейство <tex>\mathfrak I</tex> удовлетворяет аксиомам из определения матроида.
Поскольку <tex>\varnothing \notin \mathfrak C</tex>, имеем <tex>\varnothing \in \mathfrak I</tex>, очевидно и первая аксиома , очевидно, выполняется.
Очевидно, что если <tex>\mathbb A \in \mathfrak I</tex> и <tex>\mathbb B \subset \mathbb A</tex> то <tex>\mathbb B \in \mathfrak I</tex>, и, следовательно, вторая аксиома выполнена.
Проверим справедливость третьей аксиомы для семейства <tex>\mathfrak I</tex>. Предположим, что существуют множества <tex>\mathbb I, \mathbb J \in \mathfrak I</tex> такие, что <tex>|\mathbb I|<|\mathbb J|</tex>, для которых третья аксиома не выполнена. Среди всех таких пар <tex>\mathbb I, \mathbb J</tex> выберем ту, у которой мощность <tex>|\mathbb I \cup \mathbb J|</tex> минимальна. Положим <tex>\mathbb J \setminus \mathbb I = \{p_1,...,p_t\}</tex>. Если <tex>t = 1</tex>, то, очевидно, <tex>\mathbb I \subset \mathbb J</tex> и аксиома выполняется. Поэтому имеем <tex>t \ge 2</tex>.
