Введение в теорию множеств

Ординалы

Показывать лекцию целиком

Как мы уже говорили, ординалом называется порядковый тип вполне упорядоченного множества, то есть класс всех изоморфных ему упорядоченных множеств (естественно, они будут вполне упорядоченными).

На ординалах естественно определяется линейный порядок. Чтобы сравнить два ординала $$\alpha$$ и $$\beta$$, возьмем их представители $$A$$ и $$B$$. Применим теорему 22 и посмотрим, какой из трех случаев ( $$A$$ изоморфно начальному отрезку $$B$$, отличному от всего $$B$$ ; множества $$A$$ и $$B$$ изоморфны; $$B$$ изоморфно начальному отрезку $$A$$, отличному от всего $$A$$ ) имеет место. В первом случае $$\alpha\hm<\beta$$, во втором $$\alpha\hm=\beta$$, в третьем $$\alpha\hm>\beta$$.

Мы отвлекаемся от трудностей, связанных с основаниями теории множеств (см. лекцию 4); как формально можно оправдать наши рассуждения, мы еще обсудим. Пока что отметим некоторые свойства ординалов.

  • Мы определили на ординалах линейный порядок. Этот порядок будет полным: любое непустое семейство ординалов имеет наименьший элемент (теорема 23; разница лишь в том, что мы не употребляли там слова "ординал", а говорили о представителях).
  • Пусть $$\alpha$$ - некоторый ординал. Рассмотрим начальный отрезок $$[0,\alpha)$$ в классе ординалов (образованный всеми ординалами, меньшими $$\alpha$$ в смысле указанного порядка). Этот отрезок упорядочен по типу $$\alpha$$ (то есть изоморфен представителям ординала $$\alpha$$ ). В самом деле, пусть $$A$$ - один из представителей ординала $$\alpha$$. Ординалы, меньшие $$\alpha$$, соответствуют собственным (не совпадающим с $$A$$ ) начальным отрезкам множества $$A$$. Такие отрезки имеют вид $$[0,a)$$ и тем самым находятся во взаимно однозначном соответствии с элементами множества $$A$$. (Легко проверить, что это соответствие сохраняет порядок.)

    Сказанное можно переформулировать так: каждый ординал упорядочен как множество меньших ординалов. (В одном из формальных построений теории ординалов каждый ординал равен множеству всех меньших ординалов.)

  • Ординал называется непредельным, если существует непосредственно предшествующий ему (в смысле указанного порядка) ординал. Если такого нет, ординал называют предельным.
  • Любое ограниченное семейство ординалов имеет точную верхнюю грань (наименьший ординал, больший или равный всем ординалам семейства). В самом деле, возьмем какой- то ординал $$\beta$$, являющийся верхней границей. Тогда все ординалы семейства изоморфны начальным отрезкам множества $$B$$, представляющего ординал $$\beta$$. Если среди этих отрезков есть само $$B$$, то $$\beta$$ будет точной верхней гранью (и наибольшим элементом семейства). Если нет, то эти отрезки имеют вид $$[0,b)$$ для различных элементов $$b\hm\in B$$. Рассмотрим множество $$S$$ всех таких элементов $$b$$. Если $$S$$ не ограничено в $$B$$, то $$\beta$$ будет точной верхней гранью. Если $$S$$ ограничено, то оно имеет точную верхнюю грань $$s$$, и $$[0,s)$$ будет точной верхней гранью семейства.
    •

    Можно сказать, что семейство ординалов- это как бы универсальное вполне упорядоченное семейство; любое вполне упорядоченное множество изоморфно некоторому начальному отрезку этого семейства. Поэтому мы немедленно придем к противоречию, если захотим рассмотреть множество всех ординалов (ведь для всякого вполне упорядоченного множества есть еще большее- добавим к нему новый элемент, больший всех предыдущих). Этот парадокс называется парадоксом Бурали- Форти.

    124. Докажите, что точная верхняя грань счетного числа счетных ординалов счетна.

    Как же рассуждать об ординалах, не впадая в противоречия? В принципе можно заменять утверждения об ординалах утверждениями о их представителях и воспринимать упоминания ординалов как " вольность речи". Другой подход (предложенный фон Нейманом) применяется при аксиоматическом построении теории множеств, и состоит он примерно в следующем: мы объявляем каждый ординал равным множеству всех меньших ординалов. Тогда минимальный ординал $$0$$ (порядковый тип пустого множества) будет пустым множеством $$\varnothing$$, следующий за ним ординал $$1$$ (порядковый тип одноэлементного множества) будет $$\{0\}\hm=\{\varnothing\}$$, затем $$2\hm=\{0,1\}\hm=\{\varnothing, \{\varnothing\}\}$$, $$3\hm=\{0,1,2\}\hm=\{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\}$$, $$4\hm=\{0,1,2,3\}$$ и т.д За ними следует ординал $$\omega$$ (порядковый тип множества натуральных чисел), равный $$\{0,1,2,3,\dots\}$$, потом $$\omega\hm+1\hm= \{0,1,2,3,\dots,\omega\}$$, потом $$\omega\hm+2\hm= \{0,1,2,3,\dots,\omega,\omega+1\}$$ и т.д

    Мы не будем говорить подробно об аксиоматической теории множеств Цермело- Френкеля, но два обстоятельства следует иметь в виду. Во-первых, в ней нет никаких объектов, кроме множеств, и есть аксиома экстенсиональности (или объемности ), которая говорит, что два объекта, содержащие одни и те же элементы, равны. Поэтому существует лишь один объект, не содержащий элементов (пустое множество). Во-вторых, в ней есть аксиома фундирования }, которая говорит, что отношение $$\in$$ фундировано: во всяком множестве $$X$$ есть элемент, являющийся $$\in$$ - минимальным, то есть элемент $$x\hm\in X$$, для которого $$X\hm\cap x\hm=\varnothing$$. Отсюда следует, что никакое множество $$x$$ не может быть своим элементом (иначе для множества $$\{x\}$$ нарушалась бы аксиома фундирования).

    125. Выведите из аксиомы фундирования, что не существует множеств $$x$$, $$y$$, $$z$$, для которых $$x\in y \in z \in x$$.

    Философски настроенный математик объяснил бы смысл аксиомы фундирования так: множества строятся из ранее построенных множеств, начиная с пустого, и поэтому возможна индукция по построению (доказывая какое- либо свойство множеств, можно рассуждать индуктивно и предполагать, что оно верно для всех его элементов).

    Теперь можно определить ординалы так. Будем говорить, что множество $$x$$ транзитивно, если всякий элемент множества $$x$$ является подмножеством множества $$x$$, то есть если из $$z\hm\in y\hm\in x$$ следует $$z\hm\in x$$. Назовем ординалом транзитивное множество, всякий элемент которого транзитивен. Это требование гарантирует, что на элементах любого ординала отношение $$\in$$ является (строгим) частичным порядком.

    Аксиома фундирования гарантирует, что частичный порядок $$\in$$ на любом ординале является фундированным. После этого по индукции можно доказать, что он является линейным (и, следовательно, полным).

    126. (а) Используя определение ординала как транзитивного множества с транзитивными элементами, докажите, что элемент ординала есть ординал. (б) Пусть $$\alpha$$ - ординал (в смысле данного нами определения). Докажите, что отношение $$\in$$ на нем является частичным порядком. (в) Докажите, что для любых элементов $$a,b\hm\in\alpha$$ верно ровно одно из трех соотношений: либо $$a\hm\in b$$, либо $$a\hm=b$$, либо $$b\hm\in a$$. (Указание: используйте двойную индукцию по фундированному отношению $$\in$$ на $$\alpha$$, а также аксиому экстенсиональности.) (г) Докажите, что один ординал изоморфен собственному начальному отрезку другого тогда и только тогда, когда является его элементом. (Таким образом, отношение $$<$$ на ординалах как упорядоченных множествах совпадает с отношением принадлежности.) Докажите, что каждый ординал является множеством всех меньших его ординалов.

    Заметим еще, что если каждый ординал есть множество всех меньших его ординалов, то точная верхняя грань множества ординалов есть их объединение.

    Мы не будем подробно развивать этот подход и по- прежнему будем наивно представлять себе ординалы как порядковые типы вполне упорядоченных множеств.

    Прежде чем перейти к сложению и умножению ординалов, отметим такое свойство:

    Теорема 37. Пусть $$A$$ - подмножество вполне упорядоченного множества $$B$$. Тогда порядковый тип множества $$A$$ не превосходит порядкового типа множества $$B$$.

    Доказательство. Отметим сразу же, что равенство возможно, даже если $$A$$ является собственным подмножеством $$B$$. Например, четные натуральные числа имеют тот же порядковый тип $$\omega$$, что и все натуральные числа.

    Рассуждая от противного, предположим, что порядковый тип множества $$A$$ больше. Тогда $$B$$ изоморфно некоторому начальному отрезку множества $$A$$, не совпадающему со всем $$A$$. Пусть $$a_0$$ - верхняя граница (в $$A$$ ) этого отрезка, а $$f\colon B \hm\to A$$ - соответствующий изоморфизм. Тогда $$f$$ строго возрастает и потому $$f(b)\hm\ge b$$ для всех $$b\hm\in B$$ (теорема 17). В частности, $$f(a_0)\hm\ge a_0$$, но по предположению любое значение $$f(b)$$ меньше $$a_0$$ - противоречие.

    Арифметика ординалов

    Мы определили сумму и произведение линейно упорядоченных множеств в лекции 7. (Напомним, что в $$A\hm+B$$ элементы $$A$$ предшествуют элементам $$B$$, а в $$A\hm\times B$$ мы сначала сравниваем $$B$$ - компоненты пар, а в случае их равенства- $$A$$ - компоненты.)

    Легко проверить следующие свойства сложения:

  • Сложение ассоциативно: $$\alpha\hm+(\beta\hm+\gamma)\hm=(\alpha\hm+\beta)\hm+\gamma$$.
  • Сложение не коммутативно: например, $$1\hm+\omega\hm=\omega$$, но $$\omega\hm+1\hm\ne\omega$$.
  • Очевидно, $$\alpha\hm+0\hm=0\hm+\alpha\hm=\alpha$$.
  • Сумма возрастает при росте второго аргумента: если $$\beta_1\hm<\beta_2$$, то $$\alpha\hm+\beta_1\hm<\alpha\hm+\beta_2$$. (В самом деле, пусть $$\beta_1$$ изоморфно начальному отрезку в $$\beta_2$$, отличному от всего $$\beta_2$$. Добавим к этому изоморфизму тождественное отображение на $$\alpha$$ и получим изоморфизм между $$\alpha\hm+\beta_1$$ и начальным отрезком в $$\alpha\hm+\beta_2$$, отличным от $$\alpha\hm+\beta_2$$.)
  • Сумма неубывает при росте первого аргумента: если $$\alpha_1\hm<\alpha_2$$, то $$\alpha_1\hm+\beta \hm\le \alpha_2\hm+\beta$$. (В самом деле, $$\alpha_1\hm+\beta$$ изоморфно подмножеству в $$\alpha_2\hm+\beta$$. Это подмножество не является начальным отрезком, но мы можем воспользоваться теоремой 37.)
  • Определение суммы согласовано с обозначением $$\alpha\hm+1$$ для следующего за $$\alpha$$ ординала. (Здесь $$1$$ - порядковый тип одноэлементного множества.) Следующим за $$\alpha\hm+1$$ ординалом будет ординал $$(\alpha\hm+1)\hm+1\hm=\alpha\hm+(1\hm+1)\hm=\alpha\hm+2$$ и т.д.
  • Если $$\alpha\hm\ge\beta$$, то существует единственный ординал $$\gamma$$, для которого $$\beta\hm+\gamma\hm=\alpha$$. (В самом деле, $$\beta$$ изоморфно начальному отрезку в $$\alpha$$ ; оставшаяся часть $$\alpha$$ и будет искомым ординалом $$\gamma$$. Единственность следует из монотонности сложения по второму аргументу.) Заметим, что эту операцию можно называть " вычитание слева".
  • " Вычитание справа", напротив, возможно не всегда. Пусть $$\alpha$$ - некоторый ординал. Тогда уравнение $$\beta\hm+1\hm=\alpha$$ (относительно $$\beta$$ ) имеет решение тогда и только тогда, когда $$\alpha$$ - непредельный ординал, (т.е. когда $$\alpha$$ имеет наибольший элемент).
    •

    Определение суммы двух ординалов в силу ассоциативности можно распространить на любое конечное число ординалов. Можно определить и сумму $$\alpha_1\hm+\alpha_2\hm+\ldots$$ счетной последовательности ординалов (элементы $$\alpha_i$$ предшествуют элементам $$\alpha_j$$ при $$i\hm<j$$ ; внутри каждого $$\alpha_i$$ порядок прежний). Как легко проверить, это множество действительно будет вполне упорядоченным: чтобы найти минимальный элемент в его подмножестве, рассмотрим компоненты, которые это подмножество задевает, выберем из них компоненту с наименьшим номером и воспользуемся ее полной упорядоченностью.

    В этом построении можно заменить натуральные числа на элементы произвольного вполне упорядоченного множества $$I$$ и определить сумму $$\sum A_i$$ семейства вполне упорядоченных множеств $$A_i$$, индексированного элементами $$I$$, как порядковый тип множества всех пар вида $$\langle a,i\rangle$$, для которых $$a\in A_i$$. При сравнении пар сравниваются вторые компоненты, а в случае равенства и первые (в соответствующем $$A_i$$ ). Если все $$A_i$$ изоморфны одному и тому же множеству $$A$$, получаем уже известное нам определение произведения $$A\hm\times I$$.

    Теперь перейдем к умножению ординалов.

  • Умножение ассоциативно: $$(\alpha\beta)\gamma\hm= \alpha(\beta\gamma)$$. (В самом деле, в обоих случаях по существу получается множество троек; тройки сравниваются справа налево, пока не обнаружится различие.)
  • Умножение не коммутативно: например, $$2\hm\cdot\omega\hm=\omega$$, в то время как $$\omega\hm\cdot 2\hm\ne\omega$$.
  • Очевидно, $$\alpha\hm\cdot0\hm=0\hm\cdot\alpha=0$$ и $$\alpha\cdot1\hm=1\cdot\alpha\hm=\alpha$$.
  • Выполняется одно из свойств дистрибутивности: $$\alpha(\beta\hm+\gamma)\hm=\alpha\beta\hm+\alpha\gamma$$ (непосредственно следует из определения). Симметричное свойство выполнено не всегда: $$(1\hm+1)\hm\cdot\omega\hm=\omega\hm\ne\omega+\omega$$.
  • Произведение строго возрастает при увеличении второго множителя, если первый не равен $$0$$. (Для разнообразия выведем это из ранее доказанных свойств: если $$\beta_2\hm>\beta_1$$, то $$\beta_2\hm=\beta_1\hm+\delta$$, так что $$\alpha\beta_2\hm=\alpha(\beta_1\hm+\delta) \hm=\alpha\beta_1 \hm+\alpha\delta \hm>\alpha\beta_1$$.)
  • Произведение не убывает при возрастании первого множителя. (В самом деле, если $$\alpha_1\hm<alpha_2$$, то $$\alpha_1\beta$$ изоморфно подмножеству $$\alpha_2\beta$$. Это подмножество не является начальным отрезком, но можно сослаться на теорему 37.)
  • Любой ординал, меньший $$\alpha\beta$$, однозначно представим в виде $$\alpha\beta'\hm+\alpha'$$, где $$\beta'\hm<\beta$$ и $$\alpha'\hm<\alpha$$.

    (В самом деле, пусть множества $$A$$ и $$B$$ упорядочены по типам $$\alpha$$ и $$\beta$$. Тогда $$A\hm\times B$$ упорядочено по типу $$\alpha\beta$$. Всякий ординал, меньший $$\alpha\beta$$, есть начальный отрезок в $$A\hm\times B$$, ограниченный некоторым элементом $$\langle a,b\rangle$$. Начальный отрезок $$[0,\langle a,b\rangle)$$ состоит из пар, у которых второй член меньше $$b$$, а также из пар, у которых второй член равен $$b$$, а первый меньше $$a$$. Отсюда следует, что этот начальный отрезок изоморфен $$A\hm\times[0,b)\hm+[0,a)$$, так что остается положить $$\beta'\hm=[0,b)$$ и $$\alpha'\hm=[0,a)$$. Теперь проверим однозначность. Пусть $$\alpha\beta'\hm+\alpha'\hm=\alpha\beta''\hm+\alpha''$$. Если $$\beta'=\beta''$$, то можно воспользоваться однозначностью левого вычитания и получить, что $$\alpha'=\alpha''$$. Остается проверить, что $$\beta'$$ не может быть, скажем, меньше $$\beta''$$. В этом случае $$\beta''\hm=\beta'+\delta$$, и сокращая $$\alpha\beta'$$ слева, получим, что $$\alpha'\hm=\alpha\delta+\alpha''$$, что невозможно, так как левая часть меньше $$\alpha$$, а правая часть больше или равна $$\alpha$$.)

  • Аналогичное " деление с остатком" возможно и для любых ординалов. Пусть $$\alpha\hm>0$$. Тогда любой ординал $$\gamma$$ можно разделить с остатком на $$\alpha$$, то есть представить в виде $$\alpha\tau\hm+\rho$$, где $$\rho\hm<\alpha$$, и притом единственным образом.

    (В самом деле, существование следует из предыдущего утверждения, надо только взять достаточно большое $$\beta$$, чтобы $$\alpha\beta$$ было больше $$\gamma$$, скажем, $$\beta\hm=\gamma\hm+1$$. Единственность доказывается так же, как и в предыдущем пункте.)

  • Повторяя деление с остатком на $$\alpha>0$$, можно построить позиционную систему счисления для ординалов: всякий ординал, меньший $$\alpha^{k+1}$$ (здесь $$k$$ - натуральное число), однозначно представим в виде $$\alpha^k\beta_k\hm+\alpha^{k-1}\beta_{k-1}\hm+ \ldots\hm+\alpha\beta_1\hm+\beta_0$$, где $$\beta_k$$, $$\dots$$, $$\beta_1$$, $$\beta_0$$ - ординалы, меньшие $$\alpha$$.
    •

    127. Для каких ординалов $$1\hm+\alpha\hm=\alpha$$?

    128. Для каких ординалов $$2\hm\cdot\alpha\hm=\alpha$$?

    129. Какие ординалы представимы в виде $$\omega\hm\cdot\alpha$$?

    130. Докажите, что $${\alpha+\beta}\hm=\beta$$ тогда и только тогда, когда $${\alpha\omega}\hm\le\beta$$ (здесь $$\alpha$$ и $$\beta$$ - ординалы).

    131. Докажите, что если $${\alpha+\beta}\hm={\beta+\alpha}$$ для некоторых ординалов $$\alpha$$ и $$\beta$$, то найдется такой ординал $$\gamma$$ и такие натуральные числа $$m$$ и $$n$$, что $$\alpha\hm={\gamma m}$$ и $$\beta\hm={\gamma n}$$.

    132. Определим операцию "замены основания" с $$k\hm>1$$ на $$l\hm>k$$. Чтобы применить эту операцию к натуральному числу $$n$$, надо записать $$n$$ в $$k$$ - ичной системе счисления, а затем прочесть эту запись в $$l$$ - ичной системе. (Очевидно, число при этом возрастет, если оно было больше или равно $$k$$.) Возьмем произвольное число $$n$$ и будет выполнять над ним такие операции: замена основания с $$2$$ на $$3$$ - вычитание единицы - замена основания с $$3$$ на $$4$$ - вычитание единицы - замена основания с $$4$$ на $$5$$ - вычитание единицы - ... Докажите, что рано или поздно мы получим нуль и вычесть единицу не удастся. (Указание: замените все основания на ординал $$\omega$$ ; получится убывающая последовательность ординалов.)

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^