У статті розглядаються різні формулювання і доводиться еквівалентність таких тверджень:
Еквівалентність цих тверджень слід розуміти в тому сенсі, що будь-якого з них, разом із системою аксіом Цермело — Френкеля (ZF), достатньо, щоб довести інші.
Лема Цорна і принцип максимуму Гаусдорфа
Формулювання леми Цорна.
Частково впорядкована множина, в якій будь-який ланцюг має верхню грань, містить максимальний елемент.
Якщо будь-який ланцюг у частково впорядкованій множині
має верхню грань, то будь-який елемент із
підпорядкований деякому максимальному.
Нехай сімейство множин
володіє тією властивістю, що об'єднання будь-якого ланцюга множин з
є знову множиною цього сімейства. Тоді
містить максимальну множину.
Формулювання принципу максимуму Гаусдорфа (англ. Hausdorff Maximal Principle):
У будь-якій частково впорядкованій множині існує максимальна лінійно впорядкована підмножина.
У частково впорядкованій множині кожен ланцюг міститься в деякому її максимальному ланцюгу.
Еквівалентність цих пропозицій доводитимемо за такою схемою:
Ясно, що випливає із
, оскільки в
стверджується більше: існує максимальний елемент, більший від заданого
. І навпаки, нехай
— частково впорядкована множина, в якій будь-який ланцюг має верхню грань, і нехай
. Застосуємо
до множини
. Її максимальний елемент
також є і максимальним елементом
, і, крім того, задовольняє умові
.
Сімейство множин частково впорядковане за теоретико-множинним відношенням включення
. Будь-який ланцюг множин
має верхню грань — це множина
, яка, за припущенням, належить системі
. У силу
в сімействі є максимальний елемент, тобто максимальна за включенням множина.
Нехай — частково впорядкована множина,
— ланцюг у
,
— множина всіх ланцюгів у
, що містять
, упорядкованих відносно включення. Існування максимального ланцюга, що містить
, тепер випливає із
, стосовно до
, і того факту, що об'єднання всіх множин ланцюга в
(«ланцюги ланцюгів»), знову є множиною з
.
Очевидно. — окремий випадок
, коли початковий ланцюг — порожня множина
.
Нехай — частково впорядкована множина в умові
. Розглянемо максимальний ланцюг
в
, існування якого випливає з
. За умовою цей ланцюг має верхню грань
. Тоді
є максимальним елементом
, і крім того, належить ланцюгу. Припустивши протилежне, ми прийдемо до суперечності з умовою максимальності
.
Ці міркування доводять еквівалентність принципу максимуму Гаусдорфа і леми Цорна.
Теорема Цермело
Формулювання теореми Цермело (англ. Well Ordering Principle)
Будь-яку множину можна цілком упорядкувати.
Нехай — довільна дана множина. Покажемо, що її можна цілком упорядкувати.
Розглянемо сукупність усіх пар
, де
, а
— відношення повного порядку на
. На множині
уведемо природне відношення порядку:
слідує за
, якщо
є
, тобто якщо
для деякого
і на множині
відношення
збігається з
.
Далі доведемо два твердження.
I. В існує максимальний елемент. Це випливає із
і того факту, що якщо
— ланцюг у
, то об'єднання всіх елементів
є також елементом
, який є верхньою гранню ланцюга
.
II. Якщо — максимальний елемент, то
. Якби
була непорожньою, то взявши який-небудь елемент
, і поклавши
для будь-якого
, ми отримали б цілком упорядковану множину
, початковим відрізком якої є
. Це суперечить припущенню про максимальність
.
Таким чином, ми маємо цілком упорядковану множину . Що й потрібно було довести.
Нехай частково впорядкована множина. В силу теореми Цермело множину
можна цілком упорядкувати. Нехай
— відношення цілкомупорядкування на
.
Визначимо розбиття множини на дві підмножини
і
індукцією за цілком упорядкованою множиною
(такий спосіб також називають ).
Нехай і всі елементи
вже віднесено або до
, або до
. Віднести
до
, якщо він порівняємо з усіма елементами
; в іншому випадку віднесемо його до
.
Проводячи таким чином індуктивну побудову за цілком впорядкованою множиною ми отримаємо множини
і
. Як видно з побудови
— ланцюг в
. Крім того, ясно, що він є максимальним. Таким чином, ми довели принцип максимуму Гаусдорфа.
Аксіома вибору
Формулювання аксіоми вибору:
Для кожного сімейства непорожніх множин
існує функція вибору
, тобто
Достатньо довести еквівалентність одному з тверджень
. Однак нижче наведено декілька доведень.
Див. книгу Гаусдорфа, або Куроша.
Міркування аналогічне тому, що використовувалося для доведення .
Упорядкуємо кожне , і потім визначимо функцію вибору як мінімальний елемент множини:
Див. книгу Куроша.
Джерела
- Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : , 1937. — 304 с. — .(рос.)
- Александров П.С. Введение в теорию множеств и общую топологию. — Москва : Наука, 1977. — 368 с. — .(рос.)
- Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 4-е изд. — Москва : Наука, 1976. — 544 с. — .(рос.)
- Курош А. Г. Лекции по общей алгебре. — 2 изд. — М. : Наука, 1973. — 400 с.(рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U statti rozglyadayutsya rizni formulyuvannya i dovoditsya ekvivalentnist takih tverdzhen Aksioma viboru Teorema Cermelo Princip maksimumu Gausdorfa Lema Corna Ekvivalentnist cih tverdzhen slid rozumiti v tomu sensi sho bud yakogo z nih razom iz sistemoyu aksiom Cermelo Frenkelya ZF dostatno shob dovesti inshi Lema Corna i princip maksimumu GausdorfaFormulyuvannya lemi Corna Z L 1 displaystyle mathcal ZL 1 Chastkovo vporyadkovana mnozhina v yakij bud yakij lancyug maye verhnyu gran mistit maksimalnij element Z L 2 displaystyle mathcal ZL 2 Yaksho bud yakij lancyug u chastkovo vporyadkovanij mnozhini M displaystyle M maye verhnyu gran to bud yakij element iz M displaystyle M pidporyadkovanij deyakomu maksimalnomu Z L 3 displaystyle mathcal ZL 3 Nehaj simejstvo mnozhin M displaystyle mathfrak M volodiye tiyeyu vlastivistyu sho ob yednannya bud yakogo lancyuga mnozhin z M displaystyle mathfrak M ye znovu mnozhinoyu cogo simejstva Todi M displaystyle mathfrak M mistit maksimalnu mnozhinu Formulyuvannya principu maksimumu Gausdorfa angl Hausdorff Maximal Principle H M 1 displaystyle mathcal HM 1 U bud yakij chastkovo vporyadkovanij mnozhini isnuye maksimalna linijno vporyadkovana pidmnozhina H M 2 displaystyle mathcal HM 2 U chastkovo vporyadkovanij mnozhini kozhen lancyug mistitsya v deyakomu yiyi maksimalnomu lancyugu Ekvivalentnist cih propozicij dovoditimemo za takoyu shemoyu Z L 1 I Z L 2 I I Z L 3 I I I H M 2 I V H M 1 V Z L 1 displaystyle mathcal ZL 1 quad overset I Leftrightarrow quad mathcal ZL 2 quad overset II Rightarrow quad mathcal ZL 3 quad overset III Rightarrow quad mathcal HM 2 quad overset IV Rightarrow quad mathcal HM 1 quad overset V Rightarrow quad mathcal ZL 1 I Z L 1 Z L 2 displaystyle I mathcal ZL 1 Leftrightarrow mathcal ZL 2 Yasno sho Z L 1 displaystyle mathcal ZL 1 viplivaye iz Z L 2 displaystyle mathcal ZL 2 oskilki v Z L 2 displaystyle mathcal ZL 2 stverdzhuyetsya bilshe isnuye maksimalnij element bilshij vid zadanogo a displaystyle a I navpaki nehaj M displaystyle M chastkovo vporyadkovana mnozhina v yakij bud yakij lancyug maye verhnyu gran i nehaj a M displaystyle a in M Zastosuyemo Z L 1 displaystyle mathcal ZL 1 do mnozhini M m M m a displaystyle M m in M mid m geqslant a Yiyi maksimalnij element a displaystyle overline a takozh ye i maksimalnim elementom M displaystyle M i krim togo zadovolnyaye umovi a a displaystyle a leqslant overline a I I Z L 2 Z L 3 displaystyle II mathcal ZL 2 Rightarrow mathcal ZL 3 Simejstvo mnozhin M displaystyle mathfrak M chastkovo vporyadkovane za teoretiko mnozhinnim vidnoshennyam vklyuchennya displaystyle subseteq Bud yakij lancyug mnozhin M a displaystyle M alpha maye verhnyu gran ce mnozhina M a displaystyle bigcup M alpha yaka za pripushennyam nalezhit sistemi M displaystyle mathfrak M U silu Z L 2 displaystyle mathcal ZL 2 v simejstvi ye maksimalnij element tobto maksimalna za vklyuchennyam mnozhina I I I Z L 3 H M 2 displaystyle III mathcal ZL 3 Rightarrow mathcal HM 2 Nehaj M displaystyle M chastkovo vporyadkovana mnozhina C 0 displaystyle C 0 lancyug u M displaystyle M M displaystyle mathfrak M mnozhina vsih lancyugiv u M displaystyle M sho mistyat C 0 displaystyle C 0 uporyadkovanih vidnosno vklyuchennya Isnuvannya maksimalnogo lancyuga sho mistit C 0 displaystyle C 0 teper viplivaye iz Z L 3 displaystyle mathcal ZL 3 stosovno do M displaystyle mathfrak M i togo faktu sho ob yednannya vsih mnozhin lancyuga v M displaystyle mathfrak M lancyugi lancyugiv znovu ye mnozhinoyu z M displaystyle mathfrak M I V H M 2 H M 1 displaystyle IV mathcal HM 2 Rightarrow mathcal HM 1 Ochevidno H M 1 displaystyle mathcal HM 1 okremij vipadok H M 2 displaystyle mathcal HM 2 koli pochatkovij lancyug porozhnya mnozhina displaystyle varnothing V H M 1 Z L 1 displaystyle V mathcal HM 1 Rightarrow mathcal ZL 1 Nehaj M displaystyle M chastkovo vporyadkovana mnozhina v umovi Z L 1 displaystyle mathcal ZL 1 Rozglyanemo maksimalnij lancyug C displaystyle C v M displaystyle M isnuvannya yakogo viplivaye z H M 1 displaystyle mathcal HM 1 Za umovoyu cej lancyug maye verhnyu gran a displaystyle overline a Todi a displaystyle overline a ye maksimalnim elementom M displaystyle M i krim togo nalezhit lancyugu Pripustivshi protilezhne mi prijdemo do superechnosti z umovoyu maksimalnosti C displaystyle C Ci mirkuvannya dovodyat ekvivalentnist principu maksimumu Gausdorfa i lemi Corna Teorema CermeloDokladnishe Teorema Cermelo Formulyuvannya teoremi Cermelo angl Well Ordering Principle W O displaystyle mathcal WO Bud yaku mnozhinu mozhna cilkom uporyadkuvati Z L 1 W O displaystyle mathcal ZL 1 Rightarrow mathcal WO Nehaj M displaystyle M dovilna dana mnozhina Pokazhemo sho yiyi mozhna cilkom uporyadkuvati Rozglyanemo sukupnist M displaystyle mathfrak M usih par A A displaystyle langle A leqslant A rangle de A M displaystyle A subseteq M a A displaystyle leqslant A vidnoshennya povnogo poryadku na A displaystyle A Na mnozhini M displaystyle mathfrak M uvedemo prirodne vidnoshennya poryadku B B displaystyle langle B leqslant B rangle sliduye za A A displaystyle langle A leqslant A rangle yaksho A A displaystyle langle A leqslant A rangle ye B B displaystyle langle B leqslant B rangle tobto yaksho A a B a lt b displaystyle A a in B a lt b dlya deyakogo b B displaystyle b in B i na mnozhini A displaystyle A vidnoshennya B displaystyle leqslant B zbigayetsya z A displaystyle leqslant A Dali dovedemo dva tverdzhennya I V M displaystyle mathfrak M isnuye maksimalnij element Ce viplivaye iz Z L 1 displaystyle mathcal ZL 1 i togo faktu sho yaksho C displaystyle mathfrak C lancyug u M displaystyle mathfrak M to ob yednannya vsih elementiv C C displaystyle C in mathfrak C ye takozh elementom M displaystyle mathfrak M yakij ye verhnoyu grannyu lancyuga C displaystyle mathfrak C II Yaksho A A displaystyle langle A leqslant A rangle maksimalnij element to A M displaystyle A M Yakbi M A displaystyle M setminus A bula neporozhnoyu to vzyavshi yakij nebud element b M A displaystyle b in M setminus A i poklavshi b gt a displaystyle b gt a dlya bud yakogo a A displaystyle a in A mi otrimali b cilkom uporyadkovanu mnozhinu A a displaystyle A cup a pochatkovim vidrizkom yakoyi ye A displaystyle A Ce superechit pripushennyu pro maksimalnist A A displaystyle langle A leqslant A rangle Takim chinom mi mayemo cilkom uporyadkovanu mnozhinu M M displaystyle langle M leqslant M rangle Sho j potribno bulo dovesti W O H M 1 displaystyle mathcal WO Rightarrow mathcal HM 1 Nehaj M displaystyle langle M preceq rangle chastkovo vporyadkovana mnozhina V silu teoremi Cermelo mnozhinu M displaystyle M mozhna cilkom uporyadkuvati Nehaj displaystyle leqslant vidnoshennya cilkomuporyadkuvannya na M displaystyle M Viznachimo rozbittya mnozhini M displaystyle M na dvi pidmnozhini C displaystyle C i C displaystyle overline C indukciyeyu za cilkom uporyadkovanoyu mnozhinoyu M displaystyle langle M leqslant rangle takij sposib takozh nazivayut Nehaj a M displaystyle a in M i vsi elementi b lt a displaystyle b lt a vzhe vidneseno abo do C displaystyle C abo do C displaystyle overline C Vidnesti a displaystyle a do C displaystyle C yaksho vin porivnyayemo z usima elementami C displaystyle C v inshomu vipadku vidnesemo jogo do C displaystyle overline C Provodyachi takim chinom induktivnu pobudovu za cilkom vporyadkovanoyu mnozhinoyu M displaystyle langle M leqslant rangle mi otrimayemo mnozhini C displaystyle C i C displaystyle overline C Yak vidno z pobudovi C displaystyle C lancyug v M displaystyle langle M preceq rangle Krim togo yasno sho vin ye maksimalnim Takim chinom mi doveli princip maksimumu Gausdorfa Aksioma viboruDokladnishe Aksioma viboru Formulyuvannya aksiomi viboru A C displaystyle mathcal AC Dlya kozhnogo simejstva neporozhnih mnozhin S a a A displaystyle S alpha alpha in A isnuye funkciya viboru f displaystyle f tobto a f a S a displaystyle forall alpha f alpha in S alpha Dostatno dovesti ekvivalentnist A C displaystyle mathcal AC odnomu z tverdzhen Z L H M W O displaystyle mathcal ZL mathcal HM mathcal WO Odnak nizhche navedeno dekilka doveden A C W O displaystyle mathcal AC Rightarrow mathcal WO Div knigu Gausdorfa abo Kurosha A C H M displaystyle mathcal AC Rightarrow mathcal HM Mirkuvannya analogichne tomu sho vikoristovuvalosya dlya dovedennya A C W O displaystyle mathcal AC Rightarrow mathcal WO Uporyadkuyemo kozhne S a displaystyle S alpha i potim viznachimo funkciyu viboru yak minimalnij element mnozhini f a min S a displaystyle f alpha min S alpha Z L A C displaystyle mathcal ZL Rightarrow mathcal AC Div knigu Kurosha DzherelaHausdorf F Teoriya mnozhestv Moskva Leningrad 1937 304 s ISBN 978 5 382 00127 2 ros Aleksandrov P S Vvedenie v teoriyu mnozhestv i obshuyu topologiyu Moskva Nauka 1977 368 s ISBN 5354008220 ros Kolmogorov A N Fomin S V Elementy teorii funkcij i funkcionalnogo analiza 4 e izd Moskva Nauka 1976 544 s ISBN 5 9221 0266 4 ros Kurosh A G Lekcii po obshej algebre 2 izd M Nauka 1973 400 s ros