Частково еквівалентне відношення (ЧЕВ) на множині є відношення симетричне і транзитивне. Іншими словами, для всіх :
- Якщо , тоді (симетрія)
- Якщо і , тоді (транзитивність)
Якщо також є рефлексивним, тоді є відношенням еквівалентності.
Властивості
У контексті теорії множин, є проста структура до загального ЧЕВ на : це відношення еквівалентності на підмножині , де є такою підмножиною , що у доповнені () жоден елемент не пов'язаний відношенням з будь-яким іншим. Згідно з конструкцією, рефлексивно на і тому є відношенням еквівалентності на . Зверніть увагу, що є вірним тільки для елементів : якщо , то в силу симетрії , тому і по транзитивності. І навпаки будь-яке відношення еквівалентності на автоматично стає ЧЕВ на .
ЧЕВ використовується, в основному, в галузі інформатики, теорії типів і конструктивної математики.
Приклади
Простий приклад ЧЕВ, який не є відношенням еквівалентності - (якщо , то в цьому випадку порожнє відношення є відношення еквівалентності (і це єдине відношення на )).
У часткових функціях
Інший приклад ЧЕВ: розглянемо множину і часткову функцію , яка визначена на деяких елементах , але не на всіх. тоді і тільки тоді, коли визначена на і та є частково еквівалентним відношенням, але не відношенням еквівалентності. Воно володіє властивостями симетрії і транзитивності, але воно не є рефлексивним якщо не визначено, тоді - фактично, для не існує такого , щоб виконувалось . (З цього слідує, що підмножина , для якої є відношенням еквівалентності, є підмножиною, на якій визначено .)
Посилання
- Mitchell, John C. Foundations of programming languages. MIT Press, 1996.
Див. також
Ця стаття є сирим з іншої мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Chastkovo ekvivalentne vidnoshennya ChEV R displaystyle R na mnozhini X displaystyle X ye vidnoshennya simetrichne i tranzitivne Inshimi slovami dlya vsih a b c X displaystyle a b c in X Yaksho a R b displaystyle aRb todi b R a displaystyle bRa simetriya Yaksho a R b displaystyle aRb i b R c displaystyle bRc todi a R c displaystyle aRc tranzitivnist Yaksho R displaystyle R takozh ye refleksivnim todi R displaystyle R ye vidnoshennyam ekvivalentnosti VlastivostiU konteksti teoriyi mnozhin ye prosta struktura do zagalnogo ChEV R displaystyle R na X displaystyle X ce vidnoshennya ekvivalentnosti na pidmnozhini Y x X x R x X displaystyle Y x in X x R x subseteq X deY displaystyle Y ye takoyu pidmnozhinoyu X displaystyle X sho u dopovneni Y displaystyle Y X Y displaystyle X setminus Y zhoden element ne pov yazanij vidnoshennyam R displaystyle R z bud yakim inshim Zgidno z konstrukciyeyu R displaystyle R refleksivno na Y displaystyle Y i tomu ye vidnoshennyam ekvivalentnosti na Y displaystyle Y Zvernit uvagu sho R displaystyle R ye virnim tilki dlya elementiv Y displaystyle Y yaksho x R y displaystyle xRy to v silu simetriyi y R x displaystyle yRx tomu x R x displaystyle xRx i y R y displaystyle yRy po tranzitivnosti I navpaki bud yake vidnoshennya ekvivalentnosti na Y displaystyle Y avtomatichno staye ChEV na X displaystyle X ChEV vikoristovuyetsya v osnovnomu v galuzi informatiki teoriyi tipiv i konstruktivnoyi matematiki PrikladiProstij priklad ChEV yakij ne ye vidnoshennyam ekvivalentnosti R displaystyle R emptyset yaksho X displaystyle X emptyset to v comu vipadku porozhnye vidnoshennya ye vidnoshennya ekvivalentnosti i ce yedine vidnoshennya na X displaystyle X U chastkovih funkciyah Inshij priklad ChEV rozglyanemo mnozhinu A displaystyle A i chastkovu funkciyu f displaystyle f yaka viznachena na deyakih elementah A displaystyle A ale ne na vsih x y displaystyle x approx y todi i tilki todi koli f displaystyle f viznachena na x displaystyle x i y displaystyle y ta f x f y displaystyle f x f y ye chastkovo ekvivalentnim vidnoshennyam ale ne vidnoshennyam ekvivalentnosti Vono volodiye vlastivostyami simetriyi i tranzitivnosti ale vono ne ye refleksivnim yaksho f x displaystyle f x ne viznacheno todi x x displaystyle x not approx x faktichno dlya x displaystyle x ne isnuye takogo y A displaystyle y in A shob vikonuvalos x y displaystyle x approx y Z cogo sliduye sho pidmnozhina A displaystyle A dlya yakoyi displaystyle approx ye vidnoshennyam ekvivalentnosti ye pidmnozhinoyu na yakij viznacheno f displaystyle f PosilannyaMitchell John C Foundations of programming languages MIT Press 1996 Div takozhVidnoshennya ekvivalentnosti Binarne vidnoshennya Cya stattya ye sirim perekladom z inshoyi movi Mozhlivo vona stvorena za dopomogoyu mashinnogo perekladu abo perekladachem yakij nedostatno volodiye oboma movami Bud laska dopomozhit polipshiti pereklad