Абстрактное отношение зависимости — страница 8

  • Просмотров 5683
  • Скачиваний 76
  • Размер файла 765
    Кб

что По (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о:

. Доказательство: вытекает из свойства 40; Свойство 7о: . Доказательство: . §4. Связь транзитивных отношений зависимости с операторами замыкания Транзитивное отношение зависимости также может быть описано с помощью алгебраического оператора замыкания некоторого типа. Для начала сформулируем определения используемых понятий. Определение 13. Множество E подмножеств множества A называется системой замыканий, если E и система E

замкнута относительно пересечений, т. е. ∩D E для любой непустого подмножества D E Определение 14. Оператором замыкания на множестве A называется отображение J множества B (A) в себя, обладающее следующими свойствами: J. 1. Если , то J(X)J(Y); J. 2. XJ(X); J. 3. JJ(X) = J(X), для всех X, Y B (A). Определение 15. Оператор замыкания J на множестве A называется алгебраическим, если для любых и влечет для некоторого конечного подмножества множества . Определение 16.

Система замыканий называется алгебраической, если только соответствующий оператор замыкания является алгебраическим Следует отметить теорему о взаимосвязи между системами замыканий и операторами замыканий. Теорема 5. Каждая система замыканий E на множестве определяет оператор замыкания J на по правилу J(X) = ∩{Y E | YX}. Обратно, каждый оператор замыкания J на определяет систему замыканий E J. Следующая теорема показывает связь