8. Вполне упорядоченные множества

Рассмотрим множество , про некоторые пары элементов которого известно, что (т. е. на множестве задано отношение порядка). Отношение порядка можно также интерпретировать как подмножество квадрата множества : в таблице, строки и столбцы которой соответствуют элементам множества , некоторые клетки заштрихованы — если заштрихована клетка на пересечении столбца и строки , то .

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

1) для любого ;

2) если и , то ;

3) если и , то .

Отношением порядка являются, например, обычное сравнение чисел на прямой (), вложенность множеств (), отношение "делит" ( — делит ).

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

Забегая немного вперед, скажем, что упорядочение элементов множества необходимо, в частности, для того, чтобы можно было рассматривать объекты по индукции: хочется иметь возможность сначала рассмотреть первый элемент, доказать для него некоторое утверждение, а затем, используя то, что это утверждение верно для первых элементов, вывести его и для -го. Для натуральных чисел доказательство принципа математической индукции опирается на тот факт, что любое непустое подмножество натуральных чисел имеет наименьший элемент.

Рис. 4

От произвольного отношения порядка и произвольного множества хочется выполнения аналогичного свойства: в любом подмножестве рассматриваемого множества есть наименьший элемент относительно рассматриваемого отношения порядка{4}. Если множество линейно упорядочено, и, кроме того, в любом его подмножестве можно выделить наименьший элемент, то оно называется вполне упорядоченным.

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

. Пустое множество .

. Множество .

. Множество .

Заметим, что эти множества упорядочены относительно отношения принадлежности (). Нетрудно догадаться, как для такого отношения порядка выглядит вполне упорядоченное множество из трех элементов:

. .

…

. — -е множество получается объединением предыдущих множеств.

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

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

{4} Элемент множества называется наименьшим, если он меньше любого другого элемента . Можно также определить минимальный элемент : это такой элемент, меньше которого в множестве нет. Важно, что в случае, когда не является линейно упорядоченным, понятия наименьшего и минимального элементов различны. В частности, наименьших элементов всегда не более одного, а для минимальных это не так. На рис. 4 каждый из элементов и минимальный.