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

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

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

Определение

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

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

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

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

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

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

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

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

Примеры

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

Операции

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

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

$x\le y\iff \{\begin{array}{cc}x{\le }_{A}y& x,y\in A\\ x{\le }_{B}y& x,y\in B\\ \mathrm{\top }& x\in A,y\in B\\ \mathrm{\perp }& x\in B,y\in A\end{array}$.

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

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

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

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

$(a_1,b_1)\le (a_2,b_2)\iff b_1\le b_2\vee b_1=b_2\wedge a_1\le a_2$.

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

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

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

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

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья