Bevis ved kontradiksjon - vist med et eksempel

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

Bevis ved kontradiksjon - vist med et eksempel

Innlegg sEirik » 07/03-2007 21:28

I bevistypen bevis ved kontradiksjon, også kalt "Reductio ad absurdum". Prinsippet bak et slikt bevis er at vi gjør nøyaktig én antakelse. Deretter ser vi hva denne antakelsen fører til, og vi ender opp med en selvmotsigelse som ikke kan forklares på annen måte enn at den opprinnelige antakelsen er feil, derfor vil det motsatte av antakelsen være riktig. Med denne teknikken kan man bevise mye rart, blant annet at det finnes uendelig mange primtall - hvis man antok at det bare fantes endelig mange, ville man få en selvmotsigelse, derfor må det nødvendigvis finnes uendelig mange primtall.

Et enkelt, hverdagslig eksempel på et resonnement ved kontradiksjon:

1) Vi antar at jeg er kongen av Nebraska.
2) Det medfører at jeg kan bestemme alt jeg vil der, også hva staten skal hete.
3) Men jeg ville aldri vært så dum at jeg kalte en plass for Nebraska, æsj for et teit navn. Jeg ville ha kalt staten Monarkiet Bondeland.
4) Siden Nebraska nå engang heter Nebraska, og det umulig kunne hett det hvis jeg var konge der, betyr det at den opprinnelige antakelsen (1) er feil. Jeg er altså dessverre ikke kongen av Nebraska.

Kanskje et litt barnslig eksempel, men det viser tankegangen på en enkel måte.
Nå skal vi bruke et kontradiksjonsbevis til å vise at [tex]\sqrt{2}[/tex]er et irrasjonelt tall. Beviset bygger på det faktum at [tex]a^2[/tex] er et oddetall => [tex]a[/tex] er et oddetall, og [tex]a^2[/tex]er et partall => [/tex]a[/tex] er et oddetall. Dette kan man bevise ved å bruke definisjonen på et partall, som er 2n, der n er et heltall, og et oddetall er 2n-1, der n er et heltall. Til beviset:

(1) Vi antar at [tex]\sqrt{2}[/tex] er et rasjonelt tall.

(2) Det betyr at det må finnes to naturlige tall a og b, slik at [tex]\frac{a}{b} = \sqrt{2}[/tex]. Dette har vi fra definisjonen av et rasjonelt tall.

(3) Brøken er forkortet så mye som det går an, slik at a og b ikke har noen felles faktor.

Vi kvadrerer begge sider, og får
[tex]\frac{a^2}{b^2} = 2[/tex]

(4) [tex]a^2 = 2b^2[/tex]

Vi ser at [tex]2b^2[/tex] er et partall, siden 2 er en faktor. Da må også [tex]a^2[/tex] være et partall;

(5) Da må også a være et partall.

(6) Siden a er et partall, finnes det et heltall n slik at a = 2n. Vi setter inn:

[tex](2n)^2 = 2b^2[/tex]

[tex]4n^2 = 2b^2[/tex]

[tex]2n^2 = b^2[/tex]

(7) Siden [tex]2n^2[/tex] helt klart er et partall, er også [tex]b^2[/tex] et partall,

(8) Da er også [tex]b[/tex] et partall.

(9) Men (5) og (8) sier at både a og b er partall, det betyr at brøken faktisk kan forkortes mer. Men dette strider med (3), altså har vi fått en logisk kontradiksjon - en selvmotsigelse. Vi har bare gjort én antakelse, og det er (1) - at [tex]\sqrt{2}[/tex] er rasjonelt. Det betyr at antakelsen er feil, ergo er [tex]\sqrt{2}[/tex] et irrasjonelt tall.

Til slutt i bevis er det vanlig å avslutte med Q.E.D., som er latin og betyr "det som skulle bevises", eller et firkant-symbol. "∎"
sEirik offline
Guru
Guru
Brukerens avatar
Innlegg: 1551
Registrert: 12/06-2006 20:30
Bosted: Oslo

Innlegg Magnus » 07/03-2007 22:37

Magnus offline
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Bosted: Trondheim

Innlegg Maple » 07/03-2007 23:08

Hvis noen lurer på hvorfor det (nesten åpenbare) faktum at a^2 er partall medfører at a er partall, så kan de lese dette.

Aritmetikkens fundamentalteorem sier at alle tall større enn 1 kan skrives som et produkt av primtall. Siden 2 er det eneste primtallet som er partall, og en vet at det å multiplisere to oddetall blir et oddetall, så MÅ tallet 2 være blant primtallene som utgjøre a^2. Så da får vi at a^2 er 2*2=4 multiplisert med ytterlige eventuelle primtall. Og siden et oddetall multiplisert med et partall er et partall, så må a være et partall.

(Eventuelt kan man si at a er partall siden oddetallig a ville medført oddetallig a^2...)

Det å bevise at to oddetall multiplisert med hverandre er et oddetall kan føres tilbake til at et partall multiplisert med et oddetall blir et partall. For en kan skrive produktet N*M som (N-1)*M+N, som da blir et partall (forutsatt at et partall multiplisert med et oddetall er et partall) pluss et oddetall, som åpenbart er et oddetall.

Det å bevise at et oddetall multiplisert med et partall blir et partall, kan bevises med artimetikkens fundamentalteorem det også. For da blir jo (N-1)*M = 2 multiplisert med (odde) primtall.

Men kan noen hjelpe meg her? Jeg har forklart at et oddetall ganger et partall er et partall, og at et oddetall ganger er oddetall er et oddetall, men bevisene biter hverandre i halen (for de som ser det)!

Altså beviset for at et partall ganger et oddetall er et partall avhenger av at et oddetall ganger et oddetall er et oddetall, og omvendt.
Maple offline
Cayley
Cayley
Innlegg: 96
Registrert: 23/02-2007 21:46

Innlegg sEirik » 07/03-2007 23:15

Oddetall ganger partall:

[tex](2n+1) \cdot 2m = 2mn + 2m = 2m(n+1)[/tex] som har 2 som faktor, og er partall.

Oddetall ganger oddetall:

[tex](2n+1) +cdot (2m+1)= 2nm + 2n + 2m + 1 = 2(nm+n+m + 1) - 1[/tex] som er et oddetall.
sEirik offline
Guru
Guru
Brukerens avatar
Innlegg: 1551
Registrert: 12/06-2006 20:30
Bosted: Oslo

Innlegg Maple » 07/03-2007 23:35

Det koker vel ned til det faktum at alt som har 2 som faktor ER er partall. Jeg syns det er et rart resultat.

Alt som har 3 som faktor kan være både partall og oddetall.
Maple offline
Cayley
Cayley
Innlegg: 96
Registrert: 23/02-2007 21:46

Innlegg etse » 07/03-2007 23:54

Alt som har 2 som en faktor er partall.
Si det slik, hvis ikke alt som har 2 som en faktor er primtall vil dette bety at det fins et tall n som ganger med 2 blir et oddetal som vi kaller a
her er n og a elementær i naturlige tall
[tex]2n = a[/tex]
Men siden a skulle være et oddetal, så er 2n også et oddetal, noe som betyr at vi ikke kan dele detp å 2 og få et naturlig tall. vi deler på 2 på begge sider.
[tex]\frac{2n}{2} = \frac{a}{2}[/tex]
vi ser vi kan forkorte 2n
[tex]n = \frac{a}{2}[/tex]
men dette motsier det vi sa tidligere om at n var et oddetall, siden oddetall ikke kan deles på 2 og gi et naturlig tall.

Alt som har 3 som faktor men ikke 2 er oddetall, alt som har 2 som faktor og så mange ekstra faktorer du vil er partall =)
etse offline
Dirichlet
Dirichlet
Innlegg: 191
Registrert: 24/11-2006 15:07

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 2 gjester