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

Пример 9.

Зададим на множестве N натуральных чисел следующее отношение зависимости:

Z .

Получаем бесконечную строго возрастающую цепочку оболочек в Z . При получаем

.

Таким образом, имеем .

Замечание.

Понятие пространства зависимости можно и удобно определять через базу зависимости. Именно, множество B всех минимальных зависимых множеств пространства зависимости Z назовем его базой . Ясно, что множества из B непусты, конечны и не содержатся друг в друге. Кроме того, любое независимое множество содержит некоторое множество базы B . Пространство Z имеет единственную базу и однозначно определяется ей. Поэтому пространства зависимости можно задавать базами.

Легко видеть, что верно следующее утверждение:

Непустое множество B подмножеств множества задает на отношение зависимости тогда и только тогда, когда множества из B непусты, конечны и не включены друг в друга.

В терминах базы B можно сформулировать условие транзитивности соответствующего пространства зависимости.

§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.

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

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