Абстрактное отношение зависимости (стр. 4 из 9)

Рассмотрим еще одно множество

, оно является минимальным порождающим, так как если исключить из него хотя бы один элемент, то оно уже не будет порождающим множеством. Легко заметить, что зависимо, поэтому не является базисом. Данный пример иллюстрирует, что (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.