• No results found

Mer om relasjoner En relasjon på en mengde er en delmengde av produktmengden . La være en relasjon på en mengde .

N/A
N/A
Protected

Academic year: 2022

Share "Mer om relasjoner En relasjon på en mengde er en delmengde av produktmengden . La være en relasjon på en mengde ."

Copied!
7
0
0

Laster.... (Se fulltekst nå)

Fulltekst

(1)

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)

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)

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)

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)

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)

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)

7

Referanser

RELATERTE DOKUMENTER

I denne replikken til Nikolai Hegertuns essay En stille revolusjon av utviklingspolitikken, argumenterer jeg for at det er liten grunn til å være strengt normativ i dette

Kontrollert donasjon e er sirkulatorisk død beny es kun på pasienter med ubotelig hjerneskade som med intensivmedisinsk behandling ikke har vist tegn til bedring som kunne gi håp

Samtidig bør vi bli mer bevisste på at dagens opphengthet i tall og teknologi ikke nødvendigvis vil føre til best helse, og heller starte prosjekter som for eksempel måler

Vi er ikke kjent med retningslinjer som tilrår bruk av kvetiapin (eller andre antipsykotika) for behandling av insomni.. Norske nasjonale anbefalinger u rykker bekymring og er

Sandberg har sikkert fortalt historien mange ganger før, men blir fortsa blank i øynene når hun forteller om den store le elsen – og hvor viktig det er at det finnes hjertestarter

I studier hvor ulike etniske grupper slås sammen og kategoriseres som én, kan infor- masjon om ulikhet mellom gruppene når det gjelder helsestatus og risikofaktorer bli

Bevisstgjøring om samarbeid og forskjellighet burde i større grad inngå i utdanningen til mange yrkes- grupper som skal ut og samhandle i helse- vesen, forskning, skole og

Det kan være flere grunner til de e – avdelingsoverlegene ved store avdelinger bruker mer av sin arbeidstid til lederoppgaver, behovet for kvalitetssikringsarbeid er større ved