Дипломная работа: Размерность конечных упорядоченных множеств

Пусть для определённости 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<_i c и 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) сравнимы как по первой, так и по второй компоненте. И порядок на равен пересечению его линейных порядков.

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

Ч.т.д.