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

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

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

2.

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

3.

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

4.

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

5.

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

6.

Пример 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
Для любых множеств А и В А=В тогда и только тогда, когда
A B и B A
Доказательство
Доказательство этого факта основано на том, что
эквивалентность X Y равносильна конъюнкции двух
импликаций X Y Y X .

7.

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

8.

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

9.

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

3. Разность множеств, дополнение, симметрическая
разность
Определение 1
Разностью множеств называется множество
A \ B x | x A и x B .
Пример
Пусть А={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
Пусть А, В, С – произвольные множества, тогда:
а) A \ A ;
б) A \ B A B ;
в) A B \ C A \ C B \ C ;
г) A \ B C A \ B \ C .
Доказательство
x A\ A x A x A
а) Возьмем
– тождественно
ложное высказывание. Оно равносильно другому
тождественно ложному высказыванию , поэтому A \ A .

19.

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

20.

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

21.

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

22.

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

23.

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