х) Заметим, что соотношения между x0l хи х2, ... характеризуются полностью (Вт), но не (В£>). Это будет важно в дальнейшем. 2) То есть опустить xq+i, . . ., х т.
Итак, обе части (В£) доказаны.
Теперь рассмотрим следствия из (В). Если элементы х0, xi4 х2, ... не являются попарно различными, то хр = xq для некоторых р 7> q. Согласно (В£) должно быть xq+icfxq, и потому xq+itfxp; ввиду (В£>) из этого следует, что q + 1 > р, т. е. q > р; однако q << р, т. е. х0, хи х2, ... попарно различны и, следовательно, D должно быть бесконечным.
(65:N) Из неацикличности вытекает следующее: Для некоторого т ( = 1, 2, . . .) мы имеем:
(Вт) Существуют в D такие х0, хи . . ., хт-± и хт = z0, что для
Xpofxq необходимо и достаточно, чтобы р - q + 1 х).
Доказательство. Так как отношение of неациклично, в D существуют такие х0, #ь . . ., хш и хт = х0, что Л0, x2tfxu . . . . . ., xmtfxm-i. Возьмем такую последовательность с наименьшим возможным т ( = 1, 2, . . .).
Ясно, что равенство р - q + 1 достаточно для того, чтобы было Xptfxq. Докажем, что оно и необходимо. Предположим для этого, что Xptfxq, но р Ф q + 1.
Далее, циклическая подстановка последовательности х0, хи < . . . . ., хт-\, хт = #o не повлияет на её свойства; поэтому мы можем сделать Хр последним элементом, т. е. перевести р в т. Итак, не ограничивая общности, мы можем считать, что р = т. Мы имеем р Ф q + 1, т. е. q ф т - 1. Мы можем также предполагать, что q Ф т, так как q = т можно заменить на q = 0. Таким образом, q т - 2. После этой подготовки мы можем заменить х0, xl7 . . ., a:m i, £т = х0 на #0, #ь • . . . . ., xq, хт = ж0 2)> не изменив свойств последовательности. Это заменяет тп на # + 1, что <ттг, а это противоречит минимальности т.
Итак, обе части (Вт) доказаны.
65.6.3. Резюмируем доказанное.
(65:0)
(65:0:а) Ацикличность равносильна отрицанию всех (В*), (В*), . . .
(65:0:Ь) Строгая ацикличность равносильна отрицанию всех (В*), (£*), ... и
(65:0:с) Из строгой ацикличности следует ацикличность для любого D, а для конечного D они равносильны.
Доказательство. (65:0:а). Условие необходимо, так как (Вт) противоречит (Ат) и, следовательно, ацикличности. Достаточность следует из (65:N).
(65:0:b) Условия необходимы, так как неацикличность противоречит строгой ацикличности по (65:L), а (В) также противоречит (-4оо), т. е. строгой ацикличности. Эти условия достаточны, так как отрицание строгой ацикличности позволяет применить (65:М) в случае ацикличности и (65:0:а) в случае неацикличности.
(65:0:с) Первая импликация была установлена в (65:L). Если D конечно, то обратная импликация, а значит, и равносильность, следует из последнего замечания в (65:М).
Установим, наконец, связь с (65:К), (65:Р) (65:К) эквивалентно строгой ацикличности.
Доказательство. Необходимость. Предположим, что отношение of не является строго ацикличным. Найдем в D такую последовательность х0, хи х2, . . ., что хх0, х2о?хи х3о?х2, . . . Тогда Е = = (х0, Xi, х2, . . .) D и Е Ф 0 и, очевидно, не имеет максимума. Это значит, что (65:К) неверно.
Достаточность. Предположим, что (65:К) не выполняется. Выберем непустое Е a D, не имеющее максимума Выберем х0 £ Е, элемент х0 не является максимумом в Е; поэтому найдется такой xL £ Е, что Xitfxo. Элемент хх не максимум в Е; поэтому найдется такой х2, что x2iPxu и. т. д. Таким образом, для последовательности х0, х, х2, ... из Е, а следовательно, и из D, мы получаем хх0, х2оРхи x3tfx2, . . . Это противоречит строгой ацикличности.
Итак, мы видим, что строгая ацикличность эквивалентна условию (65:К); мы вправе ожидать, что оно играет фундаментальную роль. Ацикличность и строгая ацикличность тесно связаны друг с другом. Особая роль конечности D проявляется в том, что для конечного D оба эти понятия эквивалентны.
65.7. Решения для ациклического отношения
65.7.1. Обратимся теперь к нашей основной цели: исследованию решений в D для of. Именно здесь станет ясно, почему мы приписывали свойству (65:К) такую фундаментальную важность: (65:К) оказывается связанным с существованием ровно одного решения.
Мы начнем с доказательства того, что существует единственное решение (в D для с), если выполняется (65:К). Для доказательства мы ограничимся конечным множеством D; в этом случае решение может быть даже получено в виде явной конструкции. Это делается с помощью конечной индукции. Конечность D в действительности не необходима, но для бесконечного D эта конструкция была бы более сложной 2).
Так как мы должны принять (65:К), это означает ввиду (65:Р), что D должно быть строго ацикличным. Так как D конечно, согласно(65:0:с), это не отличается от обычной ацикличности. Поэтому в данный момент безразлично, требуем мы ацикличности или строгой ацикличности D. Тем не менее стоит помнить, что мы пользуемся (65:К), т. е. строгой ацикличностью, и что предположение конечности, которое стирает различие, может быть отброшено.
Мы повторяем: в оставшейся части этого параграфа мы принимаем как конечность D, так и свойство (65:К), т. е. строгую ацикличность.
Перейдем теперь к индуктивному построению, о котором было сказано. Сначала оно будет сделано, а затем будут доказаны обещанные свойства.
Определим для каждого i - 1, 2, 3, . . . три множества At, Bt, Ct (все ejD) следующим образом. Возьмем А4 = D. Если для i (= 1,2,3, . . .)
г) Читателю рекомендуется сравнить это доказательство с доказательством (65:F) из п. 65.4.2.
2) Было бы необходимо использовать более тонкие теоретико-множественные понятия (см. сноску 3 на стр. 288 и замечание на стр. 594), в частности, трансфинитную индукцию или некоторую эквивалентную ей технику.
Эти вопросы будут рассмотрены в другом месте.
множество At уже известно, то Bt, Ct и Ai+i получаются следующим образом: Bt = А™, т. е. Bt есть множество тех у £ Аи для которых не существует таких х 6 Аг, что xtfy. Ct есть множество тех у £ At, для которых xtfy для некоторого х £ Bt. Наконец,
Ai+Ai-Bi-d. Теперь мы докажем следующее: (65:Q) Множества Bt и Ct не пересекаются.
Доказательство следует непосредственно из определения. (65:R) Из Агф0 следует ЛсЛг1).
Доказательство. Из А1Ф 0 следует В1 = А?Ф0. Поэтому ввиду (65:К)2) должно быть
At+i = At Bi Ci cz Ai.
(65:S) Существует такое i, что At = 0.
Доказательство. В противном случае по (65:R) должно быть D = А zd А2 13 А3 zd . . ., что противоречит конечности D.
(65:Т) Пусть i0 - наименьшее i, удовлетворяющее (65:S); тогда D = Ay zd А2 zd А3 zd . . . zd AiG i zd Aio = 0.
Доказательство. Это - переформулировка (65:R) и (65:S).
(65:U) Bi, . . ., Bio-i, Ci, . . ., Сг0 1 суть не пересекающиеся множества с объединением D.
Доказательство. По определению Ai+i мы имеем Bt \] Ct = = Аг - Ai+i. Следовательно, Bi\jCu . . ., Z?i0 i U Ci0-i попарно не пересекаются и их объединение равно
Ai-Aio = D-0=D.
Сравнение этого с (65:Q) показывает, что множества Ви Ci, ...
. . ., Bio-i, Cio i, т. е. множества Ви . . ., 2?i0 i, Сь . . ., Ci0 i попарно не пересекаются, и их объединение также равно D. 65.7.2. Положим теперь
(65:2) V0 = fi1U-.-Uio-i-
Тогда (65 :U) дает нам
(65:3) D-y0 = d{) ... !J<Vi-
Докажем теперь следующее.
(65:V) Если V есть решение (в D для tf), то V = V0.
Доказательство. Сначала покажем, что Bt V для всех i = l, . . ., ц - 1.
Предположим противное и рассмотрим то наименьшее i, для которого включение Bt V не имеет места. Пусть z - элемент этого Ви не принадлежащий V. Тогда для некоторого у £ V должно быть ytfz. z есть максимум в А, следовательно, у не принадлежит At. Рассмотрим то наи-
г) Все дело в том, что мы имеем с:, а не просто с !
2) Это единственное (но имеющее решающее значение!) использование свойства 65:К).