2.13. Програми ордіналов

У більшості випадків міркування з використанням ¬ ем трансфінітних індукції та ордіналов можна заме ¬ нитка посиланням на лему Цорна; при цьому міркування ста ¬ новится менш наочним, але формально більш простим. Проте бувають ситуації, коли цього зробити не

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

Перший з них стосується борелевскіх множин. (Для простоти ми розглядаємо підмножини действитель ¬ ної прямій.) Сімейство підмножин дійсної прямої називається а-алгеброю, якщо воно замкнуто від ¬ вано кінцевих і лічильних перетинів і об'єд ¬ нений, а також щодо переходу до доповнення. (Це означає, що разом з кожним безліччю А це сімейство містить його доповнення М \ А, і разом з будь-якими множинами А $, Ах, ... сімейство містить їх об'єднання Ао і Ах і ... і перетин Ао П А \ П ...) Приклад: сімейство Р (І) всіх підмножин прямий, оче ¬ видно, є ст-алгеброю.

Теорема 43. Існує мінімальна ст-алгебра, со ¬ тримає всі відрізки [а, Ь] на прямій.

<Формально можна міркувати так: розглянемо всі можливі (т-алгебри, що містять відрізки. Їх пересе ¬ чення буде ст-алгеброю, і теж буде містити всі від ¬ різання. (Взагалі перетин будь-якого сімейства ст-алгебр буде ст-алгеброю - це очевидне наслідок визначенні ¬ ня.) Ця ст-алгебра і буде шуканою.>

Множини, що входять в цю мінімальну ст-алгебру, називають борелевскімі.

142. Доведіть, що всяке відкрите і всяке замкнутий підмножина прямої є борелевскім. (Вказівка: від ¬ крите безліч є об'єднання містяться в ньому від ¬ різко з раціональними кінцями.)

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

144. Нехай / о, / 1, ... - Послідовність неперервних функцій з дійсними аргументами і значеннями. До ¬ показуйте, що безліч точок х, в яких послідовник ¬ ність / о (х), $ х {х), ... має межу, є борелевскім.

Борелевскіе безлічі грають важливу роль в де ¬ скріптівной теорії множин. Але ми хочемо лише про ¬ демонструвати використання трансфінітних індук ¬ ції (навряд чи легко замінної на використання лем ¬ ми Цорна) на прикладі наступної теореми:

Теорема 44. Сімейство всіх борелевскіх множин має потужність континууму.

<Клас борелевскіх множин можна будувати по ¬ статечно. Почнемо з відрізків і доповнень до відрізкам. На наступному кроці розглянемо всілякі рахункові перетину та об'єднання вже побудованих множин (відрізків і доповнень до них).

145. Доведіть, що при цьому вийдуть (серед іншого) всі відкриті і всі замкнуті підмножини прямій.

Далі можна розглянути рахункові об'єднання і пе ¬ ресеченія вже побудованих множин і т. д.

Більш формально, нехай По - сімейство множин, що складається з усіх відрізків і доповнень до них. Визна ¬ ділимо по індукції як сімейство множин, являю ¬ щихся рахунковими об'єднаннями або перетинами мно ¬ дружність з В $.

Все сімейства В, складаються з борелевскіх множин (оскільки рахункове об'єднання або перетинання борі ¬ левский множин є борелевскім). Вичерпують вони все борелевскіе безлічі? Взагалі кажучи, немає: якщо ми візьмемо по одному безлічі з кожного клас ¬ са В, для всіх г = 0,1,2, ... і розглянемо їх рахункове перетин, то воно цілком може не належати жодному з класів. Тому ми розглянемо клас ВШ, що представляє собою об'єднання всіх В по всіх на ¬ натуральній г, потім ВШ + \, ВШ +2 і т. д. Об'єднання цієї послідовності класів природно назвати Вш2 і продовжити побудову.

В

налу а. Це робиться за допомогою трансфінітних рекур-

В

рахункові об'єднання та перетину множин з клас-В

ВВ В

З визначення випливає, що Ва с при а <¡3, так що ми отримуємо зростаючу ланцюг класів. Кожен клас замкнутий щодо переходу до доповнення (для початкового класу ми про це подбали, далі по ін-В

множин, так як ми застосовуємо лише операції рахунок ¬ ного об'єднання і перетину, щодо яких клас борелевскіх множин замкнутий.

Виникає питання: як далеко потрібно продовжувати цю конструкцію? Виявляється, що достатньо дійти до першого незліченної ордінала.

Нехай N - найменший незліченні ордінала. (Це - стандартне для нього позначення.) Іншими словами, N є сімейство всіх рахункових ордіналов, упорядкованих відношенням <на ордіналах.

Лемма. Клас замкнутий щодо рахункових об'єк ¬ єднань і перехрещень і тому містить всі борелій-ські множини.

Доказ леми. Нехай є рахункова по ¬ послідовності множин Во, Вх, ..., належать В ^. Ордінала N - граничний, і клас являє ¬ ся об'єднанням менших класів. Тому кожне з

В

а $ - деякий ордінала, менший N1, тобто кінцевий або рахунковий ордінала. Покладемо / 9 = зир ^ а *. Ордінала / 9 є точна верхня грань рахункового числа рахункових ор ¬ діналов і тому рахунку. Справді, розглянемо ордінали щ як початкові відрізки в якомусь біль ¬ шем ордінале (наприклад, в N1); їх точна верхня грань буде об'єднанням рахункового числа рахункових початкових відрізків і тому буде рахунковим ордіналом.

Тепер перше твердження леми очевидно: все У ^ В

лежить в Вр + х і тим більше в (оскільки / 9 +1 є рахунковий ордінала і менше N1).

Таким чином, клас є ст-алгеброю, содер ¬ жащей відрізки, і тому містить всі борелевскіе мно ¬ дружність. Лемма доведена.

В

левский множин, так що клас збігається з класом усіх борелевскіх множин.

Що можна сказати про потужність класів? Клас Під має потужність континууму (відрізки задаються своїми кінцями). Якщо клас Ва має потужність континууму, то і наступний клас & а + \ має потужність континууму (кожен його елемент задається лічильної послідовно ¬ стю елементів попереднього класу, а сн ° = с). Ка ¬ ждий граничний клас є об'єднання попередніх, і поки ми не виходимо за межі рахункових ордіналов, об'єднання це буде лічильно, а ско = с, так що ми не виходимо за межі континууму. Нарешті, є об'єк ¬ єднання незліченної кількості попередніх класів (а імен ¬ но, К класів), але так як К 4 с, то = с.

Таким чином, клас, він же клас всіх борелій-ських множин, має потужність континууму. >

Зазвичай побудова борелевскіх множин починає ¬ ся трохи інакше. Саме, на нижньому рівні рассматри ¬ вають два класи: відкриті і замкнуті множини. На наступному рівні знаходяться класи Ра (рахункові об'єк ¬ єднання замкнутих множин) і (рахункові перетину ¬ ня відкритих множин). Ще на рівень вище лежать рахункові перетину множин з ^ і рахункові об'єд ¬ нання множин з (7 (5, і т. д. Такий підхід є бо ¬ леї природним з точки зору топології, оскільки відрізки на прямий нічим не чудові. Можна про ¬ вірити, що різниця між таким підходом і нашим визначенням невелика.

146. Доведіть, що перетин двох / - '"-множин являє ¬ ся ^-безліччю (і взагалі класи Ра, й $, а також класи наступних рівнів, замкнуті щодо кінцевих об'єк ¬ єднань і перехрещень).

147. Доведіть, що Р "- і (^-множини лежать в класі В% відповідно до нашої класифікацією.

148. Доведіть, що всяке безліч класу В2 відрізняючи ¬ ється від деякого Ра-або (^-множини не більше ніж на рахункове безліч.

149. Доведіть, що всяке безліч класу £> з є рахунковим перетином ^-множин або рахунковим об'єднань ¬ ням С5-множин і що аналогічне твердження вірне для більш високих рівнів нашої ієрархії.

150. Доведіть, що існує відкрите безліч на

площині, серед вертикальних перерізів якого зустрічають ¬ ся всі відкриті підмножини прямій. Доведіть, що суще ¬ ствует С? 4-безліч на площині, серед перерізів якого зустрічаються все З ^-підмножини прямій. Доведіть анало ¬ гічної затвердження для наступних рівнів.

151. Покажіть, що існує З $-безліч, не явля ¬ ющееся ^-безліччю. Покажіть, що існує рахункове об'єднання З ^-множин, що не є рахунковим перетину ¬ ням ^-множин і т. д. (Вказівка: скористайтеся преди ¬ дущей завданням.)

Ордінали часто з'являються при класифікації еле ¬ ментів того чи іншого безлічі по «рангах». Напри ¬ мір, можна класифікувати елементи фундованою ¬ го множини.

Теорема 45. Нехай X - фундованою безліч. Тоді існує і єдина функція гк, визначено ¬ ва на X і приймаюча значення в класі ордіналов, для якої

гк (х) = тт {а | а> гк (г /) для будь-якого у <х}

(При будь-якому х € X).

<\ Визначимо безліч Ха рекурсією по ордіналу а: Ха складається з усіх елементів х € X, для яких все менші їх (в X) елементи належать Хр з меншими індексами /?:

х € Ха (Чу <х) (Е [1 <а) [уеХр).

Зауважимо, що тут (як і в формулюванні теореми) знак <використовується в двох різних значеннях: як поря ¬ док на X і як порядок на ордіналах.

Очевидно, що зі зростанням а безліч Ха зростає (точ ¬ неї, не убуває). Доведемо, що при досить біль ¬ шом а безліч Ха покриває всі X. Якщо це не так, то з / 3 <7 слід Хр З Х1 (довільний мінімаль ¬ ний елемент, не лежить в Хр, належить Х7). По ¬ цього відображення а> -> Ха буде ін'єкцією, що неможливо ¬ можна (візьмемо ордінала, по потужності більший Р (Х); попередніх йому ордіналов вже занадто багато).

Тепер визначимо гк (х) як мінімальне а, при кото ¬ ром х € Ха. Якщо гк (х) = а і у <х, то гк (у) <а. (В са ¬ мом справі, за визначенням Ха з х € Ха і у <х випливає, що у € ХД при деякому / 3 <а.) Навпаки, якщо для деякого ордінала 7 виконано нерівність гк (у) <7 при всіх у <х, то гк (х) 4 7 - Справді, тоді лю ¬ бій елемент у <х належить деякому Хр с / 9 <7 (покладемо (1 = гк (у)) і тому х € Х7 і гк (х ) 4 7 -

Отже, побудована нами функція гк володіє требу ¬ емим властивістю. Єдиність довести зовсім легко: якщо є дві такі функції, розглянемо мінімальну крапку в X, на якій вони різняться, і відразу ж по ¬ лучім протиріччя. >

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

Формально таке дерево можна визначити як під ¬ безліч Т безлічі М * кінцевих послідовно ¬ стей натуральних чисел, замкнутий щодо взяття префікса (якщо послідовність належить Г, то будь-який її початковий відрізок належить Г). Елементи безлічі Г ми називаємо вершинами дерева; вершина у є син вершини х, якщо у виходить з х приписуючи ¬ ням справа якогось одного числа. Вершина у є нащадком вершини х, якщо у виходить додаванням до х одного або кількох чисел.

Ми говоримо, що в дереві Т немає нескінченної гілки, якщо не існує нескінченної послідовності на ¬ натуральній чисел, все початку якої належать Г. У цьому випадку відношення порядку

у <х 4 $ у є нащадок х

фундована і можна застосувати попередню теорему, визначивши ранги всіх вершин дерева Г. Ранг його кореня

(Послідовності довжини 0) і будемо називати рангом дерева.

Теорема 46. (А) Ранг будь-якого дерева (описаного виду) є рахунковим ордіналом.

(Б) Всякий рахунковий ордінала є рангом некото ¬ рого дерева.

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

(Б) Це твердження доводиться індукцією: нехай а - найменший рахунковий ордінала, для якого такого дерева немає. Тоді для всіх менших ордіналов дерева є. Візьмемо ці дерева і зробимо їх піддерев із загальним коренем (їх коріння стануть синами цього загального кореня). Нове дерево також має рахункове розгалуження і ранг його кореня дорівнює а. >

152. Нехай є рахункове дерево, що не має бесконеч ¬ них гілок. Припустимо, що в кожному його аркуші знаходить ¬ ся відрізок або доповнення до відрізка, а в кожній внутрен ¬ ній вершині стоїть знак перетину або об'єднання. Як зіставити такому дереву деякий борелевское множест ¬ во? (Вказівка: покажіть, що в кожній вершині можна єдиний ¬ тиментом чином написати деякий безліч, узгодження ¬ ванне з позначками.) Покажіть, що все борелевскіе безлі ¬ ства можуть бути отримані таким способом.

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

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

На закінчення наведемо швидше кумедний, ніж важ ¬ ний, приклад використання трансфінітних рекурсії і ордіналов.

Теорема 47. Існує безліч точок на плоско ¬ сти, яке перетинається з кожною прямий рівно в двох точках.

Дві паралельні прямі майже задовольняють цій вимозі (винятком є ​​лише парал ¬ лельно їм прямі). Але позбутися цього виключення не так просто.

<Вимоги до безлічі можна сформулювати так: ніякі три точки не лежать на одній прямій, але будь-яка пряма перетинає його не менш ніж у двох точках.

Будемо будувати це безліч трансфінітних рекур ¬ нормуванню. Нехай а - мінімальний ордінала, що має мощ ¬ ність континууму. (Якщо континуум-гіпотеза вірна, то він збігається з К, але це нам не важливо.) Тоді множест ¬ во всіх менших ордіналов можна поставити у взаємно однозначну відповідність з безліччю всіх прямих на площині. Нехай 1 @ - пряма, відповідна ординар ¬ налу Р <а.

Для кожного ¡3 <а побудуємо безліч Мр, в кото ¬ ром ніякі три точки не лежать на одній прямій, сліду ¬ ющим чином. Об'єднаймо всі побудовані раніше мно ¬ дружність М7 при всіх 7 </?. Чи можуть в цій множині (позначимо його Г) якісь три точки лежати на одній прямій? Якщо так, то ці точки беруться з якихось мно ¬ дружність М1г, М72, М13; візьмемо найбільший з ордіналов 71; 72; 7з, у відповідному безлічі будуть три точ ¬ ки, що лежать на одній прямій, що суперечить пред ¬ положенню індукції .

Подивимося, у скількох точках перетинає пряма 1р безліч Г. Таких точок (по доведеному) не більше двох. Якщо їх рівно дві, то все добре і ми нових то ¬ чек не додаємо, вважаючи, що Мр = Т. Якщо їх мен ¬ ше, то ми повинні додати нові точки (до двох), але тільки так, щоб при цьому не утворилося трьох точок, що лежать на одній прямій. Іншими словами, не можна до ¬ додавали точки, які лежать на перетині 1р з пря ¬ мимі, що проходять через пари вже наявних точок.

Скільки таких прямих (тобто скільки пар вже име ¬ ющіхся точок)? За побудовою видно, що все вже маю ¬ щиеся точки лежать по дві на кожній прямий 11 при 7 </ 9. (Строго кажучи, це слід включити в індуктивне припущення.) Таким чином, безліч Г по мощ ¬ ності є 2/3 = /], а пар точок не більше 01 = ¡3 <з По ¬ цього заборонені точки складають лише малу (по потужності) частину прямий 1р, і можна вибрати дві разре ¬ шенние точки.

Тепер залишилося об'єднати безлічі Мр для всіх ордіналов (3 <а й отримати шукане безліч. (За умовою три точки на одній прямій в ньому з'явитися не можуть, а всяка пряма буде рано чи пізно роз ¬ трена і дві точки на ній будуть забезпечені.) >

154. Знайдіть помилку у наступному «спростування гіпо ¬ тези континууму»: нехай N1 = с. Впорядкуємо відрізок [0,1] за типом N1. Розглянемо функцію двох змінних, рівну одиниці на парі (х, у), якщо х <у (в сенсі цього порядку), і нулю в інших випадках. Тоді при фіксованому х фун-кия у н-► / (х, у) дорівнює одиниці скрізь, крім лічильного безлі ¬ ства, і тому интегрируема і / / (ж, у) йу = 1 при будь-якому х. З іншого боку, функція х н / (х, у) дорівнює нулю всюди, крім лічильного безлічі, так що /} {х, у) йх = 0. Отримувачі ¬ ем протиріччя з теоремою Фубіні, яка стверджує, що