Den forestilling ensemblist af ækvivalensrelation er allestedsnærværende i matematik . Det giver i et sæt mulighed for at relatere elementer, der ligner en bestemt egenskab.
Disse elementer kan således grupperes sammen efter "bundter" af lignende elementer, hvorved begrebet ækvivalensklasse defineres , for endelig at konstruere nye sæt ved at "assimilere" lignende elementer til et og det samme element. Vi ender derefter med forestillingen om et kvotientsæt .
En ækvivalensrelation på et sæt E er et binært forhold ~ på E, som samtidig er refleksivt , symmetrisk og transitivt .
Mere eksplicit:
Ved refleksivitet falder E derefter sammen med definitionssættet ~ (som udledes af grafen ved projektion ). Omvendt er det tilstrækkeligt for en binær relation på E- symmetrisk og transitiv at være refleksiv, at dens sæt af definition er helt E.
Vi kan også definere en ækvivalensrelation som en refleksiv og cirkulær binær relation .
En binær relation ~ siges at være cirkulær, hvis vi hver gang har x ~ y og y ~ z , vi også har z ~ x .
Fastsætte et sæt E og en ækvivalensrelation ~ på E .
Vi definerer ækvivalensklassen [ x ] for et element x af E som sættet af y af E således at x ~ y :
Vi kalder en repræsentant for [ x ] ethvert element i [ x ] og et system af klassepræsentanter enhver del af E, der indeholder nøjagtigt en repræsentant pr. Klasse.
Omvendt enhver partition af en mængde E definerer en ækvivalensrelation på E . Dette skaber en naturlig sammenhæng mellem partiets partitioner og ækvivalensforholdene på dette sæt. Antallet af ækvivalensrelationer på et sæt med n elementer er derfor lig med Bell nummer B n , som kan beregnes ved induktion .
Mange relationer er refleksive, symmetriske eller transitive uden at være alle tre på samme tid:
Vi kan give en ordentlig klasse med et ækvivalensforhold. Du kan endda definere ækvivalensklasser, men de kan selv være egne klasser og danner generelt ikke en helhed (f.eks. Forholdet mellem ækvipotens i klassesæt).
Dette navn er givet til skillevæggen E fremhævet ovenfor, som er en delmængde af alle dele af E .
Givet et ækvivalensforhold ~ på E , er kvotsættet af E ved forholdet ~, betegnet med E / ~, delmængden af ækvivalensklasser:
Kvottsættet kan også kaldes "det sæt E, der er kvotificeret af ~" eller "det sæt E, der betragtes som modulo ~". Ideen bag disse navne er at arbejde i kvotsættet som i E , men uden at skelne imellem de ækvivalente elementer ifølge ~.
Det kanoniske kort p , af E i kvotsættet, som til hvert element i E forbinder dets ækvivalensklasse:
Den opfylder følgende universelle egenskab , som udtrykker, at ethvert kort defineret på E, hvis tilknyttede ækvivalensforhold er mindre fint end ~ ", overføres til kvotienten" E / ~ på en unik måde:
Faktoriseringsteori - For ethvert kort f : E → F, der tilfredsstiller [ x ~ y ⇒ f ( x ) = f ( y )], findes der et unikt kort g : E / ~ → F, således at f = g ∘ p .
Dette kort g - som derfor har det samme billede som f - er injektivt, hvis og kun hvis x ~ y ⇔ f ( x ) = f ( y ).
Hvis E har en algebraisk struktur , er det muligt at overføre sidstnævnte til kvotienten, forudsat at strukturen er kompatibel (en) med ækvivalensforholdet, dvs. to elementer i E opfører sig på samme måde med hensyn til strukturen, hvis de tilhører den samme ækvivalensklasse. Kvottsættet forsynes derefter med kvotientstrukturen i den oprindelige struktur ved ækvivalensforholdet.
For eksempel hvis ⊤ er en intern lov om E kompatibel med ~, dvs. verificering
( x ~ x ' og y ~ y' ) ⇒ x ⊤ y ~ x ' ⊤ y' ,
den " kvotienten lov af loven ⊤ ved ~" er defineret som "loven om sammensætningen på kvotienten sæt E / ~ der, følgende ækvivalenter klasser af x og y , matcher ækvivalens klasse af x ⊤ y . "
(Mere formelt: ved at betegne p udsprøjtningen E × E → E / ~ × E / ~, ( x , y ) ↦ ([ x ], [ y ]) og f kortlægningen E × E → E / ~, ( x , y ) ↦ [ x ⊤ y ], er kompatibilitetshypotesen omskrevet p ( x , y ) = p ( x ' , y' ) ⇒ f ( x , y ) = f ( x ' , y' ). Ved at anvende faktorisering teorem ovenfor , kan vi derfor definere kvotienten lov som den unikke kort g : E / ~ × E / ~ → E / ~ således at f = g ∘ s .)
EksemplerLad R på et sæt E være et binært forhold identificeret med dets graf. Skæringspunktet mellem alle ækvivalensrelationer på E , der indeholder R kaldes ækvivalensrelationen (på E ) genereret af R . Det er lig med den transitive refleksive lukning af R ∪ R −1 .