§2. Пространства зависимости

Теорема 1.

Пусть Z - произвольное пространство зависимости. Рассмотрим следующие три утверждения:

(i) X -- базис в A;

(ii) X -- максимальное независимое подмножество в A;

(iii) X -- минимальное порождающее множество в A.

Тогда и .

Доказательство:

(i) (ii) Если X - базис, то по определению 6 X - независимое порождающее подмножество. Докажем от противного, что оно максимальное. Пусть существует независимые множества . Возьмем , тогда независимо, так как любое подмножество независимого множества независимо. Поэтому по определениям 3 и 5 , откуда , получили противоречие с условием. Поэтому X является максимальным независимым подмножеством в A.

(ii) (i) Докажем от противного, пусть не базис в , то есть . Тогда такое, что независимо и лежит в , получили противоречие с максимальностью .

(ii) (iii) Если X -- максимальное независимое множество в A, то всякий элемент уA либо принадлежит X, либо таков, что зависимо, а поэтому в том и другом случае, то есть Поскольку , то X - порождающее множество. Значит, - базис пространства .

Докажем теперь, что оно минимально. Пусть множество . Докажем, что оно не является порождающим для A. Возьмем , но . Тогда независимо, как подмножество множества X. Поэтому по определениям 3 и 5 и , а это значит, что Y не является порождающим множеством. Вывод: X - минимальное порождающее множество в A.

(i) (iii) Справедливо, по доказанным выше утверждениям (i) (ii) и (ii) (iii). ¦

Определение - обозначение 10.

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

Из теоремы 1 вытекает, что совпадает с множеством всевозможных базисов пространства и для любого .

Следующий пример показывает, что обратное включение верно не всегда.

Пример 10.

Рассмотрим девятиэлементное множество , которое записано в виде матрицы . Зависимыми будем считать подмножества множества , содержащие «прямые линии»: столбцы, строки или диагонали матрицы .

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

Рассмотрим еще одно множество , оно является минимальным порождающим, так как если исключить из него хотя бы один элемент, то оно уже не будет порождающим множеством. Легко заметить, что зависимо, поэтому не является базисом. Данный пример иллюстрирует, что (iii) (i) не верно в общем случае, то есть для произвольных пространств зависимости.

Для любого пространства зависимости Z выполняются следующие свойства:

Замещение. Если

Доказательство:

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

Вложенность. Объединение любой системы вложенных друг в друга независимых множеств является независимым множеством, то есть - независимо, где также независимы и

Доказательство:

Докажем от противного. Предположим, что зависимо, тогда в нем найдется конечное зависимое подмножество :. Имеем , получили противоречие с независимостью .

Максимальность. Любое независимое множество содержится в максимальном независимом множестве.

Доказательство:

Пусть - произвольное независимое множество в . Образуем множество Z : всех независимых множеств, содержащих . Относительно множество является упорядоченным множеством, удовлетворяющим по свойству вложенности, условию леммы Цорна. Тогда по лемме Цорна в существует максимальный элемен .

Теорема 2.

Любое пространство зависимости обладает базисом.

Доказательство:

Возьмем пустое множество, оно независимо. По свойству максимальности оно должно содержаться в некотором максимальном независимом множестве, которое по теореме 1 является базисом.

§3. Транзитивность

Особый интерес представляют транзитивные пространства зависимости. Важным результатом является доказательство инвариантности размерности любого транзитивного пространства зависимости.

Докажем некоторые свойства, справедливые для транзитивных пространств зависимости Z.

Свойство 1: зависит от .

Доказательство:

зависит от , то есть , и . Рассмотрим , тогда - независимо и - зависимо, а , получаем, что , поэтому . Имеем .

По определению 8 любое подмножество зависит от

Свойство 2: Если зависит от , а зависит от , то зависит от .

Доказательство:

Запишем условие, используя свойство 1 , а , тогда очевидно, что .¦

Свойство 3: Если X -- минимальное порождающее множество в A, то X -- базис в A.

Доказательство:

Пусть X -- минимальное порождающее множество в A. Покажем, что оно не может быть зависимым, так как в этом случае его можно было бы заменить собственным подмножеством, все еще порождающим A. Действительно, в силу транзитивности отношения зависимости, любое множество, порождающее множество X, будет так же порождать и множество A. Следовательно, X - независимое порождающее множество, которое по определению 6 является базисом.

Свойство 4: для любого .

Доказательство: Следует из свойства 3.

Свойство 5 (о замене.) :

Если X -- независимое множество и Y -- порождающее множество в A, то существует такое подмножество множества Y, что и -- базис для A.

Доказательство:

Рассмотрим систему J таких независимых подмножеств Z множества A, что .

Так как X независимо, то такие множества существуют; кроме того, если -- некоторое линейно упорядоченное множество множеств из J, то его объединение снова принадлежит J, поскольку Z удовлетворяет условию , и если Z зависимо, то некоторое конечное подмножество множества Z должно было бы быть зависимым; это подмножество содержалось бы в некотором множестве в противоречии с тем фактом, что все независимы.

По лемме Цорна J имеет максимальный элемент М; в силу максимальности каждый элемент множества Y либо принадлежит М, либо зависит от М, откуда . Этим доказано, что М -- базис в A. Так как , то М имеет вид , где удовлетворяет условиям .¦

Определение 11.

Пространство зависимости Z называется конечномерным, если любое его независимое множество конечно.

Теорема 3.

Пусть Z - транзитивное пространство зависимости. Тогда любые два базиса в этом пространстве равномощны.

Доказательство:

Рассмотрим сначала случай конечномерного пространства .

Пусть В, С -- любые два базиса в А, их существование обеспечивается теоремой 2, и , , , где различные элементы обозначены различными буквами или снабжены различными индексами. Применим индукцию по max (r, s).

Если r = 0 или s = 0, то или , и . Поэтому можно предполагать, что r ? 1, s ? 1, без ограничения общности будем считать, что r > s, так что на самом деле r > 1.

Предположим, что базисы будут равномощными для любого t < r

По лемме о замене множество можно дополнить до базиса D элементами базиса С, скажем

, t ? s < r.

Теперь пересечение D c В состоит из n + 1 элемента, и D содержит, кроме того, еще t (< r) элементов, тогда как В содержит, кроме этого пересечения, еще r - 1 элементов, так что по предположению индукции , то есть .

Поскольку r > 1, отсюда вытекает, что t ? 1, и поэтому пересечение D с С содержит не меньше чем n+1 элементов. Используя еще раз предположение индукции, находим, что и, следовательно, r = s и базисы В и С равномощны.

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

Наконец, если базисы В и С бесконечны. Каждый элемент из В зависит от некоторого конечного подмножества базиса С, и наоборот. Мощность множества всех конечных подмножеств всякого бесконечного множества равна мощности самого множества. Поэтому мощности В и С совпадают.¦

Теорема 4.

Пусть Z - произвольное пространство зависимости, тогда следующие условия эквивалентны

(i) Z транзитивно;

(ii) для любого конечного ;

(iii) конечных и Z

Z;

(iv) для любого конечного .

Доказательство:

(i) (ii) Справедливо по теореме 3 и примеру 7.

(ii) (iii) Возьмем , так что - независимы и . Допустим, что утверждение Z неверно. Тогда Z. Рассмотрим . Имеем . Но Z, поэтому Z . По (ii) имеем. Но - противоречие.

(iii) (ii) Докажем от противного. Пусть . Можно считать, что . Тогда по (iii) независимо. Получили противоречие с максимальностью

(iii) (i) Нужно доказать равенство для произвольного .

Возьмем и покажем, что Так как , то Пусть существует , тогда независимо и существует Z и Z . Расширяя в можно предположить, что По (ii) , то есть . Поэтому по (iii) Z . видим, что . Значит, . Получаем противоречие с тем, что Следовательно, , то сеть .

Теперь достаточно показать, что . Пусть , тогда зависимо, расширяя в можно предположить, что , кроме того , тогда по (ii) . независимо, поэтому . По (iii) Z . видим, что . Значит, , получили противоречие с максимальностью . Следовательно, , обратное включение очевидно, поэтому .

(iv) (ii) В силу теорем 1 и 3 и доказанной эквивалентности

(i) (ii).¦

Далее будем рассматривать произвольное конечномерное транзитивное пространство зависимости Z.

Определение 12.

Мощность максимального независимого подмножества данного множества называется рангом этого множества: .

Будем рассматривать конечные подмножества .

Имеют место следующие свойства.

Свойство 1^о: Z .

Доказательство: Z .

Свойство 2^о: Z .

Доказательство: Z, возьмем , тогда по свойству 1^о и . Обратное утверждение следует из определения 13.

Свойства 3^о - 7^о сформулированы для .

Свойство 3^о: .

Доказательство: Ясно, что , и так как число элементов любого подмножества не больше числа элементов самого множества, то данное свойство выполняется.

Свойство 4^о: .

Доказательство: следует из того, что любое независимое подмножество в можно продолжить до максимального независимого подмножества в ;

Свойство 5^о: .

Доказательство:

Пусть Тогда И затем . Имеем .

Свойство 6^о: .

Доказательство: вытекает из свойства 4⁰;

Свойство 7^о: .

Доказательство:

.