Ækvivalensrelation

En ækvivalensrelation $R$ på en mængde X er en relation, der opfylder følgende for alle $a,b,c\in X$

1. Refleksiv: $(a,a)\in R$
2. Transitiv $(a,b)\in R\wedge (b,c)\in R\Rightarrow (a,c)\in R$
3. Symmetrisk: $(a,b)\in R\Rightarrow (b,a)\in R$

Ækvivalensrelationer bliver ofte betegnet med en tilde, sådan at $(a,b)\in R$ bliver skrevet $a\sim b$. Med denne notation kan aksiomerne omskrives:

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". Denne relation kaldes kongruens modulo 4 ("a og b er kongruente modulo 4"), og 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 }

Indenfor gruppeteori kan dette generaliseres: hvis $H$ er en delgruppe af en gruppe $G$, så er to elementer $a,b\in G$ højrekongruente modulo $H$ hvis $ab^{-1}\in H$. Dette definerer en ækvivalensrelation, da

1. $aa^{-1}=1\in H$, hvor 1 er neutralelementet i $G$ (og dermed også $H$)
2. $ab^{-1}\in H\wedge bc^{-1}\in H\Rightarrow (ab^{-1})(bc^{-1})=ac^{-1}\in H$
3. $ab^{-1}\in H\iff (ab^{-1})^{-1}=ba^{-1}\in H$

Ligeledes defineres venstrekongruens ved $b^{-1}a\in H$. Hvis disse to er sammenfaldende, siges $H$ at være en normal delgruppe af $G$.

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.

Referencer

Spire Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.