Шептунов М. В. - Теория множеств (1023559), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Общее определение эквивалентности можно получить, записав три вышеприведённых условия в виде следующих соотношений:

1. xx (рефлексивность);

2. xy yx (симметричность);

3. xy и yz  xz (транзитивность).

Т. о., вырисовывается следующее определение эквивалентности:

Определение 2.2. Отношение R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Отношение эквивалентности находится в тесной связи с

разбиением множества. Пусть X – множество, на котором определено отношение эквивалентности. Например, X – это множество студентов курса, а отношением эквивалентности является отношение “быть в одной группе”.

Определение 2.3. Подмножество элементов, эквивалентных некоторому элементу xX, называется классом эквивалентности.

Например, группа, в которой учится студент Иванов, будет классом эквивалентности, эквивалентным студенту Иванову.

Определение 2.4. Отношение эквивалентности на множестве X и разбиение этого множества на классы называются сопряжёнными, если для любых x и y из X отношение xy выполняется тогда и только тогда, когда x и y принадлежат к одному и тому же классу A_j этого разбиения.

В качестве общего символа отношения эквивалентности используется символ  либо  . Что же касается частных случаев эквивалентности, таких как параллельность, логическая эквивалентность и прочие, то здесь используются соответствующие им значки ( // ,  ).

В теории множеств применяется понятие “отношение порядка”.

Определение 2.5. Отношением порядка называют антисимметричное транзитивное отношение.

Если отношение порядка рефлексивно, то оно называется отношением нестрогого порядка; если антирефлексивно, то отношением

строгого порядка.

Отношение порядка может быть полным (линейным), и тогда оно называется отношением полного, или линейного, порядка. В противном случае оно имеет название частичного порядка.

В общем случае отношение порядка обозначается знаком:

.

В тех случаях, когда X означает множество людей или групп

людей, приходится сталкиваться с отношением, которое является отношением доминирования.

Определение 2.6. Доминированием x над y в теории множеств называется выражаемое математически превосходство x над y, что обозначается:

x>>y.

Например, x может быть спортсменом либо спортивной командой, победившей спортсмена либо команду y. Это также может быть выигравший на выборах в губернаторы или куда-либо ещё, и соответственно проигравший на этих выборах.

Запишем необходимые и достаточные условия доминирования

(должны одновременно выполняться следующие два условия):

1. никакой индивидуум не может доминировать самого себя, т. е.

x>>x

является ложным (антирефлексивность);

1. в каждой паре индивидуумов в точности один индивидуум

доминирует над другим, т. е. несимметричность:

x>>y и y>>x – взаимоисключаются.

Свойство транзитивности в отношении доминирования смысла не имеет. В частности, если в соревнованиях команда x победила команду y, а команда y победила команду z, то отсюда ещё не следует, что

команда x обязательно победит команду z.

2.2. Матрица бинарного отношения и её применение

Рассмотрим два конечных множества

,

и бинарное отношение

.

Определим матрицу

размера бинарного отношения P по следующему правилу:

1

p_ij=

, если

0, если .

Полученная матрица содержит полную информацию о связях между элементами и позволяет представлять эту информацию в электронной форме для ЭВМ. Следует отметить, что любая матрица из единиц и нулей является матрицей какого-либо бинарного отношения.

Пример 2.2. Матрица бинарного отношения , A={1, 2, 3} (рис. 2.2), имеет вид

[P]= .

1

2

3

Рис. 2.2. К понятию матрицы бинарного отношения

Перечислим основные свойства матриц бинарных отношений.

1. Если

,

, ,

то

и

,

где сложение осуществляется по правилам:

;

,

а умножение осуществляется обычным образом. Итак,

,

а матрица получается перемножением соответствующих элементов из [P] и [Q]:

.

Пример 2.3. Пусть [P]= , [Q]= – матрицы

отношений P и Q.

Тогда

,

.

1. Если

, ,

то

,

где умножение матриц [P] и [Q] производится по обычному правилу

умножения матриц, но произведение и сумма элементов из [P] и [Q] – по правилам, указанным в предыдущем п. 1.

Пример 2.4. Если , , то

.

1. Матрица обратного отношения равна транспонированной

матрице отношения P:

.

4. Если

,

, ,

то

.

5. Матрица тождественного отношения id_A единична:

[id_A] = .

Пусть P – бинарное отношение на множестве A:

.

Рассмотрим понятия рефлексивного, симметричного, антисимметричного и транзитивного отношений.

Определение 2.7. Отношение P называется рефлексивным, если для всех , т. е.

,

[P] = .

Определение 2.8. Отношение P называется симметричным, если для любых из следует , т. е.

,

или

.

Определение 2.9. Отношение P называется антисимметричным, если из и следует, что , т. е.

.

На языке матриц это означает, что в матрице все элементы вне главной диагонали являются нулевыми.

Определение 2.10. Отношение P называется транзитивным, если из и следует , т. е.

.

Необходимо отметить, что антисимметричность не совпадает с несимметричностью. Действительно, отношение

на множестве

A={1, 2, 3}

не симметрично (так как , а ) и не антисимметрично (поскольку , но и ). Тождественное отношение id_A является одновременно симметричным и антисимметричным.

Пример 2.5. Выясним, какими свойствами обладает отношение

, A={1, 2, 3},

изображённое на рис. 2.3.

Составим матрицу отношения P:

.

Так как в матрице [P] на главной диагонали имеются нулевые элементы, отношение P не рефлексивно. Несимметричность матрицы [P] означает, что отношение P не симметрично. Для проверки антисимметричности вычислим матрицу

.

Имеем

.

Поскольку в полученной матрице все элементы, стоящие вне главной диагонали, нулевые, отношение P антисимметрично. Кроме того,

поскольку для рассматриваемого случая

,

то, следовательно,

,

т. е. отношение P является транзитивным.

2 3

1

Рис. 2.3. Пример отношения , A={1, 2, 3}

2.3. Соответствия

Рассмотрим два множества X и Y. Элементы этих двух множеств могут каким-либо образом сопоставляться друг с другом, образуя пары (x, y).

Определение 2.11. Если способ сопоставления двух множеств X и Y определён, т. е. если для элемента xX указан элемент yY, с которым сопоставляется элемент x, то говорят о наличии соответствия между двумя множествами. При этом совершенно необязательно, чтобы в сопоставлении участвовали все элементы множеств X и Y.

Для задания соответствия необходимо указать:

1. множество X, элементы которого сопоставляются с элементами

другого множества;

1. множество Y, с элементами которого сопоставляются элементы

первого множества;

3) множество , определяющее закон, согласно которому

осуществляется соответствие.

Соответствие, обозначенное через q, представляет собой тройку множеств

,

где .

Определение 2.12. В вышеуказанном выражении первая компонента X называется областью отправления соответствия, вторая компонента Y называется областью прибытия соответствия, третья компонента Q называется графиком соответствия.

Кроме того, с каждым соответствием неразрывно связаны ещё два множества:

1) Пр₁ Q, называемое областью определения соответствия (в него

входят элементы множества X, участвующие в сопоставлении);

2) Пр₂ Q, называемое областью значений соответствия (в него

входят элементы множества Y, участвующие в сопоставлении).

Пример 2.6. На предприятии имеются три автомашины: две грузовые  и , работающие в две смены, и автобус , используемый редко. Машина  находится в ремонте. В штате имеются три шофёра a, b, c, из которых с находится в отпуске. Распределение шоферов по машинам представляет собой соответствие. Одним из возможных соответствий будет следующее:

.

Геометрически это соответствие изображается, как показано на рис. 2.4, а. На этом рисунке элемент  соответствует элементам a и b, а элемент  соответствует элементу a. Соответствие q определено на a и b, но не определено на c, следовательно, областью определения соотвествия является множество {a, b}. Областью значений соответствия является множество {, }.

Характеристики

Список файлов книги