Дискретная математика без формул

2) А, И

3) А, Б

4) И, Б

5) А

6) И

7) Б

8) пустое

Из четырех элементов получилось бы 16 элементов. И этот ряд можно бесконечно продолжить, как ряд степеней числа 2.

Так вот, Кантор и доказал, что если взять бесконечное множества счетной мощности, например, множество целых положительных чисел и построить (разумеется, умозрительно) множество, содержащее в качестве элементов все подмножества этого множества, то получим мощность БОЛЬШУЮ, чем счетная мощность. В принципе не существует способа пересчитать (пусть в бесконечности) такое множество. В нем всегда больше элементов. Эта новая большая мощность называется мощностью КОНТИНУУМА.

И снова житейский парадокс. Мощность континуума имеет, например, множество точек прямой или множество действительных чисел, что то же самое. Более того, любой отрезок числовой оси, даже такой малюсенький отрезок, как отрезок от 0 до 1, имеет мощность континуума, то есть на нем больше чисел, чем найдется чисел в счетном множестве. А раз этот отрезок имеет мощность континуума, как и вся (бесконечная) прямая и, естественно, любой ее отрезок, то можно сказать, что на отрезке от 0 до 1 ровно столько же точек, сколько на отрезке прямой от Земли до Юпитера.

Здесь тоже часть равна целому, если и часть, и целое имеют мощность континуума. И все они одинаково больше числа звезд на небе или числа всевозможных алгоритмов…

Для бесконечностей существует очень простая арифметика, которая логически следует из предыдущих разговоров. Сложение двух счетных мощностей дает счетную мощность, а для континуумов – мощность континуума. При вычитании из мощности континуума счетной – в остатке мощность континуума. Но вот если вычитать из континуума континуум или из счетной мощности счетную – всякое может получиться в каждом конкретном случае. Тут запросто можно напрячься и придумать свои иллюстрации.

Однако, не все так просто. Бесконечность остается одной из ключевых категорий философии. И математика здесь подливает масла в огонь, показывая все новые грани этой проблемы. Тем более, если говорить не только о бесконечных, но и о бесконечных упорядоченных множествах. Впрочем, желающие могут почитать книжки об очень красивых вещах с немение красивыми романтическими названиями: «кардиналы и ординалы».

Лекция 3. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

Говорят операции НАДмножествами не потому, что они расположены «над» множествами, а просто так принято. Если НАД

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

Основных операций всего три. Это меньше, чем в школьной арифметике. Хотя даже это множество операций несколько избыточное. Операции называются ОБ'ЕДИНЕНИЕ, ПЕРЕСЕЧЕНИЕи ДОПОЛНЕНИЕ. Чем-то они напоминают школьные операции сложения, умножения и изменения знака. Но эта аналогия приблизительна и опасна, на то она и аналогия.

Начнем с исторической байки.

Аксель Иванович Берг – адмирал и академик, человек со взрывным характером, был одним из первых пропагандистов кибернетики в СССР, когда она еще официально считалась «продажной девкой капитализма». Дискретную математику тогда в технических вузах не изучали из-за полной ее практической бесполезности, а кибернетика уже начинала ею робко пользоваться.

Во время беседы с одним «журналистом по научной тематике», который утверждал, что теория множеств не только не нужна, но и не понятна простому советскому инженеру, Берг прервал беседу и приказал своему шоферу отвести их в ближайший детский садик.

В детском садике дети играли в большом песочнике. Других развлечений в послевоенных садиках было мало. Берг нарисовал в песочнике два больших частично пересекавшихся круга, как это делают со свадебными кольцами на открытках и машинах. (Для тех, кто со свадьбами в жизни не сталкивался, скажем, что с похожим перехлестом рисуют олимпийские кольца).

Далее он сказал: «Пусть в левый круг встанут все, кто любит манную кашу, а в правый – все, кто любит сливовый кисель!». Дети были горазды поесть (послевоенное время голодное), поэтому никто не остался равнодушно стоять в стороне и все забежали в нарисованные круги. Об'единение всех этих маленьких сладкоежек и есть операция об'единения теории множеств.

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

«Ну вот! Не знаю как инженеры, а дети понимают смысл операций над множествами!»,– сказал Берг…

Кстати, здесь роль универсума играл весь песочник.

То, что нарисовал на песке Берг, называют сейчас диаграммами Эйлера-Венна. А то, что находилось на песке за пределами каждого из кругов, было дополнением соответствующего множества, то есть множеством элементов универсума, не принадлежащих к числу любителей данного кушанья (там находились Берг с журналистом).