ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 3528
Скачиваний: 14
7
ГЛАВА 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Некоторые обозначения и соглашения
Под
множеством
понимается совокупность некоторых объектов, объ-
единенных общим признаком. Примеры: 1) множество жителей города Во-
ронежа; 2) множество точек плоскости; 3) множество треугольников плос-
кости; 4) множество
N
натуральных чисел
; 5) множество
Z
целых чисел
;
6) множество
Q
рациональных чисел
; 7) множество
R
вещественных чисел
.
Структура объектов, входящих в данное множество, не рассматривается при
изучении этого множества.
В 1872 г Георг Кантор, основатель теории множеств, определил множе-
ство как "объединение в одно целое объектов, хорошо различимых нашей
интуицией или нашей мыслью".
Множества обычно обозначают большими буквами
X, Y, Z, A, B, C,
Ω
.
Объекты, входящие в данное множество
X,
называются его
элементами
;
они обозначаются малыми буквами
x, y, z, a, b, c, ... .
Запись
x
∈
X
означает,
что
x
является элементом множества
X
, а запись
x
∈
X
или
x /
∈
X
означает,
что элемент
x
не принадлежит множеству
X.
Если множество
A
состоит из элементов, принадлежащих множеству
X
, то говорят, что
A
является
подмножеством
множества
X
(или
A
вклю-
чено в
X
), и в этом случае пишут
A
⊂
X
(или
A
⊆
X
). Например,
Z
– под-
множество множества
R
(кроме того,
N
⊂
Z
⊂
Q
⊂
R
). Используется также
обозначение
X
⊃
A
, которое читается так:
X
содержит A. Два множества
X
и
Y
называются
равными
, если одновременно
X
⊂
Y
и
Y
⊂
X,
т.е. они
состоят из одних и тех же элементов.
Для описания множества пользуются двумя способами. Первый состоит
в простом перечислении его элементов. Так, например, запись
A
=
{
0
,
1
,
5
}
означает, что множество
A
состоит из трех чисел 0, 1 и 5. Второй способ
состоит в определении множества с помощью некоторого свойства
P
, позво-
ляющего определить принадлежит ли данный элемент данному множеству
или нет. В этом случае используется коллективизирующее обозначение
A
=
{
x
:
P
(
x
)
}
,
которое читается следующим образом: множество
A
состоит из всех элемен-
тов
x
, для которых
P
(
x
)
истинно. Если свойство
P
относится к элементам
некоторого множества
X
, то будем писать также
A
=
{
x
∈
X
:
P
(
x
)
}
. На-
пример,
множество
{
1
,
2
,
3
,
4
,
5
}
можно
задать
следующим
образом:
8
Глава 1. Элементы теории множеств
{
1
,
2
,
3
,
4
,
5
}
=
{
x
:
x
– целое число, удовлетворяющее неравенству
1
≤
x
≤
5
}
=
{
x
∈
Z
: 1
≤
z
≤
5
}
.
Аналогичным образом могут быть
заданы следующие множества
[
a, b
] =
{
x
∈
R
:
a
≤
x
≤
b
}
,
(
a, b
) =
{
x
∈
R
:
a < x < b
}
.
Часто используется множество, которое называется
пустым
и обозначается
символом
∅
.
По определению
∅
=
{
x
:
x
6
=
x
}
.
Поскольку нет элементов,
удовлетворяющих условию
x
6
=
x,
то
∅
не содержит элементов. Ясно, что
∅ ⊂
A
для любого множества
A
.
§
1. Операции над множествами
Рассмотрим задачу построения новых множеств из тех, которыми мы
располагаем.
Определение 1.
Объединением
двух множеств
A
и
B
называется мно-
жество (см.рис. 1)
A
[
B
=
{
x
:
x
∈
A , x
∈
B
}
.
Определение 2.
Пересечением
двух множеств
A
и
B
называется мно-
жество (см.рис.2)
A
\
B
=
{
x
:
x
∈
A , x
∈
B
}
.
Определение 3.
Разностью
двух множеств
A
и
B
называется множе-
ство (см.рис.3)
A
\
B
=
{
x
∈
A
:
x
∈
B
}
.
Определение 4.
Если
A
– подмножество множества
X
, то множество
X
\
A
называют
дополнением
множества
A
до множества
X
и обозначают
также символом
A
0
или
CA.
§
1. Операции над множествами
9
Определение 5.
Симметрической разностью
двух множеств
A
и
B
называется множество
A
∆
B
= (
A
\
B
)
[
(
B
\
A
)
.
Аналогично определяется объединение и пересечение любого (конечного
или бесконечного) числа множеств
A
α
, α
∈
I,
где
I
– некоторое множество
индексов. А именно, положим
[
α
∈
I
A
α
=
{
x
:
x
∈
A
α
хотя бы для одного
α
∈
I
}
;
\
α
∈
I
A
α
=
{
x
:
x
∈
A
α
для всех
α
∈
I
}
.
Отметим следующие свойства введенных операций над множествами
1)
A
S
(
B
S
C
) = (
A
S
B
)
S
C
;
2)
A
T
(
B
T
C
) = (
A
T
B
)
T
C
;
3)
A
S
(
B
T
C
) = (
A
S
B
)
T
(
A
S
C
);
4)
A
T
(
B
S
C
) = (
A
T
B
)
S
(
A
T
C
);
5)
(
A
S
B
)
0
=
A
0
T
B
0
;
6)
(
A
T
B
)
0
=
A
0
S
B
0
.
7)
(
A
∆
B
) = (
A
S
B
)
\
(
A
T
B
);
8)
(
A
∆
B
)∆
C
=
A
∆(
B
∆
C
);
9)
(
A
∆
B
)∆
C
= (
A
S
B
S
C
)
\
(
A
T
B
T
C
)
.
Последние два свойства относятся к множествам
A, B
, являющимся подмно-
жествами некоторого множества
X
.
Докажем шестое свойство. По определению равных множеств нам следу-
ет доказать включения
(
A
T
B
)
0
=
X
\
(
A
T
B
)
⊂
A
0
S
B
0
= (
X
\
A
)
S
(
X
\
B
)
и
A
0
S
B
0
⊂
(
A
T
B
)
0
.
Для доказательства первого включения рассмотрим про-
извольный элемент
x
∈
X
\
(
A
T
B
)
.
Это означает, что
x
∈
X
, но
x
∈
A
T
B
,
то есть
x
не принадлежит либо
A
, либо
B
. Отсюда следует, что
x
принад-
лежит либо
X
\
A,
либо
X
\
B
, и поэтому
x
∈
A
0
S
B
0
.
Таким образом,
(
A
T
B
)
0
⊂
A
0
S
B
0
. Обратно, если
x
∈
A
0
S
B
0
,
то
x
принадлежит хотя бы
одному из множеств
A
0
, B
0
.
Для определенности пусть
x
∈
A
0
=
X
\
A
. Это
означает, что
x
∈
A,
и поэтому
x
∈
A
T
B
. Следовательно,
x
∈
(
A
T
B
)
0
=
X
\
(
A
T
B
)
.
Итак,
A
0
S
B
0
⊂
(
A
T
B
)
0
.
Множество, состоящее из двух элементов и в котором определен поря-
док следования элементов, называется
упорядоченной парой
. Для записи упо-
рядоченной пары используются круглые скобки. Так запись
(
a, b
)
означает
двухэлементное множество, в котором элемент
a
считается первым, а эле-
мент
b
вторым. Две упорядоченные пары
(
a, b
)
и
(
b, a
)
при
a
6
=
b
считаются
10
Глава 1. Элементы теории множеств
различными, хотя двухэлементные множества
{
a, b
}
и
{
b, a
}
одинаковы (сов-
падают). Аналогичным образом дается
определение упорядоченного набора из
n
элементов
.
Определение 5.
Пусть
X
1
и
X
2
– два непустых множества.
Произ-
ведением
(или
декартовым произведением
) этих множеств будем называть
множество упорядоченных пар
(
x
1
, x
2
)
, где
x
1
∈
X
1
и
x
2
∈
X
2
, т.е.
X
1
×
X
2
=
{
(
x
1
, x
2
) :
x
1
∈
X
1
, x
2
∈
X
2
}
.
Это понятие выросло из понятия декартовой системы координат на плос-
кости.
Определение произведения двух множеств естественно обобщается на
случай
n
множеств. Если
X
1
, X
2
, . . . , X
n
–
n
непустых множеств, то их
(декартово) произведение
X
1
× · · · ×
X
n
состоит из всевозможных упорядо-
ченных наборов
(
x
1
, . . . , x
n
)
, x
k
∈
X
k
, k
= 1
, ..., n
элементов этих множеств.
Если все множества
X
1
, ..., X
n
совпадают:
X
1
=
X
2
=
...
=
X
n
=
X,
то
их проведение
X
1
×
...
×
X
n
обозначается
X
n
. Так, например, символом
R
n
обозначается множество упорядоченных наборов
n
вещественных чисел.
§
2. Отношения эквивалентности. Фактор-множества
По данному множеству
X
можно строить новые множества, рассматри-
вая множество некоторых подмножеств множества
X
. Следует сказать, что
принято говорить не о множестве подмножеств данного множества, а о классе
подмножеств или семействе подмножеств. Так, например, класс всех подмно-
жеств множества
X
=
{
1
,
2
,
3
}
состоит из подмножеств
∅
,
{
1
}
,
{
2
}
,
{
3
}
,
{
1
,
2
}
,
{
1
,
3
}
,
{
2
,
3
}
,
{
1
,
2
,
3
}
.
Таким образом, элементами вновь построенного множе-
ства могут быть подмножества данного множества.
В самых различных вопросах (примеры будут приведены) приходится
рассматривать класс таких подмножеств данного множества
X
, которые вза-
имно не пересекаются и объединение этих подмножеств совпадает с
X
. На-
пример, плоскость можно представить как объединение прямых, параллель-
ных данной прямой. Физическое пространство есть объединение концентри-
ческих сфер (начиная со сферы радиуса нуль). Множество жителей города
Воронежа можно разбить на группы по их году рождения. В биологии все
множество животных разбивается на типы, типы - на классы и т.д.
Если данное множество
X
можно представить в виде объединения своих
попарно непересекающихся подмножеств, то будем говорить, что
X
разбито
на классы
.
§
2
. Отношения эквивалентности. Фактор-множества
11
Разбиение данного множества на классы осуществляется на базе того или
иного признака (это мы видим на примерах), по которому элементы множе-
ства
X
объединяются в классы. Чтобы придать этому высказыванию более
точный смысл, введем несколько понятий.
Определение 1.
Пусть
X
– непустое множество. Подмножество
R
из
произведения
X
×
X
называется
бинарным отношением
на множестве
X
.
Если пара
(
x, y
)
входит в
R
, иногда будем писать
xRy
и говорить, что эле-
мент
x
находится в отношении
R
с
y.
Так, например, отношения
x
=
y
;
x
≥
y
;
x < y
;
x
2
+
y
2
= 1
, x
6
= 0
являются бинарными отношениями на
R
.
Определение 2.
Бинарное отношение
R
на
X
называется
отношением
эквивалентности,
если оно обладает следующими тремя свойствами:
а) рефлексивность:
(
x, x
)
∈
R
∀
x
∈
X
;
б) симметричность: из
(
x, y
)
∈
R
следует, что
(
y, x
)
∈
R
;
в) транзитивность: если
(
x, y
)
∈
R
и
(
y, z
)
∈
R,
то
(
x, z
)
∈
R.
Вместо того, чтобы писать
(
x, y
)
∈
R
, пишут
x
∼
y
или, еще короче,
x
≡
y
(если ясно, о каком отношении идет речь). Элементы
x
и
y
будем
называть эквивалентными.
Из четырех бинарных отношений на
R
, рассмотренных после опреде-
ления 1, отношением эквивалентности является только первое. Рассмотрим
другие отношения эквивалентности.
Пример 1.
Рассмотрим множество
Z
целых чисел. Пусть
X
- подмно-
жество из
Z
×
Z
,
состоящее из пар вида
(
p, q
)
,
где
q
6
= 0
.
Отношение эквива-
лентности
R
на
X
зададим формулой
(
p, q
)
∼
(
p
0
, q
0
)
,
если
pq
0
=
p
0
q.
Таким
образом,
R
=
{
((
p, q
)
,
(
p
0
, q
0
)) : (
p, q
)
∼
(
p
0
, q
0
)
}
.
Пример 2.
Пусть
Z
- множество целых чисел и
m
≥
1
- некоторое целое
число. Отношение эквивалентности
R
на
Z
определим так, чтобы
p
∼
q
в
точности тогда, когда число
p
−
q
делится на
m.
Итак,
R
=
{
(
p, q
)
∈
Z
×
Z
:
p
∼
q
}
.
Пример 3.
Пусть
X
– множество прямых на плоскости (или в простран-
стве).
Определим
отношение
эквивалентности
на
X
следующим
образом:
A
∼
B
, если прямые
A
и
B
параллельны или совпадают.
Пример 4.
Рассмотрим множество
Y
, всех направленных отрезков про-
странства (плоскости). Два направленных отрезка
~
AB
и
~
CD
называются
эквивалентными, если они имеют одинаковую длину, лежат на параллель-
ных прямых и одинаково направлены. Так, введенное бинарное отношение
(множество пар эквивалентных направленных отрезков) является отношени-
ем эквивалентности.
Другие важные примеры отношений эквивалентности будут рассмотре-