Абстрактное отношение зависимости (стр. 3 из 9)
Пример 8.
Пусть
и Z = 
. Такое пространство зависимости 
Z 
не транзитивно, так как 
и 
. Пространство А имеет два базиса 
и 
, которые являются и единственными минимальными порождающими множествами в 
.Этот пример показывает, что существуют не транзитивные пространства зависимости, в которых минимальные порождающие множества независимы, то есть являются базисами.
Пример 9.
Зададим на множестве N натуральных чисел следующее отношение зависимости:
Z 
.
Получаем бесконечную строго возрастающую цепочку оболочек в 
Z . При
получаем 
.Таким образом, имеем
.Замечание.
Понятие пространства зависимости можно и удобно определять через базу зависимости. Именно, множество B всех минимальных зависимых множеств пространства зависимости 
Z назовем его базой. Ясно, что множества из B непусты, конечны и не содержатся друг в друге. Кроме того, любое независимое множество содержит некоторое множество базы B. Пространство Z имеет единственную базу и однозначно определяется ей. Поэтому пространства зависимости можно задавать базами.
Легко видеть, что верно следующее утверждение:
Непустое множество B подмножеств множества 
задает на 
отношение зависимости тогда и только тогда, когда множества из B непусты, конечны и не включены друг в друга.
В терминах базы B можно сформулировать условие транзитивности соответствующего пространства зависимости.
Теорема 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.
Рассмотрим девятиэлементное множество
, которое записано в виде матрицы 
. Зависимыми будем считать подмножества множества , содержащие «прямые линии»: столбцы, строки или диагонали матрицы 
.Рассмотрим множества
и 
, они будет максимальными независимыми, так как не содержат прямых и при добавлении любого элемента из , не лежащего в них, становятся зависимыми. Здесь максимальные независимые множества содержат разное количество элементов.