Быстрый поиск

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

Свойство 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 имеет максимальный элемент М; в силу максимальности каждый элемент множества Y либо принадлежит М, либо зависит от М, откуда . Этим доказано, что М — базис в A. Так как , то М имеет вид , где удовлетворяет условиям .■

Определение 11.

Пространство зависимости Z называется конечномерным, если любое его независимое множество конечно.

Теорема 3.

Пусть Z - транзитивное пространство зависимости. Тогда любые два базиса в этом пространстве равномощны.

Доказательство:

Рассмотрим сначала случай конечномерного пространства .

Пусть В, С — любые два базиса в А, их существование обеспечивается теоремой 2, и , , , где различные элементы обозначены различными буквами или снабжены различными индексами. Применим индукцию по max (r, s).

Если r = 0 или s = 0, то или , и . Поэтому можно предполагать, что r ≥ 1, s ≥ 1, без ограничения общности будем считать, что r > s, так что на самом деле r > 1.

Предположим, что базисы будут равномощными для любого t < r

По лемме о замене множество можно дополнить до базиса D элементами базиса С, скажем

, t ≤ s < r.

Теперь пересечение D c В состоит из n + 1 элемента, и D содержит, кроме того, еще t (< r) элементов, тогда как В содержит, кроме этого пересечения, еще r - 1 элементов, так что по предположению индукции , то есть .

Поскольку r > 1, отсюда вытекает, что t ≥ 1, и поэтому пересечение D с С содержит не меньше чем n+1 элементов. Используя еще раз предположение индукции, находим, что и, следовательно, r = s и базисы В и С равномощны.

Далее, пусть В - конечный базис в . Тогда и любой другой базис С пространства будет конечным. Действительно, В выражается через конечное множество элементов в силу транзитивности будет порождающим и независимым множеством в , то есть .

Наконец, если базисы В и С бесконечны. Каждый элемент из В зависит от некоторого конечного подмножества базиса С, и наоборот. Мощность множества всех конечных подмножеств всякого бесконечного множества равна мощности самого множества. Поэтому мощности В и С совпадают.■

Теорема 4.

Пусть Z - произвольное пространство зависимости, тогда следующие условия эквивалентны

(i) Z транзитивно;

(ii) для любого конечного ;

(iii) конечных и Z

(iv) для любого конечного .

Доказательство:

(i) (ii) Справедливо по теореме 3 и примеру 7.

(ii) (iii) Возьмем , так что - независимы и . Допустим, что утверждение Z неверно. Тогда Z. Рассмотрим . Имеем . Но Z, поэтому Z . По (ii) имеем. Но - противоречие.

(iii) (ii) Докажем от противного. Пусть . Можно считать, что . Тогда по (iii) независимо. Получили противоречие с максимальностью

(iii) (i) Нужно доказать равенство для произвольного .

Возьмем и покажем, что Так как , то Пусть существует , тогда независимо и существует Z и Z . Расширяя в можно предположить, что По (ii) , то есть . Поэтому по (iii) Z . видим, что . Значит, . Получаем противоречие с тем, что Следовательно, , то сеть .

Теперь достаточно показать, что . Пусть , тогда зависимо, расширяя в можно предположить, что , кроме того , тогда по (ii) . независимо, поэтому . По (iii) Z . видим, что . Значит, , получили противоречие с максимальностью . Следовательно, , обратное включение очевидно, поэтому .