Ekvivalensrelationer

Vi har nu hunnit till kapitel 3, som inleds med två avsnitt som huvudsakligen behandlar funktionsbegreppet. Som Vretblad påpekar har dessa avsnitt sin huvudsakliga tillämpning inom matematisk analys, vilket enligt min mening får som konsekvens att avsnitten utgår ur den här kursen.

Däremot innehåller avsnitten 3.3-3.4 utmärkt allmänmatematiskt stoff om relationer och framförallt ekvivalensrelationer.

I kursboken antas alla relationer vara relationer mellan två storheter, men det finns naturligtvis relationer mellan godtyckligt antal storheter. Exempelvis är den relation mellan 4 punkter i planet som gäller om punkterna A och B ligger lika långt från varandra som punkterna C och D en s.k. 4-ställig relation relation medan de som behandlas i kursboken kan betecknas som 2-ställiga

En viss typ av 2-ställiga relationer kallas ekvivalensrelationer och förekommer mycket ofta i matematiska tillämpningar. De har den egenskapen att den delar upp grundmängden i ett antal disjunkta delmängder, s.k.ekvivalensklasser, som bidrager till en strukturering eller ordning av grundmängden.

Om man detaljstuderar 2-ställiga relationer visar det sig att egenskapen att inducera ekvivalensklasser kan sägas bestå av tre komponenter eller villkor på relationen R:

Reflexivitet ( R(x,x) )
Symmetri ( R(x,y) => R(y,x) )
Transitivitet ( R(x,y) & R(y,z) => R(x,z) )

Om man testar ovanstående villkor på den arketypiska ekvivalensrelationen " = ", blir allt mycket klarare:
x = x gäller ju. Därmed är relationen reflexiv.
Om x = y gäller, gäller naturligtvis också y = x, alltså en symmetrisk relation.
Slutligen. om x = y och y = z så är ju också x = z, därmed transitiv.
Relationen " = ", har den litet speciella egenskapen att dess ekvivalensklasser är mängder som bara innehåller ett element. Att detta är undantag inser man om man tar några andra exempel på ekvivalensrelationer:
' x är (hel)syskon med y' är en ekvivalensrelation (om man antar att man är syskon till sig själv) vars ekvivalensklasser bestå av syskongrupper. (Endabarn liksom de som endast har halvsyskon bildar här ekvivalensklasser med bara ett element).
Släktskapsförhållanden kan vara nog så krångliga och utgör ett bra övningsfält för resonemang om ekvivalensrelationer.
Vilken/vilka av följande relationer är ekvivalensrelationer?:
1. ' x är kusin med y'
2. ' x och y har en gemensam förfader 4 generationer tillbaka'.
3. ' x och y är båda ättlingar till Evert Blom.'

SVAR

ISU2:6 betraktar jag som en lagom uppgift att reflektera över ekvivalensrelationer med. Vad man behöver göra är alltså att kolla de tre villkoren för ekvivalens och motivera så tydligt som möjligt att relationen E verkligen är reflexiv, symmetrisk och transitiv.


Kongruenser

Kongruenser är en typ av ekvivalensrelationer som delar in de hela talen i ekvivalensklasser. Man skriver alltså xy (mod n) om differensen x - y är delbar med n.
Exempel: 2713 (mod 7), eftersom 27 - 13 = 2*7.

Räknereglerna för kongruenser, som finns samlade i Sats 2 s. 65, leder till en elegant och kraftfull kalkyl. Typiska exempel på problem som kongruensräkning löser är följande:

1) Visa att 1927 + 893 är delbart med 17.
2) Visa att de tre sista siffrorna i 231 är 648
3) Visa att 36n + 39 är delbart med 7 för alla naturliga tal n.
Innan vi börjar räkna vill jag dock påminna om våra vanliga potensregler som t.ex. betyder att (23)4 = 23*4 och 4546 = 45+6.

Allmänt formuleras lagarna:

(ab)c = abc och
abac = ab+c

Lösning till 1) :
192 (mod17), alltså 1927227 (mod 17).
Men 29 = 512 = 510 + 2 = 17*30 + 2, varför 292 (mod 17) och 227 = (29)3238 (mod 17). Men 8 + 893 = 901 = 17*53, varför 1927 + 8930 (mod 17).


Lösning till 2) :
Räkna med (mod 1000) för att bestämma de tre sista siffrorna.
210 = 1024, varför 21024 (mod 1000).
Alltså 231 = 2*(210)32*243 (mod 1000).
Men 24 = 23*3 och 243 = 29*33, så 231210*3324*27 = 648 (mod 1000).


Lösning till 3) :
33 = 27-1 (mod 7).
Alltså 36n = (33)2n(-1)2n1 (mod 7).
Dessutom 39 = (33)3(-1)3-1 (mod 7).
Alltså 36n + 391 - 10 (mod 7) dvs, 7 delar 36n + 39.


Några kommentarer: Kalkylen är faktiskt en ganska nöjsam sysselsättning bara man kommer i gång med den. Det är ganska fascinerande att se hur de riktigt stora talen liksom smälter ned under räkningarnas gång
Samtidigt har man ju möjlighet att visa sig från sin kreativa sida genom att göra upptäckter som 292 (mod 17), 21024 (mod 1000) , 33-1 (mod 7) osv.
Här är dock att märka att lösningen inte står och faller med att man hittar den snyggaste mod-relationen. Ofta handlar det om att man gör någonting och inte fastnar helt. Även små steg leder till målet.
Särskilt när det förekommer godtyckliga heltal n i exponenten är det en god strategi att söka efter relationer av typen a1 (mod b) eftersom 1n = 1 oberoende av n.

Dessa små tips tillsammans med en noggrann genomläsning av kapitel 3.5 torde räcka mer än väl för ett lyckat resultat på ISU2:7.
Jag påminner också om listan över de 1000 första primtalen som kanske kan vara användbar i det här avsnittet.

LYCKA TILL!