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

Ми визначили суму і твір лінійно упо ¬ рядкування множин в розділі 2.1. (Нагадаємо, що в А + + В елементи А передують елементам В, авАхВ ми спочатку порівнюємо В-компоненти пар, а в разі їх рівності - А-компоненти.)

Легко перевірити наступні властивості складання: але ш + 1 Ф ш.

•

Чи Д <то а - Л \ <а - (Справді, нехай ізоморфно початкового відрізку в /? 2, відмінному від усього Додамо до цього ізоморфізму Тожде ¬ вною відображення на а й одержимо ізоморфізм між а -; 1 \ і початковим відрізком в а + /? 2, від ¬ особистим від а + /? 2 -)

•

Чи а \ << Х2, то а \ + / 9 ^ «2 + (Справді, а \ + / 9 ізоморфно підмножині в« 2 + Це під ¬ безліч не є початковим відрізком, але ми можемо скористатися теоремою 37.)

•

+ 1 для наступного за а ордінала. (Тут 1 - по ¬ порядковий тип одноелементні множини.) Сліду ¬ ющим за а + 1 ордіналом буде ордінала (а + 1) + + 1 = а + (1 + 1) = а + 2іт.д.

• Якщо а ^ / 3, то існує єдиний ординар ¬ нал 7, для якого / 9 + 7 = а. (Справді, / 3 ізоморфно початкового відрізку в а; решта а й буде шуканим ордіналом 7. Єдності ¬ ність випливає з монотонності додавання за друго ¬ му аргументу.) Зауважимо, що цю операцію можна називати «відніманням зліва».

•

Нехай а - деякий ордінала. Тоді рівняння (3 + 1 = а (щодо (3) має рішення тоді і тільки тоді, коли а - неграничні ордінала, (тобто коли а має найбільший елемент).

Визначення суми двох ордіналов в силу асоціації ¬ ності можна поширити на будь-яке кінцеве чи ¬ сло ордіналов. Можна визначити і суму «1 +« 2 + + ... лічильної послідовності ордіналов (елементи а $ передують елементам а2-прі г <у, всередині каждо ¬ го сц порядок колишній). Як легко перевірити, це мно ¬ дружність дійсно буде цілком упорядкованим: що ¬ б знайти мінімальний елемент в його підмножині, рас ¬ дивимося компоненти, які це підмножина зачепивши ¬ ет, виберемо з них компоненту з найменшим номером і скористаємося її повної впорядкованістю.

У цьому побудові можна замінити натуральні чи ¬ сла на елементи довільного цілком упорядкованої множини I і визначити суму V; А, сімейства цілком впорядкованих множин А ^, індексованого елементів ¬ тами I, як порядковий тип множини всіх пар виду (а, г), для яких про € А;. При порівнянні пар порівнюючи ¬ ються другий компонент, а в разі рівності і перші (у відповідному А,). Якщо все А, ізоморфні одне ¬ му і тому ж безлічі А, отримуємо вже відоме нам

х

Тепер перейдемо до множення ордіналов.

• Множення асоціативно: (а / 9) 7 = а (/? 7). (Справді, в обох випадках по суті виходить мно ¬ дружність трійок; трійки порівнюються справа наліво, поки не виявиться відмінність.)

• множення не коммутативно: наприклад, 2 • ш = ш, в той час як ш • 2 ф ш.

• Очевидно, «• 0 = ('а = 0іаА = 1 ^ а = а. •

а {Р + 7) = CH.fi + 0:7 (безпосередньо випливає з ухвали). Симетричне властивість виконано

другого множника, якщо перший не дорівнює 0. (Для різноманітності виведемо це з раніше доведених властивостей: якщо / 32> (3 \, то / З2 = А + 5, так що а @ 2 = а (А + Я) = а А + аб> а (Зг.)

•

множника. (Справді, якщо ах <аг, то ах / 9 з ¬ морфних підмножині аг /?. Це підмножина не є початковим відрізком, але можна послатися на теорему 37.)

•

ним у вигляді а / 3 '+ а', де / 3 '</ 3 ж а' <а.

(Справді, нехай безлічі А ж В впорядковані за типами а ж ¡3. Тоді Ах В впорядковано за типом а / 3. Всякий ордінала, менший а / 3, є початковий відрізок в А х В, обмежений деяким елементом ¬ том ( а, 6}. Початковий відрізок [0, (а, Ь}) складається з пар, у яких другий член менше виданню, а також з пар, у яких другий член дорівнює Ь, а перший мен ¬ ше а. Звідси випливає, що цей початковий відрізок х

''

'''''' '''

то можна скористатися однозначністю лівого

'''

'''

'' ''

'''

ліва частина менша а, а права частина більше або дорівнює а.)

•

будь-яких ордіналов. Нехай а> 0. Тоді будь-який ординар ¬ нал 7 можна розділити з залишком на а, тобто представити у вигляді ат + р, де р <а, ж притому єдиним чином.

(Справді, існування випливає з попе ¬ ного твердження, треба тільки взяти досить велику (3, щоб а / 3 було більше 7, скажімо, / 3 =

= 7 + 1. Єдиність доводиться так само, як і в попередньому пункті.)

• Повторюючи ділення з залишком на а> 0, можна по ¬ будувати позиційну систему числення для ординар ¬ лів: всякий ордінала, менший ak + l (тут до - натуральне число), однозначно представимо у вигляді akЯk + ak ~ 1Яk-i +. ■. + AЯi + Я0, де Я \, ..., Яi, Я0 - ордінали, менші а.

127. Для яких ордіналов 1 + а = а?

128. Для яких ордіналов 2 • а = а!

129. Які ордінали представимо у вигляді з • а?

130. Доведіть, що а + Я = Я тоді і тільки тоді, коли аш <Я (тут а і Я - ордінали).

131. Доведіть, що якщо а + Я = Я + а для деяких ор ¬ діналов cv і: i, то знайдеться такий ордінала j і такі нату ¬ ральні числа тип, що а = jm і Я = jn.

132. Визначимо операцію «заміни підстави» з к> 1 на I> к. Щоб застосувати цю операцію до натурального числа п, треба записати п в fc-ічной системі числення, а за ¬ тем прочитати цей запис в Особистою системі. (Очевидно, число при цьому зросте, якщо воно було більше або дорівнює к.) возь ¬ мем довільне число п і буде виконувати над ним такі операції: заміна підстави з 2 на 3 - віднімання одиниці-заміна підстави з 3 на 4 - віднімання одиниці - заміна осно ¬ вання з 4 на 5 - віднімання одиниці - ... Доведіть, що рано чи пізно ми отримаємо нуль і відняти одиницю не вдасться. (Вказівка: замініть всі підстави на ордінала ш; вийде спадна послідовність ордіналов.)

2.12. Індуктивні визначення і ступеня

Ми визначили додавання і множення ордіналов з по ¬ міццю явних конструкцій порядку на відповідних множинах. Замість цього можна було б їх визначити індуктивно.

Теорема 38. Додавання ордіналов володіє следующ ¬ ми властивостями:

а + 0 = а; а + (0 +1) = (а + 0) + 1;

а + 7 = вир ^ а + / 3 | / 3 <7} для граничного 7 липня ^ 0.

Ці властивості однозначно визначають операцію складний ¬ ня.

<Два перших властивості очевидні; перевіримо третє. Якщо (3 <7, то а + (3 <а + 7, так що а + 7 буде верхньою межею всіх сум виду а + / 9 при / 9 <7. Треба прове ¬ рить, що ця межа точна. Нехай деякий ординар ¬ нал т менше а + 7. Переконаємося, що він менше а + / 9 для деякого / 9 <7. Якщо т <а, все очевидно. Якщо т ^ а, подамо його у вигляді т = а + <т. Тоді а + а <а + + 7 і тому <т <7. Оскільки ордінала 7 граничний, <т + 1 також менше 7 і залишається покласти / 3 = а + 1.

Зазначені властивості однозначно визначають опера ¬ цію складання, так як представляють собою рекурсивне визначення по / 3 (якщо є дві операції додавання, обла ¬ дають цими властивостями, візьмемо мінімальне ¡3, для якого вони розрізняються і т. д.). >

Аналогічно можна визначити і множення: Теорема 39. Множення ордіналов має дотримуюся ¬ ські властивостями:

АТ = 0;

а ((3 + 1) = а (1 + а;

{|}

Ці властивості однозначно визначають операцію множення ¬ ня.

<Доказ аналогічно, потрібно тільки прове ¬ рить, що якщо т <07 для граничного 7, то т <а / 3

для деякого (3 <7. Як ми бачили на с. 101, ординарну

'' '

покласти ¡3 = ^ + 1. >

Виникає природне бажання визначити опера ¬ цію зведення в ступінь. Ми вже по суті визнач ¬ ли зведення в цілу позитивну ступінь (ап є твір п співмножників, рівних а). Іншими сло ¬ вами, якщо А впорядковано по типу а, то безліч Ап послідовностей довжини п з елементами з А з обрат ¬ вим лексикографічним порядком (порівняння справа наліво) упорядковано за типом ап.

Наступний крок - визначити а ~. Перша ідея, при ¬ ходящая в голову - узяти безліч Ам нескінченних послідовностей і визначити на ньому повний поря ¬ док. Але як його ввести - неясно. Тому можна попро ¬ бова визначити зведення в ступінь індуктивно за допомогою наступних співвідношень:

аК +1 =

1;

<Г '• а;

8ір {о / | ¡3 <7} для граничного 7 ф 0.

Теорема 18 (про трансфінітних рекурсії) гарантує, що ці співвідношення однозначно визначають деяку операцію над ордіналамі, яка і називається зведених ¬ деніем в ступінь.

Зауваження. Тут знову ми підходимо до небезпечної межі ¬ Це парадоксів і змушені висловлюватися ухильно. Насправді теорема про трансфінітних рекурсії говорила про визначення функції на цілком упорядкованому мно ¬ дружність, а ордінали не утворюють безлічі - їх занадто ¬ ком багато. Крім того, в ній йшлося про функції зі значеннями в деякому заданому безлічі, которо ¬ го тут теж немає. Подібні індуктивні визначення можна коректно обгрунтувати в теорії множин з ви ¬ користуванням так званої аксіоми підстановки, але ми про це говорити не будемо. Замість цього ми дамо явне опис зведення в ступінь, вільний від цих проблем.

Щоб зрозуміти сенс зведення в ступінь, подивився ¬ трим, як виглядає ордінала аш (для деякого а). Нехай А - множина, впорядковане за типом а. Ор ¬ Динал а за визначенням є точна верхня грань а для натуральних п. ордінала ап є порядковий тип безлічі Ап, упорядкованого в зворотному лексікогра ¬ фіческой порядку. Щоб знайти точну верхню грань, уявімо безлічі Ап як початкові відрізки один одного. Наприклад, А2 складається з пар (01,02) і отожде ¬ ствляется з початковим відрізком в А3, що складається з (

Тепер видно, що всі безлічі Ап можна розглядати ¬ вати як початкові відрізки безлічі А ° °, що складається з нескінченних послідовностей щ, а \, ..., елементів ¬ ти яких належать Айв яких лише кінцеве число членів відмінно від нуля. (Остання вимога де ¬ гавкає коректним визначення зворотного лексикографії ¬ тичного порядку - ми знаходимо саму праву позицію, в якій послідовності різняться, і порівняй ¬ ваем їх значення в цій позиції.) В об'єднанні ці початкові відрізки дають всі А ° °, так що це безліч з описаним порядком має тип аш.

Аналогічне твердження вірне і для будь-якого поки ¬ показника ступеня.

Нехай А ж В - цілком упорядковані множини, мають порядкові типи а ж (5. Розглянемо множест ¬ во [В - А] складається з відображень В в А, що мають «кінцевий носій» (рівних мінімального елементу А всюди, за винятком кінцевого безлічі) . Введемо -

елемент Ь € В, для якого / 1 (6) ф / 2 (6) і порівняємо Д (6) та / 2 (6)

Теорема 40. Зазначене правило задає повний поря ¬ -

дружність є <г '.

<Нам треба перевірити, що зазначений порядок явля ¬ ється повним і що виконані вимоги індуктивного визначення ступеня.

Назвемо носієм елементу / € [В - А] множест ¬ во тих Ь € В, для яких / (Ь)> 0 (тут 0 позначають ¬ ет найменший елемент множини А). Назвемо рангом функції / найбільший елемент носія (по определе ¬ ня носій кінцевий, так що найбільший елемент су ¬ суспільством). Ранг визначений для всіх функцій, крім то ¬ ждественно нульовий, яка є мінімальним еле ¬ ментом множини [В - А]. Чим більше ранг функції, тим більше сама функція в сенсі введеного нами по ¬ рядку.

-

> Д> Д >> ... - Спадна послідовність еле ¬ -

трим їх ранги. Ці ранги утворюють невозрастающую послідовність, тому починаючи з деякого ме ¬ ста стабілізуються (безліч В цілком упорядкування ¬ но). Відкинемо початковий відрізок і будемо вважати, що з самого початку ранги всіх елементів спадної після ¬ послідовності однакові і рівні деякого видання. У соот ¬ повідно до визначення, значення / о (6), Д (Ь), ... образу ¬ ють невозрастающую послідовність, тому начи ¬ ва з деякого місця стабілізуються. Відкинувши на ¬ чільного відрізок, будемо вважати, що все Д мають оди ¬ наково ранг видання і однакове значення Д (6). Тоді зна ¬ чення Д (6) не впливають на порівняння, і тому їх можна замінити на 0. Отримаємо убуваючу послідовність -

міркування, залишається послатися на принцип індукції по безлічі В.

(Більш формально, розглянемо всі нескінченно зменш ¬ ющие послідовності. У кожної з них розглянемо ранг першого елемента. Розглянемо ті з них, у яких цей ранг мінімально можливий; нехай Ь - це міні ¬ мального значення. У будь такій послідовності всі елементи мають ранг Ь. З усіх таких послідовно ¬ стей / о> Д> • • • виберемо ту, у якій значення Д (6) мінімально; всі наступні її члени мають те ж зна ¬ чення в точці видання (тобто Д (6) = / о (6)). Замінивши значення в точці ред нулем, отримаємо нескінченну убуваючу після ¬ довність з елементів меншого рангу, що проти ¬ воречие припущенням.)

Тепер покажемо, що таке явне визначення ступеня ¬ ні погоджено з індуктивним визначенням. Для конеч ¬ них п це очевидно. Нехай 7 = / 9 +1. Яке (явне) визна ¬ ділення А7? Нехай В впорядковано по типу /?. Тоді ми повинні додати до В новий найбільший елемент (про ¬ значущий його т) і розглянути відображення Ві {т} - Ас кінцевим носієм. Ясно, що таке відображення зада ¬ ється парою, що складається з його звуження на В (яке мо ¬ жет бути довільним елементом безлічі [В - А]) і значення на т. При визначенні порядку ми спочатку порівнюємо значення на т, а потім звуження на В, тобто отримане безліч ізоморфно [В - А] х А, що і було потрібно.

Нехай тепер 7 - ненульовий граничний ордінала і безліч З впорядковано по типу 7. Як влаштовано мно - €

€

-

-

різко (оскільки кожен елемент цієї множини име ¬ ет кінцевий носій) і тому його порядковий тип є точною верхньою межею їх порядкових типів, що й було потрібно. >

Безпосереднім наслідком цієї теореми є таке твердження:

Теорема 41. Якщо а і /? - Лічильні ордінали, то а + /?, А> 0 і ор рахункових.

<Для суми і твори твердження очевидно. Для ступеня: якщо ми пронумерували всі елементи впол ¬ не впорядкованих множин А і В, то будь-який елемент -

ком натуральних чисел (носій і значення на еле ¬ тах носія), а таких списків рахункове число. >

133. Доведіть, що а ^ +7 = А13 • а1 двома способами: по індукції та з використанням явного визначення ступеня.

134. Доведіть, що (А13) 1 = а131.

135. Доведіть, що якщо а> 2, то А13> а / 3.

136. Доведіть, що якщо ш7 = а + Р для деяких ординар ¬ лів а, / 3 і 7, то або / 3 = 0, або / 3 = ш7.

137. Які ордінали не можна представити у вигляді суми двох менших ордіналов?

138. Доведіть счетності для рахункових а і / 3, використовуючи індуктивний визначення ступеня.

139. Дан деякий ордінала а> 1. Вкажіть найменший ордінала / 3> 0, для якого а / 3 = / 3. (Вказівка: що буде, якщо помножити х на степеневий ряд 1 + ж + х2 + Хя + ...?)

Відзначимо важливу різницю між операцією зведений ¬ ня ордіналов в ступінь і раніше розглянутими опе ¬ раціями додавання і множення ордіналов. Визначаючи суму і твір ордіналов, ми вводили некото ¬ рий порядок на сумі і творі відповідних множин (у звичайному розумінні), тут же само множест -

від Ав. (Зокрема, при рахункових А ж В безліч -

-

як влаштовані його початкові відрізки, тобто який вигляд мають ордінали, менші ор.

Розглянемо деяку функцію / € [В - А]. Нехай вона відмінна від нуля в точках Ь \> Ь2>. . . > Ьк ж при ¬ приймає там значення а \, а2, ■ ■ ■, а *. Нас цікавлять всі функції, менші функції /.

Всі вони рівні нулю в точках, великих Ь \. В са ¬ мій точці Ь \ вони можуть бути або менше а \, або дорівнюють а \. Будь-яка функція першого типу менше будь-якої функції другого типу. Функції першого типу можуть приймати будь-які значення в точках, менших Ь \, а в точці & х мають значення з [0, а \). Тим самим їх можна ототожнити з елементами безлічі [[0, Ьх) - А] х х [0, ах), і при цьому ототожненні зберігається поря ¬ док.

Функції другого типу (рівні а \ в точці видання \) сно ¬ ва розбиваються на дві категорії: ті, які в точ ¬ ке Ьг менше А.2 і ті, які в Ь2 рівні а2-Функції першої категорії ототожнюються з елементами мно ¬ дружність [[0, Ьг) - А] х [0, а2). Функції другої категорії знову розіб'ємо на частини залежно від їх значення в точці & з і т. д. Таким чином, [0, /) як упорядкований безліч ізоморфно безлічі

- Х - х

-Х

Переходячи до ордіналам (початкові відрізки - це мен ¬ рілі ордінали), отримуємо таке твердження:

Теорема 42. Всякий ордінала, менший а * 3, представля ¬ ється у вигляді

а ^ ах + о / 2 «2 + ■ ■ ■ + а13как,

де Л> Л \> Л,> ... > Лк. а а \, а2, ... , Ак <а. Таке уявлення однозначно і будь-яка сума зазначеного ві ¬ да є ордіналом, меншим а &.

<Можливість такого подання ми вже дока ¬ зали. Останнє твердження випливає з того, що будь-яка сума такого виду є початковим відрізком в мно -

і /?) і різним сумам відповідають різні початкові відрізки. >

Це твердження узагальнює описану нами раніше (с. 102) «позиційну систему позначень з основою а» для ордіналов, менших ак; тепер замість до можна використовувати будь ордінала.

Можна було б відразу сказати, що елементами мно -

а ^ аг + а ^ 2а2 + ... + А13как

(Де Р> /? 1> ...> Р / с і а \, ..., ак <а) з природним порядком на них.

Тепер уже зрозуміло, як влаштовані ордінали в після ¬ послідовності

Перший з них утворений «одноповерховими» виразами виду

ь) Ь1аг + шЬ2а2 + ... + ШЬкак,

де щ і 6, - натуральні числа (і видання \> ...> Якщо в

Як дозволити писати будь-які «одноповерховий-

ві »вислови зазначеного виду, то отримані« двох ¬ поверхові »вислови впорядковані за типом До Роздільна ¬ шив в показниках двоповерхові вираження, ми отримаємо триповерхові вирази, які утворюють наступний ордінала і т. д. Якщо об'єднати всі ці множини, тобто не обмежувати число поверхів (яке для каждо ¬ го вираження проте звичайно), то вийде мно ¬ дружність, впорядковане за типом

8ір (и), ШШ \ ...)

Цей ордінала позначається £ о-

140. Доведіть, що

е0 = ш + шш + ...

141. Визначимо для натуральних чисел операцію «тоталь-

ної заміни підстави до на I »(тут до залізничного I - натуральні

числа, причому I> к) таким чином: дане число п за-

пишемо в А'-ічпой системі, тобто розкладемо за ступенями к,

показники ступенів знову запишемо в Д - ічпой системі, нові

показники також розкладемо і т. д. Потім на всіх рівнях за-

менім підставу до на підставу I ж обчислимо значення напів-

чивших вираження. Доведіть, що почавши з будь-якого п ж ви-

повна послідовність операцій «віднімання одиниці -

тотальна заміна підстави 2 на 3 - віднімання одиниці -

тотальна заміна підстави 3 на 4 - віднімання одиниці -

тотальна заміна підстави 4 на 5 - ... », Ми рано чи пізно

зайдемо в глухий кут, тобто вийде нуль і відняти одиницю бу-

дет не можна. (Вказівка: замінимо всі підстави відразу на ординарну

нал ш; вийде спадна послідовність ордіналов,

менших ео-)