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


[Старт] [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]


196

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

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



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

Тем не менее, так как мы теперь располагаем некоторыми результатами о существовании с единственностью, мы продолжим изучение этого случая. Мы увидим далее, что полученные результаты уже имеют некоторое косвенное значение для теории игр (см. § 67).

В этом направлении дам следует задать вопрос: какие свойства отношения с? необходимы и достаточны для того, чтобы существовало единственное решение? Легко увидеть, однако, что едва ли этот вопрос имеет простой и удовлетворительный ответ. Действительно, в решении (в D для &) содержится очень мало информации о структуре D (вместе с tf). Ациклический случай менее удобен для того, чтобы судить об этом, так как он несколько сложен, но случай линейного или частичного упорядочения хорошо поясняет это. В этих случаях решение связано только с максимумами D и совсем не выражает свойств других элементов D.

Это возражение устранить нетрудно. Рассмотрим множество Е gJ) вместо D. Отношение & в D является также отношением в Е и, если это линейное или частичное упорядочение или (простая или строгая) ацикличность в D, то это же будет и в Е *). Поэтому из нашего результата (65:Х) следует, что в каждом Е D существует единственное решение (для с). Теперь эти решения, построенные для всех Е g= D, говорят уже много больше о структуре D. Удобно ограничиться снова случаями линейного или частичного упорядочения. Ясно, что знание максимума для любого Е =\ D дает достаточно полную информацию о структуре D (вместе с оР).

65.8.2. Итак, мы подошли к следующему вопросу: какие свойства отношения of необходимы и достаточны для того, чтобы для каждого Е s D существовало единственное решение (в Е для #*)? Мы можем показать, что ацикличность и строгая ацикличность являются существенными понятиями, хотя и не приведут к исчерпывающему решению вопроса. Две следующие леммы содержат все, что мы можем утверждать по этому поводу.

(65:Y) Для того чтобы существовало единственное решение для

любого Е <=: D (в Е для <$Р), достаточно строгой ацикличности.

Для конечного D это следует из (65:Х), и ввиду (65:0:с) строгая ацикличность может быть заменена ацикличностью.

Для бесконечного D это зависит от возможности распространения (65:Х) на бесконечный случай (см. начало п. 65.7.1).

Доказательство. Если отношение в D (просто или строго) ациклично, то это же верно и для Е (см. выше). Теперь все утверждения леммы становятся очевидными.

(65:Z) Для того чтобы для каждого Е D существовало единствен-

ное решение (в Е для tf), ацикличность необходима.

Доказательство. Если отношение D неациклично, то из (65:0:а) следует (Вт) из (65:N) для т = 1, 2, ... Возьмем соответствующие Xq, Xi, . . ., Xm-i И хт = Xq И ПОЛОЖИМ Е = (х0, х1ч х2, • • ., #m-i).

г) То есть по крайней мере то же самое; может оказаться, что частичное упорядочение на D превращается в линейное на Е или ацикличность в D - в упорядочение на Е.



Тогда Е D и (Вт) описывает tf в Е полностью. Рассмотрим решение V в Е (для tf).

Рассмотрим такое решение V: если xt £ V, то xi+i не принадлежит V, так как xi+itfxi. Если xt не принадлежит V, то существует такой элемент у в V, что ytfxu т. е. у = жг nxjtfxf. Это означает, что/ = i + 1 -1), т. е. у = #г+1 и, следовательно, £ V. Итак, мы видим:

(65:6) xt принадлежит V тогда и только тогда, когда xi+l не при-

надлежит V. Повторное применение (65:6) дает следующее:

(65:7) Если число к четное, то х0 принадлежит V тогда и только

тогда, когда хк принадлежит V. Если к нечетное, то х0 принадлежит V тогда и только тогда, когда xh не принадлежит V.

Так как х0 = хт, (65:7) при нечетном т содержит противоречие. Следовательно, если т нечетное, то решения в Е (для tf) не существует. Если т четно, то из (65:7) следует, что V есть либо множество всех хк с четными к, либо множество всех xk с нечетными к. Легко проверить, что оба эти множества действительно являются решениями в Е (для tf).

Итак, мы имеем:

(65:8) Число решений в Е = (х0, ж1? . . ., #m-i) Для tf (с х0, хи . . .

. . ., жт ! из (Вт)) есть либо 2, либо 0, в зависимости от того, будет т четным или нечетным.

Следовательно, для такого Е ( <= D) единственного решения нет ни в одном из случаев.

Объединяя (65:Y) и (65:Z), мы видим, что существование единственного решения (в Е для tf) для всех Е <=: D в случае конечных множеств полностью описывается: для этих D оно эквивалентно ацикличности или строгой ацикличности, что в данном случае одно и то же. Для бесконечных D мы можем сказать только, что ацикличность есть необходимое условие, а строгая ацикличность - достаточное.

65.8.3. Пробел, который здесь образовался, может быть заполнен за счет изучения ациклических, но не строго ациклических (бесконечных) множеств D и их подмножеств Е. Сравнивая (65:0:а) и (65:0:Ь), мы видим, что такие D удовлетворяют условию (В%>). Образуем соответствующее множество х0, хи х2. ... и положим D* = (х0, х х2, . . .)• Оно также ациклично, но не строго ациклично; поэтому мы можем изучать его вместо D.

Таким образом, наш вопрос превратился в следующий:

(65:9) Предположим, что D* = (х0, х х2, . . .) удовлетворяет

условию (В%о). Будет ли тогда любое Е <=: D* иметь единственное решение (в Е для tf)l

Ответ на (65:9) не может быть дан немедленно, так как условие (Во) описывает отношение xtfy в J5* (т. е. xptfxq) лишь не полностью. На соответствующий вопрос для (Вт) (т = 1, 2, . . .) в доказательстве (65:Z) был получен отрицательный ответ, но (Вт) описывает отношение xtfy на этом множестве (т. е. xptfxq) полностью. Итак, ответ на (65:9) требует полного исследования всех возможных форм отношения xptfxq, которое удовлетворяет (Бу. Эта задача оказывается достаточно трудной2).

х) Если i = т, заменим его на i - 0.

2) Она лежит на границе комбинаторики и теории множеств и представляется заслуживающей внимания.

[Старт] [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]