Цитата из: Mrrl on 14-05-2006, 23:23:18
1) знаком ли кто-нибудь с таким объектом?
2) какие реализации известны?
У меня получиловь построить следующую реализацию.
Берём класс множеств, состоящих из ординалов.
Ординалы делим на чётные и нечётные следующим образом: если у ординала х нет такого элемента у, что x=уU{y}, назовём x чётным, следующий за ним называем нечётным, следующий опять чётный, и так далее.
Для двух множеств берём самый ранний из ординалов, лежащий в одном из них, и не лежащий в другом.
Если этот ординал чётен, то содержащее его множество меньше другого, иначе оно больше другого.
Данное упорядочивание отвечает требуемым условиям.
Цитата:
3) любые ли два класса K1, K2 с описанными свойствами эквивалентны (т.е. между ними существует монотонная биекция)?
Да. Поскольку такие классы не являются множествами, существует биекция между каждым из них и классом ординалов. Так что, достаточно показать, что для любых двух таких порядков на классе ординалов, можно найти биекцию этого класса на себя, переводящую один из этих порядков в другой.
Будем её строить следующим образом.
Пустое множество соответствует пустому множеству, f(0) = 0.
Пусть определены образы всех ординалов, содержащихся в данном. Пусть А - множество ординалов, содержащихся в данном и меньших него, B - содержащихся в данном и больших него (для порядка №1). Согласно свойствам порядков, найдётся ординал, больший f(A) и меньший f(B) (для порядка №2). В качестве образа данного ординала выберем самый ранний из таких ординалов.
Докажем, что это биекция, т. е. у каждого из ординалов есть прообраз.
Пусть имеется ординал x, и у всех элементов x есть прообразы. Пусть A - множество элементов x, меньших х, B - множество элементов x, больших x (для порядка №2). Пусть y - самый ранний из элементов, больший f-1(A) и меньший f-1(B).(в смысле порядка №1).
Докажем, что f(y)= x.
Поскольку f переводит порядок №1 в №2, и по определению y, для любого z, принадлежащего y, найдётся t, такое, что или f(t) принадлежит A, и t>=z, или f(t) принадлежит B, и t<=z. (в смысле порядка №1). Причём, если z<y, то, поскольку для любого s, лежащего в f-1(B) s>y>z, то соответствующее t принадлежит f-1(A), и, аналогично, если z>y, то соответствующее t лежит в f-1(B)
То есть, если z принадлежит y, то если z<y, то f(z)<=f(t)<x, а если z>y, то f(z)>=f(t)>x. По определению f, f(y)=x.
Цитата:
4) верно ли, что любое упорядоченное множество вкладывается в K?
Да. Доказывается аналогично предыдущему пункту. Более того, вложить можно не только упорядоченное множество, но и упорядоченный класс.
