Порядковый тип

Порядковый тип — изоморфный тип частично упорядоченного множества. Неформально говоря порядковый тип — это характеристика, определяющее упорядоченное множество с точностью до изоморфизма, то есть два упорядоченных множества изоморфны тогда и только тогда, когда у них один и тот же порядковый тип.

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

Определение

При формальном определении порядкового типа возникают те же трудности, что и при определении мощности множества.

Наивный подход

Простейшим подходом является определение порядкового типа множества как класс изоморфности частично упорядоченных множеств. Назовём порядковым типом частично упорядоченного множества $A$ совокупность всех множеств, изоморфных данному. Однако такое определение недопустимо в ZF, поскольку такая совокупность множеств не является множеством в смысле ZF. Для определения порядкового типа в ZF требуется иной подход.

Вполне упорядоченные множества

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

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

Трюк Даны Скотта

Определение порядкового типа в ZF для общего случая произвольного частично упорядоченного множества использует ту же самую конструкцию, что и определение мощности множества в ZF — трюк Даны Скотта. Порядковый тип множества определяется не как класс всех изоморфных ему упорядоченных множеств, а как подмножество данного класса, состоящее из всех множеств минимального ранга.

Примеры

• Порядковый тип конечного линейно упорядоченного множества отождествляется с количеством его элементов и, таким образом, является натуральным числом. Поэтому класс всех порядковых типов образует расширение натуральных чисел.
• Порядковый тип множества натуральных чисел обозначается $\omega$.
• Порядковый тип множества рациональных чисел обозначается $\eta$.
• Порядковый тип множества действительных чисел обозначается $\lambda$.

Операции

На классе порядковых типов можно определить операции сложения и умножения подобно стандартным арифметическим операциям:

• Сложение. Пусть $A,B$ не пересекающиеся частично упорядоченные множества. Упорядоченной суммой множеств $A$ и $B$ называется их объединение $A\cup B$, упорядоченное следующим отношением порядка:

$x\leq y\Leftrightarrow {\begin{cases}x\leq _{A}y&x,y\in A\\x\leq _{B}y&x,y\in B\\\top &x\in A,y\in B\\\bot &x\in B,y\in A\end{cases}}$.

Упорядоченная сумма обозначается $A+B$ или $A\oplus B$. Порядковый тип упорядоченной суммы зависит только от порядковых типов её слагаемых и не зависит от конкретных упорядоченных множеств, что позволяет определить эту операцию на порядковых типах. Сумма произвольных порядковых типов $\alpha$ и $\beta$ определяется как порядковый тип упорядоченной суммы $A$ и $B$, где $A,B$ имеют порядковые типы $\alpha ,\beta$ соответственно. Более кратко:

$\operatorname {ord} A+\operatorname {ord} B=\operatorname {ord} (A+B)$

Как можно видеть, сумма порядковых типов не является коммутативной операцией. Простейший пример: $1+\omega =\omega$ — порядковый тип $\mathbb {N}$, однако $\omega +1\neq \omega$ — порядковый тип $\mathbb {N} \cup \{+\infty \}$.

• Умножение. Пусть $A,B$ некоторые частично упорядоченные множества. Упорядоченным (антилексикографическим) произведением множеств $A$ и $B$ называется их декартово произведение $A\times B$, упорядоченное следующим отношением порядка:

$(a_{1},b_{1})\leq (a_{2},b_{2})\Leftrightarrow b_{1}\leq b_{2}\lor b_{1}=b_{2}\land a_{1}\leq a_{2}$.

Упорядоченное произведение обозначается $A\cdot B$ или $A\otimes ^{a}B$. Порядковый тип упорядоченного произведения зависит только от порядковых типов его множителей и не зависит от конкретных упорядоченных множеств, что позволяет определить эту операцию на порядковых типах. Произведение произвольных порядковых типов $\alpha$ и $\beta$ определяется как порядковый тип упорядоченного произведения $A$ и $B$, где $A,B$ имеют порядковые типы $\alpha ,\beta$ соответственно. Более кратко:

$\operatorname {ord} A\cdot \operatorname {ord} B=\operatorname {ord} (A\cdot B)$

Как можно видеть, произведение порядковых типов не является коммутативной операцией. Простейший пример: $2\omega =\omega$, однако $\omega \cdot 2=\omega +\omega \neq \omega$.

Также часто рассматривают двойственный порядковый тип. Двойственным упорядоченным множеством к $(A,\leq )$ называется упорядоченное множество $(A,\geq )$ и обозначается как $A^{*}$. Порядковый тип $A^{*}$ зависит только от порядкового типа $A$, поэтому для порядкового типа можно также определить понятие двойственного порядкового типа:

$(\operatorname {ord} A)^{*}=\operatorname {ord} (A^{*})$

Двойственный порядковый тип к натуральному числу равен тому же натуральному числу $n^{*}=n$. Двойственный порядковый тип к $\omega$ есть порядковый тип множества отрицательных чисел $\omega ^{*}=\operatorname {ord} (-\mathbb {N} )$. Сумма $\omega ^{*}+\omega$ равна порядковому типу множества целых чисел. При этом сумма $\omega +\omega ^{*}$ не равна порядковому типу целых чисел. Двойственный порядковый тип к двойственному даёт тот же порядковый тип: $\alpha ^{**}=\alpha$.

См. также

• Изоморфный тип
• Мощность множества
• Ординал

Литература

• Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа (рус.). — Москва: Наука, 1976. — 543 с.
• Just W., Weese M. Discovering Modern Set Theory. I: The Basics (англ.). — American Mathematical Societ, 1996. — 210 p.
• Jech T. Set theory (англ.). — Springer, 2002. — 769 p.
• Laver R. On Fraisse's Order Type Conjecture (англ.) // Annals of Mathematics : журнал. — 1971. — January (vol. 93, iss. 1). — P. 89–111.
• Faigle U. Geometries on Partially Ordered Sets (англ.) // Journal of Combinatorial Theory : журнал. — 1980. — Vol. 28. — P. 26–51.