Lähdekoodi sivulle Diskreetti matematiikka/Joukko-oppi

Ongelmia ratkaistaessa täytyy usein käsitellä matemaattisia kohteita. Esimerkiksi jos sinulta kysytään, kuinka paljon on kaksi kertaa kolme, saatat osoittaa kuutosta. Kun esität useita kohteita samalla kertaa, osoitat kohteiden joukkoa.
Jos haluat esittää neljä ensimmäistä numeroa, saatat kirjoittaa:

<math>\!\, \{1, 2, 3, 4\} \mbox{, } \{3, 2, 4, 1\} \mbox{, tai } \{1, 2, 2, 2, 3, 4\} </math>

Koska kaikki kolme esitystapaa osoittavat samoihin matemattisiin kohteisiin, ne ovat kaikki sama joukko. Huomaa, että joukot pitävät sisällään vain sen, mihin osoitetaan, ei sitä kuinka monta kertaa johonkin osoitetaan tai että missä järjestyksessä.

== Joukkojen suhteet ==

On olemassa monia usein käytettyjä lauseita joukoista:

* Alkio on joukossa; joukko osoittaa siihen
*: <math>\!\, 4 \isin \{1, 2, 3, 4\}</math>
* Kaksi joukkoa ovat yhtenevät; molemmat osoittavat samoihin alkioihin
*: <math>\!\, \{1, 2, 3, 4\} = \{3, 2, 4, 1\}</math>
* Joukko on toisen joukon ylijoukko; se osoittaa kaikkiin toisen joukon alkioihin, ehkä useampaankin
*: <math>\!\, \{1, 2, 3, 4\} \supseteq \{1, 2, 3\} \mbox{ ja } \{1, 2, 3, 4\} \supseteq \{1, 2, 3, 4\}</math>
* Joukko on on toisen joukon aito ylijoukko; se osoittaa kaikkiin toisen joukon alkioihin, mutta aina myös muihin sen lisäksi
*: <math>\!\, \{1, 2, 3, 4\} \supset \{1, 2, 3\} </math>
* Osajoukko ja aito osajoukko -suhteet ovat vastakkaiset verrattuna ylijoukko ja aitoylijoukko -suhteisiin
*: <math>\!\, \{1, 2, 3, 4\} \subseteq \{1, 2, 3, 4\} \mbox{ ja } \{1, 2, 3\} \subset \{1, 2, 3, 4\}</math>

Symboli &sub; näyttää ja toimii samalla tavalla kuin &lt;. Symbolit &isin; ja &lt; näyttävät samanlaisilta, mutta älä kuitenkaan sekoita niitä keskenään.

== Joukko-operaatiot ==

On olemassa monta tapaa yhdistää kaksi joukkoa kolmanneksi joukoksi:
* Voimme muodostaa yhdistejoukon
*: <math>\!\, \{1, 2, 3, 4\} \cup \{2, 4, 6, 8\} = \{1, 2, 3, 4, 6, 8\} </math>
* Voimme muodostaa leikkausjoukon
*: <math>\!\, \{1, 2, 3, 4\} \cap \{2, 4, 6, 8\} = \{2, 4\} </math>
* Voimme muodostaa erotusjoukon
*: <math>\!\, \{1, 2, 3, 4\} \mbox{ }\mathcal{n}\mbox{ } \{2, 4, 6, 8\} = \{1, 3\} \mbox{ tai } \{1, 2, 3, 4\} - \{2, 4, 6, 8\} = \{1, 3\} </math>

&cup; symboli näyttää kupilta, joka voi pitää sisällään paljon asioita. &cap; symboli näyttää ylitsevuotavalta kupilta, joka ei pysty pitämään sisällään paljon asioita. Älä sekoita symboleita keskenään.

== Joukot omine symboleineen ==

Monia joukkoja käytetään niin usein, että niille on annettu omat erityiset symbolit.

* Tyhjä joukko ilmaisee, ettemme osoita mihinkään objekteihin; tällainen joukko ei pidä sisällään yhtään objektia
*: <math>\!\, \empty = \{ \} </math>
* Luonnollisten lukujen joukko
*: <math>\!\, \mathbb{N} = \{0, 1, 2, 3, \ldots\} </math>
* Kokonaislukujen joukko
*: <math>\!\, \mathbb{Z} = \mathbb{N} \cup \{\ldots, -2, -1\} </math>
* Murtolukujen joukko
*: <math>\!\, \mathbb{Q} = \mathbb{Z} \cup \{\ldots, -1/3, -1/2, 1/2, 1/3, \ldots, 2/3, 2/5, \ldots\} </math>
* Reaalilukujen joukko
*: <math>\!\, \mathbb{R} = \mathbb{Q} \cup \{\ldots, -\pi, -\sqrt{2}, \sqrt{2}, \pi, \ldots\} </math>
* Kompleksilukujen joukko
*: <math>\!\, \mathbb{C} = \mathbb{R} \cup \{i, 1 + i, 1 - i, \sqrt{2} + \pi i, \ldots\} </math>

Vain silloin kun matemaattinen lause on omalla rivillään, käytämme liitutaulupaksunnosta (<math> \mathbb{N} \!\!</math>). Muutoin käytämme tavallista paksunnosta ('''N''').

== Set comprehension ==
Kun esitämme joukon, voimme tehdä sen kirjoittamalla esiin kaikki joukon alkiot. Jos kuitenkin haluamme esittää ''äärettömän'' joukon, niin jokaisen alkion kirjoittaminen voi olla hieman ongelmallista. Voimme ratkaista ongelman esittämällä joukon ''set comprehension'' muodossa. Joukko esitetään tässä muodossa esitämällä sen mukana ''sääntö'' ja suhde ''indeksijoukkoon'' I. Se on;
: <math>S=\{x \in I |\, R\}</math>
jossa R on ''x''<sup>2</sup>=''0'', tai ''x''=3''t'' kokonaisluvulle t. Tällaista sääntöä kutsutaan ''x:n boolen predikaatiksi'', ja voimme lukea lauseen: ''S on sellainen joukko kaikille x I:ssä, että x:n neliö on nolla.''

Esim. parillisten lukujen joukko:
: <math>\{x \in \mathbb{N}|\, x \; \bmod \; 2 = 0\}</math>

Toisen asteen yhtälön ratkaisujen joukko:
: <math>\{x \in \mathbb{C}|\, ax^2+bx+c = 0\}</math>

Huomaa, että:
: <math>\{x \in \mathbb{N}|\, ax^2+bx+c = 0\}</math>
on kokonaan eri joukko!

=== Venn-diagrammit ===

Venn-diagrammi on joukkojen graafinen esitystapa, jolla pyritään havainnollistamaan joukkoja ja niiden välisiä suhteita.
<table>
<td>Leikkaus</td>
<td>[[Kuva:Venn_A_intersect_B.svg|thumb|200px|A:n ja B:n leikkaus]]</td></tr>
<td>Yhdiste eli unioni</td>
<td>[[Kuva:Set union.png|thumb|200px|A:n ja B:n yhdiste]]</td></tr>
<td>Osajoukko</td>
<td>[[Kuva:Set subsetAofB.svg|thumb|200px|A on B:n osajoukko]]</td></tr>
</table>
*



*Ei päällekkäisyyttä, tai joukon A ja B yhdistejoukko on tyhjä joukko.

=== Perusjoukot ja komplementit ===

==== Perusjoukot ====

Kun työskentelemme joukkojen kanssa, on käytännöllistä ajatella toista, laajempaa joukkoa, jota kutsumme ''perusjoukoksi'', ja sitten työskennellä tämän joukon sisällä. Esim. jos käsittelemme joukkoja {-1,0,1} ja {-3,-1,1,3}, niin on käytännöllistä työskennellä joukossa '''Z'''. Kun työskentelemme tällaisessa laajemmassa joukossa, kuten '''Z''', sanomme että '''Z''' on perusjoukko, ja oletamme kaikkien joukkojen olevan '''Z''':n osajoukkoja.

Merkitsemme perusjoukkoa <math>\mathcal{E}</math>:lla, kuitenkin on helpompi kirjoittaa vain '''E'''.

==== Komplementit ====
Olkoon joukko A perusjoukon '''E''' osajoukko. Määrittelemme A:n komplementin olevan kaikki E:ssä olevat alkiot, jotka eivät ole A:ssa. Toisin sanottuna A:n komplementti on:
:<math>\{x\in \mathcal{E}|\,x\not\in A\}</math>

A:n komplementti esitetään merkitsemällä <math>A^'</math>, <math>A^c</math> tai <math>\bar{A}</math>.

=== Harjoituksia ===

Koeta vastata seuraaviin kysymyksiin oppimasi tiedon perusteella.

(Parillisiin kysymyksiin on annettu vastaukset.)

# Onko <math>3/4\in\mathbb{Q}</math>?
# Onko <math> \sqrt{2}\in\mathbb{Q}</math>?<!-- 2 -->
# Onko <math>\{2x |\ x\in\mathbb{N}\}=\{x\in\mathbb{N}\ |\ {x\over 2}\in \mathbb{N}\}</math>?
# Oikein vai väärin? Jos väärin, anna esimerkki alkiosta, joka kuuluu ensimmäiseen, muttei toiseen joukkoon. <!-- 4 -->
## <math>\mathbb{N} \subseteq \mathbb{Z}</math>
## <math>\mathbb{Q} \subseteq \mathbb{Z}</math>
# Oikein vai väärin? Jos väärin, anna esimerkki alkiosta, joka kuuluu ensimmäiseen, muttei toiseen joukkoon. <!-- 4 -->
## <math>\mathbb{R} \subseteq \mathbb{Q}</math>
## <math>\mathbb{Z} \subseteq \mathbb{R}</math>
# Onko <math>\{1,2,3\} \subset \{1,2,3,4\}</math>? <!--6 -->
# Onko <math>\{1,2,3,5\} \subseteq \{1,2,3,4\}</math>?
# Kirjoita joukon <br/><math>\{x\in\mathbb{Z}|x - 3 \equiv 0 \; (\bmod \; 2)\}</math> viisi alkiota<!--8 -->
# Kirjoita <br/><math>\{x\in\mathbb{C}\ |\ x^2+4x-3=0\}</math> alkiot.
# Etsi perusjoukko, siten että nämä joukot ovat sen osajoukkoja:
<math>\{x \in \mathbb{Z^+}\ |\ a=x^2 \; \mbox{ja}\ \sqrt{a}\in\mathbb{N}\},\{x \in \mathbb{N}\ |\ x/3\} </math> <!-- 10 -->
# Kun <math>\mathcal{E}=\{0,1,2,3,4,5,6,7,8,9\}</math> on annettu, etsi A', siten että <math>A=\{1,4,7,9\}</math>.

==== Vastaukset ====
:2. Ei, <math>\sqrt{2}</math> on irrationaalinen, ei rationaaliluku
:4.1. Kyllä.
:4.2. Ei. Esimerkiksi 1/2 kuuluu rationaalilukuihin mutta ei kokonaislukuihin.
:6. Kyllä.
:8. Viisi alkiota ovat esimerkiksi {3,5,7,9,11}.
:10. <math>\mathcal{E}=\mathbb{Q}</math>

== Muita konsepteja ==
Mainitut ideat eivät ole ainoita, joita kohtaamme joukko-opissa. 
Näitä keskeisiä aiheita ei välttämättä ole erityisesti painotettu tässä lähtötason kurssissa, mutta on tärkeä osata ne, sillä niitä tarvitaan myöhemmin abstraktissa algebrassa ja muilla aloilla.

Voidaan ohittaa.

=== Potenssijoukko ===
Joukon S ''potenssijoukko'', merkittynä P(S), on ''kaikkien'' S:n osajoukkojen joukko (sisältäen myös itse joukon S).
'''''NB''''': Tyhjä joukko on '''kaikkien''' joukkojen osajoukko.

Esim.
P({0,1})={{},{0},{1},{0,1}}

=== Mahtavuus ===
Joukon S ''mahtavuus'', merkittynä |S|, on yksinkertaisesti joukon alkioiden lukumäärä. Eli |{a,b,c,d}|=4, jne. Joukon mahtavuuden ei tarvitse olla äärellinen; joidenkin joukkojen mahtavuus on ääretön.

==== Potenssijoukon mahtavuus ====

Jos P(S)=T, niin |T|=2<sup>|S|</sup>.

==== Harjoituksia ====
Koita vastata seuraaviin kysymyksiin oppimasi tiedon perusteella.

(Parillisiin kysymyksiin on annettu vastaukset.)

# |{1,2,3,4,5,6,7,8,9,0}|
# |P({1,2,3})|
# P({0,1,2})
# P({1})

===== Vastaukset =====
:2. 2<sup>3</sup>=8
:4. {{},{1}}

== Joukkojen identtisyys ==
''yhdiste''- ja ''leikkaus''operaattoria käyttämällä voimme muodostaa sääntöjä, jotka yksinkertaistavat joukkojen käsittelyä.

Esim.
:<math>(A\cup B)'\cap B'\cap A</math>
Kuinka voimme yksinkertaistaa ilmaisua?

Useat seuraavista joukkojen identtisyyksistä ovat samankaltaisia tavallisessa matematiikassa, kuten ''liitännäisyyslaki'', ''osittelulaki'', jne.

==== Vaihdannaisuus ====
:<math>A\cup B = B \cup A</math>
:<math>A\cap B = B \cap A</math>

==== Liitännäisyys ====
:<math>A\cup (B \cup C) = (A\cup B)\cup C</math>
:<math>A\cap (B \cap C) = (A\cap B)\cap C</math>

==== Ositeltavuus ====
:<math>A\cup (B \cap C) = (A \cup B)\cap(A\cup C)</math>
:<math>A\cap (B \cup C) = (A \cap B)\cup(A\cap C)</math>

==== Identtisyys ====
:<math>A \cup \{\} = A</math>
:<math>A \cap \mathcal{E} = A </math>

==== Idempotenssi ====
:<math>A \cup A = A</math>
:<math>A \cap A = A</math>

==== Dominointi ====
:<math>A \cap \{\} = \{\}</math>
:<math>A \cup \mathcal{E} = \mathcal{E}</math>

==== Kaksoiskomplementti ====
:<math>(A')' = A\!\,</math>

==== Komplementit yhdisteet ja leikkaukset ====
:<math>A \cup A' = \mathcal{E}</math>
:<math>A \cap A' = \{\}</math>

==== De Morganin lait ====
:<math>(A \cup B)' = A' \cap B'</math>
:<math>(A \cap B)' = A' \cup B'</math>

Nämä ovat ''lakeja'' pikemmin kuin ''aksioomia'', koska voimme todistaa ne toisista aksioomista.

Muista, että yllä olevat kaksi joukkoa A ja B ovat yhtenevät, jos <math>A\subseteq B</math> ja <math>B\subseteq A</math>. 

Todistus.

1) <math>(A \cup B)'\subseteq A' \cap B'</math>

Otetaan satunnainen alkio <math>x \in (A \cup B)'</math>. Emme tiedä mitään x:stä, se voi olla numero, funktio tai elefantti. Ainoa asia minkä tiedämme x:stä, on että

:<math>x \in (A \cup B)'</math>

joten

:<math>x \notin (A \cup B)</math>

koska tätä komplementti tarkoittaa. Siten

:<math>x \notin A</math> and <math>x \notin B</math>

aukaisemalla yhdiste. Soveltamalla komplementteja uudestaan saamme

:<math>x \in A'</math> and <math>x \in B'</math>

Lopuksi, jos jotain on kahdessa joukossa, sen täytyy olla niiden yhdisteessä, joten

:<math>x \in A' \cap B'</math>

Joten, otimme minkä tahansa alkion :<math>(A \cup B)'</math>, niin se on aina <math>A' \cap B'</math>, joten määritelmän mukaan

:<math>(A \cup B)'\subseteq A' \cap B'</math>


2) :<math>A' \cap B'\subseteq (A \cup B)'</math>

Toimimme samanlaisella tavalla. Ensiksi, otamme satunnaisen alkion ensimmäisestä joukosta, <math>x \in A' \cap B'</math>

Käyttäen tietoamme yhdisteistä, se tarkoittaa

:<math>x \in A'</math> ja <math>x \in B'</math>

Nyt, käyttäen komplementteja

:<math>x \notin A</math> ja <math>x \notin B</math>

Jos jokin ei ole A:ssa, eikä B:ssä, se ei voi olla niiden yhdiste, joten

:<math>x \notin A \cup B</math>

Ja lopulta

:<math>x \in (A \cup B)'</math>

Joten, nyt meillä on ''molemmat'' <math>(A \cup B)'\subseteq A' \cap B'</math> ja <math>A' \cap B'\subseteq (A \cup B)'</math>. Näin todistimme ensimmäisen De Morganin laeista:

:<math>(A \cup B)' = A' \cap B'</math>

Toisen puolen lukija voi todistaa itse harjoituksena.

==== Joukkojen erotus ====
Joukkojen A ja B erotus on se joukko, johon kuuluvat ne joukon A alkiot jotka eivät kuulu joukkoon B.

:<math>A - B = A \cap B'</math>

=== Dualisointi ===
Huomaa, että yllä olevista säännöistä sinun ei tarvitse muistaa koko taulukkoa. Itse asiassa sinun tarvitsee muistaa vain ''puolet'' taulukosta ja voit vaihtaa &cup;:in &cap;:iin ja toisinpäin. Näin voi kuitenkin menetellä vain poikkeustapauksissa.

Tämä on tärkeä ominaisuus, ja sanommekin, että jokaista yhdisteitä koskevaa sääntöä vastaa vastaavan leikkaussäännön ''duaali''. Ominaisuutta voidaan käyttää joukkojen indenttisyyslakien muistamiseen.

Dualisointi liittyy Boolen algebran aksioomiin. Katso [[Diskreetti matematiikka:Boolen algebra]].

=== Harjoituksia ===
Koeta vastata seuraaviin kysymyksiin oppimasi tiedon perusteella.

(Parillisiin kysymyksiin on annettu vastaukset.)

# <math>(A \cup B)' \cap C</math>
# <math>((A \cup B) \cap (A \cup C))\cap \mathcal{E}</math>
# <math>A \cup (B \cap (C' \cup B'))</math>
# <math>(A' \cup B)'</math>

==== Vastaukset ====
:2. <math>A\cup(B \cap C)</math>
:4. <math>A \cap B'</math>

== Lisää joukko-operaatioista ==

=== Kahden joukon erotus ===

Joukko <math>A \setminus B</math>, luetaan ''A miinus B'', sisältää kaikki joukon A alkiot, jotka '''eivät''' ole joukon B alkioita. Toisin sanoen:

:<math>A \setminus B = A \cap B'</math>

Erotusta voidaan käyttää äärettömien joukkojen määrittelyssä, esim. kaikkien kokonaislukujen erisuuri kuin nolla joukko voidaan kirjoittaa: <math>\mathbb{Z}\setminus\{0\}</math>. On itsestään selvää, että <math>A \setminus B \neq B \setminus A</math> ja <math>A \setminus A = \{\}</math>

=== Suppea merkintä useammalle kuin kahdelle joukolle ===
Jos meillä on joukot <math>A_1, A_2, \ldots, A_n</math>, voimme esittää näiden joukkojen yleistetyn yhdisteen tai leikkauksen, ts. <math>A_1 \cup A_2 \cup A_3 \ldots \cup A_n</math>
jonka voimme kirjoittaa lyhyesti
:<math>\bigcup_{x=1}^{n}A_x</math>.

Samalla tavalla leikkauksille kirjoitamme:
:<math>\bigcap_{x=1}^{n}A_x</math>.`

=== Karteesinen tulo ===
Karteesinen tulo on tärkeä konsepti, kun käsittelemme funktioita seuraavassa osiossa. Esittelemme peruskäsitteet ensiksi.

==== n-tuplat ====
''n''-tupla on samanlainen kuin joukko, mutta alkioiden järjestys on tärkeä. Kirjoitamme nämä ''järjestetyt joukot'' pyöreillä sulkeilla - ( ja ) aaltosulkeiden { ja } sijaan korostaaksemme, että alkiot ovat järjestyksessä. Ajattele pisteitä tasolla - (1,0) ei ole sama kuin (0,1), mutta jos kirjoitamme nämä joukoille varatuilla aaltosulkeilla, ne ovat.
Esim.
:<math>\{1,2,3\}=\{3,1,2\}\!\,</math>
''mutta''
:<math>(1,2,3)\ne(3,1,2)</math>

==== Karteesinen tulo ====
Kahden joukon karteesinen tulo on joukko, joka sisältää kaikki kahden joukon alkioista tehdyt tuplat. Kahden joukon A ja B karteesinen tulo ilmaistaan A &times; B. Se on määritelty:
:<math>A \times B = \{(a,b)|a\in A\ \mbox{and}\ b\in B\}</math>

Ymmärtäminen voi olla helpompaa esimerkeistä:

:<math>\{0,1\}\times\{2,3\}=\{(0,2),(1,2),(0,3),(1,3)\}</math>
:<math>\{a,b\}\times\{c,d\}=\{(a,c),(a,d),(b,c),(b,d)\}</math>
:<math>\{0,1,2\}\times\{4,6\}=\{(0,4),(1,4),(2,4),(0,6),(1,6),(2,6)\}</math>

On selvää, että joukkojen A ja B karteesisen tulon mahtavuus on:
:<math>|A\times B|=|A||B|</math>

Kahden joukon A ja B karteesinen tulo voidaan muodostaa tekemällä tuplat A:n ja B:n alkioista; Operaation voi kuvitella ruudukon tai taulukon muotoon: jos, ''esim.'' A = {0,1} ja B = {2,3}, ruudukko on
<table cellpadding="5" cellspacing="2" border="1">
<tr><td rowspan="2" colspan="2" align="center" valign="middle">'''&times;'''</td><td colspan="2" align="center">'''A'''</td></tr>
<tr><td align="center">'''0'''</td><td align="center">'''1'''</td></tr>
<tr><td rowspan="2">'''B'''</td><td>'''2'''&nbsp;</td><td>(0,2)</td><td>(1,2)</td></tr>
<tr><td>'''3'''</td><td>(0,3)</td><td>(1,3)</td></tr>
</table>

Karteesinen tulo voidaan tuottaa myös useimmilla ohjelmointikielillä soveltaen kahta sisäkkäistä silmukkaa, tai suhteellisesta tietokannasta valitsemalla kahdesta taulukosta ilman, että selvittää mistä.



=== Harjoituksia ===
Koeta vastata seuraaviin kysymyksiin oppimasi tiedon perusteella.

(Parillisiin kysymyksiin on annettu vastaukset.)
# {2,3,4}&times;{1,3,4}
# {0,1}&times;{0,1}
# |{1,2,3}&times;{0}|
# |{1,1}&times;{2,3,4}|

==== Vastaukset ====
: 2. {(0,0),(0,1),(1,0),(1,1)}
: 4. 6

== Russellin antinomia ==
Tarkastellaan luokkaa
: <math>A = \{X | X\ \mbox{joukko ja}\ X \not\in X\}</math>

Luokan A alkiot ovat joukkoja. Jos siis A olisi joukko, pitäisi A:n olla luokassa A. Mutta toisaalta tämä on ristiriidassa A:n määritelmän kanssa. Siten A on luokka, mutta ei joukko.

Tämän esimerkin avulla nähdään ''naiivin'' joukko-opin ja aksiomaattisen joukko-opin ero. Aksiomaattinen joukko-oppi pyrkii määrittelemään käsitteet täsmällisesti, jotta yllä olevan esimerkin kaltaisia paradoksaalisia tilanteita ei pääse syntymään.

[[Luokka:Diskreetti matematiikka|{{SUBPAGENAME}}]]