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


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


149

Доказательство. Согласно сказанному выше мы должны проверить только, обладает ли W = У желательными свойствами.

V = Wm. Пусть S - минимальный элемент в этом ТУ. Тогда S э Т для некоторого Г из F. Т принадлежит W и поэтому минимальность S исключает S zd Т. Следовательно, S = Т, т. е. S принадлежит У.

Таким образом, остается рассмотреть только обратное свойство, т. е. будет ли каждое S £ У действительно минимальным в W. Любое ££У, очевидно, принадлежит W. Поэтому минимальность означает невозможность S zd Т, где Т £ ТУ, т. е. невозможность S zd Т 3 Г, где Г£У. Это влечет невозможность S =э Г, где Г£У, и, наоборот, следует из нее (при Т = Г). Итак, мы имеем следующее условие.

(51:2) Неверно, что S zd Т для 5, Г £ У.

ТУ удовлетворяет (49:W*). Мы должны рассмотреть (49:W*:a), (49:W*:b), (49:W*:c) порознь. Сделаем это в другом порядке.

(49:W*:b). Очевидно, что W = V содержит все надмножества своих элементов, поэтому данное условие выполняется автоматически.

(49:W*:c). Пусть (49:W*:a) доказано. (См. ниже.) Тогда (49:W*:c) может быть установлено так. Если S есть / или п - 1-элементное множество, то -S не принадлежит W. Следовательно, ни 0, ни одноэлементные множества не принадлежат W, т. е. никакое подмножество их не находится в У. Итак, мы имеем следующее условие:

(51:3) Ни 0, ни какое-либо одноэлементное множество не принад-

лежат У.

(49:W*:a). Рассмотрим доказательство в два этапа.

S и -S не могут одновременно принадлежать W. Поэтому если S и Т принадлежат У, то мы не можем иметь S S, Т -S. Существование такого S влечет S (] Т Ф 0 и, наоборот, следует отсюда (при S = S). Итак, мы имеем условие: (51:4) Неверно, что S (] Т = 0 для S, Т 6 У.

Одно из множеств S и -S должно принадлежать W. Предположим, что ни S, ни - S не принадлежит ТУ. Это означает, что ни для какого Т £ У не может быть Т S или Т -S. Последнее означает, что S (] Т = 0. Тем самым ни для какого Г £ У не может быть Т - S, или S zd Т, или S П Т = 0. Иначе говоря, S не принадлежит У, и ни для какого Т £ У не выполняется отрицание SM2T 1)-

Таким образом, S не принадлежит У, но S3i2T для всех Т £ У„

Мы должны теперь выразить то, что это невозможно, т. е.

(51:5) Если SM2T для всех Т £ У, то £ принадлежит У.

Значит, (51:2)-(51:5) являются нужными критериями. Сформулируем (51:2) и (51:4) вместе следующим образом. SM2T для всех S, Т £ У, т. е.

(51:6) SM2T для всех Г £ У, если £ принадлежит У.

(51:5) и (51:6) вместе выражают 2-насыщенность У. Таким образом, это условие и (51:3) образуют критерий, и это в точности то, что мы хотели доказать.

(51 :Е) представляет некоторый интерес, потому что это - полный аналог (51 :В). Таким образом, эти характеризации W и Wm отличаются



только заменой

неверно, что S П Т=0п

SMzT: ни S П Т - 0, ни S zdT.

Так как, однако, мы заменяем симметричное отношение М\ на несимметричное Мчч утверждение (51 :Е) не может быть использовано тем же способом, каким мы использовали (51 :В) или, вернее, основное (51 :А).

51.4. Измененный подход. Перечисление посредством Wm

51.4.1. Перейдем теперь ко второй процедуре. Она состоит в анализе следующего вопроса. Если дана система У, то что означает выполнение включения У ТУт для ТУ, удовлетворяющего (49:W*)?

У <== Wm означает следующее. Каждое S £ У есть минимальный элемент ТУ. Это значит, что такое S должно принадлежать ТУ, но его собственные подмножества не должны принадлежать ТУ. Так как ТУ удовлетворяет (49:W*:b), т. е. содержит надмножества всех своих элементов, Это достаточно установить только для максимального собственного подмножества S, т. е. для S - (&), где i £ S. Так как ТУ удовлетворяет (49:W*:а), вместо того, чтобы говорить, что S - (i) не принадлежит ТУ, мы можем сказать, что - (S - (i)) = (-S)[](i) принадлежит ТУ. Итак, мы видим следующее.

(51 :F) У ТУШ (ТУ удовлетворяют (49:W*)) означает в точности

следующее. Каждое S £ У принадлежит ТУ, и для каждого i из этого S объединение (-S) [) (i) принадлежит ТУ.

Мы теперь докажем утверждение:

(51 :G) У есть подмножество ТУ™ для ТУ, удовлетворяющего (49:W*), тогда и только тогда, когда оно обладает следующими свойствами:

(51:G:a) Любые два S, Т из У пересекаются.

(51:G:b) Ни для каких двух S и Т из У не будет S zd Т.

(51:G:c) Для S и Г, принадлежащих У из S [} Т = I следует, что S П Т есть одноэлементное множество

(51:G:d) Ни 0, ни одноэлементное множество, ни 7 не должны принадлежать У.

Доказательство. Пусть Vx - семейство всех множеств (-S) U (i), где S ё У и i £ S. Тогда У g= Wm означает по (51:F), что У U Vi ТУ. Согласно (51 :D) это возможно для некоторого ТУ, удовлетворяющего (49:W*), если Уи1 удовлетворяют (51:D:a) и (51:D:b).

Сформулируем поэтому (51:D:a) и (51:D:b) для FUi-

(51:D:a). Если оба множества S и Т принадлежат У, то это совпадает с (51:G:a). Пусть оба множества S и Т принадлежат У4. Это значит, что S = (-5") U (0 и Т = {-Tf) U (i), где S", Г £ У, i£S\]£T.

То, что £ и Г не пересекаются, означает, что -S и -7" также не пересекаются, т. е. S "(J Г = 7; (г) и (;) не пересекаются, т. е. i Ф /, (-5") и (/) не пересекаются, т. е. j £ *S", и, наконец, (-Т7), (j) не пересекаются, т. е. i £ Г.

Суммируя все сказанное, мы получаем S [} Т* = 7: a i и / - два различных элемента, оба из S и 71, т. е. из 5 П У-



Теперь мы должны сформулировать невозможность этого. Именно, если S [} Т = 7, то S fl Т не может обладать двумя различными элементами. Так как S П Т не может быть пустым множеством, по (51:G:a), это означает, что оно должно быть одноэлементным множеством.

Таким образом, получилось в точности (51:G:c) (с S и Т вместо S и Т).

Пусть из множеств S и Т одно принадлежит У, а другое У4. Мы можем предположить, в силу симметрии, что S принадлежит У, а Т принадлежит У4. Итак, Т = (-Г)и(У), где Г £ У, a j £ Г. То, что S и (-Г)иО) не пересекаются, означает, что множества S и -7" не пересекаются, т. е. S s Г; 5 и (/) не пересекаются, т. е. / не принадлежит S.

Суммируя сказанное, мы получим S Г, а / принадлежит Т и не принадлежит S.

Теперь мы должны сформулировать невозможность этого, т. е. отрицание S с Г. Но это есть просто (51:G:b).

(51:D:b). Ни 0, ни одноэлементные множества не должны принадлежать ни У, ни Vi. Последнее означает, что мы не можем иметь множества (-*9) (J (г), где S £ У и i £ S. Такое множество (-S) (J (i) может быть только одноэлементным, а это означало бы, что -S = 0, т. е. S = I.

Резюмируя, мы получаем: ни 0, ни одноэлементные множества, ни I не должны принадлежать У. Это совпадает с (51:G:d).

Таким образом, мы, как и хотели, получили условия (51:G:a) - (51:G:d).

(51 :G) решает проблему перечисления всех Wm совершенно так же, как (51 :D) решало соответствующую проблему для W. Начиная с произвольного У, которое удовлетворяет (51:G:a)-(51:G:b) х), мы будем увеличивать его последовательно до тех пор, пока это можно делать без нарушения (51:G:a)-(51:G:d). Когда этот процесс нельзя будет продолжать дальше, мы получим У, которое максимально среди всех подмножеств вида Wm для соответствующего W со свойствами (49:W*), т. е. мы имеем такое Wm. Производя этот процесс построения всеми возможными способами, мы получим все искомые Wm.

51.4.2. Наши последние замечания показывают, что практическое перечисление всех простых игр может быть основано на (51 :G), и - мы хотим фактически проделать это в п. 52. Но сначала, однако, лучше провести некоторые другие рассмотрения.

Мы намерены теперь проанализировать несколько более подробно утверждение о том, что (51 :G) есть условие типа насыщения.

Заметим сначала, что так как (51:G:b) относится к двум произвольным множествам S и Т из У, мы можем поменять их местами, т. е. мы можем заменить (51:G:b) на

(51:G:b*) Ни для каких двух S и Г из У не будет выполнено ни S => Т ни S cz Т.

Обозначим утверждение, что S и Т удовлетворяют (51:G:a), (51:G:b*), (51:G:c),- т. е. что ни S f] Т = 0, ни S =э Г, ни S cz Т, ни S U Т - I за исключением случая, когда S П Т - одноэлементное множество,- через SM3T.

Тогда (51 :G) устанавливает просто, что У является -удовлетворяемым, а также со свойством (51:G:d). Пусть теперь областью D будет семейство / тех подмножеств 7, для которых выполнено (51:G:d), т. е. не являю-

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