Изменения

Перейти к: навигация, поиск

Аксиоматизация матроида циклами

32 байта добавлено, 00:37, 26 июня 2011
м
косметика
Проверим справедливость третьей аксиомы для семейства <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>.
В силу нашего предположения <tex>\mathbb I \cup p_i \notin \mathfrak I</tex> для любого <tex>i \in \{1,...,t\}</tex>. Следовательно, существует <tex>\mathbb C_i \in \mathfrak C</tex> такое, что <tex>\mathbb C_i \subseteq \mathbb I \cup p_i</tex> и в силу <tex>\mathfrak C</tex>-независимости множества <tex>\mathbb I</tex> имеем <tex>p_i \in \mathbb C_i</tex> для любого <tex>i=\in \{1,...,t\}</tex>. Ясно, что множества <tex>\mathbb C_1,...,\mathbb C_t</tex> попарно различны.
Рассмотрим множество <tex>\mathbb C_1</tex>. Для него верно <tex>p_1 \in \mathbb C_1 \subseteq \mathbb I \cup p_1</tex>. В силу <tex>\mathfrak C</tex>-независимости <tex>\mathbb J</tex> существует <tex>q_1 \in \mathbb I \setminus \mathbb J</tex> такой, что <tex>q_1 \in \mathbb C_1</tex>. Рассмотрим теперь множество <tex>(\mathbb I \setminus q_1) \cup p_1</tex>.
Если <tex>(\mathbb I \setminus q_1) \cup p_1 \notin \mathfrak I</tex>, то существует <tex>\mathbb C' \in \mathfrak C</tex>, длф для которого существует такой <tex>\mathbb C'' \in \mathfrak C</tex>, что <tex>\mathbb C'' \subseteq (\mathbb C_1 \cup \mathbb C_2) \setminus p_1 \subseteq \mathbb I</tex>. Пришли к противоречию с условием <tex>\mathbb I \in \mathfrak I</tex>.
Пусть <tex>(\mathbb I \setminus q_1) \cup p_1 \in \mathfrak I</tex>. Заметим, что <tex>|((\mathbb I \setminus q_1) \cup p_1) \cup \mathbb J| < |\mathbb I \cup \mathbb J|</tex>. Поэтому в силу выбора пары <tex>\mathbb I, \mathbb J</tex> для пары <tex>(\mathbb I \setminus q_1) \cup p_1, J</tex> существует элемент <tex>p_j</tex>, где <tex>j \ge 2</tex>, такой, что <tex>(\mathbb I \setminus q_1) \cup p_1 \cup p_j \in \mathfrak I</tex>. Возьмем множество <tex>\mathbb C_j \in \mathfrak C</tex>. Для него выполняется <tex>p_j \in \mathbb C_j \subseteq \mathbb I \cup p_j</tex>. Если <tex>q_1 \notin \mathbb C_j</tex>, то <tex>\mathbb C_j \subseteq (\mathbb I \setminus q_1) \cup p_j \subseteq (\mathbb I \setminus q1) \cup p_1 \cup p_j</tex>, что невозможно. Следовательно, <tex>q_1 \in \mathbb C_j \cap C_1</tex> и <tex>\mathbb C_j \ne \mathbb C_1</tex>. Тогда по 3 пункуту теоремы, существует <tex>\mathbb C \in \mathfrak C</tex>, для которого <tex>\mathbb C \subseteq (\mathbb C_j \cup \mathbb C_1) \setminus q_1 \subseteq (\mathbb C_j \setminus q_1) \cup (\mathbb C_1 \setminus q_1) \subseteq ((\mathbb I \setminus q_1) \cup p_j) \cup ((\mathbb I \setminus q_1) \cup p_1)</tex>, которое равно <tex>(\mathbb I \setminus q_10) \cup p_1 \cup p_j \in \mathfrak I</tex>, что невозможно.
143
правки

Навигация