Изменения
Нет описания правки
об аксиоматизации матроида базами
|statement= Пусть семейство <tex>\mathcal B</tex> подмножеств конечного непустого множества <tex>E</tex> удовлетворяет условиям всем условиям [[Теорема о базах|теоремы о базах]], где играет роль <tex>B_s</tex>. Тогда <tex>\mathcal B</tex> является семейством баз однозначно определенного матроида на <tex>E</tex>.
|proof= Покажем, что все <tex>\mathcal B</tex>-множества равномощны. Пусть <tex>B_1, B_2\in\mathcal B, |B_1|=t, B_1=\{b_1,b_2,\ldots ,b_t\}</tex>. По третьему условию [[Теорема о базах|теоремы о базах]] существует <tex>c_1\in B_2</tex> такой, что <tex>\{c_1,b_2,\ldots,b_t\}\in\mathcal B</tex>. <tex>c_1\notin\{b_2,\ldots,b_t\}</tex> в силу условия 2. Аналогично, существует <tex>c_2\in B_2</tex> такой, что <tex>\{c_1,c_2,b_3,\ldots,b_t\}\in\mathcal B</tex> и <tex>c_2\notin\{c_1,b_3,\ldots,b_t\}</tex>. Продолжая этот процесс, получим <tex>\{c_1,c_2,\ldots,c_t\}\in\mathcal B</tex> для некоторых попарно различных элементов <tex>c_1,c_2,\ldots,c_t\in B_2</tex>. В силу аксиомы 2 второго условия [[Теорема о базах|теоремы о базах]] получаем <tex>\{c_1,c_2,\ldots,c_t\}=B_2</tex>, т.е. <tex>|B_2|=t=|B_1|</tex>.<br>
Подмножество <tex>A</tex> из <tex>E</tex> будем называть <tex>\mathcal B</tex>''-независимым'', если оно содержится в некотором <tex>\mathcal B</tex>-множестве. Ясно, что <tex>\mathcal B</tex>-множества - это максимальные <tex>\mathcal B</tex>-независимые множества. Обозначим через <tex>\mathcal I</tex> совокупность всех <tex>\mathcal B</tex>-независимых множеств.<br>
Заметим, что семейство <tex>\mathcal I</tex> удовлетворяет условиям аксиомам 1 и 2 [[Определение матроида|определения матроида]]. Осталось проверить, что семейство <tex>\mathcal I</tex> удовлетворяет третьему условиютретьей аксиоме. Пусть <tex>I,J\in\mathcal I, |I|<|J|</tex>. Зафиксируем <tex>\mathcal B</tex>-множество <tex>B_2</tex>, содержащее <tex>J</tex>. Среди <tex>\mathcal B</tex>-множеств, содержащих <tex>\mathcal I</tex>, выберем такое <tex>\mathcal B</tex>-множество <tex>B_1</tex>, для которого пересечение <tex>B_1\cap B_2</tex> содержит наибольшее возможное число элементов. Покажем, что <tex>B_1\backslash I\subseteq B_2</tex>. Действительно, если существует <tex>b_1\in B_1\backslash I</tex> такой, что <tex>b_1\notin B_2</tex>, то по условию 3 [[Теорема о базах|теоремы о базах]] существует <tex>b_2\in B_2</tex>, для которого <tex>B=(B_1\backslash b_1)\cup b_2\in\mathcal B</tex> и <tex>b_1\neq b_2</tex>, т.к. <tex>b_1\notin B_2</tex>, а <tex>b_2\in B_2</tex>. Тогда <tex>|B\cap B_2|>|B_1\cap B_2|</tex>, что невозможно, поскольку <tex>I\subseteq B</tex>.<br>
Таким образом, <tex>B_1\backslash I,J\subseteq B_2</tex>, причем <tex>|B_1\backslash I|+|J|=|B_1|-|I|+|J|>|B_1|=|B_2|</tex>. Следовательно, существует <tex>p\in(B_1\backslash I)\cap J</tex>. Так как <tex>I\cup p\subseteq B_1</tex> и <tex>p\in J\backslash I</tex>, элемент <tex>p</tex> является искомым.
}}
