тельно вытекает (65:G). Легко привести соответствующие примеры, но это не входит в наши планы. Достаточно сказать, что (65:G) окажется подлинным обобщением условия существования абсолютного максимума (см. предыдущую схему) на случай относительного максимума (см. ниже). Теперь мы имеем следующее;

(65:Н) V есть решение тогда и только тогда, когда (65:G) выполнено (для D и оР!), а V - множество всех (относительных) максимумов.

Доказательство. Необходимость. Пусть V - решение.

Если у $ V, то существует такое х £ V, что xtfу; следовательно, у не есть максимум. Поэтому все максимумы принадлежат V.

Если у £ V, то аргументы, приведенные в ходе доказательства (65:Е) из п. 65.4.1, могут быть повторены буквально, и они доказывают, что у есть максимум.

Таким образом, V есть в точности множество всех максимумов.

Если у не есть максимум, т. е. не принадлежит V, то существует некоторое х £ V, т. е. максимум, для которого xofy; поэтому (65:G) выполняется (для D и оР).

Достаточность. Предположим, что (65:G) выполняется, и пусть V - множество всех максимумов.

Для х, у £ V невозможно хоРу, так как у - максимум. Если у (J V, т. е. не максимум, то по (65:G) существует такой х, являющийся максимумом, т. е. принадлежащий V, что xtfy. Значит, V есть решение по (65:1).

Читатель может проверить, что этот результат (65:Н) превращается в (65:Е) из п. 65.4.1, если упорядочение полное.

Утверждение (65:Н) показывает, что не существует решения V, если D и оР не удовлетворяют условиям (65:G); решение существует и единственно, если это условие выполнено.

65.5.2. Если D конечно, то, очевидно, имеет место последнее. Приведем полное доказательство.

(65:1) Если D конечно, то условие (65:G) выполняется.

Доказательство. Предположим противное, т. е. что D не удовлетворяет (65:G). Назовем элемент у исключительным, если он не максимум и ХоРу не имеет места ни для какого максимума х. Невыполнение (65:G) означает, что исключительные у существуют.

Рассмотрим некоторый исключительный у. Так как он не максимум, существует такой х, что ХоРу. Так как у исключительный, х не максимум. Если существует такой максимум и, что иоРх, то по (65:В:Ь) мы получаем шТу, что противоречит исключительности у} Следовательно, такого и не существует, т. е. элемент х тоже исключительный. Таким образом, мы получаем:

(65:J) Если элемент у исключительный, то существует такой исклю-

чительный X, ЧТО ХоРу.

Выберем теперь исключительные х и х2 так, чтобы было х2оРх, затем исключительный х3 так, чтобы было х3оРх2, и т. д. По (65:В:Ь) для m> п будет хтоРхп\ следовательно, по (65:В:а) хт Ф хп, т. е. все Xi, х2, х3, ... различны, а значит, множество D бесконечно.

(Сравним последнюю часть этого вывода с доказательством (65:F) из предыдущего пункта. Заметим, что можно заменить там (65:А:а) на более слабое (65:В:а).)

Эти результаты показывают, что существование решения соответствует теперь не существованию максимума, а выполнению условия (65:G). Весьма важно обратить внимание на заключительную часть п. 65.4.2. Она согласуется с нашим прежним наблюдением, что в данном случае частичного упорядочения (65:G) есть просто замена существования максимума.

Единственность решения является еще более примечательной. В свете последней части предыдущей схемы представлялось естественным, что эта единственность связана с единственностью максимума. Но теперь мы увидим, что решение единственно, в то время как относительный максимум, как уже было сказано *), может единственным и не быть.

65.6. Ацикличность и строгая ацикличность

65.6.1. Четвертая схема. Пусть tf является ацикличным отношением. Мы знаем, что этот случай включает и два предыдущих, т. е. является более общим, чем они оба.

В этих двух случаях мы установили необходимые и достаточные условия существования решения, а также нашли, когда из них вытекает его единственность. (См. (65;Е) и (65:Н).) Далее, мы видели, что, когда D конечно, эти условия, очевидно, выполнены (см. (65:F) и (65:1)).

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

Снова удобно ввести понятия максимумов 2), и не только для самого D, но и для его подмножеств. Итак, мы назовем х максимумом в Е ( D), если х £ Е та. если не существует такого г/, что ytfx. Обозначим множество всех максимумов в Е через Еш ( Е).

Наши рассуждения покажут, что решающую роль играет то, обладают ли D и tf следующим свойством:

(65:К) Ш\Е Ф 0 (для Е с= D) следует Ем ф 0,

т. е. любое непустое подмножество D имеет максимумы.

Замечание. Даже если tf является линейным упорядочением, это свойство (65:К) имеет большое значение в теории множеств. Читатели, знакомые с этой теорией* заметят, что это свойство совпадает с понятием линейной упорядоченности. (В этом случае tf должно интерпретироваться как отношение «предшествования», а не как отношение «больше».) См. следующую литературу: А. Френкель, ук. соч, стр. 195 и след., а также 299 и след., Ф. Хаусдорф, ук. соч., стр. 55 и след. (литература указана в сноске 1 на стр. 87); см. также Э. Цермело в сноске на стр. 289. Замечательно, что то же самое свойство играет роль и в связи с нашим понятием решения для произвольных отношений. Основная доля исследований, которые будут проведены в этой главе, касается именно этого свойства и его следствия.

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

На первый взгляд (65:К) не представляется связанным каким-либо образом с ацикличностью; однако, в действительности здесь существует,

I1) (65:Н) показывает, что решение V не связано с каким-либо конкретным (не единственным) максимумом, а с (единственным) множеством всех максимумов.

2) Так как мы использовали термин «абсолютный» во второй схеме, а термин «относительный»- в третьей, мы должны были бы теперь найти термин, еще более ослабляющий это понятие. Однако нам не представляется необходимым вводить по анному поводу подобные терминологические новшества.

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

65.6.2. С этой целью мы отбросим все ограничения, касающиеся D и tf, и в том числе ацикличность.

Удобно ввести свойство, которое является модификацией (Ат) из (65:D) в п. 65.3.3 и которое окажется внутренне связанным с ним.

(Аоо) Не существует такой последовательности принадлежащих D г)

элементов х0, Xi, х2, . . ., что хх0, x2tfxi, x3tfx2, . . .

По причине, которая скоро станет ясной, назовем отношение of строго ацикличным, если оно удовлетворяет условию (Аоо).

Выясним связь строгой ацикличности, т. е. (4оо), с (65:К) и с ацикличностью, доказав для этого пять следующих лемм. Наиболее существенными результатами из них являются (65:0) и (65:Р); результаты (65:L) и (65:N) - предварительные для (65:0).

(65:L) Из строгой ацикличности следует ацикличность.

Доказательство. Предположим, что <ЗР не ациклично. Тогда существуют такие х0, хи . . ., хт с хт = х0 в D, что хх0г x2tfxu . . ., xm<2JPxm i. Дополним эту последовательность до бесконечной

Xq, Xi, Х2, . . ., ПОЛОЖИВ,

Xq = Хт = Х2пг = . . . ,

Х\ = Xm+i = X2m+i = . . . ,

Хщ-i - X2m-i - Хзт-{ - • • •

Тогда ясно, что хх0, x2oPxi, x3tfx2, ... и т. д., что противоречит строгой ацикличности.

(65:М) Ацикличность, без строгой ацикличности влечет следующее: (BfJ) В D существует последовательность х0, xt, х2, х3, ... 2), обладающая следующим свойством:

Для того чтобы xVQfxq, достаточно, чтобы р = q + 1, и необходимо, чтобы р > qs).

Из (В*о) следует, что элементы х0, х1ч х2, . . . попарно различны и, следовательно, множество D должно быть в данном случае бесконечным. Доказательство. Так как of не строго ациклично, в D существуют такие Xq, хх, х2, . . ., что хх0, х2Рхх, х3х2, . . . Значит, для xvoPxq достаточно, чтобы р = q + 1.

Теперь предположим, что xp<zFxq. Мы хотим доказать, что при этом должно быть р > q. Предположим противное, именно, что pq. Тогда

Xp + idfXp, Xv + 2ofxv + i, . . ., XqofXq-i 4), XpoPxq, ЧТО ПрОТИВОреЧИТ (4m)

для т = q - р + 1: действительно, достаточно подставить вместо Xq, хи . . ., xm-i и хт = х0 элементы нашей последовательности хрг xp+i, . . ., xq и Хр. Таким образом, мы получили противоречие с условием ацикличности of.

х) Последовательность х0, х4, х2, ... должна быть бесконечной в том смысле, что индексы должны составлять бесконечную последовательность, но сами элементы xt не обязательно должны быть все различными.

2) Сравнить с предыдущей сноской и с последней частью этой леммы.

3) В связи с этим результатом см. также п. 65.8.3.

4) Здесь имеется ровно q - р соотношений; следовательно, их не будет вовсе, если р = q.