На этом шаге мы дадим определение и приведем примеры таких множеств.

Определение.

Вполне упорядоченным множеством называется множество X, на котором определено бинарное отношение <, обладающее следующими свойствами:

если х,y,z ∈ Х, а х<y и y<z, то х<z;
для х,y ∈ Х справедлива одна и только одна из трёх возможностей: либо х<y, либо y<х, либо х=y;
любое непустое подмножество Х содержит наименьший элемент, т.е. если А - любое непустое подмножество Х, то в множестве А существует некоторый элемент х, такой, что для любого y ∈ А либо х=y, либо x<y.

Определение.

Будем говорить, что бинарное отношение < вполне упорядочивает множество Х, если X является вполне упорядоченным множеством.

Теорема.

Для любого частично упорядоченного множества X перечисленные ниже условия эквивалентны.

Условие минимальности. Всякое непустое подмножество множества X обладает хотя бы одним минимальным элементом.
Условие обрыва убывающих цепей. Всякая строго убывающая последовательность a₁ > a₂... >a_{n > ...} элементов из X (называемая цепочкой) не может быть бесконечной.
Условие индуктивности. Пусть для всякого x ∈ X задано некоторое высказывание S(x). Все высказывания S(x), x ∈ X, справедливы, если будут выполнены два требования: (а) если x₀ - минимальный элемент в X, то высказывание S(x₀) справедливо; (б) если x не минимальный элемент в X и для всякого у<х (у ∈ X) высказывание S(у) справедливо, то справедливо и S(x).

Доказательство.

(1) Пусть множество X удовлетворяет условию (1); покажем, что тогда выполнено (3). Предположим, что это не так.

Пусть А ⇔ {х¦х ∈ Х, S(x) ложно}. Если S(x) не справедливо для всех х в Х, то А - непустое подмножество Х. Т.к. X вполне упорядочено, то известно, что А содержит наименьший элемент а₀. По определению, это наименьший элемент Х, для которого S(x) не справедливо. Таким образом, S(y) справедливо для всех у (если они есть), удовлетворяющих условию у<а₀. Если а₀ - наименьший элемент в Х, то S(a₀) справедливо, что следует из первого положения. В противном случае из справедливости S(y) для всех у<а₀ и второго положения вытекает, что S(а₀) справедливо. Но это противоречит предположению, состоящему в том, что а₀ принадлежит А и S(а₀) ложно. Единственный способ устранить это противоречие - считать А пустым множеством, т.е. в Х нет элементов, для которых высказывание S(x) ложно.

(2) Пусть выполнено (3), покажем выполнение (2). Условие индуктивности применим к высказываниям S(x) (x ∈ Х): "всякая строго убывающая цепочка элементов из S, начинающая с элемента x, конечна". Высказывание S(x) справедливо для всякого минимального элемента x₀ ∈ Х, т.к. любая строго убывающая цепочка указанного вида состоит из одного элемента x₀. Пусть x - не минимальный элемент в Х, а для всех у<x (у ∈ Х) высказывания S(у) справедливы. Тогда для произвольной строго убывающей цепочки x>a₂>a₃>..., ввиду справедливости S(a₂), получаем, что цепочка a₂>a₃>... конечна, а потому конечна и вся цепочка, т.е. высказывание S(x) справедливо. Согласно (3), высказывания S(x) справедливы для всех x ∈ Х.

(3) Пусть выполнено (2), покажем, что выполнено и (1). Предположим противное, т.е. некоторое непустое подмножество A множества Х не имеет минимальных элементов. Тогда для произвольного a₁ ∈ A существует a₂ ∈ A, такой, что a₁ > a₂, и т.к. a₂ - не минимальный, то существует a₃ ∈ A, такой что a₁ > a₂ > a₃ и т.д. Этот процесс бесконечен, т.к. ни один элемент из A по предположению не минимальный. Но тогда построена бесконечная цепочка a₁ > a₂ > a₃..., что противоречит (2).

Теорема доказана.

Определение (по [1, с.62]).

Фундированными множествами называются множества, удовлетворяющие свойствам (1)-(3) предыдущей теоремы.

Примеры фундированных множеств (по [1, с.62-64]).

Множество натуральных чисел N.
Множество N×N пар натуральных чисел (меньше та пара, у которой второй член меньше; в случае равенства сравниваем первые).
Множество N×N×...×N (повторено k раз).
Множество всех слов русского алфавита (точнее, всех конечных последовательностей русских букв, независимо от смысла) с лексикографическим порядком.

Формально лексикографический порядок можно определить так: если слово x является началом слова y, то x ≤ y (например, кант ≤ кантор). Если ни одно из слов не является началом другого, посмотрим на первую по порядку букву, в которой слова отличаются: то слово, где эта буква меньше в алфавитном порядке и будет меньше.

Определение (по [1, с.64]).: Вполне упорядоченными множествами называются фундированные линейно упорядоченные множества.

⁽¹⁾Н.К.Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. 2-е изд., исправленное. М.:МЦНМО, 2002. - 128 с.

На следующем шаге мы рассмотрим рекурсивные определения функций.

Предыдущий шаг Содержание Следующий шаг