extern volatile world

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

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

EDIT: В комментариях мне подсказали, что существование такой функции есть прямое следствие аксиомы выбора в общем случае. В случае если базовое множество полностью упорядочено, то аксиома выбора не нужна — представителя класса эквивалентности можно определить как минимальный элемент. Строгого доказательства что аксиома выбора нужна в общем случае у меня нет.

www.tgoop.com/extern_world/393

1.1K viewsDmitry Bogatov, edited  Apr 13, 2021 at 22:57

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

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

EDIT: В комментариях мне подсказали, что существование такой функции есть прямое следствие аксиомы выбора в общем случае. В случае если базовое множество полностью упорядочено, то аксиома выбора не нужна — представителя класса эквивалентности можно определить как минимальный элемент. Строгого доказательства что аксиома выбора нужна в общем случае у меня нет.

BY extern volatile world