Matematički dokaz

Dokaz, u matematičkom smislu, jest logičko-matematički postupak kojim se dokazuje teorema. U njemu se smiju koristiti samo aksiomi i prethodno dokazane teoreme. Dokazi su primjeri iscrpnog deduktivnog rasuđivanja koji uspostavljaju logičku sigurnost, koje treba razlikovati od empirijskih argumenata ili neiscrpnog induktivnog rasuđivanja koji uspostavljaju "razumno očekivanje". Jedan od popularnijih načina dokazivanja teorema je metoda "pretpostavimo suprotno". U toj metodi, u kojoj se pokušava dokazati tvrdnja A, pretpostavi se da vrijedi tvrdnja ne A i traži se kontradikcija (tvrdnja koja je u suprotnosti s već prethodno dokazanom teoremom ili aksiomom). Među drugim načinima je i izvod. Kreće se od pretpostavke teoreme, pa se svi njeni uvjeti primijene na pojam na koji se teorema odnosi i tvrdnja teoreme izvede se logično-matematički.

Animacija dokaza Pitagorine teoreme, koja pokazuje kako se preuređivanjem trougla može pokazati da su površine a² + b² i c² iste.

Metode dokazivanja

Izravni dokaz

Glavni članak: Izravni dokaz

U direktnom dokazu, zaključak se uspostavlja logičkim kombinovanjem aksioma, definicija i ranijih teorema. Naprimjer, direktni dokaz se može koristiti da se dokaže da je zbir dva parna cijela broja uvijek paran:

Razmotrimo dva parna cijela broja x i y. Pošto su parni, mogu se zapisati kao x = 2a i y = 2b, respektivno, za neke cijele brojeve a i b. Tada je zbir x + y = 2a + 2b = 2(a+b). Stoga x+y ima 2 kao faktor i po definiciji je paran. Dakle, zbir bilo koja dva parna cijela broja je paran.

Ovaj dokaz koristi definiciju parnih cijelih brojeva, cjelobrojna svojstva zatvaranja pri sabiranju i množenju i distributivnosti.

Dokaz matematičkom indukcijom

Glavni članak: Matematička indukcija

Uprkos svom nazivu, matematička indukcija je metoda dedukcije, a ne oblik induktivnog zaključivanja. U dokazu matematičkom indukcijom dokazuje se jedan "osnovni slučaj" i dokazuje se "pravilo indukcije" koje utvrđuje da svaki proizvoljni slučaj implicira sljedeći slučaj. Pošto se u principu pravilo indukcije može primjenjivati više puta (počevši od dokazanog osnovnog slučaja), slijedi da su svi (obično beskonačno mnogi) slučajevi dokazivi. Time se izbjegava dokazivanje svakog slučaja pojedinačno. Varijanta matematičke indukcije je dokaz beskonačnim spuštanjem, koji se može koristiti naprimjer, za dokazivanje iracionalnosti kvadratnog korijena iz dva.

Uobičajena primjena dokaza matematičkom indukcijom je da se dokaže da svojstvo za koje se zna da vrijedi za jedan broj vrijedi za sve prirodne brojeve: Neka N = {1, 2, 3, 4, ...} skup prirodnih brojeva, i neka je P(n) matematički iskaz koji uključuje prirodni broj n koji pripada N tako da

• (i) P(1) je tačno, tj. P(n) je tačno za n = 1.
• (ii) P(n+1) je tačno kad god je P(n) tačno, tj. P(n) je tačno znači da je P(n+1) tačno.
• Tada je P(n) istinit za sve prirodne brojeve n.

Naprimjer, indukcijom možemo dokazati da su svi pozitivni cijeli brojevi oblika 2n − 1 neparni. Neka P(n) predstavlja "2n − 1 je neparan":

(i) n = 1, 2n − 1 = 2(1) − 1 = 1, a 1 je neparan, jer ostavlja ostatak od 1 kada se podijeli sa 2. Dakle, P(1) je istinit.

(ii) Za bilo koje n, ako je 2n − 1 neparan (P(n)), onda (2n − 1) + 2 također mora biti neparan, jer dodavanje 2 neparnom broju rezultira neparnim brojem. Ali je (2n − 1) + 2 = 2n + 1 = 2(n+1) − 1, pa je 2(n+1) − 1 neparan (P(n+1)). Dakle, P(n) implicira P(n+1).

Dakle, 2n − 1 neparan, za sve pozitivne cijele brojeve n.

Kraći izraz "dokaz indukcijom" često se koristi umjesto "dokaz matematičkom indukcijom".

Dokaz kontrapozicijom

Glavni članak: Kontrapozicija

Dokaz kontrapozicijom zaključuje tvrdnju "ako je p onda q" uspostavljanjem logički ekvivalentne kontrapozitivne izjave: "ako nije q onda nije p".

Naprimjer, kontrapozicija se može koristiti da se utvrdi da je, dat cijeli broj x, ako je x ² paran, onda je x paran: Pretpostavimo da x nije paran. Tada je x neparan. Proizvod dva neparna broja je neparan, pa je x ² = x ⋅ x neparan. Dakle, x ² nije paran. Dakle, ako je x ² paran, pretpostavka mora biti netačna, tako da x mora biti paran.

Dokaz kontradikcijom

Glavni članak: Dokaz kontradikcijom

U dokazu kontradikcijom, poznatom i pod latinskom frazom reductio ad absurdum (svođenjem na apsurd), pokazuje se da ako se pretpostavi da je neka izjava istinita, dolazi do logičke kontradikcije, pa stoga izjava mora biti lažna. Poznati primjer uključuje dokaz da je ${\sqrt {2}}$ iracionalan broj:

Pretpostavimo da je ${\sqrt {2}}$ racionalni broj. Tada bi se moglo napisati u najnižim terminima kao ${\sqrt {2}}$=:${\frac {a}{b}}$, gdje su a i b cijeli brojevi različiti od nule bez zajedničkog faktora. Dakle, b ${\sqrt {2}}$=a. Kvadriranjem obje strane dobije se 2b² = a². Pošto je izraz na lijevoj strani cijeli broj višekratnik od 2, desni izraz je po definiciji djeljiv sa 2. To jest, a² je paran, što implicira da a također mora biti paran, kao što se vidi u gornjoj propoziciji (dokaz putem kontrapozicije). Dakle, možemo napisati a = 2c, gdje je c također cijeli broj. Zamjena u originalnu jednačinu daje 2b² = (2c)² = 4c². Dijeljenjem obje strane sa 2 dobije se b² = 2c². Ali onda, istim argumentom kao i prije, 2 dijeli b², tako da b mora biti paran. Međutim, ako su a i b oba parni, oni imaju 2 kao zajednički faktor. Ovo je u suprotnosti s našom prethodnom tvrdnjom da a i b nemaju zajednički faktor, pa moramo zaključiti da je ${\sqrt {2}}$ iracionalni broj.

Da parafraziramo: ako bi se moglo napisati ${\sqrt {2}}$ kao razlomak, ovaj razlomak se nikada ne bi mogao napisati najnižim pojmovima, jer se 2 uvijek može rastaviti iz brojnika i nazivnika.