Введение

Теоретический принцип в математике, утверждающий, что каждое множество может быть вполне упорядочено. В математике теорема о вполне упорядочении, также известная как теорема Зермело, утверждает, что каждое множество может быть вполне упорядочено. Множество X вполне упорядочено отношением строгого полного порядка, если каждое непустое подмножество X имеет наименьший элемент относительно этого порядка. Теорема о вполне упорядочении вместе с леммой Зорна являются наиболее важными математическими утверждениями, эквивалентными аксиоме выбора (часто обозначаемой AC, см. также). Эрнст Зермело ввёл аксиому выбора как «неоспоримый логический принцип» для доказательства теоремы о вполне упорядочении. Из теоремы о вполне упорядочении следует, что каждое множество подвержено трансфинитной индукции, которая математиками считается мощным методом. Однако визуализировать вполне упорядоченное множество считается трудным или даже невозможным; такая визуализация потребовала бы использования аксиомы выбора. В 1904 году Дьюла Кёниг заявил, что доказал невозможность существования такого вполне упорядочения. Через несколько недель Феликс Хаусдорф обнаружил ошибку в доказательстве. Однако оказалось, что в логике первого порядка теорема о вполне упорядочении эквивалентна аксиоме выбора, в том смысле, что аксиомы Цермело — Френкеля с включённой аксиомой выбора достаточны для доказательства теоремы о вполне упорядочении, и наоборот, аксиомы Цермело — Френкеля без аксиомы выбора, но с включённой теоремой о вполне упорядочении, достаточны для доказательства аксиомы выбора. (То же самое справедливо и для леммы Зорна.) В логике второго порядка, однако, теорема о вполне упорядочении строго сильнее аксиомы выбора: из теоремы о вполне упорядочении можно вывести аксиому выбора, но из аксиомы выбора нельзя вывести теорему о вполне упорядочении. Существует известная шутка об этих трёх утверждениях и их относительной интуитивной понятности: аксиома выбора очевидно истинна, принцип вполне упорядочения очевидно ложен, а кто может что-нибудь сказать о лемме Зорна?

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

Теорема о хорошем упорядочении следует из аксиомы выбора следующим образом. Пусть множество, которое мы пытаемся хорошо упорядочить, будет , а — функцией выбора для семейства непустых подмножеств . Для каждого ординала определим элемент , принадлежащий , следующим образом: если дополнение непусто, то устанавливаем , иначе оставляем неопределённым. Иными словами, выбирается из множества элементов , которым ещё не было присвоено место в упорядочении (или остаётся неопределённым, если все элементы успешно перечислены). Тогда порядок на , определяемый условием ⇔ (в обычном порядке ординалов), является хорошим упорядочением множества , имеющего порядок типа .

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

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

Важный момент этого доказательства заключается в том, что оно включает в себя лишь один произвольный выбор, а именно выбор упорядочения . Применение теоремы о хорошем упорядочении к каждому элементу из коллекции по отдельности не сработало бы, поскольку теорема лишь утверждает существование хорошего упорядочения, а выбор для каждого элемента отдельного хорошего упорядочения потребовал бы столько же выборов, сколько и просто выбор элемента из каждого множества. В частности, если содержит несчетно много множеств, то выполнение всех этих несчетно многих выборов недопустимо в рамках аксиоматической теории множеств Цермело — Френкеля без аксиомы выбора.