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

Для любого нелинейного порядка конечного упорядоченного множества будет справедлива теорема.

Теорема 1. Любой нелинейный порядок ≤ на конечном упорядоченном множестве А можно продолжить до линейных порядков, дающих в пересечении исходный порядок ≤.

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

Возьмём произвольное конечное упорядоченное множество А с нелинейным порядком £.

Рассмотрим 2 его произвольных элемента а и b.

Если они несравнимы, то доопределим

(или можно взять ).

Если при этом элемент x£ а, а элемент y ³b, то .

В нашем примере b и с несравнимы. Доопределим

. При этом, а £b и c£e, значит, .

Если <A,

> - всё ещё не цепь, то, беря новую пару несравнимых элементов, аналогично доопределяем до “большего” порядка на А.

Через несколько таких шагов получим линейный порядок на A, содержащий исходный порядок £.

Если бы мы доопределили b

a, тогда получили бы другой линейный порядок, содержащий исходный порядок £. В пересечении и í линейных порядков элементы a и b окажутся несравнимыми.

Аналогичным образом можно получить и другие линейные порядки, пересечение которых образует множество А.

Ч.т.д.

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

Наименьшее число линейных порядков на А, дающих в пересечении данный порядок £, называется размерностью А. И обозначается d(A).

d(A)=2.

Корректность определения: каждое конечное упорядоченное множество имеет размерность. По определению конечного упорядоченного множества в нём будет конечное число элементов. А линейный порядок получается путём различных перестановок этих элементов. Если число элементов n, то число перестановок будет

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

Цепи имеют размерность 1. Известно, что размерность всех множеств с количеством элементов n (где n£5), кроме цепей, равна 2.

Среди 6-элементных множеств существует только одно с размерностью 3.

Остальные 6-элементные множества имеют размерность 2.

Дадим понятие перестановочно упорядоченного множества.

Пусть имеется множество А, состоящее из n элементов. А={1, 2 ,3 ,…, n}. Рассмотрим некоторую перестановку этого множества. (Например, (2, 1, 4, 3, …, n, n-1 )).

Эта перестановка задаёт свой линейный порядок на А, наряду с естественным числовым порядком, пересечение которых и определяет перестановочно упорядоченное множество < A,

>.

При этом, а

в Û а<в и в данной перестановке n-ой степени число а встречается раньше числа в.

Конечные упорядоченные множества размерности 1 и 2 получаются с точностью до изоморфизма, как перестановочно упорядоченные множества.

Например, цепи Z: d(Z)=1

соответствует перестановка (1,2,3).

А множеству P: d(P)=2

соответствует перестановка (1,6,5,4,3,2).

Перестановочно упорядоченные множества, отличные от цепей, - это в точности упорядоченные множества размерности 2.

Например, перестановка (5,3,1,2,6,4,7) задаёт упорядоченное множество размерности 2:

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

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