Vztah ekvivalence

Pojem ensemblist o rovnocennosti vztahu je všudypřítomný v matematice . To umožňuje, v sadě , aby se týkají prvky, které jsou podobné určitou vlastnost.

Tyto prvky lze tedy seskupit do „svazků“ podobných prvků, čímž se definuje pojem třídy ekvivalence , aby se nakonec vytvořily nové množiny „asimilací“ podobných prvků k jednomu a stejnému prvku. Potom skončíme s představou množiny kvocientů .

Definice

Formální definice

Vztah ekvivalence na množině E je binární vztah ~ na E, který je zároveň reflexivní , symetrický a tranzitivní .

Přesněji řečeno:

~ je binární relace na E : dvojice ( x , y ) prvků E patří do grafu této relace právě tehdy, když x ~ y .
~ je reflexivní : pro jakýkoli prvek x z E máme x ~ x .
~ Je symetrický : vždy dva prvky x a y z E ověřit x ~ y , ale také ověřit, y ~ x.
~ Je tranzitivní : vždy tři prvky x , y a z o E ověřit x ~ y a y ~ z , ale také ověřit, x ~ Z .

Reflexivitou se E potom shoduje s definiční sadou ~ (která je z grafu odvozena projekcí ). Naopak, aby binární vztah na E symetrický a tranzitivní byl reflexivní, stačí, aby jeho množina definice byla E úplně.

Ekvivalentní definice

Můžeme také definovat vztah ekvivalence jako reflexivní a kruhový binární vztah .

O binárním vztahu ~ se říká, že je kruhový, pokud pokaždé, když máme x ~ y a y ~ z , máme také z ~ x .

Třída ekvivalence

Fix sadu E a vztah rovnocennosti ~ na E .

Definujeme třídu ekvivalence [ x ] prvku x z E jako množinu y z E tak, že x ~ y :

y \ in [x] \ Leftrightarrow x \ sim y.

Nazýváme zástupce z [ x ] jakéhokoli prvku [ x ] a systém zástupci třídy jakékoliv části z E , který obsahuje přesně jeden zástupce na třídu.

$x \ sim y \ Leftrightarrow [x] = [y].$
Sada tříd ekvivalence tvoří oddíl o E .

Demonstrace

Reflexivitou ~ patří jakýkoli prvek E do své třídy, proto:
- třídy nejsou prázdné a pokrývají E ;
- [ x ] = [ y ] ⇒ x ~ y .
Transitivitou x ~ y ⇒ [ y ] ⊂ [ x ] tedy symetrií, x ~ y ⇒ [ x ] = [ y ].
Podle této poslední implikace ( x ~ z a y ~ z ) ⇒ [ x ] = [ y ] tedy kontrapozicí jsou dvě odlišné třídy disjunktní .

Naopak, jakékoliv Rozklad množiny E definuje vztah rovnocennosti na E . Tím se vytvoří přirozená bijekce mezi oddíly množiny a ekvivalenčními vztahy na této množině. Počet relací ekvivalence na množině s n prvky se proto rovná Bellovu číslu B n , které lze vypočítat indukcí .

Příklady

Rovnoběžnost na sadu linií s afinního prostoru , je vztah rovnocennosti, jehož třídy jsou směry .
Libovolná mapa f : E → F indukuje na E ekvivalenční vztah „mít stejný obraz pomocí f “.
Když je tato mapa injektivní , relací ekvivalence, kterou indukuje na E, je rovnost , jejíž třídy jsou singletony .
Na množině ℤ relativních celých čísel je kongruence modulo n (pro pevné celé číslo n ) relací ekvivalence, jejíž třídy tvoří cyklickou skupinu ℤ / n ℤ .
Obecněji, v případě, G je skupina a H podskupina z G pak vztah ~ o G definován ( x ~ y ⇔ y -1 x ∈ H ) je vztah rovnocennosti, třídy, které se nazývají třídy vlevo následující H .
Rovnost téměř všude , pro funkce nad měřeným prostorem , je vztahem ekvivalence, který hraje důležitou roli v Lebesgueově integrační teorii . Ve skutečnosti mají dvě stejné funkce téměř všude stejné chování v této teorii.
Další příklady najdete v následujících článcích:
- Rovnováha ,
- Předobjednat ,
- Skupinová akce ,
- Konstrukce relativních celých čísel , Tělo zlomků , Doplněno metrickým prostorem ,
- Kvocient topologie ,
- Homotopická ekvivalence ,
- Klíčky .

Protiklady

Mnoho vztahů je reflexivních, symetrických nebo přechodných, aniž by byly všechny tři najednou:

preorder je reflexivní a tranzitivní podle definice, ale nejsou souměrné obecně (Příklad: objednávka na dvojici );
částečný vztah rovnocennosti (v) je symetrický a transitivní podle definice, ale ne reflexivní obecně ( triviální příklad : na nonempty , vztah prázdné grafu);
vztah tolerance je reflexivní a symetrická podle definice, ale nejsou tranzitivní obecně (například: na celá čísla, vztah ~ definována: m ~ n ⇔ | m - n | ≤ 1).

Poznámka

Můžeme poskytnout vlastní třídu se vztahem ekvivalence. Můžete dokonce definovat třídy ekvivalence, ale mohou to být samy o sobě vlastní třídy a obecně netvoří celek (např. Vztah ekvipotence v sadách tříd).

Kvocient množiny

Toto jméno je dáváno do oddílu E bylo zdůrazněno výše, což je podmnožina ze všech ${\ mathcal {P}} (E)$ částí E .

Definice

Vzhledem k tomu, vztah rovnocennosti ~ na E , v kvocientu z E vztahem ~, označený E / ~, je podmnožina ekvivalence tříd: ${\ mathcal {P}} (E)$

{\ displaystyle {E / \ sim} ~ = ~ \ {[x] \ v {\ mathcal {P}} (E) \ mid x \ v E \}.}

Množinu kvocientů lze také nazvat „množinou E s kvocientem od ~“ nebo „množinou E považovanou za modulo ~“. Myšlenkou těchto jmen je pracovat v množině kvocientů jako v E , ale bez rozlišování mezi nimi ekvivalentní prvky podle ~.

Kanonické přehazování

Kanonický mapa p , o E v kvocientu, pro každý prvek E spojuje její rovnocennost třída:

\ begin {matrix} p: & E & \ rightarrow & {E / \ sim} \\ & x & \ mapsto & [x] \ end {matrix}

Je surjective konstrukcí, protože je obrazem mapy města v ; ${\ displaystyle E / \ sim}$ ${\ displaystyle x \ mapsto [x]}$ $E$ ${\ mathcal {P}} (E)$
není obecně injektivní (pokud ~ není rovnost ), protože máme jen $p (x) = p (y) \ Šipka vlevo x \ sim y.$

Splňuje následující univerzální vlastnost , která vyjadřuje, že jakákoli mapa definovaná na E, jejíž přidružený vztah ekvivalence je méně jemný než ~ " jednoznačně přechází na kvocient" E / ~:

Věta o faktorizaci - Pro jakoukoli mapu f : E → F splňující [ x ~ y ⇒ f ( x ) = f ( y )] existuje jedinečná mapa g : E / ~ → F taková, že f = g ∘ p .

Tato mapa g - která má tedy stejný obrázek jako f - je injektivní právě tehdy, když x ~ y ⇔ f ( x ) = f ( y ).

Struktura kvocientu

Pokud má E algebraickou strukturu , je možné ji přenést do množiny kvocientů za předpokladu, že struktura je kompatibilní (en) s relací ekvivalence, tj. Dva prvky E se chovají vůči struktuře stejným způsobem, pokud patří do stejné třídy rovnocennosti. Sada kvocientů je poté opatřena kvocientovou strukturou počáteční struktury vztahem ekvivalence.

Například pokud ⊤ je interní zákon o E kompatibilní s ~, tj. Ověřování

( x ~ x ' a y ~ y' ) ⇒ x ⊤ y ~ x ' ⊤ y' ,

„ kvocient zákon zákona ⊤ o ~“ je definován jako „právem prostředku na kvocientu E / ~, který je rovnocenný tříd x a y , odpovídá třídě rovnocennost X ⊤ y . "

(Formálněji: zaznamenáním p surjekce E × E → E / ~ × E / ~, ( x , y ) ↦ ([ x ], [ y ]) af mapování E × E → E / ~, ( x , y ) ↦ [ x ⊤ y ], hypotéza kompatibility se přepíše p ( x , y ) = p ( x ' , y' ) ⇒ f ( x , y ) = f ( x ' , y' ). Použitím faktorizační věta výše , můžeme tedy definovat zákon kvocientu jako jedinečnou mapu g : E / ~ × E / ~ → E / ~ takovou, že f = g ∘ p .)

Příklady

Na objednané oblasti z reálných čísel , vztah „má stejné znaménko jako“ (chápán v užším slova smyslu) má tři třídy ekvivalence:
- množina přísně kladných celých čísel;
- množina přísně záporných celých čísel;
- Singleton {0}.

Násobení je kompatibilní s tímto vztahem ekvivalence a znaménkové pravidlo je vyjádřením kvocientového zákona.

Pokud má E skupinovou strukturu, spojíme s jakoukoli normální podskupinou kompatibilní vztah ekvivalence, který umožňuje definovat kvocientovou skupinu .

Byl vytvořen vztah ekvivalence

Na množině E nechť R je binární relace identifikovaná pomocí jejího grafu. Průsečík všech ekvivalence na E , které obsahují R se nazývá ekvivalence (na E ) generované R . To se rovná tranzitivní reflexní uzávěr z R ∪ R -1 .

Poznámky a odkazy

N. Bourbaki , Základy matematiky : Teorie množin [ detail vydání ], str. II-41 v Knihách Google .
(in) WD Wallis , Průvodce pro začátečníky po diskrétní matematice , Springer Science + Business Media ,2011, 2 nd ed. ( DOI 10.1007 / 978-0-8176-8286-6 , číst online ) , s. 104.
Bourbaki, Teorie množin , str. II-42.
N. Bourbaki, Elementy matematiky, Algebra, kapitoly 1 až 3 , str. I-11.
Jean-Pierre Ramis , André Warusfel a kol. , Matematika. Vše v jednom pro licenci. Úroveň 1 , Dunod ,2013, 2 nd ed. , 896 s. ( ISBN 978-2-10-060013-7 , číst online ) , s. 31.