6.6 Bevis og matematisk argumentasjon

La $a$ og $b$ være to partall.

Siden $a$ er et partall, finnes det et heltall $m$ slik at $a = 2m$.

Siden $b$ er et partall, finnes det et heltall $n$ slik at $b = 2n$.

Vi beregner summen:
$$a + b = 2m + 2n = 2(m + n)$$

Siden $m + n$ er et heltall (summen av to heltall er et heltall), og $a + b = 2(m + n)$, er $a + b$ et partall per definisjon.

$$\blacksquare$$

La $a$ og $b$ være to oddetall.

Siden $a$ er et oddetall, finnes det et heltall $m$ slik at $a = 2m + 1$.

Siden $b$ er et oddetall, finnes det et heltall $n$ slik at $b = 2n + 1$.

Vi beregner produktet:
$$a \cdot b = (2m + 1)(2n + 1)$$

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

La $k = 2mn + m + n$. Da er $k$ et heltall, og vi har:
$$a \cdot b = 2k + 1$$

Dette er formen til et oddetall, så $a \cdot b$ er et oddetall.

$$\blacksquare$$

La $n$ være et partall.

Siden $n$ er et partall, finnes det et heltall $k$ slik at $n = 2k$.

Vi beregner $n^2$:
$$n^2 = (2k)^2 = 4k^2$$

Siden $k^2$ er et heltall, og $n^2 = 4k^2 = 4 \cdot k^2$, er $n^2$ delelig med 4.

$$\blacksquare$$

La de tre påfølgende heltallene være $n$, $n+1$ og $n+2$.

Vi beregner summen:
$$n + (n+1) + (n+2) = 3n + 3 = 3(n + 1)$$

Siden $n + 1$ er et heltall, og summen kan skrives som $3 \cdot (n+1)$, er summen delelig med 3.

$$\blacksquare$$

Antagelse: Anta at $\sqrt{2}$ er rasjonalt. Da kan vi skrive:
$$\sqrt{2} = \frac{p}{q}$$
der $p$ og $q$ er heltall uten felles faktorer (brøken er maksimalt forkortet) og $q \neq 0$.

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

Vi ganger med $q^2$:
$$2q^2 = p^2$$

Siden $p^2 = 2q^2$, er $p^2$ et partall. Men da må også $p$ være et partall (for hvis $p$ var oddetall, ville $p^2$ også vært oddetall).

Siden $p$ er et partall, kan vi skrive $p = 2k$ for et heltall $k$. Vi setter inn:
$$2q^2 = (2k)^2 = 4k^2$$

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

Siden $q^2 = 2k^2$, er $q^2$ et partall, og derfor er også $q$ et partall.

Motsigelse: Både $p$ og $q$ er partall, noe som betyr at de har felles faktor 2. Men vi antok at brøken var maksimalt forkortet! Dette er en selvmotsigelse.

Konklusjon: Antagelsen om at $\sqrt{2}$ er rasjonalt må være feil. Derfor er $\sqrt{2}$ irrasjonalt.

$$\blacksquare$$

Antagelse: Anta at det bare finnes endelig mange primtall. La disse være $p_1, p_2, p_3, \ldots, p_n$.

Betrakt tallet:
$$N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$$

Dette er produktet av alle primtall pluss 1.

Vi undersøker om $N$ er delelig med noen av primtallene $p_1, p_2, \ldots, p_n$:
- Når vi deler $N$ på $p_1$, får vi rest 1 (siden $N = p_1 \cdot (\text{noe}) + 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$ ikke delelig med noen av primtallene $p_1, \ldots, p_n$.

Men alle tall større enn 1 har minst en primfaktor. Siden $N > 1$ og $N$ ikke er delelig med noen av $p_1, \ldots, p_n$, må $N$ enten:
- Være et primtall selv (som ikke er i listen), eller
- Ha en primfaktor som ikke er i listen

Motsigelse: Uansett har vi funnet et primtall som ikke er i listen over alle primtall. Dette motsier antagelsen.

Konklusjon: Det finnes uendelig mange primtall.

$$\blacksquare$$

Antagelse: Anta at det finnes et minste positivt rasjonalt tall $r$.

Betrakt tallet $\displaystyle \frac{r}{2}$.

Vi observerer at:
- $\displaystyle \frac{r}{2}$ er rasjonalt (kvotienten av to rasjonale tall er rasjonalt)
- $\displaystyle \frac{r}{2} > 0$ (halvparten av et positivt tall er positivt)
- $\displaystyle \frac{r}{2} < r$

Motsigelse: Vi har funnet et positivt rasjonalt tall $\displaystyle \frac{r}{2}$ som er mindre enn $r$. Men $r$ var antatt å være det minste. Dette er en selvmotsigelse.

Konklusjon: Det finnes ikke noe minste positivt rasjonalt tall.

$$\blacksquare$$

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

Basissteg ($n = 1$):

Venstre side: $1$

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

Siden venstre side = høyre side, er $P(1)$ sann.

Induksjonssteg:

Induksjonsantagelse: Anta at $P(k)$ er sann for en vilkårlig $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:
$$\begin{aligned} &1 + 2 + 3 + \cdots + k + (k+1) \\ = {}&\underbrace{\frac{k(k+1)}{2}}_{\text{induksjonsantagelsen}} + (k+1) \end{aligned}$$

$$= \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)$ være påstanden: $1 + 3 + 5 + \cdots + (2n-1) = n^2$

Basissteg ($n = 1$):

Venstre side: $1$

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

$P(1)$ er sann.

Induksjonssteg:

Induksjonsantagelse: 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:
$$\begin{aligned} &1 + 3 + 5 + \cdots + (2k-1) + (2k+1) \\ = {}&k^2 + (2k+1) \end{aligned}$$

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

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

$$\blacksquare$$

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

Basissteg ($n = 1$):

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

Siden 0 er delelig med 6, er $P(1)$ sann.

Induksjonssteg:

Induksjonsantagelse: Anta at $P(k)$ er sann, dvs. $k^3 - k = 6m$ for et heltall $m$.

Å vise: $P(k+1)$: $(k+1)^3 - (k+1)$ er delelig 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)$$

Nå bruker vi at:
- $(k^3 - k) = 6m$ (induksjonsantagelsen)
- $k(k+1)$ er produktet av to påfølgende tall, så ett av dem er partall. Dermed er $k(k+1)$ delelig med 2, og $3k(k+1)$ er delelig med 6.

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

$$\blacksquare$$

La $P(n)$ være formelen ovenfor.

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:

Induksjonsantagelse: $\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 inneholder en subtil feil i induksjonssteget.

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

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

Dermed kan vi ikke konkludere at $H_1$ og $H_2$ har samme farge.

Lærdommen: I induksjonsbevis må vi være forsiktige med å sjekke at argumentet faktisk fungerer for alle verdier av $k$, spesielt for de første verdiene. Her svikter argumentet ved overgangen fra $n = 1$ til $n = 2$.

Velg bevismetode
Dette virker som et naturlig direkte bevis: Vi kan bruke at rasjonale tall er lukket under subtraksjon.

Skriv beviset

Bevis:

La $a$ og $a + b$ være rasjonale tall.

Siden $a$ er rasjonalt, finnes heltall $p_1, q_1$ med $q_1 \neq 0$ slik at $\displaystyle a = \frac{p_1}{q_1}$.

Siden $a + b$ er rasjonalt, finnes heltall $p_2, q_2$ med $q_2 \neq 0$ slik at $\displaystyle a + b = \frac{p_2}{q_2}$.

Da 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}$$

Siden $p_2 q_1 - p_1 q_2$ og $q_1 q_2$ er heltall, og $q_1 q_2 \neq 0$, er $b$ rasjonalt.

$$\blacksquare$$

Sjekk beviset
- Vi brukte begge premissene
- Hvert steg er begrunnet
- Det er ingen spesialtilfeller vi har oversett

Kontraposisjon: Hvis $n$ er et oddetall, så er $n^2$ et oddetall.

Bevis:

Anta at $n$ er et oddetall. Da finnes et heltall $k$ slik at $n = 2k + 1$.

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

La $m = 2k^2 + 2k$. Da er $m$ et heltall, og $n^2 = 2m + 1$, som er formen til et oddetall.

Altså er $n^2$ et oddetall.

Konklusjon: Ved kontraposisjon har vi vist at hvis $n^2$ er et partall, så er $n$ et partall.

$$\blacksquare$$

a) Original: $\forall p > 2$ primtall: $p$ er oddetall.

Negasjon: Det finnes et primtall $p > 2$ som er partall.

(Merk: Negasjonen er usann, noe som bekrefter at originalen er sann.)

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

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

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

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

Negasjon: Det regner OG bakken er ikke våt.

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

Svar: a) Det finnes et primtall større enn 2 som er et partall. b) For alle reelle tall $x$ er $x^2 \geq 0$. c) Det regner, og bakken er ikke våt.

Antagelse: Anta at det bare finnes endelig mange primtall på formen $4k + 3$. La disse være $p_1, p_2, \ldots, p_n$.

Konstruksjon: Betrakt tallet:
$$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å formen $4m - 1 = 4(m-1) + 3$, altså på formen $4k + 3$.

Observasjon 2: Ethvert oddetall er enten på formen $4k + 1$ eller $4k + 3$.

Observasjon 3: Produktet av tall på formen $4k + 1$ er igjen på formen $4k + 1$:
$$\begin{aligned} &(4a + 1)(4b + 1) = 16ab + 4a + 4b + 1 \\ = {}&4(4ab + a + b) + 1 \end{aligned}$$

Konklusjon fra observasjonene: Siden $N$ er på formen $4k + 3$, må $N$ ha minst en primfaktor på formen $4k + 3$.

Motsigelse: Men $N$ er ikke delelig med noen av $p_1, \ldots, p_n$ (divisjon med $p_i$ gir rest $p_i - 1$, fordi $4p_1p_2 \cdots p_n$ er delelig med $p_i$). Så denne primfaktoren er ikke i listen vår.

Konklusjon: Det finnes uendelig mange primtall på formen $4k + 3$.

$$\blacksquare$$