Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

1.3. НАТУРАЛЬНЫЕ ЧИСЛА. ПРИНЦИП МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ
25
Определим по индукции операции сложения a + b и умножения a · b
на натуральных числах. Положим a+0 ­ a (базис индукции). Если известно значение a+n, то a+n
0
­ (a+n)
0
(индукционный шаг). Аналогично a·0 ­ 0.
Если задано a · n, то a · n
0
­ (a · n) + a.
Используя операцию сложения, можно ввести отношение 6 на множестве натуральных чисел: a 6 b ⇔ ∃ c(a + c = b).
Определим по индукции функцию
n!
(n-факториал):
0! ­ 1,
(n + 1)! ­ n! · (n + 1).
Пример 1.3.1. Докажем по индукции неравенство Бернулли:
(1 + a)
n
> 1 + an
для всех n ∈ N и a > −1, a ∈ R.
При n = 0 неравенство имеет вид (1 + a)
0
> 1 + a · 0 и оно справедливо,
т. е. базис индукции выполняется. Установим справедливость индукционного шага. Предположим, что
(1 + a)
n
> 1 + an,
(1.1)
и покажем, что
(1 + a)
n+1
> 1 + a(n + 1).
(1.2)
Умножим обе части неравенства (1.1) на положительное число 1 + a. Тогда
(1 + a)
n
(1 + a) > (1 + an)(1 + a), т. е.
(1 + a)
n+1
> 1 + a + an + a
2
n.
(1.3)
Поскольку a
2
> 0, имеем
1 + a + an + a
2
n > 1 + a + an = 1 + a(n + 1).
(1.4)
Из неравенств (1.3) и (1.4) получаем неравенство (1.2). На основании принципа математической индукции заключаем, что (1 + a)
n
> 1 + an для всех n ∈ N. ¤
Иногда удается установить только выполнение P (k) для некоторого k > 0
и свойство P (n) ⇒ P (n + 1) для всех n > k. Тогда по принципу математи- ческой индукции свойство P выполняется для всех n > k:
P (k), ∀n > k (P (n) ⇒ P (n + 1))
∀n > k P (n)
.

26
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Другой эквивалентной формой принципа математической индукции яв- ляется принцип полной индукции:
если для всякого n ∈ N из предположения, что P (k) верно при любом натуральном k < n, следует, что P (k) верно также при k = n, то P (n) верно при любом натуральном n:
∀n ((∀k < n P (k)) ⇒ P (n))
∀n P (n)
.
Эта форма используется в том случае, когда для доказательства вы- полнимости P (n + 1) необходимо использовать выполнимость свойства P
не только на элементе n, но и на некоторых предыдущих элементах.
§ 1.4.
Мощность множества.
Конечные и бесконечные множества
Понятие мощности возникает при сравнении множеств по числу элемен- тов.
Множества A и B называются эквивалентными (обозначается A ∼ B),
если существует биекция f : A ↔ B.
Отметим, что для любых множеств A, B, C выполняются следующие свойства:
1) A ∼ A (поскольку id
A
: A ↔ A);
2) если A ∼ B, то B ∼ A (так как из f : A ↔ B следует f
−1
: B ↔ A);
3) если A ∼ B и B ∼ C, то A ∼ C (так как из f : A ↔ B, g: B ↔ C
следует f ◦ g: A ↔ C).
Мощностью множества A называется класс всех множеств, эквивалент- ных множеству A (обозначается |A|). Эквивалентные множества A и B на- зываются равномощными: |A| = |B|. Если A ∼ n для некоторого n ∈ ω,
т. е. A имеет ровно n элементов, то множество A называется конечным.
В этом случае пишут |A| = n. Таким образом, мощностью конечного множе- ства является число его элементов.
Множество, не являющееся конечным, называется бесконечным. Если
A ∼ ω, то множество A называется счетным: |A| = ω. Если A ∼ 2
ω
, то мно- жество A называется континуальным или континуумом: |A| = 2
ω
На мощность множества A можно смотреть и как на новый объект, на- зываемый кардинальным числом или кардиналом. В качестве примеров кар- диналов можно взять любое натуральное число n, а также ω, 2
ω
, 2 2
ω
и т. д.

1.4. МОЩНОСТЬ МНОЖЕСТВА
27
Эти числа можно рассматривать как имена, обозначающие соответствую- щие мощности. Кардинальным числом конечного множества служит число его элементов.
Существование биекции между двумя эквивалентными множествами поз- воляет переносить изучение свойств с одного множества на другое, когда природа элементов не важна. Например, если |A| = n, то с элементами мно- жества A можно работать как с числами 0, 1, 2, . . . , n − 1, которые являются элементами множества n.
Говорят, что мощность множества A не превосходит мощности множе- ства B, и пишут |A| 6 |B|, если A эквивалентно некоторому подмножеству множества B. Мощность множества A меньше мощности множества B (обо- значается |A| < |B|), если |A| 6 |B| и |A| 6= |B|.
Теорема 1.4.1 (теорема Кантора—Бернштейна).
Если
|A| 6 |B|
и |B| 6 |A|, то |A| = |B|.
Доказательство. Пусть f : A → B, g: B → A — разнозначные отоб- ражения, A
0
= A, A
1
= g(B) и A
n+2
= (f ◦ g)(A
n
). Индукцией по n легко доказать, что A
n+1
⊆ A
n
, n ∈ ω. Пусть D = ∩
k∈ω
A
k
и M
i
= A
i
\A
i+1
. Очевидно,
что A
k
=
µ
∪
k6i∈ω
M
i
¶
∪ D и M
i
∩ M
j
= ∅ при i 6= j. Так как f ◦ g разнознач- но отображает M
i
на M
i+2
для любого i ∈ ω, то отображение h: A → A,
определенное следующим образом:
h(a) =





a,
если a ∈
µ
∪
i∈ω
M
2i+1
¶
∪ D,
(f ◦ g)(a),
если a ∈ ∪
i∈ω
M
2i
,
является разнозначным отображением A на A
1
=
µ
∪
16i∈ω
M
i
¶
∪ D. Так как
|B| = |A
1
|, то |B| = |A|. ¤
Следствие 1.4.2 (теорема о сравнении множеств). Для любых мно-
жеств A и B существует одна и только одна из следующих возможно-
стей: |A| = |B|, |A| < |B|, |B| < |A|. ¤
Определим на кардинальных числах операции сложения, умножения
и возведения в степень. Если |A| = α, |B| = β, то α + β ­ |A ∪ B|,

28
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
где A ∩ B = ∅; α · β ­ |A × B|; α
β
­ |A
B
|. В случаях, когда α, β ∈ ω, вве- денные таким образом операции совпадают с обычными операциями на на- туральных числах. Для конечных кардиналов справедливы следующие три правила, используемые в комбинаторике.
Правило суммы. Если |A| = m, |B| = n, то |A ∪ B| = m + n − |A ∩ B|,
и |A ∪ B| = m + n в том и только том случае, когда A ∩ B = ∅.
Правило произведения. Если |A| = m, |B| = n, то |A × B| = m · n.
Правило степени. Если |A| = m, |B| = n, то |A
B
| = m
n
Следующее утверждение показывает, что операции на бесконечных кар- диналах могут иметь “необычные” свойства.
Предложение 1.4.3. ω
2
∼ ω.
Доказательство. По определению множество ω
2
= ω × ω равно
{(m, n) | m, n ∈ ω}. На координатной плоскости изобразим точки с нату-
6
-
•
•
•
•
•
•
•
•
•
•
@
@
@
@
@
R
@
@
@
@
@
R
@
@
@
@
@
R
@
@
@
@
@
R
@
@
@
@
@
R
@
@
@
@
@
R
@
@
@
@
@
R
(0, 0)
(0, 1)
(0, 2)
(0, 3)
(1, 0)
(2, 0)
(3, 0)
(1, 1)
(1, 2)
(2, 1)
0 1
3 6
2 5
9 4
7 8
Рис. 1.7
ральными координатами
(m, n)
(рис. 1.7).
Очевидно, что все эти точки рас- положены в первой четверти. Для доказательства утверждения требу- ется установить биекцию меж- ду множеством натуральных чисел и полученными точками, т. е. пере- нумеровать точки. Нумеруем точки
“по диагонали”: 0 7→ (0, 0), 1 7→ (0, 1),
2 7→ (1, 0), 3 7→ (0, 2), 4 7→ (1, 1),
5 7→ (2, 0), 6 7→ (0, 3), 7 7→ (1, 2) и т. д.
Так как указанная нумерация разнозначна и каждая пара натуральных чи- сел имеет натуральный номер, то это отображение осуществляет взаимно однозначное соответствие ω ↔ ω
2
. ¤
Упражнение. 1. Используя принцип математической индукции, пока- зать, что ω
n
∼ ω для любого n ∈ ω \ {0}.
2. Используя установленный в примере 1.2.10 факт, что Z ∼ ω, доказать эквивалентности ω + ω ∼ ω и Z
n
∼ ω, n ∈ ω \ {0}.

1.4. МОЩНОСТЬ МНОЖЕСТВА
29
Предложение 1.4.4. ω ∼ ∪
n∈ω
ω
n
.
Доказательство. Так как для любого n ∈ ω существует биекция
f
n
: ω ↔ ω
n
, то достаточно установить, что найдется биекция
ϕ: ω ↔
µ
∪
16n∈ω
{(n, k) | k ∈ ω}
¶
∪ {∅},
т. е. ϕ: ω ↔ {(n, k) | n, k ∈ ω, n > 1} ∪ {∅}. Биекция ϕ легко строится с помощью биекции ψ: ω ↔ ω
2
из предложения 1.4.3: ϕ(0) = ∅, ϕ(m+1) =
(n + 1, k), где ψ(m) = (n, k), m ∈ ω. ¤
Предложение 1.4.5. |Q| = ω.
Доказательство. Поскольку множество рациональных чисел Q состо- ит из дробей вида
m
n
, где m ∈ Z, n ∈ ω \ {0}, его можно представить в ви- де множества пар (m, n). Так как множество таких пар содержится в Z
2
,
а |Z
2
| = ω, то |Q| 6 ω. С другой стороны, очевидно, множество Q бес- конечно, т. е. |Q| > ω. По теореме Кантора—Бернштейна заключаем, что
|Q| = ω. ¤
Теорема 1.4.6. Выполняется |P(U)| = 2
|U |
для любого множества U.
Доказательство. Очевидно, что любому подмножеству A ⊆ U взаим- но однозначно ставится в соответствие индикаторная функция f ∈ 2
U
, для которой
f (x) =
(
0,
если x /
∈ A,
1,
если x ∈ A,
т. е. P(U) ∼ 2
U
. Осталось заметить, что 2
|U |
= |2
U
|. ¤
Теорема 1.4.7 (теорема Кантора). Выполняется |U| < 2
|U |
для любого
множества U.
Доказательство. В силу теоремы 1.4.6 достаточно доказать, что
|U| < |P(U)|. Так как отображение f : U → P(U), действующее по прави- лу f (x) = {x}, является разнозначным, то |U| 6 |P(U)|. Предположим,
что |U| = |P(U)|. Тогда существует биекция ϕ: U ↔ P(U). Рассмотрим множество K = {x ∈ U | x /
∈ ϕ(x)}. Поскольку ϕ — биекция и K ⊆ U,
т. е. K ∈ P(U), то существует k ∈ U такое, что ϕ(k) = K. Если k ∈ K,
то из определения K получаем k /
∈ ϕ(k) = K. Если же k /
∈ K, то k /
∈ ϕ(k),

30
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
и, следовательно, должно выполняться k ∈ K. Полученное противоречие показывает, что биекции ϕ существовать не может. ¤
Предложение 1.4.8. Если |A| > ω и |B| 6 ω, то |A \ B| = |A|.
Доказательство. Так как |B| 6 ω, то |A ∩ B| 6 ω. Рассмотрим мно- жество C со следующими условиями: A ∩ B ⊂ C ⊂ A, |C \ (A ∩ B)| = ω.
Такое множество C существует, поскольку по условию имеем |A \ B| > ω.
Так как C = (C \ (A ∩ B)) ∪ (A ∩ B), то |C| = ω и существует биекция
f : C \ (A ∩ B) ↔ C. Искомая биекция ϕ: A \ B ↔ A строится по следующим правилам: ϕ(x) = x, если x ∈ A \ C, ϕ(x) = f (x), если x ∈ C \ B. ¤
Предложение 1.4.9. 2
ω
∼ 10
ω
∼ ω
ω
.
Доказательство. Поскольку неравенства 2
ω
6 10
ω
6 ω
ω
очевидны,
достаточно доказать неравенство
ω
ω
6 2
ω
,
т. е. существование функ- ции ϕ: ω
ω
1−1
−−→ 2
ω
, которая кодирует всевозможные последовательности натуральных чисел с помощью последовательностей, состоящих из нулей и единиц. Для последовательности f ∈ ω
ω
определим последовательность
ϕ(f ) ∈ 2
ω
по следующим правилам:
1, 1, . . . , 1
|
{z
}
f (0) раз
, 0, 1, 1, . . . , 1
|
{z
}
f (1) раз
, 0, . . . , 1, 1, . . . , 1
|
{z
}
f (n) раз
, 0, . . .
Очевидно, что если f
1
6= f
2
(f
1
, f
2
∈ ω
ω
), то ϕ(f
1
) 6= ϕ(f
2
). ¤
Предложение 1.4.10. R ∼ [0, 1].
Доказательство. Равенство мощностей отрезка I
1
= [0, 1] и интервала
I
2
= (0, 1) обеспечивается биекцией ϕ: I
1
↔ I
2
, задаваемой по следующему правилу:
ϕ(x) =









x,
если x 6= 0, x 6=
1
n
, n ∈ ω \ {0},
1 2
,
если x = 0,
1 3
,
если x = 1,
1
n+2
,
если x =
1
n
, n > 1.
В свою очередь, биекция ψ(x) = tg (π(x −
1 2
)) (рис. 1.8) определяет экви- валентность интервала I
2
и множества R. Следовательно, R ∼ [0, 1]. ¤
Предложение 1.4.11. Множество вещественных чисел R контину-
ально.

1.5. МАТРИЦА БИНАРНОГО ОТНОШЕНИЯ
31 6
-
O
1 2
y
x
1
Рис. 1.8
Доказательство. В силу предложений 1.4.9 и 1.4.10 достаточно уста- новить, что 10
ω
∼ [0, 1]. Рассмотрим множество X = {f ∈ 10
ω
| f (m) 6= 9 для некоторого m ∈ ω и существует k ∈ ω такое, что f (n) = 9 для всех n > k}.
Так как множество 10
ω
\ X взаимно однозначно соответствует множеству бесконечных десятичных дробей, задающих числа из [0, 1], то по теореме
Кантора и предложению 1.4.8 остается показать, что множество X счетно.
Нетрудно заметить, что множество X эквивалентно множеству ∪
n∈ω
ω
n
, по- скольку каждая функция f ∈ X однозначно определяется кортежем цифр
(f (0), . . . , f (k)), где f (k) 6= 9 и f (n) = 9 для всех n > k. Теперь из предло- жения 1.4.4 получаем X ∼ ∪
n∈ω
ω
n
∼ ω, т. е. |X| = ω. ¤
§ 1.5.
Матрица бинарного отношения.
Специальные бинарные отношения
Рассмотрим два конечных множества
A = {a
1
, a
2
, . . ., a
m
},
B = {b
1
, b
2
, . . . , b
n
} и бинарное отношение P ⊆ A × B. Определим матрицу
[P ] = (p
ij
) размера m × n бинарного отношения P по следующему правилу:
p
ij
=
(
1,
если (a
i
, b
j
) ∈ P,
0,
если (a
i
, b
j
) /
∈ P.

32
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Полученная матрица содержит полную информацию о связях между эле- ментами и позволяет представлять эту информацию на компьютере. Заме- тим, что любая матрица, состоящая из нулей и единиц, является матрицей некоторого бинарного отношения.
Пример 1.5.1. Матрица бинарного отношения P ⊆ A
2
, A = {1, 2, 3},
заданного на рис. 1.9, имеет вид
[P ] =


1 1 1 0 0 1 1 0 0

 . ¤
Отметим основные свойства матриц бинарных отношений.
1. Если P, Q ⊆ A × B, [P ] = (p
ij
), [Q] = (q
ij
), то [P ∪ Q] = (p
ij
+ q
ij
)
и [P ∩ Q] = (p
ij
· q
ij
), где сложение осуществля-
•
•
•
-
¡
¡
¡
¡
¡
¡
ª
@
@
@
@
@
@
I@
@
@
@
@
@
R
¹¸
º·
¾
1 2
3
Рис. 1.9
ется по правилам 0 + 0 ­ 0, 1 + 1 ­ 1 + 0 ­
0 + 1 ­ 1, а умножение — обычным образом.
Итак, [P ∪ Q] = [P ] + [Q], а матрица [P ∩ Q] по- лучается перемножением соответствующих эле- ментов из [P ] и [Q]: [P ∩ Q] = [P ] ∗ [Q].
Пример 1.5.2. Пусть [P ] =
µ
1 0 1 0 1 1
¶
,
[Q] =
µ
0 1 1 0 0 1
¶
— матрицы отношений P и Q.
Тогда
[P ∪ Q] = [P ] + [Q] =
µ
1 0 1 0 1 1
¶
+
µ
0 1 1 0 0 1
¶
=
µ
1 1 1 0 1 1
¶
,
[P ∩ Q] = [P ] ∗ [Q] =
µ
1 0 1 0 1 1
¶
∗
µ
0 1 1 0 0 1
¶
=
µ
0 0 1 0 0 1
¶
. ¤
2. Если P ⊆ A × B, Q ⊆ B × C, то [P ◦ Q] = [P ] · [Q], где умножение матриц [P ] и [Q] производится по обычному правилу умножения матриц,
но произведение и сумма элементов из [P ] и [Q] — по определенным в п. 1
правилам.

1.5. МАТРИЦА БИНАРНОГО ОТНОШЕНИЯ
33
Пример 1.5.3. Если [P ] =
µ
0 1 0 1 1 0
¶
, [Q] =


0 1 1 0 1 1

, то
[P ◦ Q] =
µ
0 1 0 1 1 0
¶
·


0 1 1 0 1 1

 =
µ
1 0 1 1
¶
. ¤
3. Матрица обратного отношения P
−1
равна транспонированной матрице отношения P : [P
−1
] = [P ]
T
4. Если P ⊆ Q, [P ] = (p
ij
), [Q] = (q
ij
), то p
ij
6 q
ij
5. Матрица тождественного отношения id
A
единична:
[id
A
] =





1 0 · · · 0 0 1 · · · 0 0 0 · · · 1





.
Пусть P — бинарное отношение на множестве A: P ⊆ A
2
. Отношение P
называется рефлексивным, если (x, x) ∈ P для всех x ∈ A, т. е. id
A
⊆ P ,
[P ] =








1 1
∗
∗
1








.
Если P ∩ id
A
= ∅, то отношение P называется антирефлексивным или ирре-
флексивным. Отношение P называется симметричным, если для любых
x, y ∈ A из (x, y) ∈ P следует (y, x) ∈ P , т. е. P
−1
= P , или [P ]
T
= [P ]. Если
P ∩ P
−1
= ∅, то отношение P называется асимметричным. Отношение P
называется антисимметричным, если из (x, y) ∈ P и (y, x) ∈ P следует, что
x = y, т. е. P ∩ P
−1
⊆ id
A
. На языке матриц это означает, что в матрице
[P ∩ P
−1
] = [P ]∗[P ]
T
все элементы вне главной диагонали являются нулевы- ми. Отношение P называется транзитивным, если из (x, y) ∈ P и (y, z) ∈ P
следует (x, z) ∈ P , т. е. P ◦ P ⊆ P .