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

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

Имеем , получили противоречие с независимостью . Максимальность. Любое независимое множество содержится в максимальном независимом множестве. Доказательство: Пусть - произвольное независимое множество в . Образуем множество Z : всех независимых множеств, содержащих . Относительно множество является упорядоченным множеством, удовлетворяющим по свойству вложенности, условию леммы Цорна. Тогда по лемме Цорна в существует

максимальный элемен . Теорема 2. Любое пространство зависимости обладает базисом. Доказательство: Возьмем пустое множество, оно независимо. По свойству максимальности оно должно содержаться в некотором максимальном независимом множестве, которое по теореме 1 является базисом. §3. Транзитивность Особый интерес представляют транзитивные пространства зависимости. Важным результатом является доказательство инвариантности

размерности любого транзитивного пространства зависимости. Докажем некоторые свойства, справедливые для транзитивных пространств зависимости Z. Свойство 1: зависит от . Доказательство: зависит от , то есть , и . Рассмотрим , тогда - независимо и - зависимо, а , получаем, что , поэтому . Имеем . По определению 8 любое подмножество зависит от Свойство 2: Если зависит от , а зависит от , то зависит от . Доказательство: Запишем условие,

используя свойство 1 , а , тогда очевидно, что .■ Свойство 3: Если X — минимальное порождающее множество в A, то X — базис в A. Доказательство: Пусть X — минимальное порождающее множество в A. Покажем, что оно не может быть зависимым, так как в этом случае его можно было бы заменить собственным подмножеством, все еще порождающим A. Действительно, в силу транзитивности отношения зависимости, любое множество, порождающее множество X, будет

так же порождать и множество A. Следовательно, X - независимое порождающее множество, которое по определению 6 является базисом. Свойство 4: для любого . Доказательство: Следует из свойства 3. Свойство 5 (о замене.) : Если X — независимое множество и Y — порождающее множество в A, то существует такое подмножество множества Y, что и — базис для A. Доказательство: Рассмотрим систему J таких независимых подмножеств Z множества A, что . Так как X

независимо, то такие множества существуют; кроме того, если — некоторое линейно упорядоченное множество множеств из J, то его объединение снова принадлежит J, поскольку Z удовлетворяет условию , и если Z зависимо, то некоторое конечное подмножество множества Z должно было бы быть зависимым; это подмножество содержалось бы в некотором множестве в противоречии с тем фактом, что все независимы. По лемме Цорна J имеет максимальный