Разбиение на классы. Отношение эквивалентности

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

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

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

Пусть М – некоторое множество и пусть некоторые из пар (а, b)

элементов этого множества являются выделенными. Если (а, b) – выделенная пара, то мы будем говорить, что элемент а связан с b отношением j, и обозначать это символом а j b или(а, b) Îj. Например, если имеется в виду разбиение треугольников на классы равновеликих, то а j b означает «треугольник а имеет ту же площадь, что и треугольник b».

Определение. Отношение j называется отношением эквивалентности, если оно обладает следующими свойствами:

1) рефлексивность: а j а для любого элемента а Î М,

2) симметричность: если а j b, то b j а,

3) транзитивность: если а j b и b j c, то a j c.

Эти условия необходимы и достаточны для того, чтобы отношение j (признак!) позволяло разбить множество М на классы.

Понятие эквивалентности является частным случаем более общего понятия бинарного отношения.

Прямым (декартовым) произведением множеств А₁, …, А_n называется множество А₁´…´А_n = {(a ₁, …, a _n) | a ₁ Î А₁, …, a _n Î А_n}.

Если А₁ = … = А_n = А, то множество А₁´…´А_n называется прямой степенью множества А и обозначается через Аⁿ.

Бинарным отношением между элементами множеств А и В называется любое подмножество R множества А´В. Если А = В, то отношение R называется бинарным отношением на А. Вместо (х, у) Î R часто пишут х R у, т.е.высказывание: «предметы и связаны бинарным отношением » записывают в виде Если , то говорят, что бинарное отношение определено на множестве .

Примером бинарного отношения может служить отношение тождества e: (а, b) Î e в том и только том случае, если а = b. Иначе говоря, это – отношение, задаваемое диагональю D в М´М, т.е. подмножеством пар вида (а, а).

Областью определения бинарного отношения R называется множество d_R = { x | существует у такое, что (х, у) Î R}.

Областью значений бинарного отношения R называется множество r_R = { x | существует у такое, что (у, х) Î R}.

Для бинарных отношений определены обычным образом теоретико-множественные операции объединения, пересечения и т.д.