Множество (стр. 4 )

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

Определение 2. Областью значений отношения ρ () будем называть множество .

Прямое произведение множеств

Определение. Множество всех упорядоченных пар таких, что х есть элемент некоторого фиксированного множества Х, а у – элемент некоторого фиксированного множества Y называется прямым произведением множеств X и Y, и обозначается .

Символически это определение записывается в виде

.

Любое отношение ρ есть подмножество некоторого прямого произведения , такого, что и .

Если ρ – отношение: , то говорят, что ρ есть отношение от X к Y.

Если и , то ρ есть отношение от Z к Z.

Отношения от Z к Z называют отношениями в Z.

Пример 1. Даны множества и . Найти и .

,

.

Этот пример показывает, что , т. е. результат прямого произведения зависит от порядка сомножителей.

Упражнения.

1. Доказать с помощью примера, что .

2. Теорема 1. Для операции прямого произведения относительно объединения множеств, справедлив дистрибутивный закон

.

3. Теорема 2. Если А содержит m элементов, а множество В n элементов, то прямое произведение содержит mn элементов.

Для доказательства множества А и В представить в виде

, .

Рассмотрим бинарные отношения на прямом произведении с равными сомножителями .

Свойства бинарных отношений на

1. Бинарное отношение R на множестве называется рефлексивным, если для любого элемента а из S пара принадлежит R.

2. Бинарное отношение R на множестве называется симметричным, если для любых элементов а и b из S из того, что пара следует, что пара .

3. Бинарное отношение R на множестве называется транзитивным, если для любых элементов а, b и с из S из того, что пара и следует, что пара .

Пример 1. Z – множество целых чисел. Зададим на бинарное отношение ρ: , если . Определим свойства ρ:

1) для любого а из Z верно , т. е. , другими словами ρ – рефлексивно.

2) из того, что не следует, что и, следовательно, ρ не является симметричным.

3) если и , то , т. е. ρ – транзитивно.

4. Бинарное отношение R на множестве S () называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Пример 2. Пусть N – множество натуральных чисел. На зададим бинарное отношение R: , если разность чисел a и b делится на 3.

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

Определим отношение сравнимости по модулю n в Z, .

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

Лекция 3.

Связь между отношением эквивалентности и разбиением на классы

Теорема. Каждому разбиению множества М соответствует отношение эквивалентности на множестве . Каждому отношению эквивалентности на множестве соответствует разбиение множества М.

Доказательство. 1о. Пусть М – произвольное множество. Дано некоторое разбиение М на классы. Покажем, что всегда можно построить отношение эквивалентности на множестве . Зададим бинарное отношение R с помощью закона: , если все элементы a и b лежат в одном классе разбиения множества М.

Для любого а из М пара , так как всякий элемент а находится в одном классе сам с собой. Значит, R рефлексивно. По отношению к каждому a и b из М можно сказать, что если a и b лежат в одном классе разбиения, то b и a лежат в одном классе разбиения. Следовательно, если , то и . Значит R симметрично.

Для любых трех элементов из множества М справедливо следующее утверждение: