9.1 Direkte bevis og moteksempler

Tusen eksempel er ikkje nok

Prøv dette: legg saman dei første oddetala. $1 + 3 = 4$. $1 + 3 + 5 = 9$. $1 + 3 + 5 + 7 = 16$. Ser du mønsteret? Summane er kvadrattal! Du sjekkar ti eksempel til – mønsteret held. Hundre til. Framleis perfekt. Er det dermed bevist at det alltid gjeld?

Nei. Og det er her matematikken skil seg frå alle andre fag. I naturvitskapen styrkjer kvart eksperiment ein hypotese; i matematikken kan tusen stadfestande eksempel ikkje bevise ein generell påstand – men eitt einaste moteksempel kan knuse han. Det som gjev tryggleik, er eit bevis: ei logisk argumentrekkje som viser at påstanden held i alle tilfelle, òg dei uendeleg mange du aldri rekk å sjekke.

I dette kapittelet lærer du grunnferdigheitene i bevis: logikkens språk med implikasjonar og ekvivalensar, direkte bevis der du resonnerer deg frå føresetnad til konklusjon, og moteksempel – kunsten å ta livet av ein usann påstand med eitt velvalt tal.

Logikkens språk: implikasjon og ekvivalens

Før vi kan bevise noko, må vi vere presise på kva påstandar seier. Den viktigaste byggjesteinen er implikasjonen: «viss $P$, så $Q$», skrive $P \Rightarrow Q$. Her kallar vi $P$ føresetnaden og $Q$ konklusjonen. Til dømes: «Viss $n$ er deleleg med 4, så er $n$ deleleg med 2.» Sant – men legg merke til at pila berre peikar éin veg! Den omvende påstanden «viss $n$ er deleleg med 2, så er $n$ deleleg med 4» er usann: $6$ er deleleg med 2, men ikkje med 4.

Når pila faktisk går begge vegar – både $P \Rightarrow Q$ og $Q \Rightarrow P$ – har vi ein ekvivalens: $P \Leftrightarrow Q$, som vert lese «$P$ viss og berre viss $Q$». Å blande implikasjon og ekvivalens er ein av dei vanlegaste logiske feila som finst, i matematikk som i daglegliv.

To omgrep til. Den kontrapositive av $P \Rightarrow Q$ er $\neg Q \Rightarrow \neg P$ – «viss ikkje $Q$, så ikkje $P$» – og han er logisk ekvivalent med originalen. «Viss det regnar, er bakken våt» seier nøyaktig det same som «viss bakken ikkje er våt, regnar det ikkje». Dette får stor verdi i kapittel 9.3.

Og terminologien rundt: at «$P$ er tilstrekkeleg for $Q$» tyder $P \Rightarrow Q$ – det held at $P$ skjer. At «$Q$ er nødvendig for $P$» tyder òg $P \Rightarrow Q$ – utan $Q$, ingen $P$. Delelegheit med 4 er tilstrekkeleg for delelegheit med 2; delelegheit med 2 er nødvendig for delelegheit med 4.

Direkte bevis – frå definisjon til konklusjon

Eit direkte bevis går rett på sak: start med føresetnaden, og bygg ei kjede av grunngjevne steg fram til konklusjonen. Oppskrifta: skriv føresetnaden tydeleg, omset orda til algebra ved hjelp av definisjonar, rekn, og vis at konklusjonen følgjer.

Definisjonane er nøkkelen – dei er brua frå ord til symbol. For heiltal: $n$ er eit partal viss det finst eit heiltal $k$ slik at $n = 2k$, og eit oddetal viss $n = 2k + 1$ for eit heiltal $k$.

Lat oss bevise: summen av to partal er eit partal. Lat $a$ og $b$ vere partal. Per definisjon finst heiltal $m$ og $n$ slik at $a = 2m$ og $b = 2n$. Då er

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

Sidan $m + n$ er eit heiltal, har summen forma $2 \cdot (\text{heiltal})$ – eit partal. $\square$ Legg merke til finessen: vi brukte ulike bokstavar $m$ og $n$. Hadde vi skrive $a = 2k$ og $b = 2k$, hadde vi ufriviljug påstått at $a = b$!

Eitt til: produktet av to oddetal er eit oddetal. Lat $a = 2m + 1$ og $b = 2n + 1$. Då er

$$\begin{aligned} a \cdot b &= (2m+1)(2n+1) \\ &= 4mn + 2m + 2n + 1 \\ &= 2(2mn + m + n) + 1 \end{aligned}$$

– forma $2k + 1$ med $k = 2mn + m + n$, altså eit oddetal. $\square$ Mønsteret er alltid det same: definisjon inn, algebra, definisjon ut. Eit godt bevis definerer variablane sine, grunngjev kvart steg, og avsluttar gjerne med $\square$ eller «q.e.d.».

Moteksempel – eitt tal kan velte alt

Kva med påstandar som ikkje er sanne? Her snur logikken seg elegant: for å motbevise ein generell påstand («for alle $x$ gjeld...») treng du berre eitt einaste tilfelle der han feilar. Eit slikt tilfelle kallar vi eit moteksempel. Asymmetrien er verd å dvele ved: ingen mengd stadfestande eksempel beviser ein generell påstand, men eitt moteksempel motbeviser han definitivt.

Ta påstanden: «Summen av to primtal er alltid eit partal.» Han verkar rimeleg – $3 + 5 = 8$, $7 + 11 = 18$, $5 + 13 = 18$... Alle odde primtal gjev jamn sum. Men primtala si verd har ein raring: $2$, det einaste jamne primtalet. Moteksempel: $2 + 3 = 5$ – to primtal med odde sum. Påstanden er usann. $\square$

Eller denne: «For alle reelle tal $a$ og $b$ gjeld $\sqrt{a^2 + b^2} = a + b$.» Han ser nesten ut som Pytagoras og kan freiste i eksamensstress. Test $a = 3$, $b = 4$: venstre side er $\sqrt{9 + 16} = \sqrt{25} = 5$, høgre side er $7$. Sidan $5 \neq 7$ er påstanden død. (Faktisk er det nettopp 3-4-5-trekanten som viser at hypotenusen er kortare enn summen av katetane.)

Strategien for moteksempeljakt: forstå nøyaktig kva påstanden krev, og prøv systematisk dei «små» og «rare» tilfella først – $0$, $1$, negative tal, og i primtalssamanheng alltid $2$. Randtilfella er der generelle påstandar oftast sprekk.

Identitetar og ulikskapar – kvadratets makt

Mange bevis handlar ikkje om heiltal, men om at ein likskap eller ulikskap gjeld for alle verdiar av variablane. Her finst eit knep som løyser forbløffande mykje: for å vise $A \geq B$, vis at $A - B \geq 0$ – gjerne ved å skrive differansen som eit kvadrat, for kvadrat er aldri negative.

Klassikaren er ulikskapen $a^2 + b^2 \geq 2ab$ for alle reelle tal $a$ og $b$. Vi reknar ut differansen:

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

Ferdig! Differansen er eit kvadrat, altså aldri negativ, altså er $a^2 + b^2 \geq 2ab$. $\square$ Og beviset gjev ei bonusinnsikt på kjøpet: likskap gjeld nøyaktig når $(a-b)^2 = 0$, det vil seie når $a = b$. (Dette er forresten AM-GM-ulikskapen i forkleding – delt på 2 seier han at det aritmetiske gjennomsnittet av $a^2$ og $b^2$ er minst det geometriske.)

Eit siste eksempel viser ein annan teknikk – å dele opp i tilfelle. Påstand: produktet av tre påfølgjande heiltal $n(n+1)(n+2)$ er deleleg med 6. Vi viser delelegheit med 2 og 3 kvar for seg. Med 2: blant tre påfølgjande heiltal er minst eitt partal. Med 3: blant tre påfølgjande heiltal har dei tre ulike restar ved divisjon med 3, så nøyaktig eitt av dei er deleleg med 3. Sidan produktet er deleleg med både 2 og 3, og $2$ og $3$ ikkje har felles faktorar, er det deleleg med 6. $\square$

To bevis, to teknikkar – kvadratknepet og oppdeling i tilfelle. Begge er standardverktøy du vil møte att om og om igjen.

Oppsummering: tryggleik, ikkje sannsyn

Kvadrattalsmønsteret frå innleiinga illustrerte særpreget til matematikken: eksempel kan aldri bevise, men eitt moteksempel kan motbevise. Tryggleiken kjem frå beviset – den logiske kjeda frå føresetnad til konklusjon.

Du har lært grunnspråket i logikken: implikasjonen $P \Rightarrow Q$ med føresetnad og konklusjon, ekvivalensen $P \Leftrightarrow Q$ når pila går begge vegar, den logisk ekvivalente kontrapositiven $\neg Q \Rightarrow \neg P$, og omgrepa tilstrekkeleg og nødvendig – som begge skildrar same implikasjon frå kvar si side.

Det direkte beviset følgjer oppskrifta definisjon–algebra–konklusjon, slik som då partalsdefinisjonen $n = 2k$ og oddetalsdefinisjonen $n = 2k+1$ gjorde påstandar om summar og produkt til rein rekning. Moteksempeljakta går motsett veg: leit ved randtilfella – hugs primtalet $2$! For ulikskapar er kvadratknepet kongen: $A \geq B$ vert bevist ved $A - B = (\ldots)^2 \geq 0$, slik $a^2 + b^2 \geq 2ab$ fall på eitt steg. Og hugs dei gode vanane: definer variablane, grunngjev kvart steg, avslutt med $\square$. I dei neste kapitla utvidar vi arsenalet med induksjon, kontrapositive bevis og kontradiksjon.