Фундированные и вполне упорядоченные множества

Фундированные множества

Принцип математической индукции в одной из возможных форм звучит так:

(Заметим, что по условию доказательство $$A(0)$$ возможно без всяких предположений, поскольку меньших чисел нет.)

Для каких частично упорядоченных множеств верен аналогичный принцип? Ответ дается следующей простой теоремой:

Теорема 15. Следующие три свойства частично упорядоченного множества $$X$$ равносильны:

(a) любое непустое подмножество $$X$$ имеет минимальный элемент;

(б) не существует бесконечной строго убывающей последовательности $$x_0\hm>x_1\hm>x_2\hm>\dots$$ элементов множества $$X$$ ;

(в) для множества $$X$$ верен принцип индукции в следующей форме: если (при каждом $$x\hm\in X$$ ) из истинности $$A(y)$$ для всех $$y\hm<x$$ следует истинность $$A(x)$$, то свойство $$A(x)$$ верно при всех $$x$$. Формально это записывают так:$$\forall x\, (\forall y \, ((y<x)\Rightarrow A(y))\Rightarrow A(x)) \Rightarrow \forall x\, A(x).$$

Доказательство. Сначала докажем эквивалентность первых двух свойств. Если $$x_0\hm>x_1\hm>x_2>\dots$$ - бесконечная убывающая последовательность, то, очевидно, множество ее значений не имеет минимального элемента (для каждого элемента следующий еще меньше). Поэтому из (а) следует (б). Напротив, если $$B$$ - непустое множество, не имеющее минимального элемента, то бесконечную убывающую последовательность можно построить так. Возьмем произвольный элемент $$b_0\hm\in B$$. По предположению он не является минимальным, так что можно найти $$b_1\hm\in B$$, для которого $$b_0\hm>b_1$$. По тем же причинам можно найти $$b_2\hm\in B$$, для которого $$b_1\hm>b_2$$ и т.д. Получается бесконечная убывающая последовательность.

Теперь выведем принцип индукции из существования минимального элемента в любом подмножестве. Пусть $$A(x)$$ - произвольное свойство элементов множества $$X$$, верное не для всех элементов $$x$$. Рассмотрим непустое множество $$B$$ тех элементов, для которых свойство $$A$$ неверно. Пусть $$x$$ - минимальный элемент множества $$B$$. По условию меньших элементов в множестве $$B$$ нет, поэтому для всех $$y\hm<x$$ свойство $$A(y)$$ выполнено. Но тогда по предположению должно быть выполнено и $$A(x)$$ - противоречие.

Осталось доказать существование минимального элемента в любом непустом подмножестве, исходя из принципа индукции. Пусть $$B$$ - подмножество без минимальных элементов. Докажем по индукции, что $$B$$ пусто; другими словами, в качестве $$A(x)$$ возьмем свойство $$x\hm\notin B$$. В самом деле, если $$A(y)$$ верно для всех $$y\hm<x$$, то никакой элемент, меньший $$x$$, не лежит в $$B$$. Если бы $$x$$ лежал в $$B$$, то он был бы там минимальным, а таких нет.

Множества, обладающие свойствами (а)-(в), называются фундированными. Какие есть примеры фундированных множеств? Прежде всего, наш исходный пример - множество натуральных чисел.

Другой пример - множество $$\bbN\hm\times\bbN$$ пар натуральных чисел (меньше та пара, у которой второй член меньше; в случае равенства сравниваем первые). В самом деле, проверим условие (б). Нам будет удобно сформулировать его так: всякая последовательность $$u_0\hm\ge u_1\hm\ge u_2 \ge\ldots$$ элементов множества рано или поздно стабилизируется (все члены, начиная с некоторого, равны); очевидно, что это эквивалентная формулировка.

Пусть дана произвольная последовательность пар$$\langle x_0, y_0 \rangle \ge \langle x_1, y_1 \rangle \ge \langle x_2, y_2 \rangle \ge \dots$$ По определению порядка (сначала сравниваются вторые члены) $$y_0\hm\ge y_1\hm\ge y_2\ge\ldots$$ и потому последовательность натуральных чисел $$y_i$$ с какого - то места не меняется. После этого уже $$x_i$$ должны убывать - и тоже стабилизируются. Что и требовалось.

То же самое рассуждение пригодно и в более общей ситуации.

Теорема 16. Пусть $$A$$ и $$B$$ - два фундированных частично упорядоченных множества. Тогда их произведение $$A\hm\times B$$, в котором$$\langle a_1, b_1 \rangle \le \langle a_2, b_2 \rangle \Leftrightarrow [(b_1 \hm< b_2) \text{ или } (b_1=b_2 \text{ и } a_1\le a_2)],$$ является фундированным.

Доказательство. В последовательности $$\langle a_0,b_0 \rangle \hm\ge \langle a_1,b_1 \rangle \ge\ldots$$ стабилизируются сначала вторые, а затем и первые члены.

Отсюда вытекает аналогичное утверждение для $$\mathbb{N}\hm\times\mathbb{N}\times\mathbb{N}$$, для $$\mathbb{N}^k$$ или вообще для произведения конечного числа фундированных множеств.

Еще проще доказать, что сумма $$A+B$$ двух фундированных множеств $$A$$ и $$B$$ фундирована: последовательность $$x_0\le x_1\le x_2\le\dots$$ либо целиком содержится в $$B$$ (и мы ссылаемся на фундированность $$B$$ ), либо содержит элемент из $$A$$. В последнем случае все следующие элементы также принадлежат $$A$$, и мы используем фундированность $$A$$.

Часто в программировании (или в олимпиадных задачах) нам нужно доказать, что некоторый процесс не может продолжаться бесконечно долго. Например, написав цикл, мы должны убедиться, что рано или поздно из него выйдем. Это можно сделать так: ввести какой - то натуральный параметр и убедиться, что на каждом шаге цикла этот параметр уменьшается. Тогда, если сейчас этот параметр равен $$N$$, то можно гарантировать, что не позже чем через $$N$$ шагов цикл закончится.

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

Вот пример олимпиадной задачи, где по существу такое рассуждение и используется.

Задача. Бизнесмен заключил с чертом сделку: каждый день он дает черту одну монету, и в обмен получает любой набор монет по своему выбору, но все эти монеты меньшего достоинства (видов монет конечное число). Менять (или получать) деньги в другом месте бизнесмен не может. Когда монет больше не останется, бизнесмен проигрывает. Докажите, что рано или поздно черт выиграет, каков бы ни был начальный набор монет у бизнесмена.

Решение: пусть имеется $$k$$ видов монет. Искомый параметр определим так: посчитаем, сколько монет каждого вида есть у бизнесмена ( $$n_1$$ - число монет минимального достоинства, $$n_2$$ - число следующих, и так далее до $$n_k$$ ). Заметим, что в результате встречи с чертом набор $$\langle n_1,\dots,n_k\rangle$$ уменьшается (в смысле введенного нами порядка, когда мы сравниваем сначала последние члены, затем предпоследние \итд). Поскольку множество $$\bbN^k$$ фундировано, этот процесс должен оборваться.

108. Имеется конечная последовательность нулей и единиц. За один шаг разрешается сделать такое действие: найти в ней группу $$01$$ и заменить на $$100{\dots}00$$ (при этом можно написать сколько угодно нулей). Докажите, что такие шаги нельзя выполнять бесконечно много раз.

109. Рассмотрим множество всех слов русского алфавита (точнее, всех конечных последовательностей русских букв, независимо от смысла) с лексикографическим порядком. Будет ли это множество фундировано?

110. Рассмотрим множество невозрастающих последовательностей натуральных чисел, в которых все члены, начиная с некоторого, равны нулю. Введем в нем порядок так: сначала сравниваем первые члены, при равенстве первых вторые и т.д. Докажите, что это (линейно) упорядоченное множество фундировано.

111. Рассмотрим множество всех многочленов от одной переменной $$x$$, коэффициенты которых - натуральные числа. Упорядочим его так: многочлен $$P$$ больше многочлена $$Q$$, если $$P(x)\hm>Q(x)$$ для всех достаточно больших $$x$$. Покажите, что это определение задает линейный порядок и что получающееся упорядоченное множество фундировано.

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

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

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

Примеры вполне упорядоченных множеств: $$\bbN$$, $$\bbN\hm+k$$ (здесь $$k$$ обозначает конечное линейно упорядоченное множество из $$k$$ элементов), $$\bbN\hm+\bbN$$, $$\bbN\hm\times\bbN$$.

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

Пусть $$A$$ - произвольное вполне упорядоченное множество. Его наименьший элемент обозначим через $$0$$. Следующий за ним элемент обозначим через $$1$$, следующий за $$1$$ - через $$2$$ и т.д. Если множество конечно, процесс этот оборвется. Если бесконечно, посмотрим, исчерпали ли мы все элементы множества $$A$$. Если нет, возьмем минимальный элемент из оставшихся. Обозначим его $$\omega$$. Следующий за ним элемент (если он есть) обозначим $$\omega\hm+1$$, затем $$\omega\hm+2$$ и т.д Если и на этом множество не исчерпается, то возьмем наименьший элемент из оставшихся, назовем его $$\omega\hm\cdot2$$, и повторим всю процедуру. Затем будут $$\omega\hm\cdot3$$, $$\omega\hm\cdot4$$ и т.д Если и на этом множество не кончится, минимальный из оставшихся элементов назовем $$\omega^2.$$ Затем пойдут $$\omega^2\hm+1$$, $$\omega^2\hm+2$$, $$\dots$$, $$\omega^2\hm+\omega$$, $$\dots$$, $$\omega^2\hm+\omega\hm\cdot2$$, $$\dots$$, $$\omega^2\hm\cdot2$$, $$\dots$$, $$\omega^2\hm\cdot3$$, $$\dots$$, $$\omega^3$$, $$\dots$$ (мы не поясняем сейчас подробно обозначения).

Что, собственно говоря, доказывает это рассуждение? Попытаемся выделить некоторые утверждения. При этом полезно такое определение: если линейно упорядоченное множество $$A$$ разбито на две (непересекающиеся) части $$B$$ и $$C$$, причем любой элемент $$B$$ меньше любого элемента $$C$$, то $$B$$ называют начальным отрезком множества $$A$$. Другими словами, подмножество $$B$$ линейно упорядоченного множества $$A$$ является начальным отрезком, если любой элемент $$B$$ меньше любого элемента $$A\hm\setminus B$$. Еще одна переформулировка: $$B\hm\subset A$$ является начальным отрезком, если из $$a,b\hm\in A$$, $$b\hm\in B$$ и $$a\hm\le b$$ следует $$a\hm\in B$$. Заметим, что начальный отрезок может быть пустым или совпадать со всем множеством.

Отметим сразу же несколько простых свойств начальных отрезков:

Возвратимся к нашему рассуждению с последовательным выделением различных элементов из вполне упорядоченного множества. Его первую часть можно считать доказательством такого утверждения: если вполне упорядоченное множество бесконечно, то оно имеет начальный отрезок, изоморфный $$\omega$$. (Говоря о множестве натуральных чисел вместе с порядком, обычно употребляют обозначение $$\omega$$, а не $$\bbN$$.)

Но на этом наше рассуждение не оканчивается. Его следующая часть может считаться доказательством такого факта: либо $$A$$ изоморфно некоторому начальному отрезку множества $$\omega^2$$, либо оно имеет начальный отрезок, изоморфный $$\omega^2$$. (Здесь $$\omega^2$$ - вполне упорядоченное множество пар натуральных чисел: сравниваются сначала вторые компоненты пар, а при их равенстве - первые.)

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