MAT1030 – Diskret matematikk Forelesning 13: Funksjoner Dag Normann

Forelesning 13: Funksjoner

Dag Normann

Matematisk Institutt, Universitetet i Oslo

25. februar 2008

Opphenting

Forrige forelesning fortsatte vi innføringen av ekvivalensrelasjoner.

Vi definerte hva vi mener med partielle ordninger og med totale ordninger.

Deretter snakket vi generelt om funksjoner og spesielt om injektive funksjoner.

Det ble mange nye begreper, og før vi fortsetter, skal vi repetere, ved hjelp av eksempler, noen av disse begrepene.

Vi starter med ˚a se p˚a en funksjon og et par avledede relasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 2

Opphenting

Forrige forelesning fortsatte vi innføringen av ekvivalensrelasjoner.

Vi definerte hva vi mener med partielle ordninger og med totale ordninger.

funksjoner.

Det ble mange nye begreper, og før vi fortsetter, skal vi repetere, ved hjelp av eksempler, noen av disse begrepene.

Vi starter med ˚a se p˚a en funksjon og et par avledede relasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 2

Opphenting

Forrige forelesning fortsatte vi innføringen av ekvivalensrelasjoner.

Vi definerte hva vi mener med partielle ordninger og med totale ordninger.

Deretter snakket vi generelt om funksjoner og spesielt om injektive funksjoner.

Det ble mange nye begreper, og før vi fortsetter, skal vi repetere, ved hjelp av eksempler, noen av disse begrepene.

Vi starter med ˚a se p˚a en funksjon og et par avledede relasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 2

Opphenting

Forrige forelesning fortsatte vi innføringen av ekvivalensrelasjoner.

Vi definerte hva vi mener med partielle ordninger og med totale ordninger.

Deretter snakket vi generelt om funksjoner og spesielt om injektive funksjoner.

Det ble mange nye begreper, og før vi fortsetter, skal vi repetere, ved hjelp av eksempler, noen av disse begrepene.

MAT1030 – Diskret matematikk 25. februar 2008 2

Opphenting

Forrige forelesning fortsatte vi innføringen av ekvivalensrelasjoner.

Vi definerte hva vi mener med partielle ordninger og med totale ordninger.

Deretter snakket vi generelt om funksjoner og spesielt om injektive funksjoner.

Det ble mange nye begreper, og før vi fortsetter, skal vi repetere, ved hjelp av eksempler, noen av disse begrepene.

Vi starter med ˚a se p˚a en funksjon og et par avledede relasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 2

Opphenting

Eksempel

Laf(a) være tverrsummen til a∈An˚ar vi antar at vi bruker vanlig titallsystem.

f er en funksjon, hvor Aerdefinisjonsomr˚adet.

I dette tilfellet har vi ikke bestemt verdiomr˚adet, men uten ˚a tenke oss om vet vi at tverrsummen vil være et naturlig tall.

Vi ser derfor p˚af som en funksjon f :A→N

MAT1030 – Diskret matematikk 25. februar 2008 3

Opphenting

Eksempel

LaA={1, . . . ,100}

Laf(a) være tverrsummen til a∈An˚ar vi antar at vi bruker vanlig titallsystem.

f er en funksjon, hvor Aerdefinisjonsomr˚adet.

I dette tilfellet har vi ikke bestemt verdiomr˚adet, men uten ˚a tenke oss om vet vi at tverrsummen vil være et naturlig tall.

Vi ser derfor p˚af som en funksjon f :A→N

MAT1030 – Diskret matematikk 25. februar 2008 3

Opphenting

Eksempel

LaA={1, . . . ,100}

Laf(a) være tverrsummen til a∈An˚ar vi antar at vi bruker vanlig titallsystem.

I dette tilfellet har vi ikke bestemt verdiomr˚adet, men uten ˚a tenke oss om vet vi at tverrsummen vil være et naturlig tall.

Vi ser derfor p˚af som en funksjon f :A→N

MAT1030 – Diskret matematikk 25. februar 2008 3

Opphenting

Eksempel

LaA={1, . . . ,100}

Laf(a) være tverrsummen til a∈An˚ar vi antar at vi bruker vanlig titallsystem.

f er en funksjon, hvor Aerdefinisjonsomr˚adet.

I dette tilfellet har vi ikke bestemt verdiomr˚adet, men uten ˚a tenke oss om vet vi at tverrsummen vil være et naturlig tall.

Vi ser derfor p˚af som en funksjon f :A→N

MAT1030 – Diskret matematikk 25. februar 2008 3

Opphenting

Eksempel

LaA={1, . . . ,100}

Laf(a) være tverrsummen til a∈An˚ar vi antar at vi bruker vanlig titallsystem.

f er en funksjon, hvor Aerdefinisjonsomr˚adet.

I dette tilfellet har vi ikke bestemt verdiomr˚adet, men uten ˚a tenke oss om vet vi at tverrsummen vil være et naturlig tall.

f :A→N

MAT1030 – Diskret matematikk 25. februar 2008 3

Opphenting

Eksempel

LaA={1, . . . ,100}

Laf(a) være tverrsummen til a∈An˚ar vi antar at vi bruker vanlig titallsystem.

f er en funksjon, hvor Aerdefinisjonsomr˚adet.

I dette tilfellet har vi ikke bestemt verdiomr˚adet, men uten ˚a tenke oss om vet vi at tverrsummen vil være et naturlig tall.

Vi ser derfor p˚a f som en funksjon

f :A→N

MAT1030 – Diskret matematikk 25. februar 2008 3

Eksempel

LaA={1, . . . ,100}

Laf(a) være tverrsummen til a∈An˚ar vi antar at vi bruker vanlig titallsystem.

f er en funksjon, hvor Aerdefinisjonsomr˚adet.

I dette tilfellet har vi ikke bestemt verdiomr˚adet, men uten ˚a tenke oss om vet vi at tverrsummen vil være et naturlig tall.

Vi ser derfor p˚a f som en funksjon f :A→N

MAT1030 – Diskret matematikk 25. februar 2008 3

Opphenting

Eksempel (Fortsatt)

Er f injektiv?

Kravet var at for alle aog b i A, s˚a skalf(a)6=f(b) n˚ar a6=b. Men f(63) =f(72) = 9, s˚af er ikke injektiv.

Kan vi bestemme bildemengden tilf?

Bildemengden vil være B={1,2,3,4, . . . ,18}.

MAT1030 – Diskret matematikk 25. februar 2008 4

Opphenting

Eksempel (Fortsatt) Er f injektiv?

Men f(63) =f(72) = 9, s˚af er ikke injektiv. Kan vi bestemme bildemengden tilf?

Bildemengden vil være B={1,2,3,4, . . . ,18}.

MAT1030 – Diskret matematikk 25. februar 2008 4

Opphenting

Eksempel (Fortsatt) Er f injektiv?

Kravet var at for alle aog b i A, s˚a skalf(a)6=f(b) n˚ar a6=b.

Men f(63) =f(72) = 9, s˚af er ikke injektiv. Kan vi bestemme bildemengden tilf?

Bildemengden vil være B={1,2,3,4, . . . ,18}.

MAT1030 – Diskret matematikk 25. februar 2008 4

Opphenting

Eksempel (Fortsatt) Er f injektiv?

Kravet var at for alle aog b i A, s˚a skalf(a)6=f(b) n˚ar a6=b.

Men f(63) =f(72) = 9, s˚af er ikke injektiv.

Bildemengden vil være B={1,2,3,4, . . . ,18}.

MAT1030 – Diskret matematikk 25. februar 2008 4

Opphenting

Eksempel (Fortsatt) Er f injektiv?

Kravet var at for alle aog b i A, s˚a skalf(a)6=f(b) n˚ar a6=b.

Men f(63) =f(72) = 9, s˚af er ikke injektiv.

Kan vi bestemme bildemengden tilf?

Bildemengden vil være B={1,2,3,4, . . . ,18}.

MAT1030 – Diskret matematikk 25. februar 2008 4

Eksempel (Fortsatt) Er f injektiv?

Kravet var at for alle aog b i A, s˚a skalf(a)6=f(b) n˚ar a6=b.

Men f(63) =f(72) = 9, s˚af er ikke injektiv.

Kan vi bestemme bildemengden tilf?

Bildemengden vil være B={1,2,3,4, . . . ,18}.

MAT1030 – Diskret matematikk 25. februar 2008 4

Opphenting

Eksempel (Fortsatt)

Vi definerer n˚a to relasjoner p˚aAved hjelp av f: LaaRb hvis f(a) =f(b).

LaaSb hvisf(a)<f(b)∨(aRb∧a≤b)

ErR ellerS refleksiv? ErR ellerS irrefleksiv? ErR ellerS symmetrisk? ErR ellerS antisymmetrisk? ErR ellerS transitiv?

MAT1030 – Diskret matematikk 25. februar 2008 5

Opphenting

Eksempel (Fortsatt)

Vi definerer n˚a to relasjoner p˚a Aved hjelp av f:

LaaRb hvis f(a) =f(b).

LaaSb hvisf(a)<f(b)∨(aRb∧a≤b)

ErR ellerS irrefleksiv? ErR ellerS symmetrisk? ErR ellerS antisymmetrisk? ErR ellerS transitiv?

MAT1030 – Diskret matematikk 25. februar 2008 5

Opphenting

Eksempel (Fortsatt)

Vi definerer n˚a to relasjoner p˚a Aved hjelp av f: LaaRb hvis f(a) =f(b).

LaaSb hvisf(a)<f(b)∨(aRb∧a≤b)

ErR ellerS refleksiv? ErR ellerS irrefleksiv? ErR ellerS symmetrisk? ErR ellerS antisymmetrisk? ErR ellerS transitiv?

MAT1030 – Diskret matematikk 25. februar 2008 5

Opphenting

Eksempel (Fortsatt)

Vi definerer n˚a to relasjoner p˚a Aved hjelp av f: LaaRb hvis f(a) =f(b).

LaaSb hvisf(a)<f(b)∨(aRb∧a≤b)

ErR ellerS irrefleksiv? ErR ellerS symmetrisk? ErR ellerS antisymmetrisk? ErR ellerS transitiv?

MAT1030 – Diskret matematikk 25. februar 2008 5

Opphenting

Eksempel (Fortsatt)

Vi definerer n˚a to relasjoner p˚a Aved hjelp av f: LaaRb hvis f(a) =f(b).

LaaSb hvisf(a)<f(b)∨(aRb∧a≤b) ErR ellerS refleksiv?

ErR ellerS irrefleksiv? ErR ellerS symmetrisk? ErR ellerS antisymmetrisk? ErR ellerS transitiv?

MAT1030 – Diskret matematikk 25. februar 2008 5

Opphenting

Eksempel (Fortsatt)

Vi definerer n˚a to relasjoner p˚a Aved hjelp av f: LaaRb hvis f(a) =f(b).

LaaSb hvisf(a)<f(b)∨(aRb∧a≤b) ErR ellerS refleksiv?

ErR ellerS irrefleksiv?

ErR ellerS antisymmetrisk? ErR ellerS transitiv?

MAT1030 – Diskret matematikk 25. februar 2008 5

Opphenting

Eksempel (Fortsatt)

Vi definerer n˚a to relasjoner p˚a Aved hjelp av f: LaaRb hvis f(a) =f(b).

LaaSb hvisf(a)<f(b)∨(aRb∧a≤b) ErR ellerS refleksiv?

ErR ellerS irrefleksiv?

ErR ellerS symmetrisk?

ErR ellerS antisymmetrisk? ErR ellerS transitiv?

MAT1030 – Diskret matematikk 25. februar 2008 5

Opphenting

Eksempel (Fortsatt)

Vi definerer n˚a to relasjoner p˚a Aved hjelp av f: LaaRb hvis f(a) =f(b).

LaaSb hvisf(a)<f(b)∨(aRb∧a≤b) ErR ellerS refleksiv?

ErR ellerS irrefleksiv?

ErR ellerS symmetrisk?

ErR ellerS antisymmetrisk?

MAT1030 – Diskret matematikk 25. februar 2008 5

Opphenting

Eksempel (Fortsatt)

Vi definerer n˚a to relasjoner p˚a Aved hjelp av f: LaaRb hvis f(a) =f(b).

LaaSb hvisf(a)<f(b)∨(aRb∧a≤b) ErR ellerS refleksiv?

ErR ellerS irrefleksiv?

ErR ellerS symmetrisk?

ErR ellerS antisymmetrisk?

ErR ellerS transitiv?

MAT1030 – Diskret matematikk 25. februar 2008 5

Opphenting

Eksempel (Fortsatt)

La oss se p˚aR først.

Vi ser atR ersymmetriskfordif(b) =f(a) n˚arf(a) =f(b).

Vi ser atR ertransitivfordif(a) =f(c) hvis vi har atf(a) =f(b) og atf(b) =f(c).

SidenA6=∅ogR er refleksiv, er ikkeR samtidigirrefleksiv. Sidenf ikke er injektiv ogR er symmetrisk, kan ikkeR være antisymmetrisk

Det betyr at R er en ekvivalensrelasjon.

Vi har ikke brukt noen spesielle egenskaper vedAellerf, s˚a relasjoner konstruert p˚a denne m˚aten vil alltidvære ekvivalensrelasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 6

Opphenting

Eksempel (Fortsatt) La oss se p˚aR først.

Vi ser atR errefleksivfordif(a) =f(a) for allea∈A. Vi ser atR ersymmetriskfordif(b) =f(a) n˚arf(a) =f(b).

Vi ser atR ertransitivfordif(a) =f(c) hvis vi har atf(a) =f(b) og atf(b) =f(c).

SidenA6=∅ogR er refleksiv, er ikkeR samtidigirrefleksiv. Sidenf ikke er injektiv ogR er symmetrisk, kan ikkeR være antisymmetrisk

Det betyr at R er en ekvivalensrelasjon.

Vi har ikke brukt noen spesielle egenskaper vedAellerf, s˚a relasjoner konstruert p˚a denne m˚aten vil alltidvære ekvivalensrelasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 6

Opphenting

Eksempel (Fortsatt) La oss se p˚aR først.

Vi ser atR errefleksivfordif(a) =f(a) for alle a∈A.

Vi ser atR ertransitivfordif(a) =f(c) hvis vi har atf(a) =f(b) og atf(b) =f(c).

SidenA6=∅ogR er refleksiv, er ikkeR samtidigirrefleksiv. Sidenf ikke er injektiv ogR er symmetrisk, kan ikkeR være antisymmetrisk

Det betyr at R er en ekvivalensrelasjon.

Vi har ikke brukt noen spesielle egenskaper vedAellerf, s˚a relasjoner konstruert p˚a denne m˚aten vil alltidvære ekvivalensrelasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 6

Opphenting

Eksempel (Fortsatt) La oss se p˚aR først.

Vi ser atR errefleksivfordif(a) =f(a) for alle a∈A.

Vi ser atR ersymmetriskfordif(b) =f(a) n˚arf(a) =f(b).

Vi ser atR ertransitivfordif(a) =f(c) hvis vi har atf(a) =f(b) og atf(b) =f(c).

SidenA6=∅ogR er refleksiv, er ikkeR samtidigirrefleksiv. Sidenf ikke er injektiv ogR er symmetrisk, kan ikkeR være antisymmetrisk

Det betyr at R er en ekvivalensrelasjon.

Vi har ikke brukt noen spesielle egenskaper vedAellerf, s˚a relasjoner konstruert p˚a denne m˚aten vil alltidvære ekvivalensrelasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 6

Opphenting

Eksempel (Fortsatt) La oss se p˚aR først.

Vi ser atR errefleksivfordif(a) =f(a) for alle a∈A.

Vi ser atR ersymmetriskfordif(b) =f(a) n˚arf(a) =f(b).

Vi ser atR ertransitivfordif(a) =f(c) hvis vi har atf(a) =f(b) og atf(b) =f(c).

Sidenf ikke er injektiv ogR er symmetrisk, kan ikkeR være antisymmetrisk

Det betyr at R er en ekvivalensrelasjon.

Vi har ikke brukt noen spesielle egenskaper vedAellerf, s˚a relasjoner konstruert p˚a denne m˚aten vil alltidvære ekvivalensrelasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 6

Opphenting

Eksempel (Fortsatt) La oss se p˚aR først.

Vi ser atR errefleksivfordif(a) =f(a) for alle a∈A.

Vi ser atR ersymmetriskfordif(b) =f(a) n˚arf(a) =f(b).

Vi ser atR ertransitivfordif(a) =f(c) hvis vi har atf(a) =f(b) og atf(b) =f(c).

SidenA6=∅ogR er refleksiv, er ikkeR samtidigirrefleksiv.

Sidenf ikke er injektiv ogR er symmetrisk, kan ikkeR være antisymmetrisk

Det betyr at R er en ekvivalensrelasjon.

Vi har ikke brukt noen spesielle egenskaper vedAellerf, s˚a relasjoner konstruert p˚a denne m˚aten vil alltidvære ekvivalensrelasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 6

Opphenting

Eksempel (Fortsatt) La oss se p˚aR først.

Vi ser atR errefleksivfordif(a) =f(a) for alle a∈A.

Vi ser atR ersymmetriskfordif(b) =f(a) n˚arf(a) =f(b).

Vi ser atR ertransitivfordif(a) =f(c) hvis vi har atf(a) =f(b) og atf(b) =f(c).

SidenA6=∅ogR er refleksiv, er ikkeR samtidigirrefleksiv.

Sidenf ikke er injektiv ogR er symmetrisk, kan ikkeR være antisymmetrisk

Vi har ikke brukt noen spesielle egenskaper vedAellerf, s˚a relasjoner konstruert p˚a denne m˚aten vil alltidvære ekvivalensrelasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 6

Opphenting

Eksempel (Fortsatt) La oss se p˚aR først.

Vi ser atR errefleksivfordif(a) =f(a) for alle a∈A.

Vi ser atR ersymmetriskfordif(b) =f(a) n˚arf(a) =f(b).

Vi ser atR ertransitivfordif(a) =f(c) hvis vi har atf(a) =f(b) og atf(b) =f(c).

SidenA6=∅ogR er refleksiv, er ikkeR samtidigirrefleksiv.

Sidenf ikke er injektiv ogR er symmetrisk, kan ikkeR være antisymmetrisk

Det betyr at R er en ekvivalensrelasjon.

Vi har ikke brukt noen spesielle egenskaper vedAellerf, s˚a relasjoner konstruert p˚a denne m˚aten vil alltidvære ekvivalensrelasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 6

Eksempel (Fortsatt) La oss se p˚aR først.

Vi ser atR errefleksivfordif(a) =f(a) for alle a∈A.

Vi ser atR ersymmetriskfordif(b) =f(a) n˚arf(a) =f(b).

Vi ser atR ertransitivfordif(a) =f(c) hvis vi har atf(a) =f(b) og atf(b) =f(c).

SidenA6=∅ogR er refleksiv, er ikkeR samtidigirrefleksiv.

Sidenf ikke er injektiv ogR er symmetrisk, kan ikkeR være antisymmetrisk

Det betyr at R er en ekvivalensrelasjon.

Vi har ikke brukt noen spesielle egenskaper vedAellerf, s˚a relasjoner konstruert p˚a denne m˚aten vil alltidvære ekvivalensrelasjoner.

MAT1030 – Diskret matematikk 25. februar 2008 6

Opphenting

Eksempel (Fortsatt)

N˚ar vi n˚a vet at R er en ekvivalensrelasjon, kan vi prøve ˚a finne ekvivalensklassene.

Vi vil ha en ekvivalensklasse for hver tverrsum:

1 {1,10,100}

2 {2,11,20}

3 {3,12,21,30}

4 {4,13,22,31,40}

5 {5,14,23,32,41,50} osv.

MAT1030 – Diskret matematikk 25. februar 2008 7

Opphenting

Eksempel (Fortsatt)

N˚ar vi n˚a vet at R er en ekvivalensrelasjon, kan vi prøve ˚a finne ekvivalensklassene.

Vi vil ha en ekvivalensklasse for hver tverrsum:

2 {2,11,20}

3 {3,12,21,30}

4 {4,13,22,31,40}

5 {5,14,23,32,41,50} osv.

MAT1030 – Diskret matematikk 25. februar 2008 7

Opphenting

Eksempel (Fortsatt)

N˚ar vi n˚a vet at R er en ekvivalensrelasjon, kan vi prøve ˚a finne ekvivalensklassene.

Vi vil ha en ekvivalensklasse for hver tverrsum:

1 {1,10,100}

2 {2,11,20}

3 {3,12,21,30}

4 {4,13,22,31,40}

5 {5,14,23,32,41,50} osv.

MAT1030 – Diskret matematikk 25. februar 2008 7

Opphenting

Eksempel (Fortsatt)

N˚ar vi n˚a vet at R er en ekvivalensrelasjon, kan vi prøve ˚a finne ekvivalensklassene.

Vi vil ha en ekvivalensklasse for hver tverrsum:

1 {1,10,100}

3 {3,12,21,30}

4 {4,13,22,31,40}

5 {5,14,23,32,41,50} osv.

MAT1030 – Diskret matematikk 25. februar 2008 7

Opphenting

Eksempel (Fortsatt)

N˚ar vi n˚a vet at R er en ekvivalensrelasjon, kan vi prøve ˚a finne ekvivalensklassene.

Vi vil ha en ekvivalensklasse for hver tverrsum:

1 {1,10,100}

2 {2,11,20}

3 {3,12,21,30}

4 {4,13,22,31,40}

5 {5,14,23,32,41,50} osv.

MAT1030 – Diskret matematikk 25. februar 2008 7

Opphenting

Eksempel (Fortsatt)

N˚ar vi n˚a vet at R er en ekvivalensrelasjon, kan vi prøve ˚a finne ekvivalensklassene.

Vi vil ha en ekvivalensklasse for hver tverrsum:

1 {1,10,100}

2 {2,11,20}

3 {3,12,21,30}

5 {5,14,23,32,41,50} osv.

MAT1030 – Diskret matematikk 25. februar 2008 7

Opphenting

Eksempel (Fortsatt)

N˚ar vi n˚a vet at R er en ekvivalensrelasjon, kan vi prøve ˚a finne ekvivalensklassene.

Vi vil ha en ekvivalensklasse for hver tverrsum:

1 {1,10,100}

2 {2,11,20}

3 {3,12,21,30}

4 {4,13,22,31,40}

5 {5,14,23,32,41,50} osv.

MAT1030 – Diskret matematikk 25. februar 2008 7

Opphenting

Eksempel (Fortsatt)

N˚ar vi n˚a vet at R er en ekvivalensrelasjon, kan vi prøve ˚a finne ekvivalensklassene.

Vi vil ha en ekvivalensklasse for hver tverrsum:

1 {1,10,100}

2 {2,11,20}

3 {3,12,21,30}

4 {4,13,22,31,40}

5 {5,14,23,32,41,50}

MAT1030 – Diskret matematikk 25. februar 2008 7

Opphenting

Eksempel (Fortsatt)

N˚ar vi n˚a vet at R er en ekvivalensrelasjon, kan vi prøve ˚a finne ekvivalensklassene.

Vi vil ha en ekvivalensklasse for hver tverrsum:

1 {1,10,100}

2 {2,11,20}

3 {3,12,21,30}

4 {4,13,22,31,40}

5 {5,14,23,32,41,50}

osv.

MAT1030 – Diskret matematikk 25. februar 2008 7

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc.

Vi ser atS er transitiv. Anta ataSbogbSa

Da m˚af(a)≤f(b) ogf(b)≤f(a), s˚af(a) =f(b), det vil si ataRb. Da era≤bogb≤as˚aa=b

Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS.

aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc.

Vi ser atS er transitiv. Anta ataSbogbSa

Da m˚af(a)≤f(b) ogf(b)≤f(a), s˚af(a) =f(b), det vil si ataRb. Da era≤bogb≤as˚aa=b

Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc.

Vi ser atS er transitiv. Anta ataSbogbSa

Da m˚af(a)≤f(b) ogf(b)≤f(a), s˚af(a) =f(b), det vil si ataRb. Da era≤bogb≤as˚aa=b

Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea

LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc.

Vi ser atS er transitiv. Anta ataSbogbSa

Da m˚af(a)≤f(b) ogf(b)≤f(a), s˚af(a) =f(b), det vil si ataRb. Da era≤bogb≤as˚aa=b

Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc. Vi ser atS er transitiv.

Anta ataSbogbSa

Da era≤bogb≤as˚aa=b

Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc. Vi ser atS er transitiv.

Anta ataSbogbSa

Da m˚af(a)≤f(b) ogf(b)≤f(a), s˚af(a) =f(b), det vil si ataRb. Da era≤bogb≤as˚aa=b

Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc.

Vi ser atS er transitiv. Anta ataSbogbSa

Da era≤bogb≤as˚aa=b

Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc. Vi ser atS er transitiv.

Anta ataSbogbSa

Da m˚af(a)≤f(b) ogf(b)≤f(a), s˚af(a) =f(b), det vil si ataRb. Da era≤bogb≤as˚aa=b

Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc. Vi ser atS er transitiv.

Anta ataSbogbSa

Da era≤bogb≤as˚aa=b Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc. Vi ser atS er transitiv.

Anta ataSbogbSa

Da m˚af(a)≤f(b) ogf(b)≤f(a), s˚af(a) =f(b), det vil si ataRb.

Da era≤bogb≤as˚aa=b Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc. Vi ser atS er transitiv.

Anta ataSbogbSa

Da m˚af(a)≤f(b) ogf(b)≤f(a), s˚af(a) =f(b), det vil si ataRb.

Da era≤b ogb≤as˚aa=b

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc. Vi ser atS er transitiv.

Anta ataSbogbSa

Da m˚af(a)≤f(b) ogf(b)≤f(a), s˚af(a) =f(b), det vil si ataRb.

Da era≤b ogb≤as˚aa=b Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10 S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc. Vi ser atS er transitiv.

Anta ataSbogbSa

Da m˚af(a)≤f(b) ogf(b)≤f(a), s˚af(a) =f(b), det vil si ataRb.

Da era≤b ogb≤as˚aa=b Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Fortsatt)

La oss s˚a se p˚a egenskapene tilS. aSb ⇔f(a)<f(b)∨(aRb∧a≤b)

S errefleksiv fordiaRa∧a≤afor allea LaaSb ogbSc.

Hvisf(a)<f(b) ellerf(b)<f(c) vilf(a)<f(c), ogaSc.

Hvisf(a) =f(b) =f(c) har vi ata≤b≤c, s˚a da har vi ogs˚a ataSc. Vi ser atS er transitiv.

Anta ataSbogbSa

Da m˚af(a)≤f(b) ogf(b)≤f(a), s˚af(a) =f(b), det vil si ataRb.

Da era≤b ogb≤as˚aa=b Det følger atS erantisymmetrisk.

Konklusjonen er atS er en partiell ordning.

Oppgave: Vis at S er en total ordning, og skriv ned de 10S-første tallene.

MAT1030 – Diskret matematikk 25. februar 2008 8

Opphenting

Eksempel (Injektive funksjoner)

Vi skal se p˚a tre funksjoner, og spørre om de er injektive:

baklengs.

2 B er mengden av uendelige desimalutviklinger αogg(α) er det tilsvarende reelle tallet.

3 C er mengden av positive reelle tall som har en eksakt 32-bits representasjonr, og hvisr representerer talletx lar vih(r) være tallet som representerer√

x.

f vil være injektiv, for hvis vi speiler to forskjellige ord, vil speilbildene bli forskjellige.

MAT1030 – Diskret matematikk 25. februar 2008 9

Opphenting

Eksempel (Injektive funksjoner)

Vi skal se p˚a tre funksjoner, og spørre om de er injektive:

1 Aer alle ordw godkjent som norske ord, ogf(w) er ordetw skrevet baklengs.

2 B er mengden av uendelige desimalutviklinger αogg(α) er det tilsvarende reelle tallet.

3 C er mengden av positive reelle tall som har en eksakt 32-bits representasjonr, og hvisr representerer talletx lar vih(r) være tallet som representerer√

x.

f vil være injektiv, for hvis vi speiler to forskjellige ord, vil speilbildene bli forskjellige.

MAT1030 – Diskret matematikk 25. februar 2008 9

Opphenting

Eksempel (Injektive funksjoner)

Vi skal se p˚a tre funksjoner, og spørre om de er injektive:

1 Aer alle ordw godkjent som norske ord, ogf(w) er ordetw skrevet baklengs.

tilsvarende reelle tallet.

3 C er mengden av positive reelle tall som har en eksakt 32-bits representasjonr, og hvisr representerer talletx lar vih(r) være tallet som representerer√

x.

f vil være injektiv, for hvis vi speiler to forskjellige ord, vil speilbildene bli forskjellige.

MAT1030 – Diskret matematikk 25. februar 2008 9

Opphenting

Eksempel (Injektive funksjoner)

Vi skal se p˚a tre funksjoner, og spørre om de er injektive:

1 Aer alle ordw godkjent som norske ord, ogf(w) er ordetw skrevet baklengs.

2 B er mengden av uendelige desimalutviklingerαogg(α) er det tilsvarende reelle tallet.

3 C er mengden av positive reelle tall som har en eksakt 32-bits representasjonr, og hvisr representerer talletx lar vih(r) være tallet som representerer√

x.

f vil være injektiv, for hvis vi speiler to forskjellige ord, vil speilbildene bli forskjellige.

MAT1030 – Diskret matematikk 25. februar 2008 9

Opphenting

Eksempel (Injektive funksjoner)

Vi skal se p˚a tre funksjoner, og spørre om de er injektive:

1 Aer alle ordw godkjent som norske ord, ogf(w) er ordetw skrevet baklengs.

2 B er mengden av uendelige desimalutviklingerαogg(α) er det tilsvarende reelle tallet.

3 C er mengden av positive reelle tall som har en eksakt 32-bits representasjonr, og hvisr representerer talletx lar vih(r) være tallet som representerer√

x.

bli forskjellige.

MAT1030 – Diskret matematikk 25. februar 2008 9

Opphenting

Eksempel (Injektive funksjoner)

Vi skal se p˚a tre funksjoner, og spørre om de er injektive:

1 Aer alle ordw godkjent som norske ord, ogf(w) er ordetw skrevet baklengs.

2 B er mengden av uendelige desimalutviklingerαogg(α) er det tilsvarende reelle tallet.

3 C er mengden av positive reelle tall som har en eksakt 32-bits representasjonr, og hvisr representerer talletx lar vih(r) være tallet som representerer√

x.

f vil være injektiv, for hvis vi speiler to forskjellige ord, vil speilbildene bli forskjellige.

MAT1030 – Diskret matematikk 25. februar 2008 9

Opphenting

Eksempel (Fortsatt)

desimalutviklinger, eksempelvis

0,9999· · ·= 1,0000· · · .

h kan ikke være injektiv fordi hvis et tall ligger mellom 2⁻²⁴ og 2²⁴, vil kvadratroten ligge mellom 2⁻¹² og 2¹².

Vi har alts˚a langt færre binære tall til disposisjon for ˚a representere

√x enn x selv, s˚a funksjonen kan ikke være injektiv. Her har vi egentlig brukt noe som kalles skuffeprinsippet, dueslagsprinsippet eller p˚a engelskthe pigeon hole principle.

Vi er n˚a ferdige med opphentingen, og fortsetter der vi slapp p˚a onsdag.

MAT1030 – Diskret matematikk 25. februar 2008 10