Bevis og bevisteknikk

I denne artikkelen gir vi en kortfattet introduksjon til forskjellige bevis og bevisteknikker.

Et matematisk bevis består av en påstand og en kjede argumenter som ender opp med å slå fast om påstanden er sann eller usann.

Vi tar bare for oss påstander som enten er sanne eller usanne, såkalte utsagn. Eksempler på slike påstander er "vinkelsummen i en trekant er 180 grader" og "april har 31 dager", som er henholdsvis et sant og et usant utsagn. Påstander som "jordbær er godt" eller "Gerhardsen gjorde en god jobb som statsminister" er subjektive, og vi kan ikke bevise om de er sanne eller usanne.

Når vi formulerer en påstand, må vi passe på å være nøyaktige, slik at påstanden ikke kan misforstås. Vanlig språk er ofte dårlig egnet til å formulere påstander fordi dagligtalen vår er full av unøyaktigheter. Ta for eksempel påstanden "Mellom 20 og 25 finnes tre heltall med to primfaktorer". Betyr "tre heltall" nøyaktig tre heltall eller minst tre heltall? Betyr "to primfaktorer" nøyaktig to primfaktorer, eller minst to primfaktorer? Betyr "mellom 20 og 25" at 20 og 25 regnes med eller ikke?

For å unngå slike unøyaktigheter er det utviklet en egen matematisk terminolog som er fri for tvetydigheter. For eksempel kan vi uttrykke at "et tall, $n$, er mellom 20 og 25" som $n \in [20, 25]$, som betyr at 20 og 25 skal telle med, eller $n \in \langle 20, 25 \rangle$, som betyr at 20 og 25 ikke skal telle med. En påstand som utelukkende er uttrykt gjennom matematiske symboler kan imidlertid være tung å lese, så i denne artikkelen bruker vi vanlig språk når det ikke kan føre til misforståelser. For eksempel uttrykker vi den nevnte påstanden som "Det finnes nøyaktig tre heltall, $n \in[20, 25]$, som består av nøyaktig to primfaktorer."

En beviskjede kan være kort eller lang.

Eksempel 1:

  1. Påstand: $4$ er et primtall.
    Bevis for at påstanden er uriktig: $4$ kan faktoriseres som $2 \cdot 2$ og er derfor ikke et primtall.
  2. Påstand: Det finnes ingen heltallige $n, x, y, z$ slik at $x^n + y^n = z^n$ når $n > 2$.
    Beviset for denne påstanden er 150 sider langt og tok 7 år å utarbeide. Påstanden sto ubevist i over 350 år.

I eksempel 1 er det er underforstått at vi vet hva et primtall er, og at vi vet at et tall som kan faktoriseres ikke er et primtall. Det vil som regel være slik at vi i et bevis må anta at en del begreper er kjent på forhånd.

Ikke alle påstander kan bevises, og det kan bevises at enkelte påstander ikke kan bevises.

Så skal vi se litt nærmere på forskjellige typer bevis.

Uttømmende bevis

En av de enkleste bevisformene er uttømmende bevis, der vi viser at en påstand er riktig ved å undersøke alle muligheter som inngår i påstanden.

Eksempel 2:

Påstand: Det finnes nøyaktig tre heltall, $n \in[20, 25]$, som består av nøyaktig to primfaktorer.

Bevis: Vi faktoriserer heltallene mellom $20$ og $25$:

$20 = 2 \cdot 2 \cdot 5$

$21 = 3 \cdot 7$

$22 = 2 \cdot 11$

$23 = 23$

$24 = 2 \cdot 2 \cdot 2 \cdot 3$

$25 = 5 \cdot 5$

Vi ser at $21$$22$ og $25$ og ingen andre av tallene oppfyller kravet, og påstanden er derved bevist.

Oppgave 1:

Bevis følgende påstand: Det finnes nøyaktig ett heltall, $n \in[20, 25]$, som består av nøyaktig fire primfaktorer.

Se løsningsforslag

Dersom antall muligheter som må undersøkes blir mange, blir uttømmende bevis tungvint, og helt umulig hvis en påstand gjelder et uendelig antall muligheter, noe som ofte er tilfelle.

Hvis et uttømmende bevis ikke undersøker alle muligheter, er det ugyldig. Det er en vanlig feil å tro at en har bevist en påstand ved å ramse opp noen eksempler på at den er riktig.

Eksempel 3:

Påstand: Alle tall på formen $2^p – 1$ er primtall hvis $p$ er et primtall.

Ugyldig bevis: Vi tester påstanden for en del primtall:

$2^2 – 1 = 3$. Primtall.

$2^3 – 1 = 7$. Primtall.

$2^5 – 1 = 31$. Primtall.

$2^7 – 1 = 127$. Primtall.

$2^{13} – 1 = 8191$. Primtall.

$2^{17} – 1 = 131071$. Primtall.

$2^{19} – 1 = 524287$. Primtall.

Skulle metoden i eksempel 3 ført fram, måtte vi testet alle primtall som finnes. Og siden det finnes uendelig mange, lar det seg ikke gjøre. Påstanden er heller ikke riktig, som vi skal se i eksempel 5.

Eksempel 4:

Påstand: Summen av tre etterfølgende heltall er alltid lik tre ganger det midterste tallet. For eksempel er

$3 + 4 + 5 = 12 = 3 \cdot 4$

$11 + 12 + 13 = 36 = 3 \cdot 12$

$-13 + (-12) + (-11) = -36 = 3(-12)$

Ugyldig bevis: Vi tester påstanden for 10 000 sekvenser av tre etterfølgende heltall i et regneark, og finner ut at påstanden stemmer.

Påstanden i eksempel 4 er riktig, men uansett hvor mange eksempler vi prøver ut i et regneark, vil vi ikke få et et gyldig bevis. Vi sannsynliggjør imidlertid påstanden, noe som betyr at den er vel verd å utforske nærmere, og at vi kanskje kan finne et bevis for den. Som vi skal se i eksempel 11, kan vi bekrefte denne påstanden ved et enkelt, algebraisk bevis.

Bevis ved moteksempel

Det er altså ikke nok å bare sjekke en del av mulighetene som inngår for å bevise at en påstand er riktig. Derimot er det nok med ett enkelt moteksempel for å bevise at en påstand er uriktig, altså motbevise den.

Eksempel 5:

Påstand: Alle tall på formen $2^p – 1$ er primtall hvis $p$ er et primtall.

Moteksempel: $11$ er et primtall, men $2^{11} – 1 = 2047$, er ikke er et primtall. $2047$ kan faktoriseres som $23 \cdot 89$.

Oppgave 2:

Bevis at følgende påstand er uriktig: Alle sammensatte tall større enn hundre består av minst tre primfaktorer.

Se løsningsforslag

Eksempel 6:

Påstand: Alle primtall er oddetall.

Moteksempel: 2 er et primtall, men ikke et oddetall.

Påstanden i eksempel 6 er gyldig for alle andre primtall enn 2. Det finnes altså uendelig mange tall den er riktig for, men bare ett den ikke er riktig for. Allikevel betyr dette ene moteksempelet at påstanden er uriktig. Med en liten modifikasjon blir imidlertid påstanden riktig: "Alle primtall unntatt 2 er oddetall".

Dueslagprinsippet

Et enkelt bevis som går ut på opptelling er det såkalte dueslagprinsippet: Hvis $m$ objekter blir fordelt på $n$ avdelinger, og $m > n$, vil minst én avdeling inneholde mer enn ett objekt. Hvis det for eksempel er 110 duer i et dueslag med 100 seksjoner, må det finnes seksjoner med mer enn 1 due.

Eksempel 7:

Påstand: I ei bygd med 50 gårder der den største besetningen er på 40 dyr, er det minst to gårder som har samme besetning.

Bevis: Siden det er flere gårder enn dyr i den største besetningen, sier dueslagprinsippet at minst to gårder har samme besetning.

Oppgave 3:

Vi roter etter sokker innerst i klesskapet, der det ligger 5 forskjellige typer. Hvor mange må vi rote fram for å være sikre på å ha to like?

Se løsningsforslag

Kontrapositivt bevis

Vi har to påstander, A og B. Hvis B følger av A, betyr et kontrapositivt bevis at vi, gitt påstanden ikke-B, konkluderer med ikke-A.

Eksempel 8:

Alle sauene til Ola Oppigarden er svarte.

Her følger påstand B, at en sau er svart, av påstand A, at sauen tilhører Ola Oppigarden.

Påstand ikke-B, at en sau ikke er svart medfører da ikke-A, at sauen ikke tilhører Ola Oppigarden.

Det er imidlertid ikke slik at hvis B følger av A, så følger A av B.

Eksempel 9:

Alle sauene til Ola Oppigarden er svarte. Men hvis vi ser en sau som er svart, påstand B, trenger den ikke tilhøre Ola Oppigarden, påstand A.

Påstanden i neste eksempel er en variant av påstanden i eksempel 3, men denne påstanden er riktig, uten at vi går inn på beviset.

Eksempel 10:

Korrekt påstand: Hvis $n$ er et sammensatt tall, er $2^n – 1$ et sammensatt tall.

Av dette følger at hvis $2^n – 1$ ikke er et sammensatt tall, er $n$ ikke et sammensatt tall.

"Ikke sammensatt tall" er det samme som "primtall", så vi har altså at:
Hvis $2^n – 1$ er et primtall, er $n$ et primtall.

En påstand som er bevist, kalles gjerne et teorem, og en påstand som umiddelbart følger av et teorem kalles et korollar. Vi har altså:

Teorem: Hvis $n$ er et sammensatt tall, er $2^n – 1$ et sammensatt tall.

Ved kontrapositivt bevis følger da:

Korollar: Hvis $2^n – 1$ er et primtall, er $n$ et primtall.

Hvis vi feilaktig prøver å si at A følger av B hvis B følger av A, får vi den uriktige påstanden fra eksempel 3.

Algebraisk bevis

Hvis vi skal bevise en påstand der vi ikke kan bruke et uttømmende bevis, kan et algebraisk bevis være et alternativ. I et algebraisk bevis innfører vi symboler som er allmenngyldige.

Eksempel 11:

I eksempel 4 framsatte vi en påstand om at summen av tre etterfølgende heltall alltid er lik tre ganger det midterste tallet.

Det finnes uendelig heltall, så et uttømmende bevis er utelukket, og vi bruker et algebraisk bevis:

Kaller vi tallet i midten for $a$, vil de tre etterfølgende tallene være $a – 1$, $a$ og $a+ 1$. Summen av disse blir $(a – 1) + a + (a + 1) = a + a + a – 1 + 1 = 3a$. Vi ser at uansett hvilken verdi $a$ representerer, blir summen tre ganger denne verdien. Påstanden er derved bevist.

Eksempel 12:

Påstand: Summen av to partall er et partall.

Det finnes uendelig mange partall, så et uttømmende bevis er utelukket, og vi bruker et algebraisk bevis:

Et partall er et tall på formen $2t$, der $t$ er et helt tall. Summen av to heltall kan skrives som $2n + 2m = 2(n + m)$. Siden $n + m$ er et heltall, ser vi at produktet er på formen $2t$, og derved et partall.

I eksempel 12 har vi brukt $2n$ som symbol for det ene tallet og $2m$ som symbol for det andre. Hadde vi brukt samme symbol for begge, for eksempel $2t$, ville det betydd at de to tallene var like. Vi har følgende prinsipp:

$\fbox{To tall som kan være ulike må representeres med forskjellige symboler.}$

Det er en vanlig feil å bruke samme symbol for to tall som kan være ulike.

Eksempel 13:

Feilaktig påstand: Produktet av to partall er et kvadrattall.

Feilaktig bevis: Et partall er et tall på formen $2t$, der $t$ er et helt tall. Produktet av to partall kan skrives som $2t \cdot 2t = 2 \cdot 2 \cdot t \cdot t = 2^2 \cdot t^2 = (2t)^2$. Og vi ser at produktet kan skrives som kvadratet av $2t$.

Problemet er at $t$ er brukt som symbol for to tall som kan være ulike. Vi har egentlig bare bevist det opplagte, at et tall multiplisert med seg selv er et kvadrattall. Med forskjellige symboler får vi $2m \cdot 2n = 2 \cdot 2 \cdot m \cdot n = 2^2 \cdot m \cdot n$, som ikke er et kvadrattall hvis $m$ og $n$ er ulike.

Men vi sier ikke at to tall representert med forskjellige symboler nødvendigvis må være ulike. Det er mulig at de er ulike, men det er også mulig at de er like. Beviset i eksempel 12 er like gyldig for to forskjellige tall, for eksempel $2 + 4$, som for to like tall, for eksempel $2 + 2$.

Oppgave 4:

Bevis at summen av to oddetall er et partall.

Se løsningsforslag

Bevis ved selvmotsigelse

I et bevis ved selvmotsigelse antar vi at det motsatte av det vi skal bevise er riktig, og demonstrerer at dette fører til en selvmotsigelse. Denne prosessen kalles også "reductio ad absurdum".

Eksempel 14:

Påstand: Det finnes ingen hele, positive tall, $a$ og $b$, slik at $a^2 – b^2 = 10$.

Bevis: Vi antar det motsatte, at det finne to slike tall. Bruker vi tredje kvadratsetning baklengs på venstre side, får vi $(a + b)(a – b) = 10$.

$10$ kan skrives som produktet $2 \cdot 5$. Da må vi ha $(a + b) = 5$ og $(a – b) = 2$. (Siden $a$ og $b$ er positive tall, må summen bli det største tallet og differansen det minste.)

Summerer vi de to likningene, får vi $2a = 7 \Rightarrow a = \frac{\displaystyle 7}{\displaystyle 2}$.

$a$ er altså ikke et heltall, noe som er en selvmotsigelse siden vi i utgangspunktet forutsatte at $a$ var et heltall.

$10$ kan også skrives som produktet $1 \cdot 10$. Da må vi ha $(a + b) = 10$ og $(a – b) = 1$. Summerer vi de to likningene, får vi $2a = 11 \Rightarrow a = \frac{\displaystyle 11}{\displaystyle 2}$.
$a$ er heller ikke her et heltall, og vi har igjen en selvmotsigelse.

$10$ kan ikke skrives som et produkt av heltall på noen andre måter, og påstanden er derved bevist ved selvmotsigelse.

I eksempel 14 benyttet vi også prinsippet fra et uttømmende bevis. Det fantes to måter å skrive $10$ som et produkt av heltall på, og vi tok for oss begge to.

Oppgave 5:

Finn feilen i følgende resonnement:

Vi påstår at det ikke finnes hele, positive tall, $a$ og $b$, slik at $a^2 – b^2 = 12$.

Som bevis bruker vi selvmotsigelse, etter prinsippet fra eksempel 14:

$12$ kan skrives som produktet $3 \cdot 4$. Da må vi ha $(a + b) = 4$ og $(a – b) = 3$. Summerer vi de to likningene, får vi $2a = 7 \Rightarrow a = \frac{\displaystyle 7}{\displaystyle 2}$.

$a$ er altså ikke et heltall, noe som er en selvmotsigelse siden vi i utgangspunktet forutsatte at $a$ var et heltall.

$12$ kan skrives som produktet $1 \cdot 12$. Da må vi ha $(a + b) = 12$ og $(a – b) = 1$. Summerer vi de to likningene, får vi $2a = 11 \Rightarrow a = \frac{\displaystyle 11}{\displaystyle 2}$.

$a$ er heller ikke her et heltall, og vi har igjen en selvmotsigelse.

Påstanden er derved bevist ved selvmotsigelse.

Se løsningsforslag

Induksjonsbevis

Et induksjonsbevis brukes typisk i forbindelse med påstander om heltall, og går i to trinn:

  1. Vi viser at påstanden er riktig for et bestemt heltall, typisk $1$.
  2. Vi viser at hvis påstanden er riktig for et vilkårlig heltall, $n$, er den også riktig for $n + 1$.

Hvis vi i trinn 1 for eksempel viser at påstanden er gyldig for $n_1 = 1$, følger det av trinn 2 at den også er gyldig for $n_2 = n_1 + 1 = 2$. Av trinn 2 følger så igjen at den da også er gyldig for $n_3 = n_2 + 1= 2 + 1 = 3$. Siden vi kan fortsette med trinn 2 i all evighet, har vi derved vist at påstanden er gyldig for alle $n$.

Eksempel 15:

Vi skal bevise at summen av alle hele tall fra og med $1$ til og med $n$ er lik $\frac{\displaystyle n(n + 1)}{\displaystyle 2}$.

For eksempel er $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = \frac{\displaystyle 10(10 + 1)}{\displaystyle 2} = 55$.

Vi viser da først at påstanden er riktig for $n = 1$. På venstre side av likhetstegnet får vi $1$. På høyre side får vi $\frac{\displaystyle 1(1 + 1)}{\displaystyle 2} = 1$ så påstanden er riktig for $n = 1$.

Vi antar så at påstanden er riktig for en gitt $n$:

$1 + 2 + 3 + \cdots + n = \frac{\displaystyle n(n + 1)}{\displaystyle 2}$.

Og vi må så vise at

$1 + 2 + 3 + \cdots + n + (n + 1) = \frac{\displaystyle (n + 1)((n + 1) + 1)}{\displaystyle 2}$.

Legger vi til et ledd til på begge sider av likhetstegnet, får vi

$1 + 2 + 3 + \cdots + n + (n + 1) = \frac{\displaystyle n(n + 1)}{\displaystyle 2} + (n + 1)$.

Vi skriver uttrykket på høyre side som en enkelt brøk:

$\frac{\displaystyle n(n + 1)}{\displaystyle 2} + (n + 1) = \frac{\displaystyle n(n + 1) + 2(n + 1)}{\displaystyle 2}$.

Vi regner ut parenteser og trekker sammen like ledd:

$\frac{\displaystyle n(n + 1) + 2(n + 1)}{\displaystyle 2} = \frac{\displaystyle n^2 + 3n + 2}{\displaystyle 2}$.

Vi faktoriserer andregradsuttrykket:

$\frac{\displaystyle n^2 + 3n + 2}{\displaystyle 2} = \frac{\displaystyle(n + 1)(n + 2)}{\displaystyle 2}$.

Som ved en liten omforming blir:

$\frac{\displaystyle(n + 1)((n + 1) + 1)}{\displaystyle 2}$.

Som er det uttrykket vi var ute etter. Vi har derved bevist at når påstanden er gyldig for $n$, er den også gyldig for $n + 1$. Siden den er gyldig for $1$, er den følgelig gyldig for $2$, og siden den er gyldig for $2$, er den gyldig for $3$, og så videre i all evighet.

Kilder