2.4. Дополнение множеств. Мощность множеств

 

          В математической литературе разность множеств В\А иногда называют дополнением множества А до множества В. Если в некоторых рассуждениях участвуют только подмножества самого большого, универсального множества I,  то разность I\А называется дополнением множества А до множества I или просто дополнением множества А и обозначается  (или , или ). Т.е. в дополнение множества А входят все элементы, не принадлежащие А. Например, если мы рассматриваем множества студентов, описываемых различными признаками: юноши и девушки, отличники, «двоечники» и т.д., то универсальным множеством будет множество всех студентов, а дополнением до множества девушек – множество студентов-юношей.

          Если универсальное множество не указано или оно не ясно из контекста, то говорить о дополнении множества А недопустимо.

          На диаграммах Эйлера универсальное множество I  изображается множеством точек некоторого прямоугольника, а его подмножества – в виде кругов внутри этого прямоугольника. Дополнение множества А будет изображено в таком случае той частью прямоугольника, которая лежит за пределами круга (заштрихованная часть рис.2.11).

Рис.2.11

          Для любых подмножеств А и В универсального множества I справедливы следующие утверждения:

1)           =А;

2)           = I ,                      = Æ;

3)           ,    – законы де Моргана;

4)           АÈ(АÇB)=А,    АÇ(АÈB)=А – законы поглощения;

5)           АÇ = Æ,            АÈ = I ;

6)           АÈÆ = А,             АÇI  = А;     

7)           АÇÆ = Æ,            АÈI  = I .

Можно заметить, что утверждения 2) – 6) обладают замечательным свойством: если в одном из этих утверждений заменить Æ  на I , È на  Ç и наоборот, то в результате получим утверждение парное ему. Это свойство называется принципом двойственности. Принцип двойственности помогает значительно упрощать запись некоторых выражений и применяется во многих математических разделах (например, в алгебре высказываний, которая будет рассмотрена далее).

Рассмотрим вопрос относительно числа элементов множества. В случае непустого конечного множества А мы можем пересчитать элементы множества, закрепив за каждым элементом соответствующий номер 1, 2, 3, …, n. Тогда элементы множества предстанут в занумерованном виде: , , , …, . Номер последнего элемента и означает число элементов множества А. Элементы конечного множества, содержащего более одного элемента, можно занумеровать разными способами. Но последнему элементу мы всегда поставим в соответствие один и тот же номер n, число элементов множества не зависит от способа нумерации его элементов. Значит число n, соответствующее количеству элементов множества А={, , , …, }, будет количественной характеристикой этого множества. Число элементов конечного множества будем обозначать через N(A).  Число элементов пустого множества Æ равно нулю: N (Æ)=0.

Пусть существует два конечных множества А и В, количество элементов которых N(A) и N(В).  Тогда

N(АÈВ)= N(A)+N(В) –N(АÇВ).                                   (2.4)

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

         Действительно, количество элементов, составляющих общую для множеств А и В часть - АÇВ, входит в сумму N(A)+N(В) дважды и его необходимо вычесть для получения числа элементов обоих множеств N(АÈВ).

         Из (2.4) следует, что если множества А и В не пересекаются, то

N(АÈВ)= N(A)+N(В).

         Для пересекающихся множеств А и В

N(АÈВ) < N(A)+N(В).

         Для трех множеств А , В и С формула включений и исключений выглядит следующим образом:

N(A) + N(В) + N(С) – N(АÇВ) – N(BÇC) – N(АÇC) + N(АÇВÇC).

         Для любых множеств А , В и С:

N(A) + N(В) + N(С).

         N(A) + N(В) + N(С) только если множества А , В и С попарно не пересекаются.

         В том случае, когда универсальное для рассматриваемых подмножеств множество I также является конечным, то

N(I) – N(А);

N(I) – N(АÈВ)= N(I) – N(A) – N(В) + N(АÇВ).

         Аналогично для трех множеств А , В и С:

 N(I) – N(A) –N(В) –N(С) + N(АÇВ)+ N(BÇC)+ N(АÇC)-N(АÇВÇC).

         Пример 2.5.  В 101 группе – 29 студентов. Каждый из них изучает или английский, или немецкий язык. 5 студентов изучает и английский, и немецкий одновременно. Сколько студентов занимаются в английской группе, если в немецкой – 12 студентов.

         Обозначим через А множество студентов, изучающих английский язык, а через В – немецкий язык. Количество студентов в немецкой группе –  N(В)=12. Множество студентов, изучающих одновременно и английский,  и немецкий – АÇВ. N(АÇВ)=5. Всего студентов N(АÈВ)=29. Значит количество студентов в английской группе по формуле (2.4) можно найти так:

N(A) = N(АÈВ)–N(В)+N(АÇВ) = 29–12+5 = 22.

Пример 2.6. Задача Льюиса Керрола.  В одной из повестей Льюиса Керрола – автора «Алисы в стране чудес», «Алисы в зазеркалье» и др. – есть такая задача: «В ожесточенном бою 70 из 100 пиратов потеряли один глаз, 75 – одно ухо, 80 – одну руку и 85 одну ногу. Каково минимальное количество потерявших одновременно глаз, ухо, руку и ногу?»

Обозначим через А – множество пиратов, потерявших один глаз, через В – одно ухо, через С – одну руку, через D – одну ногу. Тогда множество потерявших и глаз, и ухо, и руку, и ногу одновременно – АÇВÇСÇD. Универсальное множество I можно представить в виде: I=() È (АÇВÇСÇD). По закону Моргана =ÈÈÈ. (На рис. 2.12 множество АÇВÇСÇD выделено на диаграмме темно-серым цветом, множество ÈÈÈ  – светло-серым).

Рис. 2.12

         Так как множества ÈÈÈ и АÇВÇСÇD не пересекаются, то N(I)= N(ÈÈÈ)+N(АÇВÇСÇD). Множества , ,  и  могут попарно пересекаться. Значит N(ÈÈÈ)£N()+N()+N()+N().  N()=N(I) – N(A) = 100 – 70 = 30, N()=N(I) – N(В) = 100 – 75 = 25, N()=N(I) – N(С) = 100 – 80 = 20, N()=N(I) – N(D) = 100 – 85 = 15. Таким образом, N(I) £ N()+N()+N()+N()+N(АÇВÇСÇD), а N(АÇВÇСÇD)³N(I)–N()–N()–N()–N()=100 – 30 – 25 – 20 – 15=10.

         Итак N(АÇВÇСÇD)³10, т.е. не менее 10 пиратов одновременно лишились и глаза, и уха, и руки, и ноги.

Рассмотрим два конечных множества А и В. Если они имеют одинаковое количество элементов, то они называются равночисленными. В противном случае множества А и В неравночисленны.

         Оказывается, для того чтобы установить равночисленность или неравночисленность двух множеств, не всегда нужно подсчитывать количество их элементов. Например, для сравнения численности множеств юношей и девушек в аудитории, можно не подсчитывать количество элементов в каждом множестве, а каждому юноше поставить в пару девушку. Теперь, если каждому юноше будет поставлена в пару девушка и не останется ни одной свободной девушки, значит, количества юношей и девушек одинаковы. Если останутся без пары юноши, значит количество девушек меньше, чем юношей; если останутся без пары девушки, значит их количество больше. В первом случае множества юношей и девушек равночисленны, в двух последних – неравночисленны.

         Если каждому элементу множества А можно по некоторому правилу поставить в соответствие один и только один элемент множества В и, наоборот, каждому элементу множества В по некоторому правилу можно поставить в соответствие один и только один элемент множества А, то говорят, что между элементами множеств А и В установлено взаимно-однозначное соответствие. В  этом случае множества А и В называют эквивалентными и записывают: А~B.

         Очевидно, что равночисленные множества эквивалентны. И, наоборот, два эквивалентных конечных множества равночисленны.

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

         Рассмотрим теперь бесконечные множества. Для сравнения бесконечных множеств нельзя использовать понятие натурального числа, ибо нельзя пересчитать все элементы таких множеств и поставить им в соответствие натуральное число. Однако их можно сравнивать при помощи понятий «взаимно-однозначное соответствие», «эквивалентность».

         Множество, эквивалентное множеству всех натуральных чисел, называется счетным множеством. Например, между множествами N={1, 2, 3, …, n, …} и  A={-1, -2, -3, …, -n, …} можно установить взаимно-однозначное соответствие. Значит А~N и множество целых отрицательных чисел является счетным.

         Если для конечных эквивалентных множеств мы говорили, что они равночисленны, то о бесконечных множествах будем говорить, что они равномощны, т.е. имеют одинаковую мощность. Все эквивалентные бесконечные множества характеризуются их мощностью.

         Понятие мощности бесконечного множества аналогично понятию числа конечного множества. Мощность – обобщение понятия «количество» для бесконечных множеств. Оно позволяет сравнивать различные бесконечные множества.

Предыдущая | Главная | Глава 2 | Следующая