Ækvivalensklasse

Fra Wikipedia, den frie encyklopædi

En ækvivalensklasse er i matematikken en mængde af ækvivalente objekter. Dette er selvfølgelig mht. til 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.

[redigér] 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.

Denne artikel om matematik er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.