Порядковый тип - NiNa.Az

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

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

Определение

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

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

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

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

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

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

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

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

Примеры

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

Операции

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

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

${\displaystyle 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}}}$.

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

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

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

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

${\displaystyle (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}}$.

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

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

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

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

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

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

См. также

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

Примечания

1. Колмогоров, 1976, с. 33.
2. Laver, 1971, с. 89.
3. Just, 1996, с. 156.
4. Jech, 2002, с. 65.
5. Колмогоров, 1976, с. 33-34.
6. Just, 1996, с. 24.
7. Колмогоров, 1976, с. 34.
8. Колмогоров, 1976, с. 36.
9. Just, 1996, с. 25.
10. Faigle, 1980, с. 48.

Литература

• Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа (рус.). — Москва: Наука, 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.