назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [ 195 ] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]


195

х) Заметим, что соотношения между 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:К).

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [ 195 ] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]