Mi a bizonyítás

A bizonyítások az egész matematika alapkövei: a bizonyítások segítségével néhány kis kavicsból egy egész piramist felépíthetsz, ráadásul fejre állítva.

A bizonyítások értelme

A bizonyításoknak a matematikában több okból van értelmük. A fő ok az, hogy bizonyítás nélkül nem tudunk megerősíteni semmilyen gondolatot vagy hipotézist, amely eszünkbe jut. Hihetnénk például, hogy a prímszámok száma véges, de ha nincs rá bizonyításunk, ez csak üres állítás marad. Másrészt a be nem bizonyított állításoknak is van értelmük a matematikában (és máshol is). Egyszerűen azt mondjuk, hogy ha igaz az a feltevés, hogy véges sok prímszám van, akkor igaz… valamilyen másik elmélet.

Aztán ne csodálkozzunk, ha valaki egy idő után bebizonyítja, hogy végtelen sok prímszám van, ahogy azt alább meg is mutatjuk, és az egész elméletünk összeomlik, mint egy kártyavár. A bizonyításoknak köszönhetően tehát olyan kártyavárakat építhetünk, amelyek soha nem omlanak össze.

Azért tanítják az iskolákban a bizonyításokat, mert aki megérti a bizonyítást, az az adott anyagot is megérti. Általában nehezen érthetjük meg alaposan az anyagot anélkül, hogy a bizonyításokat értenénk. Az „értenénk” szót teljesen szándékosan emeltem ki: ha ugyanis a vizsga előtti napon bemagolod a bizonyításokat, másnap pedig csak kihányod magadból a papírra, az nem jelenti azt, hogy közelebb kerültél a téma megértéséhez.

A bizonyítások tehát egy anyag tanulásakor arra a kérdésre válaszolnak, hogy „miért működik ez így?” Ha megérted, miért működik valami, könnyebben megjegyzed, és idővel az adott anyagot határozottan jobban fogod érteni, mint az, aki „betöltöm – kiöntöm” módszerrel tanulta. A kérdés az, hogy ez-e a célod.

Mi a bizonyítás

Hogy mi a bizonyítás, azt a matematikai logikában formálisan például a szintaktikai következtetéssel definiálják, nekünk azonban sokkal egyszerűbb meghatározás is elég.

Minden bizonyítás elején kell lennie egy állításnak, amelyet be akarunk bizonyítani. Ezt az állítást jelöljük a ϕ mágikus szimbólummal. Ez egy görög betű, amelyet „fí”-nek olvasunk. Továbbá szükségünk lesz axiómák és feltevések valamilyen halmazára, jelöljük Ax-szel, amelyek segítségével a ϕ állítást bebizonyítjuk. Az axiómák halmaza olyasmi, amit már tudunk, amiről feltételezzük, hogy igaz. Lehetnek ezek olyan dolgok, mint például „minden páros szám osztható kettővel”. Ezenkívül ez a halmaz tartalmazhat például kifejezések átalakítására szolgáló képleteket, amelyeket valahol máshol már bebizonyítottak, és feltételezzük, hogy érvényesek, például:

$$(a+b{)}^2=a^2+2ab+b^2;a,b\in \mathbb{R}$$

Most fokozatosan átalakítjuk az Ax halmaz állításait egészen addig, amíg megkapjuk a ϕ állítást. Minden átalakításnak logikailag helyesnek kell lennie, meg kell felelnie az alapvető ítéletlogikának. Ha például az előző képletet akarnánk bebizonyítani, úgy járunk el, hogy a

$$(a+b{)}^2$$

kifejezést ekvivalens átalakításokkal addig alakítjuk, amíg megkapjuk a jobb oldalon álló kifejezést. Bemutatom:

$$(a+b{)}^2=(a+b)\cdot (a+b)=a\cdot a+a\cdot b+b\cdot a+b\cdot b=$$

$$=a\cdot a+2ab+b\cdot b=a^2+2ab+b^2$$

Az első lépésben a hatványt szorzatként írtuk fel, a másodikban felbontottuk a zárójeleket, a harmadikban összevontuk az egyenlő tagokat, az utolsó lépésben pedig a szorzatot hatványként írtuk fel. Minden lépés valamilyen elemi átalakítás volt, amelyet megengedhettünk magunknak, és feltételezzük, hogy mindegyik ilyen elemi átalakítás benne van az Ax halmazban.

Fontos, hogy minden átalakításnak érvényesnek kell lennie, valami olyanból kell kiindulnia, amit már ismerünk. A matematikai bizonyítás olyasmi, mint az evolúció – apró lépésekben alakítjuk át az egyik kifejezést egy másikká.

Triviális bizonyítások

A triviális bizonyítás (vagy más néven nyilvánvaló bizonyítás) olyan bizonyítás szakkifejezése, amely nem fér el a táblán, ezért kihagyják, a diák pedig házi feladatként megtanulja a jegyzetből. :-) Most komolyan – a triviális bizonyítások olyan bizonyítások, amelyek jellemzően egyetlen triviális lépésben következnek valamilyen definícióból.

Próbáljuk ki egy példán: vegyük a pozitív egész számok halmazát, vagyis az ℕ⁺ = {1, 2, 3, …} számhalmazt. Most azt mondhatjuk, hogy minden

$$\frac{q}{p};q,p\in {\mathbb{N}}^{+}$$

alakú tört érvényes, vagyis nem találunk olyan q, p számpárt, amelyre a megadott törtnek ne lenne értelme. Hogyan bizonyítjuk be? Először rá kell jönnünk, mikor nincs értelme egy törtnek. A törtnek nincs értelme, ha a nevezőben nulla áll (nullával nem oszthatunk). Be kell tehát bizonyítanunk, hogy p ≠ 0 minden lehetséges p-re. Mi azonban tudjuk, hogy a p-t a pozitív egész számok közül vesszük, amelyeket úgy definiáltunk, hogy ℕ⁺ = {1, 2, 3, …}. A pozitív egész számok halmaza nem tartalmazza a nullát, ezért a p szám mindig különbözni fog a nullától.

$$\mathrm{\forall }p\in {\mathbb{N}}^{+}:p\ne 0$$

És készen is van a bizonyítás. Tudjuk, hogy ha a tört számlálója és nevezője is pozitív egész szám, akkor a tört érvényes.

A triviális bizonyítások általában tényleg triviálisak, de csak akkor, ha ismered a környező kontextust. Ha például nem érted a halmaz fogalmát, vagy nem tudod, mit jelent az, hogy a p eleme az ℕ⁺ halmaznak, akkor ez a bizonyítás sem volt triviális számodra. A triviális bizonyításokat tehát nem az jellemzi, hogy egyszerűek, hanem inkább az, hogy rövidek, és egyszerűen következnek valamilyen (tetszőlegesen nehéz) kontextusból.

Ellenpélda

Az ellenpélda talán a legegyszerűbb módja annak bizonyítására, hogy egy állítás nem igaz. Fontos ez a szó: nem. Az ellenpélda ugyanis rámutathat egy esetre, amikor a megadott állítás nem teljesül, de általában még akárhány példa sem elég, ha végtelen sok elem van, amelyek közül tesztelhetünk.

Példa: „minden természetes szám nagyobb tíznél”. Hogyan bizonyítjuk be, hogy ez nem igaz? Az állításunk ellenpéldája például az ötös szám. Az öt természetes szám, és nem nagyobb tíznél. Az állítást nem bizonyíthatjuk be úgy, hogy felsorolunk néhány tíznél nagyobb természetes számot. Nem mondhatod, hogy „a 11, 12, 13, 123 és 5345 természetes számok nagyobbak 10-nél, tehát az állítás igaz”. Ez nem megy. Ezzel csak kiválasztottunk néhány példát, amelyekre az állításunk teljesül, de ez semmit sem mond azokról a számokról, amelyeket említésre sem méltattunk.

Második példa: minden két méternél magasabb férfinak barna vagy kék a szeme. Feltételezem, hogy kevesen tudnak ellenpéldát találni. Mit mond ez az állításról? Hát, semmit. Ha nem tudunk ellenpéldát találni, az nem jelenti szükségszerűen, hogy az állítás igaz. Az ellenpélda valahol létezhet, csak éppen nem tudjuk megtalálni. Az, hogy nem tudunk ellenpéldát találni, nem bizonyítja, hogy az adott állítás igaz.

Direkt bizonyítás

A bizonyítás alaptípusa a direkt bizonyítás. Szárazon követjük a definíciót, és az eredeti állítást addig alakítjuk, amíg megkapjuk azt az állítást, amelyet meg akarunk kapni. Jellemzően olyan állítást akarunk bizonyítani, amelynek A ⇒ B alakú implikáció a formája, ahol A valamilyen kiindulópont, feltevés, B pedig az az állítás, amelyet le akarunk vezetni, be akarunk bizonyítani. Ha igaz az A állítás, akkor igaz a B állítás is. Gyakran csak a B állítás van megadva, vagyis az, amit be kell bizonyítani, az A állítást pedig nekünk kell megfelelően megválasztanunk.

Ezután következik az eljárás, amelyben implikációkkal további állításokat vezetünk le, és az utolsó állítás a B állítás. Sematikusan így írható fel:

$$A\Rightarrow A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow \dots \Rightarrow A_n\Rightarrow B$$

Példaként bebizonyítjuk, hogy igaz az

$$a>1\Rightarrow a^2>1$$

állítás. Most lépésről lépésre:

1. Mivel a>1, biztosan igaz az is, hogy a>0, és az is, hogy a ≠ 0 (valójában csak gyengítjük a feltételt).
2. Mivel a nem nulla, és pozitív, az egész egyenlőtlenséget nyugodtan megszorozhatjuk az a változóval. Ha az a nulla lenne, a szigorú egyenlőtlenség nem maradna meg (azt kapnánk, hogy 0>0), ha negatív lenne, meg kellene fordítanunk az egyenlőtlenség irányát. Az a változóval való szorzás után az a²>a kifejezést kapjuk.
3. Ebben a pillanatban tudjuk, hogy a>1, és azt is, hogy a²>a. Ha ezt a két kifejezést összerakjuk, a következőt kapjuk: a²>a>1.
4. Innen már csak elhagyjuk a középső kifejezést, és megvan az a²>1 kifejezés. Ezt azért tehettük meg, mert a nagyobb egynél, és a² nagyobb a-nál. Ha a² nagyobb a-nál, az a pedig egyszersmind nagyobb egynél, akkor a² biztosan nagyobb egynél.

Szimbolikusan így írhatnánk fel:

$$a>1\Rightarrow a>0\Rightarrow a^2>a\Rightarrow a^2>a>1\Rightarrow a^2>1.$$

Kontrapozíciós bizonyítás

A kontrapozíciós bizonyítás már jobban kihasználja az implikáció tulajdonságait. Ha egy A ⇒ B alakú állítást kell bizonyítanunk, használhatjuk az implikáció kontrapozícióját, és bebizonyíthatjuk, hogy

$$\mathrm{\neg }B\Rightarrow \mathrm{\neg }A.$$

Ez az eljárás néha előnyösebb lehet, mint például a direkt bizonyítás. Hasonló módszert használ az indirekt bizonyítás, amelyre minden kontrapozíciós bizonyítás visszavezethető. Próbáljuk meg kontrapozícióval bebizonyítani az állítást:

$$a-b=0\Rightarrow a=b.$$

Most felírjuk az implikáció kontrapozícióját:

$$\begin{array}{rcl}\mathrm{\neg }(a=b)& \Rightarrow & \mathrm{\neg }(a-b=0)\\ a\ne b& \Rightarrow & a-b\ne 0\end{array}$$

Ha a ≠ b, felbonthatjuk a b-t összegre, b = a + x, ahol az x a b szám távolságát jelenti az a számtól. A kifejezés így változik:

$$a\ne (a+x)\Rightarrow a-(a+x)\ne 0;x\ne 0$$

Kivonjuk azokat az a változókat, amelyeket lehet:

$$0\ne x\Rightarrow -x\ne 0;x\ne 0$$

Mivel x ≠ 0, ezért −x ≠ 0 is, tehát az implikáció igaz. Az állítást bebizonyítottuk, ezáltal igaz az eredeti állítás is:

$$a-b=0\Rightarrow a=b.$$

További bizonyítási technikák például a már említett indirekt bizonyítás, illetve a bizonyítás teljes indukcióval.

További források

• Matematikai bizonyítás a Wikipédián