Johdatus matematiikkaan [version 19 Aug 2014 ed.] [PDF]

Zitiervorschau

JOHDATUS MATEMATIIKKAAN Petri Juutinen 27. toukokuuta 2014

Sis¨ alt¨ o 1 Joukko-oppia 1.1 Joukko-opin perusk¨asitteit¨a ja merkint¨oj¨a

. . . . . . . . . . .

2 Todistamisen ja matemaattisen p¨ a¨ attelyn alkeita 2.1 Alkupala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 P¨a¨attelemisest¨a ja lauselogiikasta . . . . . . . . . . . . . . . 2.2.1 V¨aitelause . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Loogisista konnektiiveista . . . . . . . . . . . . . . . 2.2.3 Kvanttoreista . . . . . . . . . . . . . . . . . . . . . . 2.3 Todistamisesta . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Suora todistus . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Ep¨asuora todistus . . . . . . . . . . . . . . . . . . . . 2.3.3 Todistamisen harjoittelua: jaollisuus . . . . . . . . . . 2.3.4 Todistamisen harjoittelua: rationaali- ja irrationaaliluvuista . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.5 Tiheist¨a joukoista . . . . . . . . . . . . . . . . . . . . 2.3.6 Konstruktiivinen vs. ei-konstruktiivinen . . . . . . . . 2.3.7 Suora vai ep¨asuora p¨a¨attely? . . . . . . . . . . . . . . 2.3.8 Induktiotodistus . . . . . . . . . . . . . . . . . . . . 2.4 V¨aitteen osoittaminen v¨a¨ar¨aksi . . . . . . . . . . . . . . . . 2.5 Joukko-oppi ja todistaminen . . . . . . . . . . . . . . . . . . 3 Funktioista 3.1 Funktioihin liittyvi¨a perusk¨asitteit¨a 3.1.1 Kuvajoukko ja alkukuva . . 3.1.2 Yhdistetty funktio . . . . . 3.2 Kuvausten ominaisuuksia . . . . . . 3.2.1 Injektio ja surjektio . . . . . 3.2.2 K¨a¨anteisfunktio . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

4 4

. . . . . . . . .

13 13 14 14 15 19 22 22 24 27

. . . . . . .

29 30 31 33 37 45 46

. . . . . .

50 50 52 56 60 60 64

4 Joukkojen mahtavuus 73 4.1 Yht¨amahtavuus . . . . . . . . . . . . . . . . . . . . . . . . . . 73

1

4.2

Mahtavuuksien vertailua . . . . . . . . . . . . . . . . . . . . . 78

2

Alkulause “Much more important than specific mathematical results are the habits of mind used by the people who create those results.” Cuoco, Goldenberg and Mark (1996) Kurssi “Johdatus matematiikkaan” on tarkoitettu ensimm¨aiseksi opintojaksoksi kaikille matematiikkaa opiskeleville ja sen ensisijaisena tavoitteena on madaltaa kynnyst¨a lukion ja yliopisto-opintojen v¨alill¨a. Keskeisimm¨an sis¨all¨on kurssilla muodostavat todistamisen ja joukko-opin alkeiden opettelu sek¨a kuvauksiin liittyviin perusk¨asitteisiin tutustuminen. Osaan kurssilla k¨asitelt¨avist¨a aiheista opiskelijat ovat tutustuneet jo lukiossa, mutta n¨aidenkin kohdalla l¨ahestymis- ja esitystapa poikkeavat siit¨a mihin koulussa on yleens¨a totuttu. N¨aiden luentojen pohjana on toiminut kurssia aikaisemmin luennoineiden kollegojen muistiinpanojen lis¨aksi Lauri Kahanp¨a¨an, Harri H¨ogmanderin ja Matti Hannukaisen luentomoniste“Johdatus matematiikkaan”vuodelta 1992, sek¨a Richard Hammackin kirja “Book of Proof”.

3

Luku 1 Joukko-oppia “I don’t want to belong to any club that will accept people like me as a member“ Groucho Marx

1.1

Joukko-opin perusk¨ asitteit¨ a ja merkint¨ oj¨ a

T¨all¨a kurssilla emme l¨ahde problematisoimaan joukon k¨asitett¨a, vaan tyydymme naiiviin tulkintaan, jossa • joukko on kokoelma objekteja (alkioita), • jokaisesta objektista voidaan sanoa kuuluuko se kyseiseen joukkoon vai ei. T¨allainen m¨aa¨rittely riitt¨aa¨ hyvin varsinkin matematiikan opiskelun alkuvaiheessa, vaikka todellisuudessa joukon ja alkion k¨asitteisiin liittyy kaikenlaisia ongelmia, eik¨a joukko-oppi suinkaan ole niin yksinkertaista kuin ensisilm¨aykselt¨a saattaa vaikuttaa. Esimerkki 1.1.1. (a) Kokoelma {1, 2, 3} on joukko, jonka alkioita ovat luvut 1, 2 ja 3. (b) Kokoelma {suomi, ruotsi, norja} on joukko, jonka alkioita ovat sanat “suomi”, “ruotsi” ja “norja”. √ Esimerkiksi “tanska” ei ole t¨am¨an joukon alkio, eik¨a my¨osk¨a¨an luku 2. (c) Merkinn¨all¨a 1 1 1 1 {1, , , , , . . .} 2 3 4 5 4

tarkoitetaan joukkoa, joka koostuu kaikista muotoa n1 olevista luvuista, miss¨a n k¨ay l¨api kaikki positiiviset kokonaisluvut luvusta 1 alkaen. N¨ain 1 ollen esimerkiksi 134 on kyseisen joukon alkio, vaikka sit¨a ei olekaan listattu n¨akyviin. Kaksi joukkoa ovat samat, jos ne koostuvat t¨asm¨alleen samoista alkioista. Niinp¨a esimerkiksi {1, 2, 3} = {2, 3, 1} = {1, 1, 2, 3} ja {. . . , −2, −1, 0, 1, 2, . . .} = {0, 1, −1, 2, −2, . . .}. Usein on j¨arkev¨a¨a antaa tarkasteltavalle joukolle symbolinen nimi ja sen j¨alkeen viitata kyseiseen joukkoon kyseist¨a symbolia k¨aytt¨aen sen sijaan, ett¨a jokaisessa yhteydess¨a lueteltaisiin joukon alkiot. Voimme esimerkiksi kutsua joukkoa {1, 2, 3} joukoksi A, merkit¨aa¨n A = {1, 2, 3}, mink¨a j¨alkeen voidaan vaikkapa todeta, ett¨a luku 2 on joukon A alkio. Tietyt joukot ovat niin t¨arkeit¨a, ett¨a niill¨a on vakiintuneet merkinn¨at, joita tulisi aina k¨aytt¨a¨a. T¨allaisia joukkoja ovat esimerkiksi luonnollisten lukujen joukko N = {1, 2, 3, 4, 5, . . .}, kokonaislukujen joukko Z = {. . . , −2, −1, 0, 1, 2, 3, . . .}, ja reaalilukujen joukko R. Huomaa, ett¨a 0 ei ole luonnollinen luku(ainakaan t¨all¨a kurssilla!) . Merkinto a. Seuraavassa on listattu joitakin t¨arkeimpi¨a joukko-opin mer¨j¨ kint¨oj¨a ja merkint¨atapoja: (i) Merkint¨a x ∈ A tarkoitaa, ett¨a x on joukon A alkio. Se luetaan: “x kuuluu joukkoon A.” (ii) Merkint¨a y 6∈ A tarkoitaa, ett¨a y ei ole joukon A alkio ja luetaan: “y ei kuulu joukkoon A.” (iii) Joukko A on joukon B osajoukko, merkit¨aa¨n A ⊂ B, jos jokainen joukon A alkio on my¨os joukon B alkio. Merkint¨a A 6⊂ B puolestaan tarkoittaa, ett¨a joukko A ei ole joukon B osajoukko, eli on olemassa (ainakin yksi) alkio x ∈ A, joka ei kuulu joukkoon B. (iv) Joukot A ja B ovat samat, merkit¨aa¨n A = B, jos A ⊂ B ja B ⊂ A. 5

(v) Tyhj¨a joukko ∅ = {} on joukko, joka ei sis¨all¨a yht¨aa¨n alkiota. Esimerkki 1.1.2. Jos A = {1, 2, 3} ja B = {−1, 0, 1, 2, 3, 5}, niin A ⊂ B ja A ⊂ N. Vastaavasti B ⊂ Z, mutta B 6⊂ N, sill¨a −1 ∈ B ja −1 ∈ / N. Huomautus 1.1.3. Jokaiselle joukolle A p¨atee A ⊂ A ja ∅ ⊂ A. N¨aist¨a j¨alkimm¨ainen inkluusio (∅ ⊂ A) voi aluksi tuntua intuition vastaiselta, mutta sen voi perustella ep¨asuorasti: jos v¨aite ∅ ⊂ A ei olisi totta, niin silloin joukosta ∅ tulisi l¨oyty¨a ainakin yksi alkio, joka ei kuulu joukkoon A. Mutta koska tyhj¨ass¨a joukossa ei ole yht¨a¨an alkiota, ei kuvatunlaista alkiota voi olla olemassa. Niinp¨a ∅ on joukon A osajoukko. Joukon m¨a¨aritteleminen luettelemalla sen alkiot aaltosulkeissa voi joskus olla hankalaa ja erityisesti k¨aytett¨aess¨a merkint¨a¨a . . . saattaa j¨a¨ad¨a ep¨aselv¨aksi mitk¨a alkiot oikeastaan kuuluvatkaan k¨asitelt¨av¨aa¨n joukkoon. Lis¨aksi kaikkia joukkoja ei voida edes m¨a¨aritell¨a alkioita luettelemalla; t¨ah¨an palaamme kurssin loppupuolella. Esimerkki 1.1.4. M¨aa¨rittely A = {2, 4, 8, . . .} on liian ep¨am¨aa¨r¨ainen, sill¨a se ei kerro yksiselitteisesti mit¨a alkioita joukkoon A kuuluu. Emme tied¨a koostuuko A muotoa 2k olevista luvuista eksponentin k k¨aydess¨a l¨api kaikki positiiviset kokonaisluvut (t¨all¨oin joukkoon kuuluisivat siis mm. alkiot 2, 4, 8, 16, 32, 64 ja 128) vai onko kyseess¨a joukko, joka koostuu niist¨a parillisista positiivisista luvuista, jotka eiv¨at ole jaollisia luvulla 6 (t¨all¨oin joukkoon kuuluisivat siis mm. alkiot 2, 4, 8, 10, 14, 16 ja 20). Joukkoja m¨a¨aritell¨a¨ankin usein sanomalla niiden koostuvan kaikista alkioista, jotka toteuttavat tietyn ehdon. T¨all¨oin k¨aytet¨aa¨n merkint¨aa¨ {x : P (x)}, joka tarkoittaa kaikkien niiden alkioiden x joukkoa, joille ominaisuus P (x) on totta.1 Esimerkki 1.1.5. (i) Joukko {n ∈ N : n on pariton} koostuu kaikista parittomista luonnollisista luvuista, toisin sanoen {n ∈ N : n on pariton} = {1, 3, 5, 7, . . .}. (ii) Joukko {6, 8, 10, 12, 14, . . .} voidaan kirjoittaa t¨asm¨allisemmin muodossa {n ∈ N : n on parillinen ja n > 4}. √ (iii) Joukko {n √ ∈ N : n < 3} koostuu niist¨a luonnollisista luvuista n, joiden neli¨ojuuri n on pienempi kuin 3. Siisp¨a √ {n ∈ N : n < 3} = {1, 2, 3, . . . , 8}. 1

Joskus k¨ aytet¨ a¨ an my¨ os merkint¨aa¨ {x|P (x)} merkinn¨an {x : P (x)} sijaan.

6

(iv) Merkint¨a {k 2 : k ∈ Z, |k| < 4} tarkoittaa joukkoa, joka koostuu kaikista muotoa k 2 olevista luvuista, jossa luvun k t¨aytyy olla itseisarvoltaan lukua 4 pienempi kokonaisluku. T¨allaisia kokonaislukuja ovat −3, −2, −1, 0, 1, 2 ja 3, ja niiden neli¨ot ovat puolestaan 9, 4, 1, 0, 1, 4 ja 9. Siten {k 2 : k ∈ Z, |k| < 4} = {0, 1, 4, 9}. Huomautus 1.1.6. Merkinn¨an {x : P (x)} kanssa on syyt¨a olla huolellinen. Esimerkiksi A = {x ∈ R : x2 ∈ A} ei m¨a¨arittele joukkoa, sill¨a on mahdotonta p¨a¨atell¨a kuuluuko luku 2 joukkoon A vai ei. Nimitt¨ain, 2 kuuluu joukkoon A jos ja vain jos 22 = 4 kuuluu joukkoon A. Mutta kuuluuko 4 joukkoon A vai ei? Se taas riippuu siit¨a, kuuluuko 42 = 16 joukkoon A vai ei ... M¨ a¨ aritelm¨ a 1.1.7. Olkoot A ja B joukkoja. M¨a¨aritell¨a¨an joukkojen yhdiste A ∪ B = {x : x ∈ A tai x ∈ B}, leikkaus A ∩ B = {x : x ∈ A ja x ∈ B}, ja erotus A\B = {x : x ∈ A ja x 6∈ B}. Huomautus 1.1.8. 1. Matematiikan “tai” ei ole poissulkeva. Siksi ehto “x ∈ A tai x ∈ B” pit¨a¨a sis¨all¨a¨an mahdollisuuden, ett¨a x kuuluu molempiin joukoista A ja B. 2. Joskus joukkojen A ja B erotusta merkit¨aa¨n my¨os symbolilla A − B. Esimerkki 1.1.9. Olkoot A = {0, 1, α, β}, B = {1, 2, β}, C = {3, 4, γ}. T¨all¨oin A ∪ B = {0, 1, 2, α, β}, A ∩ B = {1, β}, A\B = {0, α}, B\A = {2}, (A ∩ B) ∪ C = {1, 3, 4, β, γ}. 7

Edell¨a m¨a¨ariteltyjen joukko-operaatioiden lis¨aksi tarvitaan matematiikassa varsin usein my¨os joukkojen tulon k¨asitett¨a. M¨ a¨ aritelm¨ a 1.1.10. Joukkojen A ja B tulojoukko eli karteesinen tulo on joukko A × B := {(a, b) : a ∈ A, b ∈ B}, miss¨a (a, b) = (c, d) jos ja vain jos a = c ja b = d. Joukko A × B koostuu siis kaikista j¨arjestetyist¨a pareista (a, b), miss¨a a on jokin joukon A alkio ja b jokin joukon B alkio. Esimerkki 1.1.11. Esimerkkej¨a tulojoukoista. (a) Jos A = {1, 2, 3} ja B = {α, β}, niin A × B = {(1, α), (1, β), (2, α), (2, β), (3, α), (3, β)}. (b) Tutuin esimerkki karteesisesta tulosta on xy-taso R2 , R2 = R × R = {(x, y) : x ∈ R, y ∈ R}, joka siis koostuu j¨arjestetyist¨a reaalilukupareista (x, y). Huomaa, ett¨a (1, 2) 6= (2, 1). (c) Karteesisen tulon avulla voidaan edelleen m¨aa¨ritell¨a R3 = R × R × R = xyz-avaruus Rn = R · · × R} = n-ulotteinen euklidinen avaruus | × ·{z n kpl

Tutuimpia esimerkkej¨a joukoista ovat reaalilukujen joukon v¨alit. Olkoon a, b ∈ R siten, ett¨a a ≤ b. Reaaliakselin R rajoitettu v¨ali on jokin seuraavista: [a, b] := { x ∈ R : ]a, b[ := { x ∈ R : [a, b[ := { x ∈ R : ]a, b] := { x ∈ R :

a ≤ x ≤ b} a < x < b} a ≤ x < b} a < x ≤ b}

(suljettu v¨ali) (avoin v¨ali) (puoliavoin v¨ali) (puoliavoin v¨ali)

Huomautus 1.1.12. Edell¨a sallitaan erikoistapaus a = b, kun tulkitaan, ett¨a [a, a] = {a} ja ]a, a[ = ∅.

8

Reaaliakselin R rajoittamattomia v¨alej¨a ovat puolestaan muotoa ]−∞, b] := { x ∈ R : ]−∞, b[ := { x ∈ R : [a, ∞[ := { x ∈ R : ]a, ∞[ := { x ∈ R : ]−∞, ∞[ := R

x ≤ b} x < b} a ≤ x} a < x}

olevat v¨alit. T¨ass¨a yhteydess¨a on hyv¨a muistuttaa siit¨a, ett¨a −∞ ja ∞ ovat pelkki¨a symboleja, eiv¨atk¨a reaalilukuja. Huomautus 1.1.13. Matematiikassa k¨aytett¨avien merkint¨ojen kanssa tulee olla huolellinen. Ei esimerkiksi ole yhdentekev¨a¨a millaisia sulkuja lausekkeissa k¨aytet¨a¨an: • merkint¨a {1, 2} tarkoittaa joukkoa, jonka alkioita ovat luvut 1 ja 2. • merkint¨a [1, 2] tarkoittaa reaaliakselin suljettua v¨ali¨a, jonka p¨a¨atepisteet ovat 1 ja 2. • merkint¨a (1, 2) tarkoittaa j¨arjestetty¨a paria, jonka ensimm¨ainen alkio on 1 ja toinen alkio 2. Joissakin yhteyksiss¨a merkint¨a (1, 2) voi my¨os tarkoittaa reaaliakselin avointa v¨ali¨a ]1, 2[. Useamman kuin kahden joukon yhdiste ja leikkaus m¨a¨aritell¨a¨an saman periaatteen mukaisesti kuin kahdenkin. M¨ a¨ aritelm¨ a 1.1.14. Olkoot A, B ja C joukkoja. M¨a¨aritell¨a¨an joukkojen yhdiste A ∪ B ∪ C = {x : x ∈ A tai x ∈ B tai x ∈ C}, ja leikkaus A ∩ B ∩ C = {x : x ∈ A ja x ∈ B ja x ∈ C}. Yhdiste ja leikkaus voidaan m¨a¨aritell¨a my¨os ¨a¨arett¨om¨an monelle joukolle: joukkojen Ai , i = 1, 2, 3, . . . yhdiste on ∞ [

Ai := {x : x ∈ Ai jollakin i = 1, 2, 3, . . . },

i=1

ja leikkaus

∞ \

Ai := {x : x ∈ Ai kaikilla i = 1, 2, 3, . . . }.

i=1

9

Esimerkki 1.1.15. Olkoon jokaiselle i ∈ N joukko Ai reaaliakselin suljettu v¨ali [i, i + 1]. T¨all¨oin siis A1 = [1, 2], A2 = [2, 3], ja niin edelleen. T¨all¨oin ∞ [

Ai = {x ∈ R : x ∈ Ai jollakin i = 1, 2, 3, . . . }

i=1

= {x ∈ R : x ∈ [i, i + 1] jollakin i = 1, 2, 3, . . . } = [1, 2] ∪ [2, 3] ∪ [3, 4] ∪ . . . = [1, ∞[ ja ∞ \

Ai = {x ∈ R : x ∈ Ai kaikilla i = 1, 2, 3, . . . }

i=1

= {x ∈ R : x ∈ [i, i + 1] kaikilla i = 1, 2, 3, . . . } = [1, 2] ∩ [2, 3] ∩ [3, 4] ∩ . . . = ∅.

Harjoitusteht¨ avi¨ a 1. Luokalla on 34 opiskelijaa. Heist¨a 21 laulaa kuorossa ja 16 soittaa jotakin soitinta. Nelj¨a opiskelijaa ei laula kuorossa eik¨a soita mit¨a¨an soitinta. (a) Kuinka moni luokan opiskelijoista laulaa kuorossa tai soittaa jotakin soitinta? (b) Kuinka moni luokan opiskelijoista laulaa kuorossa ja soittaa jotakin soitinta? (c) Kuinka moni kuorossa laulavista opiskelijoista ei soita mit¨a¨an soitinta? 2. Muodosta joukon {1, 2, 3, 4} kaikki osajoukot. 3. Olkoot A = {1, 2, 3, 4}, B = {3, 4, 5} ja C = {1, 2, 3}. Muodosta joukot (a) A ∪ B. (b) B ∩ Z. (c) A \ C. (d) A × C. (e) (A ∪ C) \ B. (f) A ∪ (C \ B).

10

4. Olkoon A = {0, 1, 2}. Mit¨a alkioita kuuluu joukkoon (a) A × A × A ? (b) {(x, y) ∈ A × A : y − x > 1} ? 5. Kirjoita seuraavat joukot muodossa {x : P (x)} (a) {1, 4, 9, 16, 25, 36, 49, . . .}. (b) {4, 5, 6, 7}. (c) {1, 21 , 13 , 14 , 15 , . . .}. 6. Esit¨a seuraavien joukkojen alkiot luettelomuodossa. (a) {x ∈ Z : − 2 ≤ x < 5}. (b) {x ∈ R : x2 + 5x = −6}. (c) {x ∈ R : cos x = 1}. (d) {5x : x ∈ Z, |2x| ≤ 8}. 7. M¨aa¨ritell¨a¨an joukko Ak jokaiselle k ∈ N asettamalla Ak = {−k, 0, k}. Mit¨a alkioita kuuluu joukkoon (a) A13 ? ∞ [ Ak ? (b) (c)

k=1 ∞ \

Ak ?

k=1 n

8. Olkoot A = { k2k+1 : k ∈ Z} ja B = { (−1) + 1 : n ∈ N}. Onko t¨all¨oin n totta, ett¨a (a) 1 ∈ A ? (b)

4 5

∈B ?

(c) 0 ∈ A ∩ B ? (d) A ⊂ Z ? (e) B ⊂ A ? (f) Z ⊂ A ∪ B ? Perustele. 11

9. Olkoot A = ]−1, 2[ ja B = ]1, 5[. M¨aa¨rit¨a perustellen joukot (a) A ∪ B. (b) A ∩ B. (c) B \ A. (d) {x2 : x ∈ A}. (e) {x + y : x ∈ A, y ∈ B}. 10. Olkoot Ak = [−2 + k1 , 2 − k1 ] kaikille k ∈ N. M¨a¨arit¨a perustellen joukot ∞ ∞ [ \ Ak ja Ak . k=1

k=1

11. Jos A ja B ovat (mit¨a tahansa) joukkoja, niin p¨ateek¨o aina (a) (A \ B) ∪ B = A ? (b) B = A \ (A \ B) ?

12

Luku 2 Todistamisen ja matemaattisen p¨ a¨ attelyn alkeita Matematiikka on deduktiivinen tiede eli tiede, jossa uutta tietoa luodaan p¨a¨attelem¨all¨a. Siksi jokaisen matematiikkaa opiskelevan on ensiarvoisen t¨arke¨a¨a tuntea logiikan ( = “oppi oikeasta ajattelusta”) perusteet ja oppia p¨a¨attelyiden tekemiseen liittyv¨at perusperiaatteet ja ajattelumallit. Tarkemmin aiheeseen perehdyt¨a¨an Logiikan kurssilla.

2.1

Alkupala

Esimerkki 2.1.1. (Rehdit ja retkut) Oletetaan, ett¨a on olemassa saari, jolla asuu tasan kahdenlaisia ihmisi¨a rehtej¨a ja retkuja. Rehdit puhuvat aina totta, retkut puolestaan valehtelevat aina. P¨a¨alle p¨ain rehtej¨a ja retkuja ei voi erottaa toisistaan. Kohtaat kolme saaren asukasta, henkil¨ot A, B ja C, joista A sanoo: ”Me olemme kaikki retkuja.” Henkil¨o B puolestaan v¨aitt¨a¨a, ett¨a ”T¨asm¨alleen yksi meist¨a on rehti.” Mit¨a tyyppi¨a A, B ja C ovat? Ratkaisu: Teht¨av¨an voisi ratkaista k¨aym¨all¨a l¨api kaikki mahdolliset kombinaatiot (joita on t¨ass¨a tapauksessa 23 = 8 kpl) yksi kerrallaan ja sulkemalla pois mahdottomat. Jatkon kannalta on kuitenkin hy¨odyllisemp¨a¨a pohtia, mit¨a henkil¨oiden A ja B lausumista voidaan p¨a¨atell¨a. • A v¨aitt¨a¨a kaikkien kolmen olevan retkuja. Jos h¨an olisi rehti, t¨am¨a v¨aite pit¨aisi paikkansa. Mutta silloin kaikki kolme, mukaan lukien A itse, olisivat siis retkuja. N¨ain ollen ei ole mahdollista, ett¨a A on rehti, joten h¨anen on pakko olla retku.

13

• Koska tied¨amme nyt, ett¨a A on retku, on h¨anen lausumansa “Me olemme kaikki retkuja” valheellinen v¨aitt¨am¨a. Ei siis pid¨a paikkaansa, ett¨a kaikki kolme olisivat retkuja, joten joukossa on joko 1 tai 2 rehti¨a (rehtej¨a ei voi olla kolmea, koska A tiedet¨a¨an jo retkuksi). • Jos rehtej¨a olisi 2, olisi tilanne siis sellainen, ett¨a A on retku ja B ja C rehtej¨a. T¨all¨oin sen, mit¨a B sanoo (”T¨asm¨alleen yksi meist¨a on rehti”) pit¨aisi olla totta, mutta n¨ainh¨an ei ole. Siisp¨a rehtej¨a ei voi olla kahta, vaan heit¨a on vain yksi. • Tied¨amme nyt, ett¨a rehtej¨a on t¨asm¨alleen yksi, joten se, mit¨a B sanoo, on totta. Niinp¨a henkil¨on B t¨aytyy olla rehti. Ja koska rehtej¨a on vain yksi, on henkil¨on C oltava retku. Vastaus: Henkil¨ot A ja C ovat retkuja, ja B on rehti.

2.2

P¨ a¨ attelemisest¨ a ja lauselogiikasta ”Logic will get you from A to B. Imagination will take you everywhere.“ Albert Einstein

2.2.1

V¨ aitelause

V¨aitelause eli propositio on lause, joka v¨aitt¨a¨a jotain ja josta voidaan sanoa (tai ainakin kysy¨a) onko se totta vai ei. T¨allainen m¨a¨arittely ei ehk¨a vaikuta kovin t¨asm¨alliselt¨a, mutta se riitt¨a¨a t¨all¨a kurssilla. Seuraava esimerkki toivottavasti valaisee asiaa. Esimerkki 2.2.1. V¨aitelauseita ja lauseita, jotka eiv¨at ole v¨aitelauseita: (a) 4 > 13 (ep¨atosi) (b) Hauki on kala. (tosi) (c) 3 ≥ 3 (tosi) √ (d) 2 ∈ Z. (ep¨atosi) (e) 1729 on pienin luonnollinen luku, joka voidaan esitt¨a¨a kahdella eri tavalla kahden luonnollisen luvun kuutioiden summana. (totta vai ei?) √ (f) 1 + 3 − 2 (ei ole v¨aitelause, ei v¨ait¨a mit¨a¨an.)

14

(g) T¨am¨a lause on ep¨atosi. (ei ole v¨aitelause, sill¨a sen totuusarvoa ei voida m¨a¨aritt¨a¨a)

Esimerkki 2.2.2. Tyypillisi¨a matemaattisia v¨aitelauseita: (a) Jos x ≤ 2, niin x2 ≤ 4. (b) Suorakulmaisen kolmion hypotenuusan pituuden neli¨o on yht¨asuuri kuin sen kateettien pituuksien neli¨oiden summa. (c) Olkoon f : [0, 1] → R jatkuva funktio siten, ett¨a f (0) = 0 ja f (1) = 2. T¨all¨oin on olemassa x ∈]0, 1[ siten, ett¨a f (x) = 1. Esimerkki 2.2.3. Goldbachin konjektuuri ”Jokainen lukua 2 suurempi parillinen luonnollinen luku on kahden alkuluvun summa“ on esimerkki matemaattisesta v¨aitelauseesta, joka selv¨astikin on joko tosi tai ep¨atosi, mutta toistaiseksi kukaan ei ole onnistunut saamaan selville kumpaa se on. Pienille parillisille luvuille vaaditut alkuluvut on suhteellisen helppo l¨oyt¨a¨a, esimerkiksi 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 40 = 3 + 37 ja 100 = 17 + 83. T¨am¨a ei kuitenkaan sulje pois mahdollisuutta, ett¨a l¨oytyisi jokin hyvin suuri parillinen luku, jolle vaadittuja alkulukuja ei l¨oytyisik¨a¨an. Huomautus 2.2.4. Matemaattista lausetta, joka riippuu jostakin muuttujasta, sanotaan avoimeksi lauseeksi. Esimerkiksi reaalilukuja koskeva lause ”x2 > 2x + 1”on avoin lause. Jos t¨ass¨a muuttujalle x annetaan jokin arvo, avoin lause muuttuu lauseeksi, jolla on jokin totuusarvo, joko tosi tai ep¨atosi. Avoin lause voi siis saada kumpiakin totuusarvoja, ts. voi olla olemassa arvo, jolle se on tosi, ja voi olla olemassa arvo, jolle se on ep¨atosi. T¨allainen on esimerkiksi edell¨a mainittu lause”x2 > 2x + 1”.

2.2.2

Loogisista konnektiiveista

V¨aitelauseista voidaan muodostaa uusia v¨aitelauseita loogisia konnektiiveja k¨aytt¨aen. Loogisia konnektiiveja ovat implikaatio ” =⇒ ”, ekvivalenssi ” ⇐⇒ ”, negaatio ”¬”, konjunktio ”∧”ja disjunktio ”∨”. Ne m¨a¨aritell¨a¨an totuustaulukoiden avulla, eli kertomalla kuinka muodostetun lauseen totuusarvo riippuu siin¨a esiintyvien v¨aitelauseiden totuusarvoista. Konjunktio ja disjunktio Loogiset konnektiivit konjunktio ”∧”ja disjunktio ”∨”vastaavat oleellisesti arkikielen ilmaisuja ”ja“ ja ”tai“.

15

P T T E E

Q E T E T

P ∧Q E T E E

P ∨Q T T E T

√ √ Esimerkki 2.2.5. (i) Olkoon P v¨aitelause ” 2 > 1“ ja Q v¨ √aitelause ”√ 2 ≤ 2“. N¨aiden lauseiden konjunktio P ∧ Q on v¨aitelause √ ” 2 > 1 ja 2 ≤ 2“, joka voidaan kirjoittaa lyhyesti muodossa ”1 < 2 ≤ 2“. √ √ Lauseiden P ja Q disjunktio P ∨Q on puolestaan ” 2 > 1 tai 2 ≤ 2“. (ii) V¨aitelauseiden x ∈ A ja x ∈ B konjunktio on x ∈ A ∩ B ja disjunktio x ∈ A ∪ B. Huomautus 2.2.6. Matemaatikon “tai” ei ole “joko-tai”. Sen vuoksi v¨aite “P tai Q” on totta, jos (i) P tosi, Q ep¨atosi (ii) P ep¨atosi, Q tosi (iii) P tosi, Q tosi √ √ Siten esimerkiksi v¨aitelause ” 2 > 1 tai 2 ≤ 2“ on totta. Negaatio V¨aitt¨am¨an P negaatiota eli v¨aitt¨am¨a¨a ”P on ep¨atosi“ merkit¨a¨an symbolilla ¬P . T¨am¨an konnektiivin totuustaulu on siis P T E

¬P E T

Esimerkki 2.2.7. V¨aitelauseita ja niiden negaatioita. Huomaa erityisesti miten v¨aitelauseiden osia toisiinsa sitovat “ja” ja “tai” k¨aytt¨aytyv¨at. √ (a) v¨aite: 2 ≥ 3. √ negaatio: 2 < 3. (b) v¨aite: 2 ≤ π ≤ 3 (eli 2 ≤ π ja π ≤ 3). negaatio: π < 2 tai π > 3. (c) v¨aite: luku 18971 on alkuluku tai

√

18971 > 138. √ negaatio: luku 18971 ei ole alkuluku ja 18971 ≤ 138. 16

(d) v¨aite: jos n ∈ N on mik¨a tahansa alkuluku, niin

√

n ei ole rationaaliluku. √ negaatio: on olemassa (ainakin yksi) alkuluku n, jolle n on rationaaliluku.

(e) v¨aite: on olemassa t¨asm¨alleen yksi luku x ∈ R siten, ett¨a x2 +4x−7 = 0. negaatio: yht¨al¨oll¨a x2 + 4x − 7 = 0 ei ole t¨asm¨alleen yht¨a (reaalista) ratkaisua, eli joko ratkaisuja ei ole yht¨aa¨n tai sitten niit¨a on ainakin 2. Implikaatio Matematiikassa vastaan tulevat v¨aitelauseet ovat varsin usein esitett¨aviss¨a muodossa Jos P, niin Q, (2.2.1) T¨am¨a vastaa implikaatio-konnektiivin “ =⇒ ” avulla muodostettua lausetta P =⇒ Q. T¨ass¨a P ja Q ovat kumpikin v¨aitelauseita, ja niist¨a k¨aytet¨a¨an t¨ass¨a yhteydess¨a seuraavia nimityksi¨a: P = oletus Q = v¨aite Jos v¨aitelause (2.2.1) on tosi, niin sanotaan, ett¨a lauseesta P seuraa Q, tai ett¨a P on riitt¨av¨a ehto lauseelle Q. Implikaation “ =⇒ ” totuustaulu on P T T E E

Q P =⇒ Q E E T T E T T T

V¨aitelause P =⇒ Q on siis ep¨atosi vain jos P on totta ja Q ep¨atosi. Esimerkki 2.2.8. Oletetaan, ett¨a kurssin luennoitsija antaa lupauksen “jos suoritat lopputentin hyv¨aksytysti, niin p¨a¨aset kurssista l¨api”. T¨all¨oin edellinen totuustaulu saa muodon tentti hyv¨aksytty kurssi l¨api tentti hyv¨aksytty =⇒ kurssi l¨api T E E T T T E E T E T T On ilmeist¨a, ett¨a luennoitsija pett¨a¨a antamansa lupauksen vain jos opiskelija suorittaa lopputentin hyv¨aksytysti, mutta ei silti p¨a¨ase kurssista l¨api. Esimerkki 2.2.9. Esimerkkej¨a implikaation avulla muodostetuista v¨aitelauseista. 17

(a) Jos x on rationaaliluku ja y on rationaaliluku, niin my¨os x + y on rationaaliluku. T¨ass¨a v¨aitelauseen oletus on “x on rationaaliluku ja y on rationaaliluku” ja v¨aite “x + y on rationaaliluku”. (b) Jos f : R → R on derivoituva, niin f on jatkuva funktio. T¨all¨a kertaa oletus muodostuu tiedosta “f : R → R on derivoituva” ja v¨aite on “f on jatkuva funktio”. (c) Goldbachin konjektuuri ”Jokainen lukua 2 suurempi parillinen luonnollinen luku on kahden alkuluvun summa“ voidaan my¨os muotoilla implikaation avulla: Jos n ∈ N on parillinen ja n > 2, niin on olemassa alkuluvut k ja l siten, ett¨a n = k + l. Implikaation totuustaulukon perusteella v¨aitelauseen P =⇒ Q negaatio (eli v¨aitelause ”P =⇒ Q on ep¨atosi“) on totta ainoastaan tapauksessa P on totta ja Q ep¨atosi. Totuustaulukoita tarkastelemalla havaitaan, ett¨a “P ja ¬Q” on totta t¨asm¨alleen silloin kun “P =⇒ Q” on ep¨atosi: P T T E E

Q P ja ¬Q P =⇒ Q E T E T E T E E T T E T

N¨ain ollen siis “¬(P =⇒ Q)” on “P ja ¬Q”. Esimerkki 2.2.10. Muotoa P =⇒ Q olevia v¨aitelauseita ja niiden negaatioita. (a) v¨aite: Jos f on derivoituva, niin f on jatkuva. (ts. mik¨a tahansa derivoituva funktio on my¨os jatkuva) negaatio: on olemassa (ainakin yksi) derivoituva funktio f , joka ei ole jatkuva. (b) v¨aite: Jos b2 − 4ac > 0, niin toisen asteen yht¨al¨oll¨a ax2 + bx + c = 0 on kaksi eri (reaalista) ratkaisua. negaatio: b2 − 4ac > 0, mutta yht¨al¨oll¨a ax2 + bx + c = 0 ei ole kahta eri ratkaisua (ratkaisuja on yksi tai ei yht¨a¨an). (c) v¨aite: jos n ∈ N on pariton, niin my¨os n3 on pariton. (ts. mink¨a tahansa parittoman luvun kolmas potenssi on my¨os pariton) negaatio: on olemassa pariton luku n ∈ N siten, ett¨a n3 ei ole pariton. 18

Huomautus 2.2.11. Implikaatio “ =⇒ ” ei ole symmetrinen, eli “P =⇒ Q” ei ole sama asia kuin“Q =⇒ P ”. On esimerkiksi totta, ett¨a “jos n on jaollinen luvulla 4, niin n on parillinen”, kun taas v¨aitelause “jos n on parillinen, niin n on jaollinen luvulla 4” on ep¨atosi (n = 6 kelpaa vastaesimerkiksi). Ekvivalenssi V¨aitelauseet P ja Q ovat ekvivalentit, merkit¨a¨an P ⇐⇒ Q, jos P =⇒ Q ja Q =⇒ P . Ekvivalenssin totuustaulu on P T T E E

Q P ⇐⇒ Q E E T T E T T E

N¨ain ollen P ⇐⇒ Q on totta, jos P ja Q ovat molemmat tosia tai molemmat ep¨atosia. Muissa tapauksissa lause P ⇐⇒ Q on ep¨atosi. V¨aitelause P ⇐⇒ Q luetaan “P jos ja vain jos Q” tai “P t¨asm¨alleen kun Q”. Esimerkki 2.2.12. (i) Positiiviselle reaaliluvulle x p¨atee x > 1 jos ja vain jos log( x1 ) < 0, ts. x > 1 ⇐⇒ log( x1 ) < 0. (ii) x ∈ A jos ja vain jos {x} ⊂ A.

2.2.3

Kvanttoreista

Hyv¨alt¨a matemaattiselta tulokselta vaaditaan p¨a¨as¨a¨ant¨oisesti tietty¨a yleisyytt¨a, jotta se olisi k¨aytt¨okelpoinen. Esimerkiksi se, ett¨a jokainen derivoituva funktio on jatkuva on hy¨odyllinen tulos juuri sen takia, ett¨a se p¨atee jokaiselle derivoituvalle funktiolle, ilman mit¨a¨an lis¨aoletuksia. Itse asiassa suuri osa matemaattisista tuloksista on muotoa “kaikilla ... p¨atee ...”. Symbolia ∀ kutsutaan universaalikvanttoriksi tai kaikki-kvanttoriksi, ja se vastaa arkikielen ilmaisua “kaikilla” tai “jokaisella”. Esimerkki 2.2.13. V¨aitelause ”Jokaiselle luonnolliselle luvulle n luku 2n on parillinen” voidaan kirjoittaa universaalikvanttorin avulla muodossa ∀ n ∈ N : 2n on parillinen. Toinen usein vastaan tuleva kvanttori on olemassolo- eli eksistenssikvanttori ∃.

19

Esimerkki 2.2.14. V¨aitelause “On olemassa rationaaliluku x, jonka neli¨o on 3” voidaan kirjoittaa my¨os muodossa ∃ x ∈ Q : x2 = 3. Joissakin v¨aitelauseissa kvanttoreita esiintyy useita kappaleita. Silloin niiden keskin¨aiseen j¨arjestykseen tulee kiinnitt¨a¨a erityist¨a huomiota: Esimerkki 2.2.15. Tarkastellaan v¨aitelausetta √ “Jokaiselle a ∈ N on olemassa b ∈ N siten, ett¨a a 6= b ja ab ∈ N”, joka kvanttoreita k¨aytt¨aen voidaan kirjoittaa muotoon √ ∀ a ∈ N ∃ b ∈ N : a 6= b ja ab ∈ N. T¨am¨a v¨aitelause on totta: mille tahansa a ∈ N voidaan etsityksi luvuksi b ottaa 4a. Jos vaihdetaan kvanttoreiden √ keskin¨aist¨a j¨arjestyst¨a, saadaan v¨aitelause ∃ b ∈ N ∀ a ∈ N : a 6= b ja ab ∈ N, eli √ “On olemassa luku b ∈ N siten, ett¨a kaikille a ∈ N on voimassa a 6= b ja ab ∈ N.” T¨am¨a v¨aitelause on ep¨atosi: Mik¨a¨an b ∈ N ei toteuta ehtoja, sill¨a jos otetaan a = b, niin ei ole totta, ett¨a a 6= b. Jos on ilmeist¨a, ett¨a v¨aitelause koskettaa kaikkia tietyn joukon alkioita, saatetaan sana “kaikille” tai “jokaiselle” j¨att¨a¨a pois. Esimerkiksi v¨aitelause ”Jokaiselle luonnolliselle luvulle n luku 2n on parillinen” voidaan esitt¨a¨a muodossa “Jos n on luonnollinen luku, niin 2n on parillinen.” Vastaavasti voidaan todeta, ett¨a “Jos f on derivoituva, niin se on my¨os jatkuva”. T¨am¨a on hyv¨a pit¨a¨a mieless¨a muodostettaessa v¨aitelauseiden negaatioita. Esimerkki 2.2.16. (i) V¨aitelauseen “Jos n on luonnollinen luku, niin 2n on parillinen” negaatio on “On olemassa luonnollinen luku n, jolle 2n ei ole parillinen”. √ n ∈ N” negaatio on (ii) V¨aitelauseen “On olemassa n ∈ N siten, ett¨ a √ “Kaikille luonnollisille luvuille n ∈ N p¨atee n 6∈ N”. (iii) V¨aitelauseen “Jokaiselle reaaliluvulle x > 0 on olemassa n ∈ N siten, ett¨a n1 < x” negaatio on “on olemassa reaaliluku x > 0 siten, ett¨a kaikille n ∈ N p¨atee n1 ≥ x”. Kvanttoreita ∀ ja ∃ k¨aytet¨a¨an tiivist¨am¨a¨an tai selkeytt¨am¨a¨an matemaattista ilmaisua esimerkiksi liitutaulua k¨aytett¨aess¨a. Sen sijaan kirjoitetussa matemaattisessa tekstiss¨a niit¨a pyrit¨a¨an v¨altt¨am¨a¨an. 20

Harjoitusteht¨ avi¨ a 1. Tapaat rehtien ja retkujen saarella saaren asukkaan A, joka sanoo: “Kaikki saaren asukkaat ovat retkuja.” (a) Puhuuko A totta vai ei? (b) Ovatko kaikki saaren asukkaat retkuja? 2. Tutkimusmatkailija tapasi kolme rehtien ja retkujen saaren asukasta maleksimasta. H¨an meni henkil¨on A luo, jolloin A sanoi: ”Nuo kaksi muuta, B ja C, ovat samaa tyyppi¨a.”(siis molemmat joko rehtej¨a tai retkuja.) T¨am¨an j¨alkeen tutkimusmatkailija meni henkil¨on C luokse ja kysyi t¨alt¨a: ”Ovatko A ja B samaa tyyppi¨a?” Mit¨a C vastasi? Perustele. 3. Olkoon a ∈ R luku, jolla on seuraavat ominaisuudet: • ∃ n ∈ N : n < a. • ∀ n ∈ N : n2 6= a. • ∀ x ∈ R : (x > a ⇒ x > 10). Mitk¨a seuraavista lukua a koskevista v¨aitteist¨a ovat t¨am¨an perusteella totta? (a) a 6= 4 ja a 6= 81. (b) a > 0. (c) a ≥ 2. (d) a ∈ / N. (e) a ≤ 10. 4. Muodosta seuraavien v¨aitelauseiden negaatiot. Mitk¨a v¨aitelauseista ovat totta ja mitk¨a eiv¨at? (a) on olemassa a ∈ N siten, ett¨a (b) kaikilla a ∈ N p¨atee

a 2

a 2

∈ N.

∈ N.

2

(c) jos x ∈ R, niin x > x. (d) kaikilla x ∈ R on olemassa n ∈ N siten, ett¨a |x − n| < 12 . (e) kaikilla n ∈ N on olemassa luvut m ∈ N ja k ∈ N siten, ett¨a nm = 2k. (f) jos x, y ∈ Z ja x < y, niin on olemassa z ∈ Z siten, ett¨a x < z < y. 21

2.3

Todistamisesta “’Obvious’ is the most dangerous word in mathematics.” E. T. Bell

2.3.1

Suora todistus

Tarkastellaan seuraavaa v¨aitelausetta: Jos luonnollinen luku n on pariton, niin my¨os n2 on pariton.

(2.3.1)

V¨aitelause on muotoa P =⇒ Q, miss¨a P (oletus): n pariton. Q (v¨aite): n2 pariton. Onko v¨aitelause (2.3.1) tosi vai ep¨atosi? T¨am¨an selvitt¨aminen on mahdollista vain jos ensin sovitaan tarkasti, mit¨a v¨aitelauseessa esiintyv¨at k¨asitteet “luonnollinen luku” ja “pariton” tarkoittavat, eli m¨a¨aritell¨a¨an ko. k¨asitteet. M¨ a¨ aritelm¨ a 2.3.1. Luonnollisten lukujen joukko N on joukko N = {1, 2, 3, 4, . . .}. Luonnollinen luku n on parillinen, jos n = 2l jollakin luonnollisella luvulla l ∈ N, ja pariton, jos n = 2k − 1 jollakin luonnollisella luvulla k ∈ N. Huomautus 2.3.2. Parittomuutta (tai parillisuutta) osoitettaessa on n¨aytett¨av¨a, ett¨a m¨a¨aritelm¨an ehto on voimassa. Nyt voidaan siis esimerkiksi todeta, ett¨a koska luku 7 on esitett¨aviss¨a muodossa 7 = 2 · 4 − 1, miss¨a 4 ∈ N, niin se on yll¨a asetetun m¨a¨aritelm¨an mukaan pariton. Huomautus 2.3.3. Vaikka yll¨a olevassa m¨a¨aritelm¨ass¨a lukeekin “Luonnollinen luku n on parillinen, jos n = 2l jollakin luonnollisella luvulla l ∈ N”, niin se tulee ymm¨art¨a¨a muodossa “Luonnollinen luku n on parillinen, jos ja vain jos n = 2l jollakin luonnollisella luvulla l ∈ N”. V¨aitelause (2.3.1) on totta, mille esit¨amme seuraavassa todistuksen. Todistus kertoo, miksi ja miten v¨aite “n2 pariton” seuraa oletuksesta “n pariton”. Se on loogisesti pit¨av¨a ja aukoton perustelu sille, ett¨a v¨aitelause on tosi. Todistus. Oletuksen mukaan n on pariton eli n = 2k − 1 jollakin k ∈ N. Haluamme osoittaa t¨ast¨a v¨altt¨am¨att¨a seuraavan, ett¨a n2 on pariton, eli ett¨a on olemassa jokin l ∈ N siten, ett¨a n2 = 2l − 1. T¨allainen l l¨oytyy laskemalla, oletusta apuna k¨aytt¨aen: n2 = (2k−1)2 = 4k 2 −4k+1 = (4k 2 −4k+2)−1 = 2(2k 2 −2k+1)−1 = 2l−1, 22

miss¨a l = 2k 2 − 2k + 1 = 2k(k − 1) + 1 on luonnollinen luku, sill¨a oletuksen mukaan k on luonnollinen luku. Siten luvulla n2 on parittomuuden m¨a¨aritelm¨ass¨a vaadittu ominaisuus, joten se on pariton. V¨aitelause on todistettu. 2 Todistuksessa k¨aytettiin siis seuraavaa p¨aa¨ttelyketjua: n pariton ⇒ n = 2k − 1 jollakin k ∈ N ⇒ n2 = (2k − 1)2 jollakin k ∈ N ⇒ n2 = 2(2k 2 − 2k + 1) − 1 ⇒ n2 = 2l − 1 er¨a¨all¨a l ∈ N ⇒ n2 on pariton. Todistuksessa edet¨a¨an vaiheittain oletuksista v¨aitteeseen, mist¨a johtuu nimitys suora todistus. P¨a¨attelyn jokainen vaihe on pystytt¨av¨a perustelemaan ja mahdollisen lukijan on voitava vakuuttautua todistuksen pit¨avyydest¨a. Esimerkiksi ensimm¨ainen vaihe (ensimm¨ainen ⇒-merkki) saadaan parittomuuden m¨a¨aritelm¨ast¨a, toinen ja kolmas vaihe ovat suoria laskuja ja niin edelleen. Todistuksen lopussa oleva 2 on yksinkertaisesti todistuksen loppumerkki, joka ilmaisee, ett¨a v¨aitelauseen todistava p¨a¨attely on saatu p¨a¨at¨okseen. Huomautus 2.3.4. Seuraava “perustelu” ei riit¨a todistukseksi. n 1 3 5 7 9 .. .

n2 1 9 25 49 81 .. .

33 .. .

1089 .. .

V¨aitelause n¨aytt¨aisi kyll¨a olevan totta, koska jokaisen yll¨a valitun parittoman luvun n neli¨o n2 on pariton. Mutta t¨am¨a ei viel¨a todista yht¨a¨an mit¨a¨an, sill¨a kaikkia mahdollisia parittomia lukuja ei ole k¨ayty (eik¨a voidakaan k¨ayd¨a) l¨api! V¨aitelauseessa vaaditaan nimenomaan, ett¨a mink¨a tahansa parittoman luvun neli¨o on pariton. Esimerkin v¨aitelause on kuitenkin “keksitty” t¨allaisten havaintojen perusteella. Laskettuaan useiden parittomien lukujen neli¨oit¨a ja todettuaan ne kaikki parittomiksi matemaatikko on p¨a¨att¨anyt selvitt¨a¨a onko ilmi¨o aina totta ja p¨a¨atynyt siten tutkimaan yo. v¨aitelauseen totuusarvoa. 23

Tavalla tai toisella merkitykselliset ja todeksi n¨aytett¨aviss¨a olevat v¨aitelauseet on matematiikassa tapana muotoilla teoreemoiksi eli lauseiksi. Aputuloksia, joita tarvitaan n¨aiden lauseiden todistamisessa, kutsutaan usein lemmoiksi tai propositioiksi. Seuraavassa muotoilemme ja todistamme yhden t¨allaisen aputuloksen. Lemma 2.3.5. Jos a, b ∈ R, niin (i) ab ≤ 12 (a2 + b2 ). (ii) (a + b)2 ≤ 2(a2 + b2 ). Todistus. (i) Koska (a − b)2 ≥ 0, niin a2 − 2ab + b2 ≥ 0. T¨ast¨a saadaan, ett¨a ab ≤ 1 2 (a + b2 ). 2 (ii) Kohdan (i) nojalla (a + b)2 = a2 + |{z} 2ab +b2 ≤ 2(a2 + b2 ). ≤ a2 + b2

2

2.3.2

Ep¨ asuora todistus

“Once you eliminate the impossible, whatever remains, no matter how improbable, must be the truth.” Sherlock Holmes Suora todistus eli suora p¨a¨attely on k¨aytetyin ja yleens¨a helpoin todistusmenetelm¨a. Joissakin tilanteissa on kuitenkin edullista k¨aytt¨a¨a toisenlaista ajattelua. Ep¨asuorassa todistuksessa oletetaan, ett¨a v¨aite ei pid¨ak¨a¨an paikkaansa ja osoitetaan, ett¨a t¨ast¨a seuraa tehdyt oletukset huomioiden mahdoton tilanne eli ristiriita. Niinp¨a v¨aitteen on pakko olla totta. T¨am¨ankaltaista p¨a¨attely¨a harrastettiin jo Rehtien ja Retkujen saarella. Esimerkki 2.3.6. Osoita, ett¨a jos n on parillinen, niin n ei ole pariton. Todistus. Haluamme siis osoittaa, ett¨a parillisella luvulla n ei ole parittomuuden m¨a¨aritelm¨ass¨a esitetty¨a ominaisuutta. On varsin luontevaa tehd¨a t¨am¨a toteamalla, ett¨a jos sill¨a olisi t¨am¨a ominaisuus, niin seuraisi mahdoton tilanne. Jos siis n olisi pariton, olisi olemassa jokin k ∈ N siten, ett¨a n = 2k − 1. Toisaalta oletuksen mukaan n on parillinen, joten n = 2l jollakin l ∈ N. Nyt 0 = n − n = (2l) − (2k − 1) = 2(l − k) + 1 24

eli

1 k−l = . 2 T¨am¨a on kuitenkin mahdotonta, sill¨a l ja k ovat luonnollisia lukuja ja siksi niiden erotus on kokonaisluku. Niinp¨a v¨aitteen “n ei ole pariton” on pakko olla totta. 2 Jotta parillisuuteen ja parittomuuteen liittyv¨at p¨a¨attelyt olisivat varmalla pohjalla, muotoillaan ja todistetaan n¨aihin k¨asitteisiin liittyv¨a ilmeisen tuntuinen tulos. Lause 2.3.7. Jokainen luonnollinen luku on joko parillinen tai pariton Todistus. Osoitetaan ensin, ett¨a mill¨aa¨n luonnollisella luvulla ei voi olla molempia ominaisuuksia. Tehd¨a¨an t¨am¨a ep¨asuoraa p¨a¨attely¨a k¨aytt¨aen, eli oletetaan (kuvitellaan), ett¨a olisi olemassa n ∈ N joka on sek¨a parillinen ett¨a pariton. Edellisess¨a esimerkiss¨a todistetun v¨aitteen perusteella luvun n parillisuudesta kuitenkin seuraa, ettei se voi olla pariton. Niinp¨a kuvitellun laista lukua ei voi olla olemassa, eli jokaisella luonnollisella luvulla on korkeintaan toinen ominaisuuksista “parillinen” ja “pariton”. Osoitetaan sitten, ett¨a jokainen luonnollinen luku on v¨altt¨am¨att¨a parillinen tai pariton. Pit¨a¨a siis osoittaa, ett¨a ei ole olemassa sellaista luonnollista lukua n, joka ei olisi parillinen eik¨a pariton. K¨aytet¨a¨an j¨alleen ep¨asuoraa p¨a¨attely¨a eli kuvitellaan, ett¨a t¨allaisia lukuja olisi olemassa (yksi tai useampia). Havaitaan, ett¨a 1 on pariton, sill¨a se voidaan esitt¨a¨a muodossa 1 = 2·1−1. Olkoon n0 pienin luonnollinen luku, joka ei ole parillinen eik¨a pariton. T¨all¨oin n0 ≥ 2 ja n0 − 1 on parillinen tai pariton (koska n0 oli pienin luku, joka ei ole parillinen eik¨a pariton). Jos n0 − 1 on parillinen, niin n0 − 1 = 2k jollakin k ∈ N. T¨all¨oin n0 = 2k+1 = 2(k+1)−1, miss¨a k+1 ∈ N, joten n0 on pariton. Jos taas n0 − 1 on pariton, on n0 − 1 = 2k − 1 jollakin k ∈ N. T¨all¨oin n0 = 2k, miss¨a k ∈ N eli n0 on parillinen. Oli siis n0 − 1 kumpi tahansa, parillinen tai pariton, on saatu ristiriita sen kanssa, ett¨a n0 ei olisi kumpaakaan. 2 Huomautus 2.3.8. Edellisen todistuksen loppuosa on esimerkki tapauskohtaisesta p¨aa¨ttelyst¨a: siin¨a sek¨a luvun n0 −1 parillisuuden ett¨a parittomuuden osoitettiin johtavan ristiriitaan tarkastelemalla n¨ait¨a kahta tapausta erikseen. Esimerkki 2.3.9. Tarkastellaan v¨aitelausetta “Jos n2 on pariton, niin n on pariton.” Yritet¨aa¨n ensin suoraa todistusta. Koska n2 on oletuksen mukaan pariton, on olemassa k ∈ N siten, ett¨a n2 = 2k − 1. Tavoitteena on n¨aytt¨a¨a, ett¨a t¨ast¨a

25

seuraa luvun n parittomuus, eli ett¨a on olemassa l ∈ N siten, ett¨a n = 2l − 1. Mutta miten luku l l¨oydet¨a¨an? n2 pariton ⇒ n2 = 2k − 1 jollakin k ∈ N √ ⇒ n = 2k − 1 jollakin k ∈ N ⇒???? T¨am¨a l¨ahestymistapa ei vaikuta kovin lupaavalta, joten kokeillaan ep¨asuoraa p¨a¨attely¨a. Todistus. K¨aytet¨a¨an ep¨asuoraa p¨a¨attely¨a eli tutkitaan, mit¨a tapahtuisi, jos v¨aite ei olisikaan totta. Tehd¨a¨an niin sanottu antiteesi (vastav¨aite, v¨aitteen negaatio): On olemassa n, jolle n2 on pariton, mutta n ei olekaan pariton. T¨all¨oin n on Lauseen 2.3.7 nojalla v¨altt¨am¨att¨a parillinen, joten on olemassa k ∈ N siten, ett¨a n = 2k. Siten n2 = (2k)2 = 4k 2 = 2(2k 2 ) = 2l, miss¨a l = 2k 2 ∈ N. Niinp¨a my¨os n2 on parillinen. Mutta t¨am¨a on mahdotonta, sill¨a oletimme, ett¨a n2 on pariton ja todistimme edell¨a, ettei parillinen luku voi olla pariton. Siten antiteesin on pakko olla ep¨atosi ja luvun n on siis oltava pariton. 2 Huomautuksia. Ep¨asuora p¨a¨attely on useissa tilanteissa hyvin n¨app¨ar¨a todistusmenetelm¨a, mutta sit¨a k¨aytett¨aess¨a on tiedett¨av¨a mit¨a on tekem¨ass¨a: (1) Ep¨asuorassa p¨a¨attelyss¨a on oltava tarkkana antiteesin muodostamisessa, eli on mietitt¨av¨a tarkkaan, mit¨a tarkoittaa se, ett¨a v¨aite ei olisikaan totta. (2) Ep¨asuorassa p¨a¨attelyss¨a ei ole etuk¨ateen selv¨a¨a mist¨a ja miten ristiriita l¨oydet¨a¨an. Huomautus 2.3.10. Edell¨a on todistettu v¨aitelauseet“n pariton ⇒ n2 pariton” ja “n2 pariton ⇒ n pariton.” Niinp¨a tied¨amme nyt, ett¨a n pariton ⇐⇒ n2 pariton Huomaa, ett¨a t¨ast¨a seuraa, ett¨a n parillinen ⇐⇒ n2 parillinen.

26

2.3.3

Todistamisen harjoittelua: jaollisuus

Jatkamme todistusmenetelmien harjoittelua k¨aytt¨aen apuna jaollisuuden k¨asitett¨a. T¨am¨an kappaleen asioita k¨asitell¨a¨an aikanaan tarkemmin lukuteorian kursseilla. M¨ a¨ aritelm¨ a 2.3.11. Olkoot n ja m luonnollisia lukuja. Sanotaan, ett¨a luku m on jaollinen luvulla n (tai n jakaa luvun m), merkit¨a¨an n|m, jos m = kn jollakin k ∈ N. T¨all¨oin n on luvun m tekij¨a. Luonnollinen luku m on alkuluku, jos m ≥ 2 ja jos m on jaollinen ainoastaan luvuilla 1 ja m. Esimerkki 2.3.12. Luku 10 on jaollinen kullakin luvuista 1, 2, 5 ja 10, sill¨a 10 = 1 · 10 = 2 · 5. Sen sijaan luvulla 5 ei ole muita tekij¨oit¨a kuin 1 ja 5, joten se on alkuluku. Huomaa, ett¨a m¨a¨aritelm¨amme mukaan 1 ei ole alkuluku. Lause 2.3.13. Luonnollinen luku n on jaollinen luvulla 6 jos ja vain jos ( ⇐⇒ ) n on jaollinen sek¨a luvulla 2 ett¨a luvulla 3. Todistus. Koska v¨aitelause koostuu itse asiassa kahdesta erillisest¨a v¨aitelauseesta, on syyt¨a kirjoittaa todistuskin kahdessa osassa: 1◦ n jaollinen luvulla 6 ⇒ n jaollinen luvulla 2 ja luvulla 3. Oletus: n jaollinen luvulla 6 eli n = 6k jollakin k ∈ N. V¨ aite: n jaollinen luvuilla 2 ja 3. K¨aytet¨aa¨n jaollisuuden m¨aa¨ritelm¨aa¨: n = 6k = 2(3k) = 2l, miss¨a l = 3k ∈ N ⇒ n on jaollinen luvulla 2. n = 6k = 3(2k) = 3m, miss¨a m = 2k ∈ N ⇒ n on jaollinen luvulla 3. Siten oletuksesta 6|n seuraa, ett¨a 2|n ja 3|n. 2◦ n jaollinen luvuilla 2 ja 3 ⇒ n jaollinen luvulla 6. Oletus: 2|n eli n = 2l jollakin l ∈ N ja 3|n eli n = 3m jollakin m ∈ N. V¨ aite: 6|n. Jos tiet¨aisimme, ett¨a luku m on parillinen, eli m = 2k jollekin k ∈ N, niin silloin saataisiin n = 3m = 3(2k) = 6k, mist¨a v¨aite seuraisi. V¨aitteen todistamiseksi riitt¨a¨a siis osoittaa, ett¨a m on parillinen. 27

Tehd¨aa¨n t¨am¨a ep¨asuoraa p¨a¨attely¨a k¨aytt¨aen. Jos m olisi pariton, eli l¨oytyisi p ∈ N siten, ett¨a m = 2p − 1, niin n = 3m = 3(2p − 1) = 6p − 3 = (6p − 2) − 1 = 2(3p − 1) − 1 = 2q − 1, miss¨a q = 3p − 1 ∈ N. Siten my¨os n olisi pariton. Kuitenkin oletuksen mukaan n = 2l jollakin l ∈ N , joten n on parillinen. T¨am¨a on ristiriita. Siten luvun m on pakko olla parillinen, ja siten olemme saaneet v¨aitteen todistettua. 1◦ ja 2◦ yhdess¨a todistavat v¨aitteen. 2 Lause 2.3.14. Alkulukuja on ¨a¨aret¨on m¨a¨ar¨a. Todistus. Tehd¨a¨an antiteesi: Alkulukuja on vain ¨a¨arellinen m¨a¨ar¨a, olkoon niit¨a k kappaletta ja olkoot kyseiset alkuluvut n1 , n2 , . . . , nk . Tarkastellaan lukua n = n1 n2 · · · nk + 1. (a) Jos n on alkuluku, niin on l¨oydetty uusi alkuluku, joka ei selv¨astik¨a¨an ole mik¨a¨an luvuista n1 , n2 , . . . , nk . Kuitenkin listassa n1 , n2 , . . . , nk piti olla jo kaikki alkuluvut, eli olemme p¨a¨atyneet ristiriitaan. (b) Jos n ei ole alkuluku, niin se voidaan esitt¨a¨a (j¨arjestyst¨a vaille yksik¨asitteisesti) alkulukujen tulona (Miksi?). Erityisesti ainakin yksi alkuluvuista n1 , n2 , . . . , nk jakaa luvun n. Olkoon nj er¨as t¨allainen luku. Mutta suoralla jakolaskulla n¨ahd¨a¨an, ett¨a n1 n2 · · · nk + 1 1 n = = n1 . . . nj−1 nj+1 . . . nk + , nj nj nj miss¨a nnj ∈ / N . Niinp¨a nj ei olekaan luvun n jakaja, ja j¨alleen p¨a¨adyt¨a¨an ristiriitaan. Siisp¨a antiteesi on v¨aa¨rin ja v¨aite totta. 2 Huomautus 2.3.15. Lauseen 2.3.14 todistuksessa on varsin luonnollista k¨aytt¨a¨a ep¨asuoraa p¨a¨attely¨a, sill¨a antiteesin mukaista ¨a¨arellist¨a lukujoukkoa on yleens¨a helpompi k¨asitell¨a kuin ¨a¨aret¨ont¨a joukkoa. Mieti mit¨a vaadittaisiin suoran todistuksen onnistumiseen.

28

2.3.4

Todistamisen harjoittelua: rationaali- ja irrationaaliluvuista

T¨all¨a kurssilla reaalilukuja ajatellaan yksinkertaisesti lukusuoran pistein¨a eik¨a niit¨a m¨a¨aritell¨a sen tarkemmin. Syv¨allisemmin t¨ah¨an ep¨atriviaaliin asiaan tutustutaan my¨ohemmill¨a kursseilla. M¨ a¨ aritelm¨ a 2.3.16. Reaaliluku x on rationaaliluku, jos on olemassa kokonaisluvut n ja m siten, ett¨a n 6= 0 ja x = m . Rationaalilukujen joukkoa n merkit¨a¨an symbolilla Q. Irrationaaliluku on reaaliluku, joka ei ole rationaaliluku. Esimerkki 2.3.17. Esimerkiksi luku 0.6 on rationaaliluku, sill¨a 0.6 = 35 . Seuraavassa esimerkki rationaalilukujen m¨a¨aritelm¨a¨an perustuvasta p¨a¨attelyst¨a: Esimerkki 2.3.18. Jos x ∈ Q ja y ∈ Q, niin x + y ∈ Q. Todistus. Oletuksen mukaan on olemassa kokonaisluvut m, n, k ja l siten, ja y = kl . Siten ett¨a n 6= 0, l 6= 0, x = m n x+y =

ml nk ml + nk m k + = + = , n l nl nl nl

miss¨a ml + nk ja nl ovat kokonaislukuja ja nl 6= 0. N¨ain ollen x + y ∈ Q. 2 Rationaalilukujen joukko Q on selv¨astikin ep¨atyhj¨a, sill¨a esimerkiksi kaikki kokonaisluvut ovat rationaalilukuja. Sen sijaan irrationaalilukujen l¨oyt¨aminen onkin hieman hankalampaa, vaikka todellisuudessa “melkein kaikki” reaaliluvut ovatkin irrationaalilukuja. √ Seuraavassa esit¨amme todistuksen sille, ett¨a 2, eli se positiivinen luku, jonka neli¨o on 2, on irrationaalinen. T¨allainen reaaliluku todella on olemassa, mutta sen todistamiseksi tarvitaan reaalilukujen joukon t¨aydellisyytt¨a, jota ei t¨all¨a kurssilla k¨asitell¨a. √ Lause 2.3.19. 2 on irrationaaliluku. √ Todistus. Koska on osoitettava, ett¨a luvulla 2 ei ole rationaaliluvut m¨a¨arittelev¨a¨a ominaisuutta, on luontevaa √ k¨aytt¨a¨a ep¨asuoraa todistusta: Antiteesi: V¨aite ei ole totta, eli 2 onkin rationaaliluku. On siis olemassa √ luonnolliset luvut (koska 2 > 0) n ja m siten, ett¨a √ m 2= . n

29

Voidaan olettaa, ett¨a osam¨a¨ar¨a¨a m ei voida supistaa, sill¨a jos voidaan, supisn tetaan niin kauan kuin voidaan, ja valitaan n¨ain saadut uudet luvut luvuiksi m ja n. Nyt  m 2 m2 √ = 2 2 = ( 2)2 = n n eli m2 = 2n2 . Siten m2 on parillinen ja Huomautuksen 2.3.10 nojalla my¨os m on parillinen, toisin sanoen m = 2k jollakin k ∈ N. N¨ain ollen 2n2 = m2 = (2k)2 = 4k 2 , mist¨a seuraa, ett¨a n2 = 2k 2 . Siten n2 on parillinen ja (j¨alleen Huomautuksen 2.3.10 nojalla) my¨os n on parillinen. nyt supistaa Koska sek¨a m ett¨a n ovat parillisia, voidaan osam¨a¨ar¨a¨a m n luvulla 2, mik¨a on ristiriita. 2

2.3.5

Tiheist¨ a joukoista

T¨ass¨a osiossa on tarkoitus osoittaa, ett¨a kahden kesken¨a¨an erisuuren reaaliluvun v¨aliss¨a on aina sek¨a rationaalilukuja ett¨a irrationaalilukuja (eli reaalilukuja, jotka eiv¨at ole rationaalilukuja). T¨alle ominaisuudelle annetaan nimi ”tiheys”, eli tulemme todistamaan, ett¨a rationaaliluvut Q ja irrationaaliluvut R \ Q ovat molemmat reaaliakselin tiheit¨a osajoukkoja. M¨ a¨ aritelm¨ a 2.3.20. Joukko A ⊂ R on tihe¨a, jos (ja vain jos) jokaiselle rajoitetulle avoimelle v¨alille ]a, b[ ( miss¨a a < b) p¨atee ]a, b[ ∩ A 6= ∅.

M¨aa¨ritelmill¨a on matematiikassa hyvin keskeinen rooli. On t¨arke¨a¨a ymm¨art¨a¨a, ett¨a jos haluamme osoittaa jonkin reaaliakselin osajoukon olevan tihe¨a, niin meid¨an on todistettava, ett¨a kyseisell¨a joukolla on yll¨a olevassa m¨a¨aritelm¨ass¨a mainittu ominaisuus. Samoin jos haluamme osoittaa, ett¨a jokin joukko ei ole tihe¨a, tulee n¨aytt¨a¨a, ett¨a yo. m¨a¨aritelm¨an ehto ei ole voimassa. Esimerkki 2.3.21. Kokonaislukujen joukko Z = {. . . , −2, −1, 0, 1, 2, . . .} ei ole tihe¨a. Todistus. Riitt¨a¨a l¨oyt¨a¨a yksikin v¨ali ]a, b[ , jolle ]a, b[ ∩ Z = ∅. Havaitaan, ett¨a ] 13 , 32 [ ∩ Z = ∅, joten Z ei ole tihe¨a. 2 30

Huomautus 2.3.22. Jos A ⊂ R on tihe¨a, niin jokaisella rajoitetulla avoimella v¨alill¨a ]a, b[ on itse asiassa ¨a¨arett¨om¨an monta joukon A alkiota. Se miten t¨am¨a seuraa tihe¨an joukon m¨a¨aritelm¨ast¨a, j¨a¨a lukijalle harjoitusteht¨av¨aksi. Lause 2.3.23. Joukot Q ja R \ Q ovat tiheit¨a. Todistus. Todistetaan ensin, ett¨a Q on tihe¨a: Olkoon ]a, b[ mik¨a tahansa 1 1 avoin v¨ali. Koska b > a eli b − a > 0, niin b−a > 0. T¨all¨oin luku b−a > 0 sijaitsee lukusuoralla kahden per¨akk¨aisen luonnollisen luvun v¨aliss¨a: on 1 ≤ n. Osoitetaan seuraavaksi, ett¨a olemassa n ∈ N siten, ett¨a n − 1 < b−a

k etsitty rationaaliluku a < q < b l¨oytyy muodossa q = n+1 jollakin k ∈ Z. Nimitt¨ain, jos t¨ a llaista kokonaislukua k ei l¨ o ytyisi, niin olisi olemassa m ∈ Z,  m−1 m  m−1 1 1 m jolle a, b ∈ n+1 , n+1 . T¨all¨oin b − a ≤ n+1 − n+1 = n+1 eli b−a ≥ n + 1.

1 T¨am¨a on kuitenkin mahdotonta, sill¨a b−a ≤ n. Siisp¨a on olemassa k ∈ Z k siten, ett¨a n+1 ∈ ]a, b[ eli erityisesti ]a, b[ ∩ Q 6= ∅. Joukon R\Q osoittaminen tihe¨aksi j¨a¨a lukijalle harjoitusteht¨av¨aksi. (Vih√ je: hy¨odynn¨a tietoa 2 + q ∈ R \ Q kaikille q ∈ Q.) 2

2.3.6

Konstruktiivinen vs. ei-konstruktiivinen

Muotoa “on olemassa ..., jolle p¨atee ...” olevien v¨aitelauseiden todistukset voidaan jakaa kahteen kategoriaan: konstruktiivisiin ja ei-konstruktiivisiin. Ensimm¨aiseen ryhm¨a¨an kuuluvat p¨a¨attelyt, joissa annetaan konkreeettinen esimerkki halutut ominaisuudet toteuttavasta objektista. J¨alkimm¨aisen kategorian p¨a¨attelyiss¨a taas osoitetaan pelk¨ast¨a¨an etsityn objektin olemassaolo ilman, ett¨a selvi¨aa¨ mik¨a kyseinen objekti on. Esimerkki 2.3.24. Osoita, ett¨a yht¨al¨oll¨a x4 − 5x2 + 6 = 0 on ainakin yksi ratkaisu. Annetaan v¨aitteelle ensin konstruktiivinen todistus: √ √ √ Todistus. Koska ( 2)4 − 5( 2)2 + 6 = 4 − 5 · 2 + 6 = 0, on 2 yht¨al¨on er¨as ratkaisu. Niinp¨a ratkaisuja on ainakin yksi. 2 31

Sitten ei-konstruktiivinen: q Todistus. Merkit¨aa¨n f (x) = x4 − 5x2 + 6. Koska f (0) = 6 > 0, f ( 52 ) = − 41 < 0 ja f on polynomifunktiona jatkuva, niin Bolzanon lauseen nojalla on q olemassa x ∈ ]0, 52 [ siten, ett¨a f (x) = 0. Niinp¨a yht¨al¨oll¨a x4 − 5x2 + 6 = 0 on ainakin yksi ratkaisu. 2 Lemma 2.3.25. On olemassa irrationaaliluvut x ja y siten, ett¨a xy on rationaaliluku. √ √ √ √2 Todistus. Tarkastellaan lukuja√ 2 ja 2. N¨aist¨a 2 tiedet¨a¨an irratio√ 2 naaliluvuksi, mutta luvusta 2 emme tied¨a, onko se rationaali- vai irrationaaliluku. √ √2 √ • Jos 2 on rationaaliluku, voimme valita x = y = 2 ja v¨aite on saatu perusteltua. √ √2 √ √ √2 • Jos taas 2 on irrationaaliluku, valitaan x = 2 ja y = 2, jolloin y

x =

 √

√

2

2

√2 =

√

√ √ 2 2

2

=

√

2

2 =2

on rationaaliluku, ja taaskin v¨aitettyjen lukujen olemassaolo on n¨aytetty. 2 Edellinen todistus on klassinen esimerkki ei-konstruktiivisesta olemassaolotodistuksesta: lukujen x ja y olemassaolo todistetaan ilman, ett¨a selvi¨a¨a mit¨a n¨am¨a luvut ovat. Seuraavassa annamme samalle v¨aitteelle konstruktiivisen todistuksen. √ Todistus. Valitaan x = 2 ja y = log2 9, jolloin x on tunnetusti irrationaaliluku ja √ log2 9 √ log2 32 √ 2 log2 3 √ 2 log2 3 xy = 2 2 = 2 = 2 = = 2log2 3 = 3 rationaaliluku. V¨aitteen todistamiseksi riitt¨a¨a siis osoittaa, ett¨a y = log2 9 on irrationaaliluku. Tehd¨a¨an t¨am¨a ep¨asuoraa p¨a¨attely¨a k¨aytt¨aen: Antiteesi: log2 9 on rationaaliluku, eli on olemassa kokonaisluvut n, m ∈ Z, n m 6= 0, siten, ett¨a log2 9 = m . Huomataan ensin, ett¨a koska log2 9 > 0, voidaan olettaa, ett¨a n, m ∈ N. Koska log2 on funktion x 7→ 2x k¨a¨anteisfunktio, on 2z = w ⇐⇒ z = log2 w. 32

Niinp¨a yht¨asuuruus log2 9 =

n m

n

tarkoittaa, ett¨a 2 m = 9, josta saadaan 2n = 9m .

Luku 2n on parillinen, kun taas 9m on pariton (sill¨a se on parittoman luvun tulo itsens¨a kanssa m kertaa). Antiteesi on siis johtanut ristiriitaan, joten sen on oltava ep¨atosi. Niinp¨a log2 9 on irrationaaliluku. 2

2.3.7

Suora vai ep¨ asuora p¨ a¨ attely?

Monia v¨aitelauseita on mahdollista todistaa sek¨a suoraa ett¨a ep¨asuoraa p¨a¨attely¨a k¨aytt¨aen: Esimerkki 2.3.26. Todistetaan v¨aitelause Jos reaaliluvulle x on x2 − 3x + 2 < 0, niin x > 0 k¨aytt¨aen sek¨a suoraa ett¨a ep¨asuoraa p¨a¨attely¨a. T¨ass¨a siis Oletus: x ∈ R ja x2 − 3x + 2 < 0 V¨aite: x > 0 Todistus. 1. tapa (suora p¨a¨attely): Koska x2 − 3x + 2 < 0, niin 3x > x2 + 2. Siten 1 1 2 1 x = (3x) > (x2 + 2) ≥ (0 + 2) = > 0, 3 3 3 3 joten v¨aite on totta. 2. tapa (ep¨asuora p¨a¨attely): Tehd¨a¨an antiteesi: v¨aite onkin ep¨atosi ja on x ≤ 0. T¨all¨oin −3x ≥ 0, joten x2 − 3x + 2 ≥ 0, sill¨a kaikki termit ovat ≥ 0. T¨am¨a on kuitenkin ristiriidassa oletuksen kanssa, joten antiteesin on oltava ep¨atosi. Siis v¨aite on totta. 2 Esimerkki 2.3.27. Tarkastellaan v¨aitelausetta √ “Jos a ja b ovat positiivisia reaalilukuja, niin ab ≤ a+b .” 2 Todistetaan t¨am¨a ep¨ayht¨al¨o harjoituksen vuoksi kahdella eri tavalla. Tapa 1: (Ep¨asuora todistus) √ Antiteesi: on olemassa reaaliluvut a, b > 0 siten, ett¨a ab > a+b . 2 √ a+b T¨all¨oin, koska ab ≥ 0 ja 2 ≥ 0, on √ 2  a + b 2 a2 + 2ab + b2 ab = ab > = . 2 4 Edell¨a ep¨ayht¨al¨o > saatiin antiteesist¨a. Nyt edellisest¨a seuraa 4ab > a2 + 2ab + b2 eli a2 − 2ab + b2 < 0. 33

T¨am¨a on ristiriita, sill¨a a2 − 2ab + b2 = (a − b)2 ≥ 0. Tapa 2: (Suora todistus)   a+b 1 √
2 √ 2 = a + b 2 2   √ 2 √ √ 1 √
2 = a − 2 ab + b + 2 ab 2   √ 2 √ 1 √ = a − b + 2 ab 2 √ 1 √ ≥ · 2 ab = ab. 2 Viimeisen rivin ep¨ayht¨al¨o saadaan yksinkertaisesti j¨att¨am¨all¨a neli¨otermi summauksesta pois. Joissakin tilanteissa suoraa ja ep¨asuoraa p¨aa¨ttely¨a kannattaa yhdistell¨a: Esimerkki 2.3.28. Jokainen nollasta eroava rationaaliluku voidaan esitt¨a¨a kahden irrationaaliluvun tulona, ts. jokaiselle x ∈ Q, x 6= 0, on olemassa luvut y, z ∈ R \ Q siten, ett¨a x = yz. Miten t¨at¨a v¨aitelausetta kannattaa l¨ahesty¨a? Olemme t¨ah¨an menness¨a √ todistaneet luvun 2 irrationaalisuuden, joten t¨at¨a tietoa kannattanee hy¨o√ x dynt¨a¨a. Koska voimme esitt¨a¨a rationaaliluvun x aina muodossa x = 2 √ , 2 riitt¨a¨akin siis todistaa, ett¨a √x2 on irrationaaliluku. Todistus. Olkoon x mik¨a tahansa nollasta eroava rationaaliluku. Osoitetaan, ett¨a t¨all¨oin √x2 on irrationaaliluku. Tehd¨a¨an t¨am¨a ep¨asuoraa p¨a¨attely¨a k¨aytt¨aen: Antiteesi: √x2 on rationaaliluku. , eli T¨all¨oin on olemassa m, n ∈ Z siten, ett¨a n 6= 0 ja √x2 = m n √ n 2=x ; m huomaa, ett¨a my¨os m 6= 0, sill¨a √x2 6= 0 oletuksen x 6= 0 nojalla. Koska oletuksen mukaan x on rationaaliluku ja x 6= 0, niin on olemassa k, l ∈ Z, k, l 6= 0 siten, ett¨a x = kl . Mutta t¨all¨oin √

2=x

n kn kn = = , m lm lm 34

√ mist¨a seuraisi, ett¨a 2 on rationaaliluku. T¨am¨an ristiriidan nojalla antiteesin t¨aytyy olla ep¨atosi ja siten luvun √x2 on oltava irrationaaliluku. N¨ain ollen luku x on saatu esitetty¨a kahden irrationaaliluvun tulona muo√ x dossa x = 2 √ . 2 2 P¨a¨attelyn suunnan suhteen on oltava tarkkana, oli kyseess¨a sitten suora tai ep¨asuora p¨aa¨ttely. Esimerkki 2.3.29. √ on er¨aa¨n oppilaan ratkaisu seuraavaan teht¨av¨aa¨n: √ Alla Ratkaise yht¨al¨o x +√ x −√a = 2, miss¨a a on positiivinen parametri. Ratkaisu: Jos kerran x + x − a = 2, niin √ √ √ √ √ √ ( x − x − a)( x + x − a) a a √ √ x− x−a= =√ = . √ 2 x+ x−a x+ x−a √ √ √ √ Laskemalla yht¨ a l¨ o t x + x − a = 2 ja x − x − a = a2 yhteen saadaan √ 2 x = 2 + a2 , josta x = (1 + a4 )2 . Kuitenkin jos a = 8, niin yll¨a oleva kaava antaa ratkaisuksi x = (1+ 48 )2 = √ √ 9, joka ei toteuta yht¨al¨o¨a x + x − 8 = 2. Mik¨a siis meni pieleen?

Harjoitusteht¨ avi¨ a 1. Todista seuraavat v¨aitteet: a) Jos n ∈ N on parillinen ja m ∈ N on parillinen, niin m + n on parillinen. b) Jos n ∈ N on pariton ja m ∈ N on pariton, niin m+n on parillinen. c) Jos n ∈ N on pariton ja m ∈ N on parillinen, niin m+n on pariton. 2. Olkoon x, y ∈ R. (a) Osoita, ett¨a jos x + y ≥ 1, niin x ≥

1 2

tai y ≥ 12 .

(b) Jos xy ≥ 1, niin onko totta, ett¨a x ≥ 1 tai y ≥ 1? 3. Olkoot a, b ja c luonnollisia lukuja siten, ett¨a luvut b ja b2 + c ovat jaollisia luvulla a. Osoita, ett¨a t¨all¨oin my¨os c on jaollinen luvulla a. 4. Olkoot a, b ja c ei-negatiivisia reaalilukuja (ts. a, b, c ≥ 0). Osoita, ett¨a (a) a2 + b2 + c2 ≥ ab + bc + ac. (b) 8abc ≤ (a + b)(b + c)(c + a). 35

5. Olkoot n, m, k ∈ N. Osoita, ett¨a (a) jos n|m ja n|k, niin n|(m + k). (b) jos n|m, niin n2 |m2 . 6. Osoita, ett¨a (a) jos p, q ∈ Q, niin pq ∈ Q. (b) jos x on irrationaaliluku ja p ∈ Q, niin x + p on irrationaaliluku. 7. Anna tarkasti perustellen esimerkki (a) irrationaaliluvuista x ja y siten, ett¨a x + y ∈ / Q. (b) irrationaaliluvuista x ja y siten, ett¨a x + y ∈ Q. (c) irrationaaliluvuista x ja y siten, ett¨a xy ∈ Q. (d) irrationaaliluvuista x ja y siten, ett¨a xy ∈ / Q. 8. Olkoon n ∈ N. Todista, ett¨a n on jaollinen luvulla 3 ⇐⇒ n2 on jaollinen luvulla 3. 9. Osoita, ett¨a

√

3 on irrationaaliluku.

10. Olkoot n, m, k ∈ N. Osoita, ett¨a jos n2 + m2 = k 2 , niin n on parillinen tai m on parillinen. 11. Osoita, ett¨a (a) jos joukossa A ⊂ R on vain ¨a¨arellisen monta eri pistett¨a, niin se ei voi olla tihe¨a. (b) jos A ⊂ R on tihe¨a ja a ∈ A, niin my¨os A \ {a} on tihe¨a. 12. Olkoon x ∈ R. Todista v¨aitelause “jos x3 + x > 0, niin x > 0” k¨aytt¨aen (a) suoraa todistusta. (b) ep¨asuoraa todistusta.

36

13. Olkoon x ∈ R. Todista v¨aitelause ”jos x > 0, niin x +

4 x

≥ 4” k¨aytt¨aen

(a) suoraa todistusta. (b) ep¨asuoraa todistusta. 14. Olkoon x ∈ Q, x > 0. Osoita, ett¨a v¨alill¨a ]0, x[ on ¨a¨arett¨om¨an monta rationaalilukua k¨aytt¨aen (a) suoraa todistusta. (b) ep¨asuoraa todistusta.

2.3.8

Induktiotodistus

“If we have no idea why a statement is true, we can still prove it by induction.” Gian-Carlo Rota Induktio on k¨atev¨a, ja joskus ainoa mahdollinen tapa todistaa luonnollisia lukuja koskevia v¨aitteit¨a, jotka ovat muotoa Kaikille n = 1, 2, 3, . . . p¨atee P (n). Induktioperiaatteen matemaattinen muotoilu on seuraava: Olkoon A ⊂ N ep¨atyhj¨a. Jos 1◦ 1 ∈ A 2◦ ehdosta n ∈ A seuraa aina, ett¨a n + 1 ∈ A niin A = N. Induktioperiaatteen k¨aytt¨o: Jos halutaan osoittaa, ett¨a jokin v¨aite on totta kaikilla n ∈ N, niin riitt¨a¨a 1◦ todistaa v¨aite tapauksessa n = 1 2◦ todistaa induktioaskel: Osoitetaan, ett¨a jos v¨aite on totta jollakin n = k, niin t¨all¨oin v¨aite on totta my¨os, kun n = k + 1. Er¨as tapa havainnollistaa induktiota on niin kutsuttu dominonappulamalli. Kuvittele ¨a¨arett¨om¨an pitk¨a¨a (!) jonoa dominonappuloita, jotka on aseteltu pystyyn per¨akk¨ain. Koko jonon pit¨aisi kaatua, kun ensimm¨ainen nappula kaadetaan. T¨am¨ah¨an tapahtuu niin, ett¨a tarkastetaan ett¨a ensimm¨ainen nappula todella kaatuu (vrt 1◦ ) ja varmistetaan, ett¨a kukin nappula kaatuessaan kaataa my¨os sit¨a seuraavan (2◦ ). Jos kumpi tahansa vaihe ep¨aonnistuu, koko jono ei kaadu, vaan jotkin dominonappulat j¨a¨av¨at pystyyn. 37

Induktion ei v¨altt¨am¨att¨a tarvitse alkaa luvusta n = 1. Yleisemm¨ass¨a muodossaan sen avulla voidaan todistaa muotoa kaikille n = n0 , n0 + 1, n0 + 2, . . . p¨atee P (n), miss¨a n0 ∈ Z, olevia v¨aitteit¨a. T¨all¨oinkin todistuksessa on kaksi vaihetta: Ensin osoitetaan, ett¨a v¨aite p¨atee arvolla n = n0 , ja sitten n¨aytet¨a¨an, ett¨a jos P (k) on tosi ja k ≥ n0 , niin P (k + 1) on tosi. Esimerkki 2.3.30. Osoita, ett¨a kaikille n = 1, 2, . . . on voimassa 1 1 1 n + + ··· + = . 1·2 2·3 n(n + 1) n+1 Todistus. 1◦ Tarkistetaan ensin, ett¨a v¨aitt¨am¨amme yht¨asuuruus on voimassa tapauksessa n = 1: 1 1 vasen puoli: = . 1·2 2 1 1 = . oikea puoli: 1+1 2 Niinp¨a v¨aite on tosi, kun n = 1. 2◦ Seuraavaksi on n¨aytett¨av¨a, ett¨a jos v¨aite on totta jollakin arvolla n = k, k ≥ 1, niin se on totta my¨os seuraavalla arvolla k + 1. T¨at¨a vaihetta todistuksessa kutsutaan joskus induktioaskeleeksi, ja sit¨a varten tehd¨a¨an ns. induktio-oletus ja induktiov¨aite. Induktio-oletus: 1 1 1 k + + ··· + = . 1·2 2·3 k(k + 1) k+1 Induktiov¨ aite: 1 1 1 1 k+1 + + ··· + + = . 1·2 2·3 k(k + 1) (k + 1)(k + 2) k+2 Todistus: Induktio-oletusta k¨aytt¨am¨all¨a saadaan 1 1 1 1 + + ··· + + 1·2 2·3 k(k + 1) (k + 1)(k + 2) k 1 = + k + 1 (k + 1)(k + 2) k(k + 2) + 1 = (k + 1)(k + 2) k 2 + 2k + 1 (k + 1)2 k+1 = = = , (k + 1)(k + 2) (k + 1)(k + 2) k+2 eli induktiov¨aite on voimassa. 38

Induktioperiaatteen nojalla v¨aite on nyt tosi kaikille n = 1, 2, 3, . . .. 2 Seuraavaksi tarkastellaan geometrisen sarjan osasummia ja todistetaan induktiolla taulukkokirjasta tuttu kaava. T¨at¨a varten olkoon b reaaliluku siten, ett¨a b 6= 0 ja b 6= 1, ja m¨a¨aritell¨a¨an n X Sn = bj = 1 + b + b2 + · · · + bn . j=0

Lause 2.3.31. Jos b 6= 0 ja b 6= 1, niin bn+1 − 1 Sn = , kun n = 0, 1, 2, . . . . b−1 Todistus. Induktio n:n suhteen alkaen luvusta n = 0: 1◦ : n = 0: vasen puoli: S0 =

0 X

bj = b0 = 1

j=0

oikea puoli:

b−1 =1 b−1

Siten v¨aite on tosi, kun n = 0. 2◦ : Induktioaskel: Osoitetaan, ett¨a jos v¨aite on totta kun n = k, on se v¨altt¨am¨att¨a totta my¨os kun n = k + 1. Luvusta k emme t¨ass¨a voi olettaa muuta kuin sen, ett¨a k ∈ N. Induktio-oletus:

bk+1 − 1 Sk = b−1

Induktiov¨ aite: Sk+1 =

bk+2 − 1 b−1

Todistus: Sk+1 =

k+1 X j=0

j

b =

k X

bj + bk+1 = Sk + bk+1 ,

j=0

josta induktio-oletuksen nojalla saadaan edelleen bk+1 − 1 bk+1 − 1 (b − 1)bk+1 + bk+1 = + b−1 b−1 b−1 bk+1 − 1 + bk+2 − bk+1 = b−1 k+2 b −1 = . b−1 Siten induktiov¨aite seuraa induktio-oletuksesta. Sk+1 =

39

Induktioperiaatteen nojalla v¨aite on nyt tosi kaikille n = 0, 1, 2, . . . 2 Seuraavaksi todistetaan induktiota k¨aytt¨aen Newtonin binomikaava. Ensin tarvitaan kuitenkin binomikertoimiin liittyv¨a aputulos. M¨ a¨ aritelm¨ a 2.3.32. Luvun n ∈ N ∪ {0} kertoma on luku n! = 1 · 2 · 3 · . . . · n, jos n ≥ 1, ja 0! = 1. Siis (n + 1)! = (n
+ 1)n!. Lis¨aksi, jos n, k ∈ N ∪ {0} ja 0 ≤ k ≤ n, niin binomikerroin nk on luku   n n! = k k!(n − k)!

Lemma 2.3.33.

      m+1 m m (i) = + . k k−1 k

  n (ii) ∈N k Todistus. (i) Harjoitusteht¨av¨a. (ii) Induktio n:n suhteen, alkaen luvusta
n = 0: V¨aite: Kaikilla n ∈ N ∪ {0} p¨atee nk ∈ N kaikilla 0 ≤ k ≤ n. 1◦ V¨aite p¨atee, kun n = 0:       n 0 0 0! =1∈N = = = 0! · 0! k k 0
2◦ Induktio-oletus: m ∈
N kaikilla 0 ≤ k ≤ m. k m+1 Induktiov¨aite: k ∈ N kaikilla 0 ≤ k ≤ m + 1. Todistus: Kohdan 1◦ nojalla       m+1 m m = + ∈N k k−1 k | {z } | {z } ∈N

2 40

∈N

Lause 2.3.34 (Newtonin binomikaava). Olkoot a, b ∈ R ja n ∈ N. T¨all¨oin n   X n n−k k a b (a + b) = k k=0           n n n n−1 n n−2 2 n n n n−1 = a + a b+ a b + ... + ab + b 0 1 2 n−1 n n

Newtonin binomikaava on tutun kaavan (a + b)2 = a2 + 2ab + b2 yleistys. Esimerkiksi tapauksessa n = 3 saadaan         3 3 3 2 3 1 2 3 3 3 (a + b) = a + a b+ ab + b 0 1 2 3 3! 3 3! 2 3! 1 2 3! 3 = a + a b+ ab + b 3!0! 2!1! 1!2! 0!3! = a3 + 3a2 b + 3ab2 + b3 . Todistus. Todistetaan Lause 2.3.34 induktiolla. 1◦ V¨aite p¨atee, kun n = 1:     1   X 1 1−k k 1 1 1! 1! a b = a+ b= a+ b = (a + b) = (a + b)1 . k 0 1 1!0! 0!1! k=0 2◦ Induktio-oletus:

m   X m m−k k (a + b) = a b . k k=0 m

Induktiov¨aite: (a + b)

m+1

=

m+1 X k=0

Todistus:

41

 m + 1 (m+1)−k k a b . k

(a + b)m+1 = (a + b)(a + b)m ! m   X m m−k k i.o. = (a + b) a b k k=0 m   m   X X m m−k k m m−k k =a a b +b a b k k k=0 k=0 m   m   X m m+1−k k X m m−k k+1 a b + a b = k k k=0 k=0  m   m+1  X m m+1−k k X m = a b + am−(j−1) bj k j−1 j=1 k=0  m   m+1  X m m+1−k k X m = a b + am+1−k bk k k − 1 k=0 k=1      m   m  X m m+1 m m+1−k k X m m m+1 m+1−k k = a + a b + a b + b 0 k k−1 m k=1 k=1       m   m m+1 m m+1 X m m m+1−k k = a + + a b + b m 0 k k−1 k=1 | {z } =

`m+1´ (Lemma 2.3.33) k

    m  m + 1 m+1 m + 1 m+1 X m + 1 m+1−k k = a + a b + b 0 k m+1 k=1 m+1 X m + 1  = a(m+1)−k bk . k k=0 

2 T¨am¨an osion lopuksi todistetaan kaavan a2 − b2 = (a − b)(a + b) yleistys: Lause 2.3.35. Olkoon a, b ∈ R ja n ∈ N. T¨all¨oin an − bn = (a − b)

n X

an−k bk−1

k=1 n−1

= (a − b)(a

+ an−2 b + . . . + abn−2 + bn−1 )

Huomautus 2.3.36. Jos a, b ≥ 0, niin Lauseen 2.3.35 nojalla a > b jos ja vain jos an > bn kaikilla n ∈ N. Todistus. Todistetaan Lause 2.3.35 induktiolla. 42

1◦ V¨aite p¨atee, kun n = 1: (a − b)

n X

an−k bk−1 = (a − b)a0 b0 = a − b = a1 − b1 .

k=1

2◦ Induktio-oletus: m

m

a − b = (a − b)

m X

am−k bk−1 .

k=1

Induktiov¨aite: a

m+1

−b

m+1

= (a − b)

m+1 X

a(m+1)−k bk−1 .

k=1

Todistus: m X

i.o.

am+1 = a · am = a (a − b)

! am−k bk−1

! + bm

k=1

= (a − b) = (a − b) = (a − b) = (a − b)

m X k=1 m+1 X k=1 m+1 X k=1 m+1 X

! am+1−k bk−1

+ abm !

am+1−k bk−1

− (a − b)a0 bm + abm !

am+1−k bk−1

− abm + bm+1 + abm !

a

m+1−k k−1

b

+ bm+1

k=1

T¨ast¨a saadaan, ett¨a a

m+1

−b

m+1

= (a − b)

m+1 X

a(m+1)−k bk−1 .

k=1

2

Harjoitusteht¨ avi¨ a 1. Osoita induktiolla, etta kaava 1 + 3 + 5 + . . . + (2n − 1) = n2 on voimassa kaikille luonnollisille luvuille n = 1, 2, . . .. 43

2. Olkoon k pariton luonnollinen luku. Osoita induktiolla, ett¨a k n on pariton kaikille n ∈ N. 3. Osoita induktiolla, ett¨a jos n ∈ N, niin 1 2 3 n 1 + + + ... + =1− . 2! 3! 4! (n + 1)! (n + 1)! 4. Osoita induktiolla, ett¨a kaava 1 · 1! + 2 · 2! + 3 · 3! + . . . + n · n! = (n + 1)! − 1 on voimassa kaikille luonnollisille luvuille n = 1, 2, 3, . . . . 5. Osoita induktiolla, ett¨a kaava 1 · 3 + 2 · 4 + 3 · 5 + · · · + n(n + 2) =

n(n + 1)(2n + 7) 6

on voimassa kaikille luonnollisille luvuille n = 1, 2, 3, . . . . 6. Osoita induktiolla, ett¨a jos n ≥ 2, niin 5|(n5 − n). 7. Olkoon x ∈ R, x > −1. Osoita induktiota k¨aytt¨aen, ett¨a (1 + x)n ≥ 1 + nx kaikille n ∈ N. 8. Osoita induktiolla, ett¨a 1 1 1 1 1 n + + + ... + n + n ≥1+ . 1 2 3 2 −1 2 2 9. Osoita induktiolla, ett¨a 2n ≥ n2 kaikille n ∈ N, n ≥ 4. 10. Seuraavassa “todistuksessa” osoitetaan oikeaksi v¨aite joka ei tunnetusti pid¨a paikkaansa. Todistuksessa t¨aytyy siis olla jokin virhe. Mik¨a se on? V¨ aite: Kaikki luonnolliset luvut ovat yht¨asuuria. Todistus: Todistetaan induktiolla, ett¨a jokainen luonnollinen luku n on yht¨asuuri kaikkien sit¨a edelt¨avien lukujen 1, 2, ..., n − 1 kanssa. 1◦ n = 1, ei edelt¨avi¨a lukuja, joten v¨aite ok. 44

2◦ Tehd¨a¨an induktio-oletus, ett¨a v¨aite p¨atee, kun n = k, ja osoitetaan, ett¨a v¨aite p¨atee, kun n = k + 1: Olkoon j ∈ {1, 2, ..., k} mielivaltainen. Riitt¨a¨a osoittaa, ett¨a j = k + 1. Koska j edelt¨a¨a lukua k + 1, j − 1 edelt¨a¨a lukua (k + 1) − 1 = k. Siten induktio-oletuksen nojalla j − 1 = k. Mutta t¨all¨oinh¨an (j − 1) + 1 = k + 1, eli j = k + 1. Koska j ∈ {1, 2, ..., k} oli mielivaltainen, on k + 1 yht¨asuuri kaikkien sit¨a edelt¨avien lukujen kanssa, ja siten induktioaskel on todistettu. Koska nyt induktioperiaatteen mukaan v¨aite p¨atee jokaiselle luonnolliselle luvulle, t¨aytyy kaikkien luonnollisten lukujen olla yht¨asuuria.

2.4

V¨ aitteen osoittaminen v¨ a¨ ar¨ aksi “A tragedy of mathematics is a beautiful conjecture ruined by an ugly fact.” Anonymous.

Edell¨a on tarkasteltu p¨a¨aasiassa teht¨avi¨a, joissa on annettu ennakkoon todeksi “tiedetty” v¨aitelause ja pyydetty todistamaan se. Matematiikassa tulee kuitenkin usein vastaan v¨aitelauseita, joiden totuusarvo ei ole ennakkoon tiedossa. T¨all¨oin on joko todistettava v¨aite tai kumottava se, eli osoitettava, ett¨a v¨aitteen negaatio on totta. Esimerkki 2.4.1. Tarkastellaan v¨aitelausetta “Jos n ∈ N, niin n2 − n + 11 on alkuluku”. Kun tarkastellaan pieni¨a luonnollisia lukuja, n¨aytt¨aisi v¨aite pit¨av¨an paikkansa: n n2 − n + 11

1 11

2 13

3 4 5 6 17 23 31 41

7 8 9 ... 53 67 83 . . .

Kuitenkin jos n = 11, niin n2 − n + 11 = 112 − 11 + 11 = 112 = 11 · 11 eli kyseess¨a ei en¨a¨a olekaan alkuluku. Luku n = 11 kelpaa siten vastaesimerkiksi, joka n¨aytt¨a¨a, ett¨a v¨aitelause “Jos n ∈ N, niin n2 − n + 11 on alkuluku” ei olekaan totta. Esimerkki 2.4.2. Tarkastellaan v¨aitelausetta “On olemassa reaaliluku x, jolle p¨atee x4 < x < x2 ”. Onko t¨am¨a v¨aitelause tosi vai ep¨atosi? V¨aitelauseen ep¨atodeksi osoittamiseksi ei t¨ass¨a tapauksessa riit¨a esimerkki luvusta x, joka ei toteuta ehtoja x4 < x < x2 , sill¨a t¨allainen vastaesimerkki n¨aytt¨aisi vasta, ett¨a v¨aitelause “Jokaiselle reaaliluvulle x p¨atee x4 < x < x2 ” on ep¨atosi. Sen sijaan on n¨aytett¨av¨a, ett¨a “ei ole olemassa reaalilukua x, jolle p¨atee x4 < x < x2 ”, toisin sanoen, “jokaiselle reaaliluvulle x p¨atee x4 ≥ x tai x ≥ x2 ”. Todistetaan t¨am¨a jakamalla tarkastelu kolmeen tapaukseen: 45

1. Jos x ≤ 0, niin x4 ≥ 0 ≥ x, eli erityisesti x4 ≥ x. 2. Jos x ∈ ]0, 1], niin x2 = x · x ≤ 1 · x = x eli x ≥ x2 . 3. Jos x ∈ ]1, ∞[, niin x4 = x · x · x · x ≥ 1 · 1 · 1 · x = x eli x4 ≥ x. N¨ain on siis kaikki reaaliluvut k¨ayty l¨api, ja jokaisessa tapauksessa ainakin toinen ep¨ayht¨al¨oist¨a x4 ≥ x tai x ≥ x2 on voimassa. Niinp¨a alkuper¨ainen v¨aite “On olemassa reaaliluku x, jolle p¨atee x4 < x < x2 ” on nyt n¨aytetty ep¨atodeksi.

2.5

Joukko-oppi ja todistaminen

Seuraavaksi tutustumme siihen, miten joukko-oppiin liittyvi¨a v¨aitelauseita todistetaan. Avainasemassa ovat aiemmin annetut m¨a¨aritelm¨at joukkojen yht¨asuuruudelle, osajoukolle, leikkaukselle, yhdisteelle jne., sill¨a viime k¨adess¨a juuri m¨a¨aritelm¨at kertovat yksityiskohtaisesti mit¨a todistuksissa on pystytt¨av¨a osoittamaan. Esimerkki 2.5.1. Olkoon A = { n1 + (−1)n : n ∈ N}. T¨all¨oin joukkoon A kuuluvat mm. alkiot 0, 32 , − 23 ja 54 , jotka saadaan kun n = 1, 2, 3, 4. Osoitetaan, ett¨a A ⊂ [−1, 23 ]. Todistus. Olkoon x mik¨a tahansa joukon A alkio. T¨all¨oin on olemassa jokin n ∈ N siten, ett¨a x = n1 + (−1)n . Todetaan ensin, ett¨a 1 + (−1)n > (−1)n ≥ −1 n Toisaalta, jos n on parillinen, niin x=

1 1 1 3 + (−1)n = + 1 ≤ + 1 = , n n 2 2 ja jos n on pariton, niin x=

x=

1 1 + (−1)n = − 1 ≤ 0. n n

N¨ain ollen, olipa n parillinen tai pariton, aina kuitenkin p¨atee x ≤ 32 . Yhdist¨am¨all¨a tiedot x > −1 ja x ≤ 32 saadaan x ∈ [−1, 23 ]. Nyt on siis todettu, ett¨a joukon A mielivaltainen alkio x v¨altt¨am¨att¨a kuuluu v¨alille [−1, 32 ], joten A ⊂ [−1, 23 ]. 2 Lause 2.5.2. Kaikille joukoille A, B ja C p¨atee (a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), (b) (A ∪ B) ⊂ A ⇐⇒ B ⊂ A. 46

Todistus. (a) Haluamme todistaa joukkojen A ∪ (B ∩ C) ja (A ∪ B) ∩ (A ∪ C) yht¨asuuruuden, eli sen, ett¨a niill¨a on t¨asm¨alleen samat alkiot: kaikille x on x ∈ A ∪ (B ∩ C) ⇐⇒ x ∈ (A ∪ B) ∩ (A ∪ C). T¨am¨an todistaminen tapahtuu kahdessa osassa: “⊂” : Osoitetaan, ett¨a A ∪ (B ∩ C) on joukon (A ∪ B) ∩ (A ∪ C) osajoukko: x ∈ A ∪ (B ∩ C) =⇒ x ∈ (A ∪ B) ∩ (A ∪ C). Todistus: Koska x ∈ A ∪ (B ∩ C), niin x ∈ A tai x ∈ (B ∩ C). Jos x ∈ A, niin yhdisteen m¨aa¨ritelm¨an nojalla x ∈ A ∪ B ja x ∈ A ∪ C. Jos taas x ∈ B ∩ C, niin leikkauksen m¨a¨aritelm¨an nojalla t¨all¨oin x ∈ B ja x ∈ C. T¨ast¨a seuraa yhdisteen m¨a¨aritelm¨an nojalla, ett¨a x ∈ A ∪ B ja x ∈ A ∪ C. Siten kummassakin tapauksessa x ∈ (A ∪ B) ∩ (A ∪ C), kuten v¨aitettiin. “⊃” : Osoitetaan, ett¨a (A ∪ B) ∩ (A ∪ C) on joukon A ∪ (B ∩ C) osajoukko: x ∈ (A ∪ B) ∩ (A ∪ C) =⇒ x ∈ A ∪ (B ∩ C). Todistus: Koska x ∈ (A ∪ B) ∩ (A ∪ C), niin x ∈ A ∪ B ja x ∈ A ∪ C. Jos nyt x ∈ A, niin selv¨asti x ∈ A ∪ (B ∩ C). Jos taas x 6∈ A, niin koska x ∈ A ∪ B ja x ∈ A ∪ C, on x ∈ B ja x ∈ C. Siten x ∈ B ∩ C, mist¨a seuraa, ett¨a x ∈ A ∪ (B ∩ C). Siten siis v¨altt¨am¨att¨a x ∈ A ∪ (B ∩ C). “⊂” ja “⊃” yhdess¨a takaavat, ett¨a joukot ovat samat. (b) Koska on kyse ekvivalenssin eli yht¨apit¨avyyden todistamisesta, on t¨am¨akin todistus teht¨av¨a kahdessa osassa: “⇒” : Jos (A ∪ B) ⊂ A, niin B ⊂ A. Todistus: Olkoon x ∈ B. Haluamme osoittaa, ett¨a x ∈ A. Koska x ∈ B, niin x ∈ A ∪ B, mist¨a oletuksen nojalla seuraa x ∈ A. Siten jokainen joukon B alkio x on v¨altt¨am¨att¨a my¨os joukon A alkio eli B ⊂ A. “⇐” : Jos B ⊂ A, niin (A ∪ B) ⊂ A. Todistus: Olkoon x ∈ A ∪ B. Haluamme osoittaa, ett¨a x ∈ A. Koska x ∈ A ∪ B, niin x ∈ A tai x ∈ B. (Muista, ett¨a t¨ah¨an sis¨altyy my¨os vaihtoehto, ett¨a x sis¨altyy molempiin joukkoihin.) Jos x ∈ A, niin todistushan on valmis! Jos taas x ∈ B, niin koska oletuksen mukaan B ⊂ A, niin x ∈ A. Siisp¨a molemmissa vaihtoehdoissa toteutui x ∈ A, joten olemme n¨aytt¨aneet, ett¨a (A ∪ B) ⊂ A. 47

Kohdat “⇒” ja “⇐” yhdess¨a osoittavat ekvivalenssin oikeaksi. 2 Lause 2.5.3. Olkoot A, A0 , B ja B 0 joukkoja siten, ett¨a A ⊂ A0 ja B ⊂ B 0 . T¨all¨oin A × B ⊂ A0 × B 0 . Todistus. On siis osoitettava, ett¨a (x, y) ∈ A × B =⇒ (x, y) ∈ A0 × B 0 . Olkoon (x, y) mik¨a tahansa joukkoon A × B kuuluva j¨arjestetty pari. Karteesisen tulon m¨a¨aritelm¨an mukaan t¨am¨a tarkoittaa sit¨a, ett¨a x ∈ A ja y ∈ B. Oletusten mukaan A ⊂ A0 ja B ⊂ B 0 , joten x ∈ A0 ja y ∈ B 0 . Karteesisen tulon m¨a¨aritelm¨an perusteella siis (x, y) ∈ A0 × B 0 aivan kuten v¨aitettiinkin. 2 Esimerkki 2.5.4. Osoitetaan vastaesimerkill¨a, ett¨a yht¨al¨o A ∪ (B ∩ C) = (A ∪ B) ∩ C ei aina p¨ade. Valitaan esimerkiksi A = {1, 2}, B = {2, 3} ja C = {1, 3}. T¨all¨oin A ∪ (B ∩ C) = {1, 2} ∪ {3} = {1, 2, 3} ja (A ∪ B) ∩ C = {1, 2, 3} ∩ {1, 3} = {1, 3}, joten A ∪ (B ∩ C) 6= (A ∪ B) ∩ C n¨aille joukoille A, B ja C.

Harjoitusteht¨ avi¨ a 1. Olkoon A = { x2x+1 : x ∈ R}. Osoita, ett¨a A ⊂ [− 12 , 12 ]. 2. Olkoot A, B ja C joukkoja, joille p¨atee A \ B = C \ B. Osoita, ett¨a (C \ A) ⊂ B. 3. Olkoot A, B ja C joukkoja. Osoita, ett¨a jos (A ∪ C) ⊂ (B ∪ C), niin (A \ C) ⊂ (B \ C). 4. Olkoon A, B ja C joukkoja, joille p¨atee (A \ B) ⊂ C. Osoita, ett¨a t¨all¨oin (A \ C) ⊂ (A ∩ B).

48

5. Muodosta seuraavien v¨aitelauseiden negaatiot ja todista v¨aitelauseet oikeaksi tai v¨a¨ar¨aksi. (a) Jokaiselle a ∈ N on olemassa luvut b, c ∈ N siten, ett¨a ab = 2c + 1. (b) Jos x, y ∈ R toteuttavat yht¨al¨on x2 + 5y = y 2 + 5x, niin x = y tai x + y = 5. 6. Muodosta seuraavien v¨aitelauseiden negaatiot ja todista v¨aitelauseet oikeaksi tai v¨a¨ar¨aksi. (a) Jokaisella x ∈ N on olemassa y ∈ N siten, ett¨a xy > 3. (b) Jos n ∈ N ja n ≥ 2, niin 4|n2 tai 4|(n − 1)(n + 1). 7. Osoita seuraavat v¨aitelauseet oikeaksi tai v¨aa¨r¨aksi. (a) Jos a, b ∈ N, niin a + b < ab. (b) Jos a, b, c ∈ N ja a|bc, niin a|b tai a|c. (c) On olemassa n ∈ N, n ≥ 4, siten, ett¨a 2n2 − 5n + 2 on alkuluku. 8. Olkoot seuraavassa A, B ja C joukkoja. Osoita seuraavat v¨aitelauseet oikeaksi tai v¨a¨ar¨aksi. (a) Jos A ⊂ (B ∪ C), niin A ⊂ B tai A ⊂ C. (b) Jos A = B \ C, niin B = A ∪ C. (c) Jos A ⊂ B ja A 6⊂ C, niin B 6⊂ C. 9. Olkoot A, B ja C joukkoja. Osoita seuraavat v¨aitelauseet oikeaksi tai v¨a¨ar¨aksi. (a) A \ (B \ C) ⊂ (A \ B) ∩ (A \ C). (b) (A \ B) ∩ (A \ C) ⊂ A \ (B \ C). 10. Olkoot seuraavassa A, B ja C joukkoja. Osoita seuraavat v¨aitelauseet oikeaksi tai v¨a¨ar¨aksi. (a) Jos A ∩ B 6= ∅ ja B ∩ C 6= ∅, niin A ∩ C 6= ∅. (b) Jos A ⊂ B, niin (C \ B) ⊂ (C \ A).

49

Luku 3 Funktioista 3.1

Funktioihin liittyvi¨ a perusk¨ asitteit¨ a

Funktio eli kuvaus on ehdottomasti yksi matematiikan keskeisimmist¨a k¨asitteit¨a. Matematiikan opiskelija t¨orm¨a¨a funktioihin jokaisella kurssilla, ja siksi funktioihin liittyvien m¨a¨aritelmien ja k¨asitteiden hallinta on eritt¨ain t¨arke¨a¨a. M¨ a¨ aritelm¨ a 3.1.1. Olkoot A ja B mit¨a tahansa ep¨atyhji¨a joukkoja. Kuvaus eli funktio f :A→B on s¨a¨ant¨o, joka liitt¨a¨a jokaiseen joukon A alkioon a t¨ asm¨ alleen yhden joukon B alkion f (a). T¨at¨a merkit¨a¨an my¨os a 7→ f (a) (a ∈ A, f (a) ∈ B), ja sanotaan, ett¨a f (a) on funktion f arvo pisteess¨a a ∈ A, tai ett¨a f (a) on a:n kuva (tai kuvapiste) kuvauksessa f , tai ett¨a alkio (piste) a kuvautuu alkioksi (pisteeksi) f (a) kuvauksessa f . Joukkoa A kutsutaan kuvauksen f : A → B m¨a¨arittelyjoukoksi, ja joukkoa B kuvauksen maalijoukoksi. Huomautus 3.1.2. (a) Funktio muodostuu siis kolmikosta (f, A, B). Erityisesti funktiot f : A → B ja g : C → D ovat samat jos ja vain jos (i) A = C (sama m¨aa¨rittelyjoukko) (ii) B = D (sama maalijoukko) (iii) f (x) = g(x) kaikilla x ∈ A = C. Funktiot f : R → R, f (x) = x2 ja g : R → ]0, ∞[, g(x) = x2 ovat siis (tarkkaan ottaen) kaksi eri funktiota, sill¨a niill¨a on eri maalijoukot.

50

(b) Jokaista alkiota x ∈ A vastaa t¨asm¨alleen yksi kuvapiste f (x) ∈ B. Sen sijaan, jos y ∈ B, niin (i) voi olla useampia joukon A alkioita x, joille f (x) = y. (ii) voi olla, ett¨a y ei ole mink¨aa¨n joukon A alkion kuvapiste. Esimerkki 3.1.3. Funktioita ja esimerkkej¨a s¨a¨ann¨oist¨a, jotka eiv¨at ole funktioita: (a) Olkoot A = {a, b, c} ja B = {1, 2, 3, 4}. M¨a¨aritell¨a¨an funktio f : A → B seuraavasti: f (a) = 2, f (b) = 3, f (c) = 2. Nyt siis f (a) = f (c), mutta t¨at¨a ei ole mill¨a¨an tavalla kielletty funktion m¨a¨aritelm¨ass¨a. (b) Ympyr¨akiekon pinta-ala P riippuu ympyr¨an s¨ateest¨a r kaavan P = πr2 mukaisesti. T¨am¨a vastaavuus m¨a¨arittelee funktion P : [0, ∞[→ [0, ∞[, P (r) = πr2 . (c) Oletetaan, ett¨a kappaleen sijainnin xy-koordinaatistossa ajanhetkell¨a t kertoo funktio g : [−2, 2] → R2 , g(t) = (t2 , t3 − 3t). T¨all¨oin kappale l¨ahtee hetkell¨a t = −2 pisteest¨a g(−2) = (4, −2) ja p¨a¨atyy hetkell¨a t = 2 pisteeseen g(2) = (4, 2) kulkien v¨alill¨a t ∈ [−2, 2] oheisen reitin mukaisesti:

(d) Olkoon f : R2 → R2 , f (x, y) = (2x + y, x − 3y). Siis esimerkiksi f (1, −1) = (2 · 1 + (−1), 1 − 3 · (−1)) = (1, 4). f (2, 1) = (5, −1).

51

n (e) S¨aa¨nt¨o f : N → Z, f (n) = n+2 ei m¨a¨arittele funktiota, sill¨a s¨a¨ann¨on lukuun n liitt¨am¨a arvo f (n) ei ole kokonaisluku (eli f (n) 6∈ Z) jos esimerkiksi n = 1.

Sen sijaan f : N → Q, f (n) = n ∈ N.

n n+2

on funktio, sill¨a

n n+2

∈ Q kaikilla

(f) Oletetaan, ett¨a a, b ∈ Z ja b 6= 0. M¨aa¨ritell¨aa¨n h : Q → R asettamalla a ab 7→ 2 . b b + a2 + 1 Onko h funktio? Ei ole, sill¨a esimerkiksi alkioon maalijoukon R alkio:

1 3

=

1 1·3 3 7→ 2 = , 3 1 + 32 + 1 11

2 6

∈ Q liitet¨aa¨n useampi kuin yksi

2 2·6 12 3 7→ 2 = = 6 . 6 2 + 62 + 1 41 11

(g) M¨aa¨ritell¨aa¨n f : Q → R k¨aytt¨am¨all¨a s¨aa¨nt¨oa¨ ab a 7→ 2 . b b + a2 Onko f funktio? Kyll¨a on. Jos

p q

=

r s

∈ Q, niin r =

ps . q

Siten

p pq 7→ 2 q p + q2 ja r rs 7→ 2 = s r + s2

ps s q p 2 s2 q2

+ s2

=

s2 pq p2

s2 ( q2 + 1)

=

pq . p2 + q 2

N¨ain ollen yll¨a oleva s¨a¨ant¨o liitt¨a¨a tietyn rationaaliluvun kaikkiin murtolukuesityksiin saman maalijoukon alkion, eli se todella m¨a¨arittelee funktion rationaalilukujen joukolta reaalilukujen joukolle.

3.1.1

Kuvajoukko ja alkukuva

M¨ a¨ aritelm¨ a 3.1.4. Olkoon f : A → B funktio. Joukon A0 ⊂ A kuvajoukko on joukko f (A0 ) = {f (x) : x ∈ A0 } = {y ∈ B : on olemassa x ∈ A0 siten, ett¨a f (x) = y }, 52

ts. f (A0 ) on (osa)joukon A0 alkioiden kuvapisteiden muodostama joukko. Joukon B 0 ⊂ B alkukuva on joukko f {−1} (B 0 ) = {x ∈ A : f (x) ∈ B 0 } ts. f {−1} (B 0 ) on (osa)joukkoon B 0 kuvautuvien pisteiden muodostama joukko. Huomautus 3.1.5. (i) Erityisesti f (A) = {f (a) : a ∈ A} ⊂ B on kuvauksen f kuvajoukko eli arvojoukko. Nyt siis f (A) ⊂ B, mutta ei tarvitse olla f (A) = B. Esimerkiksi t¨ast¨a kelpaa funktio g : R → R, g(x) = x2 , jolle g(R) = [0, ∞[. (ii) Joukon B 0 ⊂ B alkukuva f {−1} (B 0 ) kuvauksessa f : A → B on aina m¨a¨aritelty (olivatpa f, A ja B mit¨a tahansa). Se voi olla tyhj¨a joukko, koko joukko A tai jotain n¨aiden v¨alilt¨a. Esimerkki 3.1.6. Esimerkkej¨a kuvajoukoista ja alkukuvista. (a) Olkoot A = {a, b, c}, B = {1, 2, 3, 4} ja m¨aa¨ritell¨a¨an kuvaus f : A → B kuten Esimerkin 3.1.3 kohdassa (a): f (a) = 2, f (b) = 3, f (c) = 2. Olkoot U1 = {a, b}, U2 = {a, c}, V1 = {1, 4} ja V2 = {1, 2}. T¨all¨oin f (U1 ) = {f (a), f (b)} = {2, 3} f (U2 ) = {f (a), f (c)} = {2} f {−1} (V1 ) = {x ∈ A : f (x) = 1 tai f (x) = 4} = ∅ f {−1} (V2 ) = {a, c} Huomaa, ett¨a vaikka U2 = f {−1} (V2 ), niin f (U2 ) 6= V2 . (b) Olkoon f : R → R, f (x) = x2 − 2. Olkoot U = [0, 2] ja V = [−1, 1]. M¨a¨aritet¨a¨an f (U ) ja f {−1} (V ). M¨aa¨ritelm¨an mukaisesti f (U ) = {f (x) : x ∈ U } = {x2 − 2 : x ∈ [0, 2]} = [−2, 2]

53

ja f {−1} (V ) = {x ∈ R : f (x) ∈ V } = {x ∈ R : x2 − 2 ∈ [−1, 1]} = {x ∈ R : −1 ≤ x2 − 2 ≤ 1} = {x ∈ R : 1 ≤ x2 ≤ 3} √ = {x ∈ R : 1 ≤ |x| ≤ 3} √ √ = [− 3, −1] ∪ [1, 3]. (c) Olkoon f : R2 → R2 , f (x, y) = (2x + y, x − 3y). Olkoot U = {(x, y) ∈ R2 : y = 31 x + 1}, V = {(u, v) ∈ R2 : u = v}. M¨aa¨ritet¨a¨an f (U ) ja f {−1} (V ). f (U ) = {f (x, y) : (x, y) ∈ U } = {(2x + y, x − 3y) : y = 31 x + 1, x ∈ R} = {(2x + 13 x + 1, x − x − 3) : x ∈ R} = {( 73 x + 1, −3) : x ∈ R} = {(u, v) ∈ R2 : v = −3, u ∈ R}. ja f {−1} (V ) = {(x, y) ∈ R2 : f (x, y) ∈ V } =u 2

= {(x, y) ∈ R = {(x, y) ∈ R2 = {(x, y) ∈ R2 = {(x, y) ∈ R2

=v

z }| { z }| { : (2x + y, x − 3y) ∈ V } : 2x + y = x − 3y} : 4y = −x} 1 : y = − x}. 4

(d) Olkoon f : [−4, 4] → R, ( |x| − 1 jos x > −2 f (x) = 2 jos x ≤ −2. M¨aa¨ritet¨a¨an joukon [1, 3] ⊂ [−4, 4] kuvajoukko: f ([1, 3]) = { f (x) : x ∈ [1, 3] } = { |x|−1 : x ∈ [1, 3] } = { x−1 : x ∈ [1, 3] } = [0, 2]. 54

M¨aa¨ritet¨a¨an joukon [0, 5] alkukuva: f {−1} ([0, 5]) = { x ∈ [−4, 4] : f (x) ∈ [0, 5] } = { x ∈ [−4, −2] : f (x) ∈ [0, 5] } ∪ { x ∈ [−2, 4] : f (x) ∈ [0, 5] } = [−4, −2] ∪ { x ∈ [−2, 4] : |x| − 1 ∈ [0, 5] } = [−4, −2] ∪ { x ∈ [−2, 4] : −6 ≤ x ≤ −1 tai 1 ≤ x ≤ 6 } = [−4, −2] ∪ [−2, −1] ∪ [1, 4] = [−4, −1] ∪ [1, 4].

(e) Kahden muuttujan funktion f : R2 → R alkukuvia f {−1} (c), miss¨a c ∈ R, kutsutaan funktion f tasa-arvojoukoiksi. Tasa-arvojoukko f {−1} (c) muodostuu siis niist¨a m¨aa¨rittelyjoukon pisteist¨a (x, y) ∈ R2 , joissa 55

funktio f saa arvon c. Oheisissa kuvissa on funktion f : R2 → R, f (x, y) = −(x2 + 2y 2 ) kuvaaja ja muutamia sen tasa-arvojoukkoja.

(f) Olkoon f : A → B kuvaus, ja olkoot V1 ⊂ B ja V2 ⊂ B joukkoja siten, ett¨a V1 ⊂ V2 . T¨all¨oin f {−1} (V1 ) ⊂ f {−1} (V2 ). Todistus. Olkoon x ∈ f {−1} (V1 ) mielivaltainen. Meid¨an on osoitettava, ett¨a x ∈ f {−1} (V2 ): Koska x ∈ f {−1} (V1 ), niin alkukuvan m¨aa¨ritelm¨an mukaan f (x) ∈ V1 . Koska V1 ⊂ V2 , niin t¨ast¨a seuraa, ett¨a f (x) ∈ V2 . Siten alkukuvan m¨a¨aritelm¨an nojalla x ∈ f {−1} (V2 ), mik¨a haluttiinkin osoittaa. 2 Huomautus 3.1.7. Funktion kuvaaja on eri asia kuin kuvajoukko!

3.1.2

Yhdistetty funktio

M¨ a¨ aritelm¨ a 3.1.8. Olkoot f : A → B ja g : C → D funktioita. Jos f (A) ⊂ C, niin voidaan muodostaa yhdistettu funktio g ◦ f : A → D, (g ◦ f )(x) := g(f (x)). 56

(Huomaa j¨arjestys!)

Huomautus 3.1.9. Jos x ∈ A, niin f (x) ∈ f (A). Oletuksen f (A) ⊂ C mukaan f (x) ∈ C, joten g(f (x)) on m¨a¨aritelty. Esimerkki 3.1.10. Esimerkkej¨a kuvausten yhdist¨amisest¨a: (a) Olkoot f : R → R, f (x) = 3x + 1 g : R → R, g(x) = sin x T¨all¨oin f ◦ g : R → R, (f ◦ g)(x) = f (g(x)) = f (sin x) = 3 sin x + 1, g ◦ f : R → R, (g ◦ f )(x) = g(f (x)) = g(3x + 1) = sin(3x + 1). Nyt esimerkiksi (f ◦g)(0) = 3 sin 0+1 = 1 ja (g ◦f )(0) = sin(3·0+1) = sin 1 ≈ 0.017452406, joten (f ◦g)(0) 6= (g ◦f )(0). N¨ain ollen f ◦g ja g ◦f ovat eri funktioita, vaikka niill¨a onkin samat m¨a¨arittely- ja maalijoukot. √ (b) Olkoot f : R → R, f (x) = 1 − 2x ja g : [0, ∞[ → R, g(x) = x. T¨all¨oin yhdistetty¨a kuvausta g ◦ f ei voida muodostaa, sill¨a f (R) 6⊂ [0, ∞[. Nimitt¨ain √ (g ◦ f )(x) = g(f (x)) = g(1 − 2x) = 1 − 2x ei ole m¨aa¨ritelty esimerkiksi, kun x = 1. (c) Olkoot f : R2 → R, f (x, y) = x + y, g : R → R2 , g(t) = (t2 , 2 − t). 57

T¨all¨oin f ◦ g : R → R, (f ◦ g)(t) = f (g(t)) = f (t2 , 2 − t) = t2 + 2 − t = t2 − t + 2 ja g ◦ f : R2 → R2 , (g ◦ f )(x, y) = g(f (x, y)) = g(x + y) = ((x + y)2 , 2 − (x + y)) = (x2 + 2xy + y 2 , 2 − x − y). Siis yhdistetyt kuvaukset f ◦ g ja g ◦ f ovat molemmat olemassa, mutta kuvauksen f ◦ g sek¨a m¨a¨arittely- ett¨a maalijoukko on R, kun taas kuvauksen g ◦ f kohdalla m¨a¨arittely- ja maalijoukko on R2 . (d) Olkoot f : R2 → R, f (x, y) = x + y, g : R → R, g(t) = t2 . T¨all¨oin g ◦ f : R2 → R, (g ◦ f )(x, y) = g(f (x, y)) = g(x + y) = x2 + 2xy + y 2 , mutta yhdistetty¨a kuvausta f ◦ g ei voida muodostaa. Yhteenveto. Olkoot f ja g kuvauksia. (i) Yleens¨a ei ole olemassa yhdistettyj¨a kuvauksia f ◦ g tai g ◦ f . (ii) Vaikka esimerkiksi f ◦ g olisi olemassa, niin g ◦ f :n ei tarvitse olla m¨a¨aritelty. (iii) Vaikka f ◦g ja g◦f olisivat molemmat m¨a¨ariteltyj¨a, niin ne yleens¨a eiv¨at ole samat. (Kertaa mit¨a vaaditaan, jotta kuvaukset olisivat samat.) Esimerkki 3.1.11. Olkoon f : R → R, f (x) = x2 + 1. Nyt voidaan muodostaa yhdistetty kuvaus f ◦ f : R → R, (f ◦ f )(x) = f (f (x)) = f (x2 + 1) = (x2 + 1)2 + 1 = x4 + 2x2 + 2 ja edelleen f ◦ (f ◦ f ) : R → R, f ◦ (f ◦ f )(x) = f (x4 + 2x2 + 2) = (x4 + 2x2 + 2)2 + 1 = x8 + 4x6 + 8x4 + 8x2 + 5 ja niin edelleen. Usein merkit¨aa¨n fn = f ◦ f ◦ · · · ◦ f | {z } n kpl

n

ja sanotaan, ett¨a f on f :n n:s iteraatio. 58

Harjoitusteht¨ avi¨ a 1. Olkoon f : Z → Z, f (k) = k 2 + 2. Merkit¨a¨an A = {1, 2, 3, 4} ja B = {−2, −1, 0, 1, 2}. M¨a¨arit¨a (a) kuvajoukot f (A) ja f (B). (b) alkukuvat f {−1} (A) ja f {−1} (B). 2. M¨aa¨rittelev¨atk¨o seuraavat s¨a¨ann¨ot funktion? Perustele. )= (a) f : Q → Q, f ( m n

m+n n2 +1

kaikilla

m n

∈ Q.

(b) g : [−1, 1] → ]0, ∞[, g(t) = 5t2 + 5t + 1. ( x + 1, kun x > 21 , 3. Olkoon f : R → R, f (x) = M¨a¨arit¨a kuvajoukko 1 − x, kun x ≤ 12 . f ([0, 1]) ja alkukuva f {−1} ([−1, 1]). 4. Olkoot f : R → [0, 2], f (x) = x22+1 ja g : [0, 2] → [0, 2], g(x) = 2 − x. M¨a¨arit¨a seuraavista yhdistetyist¨a funktioista ne, jotka ovat m¨a¨ariteltyj¨a. (a) f ◦ g (b) g ◦ f (c) f ◦ f (d) g ◦ g 5. Olkoon seuraavassa f : R → R funktio. Osoita seuraavat v¨aitelauseet oikeaksi tai v¨a¨ar¨aksi. (a) Suljetulle v¨alille [a, b] ⊂ R p¨atee f ([a, b]) = [f (a), f (b)]. (b) Jos joukoille B1 , B2 ⊂ R p¨atee f {−1} (B1 ) = f {−1} (B2 ), niin B1 = B2 . 6. Olkoon f : A → B funktio ja A0 ⊂ A ep¨atyhj¨a joukko. Osoita seuraavat v¨aitteet todeksi tai ep¨atodeksi. (a) A0 ⊂ f {−1} (f (A0 )). (b) f {−1} (f (A0 )) ⊂ A0 .

59

3.2

Kuvausten ominaisuuksia

3.2.1

Injektio ja surjektio

Olkoon f : A → B funktio. T¨all¨oin voi aivan hyvin l¨oyty¨a kaksi eri pistett¨a a1 , a2 ∈ A niin, ett¨a f (a1 ) = f (a2 ). Toisaalta voi l¨oyty¨a piste b ∈ B, jolle f (a) 6= b kaikilla pisteill¨a a ∈ A, toisin sanoen mik¨a¨an joukon A pisteist¨a ei kuvaudu pisteeksi b. Kuvaukset, joissa ei tapahdu jompaa kumpaa tai kumpaakaan n¨aist¨a ilmi¨oist¨a, ovat matematiikassa erikoisasemassa. Esimerkki 3.2.1. Olkoon f : R → R, f (x) = sin(x). Nyt f (0) = f (2π) = f (4π) = 0 ja f (x) 6= 10 kaikilla x ∈ R, sill¨a −1 ≤ f (x) ≤ 1 kaikilla x ∈ R. Funktio f on siis esimerkki kuvauksesta, jolla on molemmat edell¨a mainitut ominaisuudet. M¨ a¨ aritelm¨ a 3.2.2. Kuvaus f : A → B on injektio, jos se kuvaa eri pisteet eri arvoiksi, eli jos kaikille a1 , a2 ∈ A p¨atee a1 6= a2 =⇒ f (a1 ) 6= f (a2 ). Esimerkki 3.2.3. (a) Kuvaus f : R → R, f (x) = sin(x) ei ole injektio, sill¨a f (0) = f (2π). (b) Olkoon A kaikkien Jyv¨askyl¨an kaupungin asukkaiden muodostama joukko ja f : A → N, f (a) = “henkil¨on a sosiaaliturvatunnus”. Mit¨a tarkoittaa injektiivisyys t¨am¨an funktion kohdalla? (c) Olkoot A = {a1 , a2 , . . . , ak } ja B = {b1 , b2 , . . . , bm }. Jos k > m, niin mik¨aa¨n funktio f : A → B ei voi olla injektio. Todistus. Antiteesi: on olemassa funktio f : A → B, joka on injektio. T¨all¨oin siis f (ai ) 6= f (aj ) aina kun i 6= j, joten kuvajoukossa f (A) = {f (ai ) : i = 1, . . . , ak } on t¨asm¨alleen k kappaletta alkioita. T¨am¨a on kuitenkin mahdotonta, sill¨a f (A) ⊂ B, joukossa B on m alkiota ja oletuksen mukaan m < k. Siisp¨a antiteesin t¨aytyy olla ep¨atosi. 2 Huomautus 3.2.4. Funktio f : A → B on injektio ⇐⇒ ehdosta f (a1 ) = f (a2 ) seuraa a1 = a2 kaikilla a1 , a2 ∈ A 60

Todistus. ”⇒”: Antiteesi: on olemassa a1 , a2 ∈ A siten, ett¨a f (a1 ) = f (a2 ), mutta a1 6= a2 . T¨all¨oin f ei kuitenkaan voi olla injektio, sill¨a se kuvaa eri pisteet a1 ja a2 samaksi arvoksi. Niinp¨a antiteesi on ep¨atosi ja v¨aite totta. ”⇐”: Olkoot a1 , a2 ∈ A siten, ett¨a a1 6= a2 . Jos olisi f (a1 ) = f (a2 ), niin oletuksesta seuraisi a1 = a2 , mik¨a olisi ristiriita. Siisp¨a f (a1 ) 6= f (a2 ). N¨ain ollen f on injektio. 2 Esimerkki 3.2.5. Injektiivisyyden tutkiminen: (a) Tutki, onko kuvaus f : R2 → R, f (x, y) = x − y injektio vai ei. Ratkaisu: K¨aytet¨a¨an edellisen huomautuksen kohtaa (ii). Oletetaan, ett¨a pisteparit (x, y), (x0 , y 0 ) ∈ R2 ovat sellaisia, ett¨a f (x, y) = f (x0 , y 0 ). Seuraako t¨ast¨a, ett¨a (x, y) = (x0 , y 0 )? f (x, y) = f (x0 , y 0 ) ⇐⇒ x − y = x0 − y 0 ⇐⇒ x − x0 = y − y 0 . Huomaamme t¨ast¨a, ett¨a yht¨asuuruus f (x, y) = f (x0 , y 0 ) voi olla voimassa vaikka olisi x 6= x0 ja y 6= y 0 . Esimerkiksi f (1, 2) = −1, f (3, 4) = −1. Siten f ei ole injektio. (b) Tutki, onko kuvaus f : R → R2 , f (t) = (2t, t3 ) injektio vai ei. Ratkaisu: Olkoot t, s ∈ R siten, ett¨a f (t) = f (s). Seuraako t¨ast¨a, ett¨a t = s? f (t) = f (s) ⇒ (2t, t3 ) = (2s, s3 ) ⇒ 2t = 2s ja t3 = s3 ⇒ t = s. ∴ f on injektio. Injektiivisyyden ohella toinen t¨arke¨a kuvausominaisuus on surjektiivisuus. N¨am¨a kaksi ominaisuutta ovat toisistaan riippumattomia: injektiivisyyden perusteella ei voi (yleisesti ottaen) p¨a¨atell¨a mit¨a¨an kuvauksen surjektiivisuudesta, ja p¨ainvastoin. 61

M¨ a¨ aritelm¨ a 3.2.6. Kuvaus f : A → B on surjektio, jos f (A) = B, eli jos jokaisella b ∈ B on olemassa ainakin yksi a ∈ A siten, ett¨a f (a) = b. Esimerkki 3.2.7. Surjektioita ja ei-surjektioita: (a) Olkoon A kaikkien Jyv¨askyl¨an kaupungin asukkaiden muodostama joukko ja f : A → N, f (a) = “henkil¨on a sosiaaliturvatunnus”. Mit¨a tarkoittaa surjektiivisuus t¨am¨an funktion kohdalla? (b) Olkoot A = {a1 , a2 , . . . , ak } ja B = {b1 , b2 , . . . , bm }. Jos k < m, niin mik¨aa¨n funktio f : A → B ei voi olla surjektio. Todistus. Antiteesi: on olemassa funktio f : A → B, joka on surjektio. T¨all¨oin siis jokaiselle bj ∈ B on olemassa (ainakin yksi) alkio ai(j) ∈ A siten, ett¨a f (ai(j) ) = bj . Lis¨aksi on oltava ai(j) 6= ai(j 0 ) aina kun j 6= j 0 , sill¨a muuten f ei olisi funktio. Siten joukossa A t¨aytyy olla v¨ahint¨a¨an m eri alkiota. T¨am¨a on kuitenkin mahdotonta, sill¨a oletuksen mukaan joukossa A on vain k kappaletta alkioita ja ja k < m. Siisp¨a antiteesin t¨aytyy olla ep¨atosi. 2 (c) Funktio f : R → R, f (x) = sin x ei ole surjektio, sill¨a kuvajoukko f (R) = [−1, 1] 6= R. Sen sijaan funktio g : R → [−1, 1], g(x) = sin x on surjektio. Huomaa, ett¨a f ja g ovat eri funktioita! (d) Olkoon f : R2 → R, f (x, y) = x − y. Onko f surjektio? Olkoon t ∈ R mik¨a tahansa. L¨oytyyk¨o lukuparia (x, y) ∈ R2 siten, ett¨a f (x, y) = t? f (x, y) = t ⇐⇒ x − y = t. Jos valitaan (x, y) = (t, 0) ∈ R2 , niin silloin f (x, y) = f (t, 0) = t. T¨am¨a voidaan tehd¨a kaikille t ∈ R, joten m¨a¨aritelm¨an mukaan f on surjektio.

62

(e) Olkoon f : R → R2 , f (t) = (2t, t3 ). Onko f surjektio? Olkoon (x, y) ∈ R2 mik¨a tahansa tason pistepari. L¨oytyyk¨o alkiota t ∈ R siten, ett¨a f (t) = (x, y)? f (t) = (x, y) ⇐⇒ (2t, t3 ) = (x, y) ⇐⇒ x = 2t ja y = t3 =


3 1 x 2

= 81 x3 .

Mutta nyt (x, y) ei saa en¨aa¨ olla mielivaltainen, koska on oltava y = 18 x3 . Esimerkiksi, jos on (x, y) = (2, 0) (huomaa: 0 6= 1 = 81 · 23 ), niin f (t) = (2, 0) ⇐⇒ (2t, t3 ) = (2, 0) ⇐⇒ 2t = 2 ja t3 = 0 ⇐⇒ t = 1 ja t = 0 ristiriita! Koska siis f (t) 6= (2, 0) kaikilla t ∈ R, ei kuvaus f ole surjektio. M¨ a¨ aritelm¨ a 3.2.8. Kuvaus f : A → B on bijektio, jos se on sek¨a injektio ett¨a surjektio. Muista. Injektiivisyyteen ja surjektiivisuuteen liittyen on hyv¨a muistaa, ett¨a (i) injektiivisyys ja surjektiivisuus ovat toisistaan riippumattomia ominaisuuksia. Kumpikaan ei seuraa toisesta. (ii) yleens¨a kuvauksella ei ole kumpaakaan n¨aist¨a ominaisuuksista. Esimerkki 3.2.9. Funktio g : [0, 2] → [0, 4], g(x) = x2 on bijektio. Todistus. 1◦ Todistetaan, ett¨a g on surjektio. Olkoon y ∈ [0, 4] mik¨a tahansa. Pit¨a¨a l¨oyt¨a¨a x √ ∈ [0, 2] siten, ett¨a √ √ g(x) = y. Valitaan x = y. Koska 0 ≤ y ≤ 4, niin 0 ≤ y ≤ 2. Siis √ Lis¨aksi

y ∈ [0, 2].

√ √ g(x) = g( y) = ( y)2 = y.

T¨aten g on surjektio.

63

2◦ Todistetaan, ett¨a g on injektio. Antiteesi: g ei ole injektio. On siis olemassa x1 , x2 ∈ [0, 2] siten, ett¨a x1 6= x2 ja g(x1 ) = g(x2 ). Nyt 0 = g(x1 ) − g(x2 ) = x21 − x22 = (x1 − x2 )(x1 + x2 ) Koska x1 6= x2 ja x1 , x2 ∈ [0, 2], niin x1 + x2 6= 0. Siten on oltava x1 − x2 = 0 eli x1 = x 2 . T¨am¨a on ristiriita, sill¨a antiteesin mukaan x1 6= x2 . Antiteesi on siis v¨aa¨rin ja g on injektio. Kohtien 1◦ ja 2◦ nojalla g on bijektio. 2

3.2.2

K¨ a¨ anteisfunktio

Olkoon f : A → B funktio. Jos f on bijektio, eli siis sek¨a surjektio ett¨a injektio, niin jokaista b ∈ B vastaa t¨asm¨alleen yksi a ∈ A siten, ett¨a f (a) = b: surjektiivisuuden nojalla annetulle b ∈ B l¨oytyy ainakin yksi t¨allainen alkio a ∈ A, ja injektiivisyys puolestaan takaa sen, ettei mik¨a¨an muu joukon A piste voi kuvautua b:ksi. Siten on olemassa s¨a¨ant¨o, joka liitt¨a¨a jokaiseen joukon B alkioon t¨asm¨alleen yhden joukon A alkion. N¨ain saadaan funktio g : B → A, jolle g(b) = “se yksik¨asitteinen a, joka toteuttaa yht¨al¨on f (a) = b”. M¨ a¨ aritelm¨ a 3.2.10. Olkoon f : A → B kuvaus. Funktio g : B → A on f k¨a¨anteisfunktio, jos f (g(b)) = b kaikilla b ∈ B ja g(f (a)) = a kaikilla a ∈ A, toisin sanoen f ◦ g : B → B on joukon B identtinen kuvaus ja g ◦ f : A → A on joukon A identtinen kuvaus. Jos k¨a¨anteiskuvaus on olemassa, se on yksik¨asitteinen ja sit¨a merkit¨a¨an symbolilla f −1 : B → A. Esimerkki 3.2.11. Funktion f : [0, 2] → [0, 4], f (x) = x2 k¨a¨anteisfunktio √ on g : [0, 4] → [0, 2], g(y) = y, sill¨a √ √ f (g(y)) = f ( y) = ( y)2 = y 64

kaikilla y ∈ [0, 4] ja g(f (x)) = g(x2 ) =

√

x2 = |x| = x

kaikilla x ∈ [0, 2]. Yleens¨a annetulla kuvauksella ei ole k¨a¨anteiskuvausta. Riitt¨av¨a ja v¨altt¨am¨at¨on ehto k¨a¨anteiskuvauksen olemassaoloon on kuvauksen bijektiivisyys. Lause 3.2.12. Olkoon f : A → B funktio. T¨all¨oin on olemassa k¨a¨anteisfunktio f −1 : B → A jos ja vain jos f on bijektio. Todistus. ” ⇒ ” Oletus: On olemassa k¨a¨anteisfunktio f −1 : B → A. V¨aite: Funktio f on injektio ja surjektio. 1◦ Todistetaan, ett¨a f on injektio. Antiteesi: f ei ole injektio. On siis olemassa x1 , x2 ∈ A siten, ett¨a x1 6= x2 ja f (x1 ) = f (x2 ). T¨all¨oin f −1 (f (x1 )) = f −1 (f (x2 )). Siten x1 = f −1 (f (x1 )) = f −1 (f (x2 )) = x2 eli x1 = x2 . T¨am¨a on ristiriita, sill¨a antiteesin mukaan x1 6= x2 . Funktio f on siis injektio. 2◦ Todistetaan, ett¨a f on surjektio. Olkoon y ∈ B. Haluamme l¨oyt¨a¨a luvun x ∈ A, jolle f (x) = y. Nyt luku f −1 (y) (k¨a¨anteisfunktion f −1 arvo pisteess¨a y) kuuluu joukkoo A ja f (f −1 (y)) = y. Voimme siis valita x = f −1 (y). T¨aten f on surjektio. ” ⇐ ” Oletus: Funktio f on bijektio eli sek¨a surjektio ett¨a injektio. V¨aite: On olemassa k¨a¨anteisfunktio f −1 : B → A. Todistus: M¨a¨aritell¨a¨an g : B → A, g(y) = ”se yksik¨asitteinen x jolle p¨atee f (x) = y”. T¨all¨oin g on funktio, sill¨a bijektiivisyyden nojalla jokaiselle y ∈ B on olemassa t¨asm¨alleen yksi x ∈ A, jolle f (x) = y. Lis¨aksi f (g(y)) = y kaikilla y ∈ B ja g(f (x)) = x kaikilla x ∈ A, joten g on funktion f k¨aa¨nteisfunktio. 2

65

Huomautus 3.2.13. Olkoot f : A → B bijektio. T¨all¨oin sen k¨a¨anteisfunktio f −1 : B → A on my¨oskin bijektio ja sen k¨a¨anteisfunktio (f −1 )−1 = f. Todistus. M¨a¨aritelm¨an 3.2.10 mukaan funktio g : A → B on funktion f −1 : B → A k¨a¨anteisfunktio, jos f −1 (g(x)) = x kaikilla x ∈ A ja g(f −1 (y)) = y kaikilla y ∈ B. Molemmat ehdot toteutuvat, jos g = f . Siten f on funktion f −1 k¨a¨anteisfunktio. Lauseen 3.2.12 nojalla f −1 on bijektio. 2 Esimerkki 3.2.14. Olkoon f : R → R, f (x) = 3x − 1. Osoitetaan, ett¨a f on bijektio ja etsit¨a¨an sen k¨a¨anteiskuvaus. 1◦ f on injektio: f (x) = f (y) =⇒ 3x − 1 = 3y − 1 =⇒ x = y. Siten ehdosta f (x) = f (y) seuraa aina x = y, eli kuvaus f on injektio. 2◦ f on surjektio: Olkoon t ∈ R mielivaltainen. Halutaan l¨oyt¨a¨a x ∈ R siten, ett¨a f (x) = t. f (x) = t ⇐⇒ 3x − 1 = t ⇐⇒ 3x = t + 1 ⇐⇒ x =

t+1 . 3

Siis f ( t+1 ) = 3( t+1 ) − 1 = t. 3 3 Kohdista 1◦ ja 2◦ seuraa, ett¨a f on bijektio. Siten funktiolla f on k¨a¨anteisfunktio ja se on f −1 : R → R, f −1 (t) =

t+1 , 3

sill¨a 

(t) = f

t+1 3



t+1 ) − 1 = t, 3 (3x − 1) + 1 f −1 ◦ f (x) = f −1 (3x − 1) = = x. 3 f ◦f

−1

= 3(

Huomaa, ett¨a k¨a¨anteisfunktion lauseke l¨oydettiin kuvauksen surjektiivisuuden osoittamisen yhteydess¨a. 66

Esimerkki 3.2.15. Olkoon f : R → R, ( x , jos x 6= 1 f (x) = 1−x −1, jos x = 1.

1◦ Osoitetaan, ett¨a f on injektio. Olkoon x1 , x2 ∈ R siten, ett¨a f (x1 ) = f (x2 ). Osoitetaan, ett¨a x1 = x2 . Huomataan ensin, ett¨a f (1) = −1 ja kaikilla x 6= 1 on f (x) =

1 1 − (1 − x) = − 1 6= −1. 1−x 1−x

T¨aten riitt¨a¨a tutkia tilannetta x1 6= 1 ja x2 6= 1. Koska f (x1 ) = f (x2 ) ja x1 6= 1 6= x2 , niin 1 1 −1= −1 1 − x1 1 − x2

⇔

1 − x1 = 1 − x2

⇔

x1 = x2

Siis f on injektio. 2◦ Osoitetaan, ett¨a f on surjektio. Olkoon y ∈ R. Halutaan l¨oyt¨aa¨ x ∈ R siten, ett¨a f (x) = y. Jos y = −1,

67

niin voidaan valita x = 1. Jos y 6= −1, niin valitaan x =

y y+1

∈ R, koska

f (x) = y 1 −1=y 1−x 1 ⇔ =y+1 1−x 1 ⇔ 1−x= y+1

⇔

⇔

Koska

y y+1

x=1−

1 y = y+1 y+1

6= 1, niin  f

y y+1

y y+1

 =

1−

y y+1

=

y y+1 1 y+1

= y.

Siis f on surjektio. Lauseen 3.2.12 nojalla on olemassa k¨a¨anteisfunktio f −1 : B → A, joka on ( 1 jos y = −1 f −1 (y) = y jos y 6= −1. y+1 Tarkistus: Jos y 6= −1, niin f (f −1 (y)) = f (

y ) = y. y+1

Jos y = −1, niin f (f −1 (−1)) = f (1) = −1. Toisaalta, jos x 6= 1, niin f

−1

(f (x)) = f

−1



x 1−x

 =

x 1−x x + 1−x

1

=

x 1−x 1 1−x

= x.

Jos taas x = 1, niin f −1 (f (1)) = f −1 (−1) = 1. ¨ a sekoita alkukuvaa ja k¨aa¨nteiskuvausta!! Huomautus 3.2.16. Al¨ (i) Jos f : A → B on funktio, niin joukon V ⊂ B alkukuva f {−1} (V ) on aina olemassa, kun taas k¨a¨anteiskuvaus f −1 : B → A on olemassa jos ja vain jos f on bijektio. 68

(ii) Oletetaan, ett¨a f : A → B on bijektio ja olkoon b ∈ B. Jos merkit¨a¨an V = {b} ⊂ B, niin f {−1} (V ) = {f −1 (b)}, ts. joukon V = {b} alkukuva on sama kuin alkion b ∈ B kuvapisteen f −1 (b) muodostama joukko. Lause 3.2.17. Jos f : A → B ja g : B → C ovat bijektioita, niin yhdistetty kuvaus g ◦ f : A → C, (g ◦ f )(x) = g(f (x)) on bijektio, ja sen k¨a¨anteiskuvaus on (g ◦ f )−1 = f −1 ◦ g −1 . Todistus. 1◦ g ◦ f on injektio: Olkoot a1 , a2 ∈ A, a1 6= a2 . T¨all¨oin f :n injektiivisyyden perusteella a1 ja a2 kuvautuvat eri pisteiksi, f (a1 ) 6= f (a2 ), josta taas g:n injektiivisyyden nojalla seuraa g(f (a1 )) 6= g(f (a2 )), eli (g ◦ f )(a1 ) 6= (g ◦ f )(a2 ). Siten g ◦ f on injektio. 2◦ g ◦ f on surjektio: Olkoon c ∈ C. Haluamme l¨oyt¨aa¨ alkion a ∈ A siten, ett¨a (g ◦ f )(a) = c. Koska g : B → C on surjektio, on olemassa b ∈ B siten, ett¨a g(b) = c. Koska f : A → B on surjektio, on olemassa a ∈ A siten, ett¨a f (a) = b. Siten (g ◦ f )(a) = g(f (a)) = g(b) = c. 69

3◦ g ◦ f :n k¨aa¨nteiskuvaus on f −1 ◦ g −1 : Koska f ja g ovat molemmat bijektioita, ovat k¨a¨anteiskuvaukset f −1 : B → A ja g −1 : C → B olemassa. Lis¨aksi niiden yhdistetty kuvaus f −1 ◦g −1 : C → A on hyvin m¨a¨aritelty. K¨a¨anteiskuvauksen m¨a¨aritelm¨an perusteella saamme (g ◦ f ) ◦ (f −1 ◦ g −1 )(c) = (g ◦ f )(f −1 ◦ g −1 (c)) = g(f (f −1 (g −1 (c)))) = g(g −1 (c)) = c kaikille c ∈ C. Vastaavasti (f −1 ◦ g −1 ) ◦ (g ◦ f )(a) = (f −1 ◦ g −1 )(g ◦ f (a)) = f −1 (g −1 (g(f (a)))) = f −1 (f (a)) = a kaikille a ∈ A. Siten g ◦ f :n k¨aa¨nteiskuvaus on f −1 ◦ g −1 . 2

Harjoitusteht¨ avi¨ a 1. Olkoot A = {1, 2, 3, 4} ja B = {a, b, c}. Anna esimerkki funktiosta f : A → B, joka ei ole injektio eik¨a surjektio. 2. Onko funktio f : Z → Z×Z, f (k) = (3k, k−2) injektio? Ent¨a surjektio? 3. Olkoon f : Z × Z → Q, f (m, n) =

m . |n| + 1

(a) M¨aa¨rit¨a alkukuva f {−1} (0). (b) Onko f injektio? (c) Onko f surjektio? 4. Olkoon f : R → R, f (x) = ax + b, miss¨a a, b ∈ R. (a) Mill¨a luvuilla a ja b funktio f on bijektio? (b) Mill¨a luvuilla a ja b p¨atee f = f −1 (ts. funktio f on itsens¨a k¨a¨anteisfunktio)?

70

5. Olkoot a, b ∈ R ja f : ]0, ∞[ → ]0, ∞[, f (x) = b

a x

+ b. Mill¨a luvuilla a ja

(a) f on funktio? (b) f on injektio? (c) f on surjektio? 6. Osoita, ett¨a funktio f : R \ {2} → R \ {5}, f (x) =

5x−1 x−2

on bijektio.

7. Onko funktio f : R2 → R2 , f (x, y) = (xy, x − y) injektio? Ent¨a surjektio? 8. Olkoot f : A → B ja g : B → C funktioita siten, ett¨a yhdistetty funktio (g ◦ f ) : A → C on injektio. (a) Osoita, ett¨a funktion f t¨aytyy olla injektio. (b) Onko my¨os funktion g oltava injektio? 9. Oletetaan, ett¨a yhdistetty funktio g ◦ f : A → C on surjektio. Onko t¨all¨oin funktion g oltava surjektio? Ent¨ap¨a funktion f ? 10. M¨aa¨rit¨a funktion f k¨a¨anteisfunktio tai perustele miksi sit¨a ei ole olemassa kun √ (a) f : [2, ∞[ → [3, ∞[, f (x) = x − 2 + 3. (b) f : Z → Z, f (k) = 6 − k 3 . 11. Onko funktio f : R × N → N × R, f (x, n) = (n, 3nx) bijektio? Jos on, niin mik¨a on sen k¨a¨anteisfunktio? 12. Osoita, ett¨a funktio ( 3 − 2x, kun 0 ≤ x ≤ 1, f : [0, 2] → B, f (x) = x + 4, kun 1 < x ≤ 2, on injektio ja m¨a¨arit¨a joukko B siten, ett¨a f on bijektio. M¨a¨arit¨a my¨os k¨aa¨nteiskuvaus f −1 : B → [0, 2].

71

13. Olkoon

( x + 1, kun x ≤ 0, f : R → R, f (x) = 1 + 3, kun x > 0. x

Onko f bijektio? Jos on, niin mik¨a on sen k¨aa¨nteisfunktio? 14. Anna esimerkki funktiosta (a) f : R → R, joka on surjektio, mutta ei injektio. (b) g : R2 → R2 , joka on injektio, mutta ei surjektio.

72

Luku 4 Joukkojen mahtavuus “The notion of infinity is our greatest friend; it is also the greatest enemy of our peace of mind.” James Pierpont Erilaisten joukkojen kokoa voidaan vertailla monella eri tavalla. Yksi ensimm¨aisen¨a mieleen tulevista tavoista on k¨aytt¨a¨a koon mittaamiseen jou¨ arellisten joukkojen, joissa on siis vain ¨a¨arellikon alkioiden lukum¨a¨ar¨a¨a. A¨ sen monta alkiota, kohdalla t¨allainen vertailu onnistuu helposti, mutta miten on ¨a¨arett¨om¨an monta alkiota sis¨alt¨avien joukkojen laita?

4.1

Yht¨ amahtavuus

Lause 4.1.1. Olkoot A = {a1 , a2 , . . . , ak } ja B = {b1 , b2 , . . . , bm } (miss¨a ai 6= aj jos i 6= j ja bi 6= bj jos i 6= j). T¨all¨oin on olemassa bijektio f : A → B ⇐⇒ m = k. Todistus. ” ⇒ ” Oletus: On olemassa bijektio f : A → B. V¨aite: m = k. Esimerkiss¨a 3.2.3 todettiin, ett¨a joukkojen A ja B v¨alill¨a voi olla injektiivinen kuvaus vain jos k ≤ m. Edelleen Esimerkiss¨a 3.2.7 todettiin, ett¨a A ja B v¨alill¨a voi olla surjektiivinen kuvaus vain jos k ≥ m. Niinp¨a bijektio f : A → B voi olla olemassa vain jos m = k. ” ⇐ ” M¨aa¨ritell¨a¨an funktio f : A → B asettamalla f (ai ) = bi . Koska m = k ja ai 6= aj jos i 6= j, kyseess¨a todella on funktio. Lis¨aksi f on injektio, koska bi 6= bj jos i 6= j, ja surjektio, koska m = k. 2 73

M¨ a¨ aritelm¨ a 4.1.2. Joukot A ja B ovat yht¨a mahtavia, merkit¨a¨an |A| = |B|, jos on olemassa bijektio f : A → B. M¨ a¨ aritelm¨ a 4.1.3. Joukko A on ¨a¨arellinen, jos A = ∅ tai A on yht¨a mahtava kuin joukko {1, 2, . . . , n} jollakin n ∈ N. T¨all¨oin merkit¨a¨an |A| = n (vastaavasti |∅| = 0). Jos joukko A ei ole ¨a¨arellinen, se on ¨a¨aret¨on. Huomautus 4.1.4. Huomautuksen 3.2.13 nojalla on olemassa bijektio f : A → B jos ja vain jos on olemassa bijektio g : B → A. Siten osoitettaessa joukkoja A ja B yht¨a mahtaviksi riitt¨a¨a l¨oyt¨a¨a bijektio “jompaan kumpaan suuntaa”. Esimerkki 4.1.5. (a) Joukot A = {a1 , a2 , . . . , ak } ja B = {b1 , b2 , . . . , bm } (miss¨a ai 6= aj jos i 6= j ja bi = 6 bj jos i 6= j) ovat yht¨a mahtavia jos ja vain jos m = k. (b) Joukot N = {1, 2, 3, . . .} ja N \ {1} = {2, 3, . . .} ovat yht¨a mahtavia, sill¨a funktio f : N → N \ {1}, f (n) = n + 1 on bijektio. (c) joukot N ja Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .} ovat yht¨a mahtavia. Todistus. V¨aitteen todistamiseksi riitt¨a¨a l¨oyt¨a¨a bijektio f : N → Z. M¨a¨aritell¨a¨an t¨allainen kuvaus seuraavan kaavion avulla: n 1 2 f (n) 0 1

3 4 5 6 7 8 9 ... -1 2 -2 3 -3 4 -4 . . .

Kuvauss¨aa¨nt¨on¨a on siis ( f (n) =

n , 2 − n−1 , 2

jos n on parillinen, jos n on pariton.

Funktion m¨a¨arittelyst¨a on ilmeist¨a, ett¨a se on sek¨a injektio ett¨a surjektio, mutta todistetaan t¨am¨a kuitenkin harjoituksen vuoksi. 1◦ f on injektio: Olkoot n, m ∈ N siten, ett¨a f (n) = f (m). Haluamme osoittaa, ett¨a n = m. Huomataan ensin, ett¨a koska f (k) < 0 kaikilla parittomilla k ja f (k) ≥ 0 kaikilla parillisilla k, niin ehto f (n) = f (m) voi toteutua vain jos n ja m ovat joko molemmat parillisia tai molemmat parittomia. Jos n ja m ovat molemmat parillisia, seuraa ehdosta f (n) = f (m) ett¨a n2 = m2 , eli on oltava n = m. Vastaavasti jos sek¨a n ett¨a m ovat parittomia, 74

saadaan − n−1 = − m−1 , josta my¨os seuraa n = m. N¨ain ollen f on 2 2 injektio. 2◦ f on surjektio: Olkoon b ∈ Z mik¨a tahansa. Haluamme l¨oyt¨a¨a luonnollisen luvun n ∈ N siten, ett¨a f (n) = b. Jos b = 0, voidaan valita n = 1. Jos b > 0, valitaan n = 2b ∈ N, jolloin = b. Jos taas b < 0, (koska n¨ain valittu n on parillinen) f (n) = n2 = 2b 2 niin valitaan n = 1 − 2b. Koska b < 0 ja b ∈ Z, niin 1 − 2b ∈ N. Lis¨aksi 1 − 2b on pariton (Miksi?), joten f (n) = f (1 − 2b) = − (1−2b)−1 = b. 2 N¨ain ollen kaikissa mahdollisissa tapauksissa on luvulle b ∈ Z l¨oydetty n ∈ N siten, ett¨a f (n) = b. N¨ain ollen f on surjektio. 2 (d) Reaalilukujen joukko R ja v¨ali ]0, ∞[ ovat yht¨a mahtavia, sill¨a esimerkiksi funktio f : R → ]0, ∞[, f (x) = 2x on bijektio. Lis¨aksi v¨alit ]0, ∞[ 1 ja ]0, 1[ ovat yht¨a mahtavia, sill¨a funktio g : ]0, ∞[→ ]0, 1[, g(x) = x+1 on bijektio. Niinp¨a my¨os R ja ]0, 1[ ovat yht¨a mahtavia. Edellisess¨a esimerkiss¨a huomattiin, ett¨a ¨a¨aret¨on joukko voi olla yht¨a mahtava aidon osajoukkonsa kanssa. Itse asiassa p¨atee Lause 4.1.6. Joukko A on a¨a ¨ret¨on jos ja vain jos se on yht¨a mahtava aidon osajoukkonsa kanssa, toisin sanoen on olemassa A0 ⊂ A siten, ett¨a A0 6= A ja |A0 | = |A|. Todistus. Sivuutetaan. 2 M¨ a¨ aritelm¨ a 4.1.7. Joukko A on numeroituva, jos se on ¨a¨arellinen tai yht¨a mahtava kuin N. Jos joukko A ei ole numeroituva, se on ylinumeroituva. Huomautus 4.1.8. Jos halutaan korostaa, ett¨a numeroituvassa joukossa A on ¨a¨arett¨om¨an monta eri alkiota, voidaan k¨aytt¨a¨a ilmaisua “A on numeroituvasti ¨a¨aret¨on”. Edellisen esimerkin perusteella joukot N \ {1} ja Z ovat numeroituvasti ¨a¨arett¨omi¨a. Lause 4.1.9. Rationaalilukujen joukko Q on numeroituva. Todistus. V¨aitteen todistamiseksi tulee l¨oyt¨a¨a bijektio f : N → Q. T¨at¨a varten taulukoidaan rationaaliluvut seuraavasti: 0 1 1 1 2 1 3 1 4 1

−1 1 −2 1 −3 1 −4 1

1 2 2 2 3 2

−1 2 −2 2 −3 2

1 3 2 3

−1 3 −2 3

1 4

−1 4

.. .

.. .

.. .

.. .

.. .

.. .

.. .

.. .

75

..

.

Yll¨a siis ensimm¨aisell¨a rivill¨a ovat ne muotoa pq (miss¨a p ∈ Z ja q ∈ N) olevat rationaaliluvut, joille |p| + q = 1, toisella rivill¨a luvut joille |p| + q = 2, ja niin edelleen. Kullekin riville tulee ¨a¨arellinen m¨a¨ar¨a lukuja1 ja rivej¨a on yht¨a paljon kuin on luonnollisia lukuja. T¨am¨an kaksiulotteisen taulukon alkiot voidaan asettaa jonoon siten, ett¨a ensin listataan ensimm¨aisen rivin alkiot, sitten toisen, sen j¨alkeen kolmannen ja niin edelleen. Saadaan siis jono 0 1

−1 1

1 1

−2 1

2 1

−1 2

1 2

3 1

−3 1

2 2

−2 2

1 3

−1 3

...

T¨ass¨a jonossa esiintyv¨at kaikki rationaaliluvut, osa useamman kerran (sill¨a 1 = 22 ). Poistamalla siit¨a luvut, jotka ovat jo esiintyneet jonossa aiemmin, 1 voidaan etsitty bijektio f : N → Q muodostaa seuraavan kaavion avulla: n

1

2

3

4

5

6

7

8

9

10

11

...

f (n)

0 1

1 1

−1 1

2 1

−2 1

1 2

−1 2

3 1

−3 1

1 3

−1 3

...

N¨ain ollen Q on yht¨a mahtava kuin N, eli Q on numeroituva. 2 Lause 4.1.10. Reaalilukujen joukko R on ylinumeroituva. Todistus. V¨aitteen todistamiseksi on n¨aytett¨av¨a, ett¨a R ei ole numeroituva. T¨am¨a on luontevaa tehd¨a ep¨asuoraa p¨aa¨ttely¨a k¨aytt¨aen: Antiteesi: R on numeroituva. Antiteesin nojalla on siis olemassa bijektio f : N → R. Erityisesti f on surjektio, joten R = f (N) = {f (n) : n ∈ N} = {f (1), f (2), f (3), . . .}. T¨am¨a tarkoittaa siis sit¨a, ett¨a lukujono f (1) f (2) f (3) f (4) f (5) f (6) . . . pit¨aa¨ sis¨all¨a¨an kaikki reaaliluvut. Esitet¨a¨an luvut f (n) desimaalilukuina seuraavin merkinn¨oin: f (n) = dn1 .dn2 dn3 dn4 . . . Yll¨a siis dn1 ∈ Z on luvun f (n) kokonaisosa, dn2 ∈ {0, 1, . . . , 9} edustaa luvun f (n) kymmenesosia, dn3 ∈ {0, 1, . . . , 9} luvun f (n) sadasosia ja niin edelleen. Esimerkiksi jos olisi f (3) = 17.782567 . . ., niin d31 = 17, d32 = 7, d33 = 8, d34 = 2, . . .. Tai jos olisi f (5) = 4.12, niin d51 = 4, d52 = 1, d53 = 2 ja d5k = 0 kaikilla k ≥ 4. Nyt siis mik¨ali antiteesi on totta, l¨oytyv¨at kaikki reaaliluvut listasta 1

Osaatko laskea kuinka monta lukua tulee n:lle riville?

76

f (1) d11 .d12 d13 d14 d15 . . . f (2) d21 .d22 d23 d24 d25 . . . f (3) d31 .d32 d33 d34 d35 . . . f (4) d41 .d42 d43 d44 d45 . . . .. .. . . Konstruoidaan seuraavaksi reaaliluku b = b0 .b1 b2 b3 . . ., jota yll¨a olevasta listasta ei l¨oydy. Valitaan ensin b0 ∈ Z siten, ett¨a b0 = d11 + 2. T¨am¨a valinta varmistaa, ett¨a b0 .b1 b2 b3 . . . 6= d11 .d12 d13 d14 d15 . . . eli b 6= f (1), riippumatta siit¨a, mit¨a lukuja desimaalit b1 , b2 , . . . ovat. Valitaan seuraavaksi b1 ∈ {0, 1, 2, . . . , 9} siten, ett¨a ( 2, jos d22 6= 2, b1 = 3, jos d22 = 2. T¨am¨a valinta varmistaa, ett¨a b 6= f (2), riippumatta siit¨a, mit¨a lukuja desimaalit b2 , b3 , . . . ovat. Seuraavaksi valitaan ( 2, jos d33 6= 2, b2 = 3, jos d33 = 2, jolla varmistetaan, ett¨a b 6= f (3). N¨ain jatketaan. Jokaiselle k ∈ N valitaan ( 2, jos dkk 6= 2, bk = 3, jos dkk = 2, N¨ain l¨oydet¨a¨an reaaliluku b siten, ett¨a b 6= f (n) kaikilla n ∈ N eli b ∈ / f (N). N¨ain ollen R 6= f (N) eli funktio f : N → R ei olekaan surjektio. Niinp¨a antiteesi on ep¨atosi ja v¨aitteen on oltava totta. 2 Huomautus 4.1.11. Reaalilukujen ja desimaalikehitelmien v¨alill¨a ei ole yksik¨asitteist¨a vastaavuutta, sill¨a esimerkiksi reaaliluvulla 1 on desimaalikehitelm¨at 1.0000 . . . ja 0.99999 . . .. Siksi yll¨a olevassa todistuksessa on lukujen bk valinnassa tarkoituksella v¨altetty desimaaleja 0 ja 9. Lause 4.1.12. Irrationaalilukujen joukko R \ Q on ylinumeroituva. Todistus. Todistetaan t¨am¨akin v¨aite ep¨asuoraa p¨a¨attely¨a k¨aytt¨aen. Antiteesi: R \ Q on numeroituva. T¨all¨oin on siis olemassa bijektio f : N → R \ Q, eli erityisesti (koska f on surjektio) R \ Q = {f (1), f (2), f (3), . . .}. 77

Koska rationaalilukujen joukko Q tiedet¨a¨an numeroituvaksi, on olemassa bijektio g : N → Q, jolloin siis Q = {g(1), g(2), g(3), . . .}. Mutta koska R = Q ∪ (R \ Q), niin t¨am¨a tarkoittaa sit¨a, ett¨a reaaliluvut voidaan j¨arjest¨a¨a jonoon: R = {f (1), g(1), f (2), g(2), f (3), g(3), . . .} Mutta Lauseen 4.1.10 nojalla t¨am¨a on mahdotonta, joten antiteesin t¨aytyy olla ep¨atosi. 2 Huomautus 4.1.13. Yll¨a olevan todistuksen sis¨all¨a tehty p¨a¨attely n¨aytt¨a¨a itse asiassa, ett¨a mink¨a tahansa kahden numeroituvan joukon yhdiste on sekin numeroituva.

4.2

Mahtavuuksien vertailua

Mahtavuuksien vertailussa ei tarvitse rajoittua numeroituvuuden ja ylinumeroituvuuden k¨asitteisiin. M¨ a¨ aritelm¨ a 4.2.1. Olkoot A ja B mit¨a tahansa joukkoja. T¨all¨oin 1. joukot A ja B ovat yht¨a mahtavia, merkit¨a¨an |A| = |B|, jos on olemassa bijektio f : A → B. 2. joukko A on aidosti mahtavampi kuin joukko B, merkit¨a¨an |A| < |B|, jos on olemassa injektio f : A → B, mutta ei surjektiota g : A → B. Esimerkki 4.2.2. |N| < |R|, sill¨a f : N → R, f (n) = n on injektio ja osoitettaessa, ett¨a R on ylinumeroituva todistettiin, ett¨a ei ole olemassa surjektiota g : N → R. Nyt on luonnollista kysy¨a, onko olemassa joukkoa X, jolle olisi |R| < |X|? Ensimm¨aisen¨a mieleen voisi tulla, ett¨a esimerkiksi R2 olisi aidosti mahtavampi kuin R, mutta n¨ain ei kuitenkaan ole: joukot R ja R2 ovat yht¨amahtavia. Todistamme seuraavaksi t¨am¨an v¨aitteen yksinkertaisemman version. Lause 4.2.3. Joukot ]0, 1[ ja ]0, 1[ × ]0, 1[ ovat yht¨amahtavia Todistus. M¨aa¨ritell¨a¨an funktio f : ]0, 1[ → ]0, 1[ × ]0, 1[ siten, ett¨a f (0.x1 x2 x3 x4 x5 x6 . . .) = (0.x1 x3 x5 . . . , 0.x2 x4 x6 . . .).

78

Funktio f on injektio, sill¨a jos 0.x1 x2 x3 x4 x5 x6 . . . 6= 0.y1 y2 y3 y4 y5 y6 . . ., niin (0.x1 x3 x5 . . . , 0.x2 x4 x6 . . .) 6= (0.y1 y3 y5 . . . , 0.y2 y4 y6 . . .). Funktio f on surjektio, sill¨a jos (0.u1 u2 u3 . . . , 0.v1 v2 v3 . . .) ∈ ]0, 1[×]0, 1[, niin f (0.u1 v1 u2 v2 u3 v3 . . .) = (0.u1 u2 u3 . . . , 0.v1 v2 v3 . . .). 2 Reaalilukujen joukkoa aidosti mahtavampia joukkoja etsitt¨aess¨a tarvitaan pontenssijoukon k¨asitett¨a. M¨ a¨ aritelm¨ a 4.2.4. Joukon A potenssijoukko on joukko P(A) = {A0 : A0 ⊂ A}, toisin sanoen P(A) on joukon A kaikkien osajoukkojen muodostama joukko. Esimerkki 4.2.5. Jos A = {1, 2, 3}, niin P(A) = {∅, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, A}. Esimerkin 4.2.5 joukossa A on 3 alkiota, ja sen potenssijoukossa P(A) alkioita on 8 = 23 . T¨am¨a ei ole suinkaan ole sattumaa: Lause 4.2.6. Olkoon S joukko, jolle |S| = n. T¨all¨oin |P (S)| = 2n Todistus. Induktio luvun n suhteen: 1◦ Alkuaskel n = 1: T¨all¨oin joukossa S on vain yksi alkio, S = {x} ja P(S) = {∅, {x}}, joten |P (S)| = 2 = 21 . 2◦ Induktioaskel: Oletetaan, ett¨a jos S on mik¨a tahansa joukko, jolle |S| = k, niin |P (S)| = 2k . Pit¨a¨a osoittaa, ett¨a jos |S| = k + 1, niin |P (S)| = 2k+1 . Olkoon S joukko, jolle |S| = k + 1, ja olkoon x ∈ S mik¨a tahansa. Merkit¨aa¨n S 0 = S \ {x}. T¨all¨oin |S 0 | = k, joten induktio-oletuksen nojalla |P (S 0 )| = 2k . Olkoot A1 , A2 , . . . , A2k joukon S 0 osajoukot. T¨all¨oin joukon S = S 0 ∪ {x} osajoukot ovat A1 , A2 , . . . , A2k , A1 ∪ {x}, A2 ∪ {x}, . . . , A2k ∪ {x}. N¨ain ollen joukon S osajoukkoja on 2k + 2k = 2k+1 kappaletta, eli |P(S)| = 2k+1 . 2 79

Lause 4.2.7. Jokaiselle joukolle A p¨atee |A| < |P(A)|. Todistus. Osoitetaan ensin, ett¨a on olemassa injektio f : A → P(A). M¨a¨aritell¨aa¨n f : A → P(A), f (x) = {x}. T¨all¨oin, jos f (x) = f (y) eli {x} = {y}, niin on oltava x = y. Siisp¨a f on injektio. Pit¨aa¨ osoittaa viel¨a, ett¨a ei ole olemassa surjektiota g : A → P(A). Tehd¨a¨an t¨am¨a ep¨asuoralla p¨a¨attelyll¨a. Antiteesi: On olemassa surjektio g : A → P(A). Antiteesin kumoamiseksi pit¨a¨a l¨oyt¨a¨a alkio B ∈ P(A) (siis osajoukko B ⊂ A) siten, ett¨a g(x) 6= B kaikilla x ∈ A. Valitaan B = {x ∈ A : x ∈ / g(x)}. Antiteesin mukaan g on surjektio, joten on olemassa xˆ ∈ A siten, ett¨a g(ˆ x) = B. Nyt kuitenkin p¨atee • jos xˆ ∈ B, niin joukon B m¨aa¨ritelm¨an nojalla xˆ ∈ / g(ˆ x) = B, ristiriita. • jos xˆ ∈ / B, niin joukon B m¨aa¨ritelm¨an nojalla xˆ ∈ g(ˆ x) = B, ristiriita. Siten surjektiota g : A → P(A) ei voi olla olemassa. 2 Edell¨a todistetun lauseen nojalla siis |R| < |P(R)| < |P(P(R))| < . . . , joten “maailman mahtavinta joukkoa” ei ole olemassa. Luonnollisiin lukuihin ja reaalilukuihin liittyen tiedet¨a¨an, ett¨a |N| < |R|, ja lis¨aksi voidaan osoittaa, ett¨a R ja P(N) ovat yht¨a mahtavia. Voidaan kuitenkin viel¨a kysy¨a, onko olemassa joukkoa A, jolle p¨atisi |N| < |A| < |R|? Cantor esitti (n. 1880) konjektuurin, ett¨a t¨allaista joukkoa A ei ole olemassa. Konjektuuri tunnetaan nimell¨a “kontinuumihypoteesi”. Kurt G¨odel osoitti vuonna 1940, ett¨a kontinuumihypoteesi¨a ei voida todistaa v¨a¨ar¨aksi ns. Zermelon-Frankelin aksiomaattisessa joukko-opissa vaikka mukaan liitett¨aisiin valinta-aksiooma. Paul Cohen osoitti puolestaan vuonna 1963 ettei kontinuumihypoteesi¨a voida my¨osk¨a¨an todistaa oikeaksi. Siten kontinuumihypoteesi on riippumaton valinta-aksioomalla laajennetusta Zermelon-Fraenkelin joukko-opista.

80

Harjoitusteht¨ avi¨ a 1. Olkoon A = {. . . , 14 , 21 , 1, 2, 4, 8, . . .}. (a) Kirjoita joukko A muodossa A = {x : P (x)}. (b) Osoita, ett¨a A on yht¨a mahtava kuin Z. 2. Osoita, ett¨a joukot N ja N × N ovat yht¨a mahtavia.

81