1
Mer om relasjoner
En relasjon R på en mengde A er en delmengde av produktmengden AA. La Rvære en relasjon på en mengde A.
• R er refleksiv hvis (a,a)R for alle aA.
• R er symmetrisk hvis (a,b)R, så er (b,a)R.
• R er antisymmetrisk hvis abog (a,b)R, så er (b,a)R.
• R er transitiv hvis (a,b)R og (b,c)R, så er(a,c)R.
Ekvivalensrelasjoner
En relasjon R på en mengde A er en Ekvivalensrelasjon hvis den er refleksiv, symmetrisk og transitiv.
Eksempel 2
Gitt relasjonen R på A der A er heltallene og R = {(a, b) | a + b er et partall}
Vi skal avgjøre om R er en ekvivalensrelasjon ved å resonnere oss frem til svaret, dvs. uten å tegne opp grafen eller skrive opp matrisen.
2
• Er R refleksiv? Ja, fordi a + a = 2a er et partall.
• Er R symmetrisk? Ja, fordi hvis a + b er et partall må b + a være et partall siden a + b = b + a.
• Er R transitiv? Ja. Begrunnelse:
La (a, b) ∈ R og (b, c) ∈ R, dvs. a + b er et partall og b + c er et partall. Vi må vise at (a, c) ∈ R, dvs. at a + c er et partall. Summen av to partall er et partall og da får vi at
(a + b) + (b + c) = 2x a + c + 2b = 2x
a + c = 2x – 2b = 2(x-b).
Vi ser at a + c et partall, dvs. (a, c) ∈ R og følgelig er R transitiv. Siden R både er refleksiv, symmetrisk og transitiv er R en ekvivalensrelasjon.
Eksempel 3
La A være mengde av alle hele tall og la R = {(a, b) | a b (mod 5)}.
Dette betyr at a og b er ledd i samme aritmetiske tallfølge med differanse lik 5 mellom hver ledd. (Alle leddene i en aritmetisk tallfølge er kongruente med hverandre).
Husk at a b (mod 5) hvis 5 går opp i a – b.
Det betyr også at a mod 5 = b mod 5.
• Er R refleksiv? Ja, fordi at a a (mod 5)
• Er R symmetrisk? Ja, fordi hvis a b (mod 5) så er b a (mod 5)
• Er R transitiv? Ja, fordi hvis a b (mod 5) og b c (mod 5), så a c (mod 5). (a mod 5 = b mod 5 = c mod 5), dvs. a, b og c er alle ledd i den samme aritmetiske tallfølgen.
Følgelig er R en ekvivalensrelasjon.
Partielle ordninger
En relasjon R på en mengde A er en Partiell ordning hvis den er refleksiv, anti- symmetrisk og transitiv.
3
Eksempel 4
La A = {1, 2, 3, 4} og R = {(a, b) | a ≤ b}. R kan også skrives helt ut:
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3,3), (3, 4), (4, 4)}
1. R er refleksiv.
2. R er ikke symmetrisk.
3. R er antisymmetrisk
4. Hvis a, b og c er tre tall slik at a ≤ b og b ≤ c, så er a ≤ c.
R er derfor transitiv.
Siden R er både refleksiv, antisymmetrisk og transitiv er R en partiell ordning.
Partisjoner (oppdelinger)
Gitt en mengde A, og delmengdene A1 og A2, der A1 ∪ A2 = A A1 ∩ A2 = Ø
dvs. at A1 ogA2 utgjør til sammen hele A, samt at A1 ogA2 disjunkte mengder uten felles elementer. Vi sier da et A1 ogA2 utgjør en partisjon av A. Et annet ord for partisjon er oppdeling.
Eksempel
La A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, der
A1 = {1, 3, 5, 7, 9}, dvs. mengde av oddetallene i A A2 = {2, 4, 6, 8, 10} dvs. mengde av partallene i A A1 ∪ A2 = A
A1 ∩ A2 = Ø, dvs. A1 ogA2 er disjunkte mengder uten felles elementer.
Delmengdene A1 ogA2 utgjør en partisjon av A.
4
Definisjon: En partisjon (oppdeling)
En samling delmengder A1, A2, A3, . . . , An av en mengde A utgjør en partisjon av A hvis A1A2A3 . . . An = A og AiAj = Ø for alle i j.
Ekvivalensklasser
La R være en ekvivalensrelasjon på en mengde A.
La a ∈ A.
Ekvivalensklassen til a betegnes som [𝑎]R
og er beskrevet som følgende delmengde av A:
[𝑎]R = { b ∈ A| (a, b) ∈ R }
Hvis (a, b) er et verdipar i R er ekvivalensklassen til a mengden av alle andrekoordinater i verdipar der a er førstkoordinat.
Eksempel
La A være heltallene og R = {(a, b)| a ≡ b(mod 5)}
Vi får da følgende ekvivalensklasser:
5
[0]R = {…, -10, -5, 0, 5, 10, 15, ….}
[1]R = {…, -9, -4, 1, 6, 11, 16, ….}
[2]R = {…, -8, -3, 2, 7, 12, 17, ….}
[3]R = {…, -7, -2, 3, 8, 13, 18, ….}
[4]R = {…, -6, -1, 4, 9, 14, 19, ….}
Vi får at [5]R =[0]R, [6]R =[1]R, [7]R =[2]R, [8]R =[3]R, [9]R =[4]R,
Setninger 1
La R være en ekvivalensrelasjon på en mengde A. Da vil ekvivalensklassene til R utgjøre en partisjon av A.
6
Setning 2
Omvendt: Gitt en partisjon av en mengde A. Da definerer den en
ekvivalensrelasjon R på A ved at alle elementene i hver delmengde i partisjonen relateres til hverandre og seg selv.
Eksempel
La A = { a, b, c, d, e, f, g }.
La A1 = {a, b, c}, A2 = {d, e} og A3 = {f, g}
Vi ser at A1 ∪ A2 ∪ A3 = A og at A1 ∩ A2 = Ø, A1 ∩ A3 = Ø, og A2 ∩ A3 = Ø
Dette definerer følgende ekvivalensrelasjon:
R = {(a, a), (b, b), (c, c), (a, b), (b, a), (a, c), (c, a), (b, c), (c, b), (d, d), (e, e), (d, e), (e, d), (f, f), (g, g), (f, g), (g, f)}
7
