Корректность определения: каждое конечное упорядоченное множество имеет размерность. По определению конечного упорядоченного множества в нём будет конечное число элементов. А линейный порядок получается путём различных перестановок этих элементов. Если число элементов 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, > - конечные упорядоченные множества.