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

Аналогичным образом можно рассматривать декартовы произведения трёх и более множеств. Их подмножества будут называться тернарными и т.п. отношениями.

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

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

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

 

 

 

Рис.1 Рис.2 Рис.3

 

Другой способ задания бинарного отношения – использование стрелок. Элементы и изображаются в виде точек плоскости. Стрелками соединены те и только те элементы , для которых .(рис.2)

Это же бинарное отношение можно задать матрицей, состоящей из 0 и 1. Её строки соответствуют элементам множества , столбцы – элементам множества . Элемент этой матрицы равен 1 тогда и только тогда, когда он стоит на пересечении строки и столбца, соответствующих паре , для которой .

Определение 2.3. Элемент называется проекцией элемента на множество . Для произвольного подмножества его проекцие й на называется множество, состоящее из проекций на всех элементов множества .

Определение 2.4. Сечением множества называется множество элементов , для которых . Множество сечений отношения называется фактормножеством по отношению и обозначается .

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

Пусть даны множества и отношения .

Определение 2.5. Композиция отношений - это отношение между элементами множеств и такое, что для всех сечение множества по совпадает с сечением множества по подмножеству , т.е. .

Если даны две пары отношений , и , причём и , то операция композиции обладает следующим свойством: .

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

Предположим, что задано некоторое основное множество . Отношение называется отношением эквивалентности, если оно обладает такими свойствами:

1. Рефлексивностью: всякий элемент эквивалентен самому себе. Иными словами, для любого пара .

2. Симметричностью: для любых двух элементов из того, что эквивалентен следует, что эквивалентен . Другими словами, если , то . Это означает, что отношение совпадает со своим обратным, .

3. Транзитивностью: если эквивалентен , а эквивалентен , то эквивалентен . Иначе говоря, если и , то .

Очень часто отношение эквивалентности элементов обозначается так: .

Важным понятием является понятие класса эквивалентности. Класс эквивалентности элемента состоит из всех элементов , эквивалентных элементу . Для неэквивалентных элементов их классы эквивалентности не пересекаются. Множество классов эквивалентности называется фактормножеством множества по отношению и обозначается . Если взять ровно по одному элементу из каждого класса эквивалентности, получим систему представителей.

В качестве примера рассмотрим множество Z целых чисел. Зафиксируем произвольное целое число и назовём два целых числа сравнимыми по модулю (что обозначается ), если разность делится на . Легко видеть, определённое таким образом отношение обладает всеми свойствами отношения эквивалентности. Классы эквивалентности называются классами вычетов по модулю , в качестве системы представителей можно взять всевозможные остатки от деления на , т.е. числа . Это множество обозначается Z . На нём можно определить операции сложения и умножения естественным образом. Имеется в виду, что следует просуммировать вычеты, как обычные целые числа, разделить сумму на с остатком и этот остаток назвать суммой вычетов. Аналогично определим произведение вычетов.