Установим, наконец, связь с (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:К).

меньшее к, для которого у не принадлежит Ah. Тогда к i, а так как у g £) = Ау, должно быть кф 1. Положим j = к - 1; тогда 1 5g у <. i, у лежит в Aj, но не в AJ+i = Ak; следовательно, у принадлежит Bj [} Cj = = Aj - AJ+l.

z 6 Bt s At cz Aj. Таким образом, если у 6 Bj, то из ytfz должно следовать, что z 6 Cj. Это неверно, так как z £Bt. Следовательно, у £ Cj.

Далее, в Bj должен существовать такой х, что xtf у. Так как у £ V, должно быть х (£ V. Итак, не может быть Bj е V. А так как у < г, это противоречит предположенной минимальности г.

Итак, мы видим, что

(65:4) BtV для всех i = 1, ..., г0 - 1.

Если г/ 6 Ct, то существует такой х £Bt, что ясг/. Так как ж £ V по (65:4), г/ не может принадлежать V. Таким образом, мы имеем:

(65:5) Ci<=:- V для всех i = 1, . . ., г0 - 1.

Сравнивая (65:4) и (65:5) с (65:2) и (65:3), мы получаем, что V должно совпадать с V0, а это и требовалось доказать.

(65:W) V0 является решением (в D для tf).

Доказательство. Разобьем доказательство на две части.

Если х, у 6 Vo, то соотношение xtfy исключается. Для доказательства предположим противное: х, у £ V0 и xtfy.

Итак, х, у £ V0; пусть для определенности х £Вг и z/ £ 5;. Если i то г/ 6 -By Лу Лг-. Но х 6 2?$; поэтому из xtfy следует, что

у (z Ct. Однако этого не может быть, так как у £ Bt. Если i > у, то я £ € .В* cz Л f с: Л у. г/ максимально в А у; следовательно, хсг/ невозможно.

Итак, во всех случаях мы получаем противоречие.

Если у (£ V0, то должно быть xtfy для некоторого ж £ V0. Но г/ принадлежит -V0. Следовательно, г/ принадлежит некоторому Ct. Итак, xtfy для х £ 2?г-, а значит, х £ V0.

Это завершает доказательство.

Объединяя (65:V) и (65:W), можно утверждать следующее:

(65:Х) Существует единственное решение V0 (в D для tf), имеющее вид (65:2).

65.8. Единственность решений, ацикличность и строгая ацикличность

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

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