Отношение частичной эквивалентности - Partial equivalence relation

В математика, а отношение частичной эквивалентности (часто сокращенно PER, в более древней литературе также называли ограниченное отношение эквивалентности) ${\displaystyle R}$ на съемочной площадке ${\displaystyle X}$ это бинарное отношение то есть симметричный и переходный. Другими словами, это справедливо для всех ${\displaystyle a,b,c\in X}$ который:

1. если ${\displaystyle aRb}$, тогда ${\displaystyle bRa}$ (симметрия)
2. если ${\displaystyle aRb}$ и ${\displaystyle bRc}$, тогда ${\displaystyle aRc}$ (транзитивность)

Если ${\displaystyle R}$ это также рефлексивный, тогда ${\displaystyle R}$ является отношение эквивалентности.

Свойства и приложения

В теория множеств, отношение ${\displaystyle R}$ на съемочной площадке ${\displaystyle X}$ является PER тогда и только тогда, когда, ${\displaystyle R}$ является отношением эквивалентности на подмножестве ${\displaystyle Y=\{x\in X|x\,R\,x\}\subseteq X}$. По конструкции, ${\displaystyle R}$ рефлексивно на ${\displaystyle Y}$ и, следовательно, отношение эквивалентности на ${\displaystyle Y}$. Фактически, ${\displaystyle R}$ может удерживать только элементы ${\displaystyle Y}$: если ${\displaystyle xRy}$, тогда ${\displaystyle yRx}$ по симметрии, поэтому ${\displaystyle xRx}$ и ${\displaystyle yRy}$ транзитивностью, то есть ${\displaystyle x,y\in Y}$. Однако с учетом набора ${\displaystyle X}$ и подмножество ${\displaystyle Y\subseteq X}$, отношение эквивалентности на ${\displaystyle Y}$ не обязательно быть PER на ${\displaystyle X}$; например, учитывая множество ${\displaystyle E=\{a,b,c,d\}}$, отношение над ${\displaystyle E}$ характеризуется набором ${\displaystyle R=\{a,b,c\}^{2}\cup \{(d,a)\}}$ является отношением эквивалентности на ${\displaystyle \{a,b,c\}}$ но не PER на ${\displaystyle E}$ поскольку он не симметричен^{[примечание 1]} ни переходный^{[заметка 2]} на ${\displaystyle E}$.

Каждое отношение частичной эквивалентности является дифункциональное отношение, но обратное неверно.

Каждое отношение частичной эквивалентности является правом Евклидово отношение. Противоположное неверно: например, xRy на натуральные числа, определяемые как 0 ≤ Икс ≤ у+1 ≤ 2, является правым евклидовым, но не симметричным (так как, например, 2р1, но не 1р2) ни транзитивный (так как, например, 2р1 и 1р0, но не 2р0). Точно так же каждое отношение частичной эквивалентности является левым евклидовым отношением, но не наоборот. Каждое отношение частичной эквивалентности квазирефлексивно,^[1] как следствие евклидовости.

В настройках, не относящихся к теории множеств

В теория типов, конструктивная математика и их приложения к Информатика, построение аналогов подмножеств часто бывает проблематичным^[2]- поэтому в этих контекстах чаще используются PER, особенно для определения сетоиды, иногда называемые частичными сетоидами. Формирование частичного сетоида из типа и PER аналогично формированию подмножеств и частных в классической теоретико-множественной математике.

Алгебраическое понятие соответствие может быть также обобщен на частичные эквивалентности, давая понятие субконгруэнтность, т.е. гомоморфное отношение это симметрично и транзитивно, но не обязательно рефлексивно.^[3]

Примеры

Простой пример PER, который нет отношение эквивалентности - это пустое отношение ${\displaystyle R=\emptyset }$, если ${\displaystyle X}$ не пусто.

Ядра частичных функций

Если ${\displaystyle f}$ это частичная функция на съемочной площадке ${\displaystyle A}$, то соотношение ${\displaystyle \approx }$ определяется

${\displaystyle x\approx y}$ если ${\displaystyle f}$ определяется в ${\displaystyle x}$, ${\displaystyle f}$ определяется в ${\displaystyle y}$, и ${\displaystyle f(x)=f(y)}$

является отношением частичной эквивалентности, поскольку оно явно симметрично и транзитивно.

Если ${\displaystyle f}$ не определено для некоторых элементов, то ${\displaystyle \approx }$ не является отношением эквивалентности. Это не рефлексивно, так как если ${\displaystyle f(x)}$ не определено тогда ${\displaystyle x\not \approx x}$ - собственно, для такого ${\displaystyle x}$ здесь нет ${\displaystyle y\in A}$ такой, что ${\displaystyle x\approx y}$. Отсюда сразу следует, что наибольшее подмножество ${\displaystyle A}$ на котором ${\displaystyle \approx }$ отношение эквивалентности - это в точности то подмножество, на котором ${\displaystyle f}$ определено.

Функции, соблюдающие отношения эквивалентности

Позволять Икс и Y быть множествами, снабженными отношениями эквивалентности (или PER) ${\displaystyle \approx _{X},\approx _{Y}}$. За ${\displaystyle f,g:X\to Y}$, определять ${\displaystyle f\approx g}$ значить:

${\displaystyle \forall x_{0}\;x_{1},\quad x_{0}\approx _{X}x_{1}\Rightarrow f(x_{0})\approx _{Y}g(x_{1})}$

тогда ${\displaystyle f\approx f}$ Значит это ж индуцирует корректно определенную функцию частных ${\displaystyle X/\approx _{X}\;\to \;Y/\approx _{Y}}$. Таким образом, PER ${\displaystyle \approx }$ отражает как идею определенность на частных и двух функций, порождающих одну и ту же функцию на частном.

Равенство IEEE с плавающей точкой значения

Стандарт IEEE 754: 2008 с плавающей запятой определяет отношение «EQ» для значений с плавающей запятой. Этот предикат симметричен и транзитивен, но не является рефлексивным из-за наличия NaN значения, которые не являются EQ сами по себе.

Примечания

1. ${\displaystyle dRa}$, но нет ${\displaystyle aRd}$
2. ${\displaystyle dRa}$ и ${\displaystyle aRb}$, но нет ${\displaystyle dRb}$

Рекомендации

1. Британская энциклопедия (EB); Хотя понятия квазирефлексивности у Е.Б. и Википедии в целом различаются, для симметричных отношений они совпадают.
2. https://ieeexplore.ieee.org/document/5135/
3. Дж. Ламбек (1996). «Бабочка и змей». В Альдо Урсини; Пауло Альяно (ред.). Логика и алгебра. CRC Press. С. 161–180. ISBN  978-0-8247-9606-8.

• Митчелл, Джон С. Основы языков программирования. MIT Press, 1996.
• Д.С. Скотт. «Типы данных как решетки». SIAM Journ. Comput., 3:523-587, 1976.