Введение в теорию множеств. Основные определения, терминология

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

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

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

Определение 3
Множества А и В называются равными, если они состоят из одних и тех же элементов (A=В). Другими словами, обозначение А=В служит сокращением для высказывания
.
Если множество А конечно и состоит из элементов а1,а2,...,аn, то пишем:
А={а1, а2,...,аn}.
Иногда подобное обозначение распространяется и на некоторые бесконечные множества. Так,
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
а) ;
б) ;
в)