10.3. Эквивалентные системы аксиом

В этом разделе мы сформулируем несколько альтернативных систем аксиом, определяющих матроид. Эти эквивалентные характеризации помогут нам в более глубоком проникновении в структуру матроидов. Начнем с эквивалентного аксиомам независимости набора.

Теорема 10.6. (Аксиомы независимости.) Набор подмножеств множества S составляет множество независимых множеств матроида тогда и только тогда, когда удовлетворяет аксиомам 1.1, 1.2 и 1.3. Если А — произвольное подмножество множества 5, то все максимальные подмножества УА, входящие в имеют одинаковую мощность.

Доказательство предлагается читателю в качестве упражнения. См. следствие 10.2.3.

Теорема 10.7. (Аксиомы баз.) Пусть — множество баз матроида. Тогда и никакое множество в не содержит в качестве собственного подмножества другое.

В.2. Если тогда существует такой, что Обратно, если -набор подмножеств S, удовлетворяющих аксиомам то для некоторого является набором независимых множеств матроида на

Доказательство. Мы уже доказали, что базы матроида удовлетворяют аксиомам (Вспомните определение базы и следствие 10.2.3.)

Пусть дан набор 33, удовлетворяющий аксиомам Покажем, что набор определенный в формулировке теоремы, является набором независимых множеств матроида на

Прежде всего заметим, что из аксиом следует существование для такого что входит в

Очевидно, что удовлетворяет аксиомам 1.1 и 1.2. Для доказательства удовлетворения аксиоме 1.3 мы сначала покажем, что все члены 33 имеют одинаковую мощность.

Допустим, что существуют Тогда, повторяя применение аксиомы мы сможем удалить из и заменить это подмножество на такое множество с что будет членом Но что противоречит аксиоме Таким образом, все члены набора имеют одинаковую мощность.

Рассмотрим теперь два любых различных члена X и Y набора с Пусть , где . Пусть

Рассмотрим множество . По аксиоме существует такой что входит в Если то и, следовательно, является членом . Поэтому аксиома 1.3 в этом случае удовлетворяется.

Если , то рассмотрим . Снова по аксиоме существует такой , что является членом Если то . Следовательно, и аксиома 1.3 удовлетворяется.

Если удалим из В" член и т. д. Поскольку не более чем через q шагов мы достигнем ситуации, в которой заменим некоторый 6,- на элемент К, посредством чего выполним аксиому 1.3.

Теорема 10.8. (Аксиомы ранга.) Функция ранга матроида М на множестве удовлетворяет аксиомам

R.1. для любого

R.3. Для любых

Обратно, если определенная на конечном множестве 5 целочисленная функция удовлетворяет аксиомам то множество является набором независимых множеств матроида на

Доказательство. Мы уже доказали в теореме 10.3, что функция ранга матроида удовлетворяет аксиомам

Для доказательства обратного предположим, что функция удовлетворяет аксиомам Из аксиомы следует, что Поэтому 0 в аксиома 1.1 удовлетворяется.

Пусть и АВ. Тогда по аксиоме получаем

Если то по аксиоме что противоречит формуле (10.3). Следовательно, и А также является членом , вследствие чего удовлетворяется аксиома 1.2.

Для доказательства аксиомы 1.3 заметим сначала, что из аксиом следует аксиома

R.3. Еслир то Пусть X и К — различные члены Предположим, что для любого . Тогда, применяя повторно аксиому получим противоречие с . Поэтому существует элемент для которого и аксиома 1.3, таким образом, удовлетворяется.

Теорема 10.9. (Аксиомы циклов.) Пусть — множество циклов матроида на множестве S. Тогда и никакое множество в не содержит другого в качестве собственного подмножества.

С.2. Если и то существует такой что

Обратно, если набор подмножеств множества удовлетворяет аксиомам то множество для всех является набором независимых множеств матроида на .

Доказательство. Мы уже доказали, что циклы матроида удовлетворяют аксиомам (теорема 10.4).

Пусть дан набор удовлетворяющий аксиомам Покажем, что набор определенный, как в формулировке теоремы, является набором независимых множеств матроида на S. Сделаем это, показывая последовательно, что удовлетворяет аксиомам 1.1, 1.2 и 1.3 (теорема 10.6).

Заметим сначала, что есть набор всех подмножеств S, не содержащие ни одного члена . Поэтому он удовлетворяет аксиомам 1.1 и 1.2.

Для доказательства того, что удовлетворяет аксиоме 1.3, рассмотрим произвольное подмножество . Пусть и различные максимальные подмножества А, принадлежащие Допуская установим противоречие.

Так как различные подмножества, Пусть Тогда, очевидно, Следовательно, существует для которого . Более того, иначе бы что противоречит принадлежности

Пусть . Заметим, что Сначала докажем:

1. . Очевидно, что Если бы тогда существовал бы такой что Более того, так как . Таким образом, — такие различные члены что . Тогда из аксиомы следует, что существует такой , что противоречит тому, что никакой член не содержит членов Следовательно,

Теперь докажем:

2. — максимальное подмножество множества А.

Допустим противное. Пусть такое максимальное подмножество множества А, что Теперь так как в противном случае что противоречит максимальности в А. Тогда Следовательно, существует такой Более того, так как иначе бы Пусть Тогда можно показать (как в доказательстве п. 1), что что противоречит максимальности в А. Таким образом, — максимальное подмножество в А.

Заметим, что построено из заменой элемента на элемент Поскольку мы можем повторить эту конструкцию конечное число раз, получив максимальное такое подмножество , что что противоречит равенству . Поэтому существует такой элемент что . Поэтому существует такой элемент что и аксиома 1.3, таким образом, удовлетворяется,