Промышленный лизинг Промышленный лизинг  Методички 

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

Эти результаты показывают, что существование решения соответствует теперь не существованию максимума, а выполнению условия (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.



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



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