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

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

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

Приклади

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

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

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

Посилання

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

Див. також

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