6.6 Bevis og matematisk argumentasjon

La $a$ og $b$ vere to partal.

Steg 1: Sidan $a$ er eit partal, finst det eit heiltal $m$ slik at $a = 2m$.

Steg 2: Sidan $b$ er eit partal, finst det eit heiltal $n$ slik at $b = 2n$.

Steg 3: Vi reknar ut summen:
$$a + b = 2m + 2n = 2(m + n)$$

Steg 4: Sidan $m + n$ er eit heiltal (summen av to heiltal er eit heiltal), og $a + b = 2(m + n)$, er $a + b$ eit partal per definisjon.

$$\blacksquare$$

La $a$ og $b$ vere to oddetal.

Steg 1: Sidan $a$ er eit oddetal, finst det eit heiltal $m$ slik at $a = 2m + 1$.

Steg 2: Sidan $b$ er eit oddetal, finst det eit heiltal $n$ slik at $b = 2n + 1$.

Steg 3: Vi reknar ut produktet:
$$a \cdot b = (2m + 1)(2n + 1)$$

Steg 4: Vi utvidar:
$$a \cdot b = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1$$

Steg 5: La $k = 2mn + m + n$. Då er $k$ eit heiltal, og vi har:
$$a \cdot b = 2k + 1$$

Dette er forma til eit oddetal, så $a \cdot b$ er eit oddetal.

$$\blacksquare$$

La $n$ vere eit partal.

Steg 1: Sidan $n$ er eit partal, finst det eit heiltal $k$ slik at $n = 2k$.

Steg 2: Vi reknar ut $n^2$:
$$n^2 = (2k)^2 = 4k^2$$

Steg 3: Sidan $k^2$ er eit heiltal, og $n^2 = 4k^2 = 4 \cdot k^2$, er $n^2$ deleleg med 4.

$$\blacksquare$$

La dei tre påfølgjande heiltala vere $n$, $n+1$ og $n+2$.

Steg 1: Vi reknar ut summen:
$$n + (n+1) + (n+2) = 3n + 3 = 3(n + 1)$$

Steg 2: Sidan $n + 1$ er eit heiltal, og summen kan skrivast som $3 \cdot (n+1)$, er summen deleleg med 3.

$$\blacksquare$$

Steg 1 (Føresetnad): Anta at $\sqrt{2}$ er rasjonalt. Då kan vi skrive:
$$\sqrt{2} = \frac{p}{q}$$
der $p$ og $q$ er heiltal utan felles faktorar (brøken er maksimalt forkorta) og $q \neq 0$.

Steg 2: Vi kvadrerer begge sider:
$$2 = \frac{p^2}{q^2}$$

Steg 3: Vi gangar med $q^2$:
$$2q^2 = p^2$$

Steg 4: Sidan $p^2 = 2q^2$, er $p^2$ eit partal. Men då må òg $p$ vere eit partal (for dersom $p$ var oddetal, ville $p^2$ òg vore oddetal).

Steg 5: Sidan $p$ er eit partal, kan vi skrive $p = 2k$ for eit heiltal $k$. Vi set inn:
$$2q^2 = (2k)^2 = 4k^2$$

Steg 6: Vi deler på 2:
$$q^2 = 2k^2$$

Steg 7: Sidan $q^2 = 2k^2$, er $q^2$ eit partal, og difor er òg $q$ eit partal.

Steg 8 (Motseiing): Både $p$ og $q$ er partal, noko som tyder at dei har felles faktor 2. Men vi antok at brøken var maksimalt forkorta! Dette er ei sjølvmotseiing.

Konklusjon: Føresetnaden om at $\sqrt{2}$ er rasjonalt må vere feil. Difor er $\sqrt{2}$ irrasjonalt.

$$\blacksquare$$

Steg 1 (Føresetnad): Anta at det berre finst endeleg mange primtal. La desse vere $p_1, p_2, p_3, \ldots, p_n$.

Steg 2: Sjå på talet:
$$N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$$

Dette er produktet av alle primtala pluss 1.

Steg 3: Vi undersøkjer om $N$ er deleleg med nokon av primtala $p_1, p_2, \ldots, p_n$:
- Når vi deler $N$ på $p_1$, får vi rest 1 (sidan $N = p_1 \cdot (\text{noko}) + 1$)
- Når vi deler $N$ på $p_2$, får vi rest 1
- Generelt: Når vi deler $N$ på $p_i$, får vi alltid rest 1

Altså er $N$ ikkje deleleg med nokon av primtala $p_1, \ldots, p_n$.

Steg 4: Men alle tal større enn 1 har minst ein primfaktor. Sidan $N > 1$ og $N$ ikkje er deleleg med nokon av $p_1, \ldots, p_n$, må $N$ anten:
- Vere eit primtal sjølv (som ikkje er i lista), eller
- Ha ein primfaktor som ikkje er i lista

Steg 5 (Motseiing): Uansett har vi funne eit primtal som ikkje er i lista vår over alle primtal. Dette motseier føresetnaden.

Konklusjon: Det finst uendeleg mange primtal.

$$\blacksquare$$

Steg 1 (Føresetnad): Anta at det finst eit minste positive rasjonale tal $r$.

Steg 2: Sjå på talet $\displaystyle \frac{r}{2}$.

Steg 3: Vi merkar oss at:
- $\displaystyle \frac{r}{2}$ er rasjonalt (kvotienten av to rasjonale tal er rasjonalt)
- $\displaystyle \frac{r}{2} > 0$ (helvta av eit positivt tal er positivt)
- $\displaystyle \frac{r}{2} < r$

Steg 4 (Motseiing): Vi har funne eit positivt rasjonalt tal $\displaystyle \frac{r}{2}$ som er mindre enn $r$. Men $r$ var antatt å vere det minste. Dette er ei sjølvmotseiing.

Konklusjon: Det finst ikkje noko minste positive rasjonale tal.

$$\blacksquare$$

La $P(n)$ vere påstanden: $\displaystyle 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$

Basissteg ($n = 1$):

Venstre side: $1$

Høgre side: $\displaystyle \frac{1 \cdot 2}{2} = 1$

Sidan venstre side = høgre side, er $P(1)$ sann.

Induksjonssteg:

Induksjonsføresetnad: Anta at $P(k)$ er sann for ein vilkårleg $k \geq 1$, dvs.:
$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Å vise: $P(k+1)$ er sann, dvs.:
$$1 + 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}$$

Bevis:
$$1 + 2 + 3 + \cdots + k + (k+1) = \underbrace{\frac{k(k+1)}{2}}_{\text{induksjonsføresetnaden}} + (k+1)$$

$$= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{k(k+1) + 2(k+1)}{2}$$

$$= \frac{(k+1)(k + 2)}{2}$$

Dette er nettopp $P(k+1)$.

Konklusjon: Ved induksjonsprinsippet er $P(n)$ sann for alle $n \geq 1$.

$$\blacksquare$$

La $P(n)$ vere påstanden: $1 + 3 + 5 + \cdots + (2n-1) = n^2$

Basissteg ($n = 1$):

Venstre side: $1$

Høgre side: $1^2 = 1$

$P(1)$ er sann.

Induksjonssteg:

Induksjonsføresetnad: Anta $P(k)$: $1 + 3 + 5 + \cdots + (2k-1) = k^2$

Å vise: $P(k+1)$: $1 + 3 + 5 + \cdots + (2k-1) + (2(k+1)-1) = (k+1)^2$

Bevis:
$$1 + 3 + 5 + \cdots + (2k-1) + (2k+1) = k^2 + (2k+1)$$

$$= k^2 + 2k + 1 = (k+1)^2$$

Konklusjon: Ved induksjonsprinsippet er $P(n)$ sann for alle $n \geq 1$.

$$\blacksquare$$

La $P(n)$ vere påstanden: $6 \mid (n^3 - n)$ (6 deler $n^3 - n$)

Basissteg ($n = 1$):

$1^3 - 1 = 0 = 6 \cdot 0$

Sidan 0 er deleleg med 6, er $P(1)$ sann.

Induksjonssteg:

Induksjonsføresetnad: Anta at $P(k)$ er sann, dvs. $k^3 - k = 6m$ for eit heiltal $m$.

Å vise: $P(k+1)$: $(k+1)^3 - (k+1)$ er deleleg med 6.

Bevis:
$$(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1$$
$$= k^3 + 3k^2 + 2k$$
$$= (k^3 - k) + 3k^2 + 3k$$
$$= (k^3 - k) + 3k(k + 1)$$

No bruker vi at:
- $(k^3 - k) = 6m$ (induksjonsføresetnaden)
- $k(k+1)$ er produktet av to påfølgjande tal, så eitt av dei er partal. Dermed er $k(k+1)$ deleleg med 2, og $3k(k+1)$ er deleleg med 6.

Altså er $(k+1)^3 - (k+1) = 6m + 6 \cdot (\text{heiltal})$, som er deleleg med 6.

$$\blacksquare$$

La $P(n)$ vere formelen ovanfor.

Basissteg ($n = 0$):

VS: $r^0 = 1$

HS: $\displaystyle \frac{r^1 - 1}{r - 1} = \frac{r - 1}{r - 1} = 1$

$P(0)$ er sann.

Induksjonssteg:

Induksjonsføresetnad: $\displaystyle 1 + r + r^2 + \cdots + r^k = \frac{r^{k+1} - 1}{r - 1}$

Å vise: $\displaystyle 1 + r + r^2 + \cdots + r^k + r^{k+1} = \frac{r^{k+2} - 1}{r - 1}$

Bevis:
$$1 + r + \cdots + r^k + r^{k+1} = \frac{r^{k+1} - 1}{r - 1} + r^{k+1}$$

$$= \frac{r^{k+1} - 1 + r^{k+1}(r - 1)}{r - 1} = \frac{r^{k+1} - 1 + r^{k+2} - r^{k+1}}{r - 1}$$

$$= \frac{r^{k+2} - 1}{r - 1}$$

$$\blacksquare$$

Dette beviset inneheld ein subtil feil i induksjonssteget.

Feilen: Induksjonssteget fungerer berre når dei to mengdene $\{H_1, \ldots, H_k\}$ og $\{H_2, \ldots, H_{k+1}\}$ har ein felles hest.

Problemet oppstår ved $k = 1$:
- Mengd 1: $\{H_1\}$ (1 hest)
- Mengd 2: $\{H_2\}$ (1 hest)
- Desse mengdene har ingen felles hestar!

Dermed kan vi ikkje konkludere med at $H_1$ og $H_2$ har same farge.

Lærdomen: I induksjonsbevis må vi vere forsiktige med å sjekke at argumentet faktisk fungerer for alle verdiar av $k$, særleg for dei første verdiane. Her sviktar argumentet ved overgangen frå $n = 1$ til $n = 2$.

Steg 2: Vel bevismetode
Dette verkar som eit naturleg direkte bevis: Vi kan bruke at rasjonale tal er lukka under subtraksjon.

Steg 3: Skriv beviset

Bevis:

La $a$ og $a + b$ vere rasjonale tal.

Sidan $a$ er rasjonalt, finst heiltal $p_1, q_1$ med $q_1 \neq 0$ slik at $\displaystyle a = \frac{p_1}{q_1}$.

Sidan $a + b$ er rasjonalt, finst heiltal $p_2, q_2$ med $q_2 \neq 0$ slik at $\displaystyle a + b = \frac{p_2}{q_2}$.

Då er:
$$b = (a + b) - a = \frac{p_2}{q_2} - \frac{p_1}{q_1} = \frac{p_2 q_1 - p_1 q_2}{q_1 q_2}$$

Sidan $p_2 q_1 - p_1 q_2$ og $q_1 q_2$ er heiltal, og $q_1 q_2 \neq 0$, er $b$ rasjonalt.

$$\blacksquare$$

Steg 4: Sjekk beviset
- Vi brukte begge premissane
- Kvart steg er grunngitt
- Det er ingen spesialtilfelle vi har oversett

Kontraposisjon: Dersom $n$ er eit oddetal, så er $n^2$ eit oddetal.

Bevis:

Anta at $n$ er eit oddetal. Då finst eit heiltal $k$ slik at $n = 2k + 1$.

Vi reknar ut $n^2$:
$$n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$$

La $m = 2k^2 + 2k$. Då er $m$ eit heiltal, og $n^2 = 2m + 1$, som er forma til eit oddetal.

Altså er $n^2$ eit oddetal.

Konklusjon: Ved kontraposisjon har vi vist at dersom $n^2$ er eit partal, så er $n$ eit partal.

$$\blacksquare$$

a) Original: $\forall p > 2$ primtal: $p$ er oddetal.

Negasjon: Det finst eit primtal $p > 2$ som er partal.

(Merk: Negasjonen er usann, noko som stadfestar at originalen er sann.)

b) Original: $\exists x \in \mathbb{R}: x^2 < 0$

Negasjon: For alle reelle tal $x$ er $x^2 \geq 0$.

(Negasjonen er sann, så originalen er usann.)

c) Original: Regn $\Rightarrow$ Våt bakke

Negasjon: Det regnar OG bakken er ikkje våt.

(Bruker $\neg(P \Rightarrow Q) \Leftrightarrow (P \land \neg Q)$)

Føresetnad: Anta at det berre finst endeleg mange primtal på forma $4k + 3$. La desse vere $p_1, p_2, \ldots, p_n$.

Konstruksjon: Sjå på talet:
$$N = 4 \cdot p_1 \cdot p_2 \cdots p_n - 1 = 4(p_1 p_2 \cdots p_n) - 1$$

Observasjon 1: $N$ er på forma $4m - 1 = 4(m-1) + 3$, altså på forma $4k + 3$.

Observasjon 2: Eitkvart oddetal er anten på forma $4k + 1$ eller $4k + 3$.

Observasjon 3: Produktet av tal på forma $4k + 1$ er igjen på forma $4k + 1$:
$$(4a + 1)(4b + 1) = 16ab + 4a + 4b + 1 = 4(4ab + a + b) + 1$$

Konklusjon frå observasjonane: Sidan $N$ er på forma $4k + 3$, må $N$ ha minst ein primfaktor på forma $4k + 3$.

Motseiing: Men $N$ er ikkje deleleg med nokon av $p_1, \ldots, p_n$ (sidan $N \equiv -1 \pmod{p_i}$ for alle $i$). Så denne primfaktoren er ikkje i lista vår.

Konklusjon: Det finst uendeleg mange primtal på forma $4k + 3$.

$$\blacksquare$$