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

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

Докажем от противного, пусть не базис в , то есть . Тогда такое, что независимо и лежит в , получили противоречие с максимальностью . (ii) (iii) Если X — максимальное независимое множество в A, то всякий элемент уA либо принадлежит X, либо таков, что зависимо, а поэтому в том и другом случае, то есть Поскольку , то X - порождающее множество. Значит, - базис пространства . Докажем теперь, что оно минимально. Пусть множество . Докажем, что оно не

является порождающим для A. Возьмем , но . Тогда независимо, как подмножество множества X. Поэтому по определениям 3 и 5 и , а это значит, что Y не является порождающим множеством. Вывод: X – минимальное порождающее множество в A. (i) (iii) Справедливо, по доказанным выше утверждениям (i) (ii) и (ii) (iii). ■ Определение - обозначение 10. Для произвольного множества пространства зависимости Z обозначим множество всех максимальных независимых

подмножеств, а через - множество всех минимальных порождающих подмножеств этого множества. Из теоремы 1 вытекает, что совпадает с множеством всевозможных базисов пространства и для любого . Следующий пример показывает, что обратное включение верно не всегда. Пример 10. Рассмотрим девятиэлементное множество , которое записано в виде матрицы . Зависимыми будем считать подмножества множества , содержащие «прямые линии»: столбцы,

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

порождающим множеством. Легко заметить, что зависимо, поэтому не является базисом. Данный пример иллюстрирует, что (iii) (i) не верно в общем случае, то есть для произвольных пространств зависимости. Для любого пространства зависимости Z выполняются следующие свойства: Замещение. Если Доказательство: Пусть , . Так как зависит от , то зависит от независимого подмножества множества , то есть зависимо. Теперь, если бы , то было бы

подмножеством множества и поэтому , что противоречило бы нашему предположению. Поэтому . Возьмем . Тогда независимо, так как . Но зависимо. Откуда . Вложенность. Объединение любой системы вложенных друг в друга независимых множеств является независимым множеством, то есть - независимо, где также независимы и Доказательство: Докажем от противного. Предположим, что зависимо, тогда в нем найдется конечное зависимое подмножество :.