4. Отношения

Бинарным отношением на множестве называется пара , где область задания отношения, а – график отношения.

Если , то будем писать и говорить, что и вступают в отношение . Если и не вступают в отношение , будем писать .

Диагональю множества называется график .

Свойства отношений:

1. Рефлексивность: .

2. Антирефлексивность: .

3. Симметричность: .

4. Антисимметричность: или равносильное определение: .

5. Транзитивность: .

6. Связность: .

Эти свойства можно определить с помощью графиков отношений:

1. , 2. , 3. ,

4. , 5. , 6. .

Операции над отношениями и сводятся к операциям над их графиками:

, , ,

, .

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

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

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

Отношение называется отношением строгого линейного порядка, если оно – связное отношение строгого порядка.

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

Классом эквивалентности, порождённым элементом , называется множество всех элементов из , вступающих с в отношение эквивалентности.

Фактор-множеством множества по отношению эквивалентности называется множество всех различных классов эквивалентности, которое обозначается .

Мощность фактор-множества называется индексом разбиения, порождённого отношением .

Задание 4.1. Проверить для произвольных отношений и справедливость утверждения: «Если отношения и обладают свойством , то отношение также обладает свойством ».

Обозначения: 1 – рефлексивность, 2 – антирефлексивность, 3 – симметричность, 4 – антисимметричность, 5 – транзитивность, 6 – связность.

Примеры решения задания 4.1.

Пример 1.

Проверить для произвольных отношений и справедливость утверждения: «Если отношения и транзитивны, то отношение также транзитивно».

Решение. Пусть . Тогда и

.

Отношение не транзитивно, так как его график содержит пары и , но не содержит пару . Значит, в общем случае утверждение, приведённое в примере 1, неверно.

Пример 2.

Проверить для произвольных отношений и справедливость утверждения: «Если отношения и рефлексивны, то отношение также рефлексивно».

Решение. Для рефлексивных отношений и выполнены условия: , . Значит, выполнено также включение: , а это и означает, что отношение также рефлексивно.

Задание 4.2.

1. Выяснить, какими из свойств: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, связность обладает данное отношение .

2. Выяснить, что представляет из себя отношение , .

3. Построить на конечном множестве отношение, обладающее таким же набором свойств, что и данное. Изобразить его графом и аналитически.

4. Построить на бесконечном множестве отношение, обладающее набором свойств, противоположным данному. В случае невозможности построения доказать противоречивость набора требований.

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

Пример решения задания 4.2.

Решить задание 4.2 для случая, когда множество теннисистов, участвующих в турнире, где каждый теннисист должен сыграть с каждым ровно три партии. Пусть означает, что обыграл по результатам личных встреч.

1. Выясним, какими из основных свойств обладает данное отношение.

1 (рефлексивность). Отношение не является рефлексивным, так как найдётся теннисист, не обыгравший сам себя.

2 (антирефлексивность). Отношение является антирефлексивным, так как каждый теннисист не обыграл сам себя.

3 (симметричность). Отношение не является симметричным, так как найдётся пара теннисистов и такая, что обыграл по очкам в личных встречах, а не обыграл .

4 (антисимметричность). Отношение является антисимметричным, так как если обыграл , то обязательно не обыграл .

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

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

2. Выясним, что из себя представляют отношения , .

По определению композиции, означает, что найдётся такой, что и . То есть в отношение будут вступать такие пары спортсменов и , для которых найдётся такой теннисист , что обыграл , а обыграл .

Рассуждая аналогично, получим, что в отношение будут вступать такие пары спортсменов и , для которых найдётся теннисист такой, что обыграл , а проиграл . То есть график отношения будут образовывать пары, составленные из теннисистов, для которых найдётся хотя бы один спортсмен, которого они оба обыграли в турнире.

3. Построим на конечном множестве отношение, обладающее таким же набором свойств, что и данное. Пусть . Изобразим это отношение в виде графа (рис. 10). 1. Это отношение не является рефлексивным, так как . 2. Отношение антирефлексивно, так как и и .

Рис. 10

3 . Отношение не симметрично, так как и .

4. Отношение антисимметрично, так как и , и , и .

5. Отношение не транзитивно, так как и , но .

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

4. Построим на бесконечном множестве отношение рефлексивное, не антирефлексивное, симметричное, не антисимметричное, транзитивное и не связное.

Пусть , означает, что и имеют одинаковую дробную часть.

1. Отношение рефлексивно, так как любое число имеет одинаковую дробную часть само с собой.

2. Отношение не антирефлексивно, так как найдётся число (например, 1,32), имеющее одинаковую дробную часть само с собой.

3. Отношение симметрично, так как если и имеют одинаковую дробную часть, то и также имеют одинаковую дробную часть.

4. Отношение не антисимметрично, так как, например, числа 1,78 и не равны, и в то же время и .

5. Отношение является транзитивным, так как если и имеют одинаковую дробную часть, и имеют одинаковую дробную часть, то и также имеют ту же самую дробную часть.

6. Отношение не связно, так как, например, и и .

Это отношение рефлексивно, симметрично и транзитивно, значит, оно является отношением эквивалентности. Классами эквивалентности являются множества, состоящие из элементов с одной и той же дробной частью, что равносильно условию . Индекс разбиения, соответствующего данному отношению эквивалентности – континуальный, так как мощность фактор-множества равна мощности всевозможных дробных частей, то есть множеству точек промежутка .

Задание 4.3. Провести факторизацию отображения , если , , а значения заданы таблицей.

Пример решения задания 4.3.

Провести факторизацию отображения , если , , а значения таковы: ; ; ; ; .

Решение. Рассмотрим на множестве отношение , которое определим так: Это – отношение эквивалентности, которое порождает разбиение множества на классы эквивалентности.

В нашем примере имеем: ; ; . Эти классы образуют фактор-множество множества по отношению : . Заметим, что индекс разбиения множества равен 3. Введём соответствие так: . Легко заметить, что является отображением на . Для исходного отображения областью значений является множество .

Рассмотрим соответствие следующего вида: , заданное равенствами: , . Это соответствие всюду определено, сюръективно, функционально и инъективно, то есть биекция между множествами и

Рассмотрим, наконец, соответствие , . Это соответствие всюду определено, функционально и инъективно, то есть является взаимно-однозначным отображением в .

Итак, исходное соответствие можно представить в виде композиции соответствий и . В построении этой композиции и заключается факторизация отображения .

Задание 4.4.

Для данного отношения проделать следующее:

1. Изобразить графом.

2. Достроить до отношения эквивалентности, указать фактор-множество.

3. Достроить до отношения частичного порядка, указать максимальные, минимальные элементы, а также пары несравнимых элементов.

4. Достроить до отношения линейного порядка, указать наибольший и наименьший элементы.

5. Достроить до отношения строгого порядка.

6. Достроить до отношения строгого линейного порядка.

Замечание. Отношение достраивается с помощью введения минимального необходимого числа дополнительных рёбер.

Пример решения задания 4.4.

Решим задание для . Решение. 1. Изобразим граф отношения (рис. 11, а). 2. Достроим до отношения эквивалентности , добавляя минимально возможное число рёбер, обозначим график полученного отношения эквивалентности через . Тогда будет иметь вид: . Изобразим граф отношения (рис.1.4.4, б) Укажем фактор-множество для по отношению : . Отметим, что индекс разбиения множества равен 2.

Рис. 11, а Рис. 1.4.4, б

3 . Достроим до отношения частичного порядка , обозначив график этого отношения через .

.

Изобразим граф (рис. 11, в).

Минимальными элементами здесь являются 1 и 5, максимальными элементами – 2, 3 и 4. Пары несравнимых элементов: 4. Достроим до отношения линейного порядка , обозначив график этого отношения через .

Рис. 11, в

И зобразим граф отношения (рис. 11, г). Наибольшим элементом здесь является 3, а наименьшим – 5. 5. Само исходное отношение является отношением строгого порядка, так что достраивать его нет необходимости. 6. Достроим до отношения строгого линейного порядка , обозначим график этого отношения через .

Рис. 11, г

.

Изобразим граф отношения (рис. 11, д).

● Рис. 1.4.4, д

54