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




 

Свойство монотонности: АÍВ Þ 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 линейных порядков , чтобы в пересечении они дали множество А В.

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

 

£1 .

 

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

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

 

… £2, где 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<1 d) для i=1,…,m. (*)

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

(a, b)<j(c, d) Û b<j d или (b=d и a<1 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 не одноэлементных цепей А1, А2,…,Аn и рассмотрим множество X=A1 A2 An= . (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.

 

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-05-16 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: