Отношение частичной эквивалентности

В математике — отношение частичной эквивалентности (часто сокращенно PER , в старой литературе также называемое отношением ограниченной эквивалентности). ^[1]) — однородное бинарное отношение , симметричное и транзитивное . Если отношение также рефлексивно , то оно является отношением эквивалентности .

Определение [ править ]

Формально отношение $R$ на съемочной площадке $X$ является PER, если он справедлив для всех $a,b,c\in X$ что:

если $aRb$ , затем $bRa$ (симметрия)
если $aRb$ и $bRc$ , затем $aRc$ (транзитивность)

Другое более интуитивное определение состоит в том, что $R$ на съемочной площадке $X$ является PER, если есть какое-то подмножество $Y$ из $X$ такой, что $R\subseteq Y\times Y$ и $R$ является отношением эквивалентности на $Y$ . Эти два определения кажутся эквивалентными, если принять $Y=\{x\in X\mid x\,R\,x\}$ . ^[2]

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

Следующие свойства справедливы для отношения частичной эквивалентности $R$ на съемочной площадке $X$ :

$R$ является отношением эквивалентности на подмножестве $Y=\{x\in X\mid x\,R\,x\}\subseteq X$ . ^{[примечание 1]}
дифункциональный : отношение представляет собой множество $\{(a,b)\mid fa=gb\}$ для двух частичных функций $f,g:X\rightharpoonup Y$ и некоторый набор индикаторов $Y$
правый и левый евклидов : для $a,b,c\in X$ , $aRb$ и $aRc$ подразумевает $bRc$ и аналогично для левой евклидовости $bRa$ и $cRa$ подразумевать $bRc$
квазирефлексивный : если $x,y\in X$ и $xRy$ , затем $xRx$ и $yRy$ . ^[3]^{[примечание 2]}

Ни одно из этих свойств не является достаточным для того, чтобы подразумевать, что отношение является PER. ^{[примечание 3]}

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

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

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

Примеры [ править ]

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

Ядра частичных функций [ править ]

Если $f$ является частичной функцией на множестве $A$ , то соотношение $\approx$ определяется

x\approx y

если

f

определяется на

x

,

f

определяется на

y

, и

f(x)=f(y)

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

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

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

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

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

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

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

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

Примечания [ править ]

^ По конструкции, $R$ является рефлексивным на $Y$ и, следовательно, отношение эквивалентности на $Y$ .
^ Это следует, поскольку если $xRy$ , затем $yRx$ по симметрии, поэтому $xRx$ и $yRy$ по транзитивности. Это также является следствием евклидовых свойств.
^ Для отношения эквивалентности рассмотрим множество $E=\{a,b,c,d\}$ и отношение $R=\{a,b,c\}^{2}\cup \{(d,a)\}$ . $R$ является отношением эквивалентности на $\{a,b,c\}$ но не PER на $E$ поскольку он не симметричен ( $dRa$ , но не $aRd$ ) ни транзитивный ( $dRa$ и $aRb$ , но не $dRb$ ). Для евклидовости xRy для натуральных чисел, определяемых как 0 ≤ x ≤ y +1 ≤ 2, является правоевклидовым, но не симметричным (поскольку, например, 2 R 1, но не 1 R 2) и не транзитивным (поскольку, например, 2 R 1 и 1 R 0, но не 2 R 0).

Ссылки [ править ]

^ Скотт, Дана (сентябрь 1976 г.). «Типы данных как решетки». SIAM Journal по вычислительной технике . 5 (3): 560. дои : 10.1137/0205037 .
^ Митчелл, Джон К. (1996). Основы языков программирования . Кембридж, Массачусетс: MIT Press. стр. 364–365. ISBN 0585037892 .
^ Британская энциклопедия (EB); хотя понятие квазирефлексивности Э.Б. является понятием левой квазирефлексивности из Википедии, для симметричных отношений они совпадают.
^ Салвесон, А.; Смит, Дж. М. (1988). «Сила подмножества типа в теории типов Мартина-Лофа» . [1988] Труды. Третий ежегодный информационный симпозиум по логике в информатике . стр. 384–391. дои : 10.1109/LICS.1988.5135 . ISBN 0-8186-0853-6 . S2CID 15822016 .
^ Дж. Ламбек (1996). «Бабочка и змея». В Альдо Урсини; Пауло Альяно (ред.). Логика и алгебра . ЦРК Пресс. стр. 161–180. ISBN 978-0-8247-9606-8 .

[3] По конструкции, $R$ является рефлексивным на $Y$ и, следовательно, отношение эквивалентности на $Y$ .

[5] Это следует, поскольку если $xRy$ , затем $yRx$ по симметрии, поэтому $xRx$ и $yRy$ по транзитивности. Это также является следствием евклидовых свойств.

[6] Для отношения эквивалентности рассмотрим множество $E=\{a,b,c,d\}$ и отношение $R=\{a,b,c\}^{2}\cup \{(d,a)\}$ . $R$ является отношением эквивалентности на $\{a,b,c\}$ но не PER на $E$ поскольку он не симметричен ( $dRa$ , но не $aRd$ ) ни транзитивный ( $dRa$ и $aRb$ , но не $dRb$ ). Для евклидовости xRy для натуральных чисел, определяемых как 0 ≤ x ≤ y +1 ≤ 2, является правоевклидовым, но не симметричным (поскольку, например, 2 R 1, но не 1 R 2) и не транзитивным (поскольку, например, 2 R 1 и 1 R 0, но не 2 R 0).

[1] Скотт, Дана (сентябрь 1976 г.). «Типы данных как решетки». SIAM Journal по вычислительной технике . 5 (3): 560. дои : 10.1137/0205037 .

[2] Митчелл, Джон К. (1996). Основы языков программирования . Кембридж, Массачусетс: MIT Press. стр. 364–365. ISBN 0585037892 .

[4] Британская энциклопедия (EB); хотя понятие квазирефлексивности Э.Б. является понятием левой квазирефлексивности из Википедии, для симметричных отношений они совпадают.

[7] Салвесон, А.; Смит, Дж. М. (1988). «Сила подмножества типа в теории типов Мартина-Лофа» . [1988] Труды. Третий ежегодный информационный симпозиум по логике в информатике . стр. 384–391. дои : 10.1109/LICS.1988.5135 . ISBN 0-8186-0853-6 . S2CID 15822016 .

[8] Дж. Ламбек (1996). «Бабочка и змея». В Альдо Урсини; Пауло Альяно (ред.). Логика и алгебра . ЦРК Пресс. стр. 161–180. ISBN 978-0-8247-9606-8 .

[1]

[2]

[примечание 1]

[3]

[примечание 2]

[примечание 3]

[4]

[5]