Дипломная работа: Абстрактное отношение зависимости

Для любого пространства зависимости 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 (о замене.) :