Свойства размерности конечных упорядоченных множеств

 

Свойство монотонности:  А Í В Þ d(A) £ d(B) для любых конечных упорядоченного множества В и его непустого подмножества А.

 

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

Пусть < B, ≤ >- конечное упорядоченное множество размерности n. Имеем,  для линейных порядков £_i  на В. На подмножестве А рассмотрим индуцированный порядок  из В, т.е. ограничение отношения £ на А.

Рассмотрим ограничения линейных порядков £_i на А – они также линейны и в пересечении дадут порядок .

Значит, по определению размерности упорядоченного множества размерность <A, > не превосходит n.

Ч.т.д.

 

Свойство размерности дизъюнктивного объединения: Пусть А и В – конечные упорядоченные множества и X =A B . Тогда d(X)=max(d(A), d(B)), если хотя бы одно из множеств А или В не является цепью, и d (X )=2, если А и В – цепи.

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

Дизъюнктивным объединением упорядоченных множеств А и В (А В) называется упорядоченное множество, состоящее из непересекающихся объединяемых множеств, на каждом из которых сохраняется свой порядок, а элементы из разных множеств попарно несравнимы.

Пусть <A, £> и <B, > - конечные упорядоченные множества.

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

Пусть для определённости n³m и n³2.

В результате объединения А и В получается упорядоченное множество, состоящее из всех элементов А и всех элементов В. Значит, одному линейному порядку на А В соответствует два линейных порядка: один для А £_i и один для В . Линейные порядки на А В должны содержать все n линейных порядков £_i и все m линейных порядков , чтобы в пересечении они дали множество А В.

Первый линейный порядок на А В определим следующим образом:

 

£₁ … .

 

Т.е. мы взяли первый линейный порядок на А и приписали к нему справа первый линейный порядок на В.

Второй линейный порядок на А В получим, взяв из множества А линейный порядок £₂, а из множества В, если m³2, то линейный порядок , если же m=1, то линейный порядок .  Но сейчас линейный порядок из множества А поместим за линейным порядком из множества В, для того, чтобы элементы из разных множеств были попарно несравнимы:

 

 … £₂, где j=1 при m=1 и j=2 при m³2.

 

Аналогичным образом будем получать остальные линейные порядки на А В:

£_i …             при i£m

£_i …             при i>m.

 

Получим n линейных порядков, пересечение которых даёт множество А В. Т.е. =n=max(d(A), d(B)).     

 Ч.т.д.

 

 

Теорема 2. Размерность прямого произведения двух конечных упорядоченных множеств А и В меньше либо равна сумме их размерностей:

.

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

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

Пусть даны конечные упорядоченные множества <А, £> и <В, £>, размерности которых соответственно равны 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<^j d или (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<_I c и b<^j d) или (a<_I c и b=d) или (a=c и b<^j d)

для 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₁  A₂  … 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.