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

дипломная работа

§2.Определение размерности упорядоченного множества

Напомним, что такое цепь на примере диаграммы Хассе для конечного упорядоченного множества <A,>. Здесь порядок будет линейным.

Примером антицепи может служить множество:

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

Например, нелинейный порядок на А

можно доупорядочить до следующих линейных порядков:

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

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

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

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

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

Если они несравнимы, то доопределим (или можно взять).

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

В нашем примере b и с несравнимы. Доопределим . При этом, а b и c e, значит, .

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

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

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

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

Ч.т.д.

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

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

d(A)=2.

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

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

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

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

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

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

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

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

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

Например, цепи : 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:

Делись добром ;)