Vztah ekvivalence - Equivalence relation

The 52 ekvivalenční vztahy na 5-prvkové sadě zobrazené jako 5 × 5 logické matice (barevná pole, včetně těch ve světle šedé barvě, znamenají jedny; bílá pole pro nuly.) Indexy řádků a sloupců nebílých buněk jsou související prvky, zatímco různé barvy, kromě světle šedé, označují třídy ekvivalence (každé světlo šedá buňka je vlastní třída ekvivalence).

v matematika, an vztah ekvivalence je binární relace to je reflexní, symetrický a tranzitivní. Vztah „rovná se“ je kanonickým příkladem vztahu ekvivalence.

Každý vztah ekvivalence poskytuje a rozdělit podkladové sady do disjunktu třídy ekvivalence. Dva prvky dané množiny jsou navzájem ekvivalentní, kdyby a jen kdyby patří do stejné třídy ekvivalence.

Zápis

V literatuře se používají různé notace k označení těchto dvou prvků A a b množiny jsou ekvivalentní s ohledem na vztah ekvivalence R; nejběžnější jsou „A ~ b" a "A ≡ b", které se používají, když R je implicitní a varianty „A ~_R b", "A ≡_R b„nebo“${displaystyle {amathop {R} b}}$" specifikovat R výslovně. Může být napsáno neekvivalence "A ≁ b„nebo“${displaystyle aot equiv b}$".

Definice

A binární relace ~ na setu X je považován za vztah ekvivalence, kdyby a jen kdyby je reflexivní, symetrický a přechodný. To je pro všechny A, b a C v X:

• A ~ A. (Reflexivita )
• A ~ b kdyby a jen kdyby b ~ A. (Symetrie )
• -li A ~ b a b ~ C, pak A ~ C. (Přechodnost )

X spolu se vztahem ~ se nazývá a setoid. The třída ekvivalence z ${displaystyle a}$ pod ~, označeno ${displaystyle [a]}$,^[1] je definován jako ${displaystyle [a] = {xin Xmid xsim a}}$.^[2][3]

Příklady

Jednoduchý příklad

Nechte set ${displaystyle {a, b, c}}$ mít vztah ekvivalence ${displaystyle {(a, a), (b, b), (c, c), (b, c), (c, b)}}$. Následující sady jsou třídy ekvivalence tohoto vztahu:

${displaystyle [a] = {a}, ~~~~ [b] = [c] = {b, c}}$.

Sada všech tříd ekvivalence pro tento vztah je ${displaystyle {{a}, {b, c}}}$. Tato sada je a rozdělit sady ${displaystyle {a, b, c}}$.

Rovnocenné vztahy

Následující vztahy jsou všechny vztahy ekvivalence:

• "Je rovno" na množině čísel. Například, ${displaystyle {frac {1} {2}}}$ je rovný ${displaystyle {frac {4} {8}}}$.^[3]
• „Má stejné narozeniny jako“ na množině všech lidí.
• "Je podobný „na množině všech trojúhelníky.
• "Je shodný „na množině všech trojúhelníky.
• „Je shodný s, modulo n" na celá čísla.^[3]
• „Má to samé obraz pod funkce "na prvcích doména funkce.
• „Má stejnou absolutní hodnotu“ na množině reálných čísel
• „Má stejný kosinus“ na množině všech úhlů.

Vztahy, které nejsou rovnocennosti

• Vztah „≥“ mezi reálnými čísly je reflexivní a přechodný, ale není symetrický. Například 7 ≥ 5 neznamená, že 5 ≥ 7. Je to však a celková objednávka.
• Vztah „má a společný faktor větší než 1 s "mezi přirozená čísla větší než 1, je reflexivní a symetrický, ale nikoli tranzitivní. Například přirozená čísla 2 a 6 mají společný faktor větší než 1 a 6 a 3 mají společný faktor větší než 1, ale 2 a 3 nemají společný faktor větší než 1.
• The prázdný vztah R (definováno tak, že aRb není nikdy pravda) na a neprázdný soubor X je vakuově symetrické a přechodné, ale ne reflexivní. (Li X je také prázdný R je reflexní.)
• Vztah „je přibližně stejný“ mezi reálnými čísly, i když je přesněji definován, není vztahem ekvivalence, protože i když je reflexivní a symetrický, není přechodný, protože se může hromadit několik malých změn, které se stanou velkou změnou. Pokud je však aproximace definována asymptoticky, například vyslovením dvou funkcí F a G jsou přibližně stejné blízko nějakého bodu, pokud je limit f - g je 0 v tomto bodě, pak to definuje vztah ekvivalence.

Vazby na jiné vztahy

• A částečná objednávka je vztah, který je reflexivní, antisymetrický a tranzitivní.
• Rovnost je jak ekvivalenční vztah, tak částečný řád. Rovnost je také jediným vztahem na množině, která je reflexivní, symetrická a antisymetrická. v algebraické výrazy, stejné proměnné mohou být nahrazeno jeden pro druhého zařízení, které není k dispozici pro proměnné související s ekvivalencí. The třídy ekvivalence vztahu ekvivalence mohou nahradit jeden druhého, ale ne jednotlivce ve třídě.
• A přísné částečné pořadí je ireflexivní, tranzitivní a asymetrický.
• A vztah částečné ekvivalence je tranzitivní a symetrický. Takový vztah je reflexivní kdyby a jen kdyby to je seriál, tj. pokud ∀A∃b A ~ b.^[4] Proto může být vztah ekvivalence alternativně definován jako symetrický, přechodný a sériový vztah.
• A ternární ekvivalenční vztah je ternární analogie obvyklého (binárního) vztahu ekvivalence.
• Reflexivní a symetrický vztah je a vztah závislosti (je-li konečný), a a vztah tolerance pokud je nekonečný.
• A předobjednávka je reflexivní a tranzitivní.
• A kongruenční vztah je vztah ekvivalence, jehož doménou X je také podkladovou sadou pro algebraická struktura, a který respektuje další strukturu. Kongruenční vztahy obecně hrají roli jádra homomorfismů a lze vytvořit kvocient struktury kongruenčním vztahem. V mnoha důležitých případech mají kongruenční vztahy alternativní zastoupení jako substruktury struktury, na které jsou definovány (např. Kongruenční vztahy na skupinách odpovídají normální podskupiny ).
• Jakýkoli vztah ekvivalence je negací vztah oddělenosti, i když platí obrácené tvrzení klasická matematika (naproti tomu konstruktivní matematika ), protože je ekvivalentní s zákon vyloučeného prostředku.

Dobře definovaná v rámci vztahu ekvivalence

Pokud ~ je vztah ekvivalence na X, a P(X) je vlastnost prvků X, takže kdykoli X ~ y, P(X) je pravda, pokud P(y) je pravda, pak vlastnost P se říká, že je dobře definované nebo a invariant třídy podle vztahu ~.

Častý konkrétní případ nastane, když F je funkce z X do jiné sady Y; -li X₁ ~ X₂ naznačuje F(X₁) = F(X₂) pak F se říká, že je morfismus pro ~, a třída invariantní pod ~, nebo jednoduše neměnný pod ~. K tomu dochází, např. v teorii znaků konečných grup. Druhý případ s funkcí F lze vyjádřit komutativním trojúhelníkem. Viz také neměnný. Někteří autoři místo „invariant pod ~“ používají „kompatibilní s ~“ nebo „respektují ~“.

Obecněji může funkce mapovat ekvivalentní argumenty (pod relací ekvivalence ~_A) na ekvivalentní hodnoty (v ekvivalenčním vztahu ~_B). Taková funkce je známá jako morfismus z ~_A do ~_B.

Třída ekvivalence, množina kvocientů, oddíl

Nechat ${displaystyle a, bin X}$. Některé definice:

Třída ekvivalence

Podmnožina Y z X takhle A ~ b platí pro všechny A a b v Y, a nikdy pro A v Y a b mimo Y, se nazývá třída ekvivalence z X od ~. Nechat ${displaystyle [a]: = {xin Xmid asim x}}$ označit třídu rovnocennosti, ke které A patří. Všechny prvky X rovnocenné jsou také prvky stejné třídy ekvivalence.

Kvocient množiny

Sada všech tříd ekvivalence X ~, označeno ${displaystyle X / {mathord {sim}}: = {[x] střední xin X}}$, je množina kvocientu z X od ~. Li X je topologický prostor, existuje přirozený způsob transformace X/ ~ do topologického prostoru; vidět kvocientový prostor pro podrobnosti.

Projekce

The projekce of ~ je funkce ${displaystyle pi: X o X / {mathord {sim}}}$ definován ${displaystyle pi (x) = [x]}$ který mapuje prvky X do příslušných tříd ekvivalence pomocí ~.

Teorém na projekce:^[5] Nechte funkci F: X → B být takový, že A ~ b → F(A) = F(b). Pak existuje jedinečná funkce G : X / ~ → B, takový, že F = Gπ. Li F je surjection a A ~ b ↔ F(A) = F(b), pak G je bijekce.

Ekvivalenční jádro

The ekvivalenční jádro funkce F je ekvivalenční vztah ~ definovaný ${displaystyle xsim yiff f (x) = f (y)}$. Ekvivalenční jádro injekce je vztah identity.

Rozdělit

A rozdělit z X je sada P neprázdných podmnožin X, takže každý prvek X je prvek jednoho prvku z P. Každý prvek P je buňka oddílu. Navíc prvky P jsou párově disjunktní a jejich svaz je X.

Počítání oddílů

Nechat X být konečný soubor s n elementy. Protože každý vztah ekvivalence skončil X odpovídá oddílu X, a naopak, počet vztahů ekvivalence na X se rovná počtu různých oddílů X, který je nth Bell číslo B_n:

${displaystyle B_ {n} = {frac {1} {e}} součet _ {k = 0} ^ {infty} {frac {k ^ {n}} {k!}}}$       (Dobinského vzorec ).

Základní věta vztahů ekvivalence

Klíčový výsledek spojuje vztahy ekvivalence a oddíly:^[6][7][8]

• Vztah ekvivalence ~ na množině X oddíly X.
• Naopak odpovídající libovolnému oddílu Xexistuje vztah ekvivalence X.

V obou případech buňky oddílu X jsou třídy rovnocennosti X od ~. Protože každý prvek X patří do jedinečné buňky libovolného oddílu X, a protože každá buňka oddílu je identická s třída ekvivalence z X ~, každý prvek z X patří do jedinečné třídy rovnocennosti X od ~. Existuje tedy přirozená bijekce mezi množinou všech vztahů ekvivalence na X a soubor všech oddílů X.

Porovnání ekvivalenčních vztahů

Pokud ~ a ≈ jsou dva ekvivalenční vztahy na stejné množině S, a A~b naznačuje A≈b pro všechny A,b ∈ S, pak ≈ se říká, že a hrubší relace než ~, a ~ je a jemnější vztah než ≈. Ekvivalentně

• ~ je jemnější než ≈, pokud je každá třída ekvivalence ~ podmnožinou třídy ekvivalence ≈, a tedy každá třída ekvivalence ≈ je sjednocením tříd ekvivalence ~.
• ~ je jemnější než ≈, pokud je oddíl vytvořený ~ vylepšením oddílu vytvořeného pomocí ≈.

Vztah ekvivalence rovnosti je nejlepší vztah ekvivalence na libovolné množině, zatímco univerzální vztah, který se týká všech párů prvků, je nejhrubší.

Vztah „~ je jemnější než ≈“ na kolekci všech relací ekvivalence na pevné sadě je sám o sobě relací částečného řádu, což z kolekce dělá geometrická mříž.^[9]

Generování vztahů rovnocennosti

Vzhledem k jakékoli binární relaci ${displaystyle Asubset X imes X}$ na ${displaystyle X}$, vztah ekvivalence generovaný ${displaystyle A}$ je průsečík vztahů ekvivalence na ${displaystyle X}$ které obsahují ${displaystyle A}$. (Od té doby ${displaystyle X imes X}$ je vztah ekvivalence, průnik je netriviální.)

• Vzhledem k jakékoli sadě X, existuje vztah ekvivalence přes množinu [X → X] všech funkcí X→X. Dvě takové funkce jsou považovány za rovnocenné, když jsou jejich příslušné sady fixní body mít stejné mohutnost, odpovídající cyklům délky jedna v a permutace. Funkce ekvivalentní tímto způsobem tvoří třídu ekvivalence na [X → X] a tyto třídy ekvivalence oddíl [X → X].
• Vztah ekvivalence ~ on X je ekvivalenční jádro jeho surjektivní projekce π: X → X/~.^[10] Naopak jakýkoli surjection mezi sadami určuje oddíl ve své doméně, sadu preimages z singletons v codomain. Tedy vztah ekvivalence přes X, oddíl X, a projekce, jejíž doména je X, jsou tři rovnocenné způsoby určení stejné věci.
• Průsečík jakékoli kolekce vztahů ekvivalence nad X (binární vztahy považovány za a podmnožina z X × X) je také ekvivalenční vztah. Tím se získá pohodlný způsob generování relace ekvivalence: vzhledem k jakékoli binární relaci R na Xvztah ekvivalence generované R. je nejmenší relace ekvivalence obsahující R. Konkrétně, R generuje vztah ekvivalence A ~ b kdyby a jen kdyby existují prvky X₁, X₂, ..., X_n v X takhle A = X₁, b = X_n, a (X_i, X_i+1) ∈ R nebo (X_i+1, X_i) ∈ R, i = 1, ..., n−1.
  Všimněte si, že vztah ekvivalence generovaný tímto způsobem může být triviální. Například vztah ekvivalence ~ generovaný libovolným celková objednávka na X má přesně jednu třídu ekvivalence, X sám, protože X ~ y pro všechny X a y. Jako další příklad lze uvést jakoukoli podmnožinu souboru vztah identity na X má třídy ekvivalence, které jsou singletony X.
• Vztahy ekvivalence mohou vytvářet nové prostory „lepením věcí dohromady“. Nechat X být jednotkou Kartézské náměstí [0, 1] × [0, 1] a nechť ~ je ekvivalenční vztah na X definován (A, 0) ~ (A, 1) pro všechny A ∈ [0, 1] a (0, b) ~ (1, b) pro všechny b ∈ [0, 1]. Pak kvocientový prostor X/ ~ lze přirozeně identifikovat (homeomorfismus ) s torus: vezměte čtvercový kousek papíru, ohněte a slepte horní a dolní okraj, abyste vytvořili válec, a pak ohněte výsledný válec tak, aby se jeho dva otevřené konce slepily, což by mělo za následek vznik torusu.

Algebraická struktura

Hodně z matematiky je založeno na studiu ekvivalencí a objednávkové vztahy. Teorie mřížky zachycuje matematickou strukturu řádových vztahů. Přestože jsou ekvivalenční vztahy v matematice stejně všudypřítomné jako řádové vztahy, algebraická struktura ekvivalencí není tak známá jako struktura řádů. Původní struktura čerpá především z teorie skupin a v menší míře na teorii svazů, Kategorie, a grupoidy.

Skupinová teorie

Stejně jako objednávkové vztahy jsou uzemněny objednané sady, sady uzavřeny pod párem supremum a infimum, jsou založeny vztahy ekvivalence rozdělené sady, což jsou sady uzavřené pod bijekce které zachovávají strukturu oddílů. Protože všechny takové bijekce mapují třídu ekvivalence na sebe, jsou takové bijekce také známé jako obměny. Proto permutační skupiny (také známý jako transformační skupiny ) a související pojem obíhat osvětlit matematickou strukturu vztahů ekvivalence.

Nechť '~' označuje vztah ekvivalence přes nějakou neprázdnou množinu A, nazvaný vesmír nebo podkladová sada. Nechat G označit soubor bijektivních funkcí nad A které zachovávají strukturu oddílů A: ∀X ∈ A ∀G ∈ G (G(X) ∈ [X]). Pak platí následující tři spojené věty:^[11]

• ~ oddíly A do tříd ekvivalence. (To je Základní věta o vztazích ekvivalence, zmíněno výše);
• Vzhledem k rozdělení na A, G je transformovaná skupina ve složení, jejíž oběžné dráhy jsou buňky přepážky;^[15]

• Vzhledem k transformační skupině G přes A, existuje vztah ekvivalence ~ A, jejichž třídami ekvivalence jsou oběžné dráhy G.^[16][17]

Stručně řečeno, vzhledem k relaci ekvivalence ~ nad A, existuje a transformační skupina G přes A jejichž oběžné dráhy jsou třídami ekvivalence A pod ~.

Tato transformační skupinová charakterizace vztahů ekvivalence se zásadně liší od cesty mříže charakterizovat řádové vztahy. Argumenty operací teorie mřížky setkat a připojit se jsou prvky nějakého vesmíru A. Mezitím argumenty operací transformační skupiny složení a inverzní jsou prvky sady bijekce, A → A.

Přesun do skupin obecně, pojďme H být podskupina některých skupina G. Nechť ~ je vztah ekvivalence G, takový, že A ~ b ↔ (ab⁻¹ ∈ H). Třídy ekvivalence ~ se také nazývají oběžné dráhy akce z H na G—Máte pravdu kosety z H v G. Zaměňovat A a b získá levé kosety.

Související myšlení lze nalézt v Rosen (2008: kap. 10).

Kategorie a grupoidy

Nechat G být množinou a nechat "~" označit vztah ekvivalence G. Pak můžeme vytvořit a grupoid představující tento vztah ekvivalence následujícím způsobem. Objekty jsou prvky Ga pro jakékoli dva prvky X a y z G, existuje jedinečný morfismus z X na y kdyby a jen kdyby X~y.

Mezi výhody týkající se vztahu ekvivalence jako zvláštního případu grupoidu patří:

• Zatímco pojem „vztah volné ekvivalence“ neexistuje, pojem a zdarma groupoid na řízený graf dělá. Je tedy smysluplné hovořit o „prezentaci vztahu ekvivalence“, tj. Prezentaci odpovídajícího grupoidu;
• Svazky skupin, skupinové akce Sady a ekvivalenční vztahy lze považovat za zvláštní případy pojmu grupoid, což je názor, který naznačuje řadu analogií;
• V mnoha kontextech „kvocient“, a proto se často nazývají odpovídající ekvivalenční vztahy shody, jsou důležité. To vede k představě o vnitřním grupoidu v a kategorie.^[18]

Mříže

Vztahy ekvivalence na libovolné množině X, na objednávku nastavit zařazení, tvoří a úplná mříž, volala Ošidit X podle konvence. Kanonický mapa ker: X^X → Ošidit X, se týká monoidní X^X ze všech funkce na X a Ošidit X. ker je surjektivní ale ne injekční. Méně formálně vztah ekvivalence ker na X, přebírá každou funkci F: X→X k jeho jádro ker F. Rovněž, ker (ker) je vztah ekvivalence na X^X.

Vztahy ekvivalence a matematická logika

Vztahy ekvivalence jsou připraveným zdrojem příkladů nebo protikladů. Například vztah ekvivalence s přesně dvěma nekonečnými třídami ekvivalence je snadným příkladem teorie, která je ω-kategorický, ale není kategorický pro větší základní číslovka.

Důsledek teorie modelů je, že vlastnosti definující relaci lze prokázat nezávisle na sobě navzájem (a tedy i nezbytné části definice) právě tehdy, když u každé vlastnosti lze najít příklady vztahů, které nesplňují danou vlastnost, zatímco uspokojují všechny ostatní vlastnosti. Tři definující vlastnosti vztahů ekvivalence lze tedy prokázat vzájemně nezávislými následujícími třemi příklady:

• Reflexní a tranzitivní: Vztah ≤ zapnutý N. Nebo nějaký předobjednávka;
• Symetrické a tranzitivní: Vztah R na N, definováno jako aRb ↔ ab ≠ 0. Nebo jakýkoli vztah částečné ekvivalence;
• Reflexní a symetrické: Vztah R na Z, definováno jako aRb ↔ "A − b je dělitelné alespoň jedním z 2 nebo 3. “Nebo libovolný vztah závislosti.

Vlastnosti definovatelné v logika prvního řádu že vztah rovnocennosti může, ale nemusí mít, zahrnuje:

• Počet třídy ekvivalence je konečný nebo nekonečný;
• Počet tříd ekvivalence se rovná (konečným) přirozeným číslům n;
• Všechny třídy ekvivalence mají nekonečno mohutnost;
• Počet prvků v každé třídě ekvivalence je přirozené číslo n.

Euklidovské vztahy

Euklid je Elementy zahrnuje následující „Společný pojem 1“:

Věci, které se rovnají stejné věci, se také navzájem rovnají.

V dnešní době se nazývá vlastnost popsaná v Common Notion 1 Euklidovský (nahrazení výrazu „stejné“ výrazem „je ve vztahu k výrazu“). Pod „vztahem“ se rozumí a binární relace, ve kterém aRb se obecně liší od podprsenka. Euklidovský vztah tedy přichází ve dvou formách:

(oblouk ∧ bRc) → aRb (Levo-euklidovský vztah)

(cRa ∧ cRb) → aRb (Pravo-euklidovský vztah)

Připojuje se následující věta Euklidovské vztahy a ekvivalenční vztahy:

Teorém

Pokud je vztah (levý nebo pravý) euklidovský a reflexní, je také symetrický a tranzitivní.

Důkaz levoeuklidovského vztahu

(oblouk ∧ bRc) → aRb [a / c] = (aRa ∧ podprsenka) → aRb [reflexní; vymazat T∧] = podprsenka → aRb. Proto R je symetrický.

(oblouk ∧ bRc) → aRb [symetrie] = (oblouk ∧ cRb) → aRb. Proto R je tranzitivní. ${displaystyle _ {Box}}$

s analogickým důkazem pravo-euklidovského vztahu. Vztah ekvivalence je tedy vztah, který je Euklidovský a reflexní. Elementy nezmiňuje ani symetrii, ani reflexivitu a Euclid by pravděpodobně považoval reflexivitu rovnosti za příliš zjevnou, aby vyžadoval výslovnou zmínku.

Viz také

• Vztah odloučenosti
• Třída konjugace
• Rovnováha (geometrie)
• Kvocient podle vztahu ekvivalence
• Topologická konjugace
• Až do

Poznámky

Reference

• Brown, Ronald, 2006. Topologie a grupoidy. Booksurge LLC. ISBN  1-4196-2722-8.
• Castellani, E., 2003, „Symetrie a ekvivalence“ v Brading, Katherine, a E. Castellani, eds., Symetrie ve fyzice: Filozofické úvahy. Cambridge Univ. Tisk: 422–433.
• Robert Dilworth a Crawley, Peter, 1973. Algebraická teorie svazů. Prentice Hall. Chpt. 12 pojednává o tom, jak vznikají ekvivalenční vztahy mříž teorie.
• Higgins, P.J., 1971. Kategorie a grupoidy. Van Nostrand. Stahovatelné od roku 2005 jako TAC dotisk.
• John Randolph Lucas, 1973. Pojednání o čase a prostoru. Londýn: Methuen. Část 31.
• Rosen, Joseph (2008) Pravidla symetrie: Jak se na symetrii zakládá věda a příroda. Springer-Verlag. Většinou kapitoly. 9,10.
• Raymond Wilder (1965) Úvod do základů matematiky 2. vydání, kapitola 2-8: Axiomy definující ekvivalenci, str. 48–50, John Wiley & Sons.

externí odkazy

• „Rovnocenný vztah“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Bogomolny, A., "Vztah rovnocennosti " cut-the-uzel. Přístupné 1. září 2009
• Vztah ekvivalence na PlanetMath
• OEIS posloupnost A231428 (binární matice představující ekvivalenční vztahy)