Московское математическое общество, Московский центр непрерывного математического образования, Малый мехмат МГУ

Серия "Библиотека «Математическое просвещение»"

И. В. Ященко Парадоксы теории множеств


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

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

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

1) a Ј a для любого a О M;

2) если a Ј b и b Ј c, то a Ј c;

3) если a Ј b и b Ј a, то a = b.

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

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

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

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

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

0°. Пустое множество Ж.

1°. Множество {Ж}.

2°. Множество {Ж, {Ж}}.

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

3°. {Ж, {Ж}, {Ж,{Ж}}}.

..............................................

n°. {Ж, {Ж}, {Ж,{Ж}}, ...,(n - 2)°, (n - 1)°} – n-е множество получается объединением предыдущих n - 1 множеств.

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

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


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

На головную страницу