Изменения

Проверим справедливость третьей аксиомы для семейства <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,...\ldots,p_t\}</tex>. Если <tex>t = 1</tex>, то, очевидно, <tex>I \subset J</tex> и аксиома выполняется. Поэтому достаточно рассмотреть <tex>t \geqslant 2</tex>.

В силу нашего предположения <tex>I \cup p_i \notin \mathfrak I</tex> для любого <tex>i \in \{1,...\ldots,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,...\ldots,t\}</tex>. Ясно, что множества <tex>C_1,...\ldots,C_t</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 \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 q1q_1) \cup p_1 \cup p_j</tex>, что невозможно. Следовательно, <tex>q_1 \in C_j \cap C_1</tex> и <tex>C_j \ne C_1</tex>. Тогда по <tex>3 пункуту </tex> пункту теоремы, существует <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_10q_1) \cup p_1 \cup p_j \in \mathfrak I</tex>, что невозможно.

Следствие <tex>1 </tex> из теоремы

Пусть <tex>M = (S\langle X, I)\rangle</tex> {{---}} [[Определение матроида|матроид]]. Если <tex>X A \in I</tex> и <tex>y \notin A, y \in X</tex>, тогда <tex>X + A \cup y \in I</tex> или существует единственный цикл <tex>C \subseteq A \cup y.</tex> Более того, для любого <tex> \widehat{y} \in C, (A \cup y) \setminus \^widehat{y}\in I.</tex>

testЕсли <tex>A \cup y \notin I, </tex> тогда в нем должен существовать цикл <tex>C_1.</tex> Предположим, что существует другой цикл <tex>C_2 \subseteq A \cup y, </tex> и <tex>C_1 \ne C_2.</tex> Поскольку <tex>A \in I,</tex> тогда и <tex>C_1</tex>, и <tex>C_2</tex> одновременно содержат <tex>y</tex>. По <tex>3</tex> пункту теоремы, <tex>(C_1 \cup C_2) \setminus y</tex> содержит цикл <tex>C.</tex> Возникает противоречие, так как <tex>(C_1 \cup C_2) \setminus y \subseteq A.</tex> Поэтому, <tex>A \cup y</tex> содержит единственный цикл <tex>C.</tex>Если для какого-либо <tex>\widehat{y} \in C, (A \cup y) \setminus \widehat{y} \notin I, </tex> то <tex>(A \cup y) \setminus \widehat{y}</tex> не является независимым и содержит цикл <tex>\widehat{C}.</tex> Более того, <tex>\widehat{C} \ne C,</tex> так как <tex>\widehat{y} \notin \widehat{C}, </tex> что противоречит единственности <tex>C.</tex>}} {{Утверждение|about= Следствие <tex>2</tex> из теоремы|statement= Пусть <tex>M = \langle X, I \rangle</tex> {{---}} матроид и <tex>\mathcal{B}</tex> {{---}} семейство его баз. Тогда для любой <tex>B \in \mathcal{B}</tex> и для любого <tex>x \in X, x \notin B</tex> существует единственный цикл <tex>C \subseteq B \cup x</tex>.|proof=Пусть, напротив, <tex>B \cup x</tex> не содержит циклов. Значит, <tex>B \cup x \in I</tex>. <tex>B</tex> {{---}} база, следовательно не существует независимых множеств большей мощности, а <tex>|B \cup x| > |B|,</tex> так как <tex>x \notin B</tex> по условию. Противоречие.По предыдущему утверждению, <tex>B \cup x</tex> содержит не более одного цикла, поэтому цикл единственный.}} {{Утверждение|about= Следствие <tex>3</tex> из теоремы|statement= Пусть <tex>M = \langle X, I \rangle</tex> {{---}} матроид и <tex>\mathcal{B}</tex> {{---}} семейство его баз. Тогда для всех <tex>B, \widehat{B} \in \mathcal{B}</tex> выполнено: для любого <tex>\widehat{x} \in \widehat{B} \setminus B</tex> существует такой <tex>x \in B \setminus \widehat{B}, </tex> что <tex>(B \cup \widehat{x}) \setminus x</tex> {{---}} база.|proof=В случае, если существует <tex>x = \widehat{x}</tex>, утверждение очевидно. Рассмотрим противоположный. <tex>B</tex> {{---}} база, следовательно <tex>B \in I, </tex> при этом <tex>\widehat{x} \notin B,</tex> а <tex>B \cup \widehat{x} \notin I, \exists !C \subseteq B \cup \widehat{x}</tex> (по предыдущему утверждению). Тогда, по утверждению <tex>1</tex>, существует такой <tex>x \in C \subseteq B \cup \widehat{x}, </tex> что <tex>(B \cup \widehat{x}) \setminus x \in I.</tex><tex>x</tex> содержится в <tex>B \setminus \widehat{B}, </tex> так как <tex> \widehat{x} \notin B \setminus \widehat{B} \in I, </tex> а <tex>\widehat{x}</tex> и <tex>x</tex> содержатся в <tex>C, </tex> то есть принадлежат не являющемуся независимым множеству <tex>(B \setminus \widehat{B}) \cup \widehat{x}, </tex> при этом <tex>x \ne \widehat{x}. |B| = |(B \cup \widehat{x}) \setminus x|, </tex> следовательно <tex>(B \cup \widehat{x}) \setminus x</tex> {{---}} база.