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


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


26

А не является подмножеством В, равно как и В не является подмножеством А; следовательно, ни разность А -В, ни разность В -А не

являются дополнением одного из этих множеств до другого. На следующем рисунке, однако, В является подмножеством А, так что А - В является дополнением В в А (рис. 3).

8.3. Разбиения, их свойства и их графическое представление

8.3.1. Пусть дано множество Q и система множеств А. Мы будем говорить, что Jh является -разбиением в Q, если оно удовлетворяет следующим двум требованиям:

(8:В:а) Любой элемент А системы Jh является непустым подмножеством множества Q.

(8:В:Ь) Jh представляет собой систему попарно непересекающихся множеств.

Это понятие также породило обширную литературу *). Если даны два разбиения Jh и 98, то мы будем говорить, что Л является подразбиением 98, если они удовлетворяют следующему условию:

(8:В:с) Любой элемент А разбиения Jh является подмножеством некоторого элемента В разбиения 98 2). Отметим, что если Jh является подразбиением 98 и 98 является подразбиением Jh, то Jh = 98 3). Сформулируем теперь следующее определение.

х) См. цитированную в сноске на стр. 88 книгу Г. Биркгофа. Наши требования (8:В:а), (8:В:Ь) не совпадают дословно с общепринятыми. Именно в (8:В:а) иногда не требуется, чтобы элементы А системы Jh были непустыми. Действительно, нам придется сделать одно исключение в п. 9.1.3 (см. сноску 1 на стр. 95). В условии (8:В:Ь) обычно требуется, чтобы объединение всех элементов Jh было равно множеству Q. Для наших целей будет более удобным это требование опустить.

2) Так как Jh и 99 также представляют собой множества, уместно сравнить отношение «быть подмножеством» (применительно к Jh и 99) с отношением «быть подразбиением». Легко видеть, что если Jh является подмножеством 9В, то Jh является и подразбиением 9В, но обратное, вообще говоря, неверно.

3) Доказательство. Рассмотрим некоторый элемент i из «i. Он должен быть подмножеством некоторого элемента В из 9В, а В в свою очередь - подмножеством некоторого элемента At из Jh. Таким образом, А и А имеют общие элементы (именно все элементы непустого множества А) и тем самым не являются дизъюнктными. Так как оба они принадлежат разбиению Jk, отсюда следует А = At. Поэтому А является подмножеством В, а В - подмножеством А (= А). Следовательно, А = В, так что А принадлежит «38. Отсюда мы получаем, что Jh есть подмножество 9В (см. предыдущую сноску). Аналогично & является подмножеством Jh. Следовательно, Jh = 9В.

Рис. 2.

Рис. 3.



(8:B:d) Пусть даны два разбиения Л и 98. Образуем систему всех непустых пересечений A f В, где А пробегает все элементы Л, а В - элементы 98. Очевидно, мы снова получим разбиение, называемое суперпозицией Л и г).

Рис. 4. Рис. 5,

Определим, наконец, описанные выше соотношения для двух разбиений Л и па данном множестве С.

(8:В:е) Л является подразбиением на множестве С, если любое А, принадлежащее Л и являющееся подмножеством С, является также подмножеством некоторого 5, которое принадлежит 98 и является подмножеством С.

(8:B:f) Л равно 98 на множестве С, если элементами Л и 98 являются одни и те же подмножества множества С.

Очевидно, сноска 3 со стр. 89 снова применима - с соответствующими изменениями. Кроме того, определенные сейчас понятия на множестве £2 совпадают с первоначальными понятиями.

8.3.2. Приведем снова некоторые графические иллюстрации в смысле п. 8.2.3.

Начнем с изображения разбиения. Мы не будем обозначать элементы разбиения, представляющие собой множества, буквами, а будем обводить каждое из них пунктиром (рис. 4).

Далее мы изобразим два разбиения Jb и 98 \ для различения их условимся изображать обводящие линии элементов Л «длинным» пунктиром, а элементов $ -«коротким» пунктиром. На рис. 5 Л является подразбиением 98. На следующем рис. 6 Л не является подразбиением 98 и 98 не является подразбиением Л. Предоставляем читателю определить суперпозицию Л и 98 на рис. 6.

Рис. 6.

г) Легко показать, что суперпозиция разбиений Л и & является подразбиением как Л, так и J и что любое разбиение %, представляющее собой подразбиение как Л, так и оказывается также подразбиением их суперпозиции. Отсюда происходит и название. См. гл. I и II цитированной выше книги Г. Биркгофа.



Рис. 7. Рис. 8.

составляющих элементы разбиения, и не может быть использовано для изображения одновременно нескольких разбиений в Q, как это было проделано на рис. 6. Этот недостаток, однако, может быть устранен, если два разбиения А и 98 в Q соотносятся так, как на рис. 5, а именно если А является подразбиением 98. В этом случае мы снова можем представить Q точкой внизу, каждый элемент 98 - отрезком, идущим вверх от этой точки, как на рис. 7, а каждый элемент А - другим отрезком, идущим

Рис. 9.

дальше вверх и начинающимся в верхнем конце того отрезка 98, который представляет элемент 98, подмножеством которого является этот элемент А. Мы можем таким образом представить два разбиения А и 98, изображенные на рис. 5 (см. рис. 8). Это представление опять-таки является менее наглядным, чем соответствующее ему изображение на рис. 5. Однако его простота позволяет продолжить его гораздо дальше, чем могут практически зайти картинки в духе рис. 4-6. Именно, мы можем изобразить при помощи этого приема последовательность разбиений А, . . . . . ., А, в которой каждое разбиение является подразбиением своего непосредственного предшественника. На рис. 9 изображен пример для [I = 5.

Конфигурации такого типа уже изучались в математике; они называются деревьями.

Другое, более схематичное описание разбиений можно получить, представляя множество Q одной точкой, а любой элемент разбиения, представляющий собой подмножество Q, отрезком, идущим из этой точки вверх. Тогда разбиение А (рис. 5) будет представлено гораздо более простым чертежом (рис. 7). Такое представление не указывает элементов,

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