ЭКВИВАЛЕНТНОСТИ ОТНОШЕНИЕ (эквивалентность, эквиваленци я) на множестве

— рефлексивное, симметричное и транзитивное бинарное отношение, т. е. такое подмножество Е прямого произведения А У. А, которое удовлетворяет следующим трем условиям: для всякого а из ; если , то ; если , то .

Простейшими примерами Э. о. являются отношение равенства, состоящее из всех пар вида , а также Э. о., совпадающее с множеством А х А. Всякое Э. о. Е на мн-ве А определяет разбиение А на попарно непересекающиеся классы эквивалентности или ), и обратно, каждое разбиение мн-ва А однозначно определяет Э. о. на А. Мощность мн-ва всех классов (т. е. фактор-множества по Е) наз. рангом Э. о. Е.

Пересечение любого мн-ва Э. о. (на одном и том же мн-ве А) является снова Э. о. Суммой двух Э. о. транзитивное замыкание объединения . Очевидны следующие неравенства:

Всякое Э. о. Е на множестве А распространяется на множество функций, отображающих А в А:

Чтобы распространить Е на мн-во ф-ций от нескольких аргументов, сначала распространяют Е на мн-во кортежей элементов из А покомпонентно:

Всякая ф-ция отображающая А в В, порождает Э. о. на А, которое наз. иногда ядром функции Для каждого класса А синтаксических объектов с ф-цией значения (приписывающей каждому а из А некоторое значение считается естественным Э. о. на А. Напр., термы произвольной алгебры эквивалентны, если они изображают одинаковые ф-ции; автоматы эквивалентны, если они имеют одинаковое поведение; программы эквивалентны, если они вычисляют одинаковые функции; номера эквивалентны, если они являются номерами одного и того же объекта.

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

Лит.: Новиков П. С. Об алгоритмической неразрешимости проблемы тождества. «Доклады АН СССР», 1952, т. 85; Мальцев А. И. Алгоритмы и рекурсивные функции. М., 1965 [библиогр. с. 375- 381 ]; Мальцев А. И. Алгебраические системы. М., 1970 [библиогр. с. 384—387]. Ю. И. Янов.