Порядковое число

Отпатрулированная версия этой страницы, проверенная 11 июня 2011, была основана на этой версии.

Порядковое число, или трансфинитное число, или ординал в теории множеств — некоторое обобщение понятия натурального числа «за пределы бесконечности». Впервые введены Георгом Кантором в 1897 году с целью классификации вполне упорядоченных множеств. Играют ключевую роль в доказательстве многих теорем теории множеств, в особенности в связи со связанным с ними принципом трансфинитной индукции.

Определение

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

Назовём множество $x$ транзитивным, если каждый элемент $x$ является подмножеством $x$ : $\mathrm {Trans} (x)\Leftrightarrow \forall t(t\in x\to t\subseteq x)$ .
Удовлетворяющее аксиоме фундирования множество называется ординалом, или порядковым числом, если оно само и каждый его элемент транзитивны: $\mathrm {Ord} (x)\Leftrightarrow \mathrm {Trans} (x)\wedge \forall t(t\in x\to \mathrm {Trans} (t))$ .

Заметим, что аксиома фундирования существенно используется в этом определении, что необходимо учитывать при работе с аксиоматическими системами, отличными от системы Цермело — Френкеля.

Для обозначения порядковых чисел обычно используются строчные греческие буквы $\alpha ,\beta ,\dots .$ Данная статья придерживается таких обозначений.

Свойства

Если $\alpha$ — порядковое число, то каждый элемент $\alpha$ — порядковое число.
Для любых $\alpha ,\beta$ выполняется ровно одно из следующих соотношений: $\alpha \in \beta ,\alpha =\beta ,\beta \in \alpha .$
Любое множество порядковых чисел вполне упорядочено отношением $\in$ (в частности, любое порядковое число, рассматриваемое как множество, вполне упорядочено отношением $\in$ ), при этом $\bigcap x$ — наименьший элемент множества $x$ , $\bigcup x$ — порядковое число, большее или равное любому из элементов множества $x$ . Выражения $\alpha <\beta$ и $\alpha \in \beta$ для порядковых чисел эквивалентны. Ниже подразумевается, что порядковые числа сравниваются с помощью отношения $\in .$
Для любого вполне упорядоченного множества $x$ существует единственное порядковое число, изоморфное $x$ (в частности, для любого множества порядковых чисел существует единственное порядковое число, изоморфное ему).
Любое $\alpha$ совпадает с множеством всех порядковых чисел, меньших чем $\alpha$ .
Начальный сегмент любого порядкового числа является порядковым числом.
Пустое множество $\varnothing$ — наименьшее порядковое число (а значит, оно является элементом любого другого порядкового числа).
$\alpha$ называется регулярным (синоним: непредельным), если оно равно $\varnothing$ либо существует непосредственно предшествующее ему $\beta ;$ другими словами, если существует $\beta <\alpha ,$ но между ними нельзя вставить другое порядковое число $\beta <\gamma <\alpha .$ В последнем случае говорят, что $\alpha$ — порядковое число, следующее за $\beta$ и пишут $\alpha =\beta {\dot {+}}1$ (иногда просто $\alpha =\beta +1,$ что оказывается согласованным с обозначением для суммы порядковых чисел).
Порядковые числа, не являющиеся непредельными, называются предельными порядковыми числами (иногда $\varnothing$ тоже относят к предельным порядковым числам).
$\alpha {\dot {+}}1=\alpha \cup \{\alpha \}.$
Множество всех конечных порядковых чисел изоморфно множеству неотрицательных целых чисел, и для них используются такие же обозначения, как для целых чисел. При этом операции сложения, умножения и возведения в степень для порядковых чисел переходят в соответствующие операции для целых чисел. Несколько первых порядковых чисел:

{\begin{aligned}&0=\varnothing ;\\&1=\{0\}=0\cup \{0\}=\{\varnothing \};\\&2=\{0,1\}=1\cup \{1\}=\{\varnothing ,\{\varnothing \}\};\\&3=\{0,1,2\}=2\cup \{2\}=\{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\};\\&\dots \end{aligned}}

Множество всех конечных порядковых чисел обозначается $\omega .$ Оно является наименьшим предельным порядковым числом и наименьшим бесконечным (а именно, счётным) порядковым числом. Следующим за ним порядковым числом является $\omega {\dot {+}}1=\omega \cup \{\omega \}.$
Условие конечности $\alpha$ можно записать как $\alpha <\omega$ или, что то же самое, $\alpha \in \omega .$
Существует бесконечное множество порядковых чисел, но не существует множества всех порядковых чисел. Иначе говоря, совокупность всех порядковых чисел является собственно классом.
Каждое множество порядковых чисел $A$ ограничено сверху и имеет точную верхнюю грань, которая обозначается $\sup A.$ При этом $A\subseteq \sup A.$
Если $\alpha$ — предельное порядковое число или $\varnothing$ , то $\sup \alpha =\alpha ,$ иначе $\sup \alpha <\alpha .$
Точная верхняя грань счётного множества счётных порядковых чисел счётна.
Каждое порядковое число имеет единственное представление в канторовской нормальной форме.

Арифметика порядковых чисел

Определения операций

Сумма порядковых чисел рекурсивно определяется следующим образом:

{\begin{aligned}&\alpha +0=\alpha \\&\alpha +(\beta {\dot {+}}1)=(\alpha +\beta ){\dot {+}}1\\&\alpha +\gamma =\sup\{\alpha +\beta |\beta <\gamma \},\end{aligned}}

где третье правило применяется в случае, когда

\gamma

является предельным порядковым числом.

Используя те же обозначения, определим операцию умножения:

{\begin{aligned}&\alpha \cdot 0=0\\&\alpha \cdot (\beta {\dot {+}}1)=\alpha \cdot \beta +\alpha \\&\alpha \cdot \gamma =\sup\{\alpha \cdot \beta |\beta <\gamma \}.\end{aligned}}

И операцию возведения в степень:

{\begin{aligned}&\alpha ^{0}=1\\&\alpha ^{\beta {\dot {+}}1}=\alpha ^{\beta }\cdot \alpha \\&\alpha ^{\gamma }=\sup\{\alpha ^{\beta }|\beta <\gamma \}.\end{aligned}}

Свойства операций

Сложение порядковых чисел некоммутативно; в частности, $1+\omega =\omega \neq \omega +1.$
Сложение порядковых чисел ассоциативно: $\alpha +(\beta +\gamma )=(\alpha +\beta )+\gamma ,$ что позволяет записывать сумму нескольких слагаемых без скобок.
Сумма возрастает при росте правого слагаемого и не убывает при росте левого слагаемого: из $\beta _{1}>\beta _{2}$ следует $\alpha +\beta _{1}>\alpha +\beta _{2}$ и $\beta _{1}+\alpha \geqslant \beta _{2}+\alpha .$
Если $\alpha \geqslant \beta ,$ то существует единственный ординал $\gamma$ , для которого $\beta +\gamma =\alpha .$
Умножение порядковых чисел некоммутативно; в частности, $2\cdot \omega =\omega \neq \omega \cdot 2.$
Умножение порядковых чисел ассоциативно: $\alpha \cdot (\beta \cdot \gamma )=(\alpha \cdot \beta )\cdot \gamma ,$ что позволяет записывать произведение нескольких сомножителей без скобок.
Для сложения и умножения выполняется левая дистрибутивность: $\alpha \cdot (\beta +\gamma )=\alpha \cdot \beta +\alpha \cdot \gamma .$
$\alpha +0=0+\alpha =\alpha .$
$\alpha +1=\alpha {\dot {+}}1.$
$\alpha \in \omega \leftrightarrow \alpha +\omega =\omega .$
$\alpha \cdot 0=0\cdot \alpha =0.$
$\alpha \cdot 1=1\cdot \alpha =\alpha .$
$\alpha \in \omega \land \alpha \neq 0\leftrightarrow \alpha \cdot \omega =\omega .$
$\alpha +\beta =0\leftrightarrow \alpha =0\land \beta =0.$
$\alpha \cdot \beta =0\leftrightarrow \alpha =0\lor \beta =0.$
$\alpha ^{0}=1.$
$\alpha ^{1}=\alpha .$
$\alpha \neq 0\leftrightarrow 0^{\alpha }=0.$
$1^{\alpha }=1.$
$\alpha \in \omega \land \alpha >1\leftrightarrow \alpha ^{\omega }=\omega .$
$\alpha ^{\beta }\cdot \alpha ^{\gamma }=\alpha ^{\beta +\gamma }.$
$(\alpha ^{\beta })^{\gamma }=\alpha ^{\beta \cdot \gamma }.$
$\alpha >1\land \beta >\gamma \leftrightarrow \alpha ^{\beta }>\alpha ^{\gamma }.$
$\beta \in \omega \to \alpha +\beta =\alpha \underbrace {{\dot {+}}1{\dot {+}}1{\dot {+}}\dots {\dot {+}}1} _{\beta }.$
$\beta \in \omega \to \alpha \cdot \beta =0\underbrace {+\alpha +\alpha +\dots +\alpha } _{\beta }.$
$\beta \in \omega \to \alpha ^{\beta }=1\underbrace {\cdot \alpha \cdot \alpha \cdot \dots \cdot \alpha } _{\beta }.$
В случае конечности аргументов сложение, умножение и возведение в степень переходят в соответствующие операции для целых чисел (с конечными результатами).
В случае счётности аргументов результаты сложения, умножения и возведения в степень также являются счётными.