Введение в теорию множеств 1. Основные определения, терминология Под множеством А мы понимаем совокупность объектов произвольной природы, объединенных общим свойством Р(х). Обозначение. Читается: "А есть множество х, таких, что Р(х)". Пример 1. Легко заметить, что множество состоит из двух чисел: 1 и 2.

Определение 1 Множество А называется подмножеством В, если для любого х ( ) Обозначение: Другими словами, символ " " есть сокращение для высказывания Теорема 2 Для любых множеств А, В, С верно следующее: а) ; б) и.

Доказательство Для доказательства а) надо убедиться в истинности высказывания, но оно очевидным образом истинно, так как представляет собой импликацию, в которой посылка и заключение совпадают. Для доказательства б) надо убедится в истинности высказывания Обозначим: " " через U, " " через V, " " через. Тогда надо убедиться в истинности высказывания. Упростим это высказывание:

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

Определение 3 Множества А и В называются равными, если они состоят из одних и тех же элементов (A=В). Другими словами, обозначение А=В служит сокращением для высказывания. Если множество А конечно и состоит из элементов а 1,а 2,...,an, то пишем: А={а 1, а 2,...,an}. Иногда подобное обозначение распространяется и на некоторые бесконечные множества. Так, N={1,2,3,...,n,...} Z={...,-n,...,-2,-1,0,1,2,...,n,...}. Вопрос Можно ли подобным образом записать множество Q рациональных чисел? А множество R вещественных чисел? Вернемся к определению равенства множеств

Пример 1 {a, b, c, d} = {c, d, a, b}. Пример 2 {a, b, c, d} {a, c, b}. Пример 3 {x|x2-3x+2=0} = {1,2}. Теорема 4 Для любых множеств А и В А=В тогда и только тогда, когда и Доказательство Доказательство этого факта основано на том, что эквивалентность равносильна конъюнкции двух импликаций.

Таким образом, для того, чтобы доказать равенство множеств А и В, надо доказать два включения: и, что часто используется для доказательства теоретико-множественных равенств. Определение 5 тогда и только тогда, когда и. Теорема 6 Для любых множеств А, В, С, если и, то Доказательство Доказать самостоятельно. Определение 7 Множество называется пустым, если оно не содержит ни одного элемента, то есть х не принадлежит этому множеству (для любого х). Обозначение:.

Отметим, что понятия элемента и множества довольно условны. Один и тот же объект в одной ситуации может выступать как элемент, а в другой – как множество. Например, N, Z, Q, R – числовые множества, но в множестве А={N, Z, Q, R} каждое из них является элементом четырехэлементного множества А. В этом отношении достаточно привлекательным является множество. Отметим, что и одновременно. В связи с этим возникает следующая Задача 1 Существует ли объект, такой, что ?

2. Операции объединения и пересечения Определение 1 Объединением двух множеств А и В называется множество. Другими словами, (теоретико- множественной операции "объединение" соответствует логическая операция "или"). Пример Пусть А={1,2,3,4}, B={2,4,6,8}, тогда = {1,2,3,4,6,8}. Теорема 2 Пусть А, В, С – произвольные множества. Тогда: а) – идемпотентность объединения; б) – коммутативность объединения; в) – ассоциативность объединения; г) ; д)

Доказательство а) Возьмем. При последнем переходе мы воспользовались идемпотентностью дизъюнкции. Таким образом, идемпотентность объединения в теории множеств есть следствие идемпотентности дизъюнкции в алгебре высказываний. б) Возьмем Мы доказали, что. Следовательно,. в) Возьмем (ассоциативность дизъюнкции). Мы доказали, что

Следовательно,. г) Возьмем, так как высказывание тождественно ложно. Следовательно,. д) Если, то. В другую сторону. Пусть То есть,. Значит высказывание является тождественно ложным. С другой стороны,, а дизъюнкция двух высказываний ложна тогда и только тогда, когда ложны оба эти высказывания. Следовательно, и а значит.

Теорема 3 Пусть А, В – произвольные множества, тогда: а) ; б). Доказательство а) Возьмем (свойство импликации). Итак,. б) Пусть. Докажем, что. Возьмем. Итак, мы доказали, что, то есть. Теперь пусть. Чтобы доказать равенство, надо доказать два включения: и. Первое включение – есть пункт а).

Докажем второе включение. Возьмем, так как,. Следовательно,. Теорема доказана. Определение 4 Пересечением множеств А и В называется множество. Пример Пусть A={1,2,4,7,8,9}, B={1,3,5,7,8,10}, тогда.

Теорема 5 Пусть А, В, С – произвольные множества, тогда: а) - идемпотентность пересечения; б) - коммутативность пересечения; в) - ассоциативность пересечения; г). Доказательство а) Возьмем. Следовательно,. б) Возьмем.

Следовательно,. в) Возьмем Следовательно,. г), так как – тождественно ложное высказывание. Теорема 6 Пусть А, В – произвольные множества. Тогда: а) ;

б). Доказательство а) Возьмем, то есть. б) Пусть. Возьмем, то есть. Теперь пусть. Включение уже доказано. Докажем включение в другую сторону. Возьмем, так как,. Следовательно,, поэтому.

Теорема 7 (дистрибутивные законы) Пусть А, В, С – произвольные множества, тогда: а) – дистрибутивность пересечения относительно объединения; б) – дистрибутивность объединения относительно пересечения. Доказательство а) Возьмем

3. Разность множеств, дополнение, симметрическая разность Определение 1 Разностью множеств называется множество. Пример Пусть А={1,3,4,7,8,9,10}, B={2,3,4,5,6,7}, тогда A\B={1,8,9,10}, B\A={2,5,6}. Теорема 2 Пусть А, В, С – произвольные множества, тогда: а) ; б) ; в) ; г). Доказательство а) Возьмем – тождественно ложное высказывание. Оно равносильно другому тождественно ложному высказыванию, поэтому.

б) Пусть. Возьмем, так как, то, значит, то есть. Теперь пусть. Возьмем, то есть. в) Возьмем г) Возьмем

Теорема 3 (законы Моргана) а) ; б). Доказательство а) Возьмем

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

Довольно часто под универсальным множеством понимают множество R –– множество вещественных чисел или множество С – комплексных чисел. Возможны и другие примеры. Всегда в контексте необходимо оговорить, что мы понимаем под универсальным множеством U. Определение 4 Пусть U – универсальное множество и. Дополнением А в U (или просто дополнением А) называется множество. Пример Если U – множество вещественных чисел и А – множество рациональных чисел, то – множество иррациональных чисел Теорема 5 а) ; б) ; в)

Доказательство Доказать самостоятельно Теорема 6 (законы Моргана для дополнений) а) ; б).