Размерность конечных упорядоченных множеств (стр. 3 из 3)

.

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

Дадим сначала несколько определений.

Пусть даны конечные упорядоченные множества <А, £> и <В, £>, размерности которых соответственно равны m и n. Поэтому

, для некоторых линейных порядков £_iна А и

для линейных порядков на В.

Определим покоординатно порядок на

:

(a, b)<(c, d) Û (a < c и b £ d) или (a £ c и b < d).

Определим m линейных порядков на

по первой компоненте:

(a, b)<_i(c, d) Û a<_i c или (a=c и b<¹ d) для i=1,…,m. (*)

Аналогично определим n линейных порядков на

по второй компоненте:

(a, b)<^j(c, d) Ûb<^jd или (b=d и a<₁ c) для j=1,…,n. (**)

Исходя из этих определений, порядок на

можно определить и следующим образом:

(a, b)<(c, d)Û(a<_ic и b£^j d ) или (a£_I c и b<^j d) (***)

для i=1,…,m и для j=1,…,n.

Для завершения доказательства достаточно показать, что имеет место равенство:

Тогда по определению размерности конечного упорядоченного множества получим

.

Требуется доказать, что для любых (a,b) и (c,d) из

:

(a, b)<(c, d) Û(a, b)<_i(c, d) и (a, b)<^j(c, d).

Для " (a,b) и (c,d) из

не умоляя общности, будем считать, что

(a, b)<(c, d)

(a<_I c и b£^j d) или (a£_I c и b<^j d) для i=1,…,m идля j=1,…,n.

Отсюда вследствие того, что x£y выполняется тогда и только тогда, когда x<y или x=y, следует равносильность:

Û(a<_Ic и b<^jd) или (a<_Ic и b=d) или (a=c и b<^jd)

для i=1,…,m и для j=1,…,n

для i=1,…,m и для j=1,…,n.

Эта система равносильна тому, что элементы (a,b) и (c,d) сравнимы как по первой, так и по второй компоненте. И порядок на

равен пересечению его линейных порядков.

А т.к. размерность – это наименьшее число линейных порядков, дающих в пересечении множество, то

.

Ч.т.д.

Теорема 3. ЕслиА и В – не одноэлементные множества, причём А- решётка, а В –цепь, то размерность их прямого произведения на единицу больше размерности решётки:

.

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

(по теореме 2).

Покажем, что выполняется и

.

Возьмём любую цепь Z из множества цепей, пересечение которых образует решётку. Каждой такой цепи (а их

) во множестве цепей, пересечение которых образует множество

, будет соответствовать своя цепь, все первые компоненты которой находятся в таком же соответствии, как и элементы цепи Z .

Но во множестве

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

, появится еще одна цепь.

Ч.т.д.

Теорема 4.

решётка X, размерности n.

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

Возьмём n не одноэлементных цепей А₁, А₂,…,А_n и рассмотрим множество X=A₁

A2

… A_n= . (n-1) раз применяя теорему 3 получаем, что d(X)=n.

Ч.т.д.

Теорема 5.Размерность множества всех подмножеств ß(M) множества М равна мощности множества М, т.е.

d(ß(M))=

.

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

1) Покажем, что ß(M) @

, где D={0,1}.

- будем рассматривать, как множество n-ок, состоящих из 0 и 1.

М={1,2,3,…,n}.

2) Чтобы доказать, что ß(M) и

изоморфны, нужно установить взаимно однозначное соответствие.

Т.е. нужно показать, что для любого подмножества X множества М существует n-ка, состоящая из 0 и 1. И для любой n-ки существует подмножество Y множества М.

3) Выделим во множестве М подмножество X и составим по нему n-ку таким образом:

на место 1-ой компоненты n-ки поставим 1, если первый элемент множества М входит и в его подмножество X;

и 0, если 1-ый элемент множества М не входит в подмножество X.

Аналогичным образом определим все остальные компоненты n-ки.

Из нашего примера:

X (0,1,1,0,1,0…0)

n компонент

4) И, наоборот, возьмём произвольную n-ку. Например, (0,1,0,1,0…0). И поставим ей в соответствие подмножество Y множества М по тому же принципу:

если к-ая компонента равна 1, то к-ый элемент множества М входит в подмножество Y;

если же к-ая компонента равна 0, то к-ый элемент множества М не входит в подмножество Y.

Из примера получаем подмножество Y={2,4}.

5) Т.о. из ß(M)@

следует, что d(ß(M))=d( ) n

Получили, что d(ß(M))=

.

Ч.т.д.

Литература

1. Беран Л. Упорядоченные множества: Популярные лекции по математике. Вып. 55. – М.: Наука, 1981.

2. Биркгоф Г. Теория решёток. – М.: Наука, 1984.

3. Вечтомов Е. М. Теория решёток: учебно-методическая разработка спецкурса. – Киров: КГПИ, 1995.

4. Гретцер Г. Общая теория решёток. – М.: Мир, 1982.

5. Оре О. Теория графов. - М.: Наука, 1980.