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


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


92

большего элемента множества D. Значит, если D не имеет наибольшего элемента (например, если D есть множество всех вещественных чисел), то такого множества А не существует; множество А единственно, если D имеет наибольший элемент (например, если оно конечно).

Пример третий. Пусть D - плоскость и хМу выражает тот факт, что точки х и у имеют одинаковую высоту (ординату). Тогда -удовлетворяе-мость множества А означает, что все точки множества А имеют одну и ту же высоту, т. е. лежат на одной прямой, параллельной оси абсцисс, .-насыщенность означает, что А является в точности прямой, параллельной оси абсцисс.

Пример четвертый. Пусть D - множество всех дележей, а хМу является отрицанием доминирования х е- у. Тогда сравнение (30:В:а) и (30:D) с (30:5:а) и (30:5:Ь) из п. 30.1.1 или, что то же самое, сравнение (30:С:Ь) с (30:5:с) дает: -насыщенность множества А означает, что А является решением.

30.3.4. Одного взгляда на условие (30:В:а) достаточно, чтобы сказать, что удовлетворяемость для отношения хМу является удовлетворяе-мостью и для отношения у&х, а следовательно, также для их конъюнкции xMsy.

Другими словами, .-удовлетворяемость совпадает с .-удовлетво-ряемостью.

Таким образом, удовлетворяемость является понятием, которое достаточно изучать только для симметричных отношений.

Это обусловливается симметричной по отношению к х и у формой определяющего условия (30:В:а). Равносильное условие (30:С:а) не выявляет этой симметрии, но, конечно, это не делает доказательство недействительным.

Далее, определяющее условие (30:С:Ь) для .-насыщенности аналогично по своей структуре условию (30:С:а). Оно в равной степени асимметрично. Однако, в то время как (30:С:а) обладает равносильной симметричной формой (30:В:а), это не имеет места для (30:С:Ь). Соответствующей равносильной формой для (30:С:Ь) является, как мы знаем, объединение (30:В:а) и (30:D), a (30:D) вовсе не симметрично. Иными словами, (30: D) существенно изменится, если отношение хМу заменить на уМх. Итак, мы получаем следующее.

(30: Е) В то время как .-удовлетворяемость не нарушается при

замене М на Ms, ничего подобного не будет для -насыщенности.

Условие (30:В:а) (соответствующее ?-удовлетворяемости) является одним и тем же для М и для Ms. Условие (30: D) для Ms следует из того же условия для J?, так как Ms влечет М- Итак:

(30: F) .-насыщенность следует из -насыщенности.

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

Таким образом, изучение насыщенности не может ограничиваться симметричными отношениями.

J) Например, первые два примера из п. 30.3.3 находятся между собой в таком отношении, kslk*MS и М (см. сноску 2 на стр. 286); понятия удовлетворяемости для них совпадают, но понятия насыщенности различны.



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

Докажем теперь следующее:

(30: G) Пусть - симметричное отношение. Тогда -насыщенность

множества А равносильна тому, что А является максимальным -удовлетворяющим; т. е. она равносильна тому, что множество А является -удовлетворяющим, а никакое его собственное надмножество .-удовлетворяющим не будет.

Доказательство, -насыщенность означает ?-удовлетворяе-мость (т. е. условие (30:В:а) вместе с условием (30:D)). Итак, остается доказать, что если множество А -удовлетворяющее, то (30: D) равносильно тому, что все собственные надмножества множества А не являются -удовлетворяющими.

Достаточность условия (30: D). Если множество В id А является -удовлетворяющим, то для любого элемента у из В, но не из А, не выполняется условие (30: D) 2).

Необходимость условия (30: D). Рассмотрим такой элемент у, для которого нарушается (30: D). Тогда

Это множество В является -удовлетворяющим, т. е. для х , у £ В всегда верно соотношение хМу. В самом деле, если х\ у £А, то это следует из -удовлетворяемости множества А. Если х = у, у = г/, то мы просто полагаем у Му- Если же один из элементов х, у принадлежит А, а другой равен у, то на основании симметричности отношения М можно считать, что х £ А и у = у. Тогда наше утверждение совпадает с отрицанием условия (30: D).

Если отношение М не симметричное, то мы можем утверждать следующее.

(30:Н) Из -насыщенности множества А следует, что оно является

максимальным -удовлетворяющим множеством.

Доказательство. Максимальность среди удовлетворяющих множеств есть то же самое, что и максимальность среди -удовлетворяющих множеств (см. (30: Е)). Так как отношение Ms симметричное, это совпадает с -насыщенностью на основании (30: G). Последнее же является следствием -насыщенности на основании (30: F).

Значение этого результата, относящегося к симметричному отношению М, состоит в следующем. Отправляясь от произвольного -удовлетворяющего множества, будем увеличивать его, насколько это возможно, т. е. пока любое дальнейшее увеличение не вызовет потерю свойства -удовлетворяемое™. Таким образом, наконец получается максимальное -удовлетворяющее множество, т. е., на основании (30:G)8), -насыщен-

!) Очевидно, это имеет место для нашего основного примера из п. 30.3.3, в котором хМу является отрицанием доминирования х £- у, поскольку х х не верно никогда.

2) Отметим, что ни одно из дополнительных ограничений, наложенных на отношение М, до сих пор еще не использовалось.

3) Этот процесс исчерпания элементарен, т. е. он заканчивается после конечного числа шагов, если множество D конечно.

Однако, поскольку множество всех дележей обычно бесконечно, случай бесконечного D очень важен. Если множество D бесконечно, то эвристически все же вполне



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

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

30.3.6. Было бы крайне удобно, если бы существование решений в нашей теории могло быть установлено такими методами. Однако бросается в глаза соображение, опровергающее это: отношение хМу, которое мы должны использовать,-отрицание доминирования х е- у (см. п. 30.3.3) - очевидно, является асимметричным. Следовательно, мы можем воспользоваться не (30: G), а лишь (30: Н); максимальность среди удовлетворяющих множеств лишь необходима, но может не быть достаточной для насыщенности, т. е. для того, чтобы сделать множество решением.

То, что эта трудность действительно глубока, можно увидеть из следующего. Если бы мы могли заменить наше отношение М на еимметрич-ное отношение, то это можно было бы использовать не только для доказательства существования решений, но и для возможности расширения любого -удовлетворяющего множества дележей до решения (см. выше). Далее, вполне вероятно, что любая игра обладает решением, но мы увидим, что существуют игры, в которых некоторые удовлетворяющие множества не являются подмножествами никаких решений 2). Таким образом, план замены отношения М некоторым симметричным отношением не может быть выполнен, так как он был бы, в равной степени, средством доказательства первого утверждения, которое, по-видимому, верно, и второго утверждения, которое, конечно, неверно 3).

Это рассуждение может показаться читателю никчемным, поскольку отношение хМу, которое мы должны использовать («не-# е- у»), в действительности является асимметричным. С технической точки зрения, однако, возможно, что удастся найти другое отношение хЗу, которое обладает следующими свойствами: отношение хЗу не равносильно отношению хМу, отношение 3* симметричное, в то время как М не симметричное, однако с-насыщенность равносильна .-насыщенности. В этом случае .-насыщенные множества, так как они являются с-насыщенными, должны были бы существовать, а сУ-удовлетворяющие (но не обязательно .-удовлетворяющие) множества всегда могли бы быть расширены до 3-насыщенных, т. е. до -насыщенных множеств 4). Такой план подхода

правдоподобно, что соответствующий процесс исчерпания может быть проведен при помощи бесконечного числа шагов. Этот процесс, известный под названием трансфинитной индукции, является объектом широкого теоретико-множественного изучения. Он может быть осуществлен строгим способом, опирающимся на так называемую аксиому выбора.

Интересующийся читатель может воспользоваться литературой, указанной в книге Ф. Хаусдорфа (см. сноску 1 на стр. 87). См. также E.Zermelo, Beweis, dass jede Menge wohlgeordnet werden kann, Math. Ann., 59 (1904), 514 и след., а также Math. Ann., 65 (1908), 107ff.

Эти вопросы уводят далеко от нашего предмета обсуждения и не являются необходимыми для наших целей. Поэтому мы больше не останавливаемся на этом.

1) Очевидно, свойство (30:В:а) сохраняется при переходе к подмножеству.

2) См. сноску 1 на стр. 304.

3) Это довольно полезный принцип технической стороны математики. Непригодность какого-нибудь метода может быть выведена из того факта, что, если бы его осуществить, он доказал бы слишком много.

4) Дело в том, что для ЗЯ- и -насыщенности допускалась их равносильность между собой, а на равносильность их ?Я- и -удовлетворяемостей мы не рассчитывали

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