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

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

Пример:

а) Отношение равенства Е на любом множестве является отношением эквивалентности.

Равенство - это минимальное отношение эквивалентности в том смысле, что при удалении любой пары из Е (т. е. любой единицы на диагонали матрицы Е) оно перестает быть рефлексивным и, следовательно, уже не является эквивалентным;

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

Определение: Формулы равносильны, если они задают одну и ту же функцию.

Равносильность хотя и обозначается знаком равенства: “=”, но по сути отличается от отношения равенства Е, так как оно может выполняться для различных формул (впрочем, можно считать, что знак равенства в таких соотношениях относится не к формулам, а к функциям, которые ими описываются). Отношение Е (равенства) для формул - это совпадение формул по написанию. Оно называется графическим равенством;

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

г) отношение “иметь один и тот же остаток от деления на 7” является эквивалентностью на N. Это отношение выполняется для пар (11, 46), (14, 70) и не выполняется для пар (12, 13), (14, 71).