Feladat: prímek száma

Bizonyítsuk be, hogy végtelen sok prímszám van!

Megoldás: prímek száma

Használjuk az indirekt bizonyítás módszerét. Tegyük fel, hogy nincs végtelen sok. Ekkor felsorolható az összes prímszám, például növekedő sorrendben p₁, p₂, …, p_k. Vegyük az ezen k db szám szorzatánál 1-gyel nagyobb számot. Az így kapott n szám a felsorolt összes prímszám egyikével sem osztható (az osztási maradék mindig 1 lesz), ezért ez egy prímszám vagy a k db prímtől különböző prímtényezője van. Abból indultunk ki, hogy pontosan k db prímszám van, majd arra a következtetésre jutottunk, hogy lennie kell még legalább egy prímszámnak. Ez ellentmondás. Így az indirekt bizonyításunk alapján látható, hogy végtelen sok prímszám van. Példák az indirekt bizonyítás alkalmazhatóságára (négyzetgyök 2 irracionális, tételek megfordításának bizonyítása, ...)

Már beláttuk, hogy a nem racionális szám. Elevenítsük fel a bizonyítási módszer lényegét. Ha be akarjuk bizonyítani, hogy egy állítás igaz, akkor gondolkodhatunk a következő módon is. Tegyük fel, hogy az állítás nem igaz. Ha ebből a feltevésből ellentmondásra jutunk (vagy a kiinduló feltétellel, vagy egy axiómával, vagy egy tétellel), akkor az a feltevés helytelenségét, vagyis az állítás helyességét jelenti. Ezt a gondolatmenetet gyakran használjuk, a módszer neve indirekt bizonyítás.

Ez a bizonyítás lényegét tekintve megtalálható Eukleidész Elemek című könyvében.

Eukleidész személyéről szinte semmit nem tudunk. Különböző utalások alapján úgy gondoljuk, hogy i. e. 300 körül írhatta munkáját. Egy anekdota azt tartja, hogy Ptolemaiosz király megkérdezte Eukleidészt, miért nem lehet a matematikát egyszerűbben tanítani. A válasza állítólag ez volt: A matematikához nem vezet királyi út.

Eukleidész munkájában jelen van a bizonyítási igény. Az ember a mindennapi életben számolások és mérések segítségével sok matematikai ismeretre tett szert, de nem volt szüksége az elméleti bizonyításra. A bizonyítás szükségessége az olyan megfigyelések során alakult ki és erősödött meg, amelyeknek a helyes vagy helytelen voltát a gyakorlat nem tudta eldönteni (a irracionális szám, végtelen sok prímszám van).

Ha valakitől azt kérjük, hogy az előtte lévő 4 darab dobozba helyezzen el 5 darab golyót, és fogalmazza meg, hogy amikor ezt teszi, mit tart érdekesnek, akkor valószínűleg nevetségesen egyszerűnek érzi a kérésünket, és azonnal válaszol.

Lehet, hogy a válasza az lesz: „Az egyik dobozba kettőt teszek.” Ha mi minden elhelyezési lehetőségre gondolunk, akkor óvatosabban fogalmazunk, hiszen nem kell feltétlenül egy dobozba két golyót tennünk. Az is lehet, hogy mind az 5 golyót egy dobozba tesszük, az is lehet, hogy két dobozba 2-2 golyót teszünk, egybe 1 darabot, és egy dobozt üresen hagyunk.

Ha az elhelyezési lehetőségek lényegét röviden akarjuk megfogalmazni, akkor azt mondjuk: „Legalább egy dobozba legalább két golyót kell tennünk.”