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

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

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

Полное: .

Антисимметричное: .

Транзитивное: .

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

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

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

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

Лемма Цорна

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

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

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

Подмножество называется линейно упорядоченным, если.

.

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

— максимальный элемент.