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

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

конечное подмножество . Введем на множестве А следующее отношение зависимости Z B (А). Таким образом, зависимыми будут все надмножества множества . Если , то . Если , то . Если , то . Получаем транзитивное пространство зависимости. Пример 7. Подпространство пространства зависимости Z. Рассмотрим , где действует то же отношение зависимости Z. Тогда получим индуцированное пространство зависимости Z B . В этом случае зависимыми будут

только те подмножества множества , которые были зависимы в пространстве Z. И если пространство Z транзитивно, то транзитивным будет и подпространство . Пример 8. Пусть и Z = . Такое пространство зависимости Z не транзитивно, так как и . Пространство А имеет два базиса и , которые являются и единственными минимальными порождающими множествами в . Этот пример показывает, что существуют не транзитивные пространства зависимости, в

которых минимальные порождающие множества независимы, то есть являются базисами. Пример 9. Зададим на множестве N натуральных чисел следующее отношение зависимости: Z. Получаем бесконечную строго возрастающую цепочку оболочек в Z. При получаем . Таким образом, имеем . Замечание. Понятие пространства зависимости можно и удобно определять через базу зависимости. Именно, множество B всех минимальных зависимых множеств

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

зависимости тогда и только тогда, когда множества из B непусты, конечны и не включены друг в друга. В терминах базы B можно сформулировать условие транзитивности соответствующего пространства зависимости. §2. Пространства зависимости Теорема 1. Пусть Z - произвольное пространство зависимости. Рассмотрим следующие три утверждения: X — базис в A; X — максимальное независимое подмножество в A; X — минимальное порождающее множество в

A. Тогда и . Доказательство: (i) (ii) Если X – базис, то по определению 6 X – независимое порождающее подмножество. Докажем от противного, что оно максимальное. Пусть существует независимые множества . Возьмем , тогда независимо, так как любое подмножество независимого множества независимо. Поэтому по определениям 3 и 5 , откуда , получили противоречие с условием. Поэтому X является максимальным независимым подмножеством в A. (ii) (i)