Ækvivalensrelation

En ækvivalensrelation på en mængde X er en relation ~, der opfylder følgende:

1. Refleksiv: a ~ a for alle a ∈ X.
2. Transitiv: a ~ b og b ~ c ⇒ a ~ c for alle a, b, c ∈ X.
3. Symmetrisk: a ~ b ⇒ b ~ a for alle a, b ∈ X.

Er a ~ b siger man, at a og b er ækvivalente.

På enhver mængde X er relationen lighed (=) og relationen, hvor alle elementer i X er ækvivalente, begge ækvivalensrelationer. Det er den mindste hhv. største ækvivalensrelation på X. Opfattet som mængder er lighed nemlig diagonalen { (a, a) | a ∈ X }, og den anden relation er hele X×X.

Givet en ækvivalensrelation ~ på en mængde X kan man dele X op i en række delmængder, hvor alle elementer er indbyrdes ækvivalente. Disse delmængder kaldes ækvivalensklasser og skrives typisk vha. en repræsentant for klassen: [a] = { b ∈ X | a ~ b } ⊆ X. Mængden af alle disse ækvivalensklasser betegnes X/~, og de udgør en partition af X. Dvs. at alle ækvivalensklasser er disjunkte, og foreningen af dem alle er X.

Omvendt kan man også konstruere en ækvivalensrelation på en mængde X ud fra en partition (X_α), ved at sætte a ~ b ⇔ a og b er indeholdt i samme X_α.

Eksempler

På de hele tal Z kan man definere relationen ~ ved

a ~ b ⇔ 4 | a - b.

Her skal 4 | x betyde "4 går op i x". Dette er en ækvivalensrelation, da

1. 4 | a - a = 0 ⇒ a ~ a,
2. a ~ b og b ~ c ⇒ 4 | a - b og 4 | b - c ⇒ 4 | (a - b) + (b - c) = a - c ⇒ a ~ c,
3. a ~ b ⇒ 4 | a - b ⇒ 4 | -(a - b) = b - a ⇒ b ~ a,

for alle a, b, c ∈ Z. Mængden af ækvivalensklasser mht. denne relation Z/~ kommer nu til at bestå af disse fire mængder:

• [0] = [4] = [508] = { ..., -8, -4, 0, 4, 8, ... } = { 4n | n ∈ Z }
• [1] = [5] = [-47] = { ..., -7, -3, 1, 5, 9, ... } = { 4n + 1 | n ∈ Z }
• [2] = [-2] = [3438] = { ..., -6, -2, 2, 6, 10, ... } = { 4n + 2 | n ∈ Z }
• [3] = [-1] = [8999] = { ..., -5, -1, 3, 7, 11, ... } = { 4n + 3 | n ∈ Z }

På mængden af alle mennesker har man relationen "født i samme stjernetegn som". Dette er en ækvivalensrelation, da

1. enhver er født i samme stjernetegn som sig selv,
2. hvis a er født i samme stjernetegn som b og b er født i samme stjernetegn som c, så er a også født i samme stjernetegn som c,
3. hvis a er født i samme stjernetegn som b, så er b også født i samme stjernetegn som a.

Dette deler alle mennesker ind i 12 ækvivalensklasser af folk, der er født i samme stjernetegn.

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