ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 3445
Скачиваний: 14
12
Глава 1. Элементы теории множеств
ны несколько позже.
Далее символом
X
обозначается множество, на котором задано отноше-
ние эквивалентности
R
.
Определение 3.
Подмножество
A
из
X
называется
классом эквива-
лентности,
если 1) оно состоит из эквивалентных друг другу элементов и 2)
если
x
∈
X
эквивалентен хотя бы одному элементу из
A
, то
x
∈
A.
Т е о р е м а.
Два класса эквивалентности либо совпадают, либо не
пересекаются.
Доказательство.
Пусть
A
и
B
– два класса эквивалентности из
X
.
Допустим, что они пересекаются и
x
∈
A
T
B
. Если
a
– некоторый элемент
из
A
, то
a
∼
x.
Поскольку
x
∈
B
, то и
a
∈
B
. Таким образом,
A
⊂
B
.
Аналогично доказывается, что
B
⊂
A
. Итак,
A
=
B
. Теорема доказана.
Из свойства транзитивности отношения эквивалентности следует, что
класс эквивалентности является множеством всех элементов, эквивалентных
произвольному элементу из этого класса. Таким образом, из теоремы следует,
что отношение эквивалентности позволяет данное множество
X
представить
в виде объединения взаимно непересекающихся классов эквивалентности.
Определение 4.
Совокупность всех классов эквивалентности называ-
ется
фактор-множеством
. Оно обозначается символом
X/R.
Как уже отмечалось, каждый элемент
x
из множества
X
полностью
определяет класс эквивалентности его содержащий, который далее обознача-
ется символом
˜
x
, так что
x
∈
˜
x
(и
˜
x
= ˜
y
если и только если
x
∼
y
). Элемент
x
называется
представителем класса
A
, если
x
∈
A
.
Теперь вернемся к рассмотрению примеров 1 – 3 отношений эквивалент-
ности и найдем соответствующие фактор-множества.
В первом примере фактор-множество совпадает с множеством
Q
рацио-
нальных чисел, так как рациональное число определяется как совокупность
пар
(
p, q
)
, q
6
= 0
,
где при
pq
0
−
p
0
q
= 0
две пары
(
p, q
)
и
(
p
0
, q
0
)
определяют
одно и то же рациональное число.
Во втором примере фактор-множеством являются множества целых чи-
сел, сравнимых по модулю
m
. Это множество состоит из элементов
˜
1 =
{
1 +
km
:
k
∈
Z
}
,
˜
2 =
{
2 +
km
:
k
∈
Z
}
, ...,
˜
m
=
{
km
:
k
∈
Z
}
.
Например, при
m
= 2
оно состоит из двух классов: четных чисел и нечетных
чисел.
В третьем примере фактор-множество есть множество направлений пря-
мых на плоскости (пространства). Каждая из параллельных друг другу пря-
мых (из класса эквивалентности) служит "представителем"направления (на-
§
2
. Отношения эквивалентности. Фактор-множества
13
правление на плоскости или в пространстве есть множество всех параллель-
ных лучей плоскости или пространства).
Наконец, в четвертом примере фактор-множество состоит из свободных
векторов (свободный вектор – подмножество направленных отрезков про-
странства, имеющих одинаковую длину, лежащих на параллельных прямых
и одинаково направленных, т.е. является классом эквивалентности).
Множество свободных векторов пространства обозначим через
V
3
(а
плоскости через
V
2
).
Множество
Z
целых чисел
можно определить как
фактор-множество
следующим образом. На множестве
X
=
N
×
N
введем отношение эквивалент-
ности:
(
m, n
)
∼
(
p, q
)
,
если
m
+
q
=
n
+
p.
Класс эквивалентности, состоящий
из пар вида
(
n, n
)
, n
≥
1
,
называется нулевым числом.
В заключение параграфа договоримся об использовании некоторых ло-
гических символов.
Импликация.
Скажем, что предложение
P
влечет (имплицирует) пред-
ложение
Q
, если
Q
справедливо всякий раз, когда справедливо
P
. В этом
случае используется запись
P
⇒
Q.
Предложения
P
и
Q
называются экви-
валентными, если одновременно
P
⇒
Q
и
Q
⇒
P
; это записывается следу-
ющим образом
P
⇔
Q
(свойство
Q
есть необходимое и достаточное условие
для того, чтобы имело место свойство
P
).
Кванторы.
Символы
∀
и
∃
называются
кванторами
. В данном учеб-
ном пособии символ
∀
обозначает выражение "каково бы ни было"или "для
любого а символ
∃
обозначает выражение "существует".
Равенство.
Равенство обозначается символом = и имеет в математике
многообразный смысл.
1. Равенство означает тождество. Равенство
x
=
y
означает, что
x
и
y
не различаются. Например, пишут
1 = 1
.
2. Равенство может быть условным; такой смысл имеет равенство между
двумя частями уравнения. Например, равенство
ax
=
b
означает, что это
равенство имеет место только тогда, когда
x
принимает конкретное значение.
3. Знак равенства ставится между элементами одного класса эквивалент-
ности из фактор-множества. Например, вместо записи 2/3
∼
4/9 (см. пример
1) используется запись 2/3 = 4/6 .
В дальнейшем нами часто используется метод математической индук-
ции.
Пусть
P
(
n
)
- некоторое утверждение, зависящее от
n
∈
N
, n
≥
n
0
.
Метод
математической индукции описывается следующим образом:
1) проверяется справедливость утверждения
P
(
n
0
)
(база индукции),
2) предполагается, что утверждение
P
(
n
)
справедливо для всех
n < k,
14
Глава 1. Элементы теории множеств
где
k > n
0
(индукционное предположение),
3) доказывается, что утверждение
P
(
n
)
верно для
n
=
k
(индукционный
переход).
Если все три этапа проделаны, то утверждение
P
(
n
)
верно для всех
n
≥
n
0
.
В этом и состоит принцип математической индукции. Говорят также,
что утверждение доказано методом математической индукции.
Определение 5.
Бинарное отношение
R
на множестве
X
называется
отношением порядка
на
X
(для пары
(
x, y
)
∈
R
используется обозначение
x
y
, причем, пишут
x < y
для
x
6
=
y,
) если выполнены свойства:
1)
x
x
∀
x
∈
X
;
2) если
x
y
и
y
x
одновременно, то
x
=
y
;
3) из условий
x
y, y
z
следует, что
x
z.
Множество
X
, на котором введено отношение порядка, называется
ча-
стично упорядоченным
множеством. Подмножество
S
из
x
называется
ли-
нейно упорядоченным
, если для любой пары
a, b
различных элементов из
S
либо
a < b,
либо
b < a.
Множество
R
n
будет являться частично упорядоченным множеством,
если положить
x
≤
y,
для
x
= (
x
1
, . . . , x
n
)
, y
= (
y
1
, . . . y
n
)
,
удовлетворяющих
условию
x
i
≤
y
i
,
1
≤
i
≤
n.
Множество
S
(
X
)
всевозможных подмножество (непустого) множества
X
является частично упорядоченным множеством, если отношение порядка
ввести таким образом:
A B
,
для
A ⊂ B
.
Упражнения к §§ 1,2
1. Докажите равенства 1) - 5) из
§
1.
2. Пусть
A
α
, α
∈
I
– некоторая совокупность подмножеств из множества
X
, индексированная элементами множества
I
. Докажите равенства
X
\
(
[
α
∈
I
A
α
) =
\
α
∈
I
(
X
\
A
α
)
, X
\
(
\
α
∈
I
A
α
) =
[
α
∈
I
(
X
\
A
α
)
.
3. Докажите, что бинарные отношения, определенные в примерах 1-3, яв-
ляются отношениями эквивалентности.
4. Рассмотрим множество
R
вещественных чисел и рассмотрим бинарное
отношение:
x
∼
y
, если
x
−
y
– целое число. Докажите, что это отношение
эквивалентности и найдите соответствующее фактор-множество.
5. На множестве
R
введено бинарное отношение
F
=
{
(
x, y
)
∈
R
2
:
|
x
−
y
| ≤
1
}
.
Будет ли оно отношением эквивалентности?
§
3
.
Отображения множеств и классификация отображений
15
6. На плоскости
P
выбрана некоторая декартова прямоугольная система
координат. На
P
заданы три бинарных отношения:
A
∼
B
для
A, B
∈
P
,
если их координаты
(
a
1
, a
2
)
,
(
b
1
, b
2
)
удовлетворяют соответствующему
условию
1)
a
1
=
b
1
, a
2
−
b
2
∈
Z
;
2)
a
1
−
b
1
, a
2
−
b
2
∈
Z
;
3)
a
1
−
b
1
+
a
2
−
b
2
∈
Z
.
Докажите, что отношения 1)-3) являются отношениями эквивалентно-
сти. Найдите соответствующие фактор-множества.
§
3. Отображения множеств и классификация отображений
Одним из важнейших широко используемых в современной математике
понятий является понятие отображения множеств.
Определение 1.
Пусть
X
и
Y
– два непустых множества.
Отображе-
нием
f
множества
X
называется правило, по которому каждому элементу
из
X
ставится в соответствие вполне определенный элемент из множества
Y
.
В этом случае для записи отображения используется запись
f
:
X
→
Y
или
X
f
−→
Y
(используется также обозначение
x
7→
f
(
x
))
.
Символом
f
(
x
)
обозначается элемент
y
∈
Y
, который ставится в соответствие элементу
x
∈
X
и называется
значением отображения
f
на элементе
x
.
Множество
X
называют
областью определения
отображения
f
, а мно-
жество
Y
–
областью значений
.
Отображения множеств называют также
функциями, преобразования-
ми, операторами
. Например, отображение
f
:
X
→
Y
обычно называют
функцией, если
X
и
Y
– подмножества из
R
(т.е. числовые множества), ли-
бо таким является одно из них.
Особо отметим, что следует различать отображение
f
и элемент
f
(
x
)
,
равный значению отображения
f
на элементе
x
. Однако это различие ино-
гда не принимается во внимание. Так, например, неправильно (но удобно)
говорить "функция cos x хотя следовало бы читать "функция cos".
Важно отметить еще, что отображение
f
считается заданным, если зада-
ны как его область определения
X
, так и область значений
Y.
Таким образом,
отображение есть тройка
(
X, Y, f
)
.
Пример 1.
Функция
f
, определенная формулой
f
(
x
) = 1
/x,
являет-
ся отображением множества
R
\{
0
}
отличных от нуля вещественных чисел
16
Глава 1. Элементы теории множеств
в
R
\{
0
}
.
Можно также рассматривать отображение
g
:
R
+
→
R
+
(
R
+
=
{
t
∈
R
:
t >
0
}
– множество положительных чисел), определенное с помо-
щью формулы
g
(
x
) = 1
/x, x >
0
.
Эта функция
g
отличается от функции
f
,
так как они имеют разные области определения.
В
школьном
курсе
математики
рассматриваются
другие
примеры функций.
Пример 2.
Пусть
E
– множество отрезков из
R
.
Каждому отрезку
[
a, b
]
поставим в соответствие его длину
b
−
a.
Получим отображение
φ
:
E
→
R
.
Пример 3.
Пусть
B
– множество жителей города Воронежа и
S
– мно-
жество слов. Каждому жителю сопоставим его имя. Получим отображение
из множества
B
в множество
S
.
Пример 4.
Пусть
X
– непустое множество и
R
отношение эквивалент-
ности на
X
. Каждому элементу
x
из
X
поставим в соответствие класс экви-
валентности
˜
x,
его содержащий. Тем самым получили отображение
f
:
X
→
X/R
.
Пример
5.
Пусть
X
– произвольное множество. Отображение
I
X
:
X
→
X
(обозначаемое также символом
I
, если ясно, о каком мно-
жестве идет речь), определенное равенством
I
X
x
=
x, x
∈
X
,
называется
тождественным отображением
.
Отображения множеств можно задавать с помощью таблиц, графиков,
стрелочных схем.
Строя таблицу отображения
f
:
A
→
B
, в ней записывают всевозможные
пары
(
a, ϕ
(
a
))
, a
∈
A
:
x
a
1
a
2
. . .
a
n
ϕ
(
x
)
ϕ
(
a
1
)
ϕ
(
a
2
)
. . .
ϕ
(
a
n
)
или
a
1
a
2
. . .
a
n
ϕ
(
a
1
)
ϕ
(
a
2
)
. . .
ϕ
(
a
n
)
.
.
Разумеется, эта таблица полностью задает отображение
ϕ
только в слу-
чае конечного множества
A
=
{
a
1
, ..., a
n
}
, то есть множества, состоящего из
определенного числа элементов.
С помощью стрелочных схем, которые также называются
графами
, отоб-
ражение
ϕ
:
A
→
B
задается так: элементы множеств
A
и
B
обозначают
различными точками плоскости (для множества
A
– слева, а для
B
– спра-
ва). Затем каждую из точек, которыми обозначены элементы множества
A
,
соединяют стрелкой слева направо с точкой, которой обозначен соответству-
ющий элемент множества
B
. Задание отображения с помощью графа наибо-
лее удобно для конечных множеств.
Пример 6.
Пусть
A
=
{
3
,
2
,
6
,
7
}
, B
=
{
28
,
12
,
4
,
5
,
11
,
14
}
, ϕ
:
A
→
B
–
отображение, которое каждому числу из A ставит в соответствие наименьшее