Теорема о хорошем порядке

Теоретический принцип математики, утверждающий, что любое множество может быть вполне упорядочено.

В математике теорема о хорошем порядке , также известная как теорема Цермело , утверждает, что каждое множество может быть хорошо упорядочено . Множество X хорошо упорядочено строгим полным порядком , если каждое непустое подмножество X имеет наименьший элемент при упорядочении. Теорема о хорошем порядке вместе с леммой Цорна являются важнейшими математическими утверждениями, которые эквивалентны аксиоме выбора (часто называемой AC, см. также Аксиома выбора § Эквиваленты ). ^{[1] [2]} Эрнст Цермело ввел аксиому выбора как «не вызывающий возражений логический принцип» для доказательства теоремы о хорошем порядке. ^[3] Из теоремы о хорошем порядке можно сделать вывод, что каждое множество восприимчиво к трансфинитной индукции , которая рассматривается математиками как мощный метод. ^[3] Одним из известных следствий теоремы является парадокс Банаха–Тарского .

История

Георг Кантор считал теорему о хорошем порядке «фундаментальным принципом мышления». ^[4] Однако считается, что трудно или даже невозможно визуализировать хорошее упорядочение ; такая визуализация должна включать аксиому выбора. ^[5] В 1904 году Дьюла Кёниг заявил, что доказал, что такое хорошее упорядочение не может существовать. Несколько недель спустя Феликс Хаусдорф обнаружил ошибку в доказательстве. ^[6] Однако оказалось, что в логике первого порядка теорема о хорошем порядке эквивалентна аксиоме выбора в том смысле, что аксиомы Цермело–Френкеля с включенной аксиомой выбора достаточны для доказательства теоремы о хорошем порядке, и наоборот, аксиомы Цермело–Френкеля без аксиомы выбора, но с включенной теоремой о хорошем порядке достаточны для доказательства аксиомы выбора. (То же самое относится и к лемме Цорна .) Однако в логике второго порядка теорема о хорошем порядке строго сильнее аксиомы выбора: из теоремы о хорошем порядке можно вывести аксиому выбора, но из аксиомы выбора нельзя вывести теорему о хорошем порядке. ^[7] ${\displaystyle \mathbb {R} }$

Существует известная шутка об этих трех утверждениях и их относительной поддаемости интуиции:

Аксиома выбора, очевидно, истинна, принцип хорошего порядка, очевидно, ложен, и кто может сказать что-либо о лемме Цорна ? ^[8]

Доказательство из аксиомы выбора

Теорема о хорошем порядке вытекает из аксиомы выбора следующим образом. ^[9]

Пусть множество, которое мы пытаемся хорошо упорядочить, будет , и пусть будет функцией выбора для семейства непустых подмножеств . Для каждого ординала определите элемент , который находится в , установив , если это дополнение непусто, или оставьте неопределенным, если это так. То есть, выбирается из множества элементов , которым еще не было назначено место в упорядочении (или не определено, если все было успешно перечислено). Тогда порядок на определяется с помощью , если и только если (в обычном хорошем порядке ординалов) является хорошим порядком , как и требуется, типа порядка . ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle \alpha }$ ${\displaystyle a_{\alpha }}$ ${\displaystyle A}$ ${\displaystyle a_{\alpha }\ =\ f(A\smallsetminus \{a_{\xi }\mid \xi <\alpha \})}$ ${\displaystyle A\smallsetminus \{a_{\xi }\mid \xi <\alpha \}}$ ${\displaystyle a_{\alpha }}$ ${\displaystyle a_{\alpha }}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle <}$ ${\displaystyle A}$ ${\displaystyle a_{\alpha }<a_{\beta }}$ ${\displaystyle \alpha <\beta }$ ${\displaystyle A}$ ${\displaystyle \sup\{\alpha \mid a_{\alpha }{\text{ is defined}}\}}$

Доказательство аксиомы выбора

Аксиому выбора можно доказать из теоремы о хорошем порядке следующим образом.

Чтобы создать функцию выбора для набора непустых множеств, , возьмите объединение множеств в и назовите его . Существует вполне упорядоченное множество ; пусть будет таким упорядочением. Функция, которая каждому множеству из сопоставляет наименьший элемент из , как упорядочено (ограничением на из) , является функцией выбора для набора . ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle E}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle E}$

Существенным моментом этого доказательства является то, что оно включает в себя только один произвольный выбор, а именно ; применение теоремы о хорошем порядке к каждому члену по отдельности не сработает, поскольку теорема утверждает только существование хорошего порядка, а выбор для каждого хорошего порядка потребовал бы столько же выборов, сколько и простой выбор элемента из каждого . В частности, если содержит несчетное множество множеств, то осуществление всех несчетных выборов не допускается в соответствии с аксиомами теории множеств Цермело-Френкеля без аксиомы выбора. ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle E}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle E}$

Примечания

1. Кучма, Марек (2009). Введение в теорию функциональных уравнений и неравенств. Берлин: Springer. С. 14. ISBN 978-3-7643-8748-8.
2. Хазевинкель, Мишель (2001). Энциклопедия математики: Приложение. Берлин: Шпрингер. п. 458. ИСБН 1-4020-0198-3.
3. Тьерри, Виалар (1945). Справочник по математике. Нордерштедт: Шпрингер. п. 23. ISBN 978-2-95-519901-5.
4. Георг Кантор (1883), «Ueber unendliche, Lineare Punktmannichfaltigkeiten», Mathematische Annalen 21, стр. 545–591.
5. Шеппард, Барнаби (2014). Логика бесконечности. Cambridge University Press. стр. 174. ISBN 978-1-1070-5831-6.
6. Плоткин, Дж. М. (2005), «Введение в «Концепцию мощности в теории множеств»", Хаусдорф об упорядоченных множествах, История математики, т. 25, Американское математическое общество, стр. 23–30, ISBN 9780821890516
7. Шапиро, Стюарт (1991). Основания без фундаментализма: случай в пользу логики второго порядка . Нью-Йорк: Oxford University Press. ISBN 0-19-853391-8.
8. Кранц, Стивен Г. (2002), «Аксиома выбора», в Кранц, Стивен Г. (ред.), Справочник по логике и методам доказательства для компьютерных наук , Birkhäuser Boston, стр. 121–126, doi :10.1007/978-1-4612-0115-1_9, ISBN 9781461201151
9. Джех, Томас (2002). Теория множеств (издание третьего тысячелетия) . Спрингер . п. 48. ИСБН 978-3-540-44085-7.

Внешние ссылки

• Доказательство системы Mizar : http://mizar.org/version/current/html/wellord2.html