Изменения

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

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

Нет изменений в размере, 20:30, 28 июня 2011
Нет описания правки
Рассмотрим множество <tex>C_1.</tex> Для него верно <tex>p_1 \in C_1 \subseteq I \cup p_1.</tex> В силу <tex>\mathfrak C</tex>-независимости <tex>J</tex> существует <tex>q_1 \in I \setminus J</tex> такой, что <tex>q_1 \in C_1.</tex> Рассмотрим теперь множество <tex>(I \setminus q_1) \cup p_1.</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_2C^') \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 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>, что невозможно.
Анонимный участник

Навигация