9.1 Direkte bevis og moteksempler

Tusen eksempler er ikke nok

Prøv dette: legg sammen de første oddetallene. $1 + 3 = 4$. $1 + 3 + 5 = 9$. $1 + 3 + 5 + 7 = 16$. Ser du mønsteret? Summene er kvadrattall! Du sjekker ti eksempler til – mønsteret holder. Hundre til. Fortsatt perfekt. Er det dermed bevist at det alltid gjelder?

Nei. Og det er her matematikken skiller seg fra alle andre fag. I naturvitenskapen styrker hvert eksperiment en hypotese; i matematikken kan tusen bekreftende eksempler ikke bevise en generell påstand – men ett eneste moteksempel kan knuse den. Det som gir sikkerhet, er et bevis: en logisk argumentrekke som viser at påstanden holder i alle tilfeller, også de uendelig mange du aldri rekker å sjekke.

I dette kapittelet lærer du bevisets grunnferdigheter: logikkens språk med implikasjoner og ekvivalenser, direkte bevis der du resonnerer deg fra forutsetning til konklusjon, og moteksempler – kunsten å avlive en usann påstand med ett velvalgt tall.

Logikkens språk: implikasjon og ekvivalens

Før vi kan bevise noe, må vi være presise på hva påstander sier. Den viktigste byggesteinen er implikasjonen: «hvis $P$, så $Q$», skrevet $P \Rightarrow Q$. Her kalles $P$ forutsetningen og $Q$ konklusjonen. For eksempel: «Hvis $n$ er delelig med 4, så er $n$ delelig med 2.» Sant – men legg merke til at pilen bare peker én vei! Den omvendte påstanden «hvis $n$ er delelig med 2, så er $n$ delelig med 4» er usann: $6$ er delelig med 2, men ikke med 4.

Når pilen faktisk går begge veier – både $P \Rightarrow Q$ og $Q \Rightarrow P$ – har vi en ekvivalens: $P \Leftrightarrow Q$, som leses «$P$ hvis og bare hvis $Q$». Å blande implikasjon og ekvivalens er en av de vanligste logiske feilene som finnes, i matematikk som i dagligliv.

To begreper til. Den kontrapositive av $P \Rightarrow Q$ er $\neg Q \Rightarrow \neg P$ – «hvis ikke $Q$, så ikke $P$» – og den er logisk ekvivalent med originalen. «Hvis det regner, er bakken våt» sier nøyaktig det samme som «hvis bakken ikke er våt, regner det ikke». Dette får stor betydning i kapittel 9.3.

Og terminologien rundt: at «$P$ er tilstrekkelig for $Q$» betyr $P \Rightarrow Q$ – det holder at $P$ skjer. At «$Q$ er nødvendig for $P$» betyr også $P \Rightarrow Q$ – uten $Q$, ingen $P$. Delelighet med 4 er tilstrekkelig for delelighet med 2; delelighet med 2 er nødvendig for delelighet med 4.

Direkte bevis – fra definisjon til konklusjon

Et direkte bevis går rett på sak: start med forutsetningen, og bygg en kjede av begrunnede steg fram til konklusjonen. Oppskriften: skriv forutsetningen tydelig, oversett ordene til algebra ved hjelp av definisjoner, regn, og vis at konklusjonen følger.

Definisjonene er nøkkelen – de er broen fra ord til symboler. For heltall: $n$ er et partall hvis det finnes et heltall $k$ slik at $n = 2k$, og et oddetall hvis $n = 2k + 1$ for et heltall $k$.

La oss bevise: summen av to partall er et partall. La $a$ og $b$ være partall. Per definisjon finnes heltall $m$ og $n$ slik at $a = 2m$ og $b = 2n$. Da er

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

Siden $m + n$ er et heltall, har summen formen $2 \cdot (\text{heltall})$ – et partall. $\square$ Legg merke til finessen: vi brukte forskjellige bokstaver $m$ og $n$. Hadde vi skrevet $a = 2k$ og $b = 2k$, hadde vi ufrivillig påstått at $a = b$!

Ett til: produktet av to oddetall er et oddetall. La $a = 2m + 1$ og $b = 2n + 1$. Da er

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

– formen $2k + 1$ med $k = 2mn + m + n$, altså et oddetall. $\square$ Mønsteret er alltid det samme: definisjon inn, algebra, definisjon ut. Et godt bevis definerer variablene sine, begrunner hvert steg, og avslutter gjerne med $\square$ eller «q.e.d.».

Moteksempler – ett tall kan velte alt

Hva med påstander som ikke er sanne? Her snur logikken seg elegant: for å motbevise en generell påstand («for alle $x$ gjelder...») trenger du bare ett eneste tilfelle der den feiler. Et slikt tilfelle kalles et moteksempel. Asymmetrien er verdt å dvele ved: ingen mengde bekreftende eksempler beviser en generell påstand, men ett moteksempel motbeviser den definitivt.

Ta påstanden: «Summen av to primtall er alltid et partall.» Den virker rimelig – $3 + 5 = 8$, $7 + 11 = 18$, $5 + 13 = 18$... Alle odde primtall gir jevn sum. Men primtallenes verden har en raring: $2$, det eneste jevne primtallet. Moteksempel: $2 + 3 = 5$ – to primtall med odde sum. Påstanden er usann. $\square$

Eller denne: «For alle reelle tall $a$ og $b$ gjelder $\sqrt{a^2 + b^2} = a + b$.» Den ser nesten ut som Pytagoras og kan friste i eksamensstress. Test $a = 3$, $b = 4$: venstre side er $\sqrt{9 + 16} = \sqrt{25} = 5$, høyre side er $7$. Siden $5 \neq 7$ er påstanden død. (Faktisk er det nettopp 3-4-5-trekanten som viser at hypotenusen er kortere enn summen av katetene.)

Strategien for moteksempeljakt: forstå nøyaktig hva påstanden krever, og prøv systematisk de «små» og «rare» tilfellene først – $0$, $1$, negative tall, og i primtallssammenheng alltid $2$. Randtilfellene er der generelle påstander oftest sprekker.

Identiteter og ulikheter – kvadratets makt

Mange bevis handler ikke om heltall, men om at en likhet eller ulikhet gjelder for alle verdier av variablene. Her finnes et knep som løser forbløffende mye: for å vise $A \geq B$, vis at $A - B \geq 0$ – gjerne ved å skrive differansen som et kvadrat, for kvadrater er aldri negative.

Klassikeren er ulikheten $a^2 + b^2 \geq 2ab$ for alle reelle tall $a$ og $b$. Vi regner ut differansen:

$$a^2 + b^2 - 2ab = (a - b)^2 \geq 0$$

Ferdig! Differansen er et kvadrat, altså aldri negativ, altså er $a^2 + b^2 \geq 2ab$. $\square$ Og beviset gir en bonusinnsikt på kjøpet: likhet gjelder nøyaktig når $(a-b)^2 = 0$, det vil si når $a = b$. (Dette er forresten AM-GM-ulikheten i forkledning – delt på 2 sier den at det aritmetiske gjennomsnittet av $a^2$ og $b^2$ er minst det geometriske.)

Et siste eksempel viser en annen teknikk – å dele opp i tilfeller. Påstand: produktet av tre påfølgende heltall $n(n+1)(n+2)$ er delelig med 6. Vi viser delelighet med 2 og 3 hver for seg. Med 2: blant tre påfølgende heltall er minst ett partall. Med 3: blant tre påfølgende heltall har de tre ulike rester ved divisjon med 3, så nøyaktig ett av dem er delelig med 3. Siden produktet er delelig med både 2 og 3, og $2$ og $3$ ikke har felles faktorer, er det delelig med 6. $\square$

To bevis, to teknikker – kvadratknepet og oppdeling i tilfeller. Begge er standardverktøy du vil møte igjen og igjen.

Oppsummering: sikkerhet, ikke sannsynlighet

Kvadrattallsmønsteret fra innledningen illustrerte matematikkens særpreg: eksempler kan aldri bevise, men ett moteksempel kan motbevise. Sikkerheten kommer fra beviset – den logiske kjeden fra forutsetning til konklusjon.

Du har lært logikkens grunnspråk: implikasjonen $P \Rightarrow Q$ med forutsetning og konklusjon, ekvivalensen $P \Leftrightarrow Q$ når pilen går begge veier, den logisk ekvivalente kontrapositiven $\neg Q \Rightarrow \neg P$, og begrepene tilstrekkelig og nødvendig – som begge beskriver samme implikasjon fra hver sin kant.

Det direkte beviset følger oppskriften definisjon–algebra–konklusjon, slik som da partallsdefinisjonen $n = 2k$ og oddetallsdefinisjonen $n = 2k+1$ gjorde påstander om summer og produkter til ren regning. Moteksempeljakten går motsatt vei: let ved randtilfellene – husk primtallet $2$! For ulikheter er kvadratknepet kongen: $A \geq B$ bevises ved $A - B = (\ldots)^2 \geq 0$, slik $a^2 + b^2 \geq 2ab$ falt på ett steg. Og husk de gode vanene: definer variablene, begrunn hvert steg, avslutt med $\square$. I de neste kapitlene utvider vi arsenalet med induksjon, kontrapositive bevis og kontradiksjon.