ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 10094
Скачиваний: 93
31
является биекцией
}
,
,
2
,
1
{
:
2
1
n
n
X
f
+
→
…
в силу биективности
1
f
и
2
f
.
Следовательно,
2
1
2
1
X
X
n
n
X
+
=
+
=
. Основание индукции доказано.
Шаг 2 . Индукционный переход заключается в следующем: предполо-
жим, что теорема справедлива при числе блоков разбиения
1
−
r
; докажем,
что в этом случае она будет справедлива и при числе блоков r.
Предположение: множества
1
,
2
,
1
,
−
=
r
i
Y
i
…
, конечны и образуют
разбиение множества
Y
. Тогда
.
1
1
1
1
∑
∑
−
=
−
=
=
=
r
i
i
r
i
i
n
Y
Y
Рассмотрим разбиение множества
X
на
r
конечных множеств. Тогда
r
r
r
i
i
X
X
X
X
X
X
∪
∪
∪
∪
=
=
−
=
)
...
(
1
2
1
1
∪
по закону ассоциативности объ-
единения. Обозначим
∪
1
1
.
−
=
=
r
i
i
X
Y
Опираясь на основание индукции (шаг 1),
имеем
r
r
X
Y
X
Y
X
+
=
∪
=
, а по индукционному предположению
.
1
1
1
1
1
∑
∑
=
−
=
−
=
=
+
=
+
=
r
i
i
r
r
i
i
r
r
i
i
X
X
X
X
X
X
∪
Индукционный переход доказан.
Заключение. Согласно методу математической индукции, теорема спра-
ведлива для любого натурального числа
r
блоков разбиения.
Теорема (правило произведения). Пусть конечное множество
X
пред-
ставлено в виде декартова произведения r конечных множеств
r
X
X
X
×
×
×
…
2
1
. Тогда
r
X
X
X
X
⋅
⋅
⋅
=
…
2
1
.
Правило произведения доказывается методом математической индукции
аналогично правилу суммы.
Теорема (правило включения – исключения). Пусть
1
X
и
2
X
конечные
множества. Тогда
2
1
2
1
2
1
X
X
X
X
X
X
∩
−
+
=
∪
.
Доказательство теоремы опирается на правило суммы. Представим мно-
жество
2
1
X
X
∪
в виде объединения непересекающихся множеств
C
B
A
X
X
∪
∪
=
∪
2
1
, где
2
1
\
X
X
A
=
,
2
1
X
X
B
∩
=
,
1
2
\
X
X
C
=
(рис. 1.21). Тогда по правилу суммы
C
B
A
X
X
+
+
=
∪
2
1
, но
C
B
X
B
A
X
∪
=
∪
=
2
1
,
, поэтому
B
A
X
+
=
1
,
C
B
X
+
=
2
. Имеем
C
B
B
A
X
X
+
+
+
=
+
2
1
, отсюда
=
−
+
=
∪
B
X
X
X
X
2
1
2
1
2
1
2
1
X
X
X
X
∩
−
+
.
32
Теорема (обобщенное правило включения – исключения).
Пусть конечное множество X является объединением r конечных мно-
жеств:
∪
r
i
i
X
X
1
.
=
=
Тогда
.
...
)
1
(
...
2
1
1
1
1
1
r
r
n
k
j
i
k
j
i
n
j
i
j
i
r
i
i
X
X
X
X
X
X
X
X
X
X
∩
∩
∩
−
+
−
∩
∩
+
+
∩
−
=
+
≤
<
<
≤
≤
<
≤
=
∑
∑
∑
Теорема (о мощности булеана конечного множества). Пусть множество
X
конечно и
⏐X⏐
=
n
. Тогда
⏐
B
(X)
⏐
=
n
2
.
Напомним, что
B
(X
) есть булеан множества
X
, т.е. множество всех под-
множеств множества
X
(см 1.1.6). Докажем теорему методом математической
индукции по числу
n
элементов множества
X
.
Основание индукции. Проверим правильность теоремы при
n=
1
. Т.к.
множество
X
состоит из одного элемента
}
{
1
x
X
=
, то всех возможных под-
множеств у множества
X
будет два: пустое множество и само множество
X
,
т.е.
⏐
B
(X)
⏐
n
2
2
=
=
.
Индукционный переход. Пусть теорема справедлива при
⏐X⏐
= 1
−
n
.
Рассмотрим произвольное множество
}
,
,
{
2
1
n
x
x
x
X
…
=
и покажем, что
количество всех его подмножеств равно
n
2
.
Покрасим элемент
1
x
множества
X
в “зелубой ” цвет, и все подмноже-
ства множества
X
, содержащие этот элемент, назовем красивыми, а не содер-
жащие этот элемент – некрасивыми. Количество некрасивых подмножеств по
индукционному предположению равно
1
2
−
n
. Красивые подмножества полу-
чены добавлением “зелубого” элемента к каждому некрасивому подмножеству
33
поочередно, значит, их тоже
1
2
−
n
. По правилу суммы количество всех
подмножеств множества
X
равно
n
n
n
n
2
2
2
2
2
1
1
1
=
⋅
=
+
−
−
−
.
Заключение. Согласно методу математической индукции, теорема спра-
ведлива для любого натурального числа
n
.
1.4.7. Определение счетного множества
Будем говорить, что множество
X
счетно, если оно равномощно множе-
ству натуральных чисел
N
.
Пример 1. Пусть
X
множество нечетных натуральных чисел. Покажем,
что
X
счетно. Для этого нужно установить биекцию множества
X
на множе-
ство натуральных чисел, т.е. занумеровать элементы множества
X
так, чтобы
каждому элементу
X
соответствовал ровно один номер, а любому натурально-
му числу соответствовал ровно один элемент из
X
. Очевидно, соответствие
∈
−
=
n
n
f
,
1
2
N
, удовлетворяет этим требованиям:
...}
,
,
...
,
4
,
3
,
2
,
1
{
...}
,
1
2
...,
,
7
,
5
,
3
,
1
{
n
N
n
X
=
−
=
Таким образом,
⏐X⏐
=
⏐
N
⏐
и
X
счетно.
Пример 2. Пусть
X
=
N
×N
– декартово произведение множества
N
на се-
бя. Покажем, что
X
счетно. Расположим все элементы
X
в виде матрицы (рис.
1.22) и занумеруем его элементы “ по диагоналям ”: номер 1 присвоим эле-
менту (1,1), номер 2 – элементу (2,1), 3 – (1,3) и т.д.
Полученное отображение
X
на
N
также является биекцией (хотя записать
формулу в явном виде сложнее, чем в примере 1).
Мощность счетного множества обозначается
ℵ
0
. Когда мы пишем
⏐X⏐
=
ℵ
0
, мы утверждаем, что множество
X
счетно, т.е. относится к тому же
34
классу эквивалентности, что и множество натуральных чисел. А множество
N
считается эталоном (образцом) счетных множеств.
1.4.8. Свойства счетных множеств
Покажем, что класс счетных множеств расположен в ряду мощностей ле-
вее любых других классов бесконечных множеств, а предшествуют ему только
классы конечных множеств (рис. 1.23).
Основой для такого утверждения служат следующие теоремы о счетных
множествах.
Теорема 1. Любое подмножество счетного множества конечно или счет-
но.
Пусть
X
– счетное множество, а
X
Y
⊆
– произвольное его подмноже-
ство. Занумеруем элементы множества
}
,
,
,
{
2
1
…
…
n
x
x
x
X
=
и выберем тот
элемент, который имеет минимальный номер и принадлежит подмножеству
Y
– обозначим его
1
y
. Затем рассмотрим множество
}
{
\
1
y
X
и найдем в нем
элемент с минимальным номером, принадлежащий
Y
, - обозначим
2
y
, и т.д.
Если на
n
-ом шаге мы не обнаружим в множестве
}
,
,
{
\
2
1
n
y
y
y
X
…
элемен-
тов множества
Y
, то
Y
конечно и
⏐Y⏐
=
n
. В противном случае (если процесс
будет продолжаться бесконечно) множество
Y
счетное, т.к. указан способ ну-
мерации его элементов.
Теорема 2. Всякое бесконечное множество имеет счетное подмножество.
Пусть
X
– бесконечное множество. Выберем произвольный элемент
X
x
∈
1
. Так как
X
бесконечно, то
≠
}
{
\
1
x
X
∅
. Обозначим
2
x
произвольный
элемент
из
}
{
\
1
x
X
.
Далее
найдется
},
,
{
\
2
1
3
x
x
X
x
∈
…
},
,
,
{
\
3
2
1
4
x
x
x
X
x
∈
. Поскольку
X
бесконечно, этот процесс не может
оборваться из-за “нехватки” элементов, и мы получим счетное подмножество
Y
множества
X
:
X
x
x
x
Y
⊆
=
}
,
,
,
{
3
2
1
…
.
Теорема 3. Объединение конечного или счетного количества счетных
множеств есть множество счетное.
Пусть
∪
∞
=
=
1
n
n
X
X
, где
…
…
,
,
,
,
2
1
n
X
X
X
- счетные множества. Будем
считать, что они попарно не пересекаются (в противном случае перейдем от
35
множеств
n
X
к множествам
∪
1
1
\
−
=
=
n
k
k
n
n
X
X
Y
, которые попарно не пересе-
каются и
∪
∪
∞
=
∞
=
=
1
1
n
n
n
n
Y
X
). Все элементы множества
X
запишем в виде беско-
нечной таблицы:
…
…
…
…
…
…
…
33
34
31
23
22
21
13
12
11
x
x
x
x
x
x
x
x
x
где в первой строке записаны элементы множества
1
X
, во второй –
2
X
и т.д.
Занумеруем эти элементы “по диагонали” (как в примере 2 из 1.4.7), при этом
устанавливается биекция между множествами
X
и
N
, т.е.
X
– счетное множе-
ство.
Теорема 4. Пусть
X
бесконечное множество, а
Y
– счетное. Тогда
X
Y
X
=
∪
.
Теорема утверждает, что добавление счетного множества элементов не
увеличивает мощность бесконечного множества.
Доказательство. Рассмотрим множество
Y
X
Z
∪
=
и представим его в
виде объединения непересекающихся множеств
,
1
Y
X
Z
∪
=
где
X
Y
Y
\
1
=
.
Так как
Y
счетно, то
1
Y
конечно или счетно (по теореме 1). Множество
X
бес-
конечно, значит, существует счетное подмножество
X
X
⊆
1
(по теореме 2).
Тогда
)
\
(
1
1
X
X
X
X
∪
=
, а
)
(
)
\
(
)
\
(
1
1
1
1
1
1
1
Y
X
X
X
Y
X
X
X
Y
X
Z
∪
∪
=
∪
∪
=
∪
=
.
По
теореме 3
1
1
Y
X
∪
счетно,
т.е
1
1
1
X
Y
X
=
∪
.
Поэтому
X
X
X
X
Z
=
∪
=
1
1
)
\
(
. Теорема доказана.
В примере 1 из 1.4.7 мы установили, что множество
N
равномощно сво-
ему собственному подмножеству. Рассуждения, близкие к доказательству тео-
ремы 4, позволяют утверждать, что таким свойством обладает не только мно-
жество
N
, но любые бесконечные множества.
Рассмотренные четыре теоремы показывают, что среди бесконечных
множеств счетные множества являются наименьшими по мощности. Суще-
ствуют ли множества более чем счетные?