ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 3450
Скачиваний: 14
22
Глава 1. Элементы теории множеств
Для обратимого отображения
f
:
X
→
X
можно еще ввести отображе-
ние
f
−
n
:
X
→
X,
положив
f
−
n
= (
f
−
1
)
n
.
Ясно (это вытекает из теоремы 2),
что
f
−
n
– отображение обратное к
f
n
.
Т е о р е м а 3.
Пусть
f
:
X
→
Y, g
:
Y
→
Z
– два обратимых
(биективных) отображения. Тогда их суперпозиция
g
◦
f
является также об-
ратимым (биективным) отображением и
(
g
◦
f
)
−
1
=
f
−
1
◦
g
−
1
(т.е. обратное
отображение к суперпозиции отображений есть суперпозиция обратных к
g
и
f
отображений, но взятых в другом порядке сомножителей).
Доказательство.
Из теоремы 2 следуют равенства
(
g
◦
f
)
◦
(
f
−
1
◦
g
−
1
) =
g
◦
(
f
◦
f
−
1
)
◦
g
−
1
=
g
◦
I
Y
◦
g
−
1
=
g
◦
g
−
1
=
I
Z
.
Аналогично проверяется равенство
(
f
−
1
◦
g
−
1
)
◦
(
g
◦
f
) =
I
X
. Таким образом,
отображение
g
◦
f
обратимо (следовательно, биективно) и
(
g
◦
f
)
−
1
=
f
−
1
◦
g
−
1
.
Теорема доказана.
Следующие два понятия используются нами далее, они тесно связаны с
понятием отображения.
Определение 12.
Пусть
X
– непустое множество. Отображение
x
:
N
→
X
называется
последовательностью
. Для задания последователь-
ности
x
:
N
→
X
достаточно выписать упорядоченный (элементами из
N
)
набор элементов
(
x
1
, x
2
, . . .
)
,
и тогда
x
(
k
) =
x
k
. В связи с этим последова-
тельности обозначают символом
(
x
1
, x
2
, . . .
)
или, короче,
(
x
k
)
.
Определение 13.
Отображение
f
:
X
1
×
X
2
×· · ·×
X
n
→
Y, n
≥
2
, опре-
деленное на произведении нескольких множеств, называется отображением
(функцией) нескольких переменных.
Упражнения к § 3
1. Постройте графы преобразований, заданных таблицами:
a
)
1 2 3 4 5 6 7 8
5 6 1 8 3 7 2 4
;
b
)
1 2 3 4 5 6 7 8
6 8 5 4 3 7 1 3
;
c
)
1 2 3 4 5 6 7
6 4 3 7 5 1 2
;
d
)
1 2 3 4 5 6 7 8 9
6 4 1 8 4 3 4 9 9
.
2. Какие из преобразований a)-d) из задачи 1 инъективны, сюръективны,
биективны?
3. Пусть
f
:
X
→
Y
– отображение и
B, C
– подмножества из
Y
.
Докажите, что имеют место равенства
а)
f
−
1
(
B
S
C
) =
f
−
1
(
B
)
S
f
−
1
(
C
);
§
3
.
Отображения множеств и классификация отображений
23
б)
f
−
1
(
Y
\
B
) =
X
\
f
−
1
(
B
);
в)
f
−
1
(
B
T
C
) =
f
−
1
(
B
)
T
f
−
1
(
C
)
.
4. Пусть
f
:
X
→
Y
– отображение и
A, B
– подмножества из
X
.
Докажите, что имеют место следующие соотношения
A
⊂
B
=
⇒
f
(
A
)
⊂
f
(
B
);
f
(
A
T
B
)
⊂
f
(
A
)
T
f
(
B
);
f
(
A
S
B
) =
f
(
A
)
S
f
(
B
)
.
5. Докажите, что для любого отображения
f
:
X
→
X
имеют место
включения
f
(
X
)
⊃
f
2
(
X
)
⊃
f
3
(
X
)
⊃
. . . .
6. Приведите пример отображения
f
:
X
→
Y
и подмножества
B
⊂
Y
такого, что
f
−
1
(
B
) =
∅
(рассмотрите
f
(
x
) =
x
2
, f
:
R
→
R
)
.
7. Приведите пример отображения
f
:
X
→
X
и двух подмножеств
A, B
из
X
таких, что
f
(
A
T
B
)
6
=
f
(
A
)
T
f
(
B
)
.
8. Приведите пример отображения
f
:
N
→
N
, которое
а) инъективно, но не сюръективно;
б) сюръективно, но не инъективно.
9. Пусть
X
– конечное множество. Докажите, что если
f
:
X
→
X
–
инъективное отображение, то оно сюръективно (и, следовательно, биектив-
но).
10. Найдите суперпозиции
g
◦
f
и
f
◦
g
функций
f, g
:
R
→
R
, если
а)
f
(
x
) = 2
x
+ 3
, g
(
x
) = 3
x
+ 4;
б)
f
(
x
) =
x
3
+ 5
x
2
, g
(
x
) =
x
2
+ 3;
в)
f
(
x
) =
x
2
+ 2
, g
(
x
) =
x
3
+
x
2
+ 1
.
11. Пусть
f
:
R
\ {−
1
} →
R
\ {−
1
}
– функция, определенная формулой
f
(
x
) =
−
x
−
3
x
+ 1
.
Найдите
f
2
и
f
3
.
12. Какие из следующих отображений множества
R
и
R
обратимы:
а)
f
1
(
x
) =
x
n
(
n
– натуральное число);
б)
f
2
(
x
) = 2
x
;
в)
f
3
(
x
) =
ax
+
b, a, b
∈
R
, a
6
= 0;
г)
f
4
(
x
) =
cos x
?
Найдите обратные к обратимым отображениям.
13. Пусть
f
:
X
→
Y
– обратимое отображение. Докажите, что тогда
отображение
f
−
1
:
Y
→
X
обратимо и
(
f
−
1
)
−
1
=
f
.
14. Пусть
f
:
X
→
X
– обратимое отображение. Докажите, что для
любого натурального
n
отображение
f
n
обратимо и
(
f
n
)
−
1
=
f
−
n
.
15. Докажите единственность обратного для обратимого отображения.
24
Глава 1. Элементы теории множеств
16. Пусть
f
:
X
→
Y
– отображение. Докажите, что если существует
отображение
g
:
Y
→
X
такое, что
g
◦
f
=
I
X
, то
f
–инъективное отображе-
ние. Отображение
g
называют левым обратным для
f
.
17. Докажите, что если для отображения
f
:
X
→
Y
существует отобра-
жение
g
:
Y
→
X
такое, что
f
◦
g
=
I
Y
, то
f
– сюръективное отображение.
Отображение
g
называют правым обратным для
f
.
18. Пусть
X
и
Y
- конечные множества с числом элементов
n
и
m
соответственно. Найти число
а) отображений;
б) инъективных отображений;
в) сюръективных отображений
множества
X
в множество
Y
.
§
4. Сравнение множеств. Мощность множества
Множества бывают конечные и бесконечные.
Конечным
называется мно-
жество, состоящее из нескольких элементов. Любые два конечных множества
можно сравнивать по числу элементов и говорить об одинаковом количестве
элементов или о том, что в одном множестве число элементов меньше, чем
число элементов второго. Однако в вопросах сравнения двух множеств мож-
но поступить несколько по-иному, заметив, что два конечных множества
X
и
Y
имеют одинаковое количество элементов тогда и только тогда, когда
существует биективное отображение
f
:
X
→
Y
(т.е. между множествами
X
и
Y
можно установить взаимно однозначное соответствие). Этот подход
позволяет ввести следующее понятие.
Определение 1.
Два множества
X
и
Y
называются
эквивалентны-
ми
(будет использоваться обозначение
X
∼
Y
), если существует биективное
отображение
f
:
X
→
Y.
Определение 2.
Множество
X
называется
бесконечным
, если оно не
эквивалентно никакому конечному множеству.
Т е о р е м а 1.
Введенное в классе всех множеств бинарное отношение
является отношением эквивалентности.
Доказательство.
Если
X
∼
Y
, то существует биективное отображение
f
:
X
→
Y
. В силу теоремы 1 из
§
1
оно обратимо и поскольку обратное
отображение
f
−
1
:
Y
→
X
также биективно (см. задачу 13 из
§
3)
, то
Y
∼
X
.
Ясно, что
X
∼
X
(тождественное отображение
I
X
биективно). Наконец,
если
X
∼
Y, Y
∼
Z
и
f
:
X
→
Y, g
:
Y
→
Z
– биективные отображения, то
в силу теоремы 3 из
§
3
их суперпозиция
g
◦
f
:
X
→
Z
есть снова биективное
отображение и поэтому
X
∼
Z.
Теорема доказана.
§
4
.
Сравнение множеств. Мощность множества
25
Таким образом, класс всех множеств (мы избегаем термина множество
всех множеств) разбивается на непересекающиеся классы эквивалентности.
Определение 3.
Два множества, входящие в один класс эквивалентно-
сти, называются
равномощными
или про такие множества говорят, что они
имеют одинаковую
мощность
или одинаковое
кардинальное число.
Пусть
n
– натуральное число. Тогда класс эквивалентности, содержа-
щий множество
{
1
,
2
, . . . , n
}
, состоит из всех конечных множеств, содержа-
щих ровно
n
элементов. Таким образом, понятие мощности множества (кар-
динального числа) является непосредственным обобщением понятия числа.
Определение 4.
Множество
X
называется
счетным
, если оно эквива-
лентно множеству
N
натуральных чисел.
Следующие примеры показывают, что при рассмотрении бесконечных
множеств следует проявлять большую осторожность.
Пример 1.
Множество
N
2
четных натуральных чисел счетно. Для до-
казательства следует рассмотреть биективное отображение
f
(
n
) = 2
n,
f
:
N
→
N
2
.
Таким образом, подмножество
N
2
из
N
эквивалентно самому
множеству
N
.
Разумеется, таким свойством могут обладать только бесконеч-
ные множества.
Пример 2.
Любые два отрезка [a,b] и [c,d] имеют одинаковую мощность,
так как отображение
f
: [
a, b
]
→
[
c, d
]
, f
(
x
) =
d
−
c
b
−
a
x
+
bc
−
da
b
−
a
биективно.
Определение 5.
Множества, эквивалентные отрезку [0,1], называются
множествами мощности континуума.
Из примера 2 следует, что любой отрезок из [0,1] имеет мощность кон-
тинуума.
Т е о р е м а 2.
Множество
Q
рациональных чисел счетно.
Доказательство.
Каждое рациональное число
α
однозначно записы-
вается в виде несократимой дроби
α
=
p/q, q >
0
. Число
|
p
|
+
q
назовем
высотой рационального числа
α.
Отметим, что имеется лишь конечное чис-
ло рациональных чисел, имеющих данную высоту
n
∈
N
.
Пронумеруем все
рациональные числа по возрастанию высоты, т.е. вначале выпишем числа вы-
соты 1 (имеется только одно число 0/1=0 такой высоты), затем высоты 2 (это
числа
1
/
1
и
−
1
/
1)
,
высоты 3 и т.д. При этом всякое рациональное число по-
лучит некоторый номер, т.е. построено биективное отображение
ϕ
:
Q
→
N
.
Теорема доказана.
Бесконечное множество, не являющееся счетным множеством, называ-
ется
несчетным множеством
.
Г.Кантором было доказано (см., например, [7]), что отрезок [0,1] – несчет-
ное множество.
26
Глава 1. Элементы теории множеств
Упражнения к § 4
1. Докажите счетность следующих двух множеств
{
2
,
3
,
4
, . . .
}
{
1
,
3
,
5
, . . . ,
2
n
+ 1
, . . .
}
.
2. Докажите счетность множества
Z
целых чисел.
3. Докажите эквивалентность интервала (0,1) и множества
R
.
4. Докажите эквивалентность интервала
(
a, b
)
и отрезка
[
a, b
]
.