Ekvivalencia reláció

Az elképzelés ensemblist az ekvivalencia reláció mindenütt jelen van az a matematika . Lehetővé teszi, hogy egy halmazban olyan elemeket kapcsolhassanak össze, amelyek egy bizonyos tulajdonság alapján hasonlóak.

Ezeket az elemeket tehát hasonló elemek „kötegei” segítségével csoportosíthatjuk, meghatározva ezzel az ekvivalencia osztály fogalmát , hogy végül új halmazokat állítsunk össze hasonló elemek egy és ugyanazon elemhez „asszimilálásával”. Ezután a hányadoshalmaz fogalmával végzünk .

Meghatározás

Formális meghatározás

Egy ekvivalencia reláció a halmaz E egy bináris reláció ~ on E , amely ugyanakkor reflexív , szimmetrikus és tranzitív .

Pontosabban:

• ~ Egy bináris reláció a E  : egy pár ( x , y ) az elemeinek E tartozik a grafikon a jelen összefüggésben, ha, és csak akkor, ha x ~ y .
• ~ Jelentése visszaható  : bármely elem x a E , van x ~ x .
• ~ Jelentése szimmetrikus  : amikor két elem x és y a E ellenőrizze x ~ y , ők is ellenőrzi y ~ x.
• ~ Jelentése tranzitív  : amikor három elem x , y és z a E ellenőrizze x ~ y és y ~ z , ők is ellenőrzi x ~ z .

A reflexivitás révén E egybeesik a ~ definíciókészlettel (amelyet a grafikon vetít ki a grafikonból ). Ezzel szemben ahhoz, hogy az E szimmetrikus és transzitív bináris reláció reflexív legyen, elegendő, ha definíciókészlete teljes egészében E.

Egyenértékű meghatározás

Az ekvivalencia relációt reflexív és kör bináris relációként is meghatározhatjuk .

A bináris relációról azt mondjuk, hogy kör alakú, ha minden egyes alkalommal, amikor x ~ y és y ~ z van , akkor van z ~ x is .

Ekvivalencia osztály

Rögzítsen egy E halmazt és egy ~ ekvivalencia relációt E-re .

Definiáljuk a ekvivalencia osztály [ x ] egy elem X az E , mint a beállított y az E olyan, hogy x ~ y  :

y∈[x]⇔x∼y.{\ displaystyle y \ itt: [x] \ Balra mutató nyíl x \ sim y.}

Hívjuk a képviselője a [ x ] minden eleme [ x ], és a rendszer osztály képviselői bármely részét a E , amely pontosan egy képviselője egy osztályban.

• x∼y⇔[x]=[y].{\ displaystyle x \ sim y \ Balra mutató nyíl [x] = [y].}
• Az egyenértékűségi osztályok halmaza alkotja az E partícióját .

Demonstráció

• A ~ reflexivitása révén az E bármely eleme az osztályába tartozik, ezért:
  • az osztályok nem üresek és E fedéllel rendelkeznek  ;
  • [ x ] = [ y ] ⇒ x ~ y .
• A transzitivitás révén x ~ y ⇒ [ y ] ⊂ [ x ] tehát szimmetriával, x ~ y ⇒ [ x ] = [ y ].
• Ez utóbbi következtetés szerint ( x ~ z és y ~ z ) ⇒ [ x ] = [ y ], ezért egymásnak ellentmondva két különböző osztály nem különbözik egymástól .

Ezzel szemben az E halmaz bármely partíciója ekvivalencia relációt határoz meg E-n . Ez létrehoz egy természetes bijekciót között osztályfelbontás és az egyenértékűség kapcsolatok ezt meg. A száma egyenértékűség kapcsolatok egy halmaz n elemek ezért egyenlő azzal, a Bell szám B n , amely lehet kiszámítani indukció .

Példák

• Az affin tér vonalainak halmazán a párhuzamosság ekvivalencia reláció, amelynek osztályai az irányok .
• Bármilyen térkép f  : E → F indukálja az E a ekvivalencia reláció „hogy ugyanaz a kép által f  ”.
• Amikor ez a térkép injektıv , az ekvivalencia reláció, hogy indukálja a E jelentése egyenlőség , akinek osztályok a egyesterhességek .
• A relatív egész számok the halmazán a modulo n kongresszió ( rögzített n egész szám esetén ) ekvivalencia reláció, amelynek osztályai alkotják a ℤ / n cyc ciklikus csoportot .
• Általánosabban elmondható, hogy ha G egy csoport, és H egy G alcsoportja , akkor az ( x ~ y ⇔ y −1 x ∈ H ) által definiált ~ G kapcsolata ekvivalencia reláció, amelynek osztályait H után hagyott osztályoknak nevezzük. .
• Az egyenlőség szinte mindenhol , a mért téren belüli funkciók esetében , ekvivalencia reláció, amely fontos szerepet játszik Lebesgue integrációs elméletében . Valójában két egyenlő függvény szinte mindenütt azonos viselkedéssel bír ebben az elméletben.
• További példák a következő cikkekben találhatók:
  • Egyensúly ,
  • Előrendelés ,
  • Csoportos fellépés ,
    • Vetítőtér ,
    • Mátrix kongruencia , ekvivalens mátrixok , hasonló mátrixok ,
    • Kongruens háromszögek , hasonló háromszögek ,
  • Építőipari relatív egészek , Body frakciók , kiegészítve egy metrikus tér ,
  • Quotient topológia ,
  • Homotópia egyenértékűsége ,
  • Csíra .

Ellenpéldák

Számos kapcsolat reflexív, szimmetrikus vagy tranzitív, anélkül, hogy mindhárman egyszerre lennének:

• egy előrendelésre van reflexív és tranzitív definíció, de nem szimmetrikus általában (például: olyan sorrendben egy pár );
• Egy részleges ekvivalenciareláció  (a) jelentése szimmetrikus és tranzitív definíció, de nem reflexszerű általában ( triviális példa  : egy nem üres halmaz , a kapcsolatban üres grafikon);
• a tolerancia kapcsolatban van reflexív és szimmetrikus definíció, de nem tranzitív általában (például: a egész számok, a kapcsolatban ~ által meghatározott: m ~ n ⇔ | m - n | ≤ 1).

jegyzet

Megfelelő osztályt tudunk biztosítani ekvivalencia relációval. Megadhat akár egyenértékűségi osztályokat is, de ezek maguk is lehetnek saját osztályok, és általában nem alkotnak egészet (pl. Az ekvipotencia kapcsolata az osztályhalmazokban).

Mennyiségi készlet

Ez a név adott partíció E fent kiemelt, ami egy részhalmaza az összesP(E){\ displaystyle {\ mathcal {P}} (E)} rész E .

Meghatározás

Adott egy ekvivalencia reláció ~ on E , a hányados sor az E a kapcsolat ~, jelöljük E / ~, az a részhalmaza ekvivalencia osztályok: P(E){\ displaystyle {\ mathcal {P}} (E)}

E/∼ = {[x]∈P(E)∣x∈E}.{\ displaystyle {E / \ sim} ~ = ~ \ {[x] \ in {\ mathcal {P}} (E) \ x közepe \ in E \}.}

A hányadoshalmaz nevezhetõ „ E ~ halmazával ~ vagy" az E halmaznak, amelyet modulo ~ -nak tekintünk . E nevek mögött az az elképzelés áll, hogy az E-nek megfelelő hányadosban kell dolgozni , de nem kell megkülönböztetnünk közöttük a ~ szerinti egyenértékű elemeket.

Kanonikus túlzás

A kanonikus térkép p , az E a hányados készlet, amely minden elemének E társítja az ekvivalencia osztály:

o:E→E/∼x↦[x]{\ displaystyle {\ begin {mátrix} p: & E & \ rightarrow & {E / \ sim} \\ & x & \ mapsto & [x] \ end {mátrix}}}

• az szürjektıv megépítésével, mert a kép a térkép az itt ;E/∼{\ displaystyle E / \ sim}x↦[x]{\ displaystyle x \ mapsto [x]}E{\ displaystyle E}P(E){\ displaystyle {\ mathcal {P}} (E)}
• általában nem injektív (hacsak a ~ nem egyenlőség ), mivel csak nekünk vano(x)=o(y)⇔x∼y.{\ displaystyle p (x) = p (y) \ Balra mutató nyíl x \ sim y.}

Ez megfelel a következő általános tulajdonság , amely kifejezi, hogy minden térkép definiált E akinek kapcsolódó ekvivalencia reláció a kevésbé finom , mint ~ „átmegy a hányados” E / ~ egyedülálló módon:

Faktorizációs tétel  -  Bármely f  : E → F térkép esetében,amely kielégíti az [ x ~ y ⇒ f ( x ) = f ( y )] értéket, létezik egy egyedi g  : E / ~ → F térkép, amely f = g ∘ p .

Ez a g térkép - amelynek tehát ugyanaz a képe, mint az f-nek - csak akkor injektív, ha x ~ y ⇔ f ( x ) = f ( y ).

Mennyiségi szerkezet

Ha E egy algebrai struktúrával , lehetséges, hogy át az utóbbi a hányados beállított, feltéve, hogy a szerkezet kompatibilis  (EN) az ekvivalencia reláció, azaz két eleme E viselkednek azonos módon képest a szerkezet, ha ugyanabba az egyenértékűségi osztályba tartoznak. A hányadoshalmazt az ekvivalencia-reláció biztosítja ezután a kezdeti szerkezet hányadosszerkezetével .

Például, ha ⊤ az E- vel kapcsolatos belső törvény, amely kompatibilis a ~ -val, vagyis az ellenőrzéssel

( x ~ x ' és y ~ y' ) ⇒ x ⊤ y ~ x ' ⊤ y' ,

az "  ~ ~ törvény törvény hányados törvénye " az " E / ~ hányados halmaz összetételének törvénye", amely az x és y ekvivalencia osztályokhoz illeszkedik az x ⊤ y ekvivalencia osztályhoz . "

(Formálisabban: ha p megjegyezzük az E × E → E / ~ × E / ~, ( x , y ) ↦ ([ x ], [ y ]) és f az E × E → E / ~, ( x , y ) x [ x ⊤ y ], a kompatibilitási hipotézist átírják p ( x , y ) = p ( x ' , y' ) ⇒ f ( x , y ) = f ( x ' , y' ). A fenti tényezőtétel tehát meghatározhatjuk a hányados törvényt, mint egyedi g térképet  : E / ~ × E / ~ → E / ~ úgy, hogy f = g ∘ p .)

Példák

• A valós számok rendezett mezőjén a "szoros értelemben vett" relációnak "ugyanaz a jele van", és az egyenértékűségnek három osztálya van:
  • szigorúan pozitív egész számok halmaza;
  • szigorúan negatív egészek halmaza;
  • a szingulett {0}.

A szorzás kompatibilis ezzel az ekvivalencia relációval, és az előjel szabály a hányados törvény kifejezője.

• Ha E csoportszerkezettel rendelkezik, akkor bármely normál alcsoporthoz társítunk egy kompatibilis ekvivalencia relációt, amely lehetővé teszi a hányadoscsoport definiálását .

Generált ekvivalencia reláció

Az E halmazon legyen R bináris reláció, amelyet a grafikonjával azonosítunk. Az R- t tartalmazó összes ekvivalencia-reláció kereszteződését E- nek nevezzük az R által generált ekvivalencia-relációnak ( E-n ) . Ez egyenlő az R ∪ R −1 tranzitív reflexív záródásával .

Megjegyzések és hivatkozások

1. N. Bourbaki , A matematika elemei  : halmazelmélet [ a kiadások részlete ], P.  II-41 a Google Könyvekben .
2. (in) WD Wallis , Útmutató a diszkrét matematikához , Springer Science + Business Media ,2011, 2 nd  ed. ( DOI  10.1007 / 978-0-8176-8286-6 , olvassa el online ) , p.  104.
3. Bourbaki, halmazelmélet , p.  II-42.
4. N. Bourbaki, A matematika elemei, Algebra, 1–3 . Fejezet , p.  I-11.
5. Jean-Pierre Ramis , André Warusfel et al. , Matematika. Minden az egyben a Licencért. 1. szint , Dunod ,2013, 2 nd  ed. , 896  p. ( ISBN  978-2-10-060013-7 , online olvasás ) , p.  31.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">