Изменения
Нет описания правки
Очевидно, что если <tex>A \in \mathfrak I</tex> и <tex>B \subset A</tex> то <tex>B \in \mathfrak I</tex>, и, следовательно, вторая аксиома выполнена.
Проверим справедливость третьей аксиомы для семейства <tex>\mathfrak I</tex>. Предположим, что существуют множества <tex>I, J \in \mathfrak I</tex> такие, что <tex>|I|<|J|</tex>, для которых третья аксиома не выполнена. Среди всех таких пар <tex>I, J</tex> выберем ту, у которой мощность <tex>|I \cup J|</tex> минимальна. Положим <tex>J \setminus I = \{p_1,...,p_t\}</tex>. Если <tex>t = 1</tex>, то, очевидно, <tex>I \subset J</tex> и аксиома выполняется. Поэтому достаточно рассмотреть <tex>t \ge geqslant 2</tex>.
В силу нашего предположения <tex>I \cup p_i \notin \mathfrak I</tex> для любого <tex>i \in \{1,...,t\}</tex>. Следовательно, существует <tex>C_i \in \mathfrak C</tex> такое, что <tex>C_i \subseteq I \cup p_i</tex> и в силу <tex>\mathfrak C</tex>-независимости множества <tex>I</tex> имеем <tex>p_i \in C_i</tex> для любого <tex>i \in \{1,...,t\}</tex>. Ясно, что множества <tex>C_1,...,C_t</tex> попарно различны.
Если <tex>(I \setminus q_1) \cup p_1 \notin \mathfrak I</tex>, то существует <tex>C' \in \mathfrak C</tex>, для которого существует такое <tex>C'' \in \mathfrak C,</tex> что <tex>C'' \subseteq (C_1 \cup C') \setminus p_1 \subseteq I.</tex> Пришли к противоречию с условием <tex>I \in \mathfrak I.</tex>
Пусть <tex>(I \setminus q_1) \cup p_1 \in \mathfrak I</tex>. Заметим, что <tex>|((I \setminus q_1) \cup p_1) \cup J| < |I \cup J|</tex>. Поэтому в силу выбора пары <tex>I, J</tex> для пары <tex>(I \setminus q_1) \cup p_1, J</tex> существует элемент <tex>p_j</tex>, где <tex>j \ge geqslant 2</tex>, такой, что <tex>(I \setminus q_1) \cup p_1 \cup p_j \in \mathfrak I</tex>. Возьмем множество <tex>C_j \in \mathfrak C</tex>. Для него выполняется <tex>p_j \in C_j \subseteq I \cup p_j.</tex> Если <tex>q_1 \notin C_j</tex>, то <tex>C_j \subseteq (I \setminus q_1) \cup p_j \subseteq (I \setminus q1) \cup p_1 \cup p_j</tex>, что невозможно. Следовательно, <tex>q_1 \in C_j \cap C_1</tex> и <tex>C_j \ne C_1</tex>. Тогда по 3 пункуту теоремы, существует <tex>C \in \mathfrak C</tex>, для которого <tex>C \subseteq (C_j \cup C_1) \setminus q_1 \subseteq (C_j \setminus q_1) \cup (C_1 \setminus q_1) \subseteq ((I \setminus q_1) \cup p_j) \cup ((I \setminus q_1) \cup p_1)</tex>, которое равно <tex>(I \setminus q_10) \cup p_1 \cup p_j \in \mathfrak I</tex>, что невозможно.
Итак, семейство <tex>\mathfrak I</tex> удовлетворяет аксиомам матроида. Следовательно, существует матроид <tex>M</tex> на множестве <tex>E</tex>, для которого семейство <tex>\mathfrak I</tex> является семейством независимых множеств. Из определения <tex>\mathfrak C</tex>-независимости легко следует, что семейство <tex>\mathfrak C</tex> совпадает с множеством циклов матроида <tex>M</tex>
