ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 2330
Скачиваний: 10
ГЛАВА 2. БИНАРНЫЕ ОТНОШЕНИЯ
§ 1. Определение и способы задания отношений
Подмножество
ϕ
множества
A
n
(
ϕ
⊆
A
n
)
называется
n
-мест-
ным отношением на множестве
A
.
Говорят, что элементы
(
a
i
1
, . . . , a
i
n
)
находятся в отношении
ϕ
,
если
(
a
i
1
, . . . , a
i
n
)
∈
ϕ
.
Одноместное отношение — это просто подмножество
ϕ
множества
A
(
ϕ
⊆
A
)
. Такие отношения называют свойствами или признаками:
свойство четности чисел, признак делимости на
3
и т. д.
Наиболее часто встречающимися являются двуместные или бинар-
ные отношения. Ниже будем рассматривать только бинарные отношения,
поэтому для краткости слово
бинарные
будем опускать. Если
a
и
b
находятся в отношении
ϕ
, то пишут
(
a, b
)
∈
ϕ
или
aϕb
.
Примерами отношений на множестве вещественных чисел являют-
ся отношения:
≤
,
≥
,
<
,
>
,
=
. На множестве нату-
ральных чисел рассмотрим отношения: а) иметь один и тот же остаток
от деления на
5
; б) иметь общий делитель, отличный от
1
. На
множестве плоских прямых отметим отношения параллельности, перпен-
дикулярности, симметричности относительно начала координат и др.
Областью определения отношения
ϕ
на множестве
A
называет-
ся множество тех
x
∈
A
, для которых существует
y
∈
A
такое, что
(
x, y
)
∈
ϕ
.
Областью значений отношения
ϕ
на множестве
A
называется
множество тех значений
x
∈
A
, для которых существует
y
∈
A
такое, что
(
y, x
)
∈
ϕ
.
Рассмотрим способы задания отношений. Для задания отношений
можно использовать любые способы задания множеств (например, от-
ношение может быть задано списком пар, для которых это отношение
выполняется). Отношения на конечном множестве могут быть заданы в
виде таблицы (матрицы).
Таблица бинарного отношения
ϕ
на множестве
A
= (
a
1
, . . . , a
m
)
содержит
m
строк и столько же столбцов, на пересечении
i
-й строки и
j
-го столбца находится элемент
c
ij
, который определяется следующим
образом:
c
ij
=
(
1
,
если
(
a
i
, a
j
)
∈
ϕ,
0
,
если
(
a
i
, a
j
)
/
∈
ϕ,
∀
i, j
= 1
, m.
Так, для бинарных отношений
ϕ
=
{
(
M
,
)
,
(
♦
,
M
)
,
(
M
,
M
)
,
(
,
M
)
}
и
ϕ
−
1
=
{
(
,
M
)
,
(
M
,
♦
)
,
(
M
,
M
)
,
(
M
,
)
}
на множестве
M
=
{
M
,
,
♦
}
16
таблицы будут иметь следующий вид:
i
j
M ♦
M
1
1
0
1
0
0
♦
1
0
0
i
j
M ♦
M
1
1
1
1
0
0
♦
0
0
0
Отношение также можно задать с помощью рисунка, который назы-
вают графом. Каждому элементу
x
i
∈
A
,
i
= 1
, n
, на плоскости ставится
в соответствие точка, которую также обозначают через
x
i
. Пара точек
x
i
и
x
j
соединяется направленным отрезком или кривой тогда и только
тогда, когда пара точек
(
x
i
, x
j
)
∈
ϕ
,
i, j
= 1
, n
. Для вышезаданного
отношения
ϕ
построим граф (см. рис. 8).
Рис. 8: Граф отношения
ϕ
§ 2. Операции над отношениями
Поскольку отношения на множестве
A
являются подмножествами
множества
A
2
, для них можно определить те же операции, что и для
множеств: объединение, пересечение, дополнение, разность. Так отно-
шение
≤
на множестве натуральных чисел является объединением
отношений
<
и
=
. Отношение
>
является дополнением от-
ношения
≤
, а отношение равенства
=
является пересечением
отношений
≤
и
≥
на множестве действительных чисел.
Отношение
ϕ
−
1
называется обратным к отношению
ϕ
, если
(
x, y
)
∈
ϕ
−
1
тогда и только тогда, когда
(
y, x
)
∈
ϕ
.
Произведением отношений
ϕ
1
и
ϕ
2
на множестве
A
называется
отношение
ϕ
1
◦
ϕ
2
, состоящее из пар
(
x, y
)
, для которых существует
элемент
z
∈
A
, такой, что
(
x, z
)
∈
ϕ
1
и
(
z, y
)
∈
ϕ
2
:
ϕ
1
◦
ϕ
2
=
{
(
x, y
)
|∃
z
(
x, z
)
∈
ϕ
1
,
(
z, y
)
∈
ϕ
2
}
.
Транзитивным замыканием отношения
ϕ
на множестве
A
на-
зывается отношение
b
ϕ
, которое определяется следующим образом:
17
(
x, y
)
∈
b
ϕ
тогда и только тогда, когда существует цепочка из ко-
нечного числа элементов
x
=
x
1
, x
2
, . . . , x
k
=
y
, в которой для каждой
пары соседних элементов выполняется отношение
ϕ
:
(
x
i
, x
i
+1
)
∈
ϕ
,
∀
i
= 1
, k
−
1
.
Транзитивным замыканием отношения
быть сыном
является от-
ношение
быть прямым потомком
. Оно представляет собой объедине-
ние отношений
быть сыном
,
быть внуком
,
быть правнуком
и
т. д. Транзитивным замыканием
жить в одном городе
является то же
отношение.
§ 3. Свойства отношений
Отношение
ϕ
на множестве
A
называется рефлексивным, если
(
x, x
)
∈
ϕ
для
∀
x
∈
A
, и антирефлексивным в противоположном слу-
чае:
(
x, x
)
/
∈
A
,
∀
x
∈
A
.
Примерами рефлексивных отношений являются отношения
≤
,
=
и
≥
на произвольном числовом множестве.
Отношения
x < y
,
быть сыном
,
быть старше
являются
примерами антирефлексивных отношений.
Отношение
ϕ
на множестве
A
называется симметричным, если
из
(
x, y
)
∈
ϕ
следует
(
y, x
)
∈
ϕ
. Отношение
ϕ
называется антисим-
метричным, если из
(
x, y
)
∈
ϕ
и
(
y, x
)
∈
ϕ
следует
x
=
y
.
Отношения
жить в одном городе
,
иметь общий делитель, от-
личный от 1
на множестве целых чисел,
быть симметричным отно-
сительно оси
на множестве точек плоскости являются примерами сим-
метричных отношений. Отношения
<
,
>
,
≤
,
≥
на
R
,
отношение включения
⊆
на Б
(
A
)
являются антисимметричными.
Таблица (матрица) симметричного отношения симметрична относи-
тельно главной диагонали (
c
ij
=
c
ji
для всех
i, j
= 1
, m
).
Теорема.
Отношение
ϕ
симметрично тогда и только тогда, ко-
гда
ϕ
−
1
=
ϕ
.
Доказательство. Действительно, пусть
ϕ
=
ϕ
−
1
:
(
x, y
)
∈
ϕ
⇒
(
y, x
)
∈
ϕ
−
1
=
ϕ
, что означает симметричность
ϕ
. Наоборот, если
ϕ
— симметрично, то
(
x, y
)
∈
ϕ
⇔
(
y, x
)
∈
ϕ
⇔
(
x, y
)
∈
ϕ
−
1
, следователь-
но
ϕ
=
ϕ
−
1
. Теорема доказана.
Отношение
ϕ
на множестве
A
называется транзитивным, если
для любых
x
,
y
,
z
из множества
A
из
(
x, y
)
∈
ϕ
,
(
y, z
)
∈
ϕ
следует
(
x, z
)
∈
ϕ
.
Отношения
<
,
≥
,
=
на множестве действительных чи-
сел, отношение параллельности прямых, отношение
быть соседом
так-
же являются транзитивными. Отношение перпендикулярности прямых,
18
отношение
иметь общий делитель, отличный от 1
на множестве на-
туральных чисел свойством транзитивности не обладают.
Теорема.
Если
ϕ
— транзитивное отношение, то
ϕ
=
b
ϕ
.
Доказательство. Из определения транзитивности замыкания следу-
ет, что
ϕ
⊆
b
ϕ
. Пусть
(
x, y
)
∈
b
ϕ
, тогда существует последователь-
ность
x
=
x
1
, x
2
, . . . , x
k
=
y
элементов из
A
таких, что
(
x
1
, x
2
)
∈
ϕ
,
(
x
2
, x
3
)
∈
ϕ
,
. . .
,
(
x
k
−
1
, x
k
)
∈
ϕ
, откуда в силу транзитивности
ϕ
полу-
чаем
(
x, y
) = (
x
1
, x
k
)
∈
ϕ
. Так как
(
x, y
)
произвольная пара из
b
ϕ
, то
b
ϕ
⊆
ϕ
, что и доказывает утверждение теоремы.
§ 4. Отношение эквивалентности
Отношение называется отношением эквивалентности (или про-
сто эквивалентностью), если оно рефлексивно, симметрично и тран-
зитивно
.
Будем говорить, что имеет место разбиение множества
A
на
классы, если существует система
{
A
1
, A
2
, . . . , A
k
}
непустых, попарно
не пересекающихся множеств такая, что
A
i
6
=
, A
=
[
k
A
k
, A
i
\
A
j
=
, i
6
=
j.
(2
.
1)
Теорема
.
Между совокупностью различных разбиений множества
A
на классы и семейством всех отношений эквивалентности на этом
множестве существует взаимнооднозначное соответствие
.
Доказательство. Пусть имеет место разбиение
(2
.
1)
множества
A
на классы. Построим отношение
ϕ
на множестве
A
по правилу: для
∀
x, y
∈
A
пара
(
x, y
)
∈
ϕ
, если элементы
x
,
y
принадлежат одному
и тому же классу
A
i
в представлении
(2
.
1)
. Рефлексивность и сим-
метричность этого отношения очевидны, покажем его транзитивность.
Пусть
(
x, y
)
∈
ϕ
и
(
y, z
)
∈
ϕ
. Это означает, что
x
и
y
принадлежат
классу
A
k
и одновременно
y
и
z
принадлежат классу
A
l
. Если
k
6
=
l
,
то получается, что элемент
y
принадлежит двум различным классам.
Последнее противоречит тому, что
A
k
∩
A
l
=
. Поэтому
k
=
l
, все эле-
менты
x
,
y
и
z
принадлежат одному классу, откуда следует
(
x, z
)
∈
ϕ
.
Мы доказали, что
ϕ
— отношение эквивалентности.
Пусть
ϕ
— произвольное отношение эквивалентности на множе-
стве
A
. Построим разбиение этого множества на классы. С этой це-
лью выберем произвольный элемент
a
1
∈
A
и определим класс
A
1
следующим образом:
A
1
=
{
x
∈
A
|
(
a
1
, x
)
∈
ϕ
}
. Класс
A
1
не пуст,
так как в силу рефлексивности
ϕ
элемент
a
1
∈
A
1
. Выберем элемент
a
2
∈
A
\
A
1
и построим класс
A
2
:
A
2
=
{
x
∈
A
|
(
a
2
, x
)
∈
ϕ
}
. Построив
19
классы
A
1
,
A
2
,
. . .
,
A
k
, выбираем элемент
a
k
+1
∈
A
\
S
k
i
=1
A
i
и класс
A
k
+1
=
{
x
∈
A
|
(
a
k
+1
, x
)
∈
ϕ
}
. Элемент
a
i
назовем представителем клас-
са
A
i
, i
= 1
,
2
, . . .
Процесс продолжается до тех пор, пока
A
\
S
A
i
6
=
.
В результате получим представление
A
=
S
A
i
. Покажем, что оно явля-
ется разбиением множества
A
на классы, а именно
A
i
T
A
j
=
,
i
6
=
j
.
Предположим, что последнее не верно: существует элемент
x
0
∈
A
,
классы
A
p
и
A
q
такие, что
x
0
∈
A
p
,
x
0
∈
A
q
,
p
6
=
q
– тогда
(
a
p
, x
0
)
∈
ϕ
,
(
a
q
, x
0
)
∈
ϕ
. В силу симметричности и транзитивности
ϕ
получаем
(
a
p
, a
q
)
∈
ϕ
, а поэтому
a
q
∈
A
p
, что противоречит выбору элемента
a
q
. Теорема доказана.
Если
ϕ
отношение эквивалентности на
A
и
A
=
S
A
i
, соот-
ветствующее ему разбиение множества
A
на классы, то множества
A
1
,
. . .
,
A
k
,
. . .
называются классами эквивалентности, а семейство
{
A
i
}
обозначается символом
A/ϕ
и называется фактор-множеством
множества
A
по отношению
ϕ
.
Мощность множества
A/ϕ
называется индексом разбиения
.
Фактор-множество множества
N
по отношению
иметь общий оста-
ток от деления на 5
состоит из пяти счетных классов:
A
1
=
{
1
,
6
,
11
, . . .
}
,
A
2
=
{
2
,
7
,
12
, . . .
}
,
A
3
=
{
3
,
8
,
13
, . . .
}
,
A
4
=
{
4
,
9
,
14
, . . .
}
,
A
5
=
{
5
,
10
,
15
, . . .
}
.
§ 5. Отношение порядка
Отношение
ϕ
на множестве
A
называется отношением нестро-
гого порядка, если оно рефлексивно, антисимметрично и транзитивно
.
Отношение
ϕ
на
A
называется отношением строгого порядка,
если оно антирефлексивно, антисимметрично и транзитивно
.
Говорят, что два элемента
x
и
y
из множества
A
сравнимы по
отношению порядка
ϕ
, если
(
x, y
)
∈
ϕ
или
(
y, x
)
∈
ϕ
.
Множество
A
, на котором задано отношение порядка (строгого или
нестрогого), называется полностью упорядоченным, если любые его два
элемента сравнимы, и частично упорядоченным, если это не так.
Пусть множество
A
упорядочено отношением порядка
ϕ
.
Элемент
x
∈
A
называется наибольшим элементом множества
A
, если для всех
y
∈
A
имеет место отношение
(
y, x
)
∈
ϕ
.
Наиболь-
ший элемент множества
A
обозначают
max
A
.
Элемент
x
∈
A
называется наименьшим элементом множества
A
, если для всех
y
∈
A
имеет место отношение
(
x, y
)
∈
ϕ
.
Наимень-
ший элемент множества
A
обозначают
min
A
.
Из этих определений следует, что наибольший и наименьший эле-
20