Определение 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
а)
;
б)
;
в)
.
Доказательство
Доказать самостоятельно
Теорема 6 (законы Моргана для дополнений)
а)
;
б)
.
Доказательство
а) Возьмем
.
Необходимо внимательно следить за тем, какая черточка означает отрицание, а какая – теоретико-множественное дополнение.
б) Возьмем
.
Следовательно, .
§4. Декартовы произведения
Под упорядоченной парой (а; b) мы будем понимать двухэлементное множество, состоящее из элементов а и b, в котором зафиксирован порядок расположения элементов. Отметим два характерных свойства упорядоченных пар:
1)
если
;
2)
.
Можно дать и строгое определение упорядоченной пары, но в этом случае, приобретая строгость, оно теряет наглядность.
Определение 1
Упорядоченной парой называется множество (a; b)={{a};{a, b}}.
Теорема 2
Если (a; b)=(x; y), то a=x, b=y.
Доказательство
Из (a; b)=(x; y) следует {{a};{a; b}}={{x};{x; y}}.
Равенство двух двухэлементных множеств возможно лишь при равенстве составляющих их элементов. Здесь возможны два случая:
1) {a}={x}, {a; b}={x; y} или
2) {a}={x, y}, {a; b}={x}.
В первом случае из равенства {a}={x}
следует а=х,
а из второго равенства
и того, что а=х,
следует у=в,
что и требовалось доказать.
Во втором случае из равенства {a}={x, y} следует а=х=у, а из равенства {a; b}={x} следует х=а=в. В частности, а=х и в=у.
Теорема доказана.
Индуктивно определим упорядоченный набор длины n.
Определение 3
1) (a; b)={{a};{a; b}};
2) (a1,a2,...,an,an+1)=((a1,a2,...,an),an+1).
Упорядоченные наборы длины n называются также упорядоченными n-ками, векторами, кортежами.
Теорема 4
.
Доказательство
Индукция по n.
При n=2 это
есть теорема 2. Допустим, утверждение
верно при n=k,
то есть допустим, что из равенства
следует
.
Докажем теорему при n=k+1.
Пусть
.
Это можно переписать по определению
следующим образом:
.
По теореме 2 из равенства пар вытекает
и
.
По индуктивному предположению получаем
.
Определение 5
Декартовым произведением множеств А и В называется множество
.
Пример
Пусть A={1;2}, B={a, b, c}, тогда
{(1;a);(1;b);(1;c);(2;a);(2;b);(2;c)};
а
{(a;1);(b;1);(c;1);(a;2);(b;2);(c;2)}.
Очевидно, что, вообще говоря,
.
Упражнения
1) Доказать, что
.
2) Доказать, что
.
Определение 6
а) Множество
– декартово произведение n множеств;
б)
-
(n cомножителей) –
n-aя
декартова степень множества А;
в)
.
Установим связь между декартовыми произведениями и ранее введенными теоретико-множественными операциями.
Теорема 7
Пусть А, В, С – произвольные множества, тогда
а)
;
б)
;
в)
.
Доказательство
а) Возьмем
.
Следовательно,
.
б) Возьмем
.
Следовательно,
.
в) Возьмем
.
Поскольку в цепочке преобразований не
везде стоят эквивалентности, а в одном
месте стоит всего импликация, мы доказали
включение
.
Необходимо доказать включение в другую
сторону.
Возьмем
.
Следовательно,
.
Теорема 8
Если множество А
состоит из m
элементов, а В –
из n
элементов, тогда А
В
состоит из m
n
элементов.
Доказательство
Доказываем индукцией по числу n-элементов множества В.
При n=1 имеем
,
поэтому
,
то есть A
B
имеет m=m
1
элементов.
Допустим, теорема верна при n=k. И пусть теперь В состоит из к+1 элемента, то есть
,
где
.
Тогда
.
Первое множество
состоит из m
k
элементов по индуктивному предположению,
второе множество
состоит из m
элементов, как отмечалось в базисе
индукции. Кроме того,
,
так как
,
поэтому множество А
В
состоит из mk+m=m(k+1)
элементов, что и требовалось доказать.
§5. Предикаты
Определение 1
а) Множество
называется n-местным
предикатом (отношением) между элементами
множеств А1,А2,...,Аn;
б) Если
,
то мы говорим, что отношение Р
истинно на наборе (a1,a2,...an)
и обозначаем Р(a1,a2,...an)=1
или просто Р(a1,a2,...an),
если же
,
то мы говорим, что P
ложно на наборе (a1,a2,...an)
и пишем Р(a1,a2,...an)=0
или
(a1,a2,...an).
Определение 2
Пусть – n-местный предикат.
а) При n=1
называется одноместным предикатом
или свойством, определенным на
множестве
;
б) при n=2 Р называется двухместным предикатом или бинарным предикатом или просто отношением;
в) если
,
то Р
называется отношением между
элементами множества А.
Примеры
1) Пусть
.
Свойство
определяется условием: Р(х)=1«х –
четное число, тогда
Р={...;-4;-2;0;2;4;...}.
2)
,
определяется условием: Р(х)=1«х –
иррациональное число. Тогда
,
а
.
3)
–
множество всех людей,
определим так:
– мужчина.
4) – множество треугольников на плоскости, – равносторонний треугольник.
Список примеров подобран таким образом, чтобы стало ясно, что одноместные предикаты или свойства присущи элементам самих произвольных множеств.
Задача
Пусть А1 состоит из n элементов. Сколько разных свойств можно определить на А1?
Примеры отношений
1)Пусть
определяется условием:
делится на 3;
2)
определяется условием:
делится на 3;
3)
–
рациональное число. Очевидно, что
,
очевидно также, что
.
Менее очевидно, что
4)
-
рациональное число.
.
5)
где А –
множество людей.
–
муж y.
6)
–
брат у.
7)
,
где F –
множество треугольников,
подобен у.
В дальнейшем мы будем изучать, как правило, 1– и 2– местные предикаты.
На множестве всех бинарных предикатов можно определить две полезные операции.
Определение 3
Пусть
–
бинарный предикат. Тогда предикат
называется обратным к Р,
если для любых
и
.
Обозначим через
следующий бинарный предикат:
.
IA называется диагональным отношением или отношением равенства или просто равенством на множестве А.
Очевидно, что
.
Определение 4
Пусть
–
бинарные предикаты, тогда предикат
определяется следующим условием: для
любых
существует
,
такой, что
.
называется суперпозицией предикатов
Р и Q.
Пример 1
A={1,2,3},B={a, b, c},C={x, y, t};
P={(1;a);(1:c);(2;b);(2;c);(3;a)}A B;
Q={(a; x);(a; y);(b; y);(b; z);(c; x);(c; z)};
={(1;x);(1;y);(1;z);(2;x);(2;y);(2;z);(3;x);(3;y)}=A C\{(3;Z)}.
Пример 2
A={a, b, c, d};
P={(a; a);(a; b);(a; d);(c; a);(c; b);(d; a)},
тогда
={(a;
a);(b; a)'(d; a);(a; c);(b; c);(a; d)}.
Вычислим
:
а)
=
{(a; a);(a; d)};
б)
=
{(a; a);(a; c);(a; d);(c; a);(c; c);(c; d);(d; a);(d; c); (d; d)};
в)
= {(a;
a);(a; b);(a; d);(b; a);(b; b);(b; d);(d; a);(d; b); (d; d)}.
Непосредственно видно, что
,
то есть операция суперпозиции, не
является коммутативной.
Теорема 5
Пусть , тогда
а)
;
б)
.
Доказательство
а) Возьмем
® существует
.
Но
влечет
,
значит
,
то есть
.
Теперь возьмем
,
тогда можно написать
,
то есть существует такое
,
что
,
значит
.
Аналогично доказывается пункт б).
Теорема 6
Пусть
и
,
тогда
.
Доказательство
Возьмем
существует , такой, что
.
Теорема 7
Пусть
тогда
–
ассоциативность суперпозиции.
Доказательство
Возьмем
существует
,
такой, что
существует
,
такой, что
.
Значит, .
§6. Отношение эквивалентности
Определение 1
Отношение
называется отношением эквивалентности,
если выполняются три аксиомы:
а) для любого
–
рефлексивность;
б) для любых
–
симметричность;
в) для любых
–
транзитивность.
Пример 1
определяется условием:
делится на 3.
Проверка выполняется для всех трех
аксиом.
а)
делится на 3,
следовательно,
.
б) Пусть
,
то есть
делится на 3,
значит, и
также делится на 3,
значит,
.
в) Пусть
,
,
следовательно,
делится на 3
и
делится на 3,
тогда
тоже делится на 3,
то есть
.
Пример 2
Пусть
определяется следующим условием:
делится на 3.
Данное отношение не является отношением
эквивалентности, так как нарушается
уже первая аксиома – рефлексивность,
так как не для любого
делится на 3.
Достаточно взять
.
Отметим кстати, что остальные две
аксиомы – симметричность и
транзитивность – выполняются.
Проверьте это самостоятельно.
Пример 3
определяется условием
.
а) Так как для любого
,
значит,
.
б) Пусть
,
то есть
,
значит,
,
то есть
.
Симметричность выполняется.
в) Пусть
и
,
значит,
и
,
следовательно,
,
поэтому
.
Транзитивность выполняется.
Пример 4
Пусть
–
множество мужчин,
определяется условием
–
брат y. Если
договориться, что мужчина сам себе
является братом, то
является отношением эквивалентности,
так как симметричность и транзитивность
выполняется очевидным образом.
Если договорится для отношения
эквивалентности
вместо
писать
~
,
то аксиомы этого отношения перепишутся
более простым и обычным образом:
а) для любого
~
;
б) для любых
~
~
;
в) для любых
~
~
~
.
Задача
Докажите, что эти условия равносильны следующим отношениям:
а)
;
б)
;
в)
.
Определение 2
Пусть задана система множеств
,
тогда:
а)
;
б)
.
Очевидно, что объединение и пересечение
конечного числа множеств, например, n,
является частным случаем этих определений,
когда индексное множество
.
Определение 3
Система множеств
называется разбиением множества
,
если
а)
;
б) для любых
.
Другими словами, различные множества
из системы
не пересекаются.
Определение 4
Пусть
–
отношение эквивалентности на
.
Классом эквивалентности, порожденным
элементом
,
называется множество
.
Теорема 5
Если – отношение эквивалентности на , то множество классов эквивалентности образуют разбиение .
Доказательство
Докажем вначале
.
Так как
для любого
,
то включение
очевидно. Возьмем
.
Так как
,
то
,
значит
,
то есть
,
значит и
.
Пусть
,
значит существует
,
то есть
и
.
По транзитивности
.
Теперь докажем, что
.
Возьмем
.
Если же
.
Таким образом,
.
Итак, мы доказали, что любое отношение эквивалентности на множестве порождает естественным образом разбиение на классы эквивалентности. Оказывается, имеет место и обратное утверждение.