Indirekt bizonyítás

Az indirekt bizonyítás a bizonyítás kedvelt technikája. Ha be akarjuk bizonyítani, hogy valamilyen állítás igaz, megtagadjuk, feltételezzük, hogy a tagadása igaz, és megpróbálunk ellentmondásra jutni. A cél annak bizonyítása, hogy az általunk választott feltevés valamilyen képtelenséghez vezet.

Triviális példa

Legyen az állításunk: „nincs legkisebb pozitív racionális szám”. Ezt az állítást indirekt módon úgy bizonyítjuk, hogy először megtagadjuk: „van legkisebb pozitív racionális szám”, és ezt a számot jelöljük q-val. Ha q a legkisebb pozitív racionális szám, akkor nem tudunk nála kisebb pozitív racionális számot találni – mert akkor a q szám nem lenne a legkisebb.

Ezt használjuk ki az ellentmondás keresésekor. Ha mégis találunk a q-nál kisebb számot, amelyet szabadon választhatunk, akkor ellentmondásra jutottunk, és a megtagadott állítás nem igaz. Ha például a legkisebb számnak a 0,1-et választjuk, akkor látjuk, hogy a 0,01 kisebb. Aztán a 0,001 még kisebb, a 0,0001 megint kisebb, és így tovább. Elég a q számot elosztani tízzel, és kisebb számot kapunk. Tulajdonképpen elég bármilyen egynél nagyobb számmal elosztani, mondjuk kettővel – a q szám fele biztosan kisebb, mint az egész q szám.

Tehát a q/2 szám biztosan kisebb a q-nál, és egyben pozitív racionális szám. Ezzel ellentmondásra jutottunk a megtagadott állítással, vagyis a megtagadott állítás nem igaz, és így az eredeti, meg nem tagadott állítás igaz.

Érdekes számok

Az ellentmondás elvét egy klasszikus, mókás bizonyítás szemlélteti. Tegyük fel, hogy vannak olyan természetes számok, amelyek valamilyen módon érdekesek. Például a 2 érdekes szám, mert igaz, hogy 2 · 2 = 2 + 2, ez elég szokatlan tulajdonság. A 42 érdekes szám, mert ez a válasz mindenre. És így tovább. A kérdés: végtelen sok érdekes szám van?

Tegyük fel az ellenkezőjét, vagyis hogy csak véges sok érdekes szám van, és néhány szám érdektelen. Ezeket az érdektelen természetes számokat rendezzük az érdektelen számok halmazába. Most kiválasztjuk a legkisebb érdektelen számot. Egy pillanat, a legkisebb érdektelen szám? Ez elég érdekesen hangzik, nem? :-)

Ezzel ellentmondásra jutottunk, mert a legkisebb érdektelen szám valójában elég érdekes, tehát nem létezhet legkisebb érdektelen szám, így az érdektelen számok halmaza szükségszerűen üres.

Ez persze képtelenség, hiszen nincs rendesen definiálva, mi az érdekes szám, de maga a bizonyítás menete rendben van.

A prímszámok végtelenségének bizonyítása

Ebben a példában az előző fejezethez hasonló eljárást mutatunk meg, de ezúttal már minden szempontból helyes lesz.

A prímszám olyan szám, amely csak két különböző számmal osztható – önmagával és eggyel. Vedd észre, hogy a definíciónak az egyes nem felel meg, a kettes viszont megfelel.

A prímtényezős felbontás, más szóval faktorizáció, a természetes szám felbontása prímszámok szorzatára (az egyes kivételével). Ez a természetes számok elég érdekes tulajdonsága. Bármilyen természetes számot veszel (az egyes kivételével), igaz, hogy felbontható néhány (akár egyenlő) prímszám szorzatára. Példák:

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

A prímtényezős felbontásról szóló állítás neve a számelmélet alaptétele. Többek között azt mondja, hogy a felbontás egyértelmű, vagyis egy természetes számnak nem találunk két különböző prímtényezős felbontását. Továbbá csak a prímszámoknak van egyetlen számból álló prímtényezős felbontása – önmaguk. A hetes prímtényezős felbontása tehát a hetes szám. Ezeket a tényeket használjuk fel a következő állítás bizonyításának megszerkesztésekor.

Most bebizonyítjuk azt az állítást, hogy „végtelen sok prímszám van”. Az állítást megint megtagadjuk: „véges sok prímszám van”. Tegyük fel, hogy az

$$a_1,a_2,a_3,\dots ,a_n$$

számok sorozata az összes létező prímszámot jelenti. Ha ebben a sorozatban az összes prímszám benne van, akkor biztosan igaz, hogy már nem tudunk olyan számot találni, amely prímszám, és mégsem szerepel ebben a sorozatban. Az összes prímszám a sorozatban van, a sorozaton kívül már egyetlen prímszám sem fordulhat elő.

Ha ellentmondásra akarunk jutni, össze kell állítanunk valamilyen prímszámot, amely nincs ebben a sorozatban. Ebben segít nekünk a q szám. Úgy állítjuk össze, hogy a sorozat összes prímszámát összeszorozzuk, és hozzáadunk egyet:

$$q=a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1$$

Most meg kell mutatnunk, hogy ez a szám vagy prímszám, vagy valamilyen módon prímszámot generál. Tudjuk, hogy a q természetes szám, és hogy minden természetes szám kifejezhető prímszámok szorzataként. Ám egyetlen a_i prímszám sem osztja maradék nélkül a q számot, osztás után mindig egy marad. Ha például megpróbálnánk a q számot elosztani az a₂ prímszámmal, így járnánk:

$$\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1}{a_2}=\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1\cdot a_3\cdot a_4\cdot \dots \cdot a_n+\frac{1}{a_2}$$

A törtet először két törtre bontjuk. Az első törtben egyszerűsítünk a₂-vel, és marad valamilyen prímszámok szorzata, ami egyszerűen valamilyen másik, lényegtelen egész szám. A második törtben nincs mit egyszerűsíteni, ez a tört mindig valamilyen nem egész szám lesz (mert a nevező nem lehet egy, az egyes nem prímszám). Az összegük tehát olyan szám, amely nem egész, vagyis az a₂ prímszám nem osztja a q számot.

Ezzel bebizonyítottuk, hogy az a_n sorozat egyetlen prímszáma sem osztja a q számot. (Megjegyzés: bár ezt csak az a₂-re mutattuk meg, könnyen általánosítható, ha az a₂-t az általános a_i-re cseréljük.) De mivel minden természetes szám felbontható prímszámok szorzatára, léteznie kell más prímszámoknak is, amelyek nincsenek az a_n sorozatban, de a q szám faktorizációjában szerepelnek. Maga a q szám akár prímszám is lehet, és akkor a prímtényezős felbontás csak a q számot tartalmazza. Még egyszer tehát az utolsó gondolatmenet:

1. Minden természetes szám kifejezhető prímszámok valamilyen szorzataként.
2. A feltevés szerint az a_n sorozat tartalmazza az összes létező prímszámot.
3. Az első állítást úgy alakítjuk át, hogy minden természetes szám kifejezhető az a_n sorozat kiválasztott tagjainak szorzataként, mert az tartalmazza az összes prímszámot.
4. Bebizonyítottuk, hogy az a_n sorozat egyetlen száma sem osztja a q számot.
5. Ezzel ellentmondás keletkezett a feltevéssel → ha minden természetes számot fel kell tudnunk bontani prímszámok szorzatára, és az a_n sorozat nem tartalmaz egyetlen olyan számot sem, amely osztja a q számot, akkor léteznie kell más prímszámoknak, amelyek osztják a q számot, és a q szám prímtényezős felbontását alkotják.

Ezzel ellentmondásra jutottunk. A q szám prímtényezős felbontása olyan prímszámokat tartalmaz, amelyek nincsenek benne abban a sorozatban, amelyről azt feltételeztük, hogy az összes prímszámot tartalmazza. A megtagadott állítás tehát nem igaz, az eredeti, meg nem tagadott állítás igaz. Végtelen sok prímszám van.