Виленкин Рассказы о множествах. Рассказы о множествах 3е издание
 Скачать 9.06 Mb.
|
|
В какую секцию пойти? у одного больного этой болезнью одних микробов, у другого — дру- гих, у третьего — третьих. Множества микробов, наблюдаемых у раз- ных больных, различны, но обычно два или три микроба наблюда- ются у всех больных этой болезнью. На них и падает подозрение как на возбудителей болезни. И дальнейшее исследование показывает, кто же истинный виновник заболевания. Множество, состоящее из общих элементов нескольких мно- жеств A, B, C, . . . , называется пересечением этих множеств или их произведением. Пересечение двух множеств A и B обозначается AB или A ∩ B. Итак, пересечением нескольких множеств A, B, C, . . . называют новое множество, содержащее те и только те элементы, которые входят в каждое из множеств A, B, C, . . . Например, пусть ученики данной школы участвуют в четырех спортивных секциях: футбольной, плавания, шахматной и бокса. Пе- ресечение множеств участников каждой секции состоит из спортс- менов-универсалов, которые могут и забить пенальти, и переплыть широкую реку, и создать грозную атаку на короля противника, и от- разить нападение хулигана. Разумеется, и в самой математике понятие пересечения мно- жеств находит многочисленные приложения. Одним из основных ме- тодов решения задач на построение является метод геометрических 26 Глава I. Множества и действия над ними мест. Если надо построить точку, удовлетворяющую каким-нибудь двум условиям, то сначала сохраняют только одно из этих усло- вий и опускают второе. Множество точек, удовлетворяющих пер- вому условию, заполняет некоторую линию (геометрическое место точек). Точно так же множество точек, удовлетворяющих только второму условию, заполняет другую линию. А тогда искомая точ- ка является пересечением этих двух линий (геометрических мест). Может, конечно, оказаться, что эти линии пересекаются не в од- ной, а в нескольких точках. Тогда задача имеет несколько решений. А если эти линии совсем не пересекаются, то задача не имеет реше- ния. Например, пусть надо найти точку C, удаленную на расстояние a от точки O и равноудаленную от точек A и B. Искомая точка должна, во-первых, лежать на окружности радиуса a с центром в O, а во-вторых, на перпендикуляре к отрезку AB, проходящему через середину этого отрезка. Значит, чтобы найти точки, удовлетворяю- щие поставленным условиям, достаточно взять точки пересечения прямой и окружности (здесь могут получиться две, одна или ни од- ной точки пересечения, см. рис. 8). Рис. 8 Иногда приходится пересекать множества геометрических фигур или чисел. Например, множество всех квадратов является пересече- нием множества всех прямоугольников с множеством всех ромбов. Множество правильных треугольников является пересечением мно- жества всех треугольников с множеством правильных многоугольни- ков. Пересечением множества натуральных чисел, делящихся на 2, и множества натуральных чисел, делящихся на 3, является множе- ство натуральных чисел, делящихся на 6. Решение систем уравнений и неравенств, по сути дела, сводит- ся к отысканию пересечения некоторых множеств (впрочем, можно сказать и наоборот: пересечение некоторых множеств ищется путем решения систем уравнений или неравенств). Пусть, например, надо Пересечение множеств 27 решить систему уравнений x 2 + y 2 = 25, x + y = 7. (1) С точки зрения алгебры перед нами задача найти все пары чисел (x; y), при подстановке которых в оба уравнения системы получают- ся тождества. Но уравнения системы можно рассматривать по от- дельности. Обозначим через M множество всех пар чисел (x; y), удовлетворяющих первому из наших уравнений, а через N — мно- жество всех пар чисел (x; y), удовлетворяющих второму уравнению. Тогда решениями системы будут все пары чисел, принадлежащие Рис. 9 как множеству M , так и множеству N . Иными словами, множеством решений системы (1) является пересечение мно- жеств M и N . Это замечание лежит в основе гео- метрического метода решения систем — строят линии, выражаемые каждым из уравнений системы, и находят их пересечение. Например, мы уже знаем, что точки A(x; y), координаты которых удовлетворяют уравнению x 2 + y 2 = 25, лежат на окружности радиуса 5 с цен- тром в начале координат. А уравнение x + y = 7 — это уравнение прямой, отсе- кающей на обеих координатных осях отрезки длины 7. Если начер- тить эти линии, то окажется, что они пересекаются в двух точках: A(4; 3) и B(3; 4). Значит, наша система имеет два решения: x 1 = 3, y 1 = 4 и x 2 = 4, y 2 = 3 (рис. 9). Рассмотрим теперь систему неравенств y x 2 , y 8 − x 2 (2) Множество M решений неравенства y x 2 состоит из точек A(x; y), лежащих на параболе y = x 2 и выше этой параболы. А множе- ство N решений неравенства y 8 − x 2 состоит из точек плоскости, лежащих на параболе y = 8 − x 2 и ниже этой параболы (рис. 10). На рис. 10 множество M заштриховано горизонтальными линиями, а множество N — вертикальными линиями. Решением системы нера- венств (2) является пересечение P множеств M и N . На рис. 10 28 Глава I. Множества и действия над ними оно отмечено двойной штриховкой. При этом точки границы множе- ства P принадлежат этому множеству. Точно так же устанавливаем, что решением системы y > x 2 , y = 2x + 3 (3) является часть прямой y = 2x + 3, лежащая выше параболы y = x 2 Прямая пересекается с параболой в точках A(−1; 1) и B(3; 9), и выше параболы лежит часть прямой, заключенная между точками A и B (сами точки A и B не принадлежат множеству решений системы, см. рис. 11). Рис. 10 Рис. 11 А теперь путем изучения пересечения множеств покажем, что иррациональное уравнение 2 + x − x 2 + 8x − x 2 − 15 = 7 (4) не имеет решений. Конечно, можно было бы начать решать это урав- нение, уединив радикал и возведя обе части уравнения в квадрат, и лишь в самом конце, после проверки получившихся корней, убе- диться, что уравнение не имеет решений. Но мы сделаем по-другому. Сначала выясним, при каких значениях x имеют смысл радикалы, входящие в это уравнение. Радикал √ 2 + x − x 2 имеет смысл, если 2 + x − x 2 0. Решая это неравенство, получим, что −1 x 2. Точ- но так же обнаруживаем, что радикал √ 8x − x 2 − 15 имеет смысл, лишь если 3 x 5. Но отрезки −1 x 2 и 3 x 5 не имеют Сложение множеств 29 общих точек, их пересечение пусто. Поэтому ни одно значение x не может удовлетворять уравнению (4). Сложение множеств Еще чаще, чем пересекать множества, приходится объединять их. Уже первоклассник, складывая три палочки и две палочки, объеди- няет два множества. Вообще, действие сложения натуральных чисел связано с подсчетом числа элементов объединения двух множеств. Но здесь надо иметь в виду одну тонкость. Пусть есть два сплава. Один сплав содержит железо, углерод, ванадий и марганец, а вто- рой — железо, углерод, хром и никель. В каждый сплав входят по 4 химических элемента, но если мы сплавим их вместе, то в новый сплав войдут только 6 элементов: железо, углерод, ванадий, марга- нец, хром и никель. Дело в том, что железо и углерод были в обоих сплавах, то есть объединяемые множества элементов имели непустое пересечение. Поэтому будет правильнее сказать, что сложение нату- ральных чисел связано с объединением непересекающихся множеств. Рис. 12 Если же пересечение множеств не пусто, то в их объединении повто- ряющиеся элементы считаются лишь по одному разу. Таким образом, сум- мой нескольких множеств A, B, . . . называют новое множество, состоя- щее из тех и только тех элементов, которые входят хоть в одно из слага- емых множеств. Сумму множеств A и B обычно обозначают A + B или A ∪ B. На рис. 12 изображено объ- единение множества A точек круга Γ 1 и множества B точек круга Γ 2 Если некоторые элементы входят не в одно, а в несколько слага- емых множеств, в сумму они все равно входят только один раз. Поэтому для конечных множеств число элементов суммы может оказаться меньше, чем сумма чисел элементов слагаемых. Например, пусть первое множество состоит из различных букв русского алфа- вита, входящих в первую строку «Евгения Онегина», а второе — из различных букв, входящих во вторую строку этой поэмы. Первое множество мы уже выписывали. Оно состоит из 18 букв (см. с. 11): М, О, Й, Д, Я, С, А, Ы, Х, Ч, Е, Т, Н, П, Р, В, И, Л. 30 Глава I. Множества и действия над ними Второе же множество состоит из 13 букв: К, О, Г, Д, А, Н, Е, В, Ш, У, Т, З, М. Суммой этих двух множеств является следующий набор 23 букв: М, О, Й, Д, Я, С, А, Ы, Х, Ч, Е, Т, Н, П, Р, В, И, Л, К, Г, Ш, У, З. Буквы О, Д, А, Н, Е, В, Т, М, входящие в пересечение наших множеств, вошли в сумму только один раз, и поэтому мы получили только 23 буквы, а не 18 + 13 = 31 букву. Вот еще один пример, когда складываемые множества имеют общие элементы. Множество всех учеников в классе является суммой следующих трех множеств: а) множества успевающих учеников, б) множества девочек, в) множества неуспевающих мальчиков. Ясно, что каждый учащийся этого класса принадлежит хотя бы од- ному из указанных множеств. Однако эти множества могут иметь общие элементы: успевающие девочки входят и в первое, и во вто- рое множество. Иногда сумма состоит из бесконечного числа слагаемых мно- жеств. Например, обозначим через A n множество всех положитель- ных дробей со знаменателем n: A 1 = m 1 , A 2 = m 2 , . . . , A n = m n , . . . Суммой всех множеств A 1 , A 2 , . . . , A n , . . . является множество всех положительных дробей, то есть дробей вида m n , где m и n — нату- ральные числа. Обозначим через A 3 множество правильных треугольников, че- рез A 4 — множество правильных четырехугольников, через A 5 — множество правильных пятиугольников и т. д. Тогда суммой всех этих множеств является множество A всех правильных многоуголь- ников. Поговорим теперь о сложении множеств в алгебре. В одном из своих рассказов известный американский писатель Эдгар По пишет: «Я никогда не встречал математика, который не держался бы как за Символ Веры за то, что x 2 + px + q абсолютно и безусловно рав- но нулю. Скажите одному из этих джентльменов, если вам угодно, в виде опыта, что, на ваш взгляд, могут существовать случаи, когда Сложение множеств 31 x 2 + px + q не целиком равно нулю, и, втолковав ему то, что вы ра- зумеете, возможно скорее спасайтесь из пределов его досягаемости, так как, без сомнения, он попытается вас поколотить». Разумеется, читатель понимает, что x 2 + px + q может быть рав- но нулю при одних значениях x и отличаться от нуля при других. Но нас интересует иной вопрос: почему математики всегда стараются записать уравнение так, чтобы одна его часть была равна нулю? Что- бы это стало яснее, рассмотрим такое уравнение: x 2 (x 2 − 7) = −12. Из того, что произведение двух выражений равно −12, трудно вы- вести что-либо о величине каждого из этих выражений. Поэтому решать уравнение в таком виде весьма затруднительно. А если пе- ренести −12 в левую часть уравнения и разложить получившееся выражение на множители, то получим уравнение (x 2 − 4)(x 2 − 3) = 0. (1) Теперь уже можно применить известное рассуждение: для того что- бы произведение было равно нулю, надо, чтобы хоть один из мно- Рис. 13 жителей был равен нулю. Поэтому решение уравнения (1) сводится к решению двух уравне- ний: x 2 − 4 = 0 и x 2 − 3 = 0. Но в от- личие от случая решения систе- мы уравнений здесь надо искать не числа, которые удовлетворяют сразу обоим уравнениям, а числа, которые удовлетворяют хотя бы одному из двух уравнений. Ины- ми словами, нам надо теперь ис- кать не пересечение, а объедине- ние множеств корней. Решая первое уравнение, получим корни x 1 = 2, x 2 = −2, а решая второе уравнение, находим еще два корня: x 3 = √ 3, x 4 = − √ 3. Объединяя множества {2, −2} и { √ 3, − √ 3}, получаем множество корней {2, −2, √ 3, − √ 3} заданного уравнения. Точно так же уравнение (x 2 + y 2 − 37)(y − x − 7) = 0 (2) задает множество, состоящее из окружности с уравнением x 2 + + y 2 − 37 = 0 и прямой, имеющей уравнение y − x − 7 = 0 (рис. 13). 32 Глава I. Множества и действия над ними Если бы вместо этого уравнения была задана система уравнений x 2 + y 2 − 37 = 0, y − x − 7 = 0, то она задавала бы не всю фигуру, изображенную на рис. 13, а лишь две точки A(−6; 1) и B(−1; 6), в которых прямая пересекает окруж- ность. Разбиение множеств Вообще говоря, слагаемые множества могут иметь общие элемен- ты. Однако часто бывает, что некоторое множество является суммой своих подмножеств, никакие два из которых не имеют общих эле- ментов (или, как обычно говорят, не пересекаются). В этом случае говорят, что множество A разбито на непересекающиеся подмноже- ства. Разбиение на подмножества часто используется для классифика- ции объектов. Например, когда составляют каталог книг в библио- теке, то все множество книг разбивают на книги беллетристическо- го характера, книги по общественно-политическим наукам, по есте- ственным наукам и т. д. В биологии все множество животных разбивается на типы, ти- пы — на классы, классы — на отряды, отряды — на семейства, семейства — на роды, а роды — на виды. Конечно, одно и то же множество можно разными способами раз- бивать на подмножества. Когда в той же библиотеке составляют ал- фавитный каталог, то сначала книги разбиваются на подмножество книг, фамилии авторов которых начинаются на А, подмножество книг, фамилии авторов которых начинаются на Б, и т. д. После этого каждое полученное подмножество разбивают в соответствии со вто- рой буквой фамилии авторов и т. д. При разбиении множества на подмножества часто использу- ют понятие эквивалентности элементов. Для этого определяют, что значит «элемент x эквивалентен элементу y», после чего объединя- ют эквивалентные элементы в одно подмножество. Однако не всякое понятие эквивалентности годится для такого разбиения. Например, назовем двух людей эквивалентными, если они знакомы друг с дру- гом. Такое определение эквивалентности окажется неудачным. Ведь может случиться, что человек X знаком с человеком Y , человек Y Арифметика остатков 33 знаком с человеком Z, а люди X и Z друг с другом незнакомы. То- гда нам придется сначала отнести в одно подмножество людей X и Y (они друг с другом знакомы), потом в то же подмножество включить и Z (он знаком с Y ), и у нас в одном подмножестве окажутся незна- комые друг с другом X и Z. Чтобы не было таких неприятностей, нужно, чтобы для понятия эквивалентности выполнялись следую- щие три условия: а) каждый элемент сам себе эквивалентен; б ) если элемент x эквивалентен элементу y, то элемент y эк- вивалентен элементу x; в) если элемент x эквивалентен элементу y, а элемент y экви- валентен элементу z, то элемент x эквивалентен z. Можно доказать, что выполнение этих условий необходимо и до- статочно для того, чтобы множество A можно было разбить на под- множества эквивалентных между собой элементов (и притом так, что разные подмножества не имеют общих элементов). Например, назовем два целых числа x и y эквивалентными, если их разность — четное число. Легко проверить, что при этом выполня- ются все три условия а)–в). Объединяя эквивалентные целые числа, мы разобьем множество всех целых чисел на два подмножества: мно- жество четных чисел и множество нечетных чисел. Арифметика остатков Если m — любое натуральное число, большее 1, то с его помощью множество натуральных чисел можно разбить следующим образом на классы. Назовем два числа сравнимыми по модулю m, если их разность делится на m. Например, числа 7 и 19 сравнимы по моду- лю 4, но не сравнимы по модулю 5, так как 19 − 7 = 12 делится на 4, но не делится на 5. Легко проверить, что сравнимость чисел по дан- ному модулю обладает всеми свойствами эквивалентности. Поэтому множество целых чисел разбивается на классы чисел, сравнимых между собой по модулю m. Число таких классов равно m, и все чис- ла данного класса при делении на m дают один и тот же остаток. Например, если m = 3, то получается 3 класса: класс чисел, крат- ных 3, класс чисел, дающих при делении на 3 остаток 1, и класс чисел, дающих при делении на 3 остаток 2. Составим теперь новое множество, элементами которого являют- ся классы чисел, сравнимых по заданному модулю m. Множество M 34 Глава I. Множества и действия над ними состоит из m элементов. В этом множестве можно определить дей- ствия сложения и умножения элементов. Например, пусть m = 5. Возьмем класс A чисел, дающих при делении на 5 остаток 2, и класс B чисел, дающих при делении на 5 остаток 4. Если взять любое число класса A и прибавить к нему любое число класса B, то получится число, дающее при делении на 5 остаток 1 (в самом деле, (5a + 2) + (5b + 4) = 5(a + b + 1) + 1). Поэтому можно сказать, что суммой класса A и класса B является класс C чисел, дающих при делении на 5 остаток 1. Если умножить любое число класса A на любое число класса B, то получится число, дающее при делении на 5 остаток 3 (так как (5a + 2)(5b + 4) = 5(5ab + 4a + 2b + 1) + 3). Мы получили любопытную арифметику, в которой имеют дело не с бесконечным множеством целых чисел, а всего с пятью эле- ментами — пятью классами чисел. Будем обозначать класс чисел, дающих при делении на 5 остаток a, через a (например, класс чи- сел {. . . , −4, 1, 6, 11, 16, . . . } обозначим просто 1). Для «чисел» 0, 1, 2, 3, 4 арифметика задается следующими таблицами сложения и умножения: Таблица сложения + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 Таблица умножения × 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 Особенно простой вид принимают эти таблицы для случая m = 2: + 0 1 0 0 1 1 1 0 × 0 1 0 0 0 1 0 1 Первая таблица показывает, что сумма двух четных или нечетных чисел четна, а сумма четного и нечетного числа нечетна. Вторая же таблица показывает, что произведение двух целых чисел нечетно лишь в случае, когда нечетны оба сомножителя. Арифметика клас- сов по данному модулю изучается в отделе математики, называемом теорией чисел. Вычитание множеств 35 Вычитание множеств Полицейский-инспектор Варнике осмотрел сейф, закурил свою трубку и сказал: «Электродрелью вскрывают сейфы только пять взломщиков: Алек Кунце, Фриц Шмидт, Густав Хойгер, Генрих Кунтцман и Томас Мюллер. Но Алек, Фриц и Густав сейчас нахо- дятся в тюрьме Моабит. Придется спросить Генриха и Томаса, где они провели прошлую ночь...» Метод, которым воспользовался инспектор Варнике, основан на операции вычитания множеств. Он имел дело с двумя множества- ми — множеством A взломщиков, пользовавшихся электродрелью, и множеством B всех обитателей тюрьмы Моабит. Удалив из множе- ства A все элементы, принадлежащие множеству B, он сузил круг подозреваемых преступников. Вообще, разностью двух множеств A и B называют новое множе- ство, обозначаемое A − B или A \ B, в которое входят все элементы множества A, не принадлежащие B. Мы видим, что для того, чтобы из множества A можно было вы- честь множество B, совершенно не обязательно, чтобы множество B было частью множества A — вычитание B из A сводится к удалению из A общей части A и B: A − B = A − AB. Например, инспектору Варнике надо было из числа пяти взломщи- ков отбросить трех — тех, что пользовались электродрелью и в то же Рис. 14 время находились в данный момент в тюрьме. Если A — множество то- чек первого круга на рис. 14, а B — множество точек второго круга, то их разностью является множество точек заштрихованной серповидной фигуры (без дуги M N ). Если A — множе- ство всех учеников данного класса ка- кой-либо школы, а B — множество всех девочек, учащихся в этой школе, то A − B — множество всех мальчи- ков, которые учатся в данном классе этой школы. В случае, ко- гда B является частью множества A, A − B называют дополнением к множеству B в A и обозначают B A (разумеется, oдно и то же 36 Глава I. Множества и действия над ними множество B имеет разные дополнения в разных содержащих его множествах A). Например, дополнением множества четных чисел в множестве всех целых чисел является множество нечетных чисел. Дополнением множества всех квадратов в множестве прямоуголь- ников является множество всех прямоугольников с неравными сто- ронами. А дополнением того же множества квадратов в множестве всех ромбов является множество ромбов с неравными диагоналями. Если все множества рассматриваются как подмножества универ- сального множества I, то обычно под дополнением множества B понимают его дополнение в I. В этом случае вместо B I пишут про- сто B . Алгебра множеств Мы познакомились с основными действиями над множествами — сложением, вычитанием и умножением (пересечением) множеств. Эти действия обладают целым рядом свойств, напоминающих свой- ства действий над числами. Как известно, вся алгебра многочленов построена на немногих законах действий над числами, которые выражаются следующими равенствами: а) a + b = b + a (коммутативность сложения), б) (a + b) + c = a + (b + c) (ассоциативность сложения), в) a + 0 = a (свойство нуля), г) a + (−a) = a − a = 0 (свойство противоположного элемента), д) ab = ba (коммутативность умножения), е) (ab)c = a(bc) (ассоциативность умножения), ж) a(b + c) = ab + ac (дистрибутивность умножения относительно сложения), з) a · 1 = a (свойство единицы). Большинство этих свойств действий над числами сохраняется и для действий над множествами. Например, ясно, что для любых двух множеств имеем A + B = B + A (A + B и B + A обозначают одно и то же множество, в которое входят все элементы из A и из B и не входят никакие другие элементы). Точно так же ясно, что (A + B) + C = A + (B + C) — оба множества составлены из всех элементов, входящих хотя бы в одно из множеств A, B и C. Так же доказывается, что AB = BA и (AB)C = A(BC) (множества AB и BA состоят из общих элементов Алгебра множеств 37 множеств A и B, а множества (AB)C и A(BC) — из общих элементов множеств A, B и C). Несколько сложнее доказать дистрибутивность умножения мно- жеств относительно сложения, то есть выполнение равенства A(B + C) = AB + AC. (1) Строгое логическое доказательство этого равенства несложно, но несколько кропотливо. Мы ограничимся поэтому двумя ри- сунками, поясняющими это равенство (рис. 15). На первом из этих рисунков заштриховано пересечение множества A с множеством B + C, а на втором — пересечения A с B и A с C. Рис. 15 Роль нуля и единицы в действиях над множествами играют мно- жества ∅ (пустое множество) и I (универсальное множество). Имен- но, справедливы равенства A + ∅ = A, A · ∅ = ∅, A · I = A, соответствующие равенствам a + 0 = a, a · 0 = 0, a · 1 = a для чисел. Таким образом, сложение и умножение множеств обладают теми же свойствами, что и сложение и умножение чисел. Поэтому все формулы алгебры многочленов, в которые входят лишь действия сложения и умножения, остаются справедливыми и для множеств. Например, тождеству (a + b) 2 = a 2 + b 2 + 2ab соответствует тождество (A + B) 2 = A 2 + B 2 + 2AB, (2) где положено A 2 = A · A и 2AB = AB + AB. 38 Глава I. Множества и действия над ними Но алгебра множеств имеет и своеобразные черты. Ее основ- ное своеобразие состоит в том, что если одно из множеств A и B Рис. 16 является подмножеством другого, то фор- мулы для суммы и произведения мно- жеств упрощаются, а именно: если A ⊂ B, то A + B = B и AB = A. Это сразу становит- ся ясно из рис. 16. В частности, так как A ⊂ A, то A + A = = AA = A, а так как A ⊂ I, то A + I = I. Это позволяет упростить формулы ал- гебры множеств. Например, так как A 2 = A, B 2 = B, AB ⊂ A, то A 2 + 2AB = A + 2AB = A и формула (2) прини- мает вид (A + B) 2 = A + B. Вообще, в алгебре множеств не имеет смысла говорить о степенях, так как для любого n имеем A n = A. Покажем теперь, что для множеств есть и второй «распредели- тельный закон», которого нет для чисел. Он выражается формулой A + BC = (A + B)(A + C). Чтобы доказать его, достаточно раскрыть справа скобки по прави- лу (1) и заметить, что множества AB и AC являются подмножества- ми в A: AC ⊂ A и AB ⊂ A. Кроме того, AA = A, а поэтому AA + AC + BA + BC = A + BC. Отметим, далее, что операция вычитания множеств уже не похожа по своим свойствам на операцию вычитания чисел. Для любых трех чисел a, b, c верно равенство a + (b − c) = (a + b) − c. А для трех мно- жеств A, B, C, вообще говоря, A + (B − C) = (A + B) − C. Дело в том, что при сложении множеств повторяющиеся элементы берутся только один раз, а вычитать можно и множество, не со- держащееся в уменьшаемом. Поэтому, если, например, все три множества A, B, C совпадают, A = B = C, то A + B = A и пото- му (A + B) − C = A − A = ∅ — пустое множество, а A + (B − C) = = A + ∅ = A. В теории множеств есть еще операция, отсутствующая в обыч- ной алгебре. Это операция перехода от данного множества A к его дополнению A = I − A. Ясно, что множества A и A не пересека- ются, а в сумме составляют все универсальное множество I. Таким Алгебра множеств 39 образом, AA = ∅ и A + A = I. Кроме того, ясно, что ∅ = I (допол- нение пустого множества совпадает с универсальным множеством) Рис. 17 и I = ∅. Далее, имеет место равенство (A ) = A (рис. 17). Покажем теперь, что если A ⊂ B, то A ⊃ B . В самом деле, чем больше само множество, тем меньше элементов останется в его дополнении. На рис. 18 универсальное множество I изображено в виде прямоугольника, а множества A и B — в виде кругов. Дополнение к мно- жеству A состоит из точек прямоуголь- ника, лежащих вне меньшего круга, а дополнение к множеству B — из точек прямоугольника, лежащих вне большого круга. Ясно, что A ⊃ B . Рис. 18 Рис. 19 Несколько сложнее доказываются следующие формулы: (A + B) = A B и (AB) = A + B . На рис. 19 дополнение к множеству A заштриховано горизонтальны- ми линиями, а дополнение к множеству B — вертикальными линия- ми. Дополнение к множеству A + B состоит из точек прямоугольни- ка, не попавших ни в один из кругов. Это как раз точки, лежащие в области, покрытой обеими штриховками, то есть точки из A B . Поэтому ясно, что (A + B) = A B . Точно так же этот рисунок ил- люстрирует и формулу (AB) = A + B . Мы установили ряд свойств действий над множествами. Ра- ди удобства приведем список этих свойств (как обычно, через ∅ 40 Глава I. Множества и действия над ними мы обозначаем пустое множество, через I — универсальное мно- жество, через A — дополнение множества A в универсальном множестве). 1) A ⊂ A. 2) Если A ⊂ B и B ⊂ A, то A = B. 3) Если A ⊂ B и B ⊂ C, то A ⊂ C. 4) ∅ ⊂ A. 5) A ⊂ I. 6) A + B = B + A. 7) AB = BA. 8) A + (B + C) = (A + B) + C. 9) A(BC) = (AB)C. 10) A + A = A. 11) AA = A. 12) A(B + C) = AB + AC. 13) A + BC = (A + B)(A + C). 14) A + ∅ = A. 15) AI = A. 16) A + I = I. 17) A∅ = ∅. 18) Соотношение A ⊂ B эквивалентно каждому из соотношений A + B = B, AB = A. 19) A + A = I. 20) AA = ∅. 21) ∅ = I. 22) I = ∅. 23) (A ) = A. 24) Соотношение A ⊂ B эквивалентно B ⊂ A . 25) (A + B) = A B . 26) (AB) = A + B . Отметим следующее замечательное «соотношение двойственно- сти». Если в каждом из свойств 1)–26) заменить друг на друга сим- волы «⊂» и «⊃», «∅» и «I», «+» и «·», то в результате получится снова одно из этих свойств. Например, таким путем из свойства 6) получается свойство 7), из свойства 12) — свойство 13) и т. д. Отсюда вытекает, что каждой теореме, которая может быть вы- ведена из свойств 1)–26), соответствует другая «двойственная» ей теорема, получающаяся из первой посредством указанных переста- новок символов. Планета мифов 41 Разумеется, запомнить все свойства 1)–26) не слишком легко. Но это и не нужно. Дело в том, что можно ограничиться двумя основными операциями: сложением множеств и образованием допол- нения, потребовав, чтобы выполнялись следующие три соотношения: а) A + B = B + A, б) (A + B) + C = A + (B + C), в) (A + B ) + (A + B) = A. Определим теперь действие умножения AB, соотношение вклю- чения A ⊂ B и множества I, ∅ формулами г) AB по определению равно (A + B ) ; д) A ⊂ B по определению означает, что A + B = B; е) I = A + A , ∅ = I . Тогда все свойства 1)–26) вытекают из формул а)–е). Планета мифов Однажды во время беседы за чашкой кофе в клубе Межгалакти- ческих путешественников знаменитый член этого клуба, Мюнхгаузен космической эры, Йон Тихий 1 рассказал: «Высадка на планету Гесиод была очень трудна. Но когда я ока- зался на поверхности, то пожалел, что решил опуститься: на ней жили чудовища, более страшные, чем описанные в древних мифах греков. Навстречу мне вышла делегация из 1000 жителей планеты. У 811 из них был один глаз, как у циклопа Полифема, у 752 — вместо волос были змеи, как у Медузы Горгоны, а 418 имели рыбий хвост, как нереиды. При этом 570 чудовищ были одноглазы и змееволосы, 356 — одноглазы и имели рыбий хвост, 348 — змееволосы и с ры- бьим хвостом, а 297 — одноглазы, змееволосы и с рыбьим хвостом. Старший из них обратился ко мне и сказал...» Но члены клуба так и не узнали, что услышал Йон Тихий на пла- нете чудовищ. Слушавший рассказ путешественника профессор Та- рантога мгновенно произвел в уме какие-то выкладки и воскликнул: «Дорогой Йон! Я готов поверить, что на этой планете жили суще- ства с одним глазом, со змеями вместо волос и с рыбьими хвостами. 1 Путешествия Йона Тихого описаны известным польским писателем-фанта- стом Станиславом Лемом в «Звездных дневниках Иона Тихого». Автор «Рас- сказов о множествах» надеется, что С. Лем простит ему неумелую попытку подражания, а читатели не будут обвинять С. Лема в литературных недочетах изложения автора. 42 Глава I. Множества и действия над ними Тебе приходилось встречать еще более страшных чудовищ — вспом- ни о курдлях. Но я надеюсь, что законы математики на этой планете не превратились в мифы». И Тарантога взял со стола бумажную салфетку и нарисовал на ней следующую схему (рис. 20). Он сказал: «Обозначим через I множество всех членов делегации, через A — множество одноглазых, через B — множество змееволосых делега- Рис. 20 тов, а через C — имеющих рыбьи хвосты. Эти множества изображены на рис. 20 в виде кругов. Три круга де- лят прямоугольник на 8 частей. Подсчи- таем, сколько элементов входит в каж- дую часть. По условию в множество AB (то есть одноглазых и змееволосых) вхо- дило 570 существ, а в множество ABC (одноглазых, змееволосых и с рыбьими хвостами) — 297. Значит, в множество AB − ABC входит 273 существа. Это то самое множество, которое на рис. 20 заштриховано горизонтальными линия- ми. Точно так же находим, что множе- ство AC − ABC состоит из 59 существ (это множество на рис. 20 заштриховано вертикальными линиями), а множество BC − ABC — из 51 существа (это множество заштриховано косыми линиями). Теперь уже легко найти численность части множества A, не при- надлежащей B + C. Для этого из 811 надо вычесть 570 (численность множества AB) и еще 59 (численность множества AC − ABC). Оста- нется 182 существа, которые одноглазы, но не имеют ни змей на голо- ве, ни рыбьих хвостов. Точно так же устанавливаем, что численность множества B − (A + C) равна 131, а множества C − (A + B) равна 11. Результаты подсчетов изображены на рис. 21. Подсчитаем теперь, сколько же членов делегации не были ни од- ноглазыми, ни змееволосыми и не имели рыбьих хвостов, то есть сколько элементов содержит множество I − A − B − C. Так как от- дельные множества на рис. 21 не пересекаются, то для этого на- до просто отнять от 1000 сумму 297 + 273 + 59 + 51 + 182 + 131 + 11. Но эта сумма равна 1004, и потому множество I − A − B − C насчи- тывает −4 существа. Но согласись сам, дорогой Йон, даже на планете мифов ни одно множество не может иметь отрицательной численно- сти. Даже для тебя такие выдумки слишком невероятны». Планета мифов 43 Рис. 21 Рис. 22 Оставим Йона Тихого объясняться с профессором Таран- тогой (скоро мы снова встретимся с нашим героем) и сделаем несколько замечаний. Мы разложили все множество I на 8 подмно- жеств и нашли их численность. Смысл этого разложения состоял в том, что полученные подмножества попарно не пересекались. Но это же разложение можно было бы получить иначе. Мы знаем, что I = A + A = B + B = C + C и потому I = (A + A )(B + B )(C + C ) = ABC + ABC + AB C + + AB C + A BC + A BC + A B C + A B C . Получилось разложение множества I на 8 подмножеств. Это те же самые подмножества, которые получил ранее профессор Тарантога (рис. 22). Из предыдущей формулы сразу вытекает, что N (A B C ) = N (I) − N (ABC) − N (ABC ) − N (AB C) − − N (AB C ) − N (A BC) − N (A BC ) − N (A B C), где через N (D) обозначена численность множества D. Эту формулу можно преобразовать так, чтобы в нее не входили дополнения A , B , C множеств A, B, C. С этой целью заменим C на I − C. Мы получим, что ABC = AB(I − C) = AB − ABC и потому N (ABC ) = N (AB) − N (ABC), N (AB C ) = N (AB ) − N (AB C) и т. д. 44 Глава I. Множества и действия над ними Заменим потом B на I − B и, наконец, A на I − A, получим в конце концов равенство N (A B C ) = N (I) − N (A) − N (B) − N (C) + + N (AB) + N (AC) + N (BC) − N (ABC). Эта формула называется формулой включений и исключений и по- зволяет решать многие задачи, аналогичные рассмотренной выше. Например, Тарантога мог сразу подсчитать по этой формуле, что N (A B C ) = 1000 − 811 − 752 − 418 + 570 + 356 + 348 − 297 = −4. Вот еще одна задача, связанная с подсчетом численности ко- нечных множеств. Она принадлежит известному детскому писателю Льюису Кэрроллу, автору «Алисы в стране чудес». Любопытно, что под псевдонимом Льюис Кэрролл писал математик Доджсон. В одной из повестей Кэрролла есть следующая задача: «В ожесточенном бою 70 из 100 пиратов потеряли один глаз, 75 — одно ухо, 80 — одну руку и 85 — одну ногу. Каково минимальное число потерявших одновременно глаз, ухо, руку и ногу?» Обозначим через A множество одноглазых, через B — множество одноухих, через C — множество одноруких и через D — множе- ство одноногих. В задаче требуется оценить численность множества ABCD. Ясно, что все универсальное множество I можно предста- вить как сумму этого множества ABCD и множества пиратов, со- хранивших либо оба глаза, либо оба уха, либо обе руки, либо обе ноги. Поэтому I = A + B + C + D + ABCD. Отсюда следует, что численность множества I не больше суммы чис- ленностей множеств A , B , C , D и ABCD (она была бы равна этой сумме, если бы множества A , B , C и D попарно не пересе- кались). Но численность множества A равна 30, множества B — 25, множества C — 20 и множества D — 15. Так как численность универсального множества равна 100, то имеем 100 30 + 25 + 20 + 15 + N (ABCD). Отсюда N (ABCD) 100 − 30 − 25 − 20 − 15 = 10. Итак, не менее 10 пиратов лишились и глаза, и уха, и руки, и ноги. Булевы алгебры 45 Булевы алгебры В математике встречаются и другие объекты, кроме множеств, для которых определены действия сложения и умножения, удо- влетворяющие условиям 1)–26). Такие системы объектов изучил в 1847 году английский математик Буль (отец писательницы Этель Лилиан Войнич — автора знаменитой книги «Овод»). Поэтому та- кие системы назвали булевыми алгебрами. Но когда это название уже укоренилось, выяснилось, что Буль имел предшественников — в 1685 году братья Бернулли изучали «алгебру» с теми же законами. Совпадение интересов братьев Бернулли и Буля вполне понятно: все они интересовались алгеброй логики, возможностью представить в алгебраической форме рассуждения, высказывания. А булевы ал- гебры специально приспособлены к этой цели. Высказыванием в ма- тематической логике называют предложение, которое может быть верно или ложно. При этом в логике не интересуются вопросом, вер- но или ложно данное высказывание на самом деле. Там обсуждают лишь проблему, по каким правилам можно из данных высказываний получать более сложные и как из знания истинности или ложности исходных высказываний выводить истинность или ложность слож- ных высказываний. Над высказываниями можно делать следующие операции: 1) Отрицание — замена данного высказывания X противополож- ным высказыванием X, которое истинно, если данное выска- зывание ложно, и ложно, если высказывание X истинно. 2) Конъюнкция — образование из данных двух высказываний X и Y третьего высказывания X ∧ Y , истинного лишь в случае, если истинны оба высказывания X и Y . 3) Дизъюнкция — образование из данных двух высказываний X и Y третьего высказывания X ∨ Y , истинного в случае, когда истинно хоть одно из данных высказываний. 4) Импликация — образование из высказываний X и Y третьего высказывания X → Y , ложного лишь в случае, когда X ис- тинно и Y ложно. Во многих случаях высказывание состоит в том, что некоторый элемент x принадлежит подмножеству A некоторого универсально- го множества I. В этом случае операции 1)–4) над высказываниями соответствуют известным нам операциям над множествами. Напри- мер, отрицание высказывания «x ∈ A» есть высказывание «x ∈ A ». 46 Глава I. Множества и действия над ними Таким образом, взятию дополнения A соответствует отрицание вы- сказывания «x ∈ A». Точно так же операции пересечения множеств A и B соответствует конъюнкция высказываний «x ∈ A» и «x ∈ B», операции сложения множеств — дизъюнкция высказываний и соот- ношению A ⊂ B — импликация высказываний «x ∈ A» и «x ∈ B». При этом высказывание «x ∈ I» всегда истинно, а высказывание «x ∈ ∅» всегда ложно. Отмеченная связь делает естественным предположение, что зако- ны 1)–26) верны не только для множеств, но и для высказываний, ес- ли только понимать A ∩ B как конъюнкцию высказываний, A ∪ B — как их дизъюнкцию, A — как отрицание высказывания A, A ⊂ B — как импликацию высказываний, I — как всегда истинное, а ∅ — как всегда ложное высказывание. Оказалось, что это предположение верно — высказывания образуют булеву алгебру относительно опе- раций 1)–4). Но булевы алгебры можно строить не только из высказываний. Рассмотрим, например, множество всевозможных последовательно- стей, содержащих n цифр, причем каждая цифра равна нулю или единице. Определим сложение и умножение двух таких последова- тельностей «покоординатно», причем таблицы сложения и умноже- ния зададим так: + 0 1 0 0 1 1 1 1 × 0 1 0 0 0 1 0 1 логическое сложение логическое умножение Например, (1, 0, 0, 1) + (1, 1, 0, 1) = (1, 1, 0, 1); (1, 0, 0, 1)(1, 1, 0, 1) = (1, 0, 0, 1). Положим, далее, x ⊂ y, где x = (x 1 , . . . , x n ), y = (y 1 , . . . , y n ), если для каждой координаты имеем x k y k . Заменяя в последователь- ности 0 на 1, а 1 на 0, получим новую последовательность, кото- рую обозначим x . Наконец, через ∅ обозначим последовательность (0, 0, . . . , 0), а через I — последовательность (1, 1, . . . , 1). Предостав- ляем читателю проверить выполнение законов 1)–26) для введенных операций над последовательностями. Интересный пример булевой алгебры получается, если рассмот- реть все натуральные делители натурального числа N , которое Булевы алгебры 47 является произведением нескольких различных простых чисел. В качестве операции сложения делителей выберем образование наи- меньшего общего кратного этих делителей, а в качестве операции умножения — образование их наибольшего общего делителя. До- полнением делителя n назовем число n = N n . Наконец, скажем, что n ⊂ m, если m делится на n. Нетрудно проверить, что введенные операции удовлетворяют условиям 1)–26) из пункта «Алгебра мно- жеств», причем роль пустого множества ∅ играет число 1, а роль универсального множества I — число N . Если, например, взять N = 30, то булева алгебра будет состоять из чисел {1, 2, 3, 5, 6, 10, 15, 30}. «Сумма» делителей 2 и 5 равна 10, а их «произведение» равно 1. Делителем, «обратным» делителю 3, является 10, 3 = 10. Наконец, 5 ⊂ 15, так как 15 делится на 5. Глава II. В мире чудес бесконечного Тайны бесконечности Не будет преувеличением сказать, что всю математику пронизы- вает идея бесконечности. Как правило, в математике интересуются не отдельными объектами (числами, геометрическими фигурами), а целыми классами таких объектов: совокупностями всех натураль- ных чисел, всех треугольников и т. д. А такие совокупности состоят из бесчисленного множества отдельных элементов. Поэтому математики и философы всегда интересовались поняти- ем бесконечности. Этот интерес возник с того самого момента, когда стало ясно, что за каждым натуральным числом идет следующее, то есть что числовой ряд бесконечен. Но уже первые попытки изу- чения бесконечности привели к многочисленным парадоксам. Например, греческий философ Зенон, используя понятие беско- нечности, доказывал невозможность движения. В самом деле, го- ворил он, для того чтобы стрела пролетела какой-то путь, сначала она должна сделать половину пути. Но прежде чем сделать полпу- ти, надо пролететь четверть пути, восьмую часть пути и т. д. Так как процесс деления пополам никогда не кончится (вот она, беско- нечность!), то стрела никогда не сможет сдвинуться с места. Точно так же он доказывал, что быстроногий Ахиллес никогда не догонит медлительную черепаху. Из-за таких парадоксов и софизмов древнегреческие математики отказывались иметь дело с бесконечностью, изгоняли ее из матема- тических рассуждений. Некоторые философы считали, что все гео- метрические фигуры состоят из конечного числа мельчайших неде- лимых частиц (атомов). Атомистическая теория легко устраняет па- радоксы Зенона, поскольку в ней не допускается бесконечное деле- ние — делить можно лишь до атомов, далее не делимых. Однако тут возникли новые трудности. Нельзя разделить пополам отрезок, ес- ли он состоит из нечетного числа неделимых (рис. 23). Круг тоже нельзя разделить на две равные части: центр будет принадлежать только одной из частей, а это противоречит их равенству. Тайны бесконечности 49 Ахиллес и черепаха Надо сказать, споры о бесконечности протекали порою довольно остро. Так, известный греческий философ Платон с такой неприми- римостью относился к атомистической теории Демокрита, что по- всюду разыскивал рукописи сочинений этого автора и уничтожал их — до изобретения книгопечатания такой метод идейной борьбы был весьма эффективен. Методы, в которых использовалось понятие бесконечности, поз- волили греческим ученым получить ряд важных результатов, осо- Рис. 23 бенно в геометрии. Однако парадоксы Зено- на приучили их к осторожности. Например, Евклид, формулируя свою знаменитую тео- рему о бесконечности множества простых чисел, выражается так: «Простых чисел существует больше всякого предложенного количества простых чисел». Итак, больше всякого предложенного количества, а бес- конечно много или нет — об этом Евклид умалчивает. Вообще, древние греки с такой тщательностью маскировали применение ме- тодов, в которых существенную роль играло понятие бесконечности, что в XVI–XVII веках европейским математикам пришлось эти ме- тоды переоткрывать. В средние века проблемой бесконечного интересовались главным образом в связи с рассуждениями о том, конечно или нет множество ангелов, которое может поместиться на кончике иглы. Широкое ис- пользование бесконечности в математике началось с XVII века, когда 50 Глава II. В мире чудес бесконечного был создан математический анализ. Такие понятия, как «бесконечно большая величина», «бесконечно малая величина», использовались в математических рассуждениях на каждом шаге. Однако в это вре- мя изучали не множества, содержащие бесконечно много элементов, а величины, которые в процессе своего изменения становятся все больше и больше, так что в конце концов они превосходят любое фиксированное значение. Такие величины называли «потенциально бесконечно большими» в том смысле, что они могут стать как угодно большими (potentia — возможность). |