Johdatus diskreettiin matematiikkaan, syksy 2000
Harjoitus 1, 26.-28.9.

1. Fibonaccin luvut $F_n$, $n \geq 0$, määritellään kaavoilla $F_0 = 0$, $F_1 = 1$, $F_{n} = F_{n-1} + F_{n-2}$, kun $n \geq 2$. (Lukusarjan ensimmäiset luvut ovat siis 0, 1, 1, 2, 3, 5, 8, ...) Todista induktiolla indeksin $n$ suhteen, että kaikilla $n \geq 2$ on voimassa
   
   $$\phi^{n-2} \leq F_n \leq \phi^{n-1},$$
   
   
   missä luku $\phi$ on ns. ``kultaisen leikkauksen suhde'' $\phi = \frac{\sqrt{5}+1}{2}$.

2. Olkoon $A = \{0,1,2\}^2$. Piirrä Hasse-kaavio järjestysrelaatiosta $\preceq\; \subseteq A\times A$, missä
   
   $$(r,s) \preceq (r',s') \qquad \mbox{joss} \qquad r \leq r' \mbox{ ja } s \leq s'.$$
   
   
   (Tässä siis relaatio $\leq$ on kokonaislukujen tavanomainen järjestys.) Onko vastaava relaatio, jonka määrittelyssä on ``ja''-sana korvattu ``tai''-sanalla, myös osittainjärjestys?

3. 1. Luettele kaikki joukon $\{a,b,c\}$ ekvivalenssirelaatiot (ositukset).
   2. Piirrä kaikkien joukon $\{a,b,c\}$ järjestysrelaatioiden (osittainjärjestysten) Hasse-kaaviot.

4. Kuvaile yleisesti järjestettyjen joukkojen $({\cal P}(\{1,2,\dots,n\}),\subseteq)$ ja $(\{2,3,4,\dots,n\}, \vert)$ rakennetta. (Merkintä ``|'' tarkoittaa tässä kokonaislukujen jaollisuusrelaatiota: $m \vert n$, jos $m$ on $n$:n tekijä.) Mitkä ovat järjestysten minimialkiot? Annetun alkion välittömät seuraajat? Miten pitkä voi kummassakin järjestyksessä olla maksimaalisen pitkä ketju, so. täydellisesti järjestetty alkiojono $a_1 \prec a_2 \prec \cdots \prec a_k$?

5. Osoita, että jokainen äärellinen järjestetty joukko sisältää maksimaalisen, mutta ei välttämättä suurinta alkiota.

6. Luonnollisten lukujen induktioperiaatteen mukaan mille tahansa luonnollisten lukujen ominaisuudelle $P$ on voimassa, että jos $P(0)$ on tosi ja implikaatio $P(n-1) \Rightarrow P(n)$ on tosi kaikilla $n \in {\mathbf N}\setminus\{0\}$, niin $P(n)$ on tosi kaikilla $n \in {\mathbf N}$. Todista periaate oikeaksi lähtien tiedoista, että luonnollisten lukujen suuruusjärjestys $({\mathbf N}, \leq)$ on hyvinjärjestys, jolla on pienin alkio $0$, ja lisäksi jokaisella alkiolla $n \in {\mathbf N}\setminus\{0\}$ on välitön edeltäjä $n-1$.