Частково еквівалентне відношення (ЧЕВ) на множині є відношення симетричне і транзитивне. Іншими словами, для всіх :
- Якщо , тоді (симетрія)
- Якщо і , тоді (транзитивність)
Якщо також є рефлексивним, тоді є відношенням еквівалентності.
Властивості
У контексті теорії множин, є проста структура до загального ЧЕВ на : це відношення еквівалентності на підмножині , де є такою підмножиною , що у доповнені () жоден елемент не пов'язаний відношенням з будь-яким іншим. Згідно з конструкцією, рефлексивно на і тому є відношенням еквівалентності на . Зверніть увагу, що є вірним тільки для елементів : якщо , то в силу симетрії , тому і по транзитивності. І навпаки будь-яке відношення еквівалентності на автоматично стає ЧЕВ на .
ЧЕВ використовується, в основному, в галузі інформатики, теорії типів і конструктивної математики.
Приклади
Простий приклад ЧЕВ, який не є відношенням еквівалентності - (якщо , то в цьому випадку порожнє відношення є відношення еквівалентності (і це єдине відношення на )).
У часткових функціях
Інший приклад ЧЕВ: розглянемо множину і часткову функцію , яка визначена на деяких елементах , але не на всіх. тоді і тільки тоді, коли визначена на і та є частково еквівалентним відношенням, але не відношенням еквівалентності. Воно володіє властивостями симетрії і транзитивності, але воно не є рефлексивним якщо не визначено, тоді - фактично, для не існує такого , щоб виконувалось . (З цього слідує, що підмножина , для якої є відношенням еквівалентності, є підмножиною, на якій визначено .)
Посилання
- Mitchell, John C. Foundations of programming languages. MIT Press, 1996.
Див. також
![]() | Ця стаття є сирим перекладом з іншої мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. |