§ 69. Аксиома выбора и лемма Цорна

Цермело первым заметил, что многочисленные математические исследования опираются на некоторую аксиому, которую он сформулировал как аксиому выбора. Состоит она в следующем:

Если задано некоторое множество непустых множеств, то существует «функция выбора», т. е. функция, которая каждому из этих множеств сопоставляет какой-либо его элемент.

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

Всюду в дальнейшем, где это будет нужно, мы предполагаем выполненной аксиому выбора.

Важными следствиями из аксиомы выбора являются лемма Цорна и теорема о том, что каждое множество можно вполне упорядочить. В настоящем параграфе мы сформулируем и докажем лемму Цорна, а в следующем параграфе — теорему о полном упорядочении.

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

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

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

Принцип максимума или лемма Цорна утверждает:

Каждое замкнутое подмножество А в множестве содержит по меньшей мере один максимальный элемент

Эту лемму можно сформулировать несколько более общим образом, следуя Бурбаки. Вместо подмножества А из можно рассматривать произвольное полуупорядоченное множество Цепь как и прежде, определяется как линейно упорядоченное подмножество в Для любых двух элементов некоторой цепи должно, следовательно, выполняться одно из соотношений: а или или

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

Любое частично упорядоченное замкнутое множество содержит максимальный элемент

Согласно Кнезеру существование максимального элемента можно доказать при более слабых предположениях. Вместо требования о том, чтобы множество содержало вместе с каждым своим линейно упорядоченным подмножеством К и его верхнюю грань, достаточно предположить, что содержит вместе с каждым своим вполне упорядоченным подмножеством К какую-либо его верхнюю границу Кроме того, как показал Кнезер, при этом ослабленном предположении доказывается «основная лемма Бурбаки».

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

Пусть частично упорядоченное замкнутое множество, и пусть некоторое отображение множества в себя, обладающее следующим свойством:

Тогда в существует элемент со свойством:

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

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

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

Пусть теперь частично упорядоченное и замкнутое множество. Каждая цепь обладает тогда некоторой верхней гранью в Каждый отрезок вновь является некоторой цепью и поэтому обладает верхней гранью Если подмножество К вполне упорядочено и для каждого у из К имеет место равенство то К называется -цепью. Каждое начало любой -цепи вновь является -цепью.

Пусть некоторые -цепи. Покажем, что если К не является началом множества то начало множества

Начала множества это отрезки К у и само множество Так как К вполне упорядочено отношением множество начал вполне упорядочивается отношением с. Если К не является началом множества то существует первое начало А множества К, не являющееся началом множества

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

Следовательно, мы можем предположить, что А обладает некоторым последним элементом у. Начало является началом в Если и если — первый элементе не принадлежащий множеству А, то

следовательно,

Теперь А состоит в точности из А и у, т. е. А является началом в что противоречит предположению. Остается лишь одна возможность: является началом в К.

Таким образом, из двух -цепей всегда одна является началом другой.

Построим теперь объединение V всех -цепей. Тогда:

1) множество V линейно упорядочено и, следовательно, является цепью;

2) множество V вполне упорядочено;

3) в множестве V имеет место равенство для каждого у, т. е. V является -цепью;

4) если к V добавить еще один элемент то полученное множество не будет -цепью.

Положим Так как то элемент является верхней границей множества Если бы не принадлежало множеству V, то множество было бы -цепью, что противоречит 4). Следовательно, принадлежит множеству Поэтому

С другой стороны, было известно, что следовательно,

чем и доказывается основная лемма.

Теперь мы предположим выполненной аксиому выбора и докажем принцип максимума.

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