Аксиома выбора

Материал из Википедии — свободной энциклопедии

Аксио́ма вы́бора утверждает: «Для каждого семейства $A$ непустых непересекающихся множеств существует множество $B$ , имеющее один и только один общий элемент с каждым из множеств $X$ , принадлежащих $A$ ».

Аксиома выбора не всеми математиками принимается безоговорочно, некоторые относятся к ней с недоверием. Бытует мнение, что доказательства, полученные с привлечением этой аксиомы, имеют иную познавательную ценность, чем доказательства, независимые от неё. Основано оно, прежде всего, на том, что утверждается лишь существование множества $B$ , но не дается никакого способа его определения – отсюда неэффективность в случае бесконечных множеств. Это мнение, например, Бореля и Лебега. Противоположного мнения придерживались, например, Хаусдорф и Френкель, которые принимали аксиому выбора без всяких оговорок, признавая за ней ту же степень «очевидности», что и за другими аксиомами теории множеств: аксиома объемности, аксиома существования пустого множества, аксиома пары, аксиома суммы, аксиома степени, аксиома бесконечности. Более того, среди следствий аксиомы выбора есть много довольно специфичных: например, появляется возможность доказать парадокс Банаха—Тарского, который вряд ли можно считать «очевидным». Подробный анализ многочисленных доказательств, использующих аксиому выбора, провел Серпиньский. Однако, без сомнения, многие важные математические открытия нельзя было бы сделать без аксиомы выбора.

[править] Альтернативные формулировки

Аксиома выбора утверждает:

Пусть X — множество непустых множеств. Тогда мы можем выбрать единственный элемент из каждого множества в X.

Функция выбора — функция на множестве множеств X такая, что для каждого множества s в X, f(s) является элементом из s. С использованием понятия функции выбора аксиома утверждает:

Для любого семейства непустых множеств X существует функция выбора f, определенная на X.

Или альтернативно:

Произвольное декартово произведение непустых множеств непусто.

Или наиболее сжато:

Каждое множество непустых множеств имеет функцию выбора.

Отсюда немедленно следует компактная формулировка отрицания аксиомы выбора:

Существует множество непустых множеств, которое не имеет никакой функции выбора.

Вторая версия аксиомы выбора утверждает:

Для данного произвольного множества попарно непересекающихся непустых множеств существует, по крайней мере, одно множество, которое содержит точно один элемент, общий с каждым из непустых множеств.

Некоторые авторы используют другую версию, которая эффективно утверждает:

Для любого множества A, степенное множество (минус пустое подмножество) имеет функцию выбора.

Авторы, которые используют эту формулировку, часто также говорят о «функции выбора на A», но оговаривают, что имеют ввиду немного другое понятие функции выбора. Её область определения — степенное множество (минус пустое подмножество), тогда как в других местах этой статьи, область определения функции выбора — «множество множеств». С этим дополнительным понятием функции выбора, аксиома выбора может быть сжато сформулирована так:

Каждое множество имеет функцию выбора.

[править] Принцип вполне упорядочивания (теорема Цермело)

Очень распостранённая и удобная формулировка использует понятие вполне упорядоченного множества. Нам потребуется несколько определений, и мы начнём со строгого определения линейного порядка, выражающего знакомую нам идею на языке теории множеств. Напомним, что упорядоченная пара множеств обозначается $(x, y)$ и что декартово произведение множеств $X \times Y$ состоит из всех возможных упорядоченных пар $(x, y)$ где $x \in X, y \in Y$ .

Линейным порядком на множестве $A$ называется подмножество декартова произведения $R \subseteq A \times A$ , обладающее следующим свойствами:

Полное: $\forall x,y \in A ((x,y) \in R \vee (y,x) \in R)$

Антисимметричное: $\forall x,y \in A((x,y) \in R \wedge (y,x) \in R \rightarrow y=x)$

Транзитивное: $\forall x,y,z \in A ((x,y)\in R \wedge (y,z) \in R \rightarrow (x,z) \in R)$

Полным порядком на множестве $A$ называется такой линейный порядок, что каждое подмножество $X \subseteq A$ имеет наименьший элемент.

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

Например, множество натуральных чисел может быть вполне упорядоченно обычным отношением «меньше или равно чем». С тем же отношением, множество целых чисел не имеет наименьшего элемента. В этом случае мы можем собрать целые числа в последовательность (0, −1, 1, −2, 2, … , −n, n, …) и сказать, что младшие члены меньше чем старшие. Очевидно, такое отношение будет полным порядком на целых числах.

Гораздо менее очевидно, что действительные числа, формирующие несчётное множество, могут быть вполне упорядочены.

[править] Лемма Цорна

Если в частично упорядоченном множестве любая цепь (то есть линейно упорядоченное подмножество) имеет верхнюю грань, то всё множество имеет хотя бы один максимальный элемент.

Более формально:

Пусть $(P,\le)$ — частично упорядоченное множество, то есть, отношение $\le$ рефлексивно, антисимметрично и транзитивно:

$\forall x\in P\quad x\le x$

$\forall x,y\in P\quad x\le y \and y\le x \rightarrow x=y$

$\forall x,y,z\in P\quad x\le y \and y\le z \rightarrow x\le z$

Подмножество $S\subset P$ называется линейно упорядоченным, если $\forall x,y\in S\quad x\le y \or y\le x$ . Элемент $u\in S$ называется верхней гранью, если $\forall x\in S\quad x\le u$ . Допустим, что любое линейно упорядоченное подмножество множества $P$ имеет верхнюю грань. Тогда $\exists m\in P \forall x\in P\quad m\le x\rightarrow m=x$ — максимальный элемент.