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:

$\!\,\{1,2,3,4\}{\mbox{, }}\{3,2,4,1\}{\mbox{, tai }}\{1,2,2,2,3,4\}$

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

  $\!\,4\in \{1,2,3,4\}$

• Kaksi joukkoa ovat yhtenevät; molemmat osoittavat samoihin alkioihin

  $\!\,\{1,2,3,4\}=\{3,2,4,1\}$

• Joukko on toisen joukon ylijoukko; se osoittaa kaikkiin toisen joukon alkioihin, ehkä useampaankin

  $\!\,\{1,2,3,4\}\supseteq \{1,2,3\}{\mbox{ ja }}\{1,2,3,4\}\supseteq \{1,2,3,4\}$

• Joukko on on toisen joukon aito ylijoukko; se osoittaa kaikkiin toisen joukon alkioihin, mutta aina myös muihin sen lisäksi

  $\!\,\{1,2,3,4\}\supset \{1,2,3\}$

• Osajoukko ja aito osajoukko -suhteet ovat vastakkaiset verrattuna ylijoukko ja aitoylijoukko -suhteisiin

  $\!\,\{1,2,3,4\}\subseteq \{1,2,3,4\}{\mbox{ ja }}\{1,2,3\}\subset \{1,2,3,4\}$

Symboli ⊂ näyttää ja toimii samalla tavalla kuin <. Symbolit ∈ ja < 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

  $\!\,\{1,2,3,4\}\cup \{2,4,6,8\}=\{1,2,3,4,6,8\}$

• Voimme muodostaa leikkausjoukon

  $\!\,\{1,2,3,4\}\cap \{2,4,6,8\}=\{2,4\}$

• Voimme muodostaa erotusjoukon

  $\!\,\{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\}$

∪ symboli näyttää kupilta, joka voi pitää sisällään paljon asioita. ∩ 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

  $\!\,\emptyset =\{\}$

• Luonnollisten lukujen joukko

  $\!\,\mathbb {N} =\{0,1,2,3,\ldots \}$

• Kokonaislukujen joukko

  $\!\,\mathbb {Z} =\mathbb {N} \cup \{\ldots ,-2,-1\}$

• Murtolukujen joukko

  $\!\,\mathbb {Q} =\mathbb {Z} \cup \{\ldots ,-1/3,-1/2,1/2,1/3,\ldots ,2/3,2/5,\ldots \}$

• Reaalilukujen joukko

  $\!\,\mathbb {R} =\mathbb {Q} \cup \{\ldots ,-\pi ,-{\sqrt {2}},{\sqrt {2}},\pi ,\ldots \}$

• Kompleksilukujen joukko

  $\!\,\mathbb {C} =\mathbb {R} \cup \{i,1+i,1-i,{\sqrt {2}}+\pi i,\ldots \}$

Vain silloin kun matemaattinen lause on omalla rivillään, käytämme liitutaulupaksunnosta ($\mathbb {N} \!\!$). 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;

$S=\{x\in I|\,R\}$

jossa R on x²=0, tai x=3t 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:

$\{x\in \mathbb {N} |\,x\;{\bmod {\;}}2=0\}$

Toisen asteen yhtälön ratkaisujen joukko:

$\{x\in \mathbb {C} |\,ax^{2}+bx+c=0\}$

Huomaa, että:

$\{x\in \mathbb {N} |\,ax^{2}+bx+c=0\}$

on kokonaan eri joukko!

Venn-diagrammit

Venn-diagrammi on joukkojen graafinen esitystapa, jolla pyritään havainnollistamaan joukkoja ja niiden välisiä suhteita.

Leikkaus	A:n ja B:n leikkaus
Yhdiste eli unioni	A:n ja B:n yhdiste
Osajoukko	A on B:n osajoukko

• 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 ${\mathcal {E}}$: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:

$\{x\in {\mathcal {E}}|\,x\not \in A\}$

A:n komplementti esitetään merkitsemällä $A^{'}$, $A^{c}$ tai ${\bar {A}}$.

Harjoituksia

Koeta vastata seuraaviin kysymyksiin oppimasi tiedon perusteella.

(Parillisiin kysymyksiin on annettu vastaukset.)

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

$\{x\in \mathbb {Z^{+}} \ |\ a=x^{2}\;{\mbox{ja}}\ {\sqrt {a}}\in \mathbb {N} \},\{x\in \mathbb {N} \ |\ x/3\}$

1. Kun ${\mathcal {E}}=\{0,1,2,3,4,5,6,7,8,9\}$ on annettu, etsi A', siten että $A=\{1,4,7,9\}$.

Vastaukset

2. Ei, ${\sqrt {2}}$ 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. ${\mathcal {E}}=\mathbb {Q}$

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^|S|.

Harjoituksia

Koita vastata seuraaviin kysymyksiin oppimasi tiedon perusteella.

(Parillisiin kysymyksiin on annettu vastaukset.)

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

Vastaukset

2. 2³=8

4. {{},{1}}

Joukkojen identtisyys

yhdiste- ja leikkausoperaattoria käyttämällä voimme muodostaa sääntöjä, jotka yksinkertaistavat joukkojen käsittelyä.

Esim.

$(A\cup B)'\cap B'\cap A$

Kuinka voimme yksinkertaistaa ilmaisua?

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

Vaihdannaisuus

$A\cup B=B\cup A$

$A\cap B=B\cap A$

Liitännäisyys

$A\cup (B\cup C)=(A\cup B)\cup C$

$A\cap (B\cap C)=(A\cap B)\cap C$

Ositeltavuus

$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

Identtisyys

$A\cup \{\}=A$

$A\cap {\mathcal {E}}=A$

Idempotenssi

$A\cup A=A$

$A\cap A=A$

Dominointi

$A\cap \{\}=\{\}$

$A\cup {\mathcal {E}}={\mathcal {E}}$

Kaksoiskomplementti

$(A')'=A\!\,$

Komplementit yhdisteet ja leikkaukset

$A\cup A'={\mathcal {E}}$

$A\cap A'=\{\}$

De Morganin lait

$(A\cup B)'=A'\cap B'$

$(A\cap B)'=A'\cup B'$

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 $A\subseteq B$ ja $B\subseteq A$.

Todistus.

1) $(A\cup B)'\subseteq A'\cap B'$

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

$x\in (A\cup B)'$

joten

$x\notin (A\cup B)$

koska tätä komplementti tarkoittaa. Siten

$x\notin A$ and $x\notin B$

aukaisemalla yhdiste. Soveltamalla komplementteja uudestaan saamme

$x\in A'$ and $x\in B'$

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

$x\in A'\cap B'$

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

$(A\cup B)'\subseteq A'\cap B'$

2) :$A'\cap B'\subseteq (A\cup B)'$

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

Käyttäen tietoamme yhdisteistä, se tarkoittaa

$x\in A'$ ja $x\in B'$

Nyt, käyttäen komplementteja

$x\notin A$ ja $x\notin B$

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

$x\notin A\cup B$

Ja lopulta

$x\in (A\cup B)'$

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

$(A\cup B)'=A'\cap B'$

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.

$A-B=A\cap B'$

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 ∪:in ∩: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.)

1. $(A\cup B)'\cap C$
2. $((A\cup B)\cap (A\cup C))\cap {\mathcal {E}}$
3. $A\cup (B\cap (C'\cup B'))$
4. $(A'\cup B)'$

Vastaukset

2. $A\cup (B\cap C)$

4. $A\cap B'$

Lisää joukko-operaatioista

Kahden joukon erotus

Joukko $A\setminus B$, luetaan A miinus B, sisältää kaikki joukon A alkiot, jotka eivät ole joukon B alkioita. Toisin sanoen:

$A\setminus B=A\cap B'$

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

Suppea merkintä useammalle kuin kahdelle joukolle

Jos meillä on joukot $A_{1},A_{2},\ldots ,A_{n}$, voimme esittää näiden joukkojen yleistetyn yhdisteen tai leikkauksen, ts. $A_{1}\cup A_{2}\cup A_{3}\ldots \cup A_{n}$ jonka voimme kirjoittaa lyhyesti

$\bigcup _{x=1}^{n}A_{x}$.

Samalla tavalla leikkauksille kirjoitamme:

$\bigcap _{x=1}^{n}A_{x}$.`

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.

$\{1,2,3\}=\{3,1,2\}\!\,$

mutta

$(1,2,3)\neq (3,1,2)$

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 × B. Se on määritelty:

$A\times B=\{(a,b)|a\in A\ {\mbox{and}}\ b\in B\}$

Ymmärtäminen voi olla helpompaa esimerkeistä:

$\{0,1\}\times \{2,3\}=\{(0,2),(1,2),(0,3),(1,3)\}$

$\{a,b\}\times \{c,d\}=\{(a,c),(a,d),(b,c),(b,d)\}$

$\{0,1,2\}\times \{4,6\}=\{(0,4),(1,4),(2,4),(0,6),(1,6),(2,6)\}$

On selvää, että joukkojen A ja B karteesisen tulon mahtavuus on:

$|A\times B|=|A||B|$

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

×		A
		0	1
B	2	(0,2)	(1,2)
	3	(0,3)	(1,3)

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.)

1. {2,3,4}×{1,3,4}
2. {0,1}×{0,1}
3. |{1,2,3}×{0}|
4. |{1,1}×{2,3,4}|

Vastaukset

2. {(0,0),(0,1),(1,0),(1,1)}

4. 6

Russellin antinomia

Tarkastellaan luokkaa

$A=\{X|X\ {\mbox{joukko ja}}\ X\not \in X\}$

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.