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

18
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Бинарные отношения P ⊆ A × B иногда удобно изображать графически.
Рассмотрим два таких представления. Начертим пару взаимно перпендику- лярных осей (Ox — горизонтальная ось, Oy — вертикальная ось), на каж- дой оси отметим точки, представляющие элементы множеств A и B соот- ветственно. Отметив на плоскости точки с координатами (x, y) такие, что
(x, y) ∈ P , получаем множество, соответствующее отношению P . На рис. 1.3
показано множество точек, соответствующих отношению из примера 1.2.1.
Другой способ состоит в том, что элементы
-
6 2 3 4 5 6 7 8 2
3 4
5 6
7 8
•
•
•
•
•

1.2. ОТНОШЕНИЯ. ФУНКЦИИ. ВЗАИМНО ОДНОЗНАЧНЫЕ СООТВЕТСТВИЯ
19
Обратным к P отношением называется множество
P
−1
­ {(y, x) | (x, y) ∈ P }.
Образом множества X относительно предиката P называется множество
P (X) ­ {y | (x, y) ∈ P для некоторого x ∈ X},
прообразом множества X относительно P — множество P
−1
(X) или, другими словами, образ множества X относительно предиката P
−1
Пример 1.2.5. Для отношения P из примера 1.2.1 и множества X = {3}
имеем δ
P
= {2, 3}, ρ
P
= {2, 3, 4, 6, 8}, P
−1
= {(2, 2), (4, 2), (6, 2), (8, 2), (3, 3),
(6, 3)}, P (X) = {3, 6}, P
−1
(X) = {3}. ¤
Произведением бинарных отношений P
1
⊆ A × B и P
2
⊆ B × C, или
композицией P
1
и P
2
называется множество
P
1
◦ P
2
­ {(x, y) | x ∈ A, y ∈ C, и найдется элемент z ∈ B,
для которого (x, z) ∈ P
1
и (z, y) ∈ P
2
} (рис. 1.5).
В дальнейшем произведение P
1
◦ P
2
будем также обозначать через P
1
P
2
Предложение 1.2.1. Для любых бинарных отношений P , Q и R
выполняются следующие свойства:
1) (P
−1
)
−1
= P ;
2) (P ◦ Q)
−1
= Q
−1
◦ P
−1
;
3) (P ◦ Q) ◦ R = P ◦ (Q ◦ R) (ассоциативность композиции).
'
&
$
%
'
&
$
%
'
&
$
%
•
•
•
A
B
C
x
z
y
P
1
P
2
-
-
P
1
◦ P
2
µ
Рис. 1.5

20
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Доказательство. 1. По определению обратного отношения условие
(x, y) ∈ P равносильно условию (y, x) ∈ P
−1
, что в свою очередь выполняет- ся тогда и только тогда, когда (x, y) ∈ (P
−1
)
−1
. Следовательно, P = (P
−1
)
−1 2. Предположим, что (x, y) ∈ (P ◦Q)
−1
. Тогда (y, x) ∈ P ◦Q и, следователь- но, (y, z) ∈ P и (z, x) ∈ Q для некоторого элемента z. Значит, (x, z) ∈ Q
−1
,
(z, y) ∈ P
−1
и (x, y) ∈ Q
−1
◦ P
−1
. Включение Q
−1
◦ P
−1
⊆ (P ◦ Q)
−1
доказы- вается аналогично.
3. Пусть (x, y) ∈ (P ◦ Q) ◦ R. Тогда для некоторых u и v имеем (x, u) ∈ P ,
(u, v) ∈ Q, (v, y) ∈ R. Таким образом, (u, y) ∈ Q ◦ R и (x, y) ∈ P ◦ (Q ◦ R).
Включение P ◦ (Q ◦ R) ⊆ (P ◦ Q) ◦ R доказывается аналогично. ¤
Ассоциативность композиции позволяет обозначать композицию
(P ◦ Q)◦ R = P ◦ (Q ◦ R) через P QR. По этой же причине однозначно опре- делена композиция P
1
P
2
. . . P
n
двухместных предикатов P
1
, P
2
, . . . , P
n
. Отме- тим, что существуют предикаты P и Q, для которых не выполняется закон коммутативности P ◦ Q = Q ◦ P (приведите примеры таких предикатов).
Отношение f ⊆ A × B называется функцией или отображением из мно- жества A в множество B, если δ
f
= A, ρ
f
⊆ B и из (x, y
1
) ∈ f , (x, y
2
) ∈ f
следует y
1
= y
2
. Если вместо δ
f
= A выполняется δ
f
⊆ A, то f называется
частичной функцией. Функция f из A в B обозначается через f : A → B или
A
f
→ B. Если (x, y) ∈ f , то пишем y = f (x) (y — значение функции f при значении аргумента x) или f : x 7→ y (функция f ставит в соответствие
элементу x элемент y).
Пример 1.2.6. Отношение {(1, 2), (2, 3), (3, 2)} ⊆ {1, 2, 3}
2
— функция,
отношение {(1, 2), (1, 3), (2, 3)} не является функцией, а отношение
{(x, x
2
− 2x + 3) | x ∈ R} — функция, которая обычно обозначается через
y = x
2
− 2x + 3. ¤
Пример 1.2.7. Тождественное отношение id
A
= {(x, x) | x ∈ A} является функцией id
A
: A → A, для которой id
A
(x) = x при всех x ∈ A. Другими при- мерами функций являются проекции π
A,B
1
: A × B → A и π
A,B
2
: A × B → B,
которые задаются по следующим правилам: π
A,B
1
((a, b)) ­ a, π
A,B
2
((a, b)) ­
b. ¤
Функция f называется разнозначной, инъективной (инъекцией) или
1-1-функцией, если отношение f
−1
является частичной функцией, т. е. для любых элементов x
1
, x
2
∈ δ
f
из x
1
6= x
2
следует f (x
1
) 6= f (x
2
). Если f —
инъекция, то будем писать f : A
1−1
−−→ B.

1.2. ОТНОШЕНИЯ. ФУНКЦИИ. ВЗАИМНО ОДНОЗНАЧНЫЕ СООТВЕТСТВИЯ
21
-
x
6
y
O
1 1
f
1
f
3
f
4
f
2
Рис. 1.6
Функция f : A → B называется функцией A на B или сюръективной
функцией (сюръекцией), если ρ
f
= B. Если f — сюръекция, то будем писать
f : A
на
−→ B.
Функция f называется взаимно однозначным соответствием между множествами A и B или биективной функцией (биекцией), если f — раз- нозначное отображение A на B. Таким образом, функция является биекци- ей, если она инъективна и сюръективна. Если f — биекция между A и B,
то будем писать f : A ↔ B. Биекция f : A ↔ A называется подстановкой
множества A. Простейшим примером подстановки является функция id
A
Пример 1.2.8. На рис.
1.6
графически показаны функции
f
i
: [0, 1] → [0, 1], i ∈ {1, 2, 3, 4}. Функция f
1
сюръективна, но не инъективна,
функция f
2
инъективна, но не сюръективна, функция f
3
биективна и явля- ется подстановкой, а функция f
4
не инъективна и не сюръективна. ¤
Пример 1.2.9. Рассмотрим три функции f
i
: R → R, i = 1, 2, 3:
1) функция f
1
(x) = e
x
инъективна, но не сюръективна;
2) функция f
2
(x) = x · sin x сюръективна, но не инъективна;
3) функция f
3
(x) = 2x − 1 биективна. ¤
Пример 1.2.10. Биекцией между множеством натуральных чисел
N = {0, 1, 2, . . .} и множеством целых чисел Z = {0, ±1, ±2, . . .} является функция f : N → Z, для которой
f (n) =
(
m,
если n = 2m − 1,
−m, если n = 2m.
¤

22
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Предложение 1.2.2. 1. Если f : A → B и g: B → C, то f ◦ g: A → C.
2. Если f : A → B, то id
A
◦ f = f , f ◦ id
B
= f .
3. Если f : A
на
−→ B, g: B
на
−→ C, то f ◦ g: A
на
−→ C.
4. Если f и g — разнозначные отображения, то f ◦ g — разнозначное
отображение.
5. Если f : A ↔ B, g: B ↔ C, то f ◦ g: A ↔ C.
6. Если f : A ↔ B, то f
−1
: B ↔ A, f ◦ f
−1
= id
A
, f
−1
◦ f = id
B
.
Доказательство. Утверждения 1 и 2 очевидны.
3. Достаточно доказать, что для любого c ∈ C найдется элемент a ∈ A
такой, что (f ◦ g)(a) = c. Поскольку g — сюръекция, найдется элемент b ∈ B,
для которого g(b) = c, а так как f — сюръекция, существует искомый эле- мент a ∈ A такой, что f (a) = b. Следовательно, f ◦ g: A
на
−→ C.
4. Предположим противное, т. е. найдутся элементы x
1
, x
2
, y такие, что
x
1
6= x
2
, (x
1
, y) ∈ f ◦ g и (x
2
, y) ∈ f ◦ g. В силу разнозначности f имеем
f (x
1
) 6= f (x
2
). Отсюда в силу разнозначности g получаем g(f (x
1
)) 6= g(f (x
2
)),
а это противоречит предположению g(f (x
1
)) = y = g(f (x
2
)).
Доказательство пп. 5 и 6 оставляется читателю в качестве упраж- нения. ¤
Если f — отображение и X ⊆ δ
f
, то множество {f (x) | x ∈ X} называет- ся образом множества X при отображении f и обозначается через f (X),
а отображение f ∩ (X × ρ
f
) называется ограничением f на X и обозначается через f |
X
или f ¹ X.
Функция f : N → B называется последовательностью. Ее можно пред- ставить в виде f (0), f (1), f (2), . . . , f (n), . . . или b
0
, b
1
, . . . , b
n
, . . ., где b
n
= f (n),
n ∈ N.
Множество всех функций из A в B обозначается через B
A
:
B
A
­ {f | f : A → B}.
Функция f : A
n
→ B называется n-местной функцией из A в B.
Если y — значение n-местной функции f при значении аргумента
(x
1
, x
2
, . . . , x
n
), то пишем y = f (x
1
, x
2
, . . . , x
n
). Функция f : A
n
→ A назы- вается n-местной алгебраической операцией на множестве A. При n = 1
операция f называется унарной, при n = 2 — бинарной, а в общем слу- чае — n-арной. При n = 0 операция f : A
0
→ A есть множество {(∅, a)} для некоторого a ∈ A. Часто 0-местную операцию {(∅, a)} на A будем называть
константой на A и отождествлять с элементом a.

1.3. НАТУРАЛЬНЫЕ ЧИСЛА. ПРИНЦИП МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ
23
Пример 1.2.11. Операция сложения вещественных чисел является двух- местной, т. е. бинарной операцией +: R
2
→ R, которая паре чисел (a, b) ста- вит в соответствие число a + b по обычному правилу: +(a, b) = a + b. Любой выделенный элемент множества R, например
√
2, является 0-местной опера- цией, т. е. константой на R. ¤
Очевидно, что n-местная операция на множестве A является (n + 1)- местным отношением на том же множестве A.
§ 1.3.
Натуральные числа.
Принцип математической индукции
Рассмотрим два подхода к заданию множества натуральных чисел. Пер- вый подход — конструктивный — позволяет представлять натуральные чис- ла в виде объектов, построенных из пустого множества. Второй подход — ак- сиоматический. Согласно этому подходу натуральные числа образуют мно- жество, удовлетворяющее некоторому набору свойств (аксиом), и при этом природа элементов множества не важна. Таким образом, с одной стороны,
указывается множество натуральных чисел, а с другой стороны — все суще- ственные (определяющие) свойства этого множества.
Положим по определению 0 ­ ∅, 1 ­ {0} (т. е. 1 = {∅}), 2 ­ {0, 1}
(т. е. 2 = {∅, {∅}}), . . ., n ­ {0, 1, . . . , n − 1}, . . . Множества, обозначаемые
0, 1, 2, . . . , n, . . ., называются натуральными числами. Объединив эти мно- жества, получаем множество всех натуральных чисел {0, 1, 2, . . . , n, . . .},
обозначаемое через ω.
В силу обозначений предыдущего параграфа, если A = n = {0, 1, . . . ,
n − 1}, B = 2 = {0, 1}, то
2
n
= B
A
= {f | f : n → {0, 1}}.
Обозначение B
A
согласуется с тем, что в множестве B
A
имеется ровно 2
n
функций. Действительно, поскольку функция f на каждом аргументе i ∈ n
может принимать одно из двух значений 0 или 1 и таких элементов i ровно n,
то всего имеется 2 · 2 · . . . · 2 = 2
n
различных функций.
Аналогично имеем 2
ω
= {f | f : ω → {0, 1}} — множество, состоящее из всех последовательностей нулей и единиц.

24
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Как уже отмечалось, второй подход к определению множества нату- ральных чисел является аксиоматическим. Мы рассмотрим аксиоматику
Дедекинда—Пеано.
Пусть имеется некоторое множество N, в котором выбран элемент, обо- значаемый через 0, и функция, которая произвольному элементу n ∈ N
ставит в соответствие элемент n
0
∈ N, называемый непосредственно сле-
дующим (элемент n
0
играет роль числа n + 1). Таким образом, с помощью функции n 7→ n
0
можно однозначно найти элементы 0
0
, 0
00
, 0
000
и т. д. (элемент
0
(n)
играет роль числа n). Множество N называется множеством натураль-
ных чисел, если система N ­ hN; 0,
0
i удовлетворяет следующим аксиомам:
1) для любого m 6= 0 найдется n ∈ N такой, что n
0
= m;
2) для любых m, n ∈ N, если m
0
= n
0
, то m = n;
3) n
0
6= 0 для любого n ∈ N;
4) (аксиома математической индукции) для любого свойства P (унар- ного отношения на множестве N), если P
выполняется на элементе 0
(т. е. 0 обладает свойством P ), и для любого n ∈ N из выполнимости P
на элементе n следует выполнимость P на элементе n
0
, то свойство P вы- полняется на любом элементе n ∈ N.
Последняя аксиома является наиболее содержательной, она символиче- ски записывается следующим образом: