Лекции и упражнения

1.2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ
13
1.2.2 Индикаторная функция.
Для получения тождеств в теории множеств часто используется следующее
понятие:
Определение 9. Индикаторной функцией (индикатором) множе-
ства
A
называется функция
I
A
:
M
? {
0
,
1
}
заданная следующим образом:
I
A
(
x
) =
(
1
,
x
?
A
0
,
x
6?
A
, т.е. функция, равная единице на элементах множества
A
и нулю на всех остальных элементах объемлющего множества
M
.
Очевидно, что множества равны тогда и только тогда, когда их индика-
торные функции равны при всех
x
.
Свойства индикаторной функции:
1.
I
A
?
I
B
?
A
=
B
;
2.
|
A
|
=
P
x
?
M
I
A
(
x
)
;
3.
I
Ї
A
(
x
) = 1
?
I
A
(
x
)
;
4.
I
A
?
B
(
x
) =
I
A
(
x
)
·
I
B
(
x
)
;
5.
I
A
?
B
(
x
) =
I
A
(
x
) +
I
B
(
x
)
?
I
A
(
x
)
·
I
B
(
x
)
;
6.
I
A
\
B
(
x
) =
I
A
(
x
)
?
I
A
(
x
)
·
I
B
(
x
)
;
7.
I
A
4
B
(
x
) =
I
A
(
x
) +
I
B
(
x
)
?
2
·
I
A
(
x
)
·
I
B
(
x
)
;
8.
B
?
A
, тогда и только тогда, когда
f orallxI
B
(
x
)
6
I
A
(
x
)
.
С помощью индикаторной функции можно доказывать различные тож-
дества. Например, докажем тождество 12 из раздела 1.2.1:
A
4
B
= (
A
\
B
)
?
(
B
\
A
)
.
Запишем индикаторные функции для левой и правой части тождества:
f
1
(
x
) =
I
A
4
B
(
x
) =
I
A
(
x
) +
I
B
(
x
)
?
2
·
I
A
(
x
)
·
I
B
(
x
)
 по свойству 7;
f
2
(
x
) =
=
I
(
A
\
B
)
?
(
B
\
A
)
(
x
) =
I
(
A
\
B
)
(
x
) +
I
(
B
\
A
)
(
x
)
?
I
(
A
\
B
)
(
x
)
·
I
(
B
\
A
)
(
x
) =
I
A
(
x
)
?
?
I
A
(
x
)
·
I
B
(
x
)+
I
B
(
x
)
?
I
B
(
x
)
·
I
A
(
x
)
 по свойствам 5 и 6. Поскольку
f
1
?
f
2
,
то множества тоже равны.
1.2.3 Формула включений-исключений
Теорема 1. [Формула включенийисключений] Будем обозначать
|
A
|
 ко-
личество элементов множества
A
. Тогда для произвольных множеств
A
1
,...
A
n
верна формула:
|
A
1
?
. . .
?
A
n
|
=
X
1
?
i
?
n
|
A
i
| ?
X
1
?
i?
n
|
A
i
?
A
j
|
+
+
X
1
?
i?
n
|
A
i
?
A
j
?
A
k
| ?
. . .
+ (
?
1)
n
?
1
|
A
1
?
A
2
?
. . .
?
A
n
|
.

14
ГЛАВА 1. ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВ.
В частности, при
n
= 2
,
3
верны формулы:
|
A
?
B
|
=
|
A
|
+
|
B
| ? |
A
?
B
|
;
|
A
?
B
?
C
|
=
|
A
|
+
|
B
|
+
|
C
| ? |
A
?
B
| ? |
A
?
C
| ? |
B
?
C
|
+
|
A
?
B
?
C
|
.
Доказательство.
Из свойств 10-11 операций со множеcтвами следует, что
A
1
?
. . .
?
A
n
= Ї
A
1
?
. . .
?
Ї
A
n
.
Поэтому для индикатора множества
A
1
?
. . .
?
A
n
выполнено
I
A
1
?
...
?
A
n
= 1
?
n
Y
i
=1
(1
?
I
A
i
)
.
Раскрыв скобки и сократив получим,
I
A
1
?
...
?
A
n
=
X
1
?
i
?
n
I
A
i
?
X
1
?
i?
n
I
A
i
·
I
A
j
+
+
X
1
?
i?
n
I
A
i
·
I
A
j
·
I
A
k
?
. . .
+ (
?
1)
n
?
1
I
A
1
·
I
A
2
·
. . .
·
I
A
n
.
Просуммируем по
x
?
M
, получим:
|
A
1
?
. . .
?
A
n
|
=
X
x
?
M
I
A
1
?
...
?
A
n
(
x
) =
=
X
x
?
M
X
1
6
i
6
n
I
A
i
(
x
)
?
X
x
?
M
X
1
6
i6
n
I
A
i
(
x
)
·
I
A
j
(
x
)+
+
X
x
?
M
X
1
6
i6
n
I
A
i
(
x
)
·
I
A
j
(
x
)
·
I
A
k
(
x
)
?
. . .
. . .
+
X
x
?
M
(
?
1)
n
?
1
I
A
1
(
x
)
·
I
A
2
(
x
)
·
. . .
·
I
A
n
(
x
) =
=
X
1
6
i
6
n
|
A
i
| ?
X
1
6
i6
n
|
A
i
?
A
j
|
+
+
X
1
6
i6
n
|
A
i
?
A
j
?
A
k
| ?
. . .
+ (
?
1)
n
?
1
|
A
1
?
A
2
?
. . .
?
A
n
|
.
Пример 3. Из 100 студентов университета английский язык знают 28
студентов, немецкий  30, французский  42, английский и немецкий  8,
английский и французский  10, немецкий и французский  5, все три язы-
ка знают 3 студента. Сколько студентов не знают ни одного из трех
языков?

1.3. ПАРАДОКС РАССЕЛА
15
Решение. Обозначим все множество студентов буквой
M
, изучающих
английский язык  буквой
E
, немецкий 
D
и французский 
F
. Тогда усло-
вие можно переформулировать на языке теории множестве: Дано
|
M
|
= 100
,
|
E
|
= 28
,
|
D
|
= 30
,
|
F
|
= 42
,
|
E
?
D
|
= 8
,
|
E
?
F
|
= 10
,
|
D
?
F
|
= 5
и
|
E
?
D
?
F
|
= 3
. Надо найти
|
M
\
(
E
?
D
?
F
)
|
. Применим формулу
включений-исключений:
|
E
?
D
?
F
|
= 28 + 30 + 42
?
8
?
10
?
5 + 3 = 80
,
следовательно
|
M
\
(
E
?
D
?
F
)
|
= 20
. Ответ: 20 студентов.
Пример 4. На кафтане площадью 1 размещены 5 заплат, площадь каж-
дой из которых не меньше
1
2
. Докажите, что найдутся две заплаты, пло-
щадь общей части которых не меньше
1
5
.
Решение. Суммарная площадь всех заплат равна
5
2
. Пусть
S
k
 пло-
щадь, покрытая ровно
k
заплатами, тогда
S
0
+
S
1
+
S
2
+
S
3
+
S
4
+
S
5
= 1
и
S
1
+ 2
S
2
+ 3
S
3
+ 4
S
4
+ 5
S
5
=
5
2
.
Сумма площадей всех 10 попарных пересечений заплат равна
S
2
+ 3
S
3
+
+6
S
4
+10
S
5
>
2(
S
1
+2
S
2
+3
S
3
+4
S
4
+5
S
5
)
?
3(
S
0
+
S
1
+
S
2
+
S
3
+
S
4
+
S
5
) = 2
,
поэтому хотя бы одно из 10 попарных пересечений заплат будет по площади
не меньше
2
10
=
1
5
.
1.3 Парадокс Рассела
Для начала напомню одну старую загадку:
Парадокс брадобрея
В некотором селе живет брадобрей, который бреет тех и только
тех жителей, которые не бреются сами. Бреет ли он себя?
У этой загадки нет решения, т.к. условие противоречиво. Действительно,
если предположить, что брадобрей бреет себя, то оказывается, что он входит
в множество тех, кто бреет себя сам, следовательно не должен брить себя.
Если же он не бреет себя сам, то должен себя брить. В любом случае
получаем противоречие.
Аналогичный парадокс был сформулирован выдающимся британским
математиком Бертраном Расселом в 1901 году:
Предположим, что существует множество всех множеств. Тогда
некоторые его элементы являются членами самих себя (напри-
мер, множество всех множеств), а некоторые  нет (например
N
). Рассмотрим
A
 множество всех множеств, которые не яв-
ляются элементами себя. Вопрос: принадлежит ли
A
множеству
A
?
Если допустить, что
A
?
A
, то получается, что
A
не удовлетворяет условию,
что множество не должно быть своим членом, а значит не должно принад-
лежать
A
. C другой стороны, если
A
6?
A
, то оно удовлетворяет условию
отбора, значит должно принадлежать
A
. В обоих случаях приходим к про-
тиворечию.

16

жүктеу/скачать 1,95 Mb.

Достарыңызбен бөлісу: