Частково еквівалентне відношення

Частково еквівалентне відношення (ЧЕВ) $R$ на множині $X$ є відношення симетричне і транзитивне. Іншими словами, для всіх $a,b,c\in X$:

1. Якщо $aRb$, тоді $bRa$ (симетрія)
2. Якщо $aRb$ і $bRc$, тоді $aRc$ (транзитивність)

Якщо $R$ також є рефлексивним, тоді $R$ є відношенням еквівалентності.

Властивості

У контексті теорії множин, є проста структура до загального ЧЕВ $R$ на $X$: це відношення еквівалентності на підмножині $Y=\{x\in X|xRx\}\subseteq X$, де$Y$ є такою підмножиною $X$, що у доповнені $Y$($X\setminus Y$) жоден елемент не пов'язаний відношенням $R$ з будь-яким іншим. Згідно з конструкцією,$R$ рефлексивно на $Y$ і тому є відношенням еквівалентності на $Y$. Зверніть увагу, що $R$ є вірним тільки для елементів $Y$: якщо $xRy$, то в силу симетрії $yRx$, тому $xRx$ і $yRy$ по транзитивності. І навпаки будь-яке відношення еквівалентності на $Y$ автоматично стає ЧЕВ на $X$.

ЧЕВ використовується, в основному, в галузі інформатики, теорії типів і конструктивної математики.

Приклади

Простий приклад ЧЕВ, який не є відношенням еквівалентності - $R=\mathrm{\varnothing }$ (якщо $X=\mathrm{\varnothing }$, то в цьому випадку порожнє відношення є відношення еквівалентності (і це єдине відношення на $X$)).

У часткових функціях

Інший приклад ЧЕВ: розглянемо множину $A$ і часткову функцію $f$, яка визначена на деяких елементах $A$, але не на всіх. $x\approx y$ тоді і тільки тоді, коли $f$ визначена на $x$ і $y$ та $f(x)=f(y)$ є частково еквівалентним відношенням, але не відношенням еквівалентності. Воно володіє властивостями симетрії і транзитивності, але воно не є рефлексивним якщо $f(x)$ не визначено, тоді $x\approx ̸x$ - фактично, для $x$ не існує такого $y\in A$, щоб виконувалось $x\approx y$. (З цього слідує, що підмножина $A$, для якої $\approx$ є відношенням еквівалентності, є підмножиною, на якій визначено $f$.)

Посилання

• Mitchell, John C. Foundations of programming languages. MIT Press, 1996.

Див. також

• Відношення еквівалентності
• Бінарне відношення