Relace ekvivalence

Z Wikipedie, otevřené encyklopedie

V matematice je relace ekvivalence (nebo zkráceně ekvivalence) taková binární relace, která je reflexivní, symetrická a tranzitivní. Pokud tedy tuto relaci značíme „~“, pak pro všechny prvky a, b a c z množiny A (na které je tato relace definována) platí:

• a ~ a (reflexivnost)
• a ~ b ⇒ b ~ a (symetričnost)
• a ~ b ∧ b ~ c ⇒ a ~ c (tranzitivita)

Relace ekvivalence vyjadřuje společné vlastnosti dané množiny objektů.

Obsah 1 Příklady relací ekvivalence 2 Příklady relací, které nejsou ekvivalence 3 Ekvivalence a rozklad množiny 4 Generování ekvivalence

[editovat] Příklady relací ekvivalence

• Rovnost na množině (např. množině reálných čísel)
• Relace „být kongruentní v modulu 5“ na množině celých čísel
• Relace „být podobný“ na množině všech trojúhelníků
• Relace „být rovnoběžný“ na množině všech přímek v rovině
• Relace „být ekvivalentní“ na množině výroků
• Relace „narodit se stejný den“ na množině všech lidí

[editovat] Příklady relací, které nejsou ekvivalence

• Relace „být větší nebo rovný než“ není ekvivalence, protože i když je reflexivní a tranzitivní, není symetrická (7 ≥ 5 neznamená, že 5 ≥ 7).
• Relace „být vzdálen nejvýše“ není ekvivalence, protože není tranzitivní (|a-b|≤10, a=0, b=8, c=16)
• Relace „být matkou …“ není ekvivalence, protože není ani reflexivní, ani symetrická a ani tranzitivní.

[editovat] Ekvivalence a rozklad množiny

Každá ekvivalence definovaná na nějaké množině tuto množinu rozkládá na systém podmnožin zvaných třída rozkladu. Všechny vzájemně ekvivalentní prvky náleží právě jedné takové třídě.

Pokud tedy například máme množinu všech přímek v rovině, budou v každé třídě rozkladu podle relace „být rovnoběžný“ všechny přímky, které mají stejný směr a jsou tedy navzájem rovnoběžné.

Je-li na množině X definována relace ekvivalence „~“, pak tato relace tuto množinu rozkládá na třídy a množinu všech těchto tříd rozkladu nazýváme faktorová množina množiny X podle ekvivalence „~“ a značíme ji X/~.

Naopak jestliže jsou všechny prvky množiny rozděleny do několika disjunktních podmnožin, pak je tím dána ekvivalence. Dva prvky jsou ekvivalentní, když patří do stejné podmnožiny.

[editovat] Generování ekvivalence

Jsou-li dány dvě relace na téže množině X pak jejich průnikem je opět relace ekvivalence. Díky tomu lze definovat následující: Máme-li dánu libovolnou binární relaci R na množině X, pak relací ekvivalence generovanou relací R nazveme nejmenší relaci ekvivalence obsahující R.

Konkrétně může být ekvivalence „~“ generovaná relací R popsána takto: a~b tehdy a jen tehdy, když existují prvky x₁, x₂, x₃, …, x_n takové, že x₁=a a x_n=b a (x_i,x_i+1) nebo (x_i+1,x_i) je v R pro všechna i = 1,…,n-1.

Takto generované ekvivalence jsou často triviální. Například ekvivalence generovaná relací „≤“ má právě jednu třídu rozkladu: x~y pro všechna x a y. Obecně platí, že vzniklá ekvivalence je triviální vždy, když generující relace je antisymetrická a tedy platí buď xRy a nebo yRx.