Определение. Пусть

— множества. Множество упорядоченных пар
, где
,
, называется декартовым произведением множеств и обозначается
. Упорядоченных значит, что порядок в паре

имеет значение.
Определение. Пусть

— множества. Бинарное отношение

на множествах

и

задается выбором подмножества декартова произведения
. Если пара
, то пишут
.
Следующее определение получается из этого при
.
Определение. Пусть

— множество. Бинарное отношение на множестве

задается выбором подмножества декартова произведения
. Если пара
, то также пишут
.
Пример. Пусть

— множество людей. Если

влюблен в
, то это можно записать как бинарное отношение
. Причем из того, что

влюблен в
, вообще говоря, не следует, что

влюблен в
. То есть может быть
, но не быть
. Важен порядок.
Некоторый элемент

может ни с кем не быть в отношении
. Как в качестве влюбленного (то есть не существует

такого, что
). Также в качестве того, в кого влюблены (не существует

такого, что
).
Какой-то

может состоять в отношении

одновременно с несколькими. Как на первом месте
(
может быть влюблен сразу в нескольких людей, то есть имеет место

и
). Так и на втором месте (в

влюблены несколько человек:

и
).
Также не исключено, что

нарцисс и
.
Бинарное отношение

на множестве

может обладать различными свойствами, например:

— рефлексивность.

— симметричность.

— транзитивность.

— антисимметричность.
Определение. Рефлексивное, симметричное, транзитивное бинарное отношение называют отношением эквивалентности. Обычно обозначают
.
Свойства отношения эквивалентности:
1)

— рефлексивность;
2)

— симметричность;
3)

— транзитивность.
Определение. Рефлексивное, антисимметричное, транзитивное бинарное отношение называют отношением порядка (частичного порядка). Обычно обозначают
.
Свойства отношения порядка:
1)

— рефлексивность;
2)

— антисимметричность;
3)

— транзитивность.
Функцию

также можно считать бинарным отношением на множествах

и
. Чтобы быть классической однозначной функцией, бинарное отношение

должно удовлетворять следующему условию:

найдется и единственный

такой, что
. Заметим, что множество

является ничем иным, как графиком функции
. С такой точки функция

по сути задается своим графиком, или множеством пар
, где
.
С другой стороны, бинарные отношение можно считать обобщением понятия функция (отображение).
Далее сформулируем и докажем свойства отношения эквивалентности.
Утверждение. Отношение эквивалентности

на множестве

разбивает множество

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

лежит в множестве такого вида, а именно
, поскольку

ввиду рефлексивности. Из этого также следует, что множество
.
Так как любое
, то можно записать, что
.Покажем, что множества вида
![$[a]$ $[a]$](/getteximg?%5Ba%5D)
либо не пересекаются, либо совпадают.
Сначала покажем, что если
, то
. Так как
, то по определению

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

и

следует
, то есть
. Следовательно,
.
Если
, то по определению
. Ввиду транзитивности из

и

следует
, то есть
. Следовательно,
.
Таким образом,
.
Допустим, что множества
![$[a]$ $[a]$](/getteximg?%5Ba%5D)
и
![$[b]$ $[b]$](/getteximg?%5Bb%5D)
пересекаются, то есть содержат какой-то общий элемент
. Тогда по доказанному
![$c \in [a]$ $c \in [a]$](/getteximg?c%20%5Cin%20%5Ba%5D)
и, следовательно,
. В то же время,
![$c \in [b]$ $c \in [b]$](/getteximg?c%20%5Cin%20%5Bb%5D)
и, следовательно,
. В итоге
.