6.6 Bevis og matematisk argumentasjon

Evighetsgarantien

For 2300 år siden skrev Euklid ned et argument for at det finnes uendelig mange primtall. Det argumentet er like gyldig i dag — ikke «fortsatt godt bekreftet», ikke «ennå ikke motbevist», men gyldig, punktum. Ingen naturvitenskap kan tilby noe lignende. Fysikkens teorier revideres når nye målinger kommer; Newtons mekanikk måtte vike for Einsteins. Men et matematisk bevis er en evighetsgaranti: en logisk argumentasjonsrekke som viser at en påstand må være sann, gitt premissene.

Hva hviler garantien på? Tre slags byggesteiner: aksiomer — grunnsannheter vi aksepterer uten bevis, definisjoner — presise avgrensninger av begrepene, og tidligere beviste teoremer — resultater som allerede har fått garantien. Fra disse bygges nye sannheter, steg for logisk steg, og et godt bevis kjennetegnes av presisjon, logisk sammenheng, fullstendighet og gyldige slutninger. Merk kontrasten til empirien: at $n^2 - n + 41$ er primtall for $n = 1, 2, 3, \ldots, 40$ er fristende bevismateriale — men ved $n = 41$ ryker det. En million eksempler beviser ingenting; ett gyldig argument beviser alt.

I dette kapittelet lærer du håndverket. Tre hovedmetoder: det direkte beviset, som marsjerer fra premiss til konklusjon; motsigelsesbeviset, som feller en påstand ved å vise at det motsatte er absurd; og induksjonsbeviset, dominorekken som når alle naturlige tall. I tillegg: kontraposisjonens elegante omvei, logikkens spilleregler — og kunsten å lese et bevis kritisk nok til å avsløre det når det jukser.

Det direkte beviset — marsjen fra premiss til konklusjon

Den mest naturlige bevisformen går rett fram: anta premissene, utfør logiske slutninger, land på konklusjonen. Drivstoffet er definisjonene — og tallteoriens to arbeidshester er presist definert: et heltall $n$ er et partall hvis $n = 2k$ for et heltall $k$, og et oddetall hvis $n = 2k + 1$.

Se hvordan definisjonene bærer et helt bevis. Påstand: summen av to partall er et partall. La $a$ og $b$ være partall. Per definisjon finnes heltall $m$ og $n$ med $a = 2m$ og $b = 2n$. Da er

$$a + b = 2m + 2n = 2(m + n)$$

og siden $m + n$ er et heltall, har summen formen $2 \cdot (\text{heltall})$ — et partall, per definisjon. $\blacksquare$ Hele kunsten ligger i å oversette påstanden til definisjonenes språk, regne, og oversette tilbake.

Samme marsj tar oddetallene: produktet av $a = 2m + 1$ og $b = 2n + 1$ er $4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1$ — formen til et oddetall, så oddetall ganger oddetall er oddetall. Og kvadratet av et partall: $(2k)^2 = 4k^2$, delelig med $4$, alltid.

Et siste eksempel viser hvordan et smart oppsett gjør beviset til ren regning. Påstand: summen av tre påfølgende heltall er delelig med 3. Kall tallene $n$, $n+1$ og $n+2$:

$$n + (n+1) + (n+2) = 3n + 3 = 3(n+1)$$

Ferdig — summen er tre ganger et heltall. Merk hvor mye arbeid valget av notasjon gjorde: «tre påfølgende heltall» ble til algebra som beviste seg selv. Slik ser direkte bevis ut når de lykkes: ingen triks, bare definisjoner, omskriving og en konklusjon som modnes fram.

Motsigelse og kontraposisjon — å bevise baklengs

Noen påstander lar seg vanskelig angripe forfra — særlig de negative: «$\sqrt{2}$ kan ikke skrives som brøk», «det finnes ikke et største primtall». Da snur vi våpenet: motsigelsesbeviset (reductio ad absurdum) antar det motsatte av påstanden, utleder konsekvenser — og viser at de kolliderer med seg selv. Da må antakelsen være gal, og påstanden står igjen som sann.

Antikkens juvel: $\sqrt{2}$ er irrasjonal. Anta det motsatte — at $\displaystyle \sqrt{2} = \frac{p}{q}$ for heltall uten felles faktorer (brøken maksimalt forkortet). Kvadrering gir $2q^2 = p^2$, så $p^2$ er et partall — og da må $p$ selv være det (et oddetall i kvadrat er odde). Skriv $p = 2k$: da er $2q^2 = 4k^2$, altså $q^2 = 2k^2$ — så $q$ er også partall. Men da har $p$ og $q$ felles faktor $2$, stikk i strid med at brøken var forkortet. Antakelsen kollapser; $\sqrt{2}$ er irrasjonal. $\blacksquare$ Pytagoreerne skal ha holdt dette resultatet hemmelig — det knuste troen på at alt er forhold mellom hele tall.

Euklids primtallsbevis følger samme dramaturgi. Anta endelig mange primtall $p_1, \ldots, p_n$, og se på $N = p_1 p_2 \cdots p_n + 1$. Divisjon med hvert $p_i$ gir rest $1$, så ingen av dem deler $N$ — men ethvert tall større enn $1$ har en primfaktor. Altså finnes et primtall utenfor listen som skulle være komplett. Motsigelse — primtallene tar aldri slutt. Og miniatyrutgaven: finnes et minste positive rasjonale tall $r$? Nei — $\displaystyle \frac{r}{2}$ er mindre, positivt og rasjonalt. Antakelsen motsier seg selv umiddelbart.

I slekt med motsigelsen er kontraposisjonen: «hvis $P$, så $Q$» er logisk ekvivalent med «hvis ikke $Q$, så ikke $P$». Skal du vise at $n^2$ partall medfører $n$ partall, er det lettere baklengs: anta $n$ odde, $n = 2k+1$; da er $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ — odde. Dermed: er $n^2$ partall, kan $n$ umulig være odde. Samme garanti, enklere marsjrute.

Induksjon — dominorekken

Hvordan beviser man noe for alle naturlige tall — uendelig mange tilfeller — med endelig mange ord? Svaret er matematikkens dominorekke. Still opp én brikke per tall. Hvis du vet at den første brikken faller, og at hver fallende brikke velter den neste, da faller alle sammen — hele den uendelige rekken.

Formelt: la $P(n)$ være en påstand om tallet $n$. Induksjonsprinsippet sier at $P(n)$ gjelder for alle $n \geq n_0$ hvis to ting er vist: basissteget — $P(n_0)$ er sann — og induksjonssteget — for hver $k \geq n_0$: hvis $P(k)$ er sann (dette kalles induksjonsantagelsen), så er $P(k+1)$ sann.

Klassikeren: $\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$. Basis ($n = 1$): venstre side $1$, høyre side $\displaystyle \frac{1 \cdot 2}{2} = 1$. ✓ Induksjonssteg: anta formelen for $n = k$, og legg til $k+1$:

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

— nøyaktig formelen for $n = k+1$. Brikke $k$ veltet brikke $k+1$, og formelen gjelder for alle $n$. $\blacksquare$ Legg merke til selve grepet: induksjonsantagelsen brukes til å erstatte den lange summen, og resten er algebra.

Samme maskineri beviser at $1 + 3 + 5 + \cdots + (2n-1) = n^2$ (steget er $k^2 + (2k+1) = (k+1)^2$ — andre kvadratsetning i hovedrollen), at $n^3 - n$ alltid er delelig med $6$ (skriv $(k+1)^3 - (k+1) = (k^3 - k) + 3k(k+1)$; første ledd er delelig med 6 per antagelse, og $k(k+1)$ er produktet av to naboer, alltid partall), og den geometriske summeformelen $\displaystyle 1 + r + \cdots + r^n = \frac{r^{n+1} - 1}{r - 1}$ som du kjenner fra rekkekapittelet — induksjon er nettopp verktøyet som gjorde den til teorem.

Å lese bevis med lupe — og logikkens spilleregler

Et bevis skal ikke bare skrives — det skal leses, kritisk. Strategien: identifiser premissene, konklusjonen og metoden; kontrollér hvert steg; sjekk hvor hver premiss brukes; og let etter spesialtilfeller der argumentet kan svikte. At dette ikke er pedanteri, viser tidenes mest lærerike falske bevis.

«Teorem»: alle hester har samme farge. «Bevis» ved induksjon: én hest har opplagt samme farge som seg selv. Anta så at enhver mengde med $k$ hester er ensfarget, og se på $k+1$ hester. Mengden $\{H_1, \ldots, H_k\}$ er ensfarget per antagelse; det samme er $\{H_2, \ldots, H_{k+1}\}$; og siden $H_2$ står i begge, har alle samme farge. $\blacksquare$? Hvor jukser det? Sett $k = 1$: mengdene er $\{H_1\}$ og $\{H_2\}$ — ingen felles hest, og limet ryker. Induksjonssteget svikter nøyaktig i overgangen fra én til to hester, og hele rekken står uveltet. Lærdommen: sjekk at steget holder for alle $k$, særlig de minste.

Slik granskning krever logikkens spilleregler. Konnektivene: $P \land Q$ (og), $P \lor Q$ (eller), $\neg P$ (ikke), $P \Rightarrow Q$ (hvis–så — usann bare når $P$ er sann og $Q$ usann) og $P \Leftrightarrow Q$ (hvis og bare hvis). De viktigste ekvivalensene: kontraposisjonen $(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)$, De Morgans lover $\neg(P \land Q) \Leftrightarrow \neg P \lor \neg Q$ og $\neg(P \lor Q) \Leftrightarrow \neg P \land \neg Q$, og implikasjonens negasjon $\neg(P \Rightarrow Q) \Leftrightarrow P \land \neg Q$ — å benekte «hvis det regner, blir bakken våt» er å påstå «det regner og bakken er tørr».

Kvantorene følger samme speillogikk: negasjonen av «for alle $x$ gjelder...» ($\forall$) er «det finnes en $x$ der det ikke gjelder» ($\exists$), og omvendt. Negasjonen av «det finnes et reelt tall med $x^2 < 0$» er «for alle reelle $x$ er $x^2 \geq 0$» — sann, så originalen er usann. Når du skal utvikle egne bevis, er dette verktøyene: forstå påstanden presist, velg metode — direkte når veien fram er farbar, motsigelse for negative påstander, induksjon for «alle $n$» — skriv hvert steg begrunnet, og les til slutt ditt eget bevis som din strengeste kritiker.

Oppsummering

Evighetsgarantien har fått sitt håndverk. Et bevis bygger nye sannheter av aksiomer, definisjoner og tidligere teoremer — og i motsetning til empirien gir det visshet: en million eksempler beviser ingenting, ett gyldig argument beviser alt.

Tre metoder bar kapittelet. Det direkte beviset marsjerte fra definisjon til konklusjon: partall $2k$ og oddetall $2k+1$ ga sum-, produkt- og delelighetsresultatene, og «tre påfølgende heltall» ble til $3(n+1)$ av seg selv. Motsigelsesbeviset antok det motsatte og lot antakelsen kollapse: $\displaystyle \sqrt{2} = \frac{p}{q}$ tvang både $p$ og $q$ til å være partall i en forkortet brøk, og Euklids $N = p_1 \cdots p_n + 1$ avslørte et primtall utenfor enhver komplett liste. Kontraposisjonen $(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)$ ga baklengsruten: «$n$ odde gir $n^2$ odde» beviste «$n^2$ partall gir $n$ partall». Og induksjonen veltet sin uendelige dominorekke med basissteg og induksjonssteg: sumformelen $\displaystyle \frac{n(n+1)}{2}$, oddetallssummen $n^2$, deleligheten $6 \mid n^3 - n$ og den geometriske rekkeformelen.

Til slutt lupen: hestefarge-«beviset» viste at induksjonssteg må holde for alle $k$ — det røk ved overgangen fra én til to. Logikkens regler — konnektiver, De Morgan, $\neg(P \Rightarrow Q) \Leftrightarrow P \land \neg Q$, kvantorbytte mellom $\forall$ og $\exists$ — er presisjonsverktøyene som gjør slik gransking mulig.

Dermed slutter R2 der matematikken begynner: ikke med å regne riktig, men med å vite hvorfor det er riktig. Det er fagets dypeste ferdighet — og nå er den din.