Tehtävä:
Joukko-opin alkeet

Lyhyt MathCheck-ohje (uuteen välilehteen)

Joukot ovat työkalu, jolla matematiikassa ja tietojen­käsittelytieteessä rakennetaan uusia käsitteitä. Joukko-opin alkeet ovat välttämättömät monien muiden asioiden, kuten erityyppisten relaatioiden sekä verkkojen ymmärtämiselle.

Joukko on kokoelma alkioita. Alkiot voivat tilanteesta riippuen olla melkeinpä mitä tahansa. Usein ne ovat lukuja, merkkejä, lukupareja tai merkkijonoja. Ne voivat myös olla toisia joukkoja. Yhden alkion joukko ja sen alkio ovat eri asioita.

On tavallista ilmaista äärellinen joukko luettelemalla sen alkiot aaltosulkeiden välissä, esimerkiksi {2, 5, 8, 11, 14}. Luettelointijärjestyksellä ei ole väliä. Ei ole väliä esiintyykö alkio luettelossa yhden vai useamman kerran; ainoa mikä merkitsee on, esiintyykö se ainakin kerran vai ei yhtään kertaa. Niinpä {6, 5, 5, 3, 6} on sama joukko kuin {3, 5, 6} eli {6, 5, 5, 3, 6} = {3, 5, 6}.

Mitkä alla luetelluista joukoista ovat sama joukko kuin {2, 5, 6}?
{256}
{2, 3, 4, 5, 6}
{6, 5, 2}
{2, 2, 5, 2}
{5, 2, 2, 6, 2, 6}
{{2}, {5}, {6}}
tai

Tyhjää joukkoa eli joukkoa, jossa ei ole yhtään alkiota, voitaisiin merkitä {} (ja jotkut merkitsevätkin), mutta tapana on merkitä sitä ∅. Luetteloinnissa voidaan käyttää kolmea pistettä … silloin, kun lukijalle on selvää, mitä alkioita ne edustavat.

Joukon `A` alkioiden määrää merkitään `|A|`. Ilmoita seuraavat joukkojen alkioiden määrät.

|{1, 0, 2, 0}| = tai
|{1, 9, 3, 7, 5, 5, 7, 3, 1}| = tai
|∅| = tai
|{0, 1, 2, …, 9}| = tai

Jos emme tiedä, mitä lukuja `x`, `y`, `z` ja `t` edustavat, niin `<= |{x,y,z,t}| <=`. (Anna mahdollisimman tiukat rajat.) tai

Alkion `a` kuuluminen joukkoon merkitään `a in A` ja sen vastakohta on `a notin A`. Valitse todet väitteet.
2 ∈ {3,1,4,9,5}
5 ∈ {3,1,4,9,5}
145 ∈ {3,1,4,9,5}
{3} ∈ {3,1,4,9,5}
7 ∉ {3,1,4,9,5}
9 ∉ {3,1,4,9,5}
tai

Joukko `A` on joukon `B` osajoukko, merkitään `A sube B`, jos ja vain jos jokainen `A`:n alkio on myös `B`:n alkio. Niinpä jokainen joukko on itsensä osajoukko, eli `A sube A` pätee jokaiselle joukolle `A`. Jos `A sube B` ja `B sube A`, niin `A = B`.

Jos ja vain jos `A sube B` ja `A ne B`, niin `A` on `B`:n aito osajoukko. Se merkitään `A sub B`. Tällöin on olemassa jokin `b` siten, että `b in B` ja `b notin A`, mutta ei ole olemassa jotain `a` siten, että `a in A` ja `a notin B`.

Joillakin matematiikan osa-alueilla käytetään symbolia ⊂ siinä merkityksessä missä muut käyttävät ⊆. Jostain syystä niissäkään ei käytetä symbolia < siinä merki­tyksessä missä muut käyttävät ≤.

Valitse todet väittämät.
`3 sube {3,1,4,9,5}`
`{3} sube {3,1,4,9,5}`
`{3} sub {3,1,4,9,5}`
`{3,1,4,9,5} sube {3,1,4,9,5}`
`{3,1,4,9,5} sub {3,1,4,9,5}`
tai

Valitse todet väittämät.
jokaisella `a` pätee `a in O/`
jokaisella `a` pätee `a notin O/`
jokaisella `A` pätee `O/ sube A`
jokaisella `A` pätee `O/ sub A`
millään `A` ei päde `A sube O/`
millään `A` ei päde `A sub O/`
tai

Kuinka monta osajoukkoa on seuraavilla joukoilla?

tai
{7} tai
{19, 22} tai
{65, 56, 55} tai
`{1, 2, …, n}` tai

Kuinka monta aitoa osajoukkoa on joukolla, jossa on `k` alkiota?
tai

Kolmea pistettä käytetään usein myös esittämään päätty­mätöntä jonoa alkioita. Esimerkkejä:

Muita tärkeitä lukujoukkoja ovat `QQ` eli rationaalilukujen joukko, eli kaikki ne luvut, jotka voidaan esittää murtolukuna `m/n`, missä `m in ZZ` ja `n in ZZ^+`; sekä `RR` eli reaalilukujen joukko, eli kaikki lukusuoran luvut. Jokainen rationaaliluku on reaaliluku mutta ei toisinpäin, eli `QQ sub RR`. Merkinnät `QQ^+` ja `RR^+` tarkoittavat positiivisten rationaalilukujen joukkoa ja positiivisten reaalilukujen joukkoa, ja `QQ^(-)` ja `RR^(-)` vastaavasti negatiivisten.

Valitse ne tapaukset, joissa vasemman reunan joukko on ylärivin joukon osajoukko. Kohtia on paljon, mutta niitä napsuttelee nopeasti. Vihje: lukuunottamatta `NN`:n riviä ja saraketta, taulukkoon syntyy kuvio joka toistuu monta kertaa. Mieti siis `NN` huolellisesti (`NN` on osapuoli kaikkiaan 5 tapauksessa), ja mieti vaikka `ZZ`:n, `ZZ^+`:n ja `ZZ^(-)`:n avulla minkälainen kuvio toistuu.
`sube``NN` `ZZ``ZZ^+``ZZ^(-)` `QQ``QQ^+``QQ^(-)` `RR``RR^+``RR^(-)`
`NN`
`ZZ`
`ZZ^+`
`ZZ^(-)`
`QQ`
`QQ^+`
`QQ^(-)`
`RR`
`RR^+`
`RR^(-)`
tai

Usein joukko ilmaistaan muodossa `{a | sf"ehto"}` tai `{a in A | sf"ehto"}`. Se tarkoittaa niiden alkioiden joukkoa, jotka toteuttavat annetun ehdon ja jälkimmäisessä tapauk­sessa myös kuuluvat joukkoon `A`. Siis `x in {a | sf"ehto"}` jos ja vain jos `x` toteuttaa annetun ehdon. Esimerkiksi

`QQ^+ = { x in Q | x > 0 }`

Ilmausta `{ a | sf"ehto"}` saa käyttää vain silloin, kun on sovittu jokin joukko, jonka alkioita kaikki tarkasteltavat alkiot ovat (ja joka siis voisi olla `A`:n paikalla).

Syy tähän rajoitukseen on ristiriita, joka syntyy kirjoittamalla `{a | a notin a}`. Annetaan tälle nimi `R`, siis `R``=``{a | a notin a}`. Päteekö `R in R`? Se pätee jos ja vain jos `R`:n ehto `a notin a` toteutuu kun `a`:n paikalla on `R`, eli jos ja vain jos `R notin R`. Siis `R in R` jos ja vain jos `R notin R`! Tämä ongelma tunnetaan Russellin paradoksina Bertrand Russellin kunniaksi, joka keksi sen vuonna 1901. Jotkut muutkin keksivät sen samoihin aikoihin.

Seuraavat joukko-operaattorit voidaan määritellä helposti propositiologiikan operaattoreiden avulla:

Siis `A cup B` sisältää kaikki `A`:n alkiot ja kaikki `B`:n alkiot, mutta se ei vastaa sanaa ”ja” vaan sanaa ”tai”, koska alkio kuuluu siihen jos ja vain jos se kuuluu `A`:han tai `B`:hen. Vastaaavasti `A cap B` sisältää kaikki ne alkiot, jotka ovat sekä `A`:ssa että `B`:ssä, ja `A setminus B` kaikki ne, jotka ovat `A`:ssa mutta ei `B`:ssä.

Olkoon `A = {2,4,5,8,9}` ja `B = {3,5,7,8}`. Ilmaise valinnoilla seuraavat joukot.
012345 6789
`A cup B`
`A cap B`
`A setminus B`
`B setminus A`
tai

Valitse oikeat vaihtoehdot.
Edellä olisi pitänyt valita jotkin ruudut kahteen kertaan. MathCheck toimi väärin kun se ei antanut tehdä niin.
Alkio vain kuuluu joukkoon tai ei kuulu. Ei ole niin että on eri asia, kuuluuko se sinne yhdesti vai kahdesti. Siksi MathCheck toimi oikein.
Tiesin, että alkiota ei tarvitse merkitä joukkoon kahdesti, vaikka se tulisi mukaan sekä `A`:sta että `B`:stä.
Jokainen joukon `A cup B` alkio kuuluu täsmälleen yhteen joukoista `A cap B`, `A setminus B` ja `B setminus A`.
tai

Merkitsemme `n = |A|`, `m = |B|` ja `l = |A cap B|`. Näillä pätee `|A cup B| =` ja `|A setminus B| =`.
tai

Koska alkio kuuluu ehdolla määriteltyyn joukkoon jos ja vain jos se toteuttaa ko. ehdon, saamme kolme helppoa lakia:

Unionia, leikkausta ja erotusta koskevia lakeja on helppo johtaa näiden lakien ja propositiologiikan avulla. Johdamme malliksi toisen de Morganin laeista.

`x in A setminus (B cup C)`
(1)`hArr` `x in A ^^ x notin B cup C`
(2)`hArr` `x in A ^^ not(x in B cup C)`
(3)`hArr` `x in A ^^ not(x in B vv x in C)`
(4)`hArr` `x in A ^^ (not(x in B) ^^ not(x in C))`
(5)`hArr` `x in A ^^ x notin B ^^ x notin C`
(6)`hArr` `(x in A ^^ x notin B) ^^ (x in A ^^ x notin C)`
(7)`hArr` `x in A setminus B ^^ x in A setminus C`
(8)`hArr` `x in (A setminus B) cap (A setminus C)`

Mitä alla lueteltuja lakeja tämän päättelyn eri askelissa sovellettiin?
123456 78
jokin em. kolmesta helposta
`x notin X hArr not(x in X)`
logiikan de Morgan
`P ^^ P hArr P`
tai

Olemme osoittaneet mielivaltaiselle alkiolle `x`, että se kuuluu joukkoon `A setminus (B cup C)` jos ja vain jos se kuuluu joukkoon `(A setminus B) cap (A setminus C)`. Niinpä näillä kahdella joukolla on samat alkiot, eli `A setminus (B cup C)``=``(A setminus B) cap (A setminus C)`.

Seuraava tärkeä joukko-opin operaattori on tulojoukko eli karteesinen tulo `A xx B`. Sen alkiot ovat ne parit `(a,b)`, joille `a in A` ja `b in B`. Siis

`A xx B = { (x,y) | x in A ^^ y in B }`

Esimerkiksi {1, 2} × {3, 4, 5} =

{(1,3),(1,4),(1,5),
(2,3),(2,4),(2,5)}

Voidaan myös kertoa kolme tai useampia joukkoja. Esimerkiksi `A xx B xx C xx D` koostuu nelikoista `(a,b,c,d)`, missä `a in A`, `b in B`, `c in C` ja `d in D`. Merkintä `A^2` tarkoittaa `A xx A`, `A^3 = A xx A xx A` jne. Niinpä tuttu `x`-`y`-koordinaatisto esittää joukon `RR^2`.

Seuraavissa tehtävissä valitse joukon alkiot.

`{(x,y) in {0,1,2}^2 | x < y }`
(0, 0)(0, 1)(0, 2)(1, 0)(1, 1) (1, 2)(2, 0)(2, 1)(2, 2)
tai

`{(x,y) in {0,1,2}^2 | x y = 0 vv x(y-2) = 0 }`
(0, 0)(0, 1)(0, 2)(1, 0)(1, 1) (1, 2)(2, 0)(2, 1)(2, 2)
tai

`{(x,y) in {0,1,2}^2 | (x^2 + 1) mod 3 = y }`
(0, 0)(0, 1)(0, 2)(1, 0)(1, 1) (1, 2)(2, 0)(2, 1)(2, 2)
tai

Jos `|A| = n`, `|B| = m` ja `|C| = k`, niin kuinka paljon on `|A xx B xx C|`?
tai

Moni tärkeä matematiikan käsite perustuu tulojoukkoihin, kuten relaatio ja funktio. Ohjelmoinnissa tulojoukot vastaavat tietueita, aliohjelmien parametrilistoja ja ylipäätään kaikkea, missä (mahdollisesti erityyppisiä) olentoja kootaan kiinteän mittaisiksi rakenteiksi. Mutta emme ahnehdi kaikkea kerralla, vaan lopetamme tällä kertaa tähän ja jatkamme toiste.