Ækvivalensklasse
En ækvivalensklasse er i matematikken en mængde af ækvivalente objekter. Dette er selvfølgelig mht. en given ækvivalensrelation. Lad derfor ~ være en ækvivalensrelation på en mængde X. Typisk skriver man ækvivalensklasser vha. en repræsentant a ∈ X for klassen, så
- [a] := { b ∈ X | a ~ b }.
Mængden af disse ækvivalensklasser udgør en partition af X, og skrives X/~. Dvs. foreningen af alle ækvivalensklasser udgør hele X, og de er alle parvist disjunkte.
Bevis for at ækvivalensklasser udgør en partition
Lad i resten af dette afsnit ~ være en ækvivalensrelation på en mængde X.
Lemma 1: a ∈ [a] for alle a ∈ X.
Bevis. Da ~ er refleksiv er a ~ a, og dermed må a ∈ [a] per definitionen af ækvivalensklassen [a].
Lemma 2: [a] = [b] ⇔ a ~ b for alle a, b ∈ X.
Bevis. Antag først [a] = [b]. Per lemma 1 er nu b ∈ [b] = [a] = { c ∈ X | a ~ c }, så dermed må a ~ b. Antag nu a ~ b, og lad c ∈ [a]. Altså er a ~ c, og da ~ er transitiv og symmetrisk, må b ~ c. Per definitonen af [a] må så c ∈ [b], og det er nu vist, at [a] ⊆ [b]. At [b] ⊆ [a] vises på helt samme måde.
Sætning 1: [a] ≠ [b] ⇒ [a] ∩ [b] = Ø for alle a, b ∈ X.
Bevis. Antag for modstrid, at der findes et c ∈ [a] ∩ [b]. Altså er a ~ c og b ~ c, men da ~ er transitiv og symmetrisk, må a ~ b. Lemma 2 siger nu, at [a] = [b], hvilket klart strider mod [a] ≠ [b].
Sætning 2: Foreningen af alle ækvivalensklasserne i X/~ udgør hele X.
Bevis. Lad a være et vilkårligt element i X. Nu er a indeholdt i ækvivalensklassen [a] per lemma 1, og dermed er a også indeholdt i foreningen af alle ækvivalensklasser.
Korrollar: Ækvivalensklasserne X/~ udgør en partition af X.
Bevis. Sætning 1 og 2.
 | Spire Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den. |