Vztah částečné ekvivalence - Partial equivalence relation
v matematika, a vztah částečné ekvivalence (často zkráceno jako ZA, ve starší literatuře také nazývaný omezený vztah ekvivalence) na setu je binární relace to je symetrický a tranzitivní. Jinými slovy to platí pro všechny že:
- -li , pak (symetrie)
- -li a , pak (tranzitivita)
Li je také reflexní, pak je vztah ekvivalence.
Vlastnosti a aplikace
v teorie množin vztah na setu je PER tehdy a jen tehdy, je ekvivalenční vztah na podmnožinu . Podle konstrukce je reflexní a tedy vztah ekvivalence na . Vlastně, může obsahovat pouze prvky : pokud , pak symetrií, tak a tranzitivitou, tj. . Vzhledem k tomu, sada a podmnožina , vztah ekvivalence na nemusí být PER ; například s ohledem na sadu , vztah skončil charakterizovaná sadou je vztah ekvivalence na ale ne PER protože to není ani symetrické[poznámka 1] ani tranzitivní[poznámka 2] na .
Každý vztah částečné ekvivalence je a difunkční vztah, ale konverzace neplatí.
Každý vztah částečné ekvivalence je právo Euklidovský vztah. Naopak to neplatí: například xRy na přirozených číslech, definovaných 0 ≤ X ≤ y+1 ≤ 2, je správné euklidovské, ale ani symetrické (protože napřR1, ale ne 1R2) ani tranzitivní (protože napřR1 a 1R0, ale ne 2R0). Podobně je každý vztah částečné ekvivalence levým euklidovským vztahem, ale ne naopak. Každý dílčí vztah ekvivalence je kvazi-reflexivní,[1] jako důsledek bytí euklidovský.
V nastavení non-set-theory
v teorie typů, konstruktivní matematika a jejich aplikace pro počítačová věda, konstrukce analogů podmnožin je často problematická[2]—V těchto kontextech se proto PER používají běžněji, zejména k definování setoidy, někdy nazývané částečné setoidy. Formování parciálního setoidu z typu a PER je analogické s formováním podmnožin a kvocientů v klasické množinově-teoretické matematice.
Algebraická představa shoda lze také zobecnit na částečné ekvivalence, čímž se získá pojem subkongruence, tj. a homomorfní vztah to je symetrické a přechodné, ale ne nutně reflexivní.[3]
Příklady
Jednoduchý příklad PER, který je ne vztah ekvivalence je prázdný vztah , pokud není prázdný.
Jádra dílčích funkcí
Li je částečná funkce na setu , pak vztah definován
- -li je definována na , je definována na , a
je vztah částečné ekvivalence, protože je jasně symetrický a tranzitivní.
Li není u některých prvků definováno není vztah ekvivalence. Není to reflexivní, protože pokud pak není definován - ve skutečnosti pro takový tady není žádný takhle . Z toho okamžitě vyplývá, že největší podmnožina na kterých je ekvivalenční vztah je přesně ta podmnožina, na které je definováno.
Funkce respektující ekvivalenční vztahy
Nechat X a Y být soubory vybavené ekvivalenčními vztahy (nebo PER) . Pro , definovat znamenat:
pak znamená, že F indukuje dobře definovanou funkci kvocientů . Tedy PER zachycuje jak myšlenku definičnost na kvocientech a dvou funkcí indukujících stejnou funkci na kvocientu.
Rovnost IEEE s plovoucí desetinnou čárkou hodnoty
Standard IEEE 754: 2008 s plovoucí desetinnou čárkou definuje vztah „EQ“ pro hodnoty s plovoucí desetinnou čárkou. Tento predikát je symetrický a přechodný, ale není reflexivní kvůli přítomnosti NaN hodnoty, které pro sebe nejsou EQ.
Poznámky
Reference
- ^ Encyclopaedia Britannica (EB); ačkoliv se pojmy kvazi-reflexivity EB a Wikipedie obecně liší, shodují se pro symetrické vztahy.
- ^ https://ieeexplore.ieee.org/document/5135/
- ^ J. Lambek (1996). „Motýl a had“. In Aldo Ursini; Paulo Agliano (eds.). Logika a algebra. CRC Press. 161–180. ISBN 978-0-8247-9606-8.
- Mitchell, John C. Základy programovacích jazyků. MIT Press, 1996.
- Scott. Msgstr "Datové typy jako svazy". SIAM Journ. Comput., 3:523-587, 1976.