A következő három fejezet nem része az előadásnak, de a további fejezetek megértéséhez mindenképpen javasolt az elolvasása. A fejezetek anyaga a matematika BsC-s hallgatók számára készült Bevezető analízis I. jegyzet és Bevezető analízis II. példatár anyagán alapul.
1.1. A logika alapfogalmai
Azokat a mondatokat, amelyekhez józan ésszel az igaz vagy hamis logikai értékek valamelyikét hozzárendelhetjük, állításoknak nevezzük.
Nem minden mondat állítás.
Példák olyan mondatokra, amelyek nem állítások:
Miért nem süt a nap?
Ez a mondat nem igaz.
Példák állításokra:
Most nem süt a nap. (Lehet igaz is, lehet hamis is.)
A logaritmus függvény a pozitív számokon van értelmezve. (Igaz.)
A logaritmus függvény a negatív számokon van értelmezve. (Hamis.)
Az állításokat logikai műveletekkel kapcsolhatjuk össze. Az alábbiakban és két állítást jelöl.
Definíció: A logikai műveletek és jelölésük.
konjunkció
(az és művelet),
,
és
diszjunkció
(a vagy művelet),
,
vagy
negáció
(tagadás),
vagy ,
nem
implikáció
(következtetés),
,
ha akkor
ekvivalencia
akkor és csak akkor, ha
A logikai műveletek értelmezése:
pontosan akkor igaz, ha is igaz, és is igaz.
pontosan akkor hamis, ha is hamis, és is hamis.
vagy pontosan akkor igaz, ha hamis.
pontosan akkor hamis, ha igaz, és hamis.
pontosan akkor igaz, ha mindkét állítás igaz vagy mindkét állítás hamis.
Megjegyzés:
A pontosan akkor igaz ... azt jelenti, hogy minden más esetben hamis.
A pontosan akkor hamis ... azt jelenti, hogy minden más esetben igaz.
A vagy-gyal összekötött állítás akkor is igaz, ha mindkét rész állítás igaz. A matematikában az úgynevezett megengedő vagy-ot használjuk.
Az implikáció arról szól, hogy minden olyan esetben, amikor igaz, -nek is teljesülnie kell. Arról nem szól az implikáció, hogy mi van akkor, ha hamis. Ezért értelmes az implikációt úgy definiálni, hogy igaz legyen azokban az esetekben, amikor hamis, függetlenül attól, hogy igaz vagy hamis. Tehát hamis állításból minden következik. Ezt azért fontos tudnunk, mert így látjuk, hogy hamis állításból kiindulva nem tudunk semmit bizonyítani, hamis állításból ugyanis minden igaz és minden hamis állítás következik.
A logikai műveleteket igazságtáblázatokkal is fel lehet írni:
i
i
i
i
i
i
i
h
h
i
h
h
h
i
h
i
i
h
h
h
h
h
i
i
i
h
h
i
A logikai műveletekkel összekapcsolt állítások tagadásait is felírtuk táblázatba. Egy állításnak és a tagadásának mindig ellentétes a logikai értéke.
i
i
h
h
h
h
i
h
i
h
i
i
h
i
i
h
h
i
h
h
i
i
h
h
Példák igaz állításokra:
A páros szám.
A páros szám és .
A páros szám vagy .
A páratlan szám vagy .
A páros szám vagy .
Ha páros szám, akkor .
Ha páratlan szám, akkor .
Ha páratlan szám, akkor .
Példák hamis állításokra:
A páratlan szám.
A páros szám és .
A páratlan szám és .
A páratlan szám és .
A páratlan szám vagy .
Ha páros szám, akkor .
Példák állításokra és a tagadásukra:
Állítás: A csitári hegyek alatt leesett a hó. Tagadása: A csitári hegyek alatt nem esett le a hó.
Állítás: Nem vagy itt jó helyen, és nem vagy való nekem. Tagadása: Jó helyen vagy itt, vagy nekem való vagy.
Állítás: Esik az eső és nem találsz rám. Tagadása: Nem esik az eső vagy rám találsz.
Állítás: Nem bérelek ki egy jó nagy puputevét vagy nem járom be Kenyát. Tagadása: Kibérelek egy jó nagy puputevét és bejárom Kenyát.
Állítás: A világ a jóra éhes vagy az ember a széptől ékes. Tagadása: A világ nem a jóra éhes és az ember nem a széptől ékes.
Állítás: Ha itt a nyár, akkor meleg az idő. Tagadása: Itt a nyár, és nem meleg az idő.
A matematika fogalmait, a bizonyítások és indoklások helyességét csak a logika elemeinek ismeretével érthetjük meg.
1.2. Bizonyítási módszerek
A matematikában az axiómák kivételével minden állítást bizonyítani kell. Az egyszerű vagy egyszerűnek látszó állításokat is. Bizonyítás közben felhasználhatjuk az
axiómákat és a már korábban bizonyított állításokat. Ez nem jelenti azt, hogy valóban mindig mindent bizonyítani fogunk, erre időnk sem lesz, ehelyett elfogadjuk, hogy mások már bizonyították a megfelelő állításokat, tételeket.
Ugyanakkor a feladatok gyakran szólnak állítások bizonyításáról.
A bizonyításokat éppen úgy meg lehet tanulni, mint a matematika többi
részét.
Példa:
A feladatok egy része megmondja, hogy mit kell bizonyítani.
Bizonyítsuk be, hogy , ahol .
Ilyenkor végig kell gondolni az állítást, és hogy milyen bizonyítási
módszerek jöhetnek szóba. Itt például bizonyíthatunk teljes indukcióval vagy felhasználhatjuk a számtani sorozat összegképletét.
Példa:
Sok esetben a feladat csak kérdez, és nem mondja meg, hogy mit kell
bizonyítani.
Van-e olyan szám, amelyikre teljesül, hogy ha ,
akkor ?
Bizonyítás:
Ahhoz, hogy tudjuk, hogy mit akarunk bizonyítani sejtésekre van szükségünk. A sejtésekhez rajzokkal, konkrét értékek kiszámításával juthatunk el. Nagyon fontos, hogy meg tudjuk különböztetni a sejtéseket a bizonyított állításoktól.
Ha az előző példát akarjuk megoldani, érdemes néhány kis esetet kiszámolni:
-re
,
-re
,
-re
,
-re
,
-re
,
Most az a sejtésünk, hogy igen, van ilyen szám. Ha már van sejtésünk, akkor el kell kezdeni a bizonyítást. A bizonyítás nem azonos a bizonygatással. Az, hogy látszik, hogy igaz, nem bizonyítás.
Az előző sejtést becsléssel bizonyíthatjuk be: , ha . Tehát, ha , akkor , továbbá ha , akkor . Vagyis, ha , akkor az összes egyenlőtlenség teljesül a következő becslésben: , tehát az jó megoldás. Most esetben bizonyítottuk a sejtést.
Megjegyzés: Az teljesen érdektelen, hogy esetleg -nél kisebb jó megoldása is van a feladatnak.
Példa:
Van-e olyan , amelyikre teljesül, hogy ha , akkor ?
Bizonyítás:
Próbálkozzunk most is:
-re
,
-re
,
-re
,
-re
,
-re
,
Most az a sejtés alakulhat ki, hogy a feladatban szereplő nem létezik, és ez látszik is. A látszik nem bizonyítás. Ha megpróbáljuk a sejtésünket bizonyítani, és azt tapasztaljuk, hogy nem sikerül, két lehetőség van: az egyik az, hogy ügyetlenek vagyunk, és ezért nem sikerül bizonyítani, a másik lehetőség az, hogy nem is igaz a sejtésünk. Tehát, ha nem sikerül egy bizonyítás, érdemes megváltoztatni a sejtést. Ebben az esetben a megváltoztatott sejtést kell bizonyítani.
Megjegyzés: Például teljes indukcióval be lehet bizonyítani, hogy van olyan , amelyikre teljesül, hogy ha , akkor . Ezt a bizonyítást most nem írjuk le.
A bizonyításoknál figyeljünk oda, hogy csak a feladatban megadott feltételeket használjuk fel! A megoldás során minden sejtést igazoljunk!
A bizonyítási módszerek közül kettővel foglalkozunk: a direkt és az
indirekt bizonyítással. Szóba kerül még a teljes indukció is, amivel állítások egy sorozatát lehet bizonyítani, de ez is a direkt vagy indirekt bizonyítási módszerek valamelyikével történik.
Direkt bizonyítás:
A direkt bizonyításnál igaz állításból indulunk ki, és helyes
matematikai lépésekkel jutunk el a bizonyítandó állításhoz.
Példa direkt bizonyításra: A számtani-mértani közép egyenlőtlenség bizonyítása két szám esetén.
Tétel:
Ha és két pozitív szám, akkor
Egyenlőség csak akkor van, ha .
Bizonyítás:
Ha , akkor nyilvánvalóan egyenlőség van. Nézzük azt az esetet, amikor , azaz .
mert minden nem nulla szám négyzete pozitív. De akkor
Az egyenlőtlenség mindkét oldalához hozzáadhatjuk -t, és így
A bal oldal átalakítása és (a pozitív) -el való osztás után
A bal oldal egy pozitív szám négyzete és a jobb oldal is pozitív, ezért igaz marad az egyenlőtlenség, ha mindkét oldalból gyököt vonunk, mert a gyökfüggvény szigorúan monoton növő a pozitív számokon.
Ez pedig éppen a bizonyítandó egyenlőtlenség.
A direkt bizonyításoknál nagyon kell figyelni arra, hogy nem a bizonyítandó állításból indulunk ki, hiszen arról nem tudjuk, hogy igaz-e, csak majd a bizonyítás után. Ha hamis állításból indulunk ki, bármit levezethetünk, ld. a megjegyzést az implikációnál.
Példa olyan hibás bizonyításra, amikor hamis állításból indulunk ki:
Az a sejtésünk, hogy . Az egyenlőség mindkét oldalát -val megszorozva a igaz állításhoz jutunk. Abból, hogy a végeredmény igaz, nem következtethetünk arra, hogy a kiindulás is igaz volt.
Nem minden esetben tudjuk előre, hogy melyik az az igaz állítás, amiből ki kell indulni. Természetesen gondolkozhatunk visszafele, próbálkozhatunk a bizonyítandó állítás alakításával, és azzal, hogy így jussunk el egy igaz állításhoz, de a megoldás végén a bizonyítás leírásakor az igaz állításból kiindulva kell eljutni helyes lépéseken keresztül a bizonyítandó állításhoz. Az igaz állítás a START, a bizonyítandó állítás a CÉL. Segíthet, ha visszafele bejárjuk a pályát, de a versenyen a STARTBÓL kell kiindulni, és a CÉLBA kell beérkezni.
Indirekt bizonyítás:
Az indirekt bizonyításnál feltesszük, hogy a bizonyítandó állítás tagadása igaz (ld. logikai műveletek), ez az indirekt feltevés, majd ebből az indirekt feltevésből kiindulva helyes matematikai lépéseken keresztül ellentmondásra jutunk. Az ellentmondás azt jelenti, hogy az indirekt feltevés hamis, tehát az eredeti állítás igaz.
Példa indirekt bizonyításra:
Tétel:A szám irracionális.
Bizonyítás:
Indirekt módon tegyük fel, hogy racionális, azaz előáll két egész szám, és hányadosaként:
A két egész számot megválaszthatjuk úgy is, hogy relatív prímek legyenek, azaz a jobb oldalon álló tört nem egyszerűsíthető. Négyzetre emelés és átszorzás után
A bal oldal páros szám, ezért a jobb oldal is az. De ha páros, akkor is az, tehát , valamilyen egész számra.
Eszerint is páros szám, de ez ellent mond annak a feltevésnek, hogy és relatív prím, hiszen mindkettő osztható -vel.
Az indirekt bizonyításnál arra kell figyelnünk, hogy helyesen fogalmazzuk meg a bizonyítandó állítás tagadását. Hibás tagadás hibás bizonyításhoz vezet. Annak a tagadása, hogy ez a toll kék az, hogy ez a toll nem kék. Nem a tagadása az ez a toll kék állításnak sem az, hogy ez a toll piros, sem az hogy ez a toll nem kék, hanem piros.
Példa olyan hibás bizonyításra, amikor rosszul fogalmazzuk meg az indirekt feltevést:
Az a sejtésünk, hogy ha , akkor . A sejtést indirekt módon próbáljuk bizonyítani. A hibásan megfogalmazott indirekt feltevés:
Ha , akkor .
Az így megfogalmazott indirekt feltevés biztosan nem igaz, ellenpélda az , hiszen , és . Tehát az indirekt feltevés nem igaz. Ebből helyesen megfogalmazott indirekt feltevés esetén következne, hogy az eredeti állítás igaz.
Most viszont nem következik, és az eredeti állítás nem is igaz: például esetén és .
Definíció:A teljes indukció elve. Ha minden természetes szám esetén egy állítás és
(1)
igaz,
(2)
ha igaz, akkor is igaz,
akkor mindegyik igaz.
A teljes indukció elve a természetes számok halmazának egy fontos tulajdonságán múlik:
Tétel:A természetes számok minden nem üres részhalmazának van legkisebb eleme.
1.3. Feladatok
Biztatásul közlöm, hogy tévesnek bizonyult a cáfolata annak a
híresztelésnek, mely szerint mégsem hazugság azt tagadni, hogy
lesz olyan hallgató, akinek egy analízis feladatot sem kell
megoldania ahhoz, hogy ne bukjon meg.
Baranyai Zsolt
1.3.1. Bevezető feladatok
Balkezes Bendegúz a bal kezével mindig igaz, a jobb kezével mindig
hamis állításokat írt. Melyik kezével írta a következő állításokat?
Fogalmazzuk meg az állítások tagadását! Döntsük el az állításokról is,
és a tagadásokról is, hogy igazak-e! Minden választ indokoljunk!
Ha , akkor .
Ha , akkor .
Ha az függvény monoton csökken -en, akkor monoton
nő -en.
Ha az függvény páratlan, akkor páros.
Ha az függvény páros, akkor páratlan.
Ha az függvény periodikus, akkor is periodikus.
Ezt a mondatot a bal kezemmel írtam.
Minden -nél kisebb pozitív szám szereti a tökfőzeléket.
Van olyan -nél kisebb pozitív szám, amelyik szereti a
tökfőzeléket.
A teremben hallgatók ülnek, az asztalon nyalókák vannak. Ugyanazt
jelenti-e a következő két mondat?
Minden hallgatóhoz van olyan nyalóka, amelyiket szopogatott.
Van olyan nyalóka, amelyiket minden hallgató szopogatott.
Ha esik az eső, akkor nem találsz rám. Melyik mondat jelenti
ugyanezt?
Ha nem esik az eső, akkor rám találsz.
Ha rám találsz, akkor nem esik az eső.
Tudjuk, hogy az és olyan sorozatok, hogy ha ,
akkor . Mire következtethetünk abból, hogy
?
?
Egy udvarban kecskék és bolhák vannak. Azt, hogy egy bolha megcsípett
egy kecskét, a formulával jelöljük. Olvassuk fel a
következő állításokat, és írjuk is le őket szöveggel! Döntsük el, hogy
melyik állításból melyik állítás következik!
Egy buliban fiú és lány volt. Azt, hogy egy fiú táncolt egy
lánnyal, a formulával jelöljük. Vizsgáljuk meg, hogy
következik-e az A állításból a B állítás, illetve, hogy
következik-e a B állításból az A állítás!
Vezessünk be jelöléseket, és írjuk fel formulákkal a következő
állításokat, amelyek egy teniszbajnokságról szólnak!
Volt olyan versenyző, aki senkit nem vert meg.
Volt olyan versenyző, aki mindenkit megvert.
Minden versenyző nyert is, és veszített is játékot.
Egyetlen versenyző sem vert meg mindenkit.
Bizonyítsuk be a következő egyenlőtlenségeket, ha és pozitív számok!
Legyen állítások egy sorozata. Mely állításokról
tudjuk biztosan, hogy igazak, illetve mely állításokról tudjuk
biztosan, hogy hamisak, ha
igaz, és ha igaz, akkor igaz.
igaz, és ha igaz, akkor igaz.
igaz, és ha hamis, akkor hamis.
hamis, és ha igaz, akkor igaz.
igaz, és esetén ha igaz, akkor igaz.
igaz, és esetén ha igaz, akkor igaz.
igaz és igaz, és ha igaz, és igaz, akkor
igaz.
igaz és igaz, és ha igaz, és igaz,
akkor igaz.
igaz és igaz, és esetén ha igaz, és
igaz, akkor igaz.
Bizonyítsuk be a következő állításokat tetszőleges pozitív egész esetén!
Fejezzük ki közvetlenül -nel az összeget! Először sejtsük meg az eredményt, majd bizonyítsuk be!
Bizonyítsuk be a következő állításokat! A feladatokban pozitív egész
számokat jelöl.
, ha
Állítás: Ha , akkor minden pozitív egész szám .
Bizonyítás teljes indukcióval: Az állítás -re igaz. Most
induljunk ki abból, hogy
Ha , akkor írjuk fel az előbbi azonosságot helyett -gyel:
Adjunk mindkét oldalhoz -et:
Tehát , amiből
következik, hogy .
Állítás: Minden ló egyszínű, azaz bármely két lónak ugyanolyan a színe.
Bizonyítás: Teljes indukcióval belátjuk, hogy bármely ló egyszínű.
Az állítás -re nyilvánvaló. Tegyük fel, hogy igaz -re, és ebből fogjuk -re belátni:
adott ló közül az indukciós feltevés miatt az is egyszínű és a is egyszínű, tehát mind az ló egyszínű.
Mivel az állítás hamis, a bizonyítás rossz. Keressük meg a hibát!
Legyen a Fibonacci-sorozat -edik tagja, azaz
Bizonyítsuk be, hogy
és relatív prímek!
.
Kivágjuk egy sakktáblából az egyik átlójának két végén levő
négyzeteket (az A1 és a H8 mezőket). Le lehet-e fedni a megmaradó
sakktáblát darab -es lappal (dominóval)? (Egy lap
mezőt tud lefedni.)
Bizonyítsuk be, hogy két racionális szám összege racionális!
Bizonyítsuk be, hogy irracionális!
Bizonyítsuk be, hogy a következő két szám irracionális:
Lehet-e
két irracionális szám összege racionális?
két racionális szám hányadosa irracionális?
Igaz-e, hogy egy racionális és egy irracionális szám összege irracionális?
Állítás: Az a legnagyobb szám.
Bizonyítás: Indirekt módon tegyük fel, hogy nem az a legnagyobb
szám, hanem .
Ekkor , továbbá . Az utolsó egyenlőtlenség
mindkét oldalát a pozitív -val osztva azt kapjuk, hogy , ami
ellentmond az indirekt feltevésnek, tehát mégis az a legnagyobb szám.
Hol a hiba?
Legyen és . Bizonyítsuk be, hogy a
sorozatnak van -nál nagyobb tagja!
1.3.2. Gyakorló feladatok
Írjuk le a következő mondatok tagadását!
Minden medve szereti a mézet.
Van olyan medve, amelyik nem szereti a mézet.
Van olyan tengerész, aki ismer olyan kikötőt, ahol minden kocsmában járt.
Minden tengerész, minden kikötőben talál olyan kocsmát, ahol még nem járt.
Van olyan méz, amit nem minden medve szeret.
Minden medve minden mézet szeret.
Tagadjuk a következő mondatokat!
Ha itt a nyár, akkor meleg az idő.
Itt a nyár, de mégis hideg van.
Ha a nagynénikémnek kerekei lennének, akkor ő lenne a miskolci gyorsvonat.
A nagynénikémnek kerekei vannak, mégsem ő a miskolci gyors.
Egy udvarban kecskék és bolhák vannak. Azt, hogy egy bolha megcsípett egy kecskét, a formulával jelöljük. Írjuk le a következő állítások tagadását formulákkal is, és szöveggel is!
Van olyan kecske, amit egyetlen bolha sem csípett meg. (bekenték bolhariasztóval)
Van olyan kecske, amit valamelyik bolha nem csípett meg. (szerencséje volt)
Egyetlen kecskét sem csípte meg az összes bolha. (elszaladtak a kecskék)
Egyetlen bolha sem csípett meg egyetlen kecskét sem. (ezek csak kutyát csípnek)
Egyetlen bolha sem csípett meg minden kecskét. (túl sok a kecske)
Van olyan bolha, amelyik egyetlen kecskét sem csípett meg. (vegetáriánus bolha)
Egy buliban fiú és lány volt. Azt, hogy egy fiú táncolt egy lánnyal, a formulával jelöljük. Írjuk le a következő állításokat formulákkal, és vizsgáljuk meg, hogy következik-e az A állításból a B állítás, illetve, hogy következik-e a B állításból az A állítás!
A: Van olyan lány, aki minden fiúval táncolt.
B: Van olyan fiú, aki minden lánnyal táncolt.
A:
B:
, például, ha egy fiú senkivel sem táncolt.
, például, ha egy lány senkivel sem táncolt.
A: Van olyan lány, aki táncolt valamelyik fiúval.
B: Van olyan fiú, aki táncolt valamelyik lánnyal.
A:
B:
, mert és egyszerre igaz vagy hamis, a formula szimmetrikus a változóira nézve.
A: Minden fiú táncolt valamelyik lánnyal.
B: Minden lány táncolt valamelyik fiúval.
A:
B:
, például, ha csak egy lány táncolt, de ő mindenkivel.
, például, ha csak egy fiú táncolt, de ő mindenkivel.
A: Minden fiú táncolt minden lánnyal.
B: Van olyan lány, aki minden fiúval táncolt.
A:
B:
, mert van legalább egy lány, és őt minden fiú megtáncoltatta.
, például, ha csak egy lány táncolt, de ő mindenkivel.
Bizonyítsuk be a következő egyenlőtlenségeket, ha és pozitív számok!
Azonos átalakításokat végzünk, felhasználva, hogy és pozitív.
Megjegyzés: az utolsó egyenlőtlenség baloldala, pontosan akkor nulla, ha
. Ezzel azt is beláttuk, hogy az eredeti egyenlőtlenségben akkor és csak akkor van egyenlőség, ha .
Visszavezetjük az előző feladatra.
Alkalmazhatjuk az előző feladat eredményét, és helyett az és pozitív számokra.
Legyen állítások egy sorozata. Mely állításokról
tudjuk biztosan, hogy igazak, illetve mely állításokról tudjuk
biztosan, hogy hamisak, ha
igaz, és ha igaz, akkor igaz.
Egyedül igaz biztosan. A feladat állítása igaz akkor is, ha igaz, de az összes többi hamis.
igaz, és ha hamis, akkor hamis.
Mindegyik igaz. Ez a forma a teljes indukció descente infinie verziója.
Fejezzük ki közvetlenül -nel az összeget!
Először sejtsük meg az eredményt, majd bizonyítsuk is be!
Legyen . Ekkor
. A sejtés
Az esetre igaz. Tegyük fel, hogy -re igaz, belátjuk, hogy akkor -re is igaz.
Bizonyítsuk be a következő állításokat! A feladatokban egész
számokat jelöl.
, ha
Teljes indukcióval bizonyítjuk. Ha , akkor
Tegyük fel, hogy -re igaz az egyenlőtlenség. Mivel ekkor
ezért elég belátni, hogy ha , akkor , azaz azt,
hogy .
Ha , akkor . Másrészt
Ez biztosan teljesül, ha . A két utoljára bizonyított egyenlőtlenség szorzatából
Teljes indukcióval bizonyítjuk. Ha akkor .
Tegyük fel, hogy -re igaz az egyenlőtlenség, azaz
Elég belátni, hogy .
Ez pedig igaz a kéttagú számtani és mértani közepek közötti egyenlőtlenség alkalmazásával az és számokra.
Legyen a Fibonacci-sorozat -edik tagja, azaz ,
és . Bizonyítsuk be, hogy
, ha .
Teljes indukcióval bizonyítjuk. Ha akkor .
Tegyük fel, hogy -re igaz, hogy
Felhasználjuk, hogy , és ezért .
Ez éppen a bizonyítandó egyenlőség, helyett -re felírva.
, ha .
Teljes indukcióval bizonyítjuk, hogy ha , akkor . Ha és , akkor
Legyen és tegyük fel, hogy és esetén igaz az egyenlőtlenség:
Be kell látnunk, hogy esetén is igaz az egyenlőtlenség.
mivel .
Legyen és . Határozzuk
meg értékét!
Írjuk fel az sorozat néhány tagját:
A sejtés az, hogy , Tegyük fel, hogy és . Ekkor
éppen a keresett egyenlőség. Tehát
Egy -ös sakktábla minden mezőjén áll egy bolha. Amikor az óra éjfélt üt, minden bolha átugrik valamelyik oldalszomszédos mezőre. Tudnak-e úgy ugrani, hogy az ugrás után is minden mezőn bolha legyen?
Nem tudnak így ugrani.
Színezzük meg a sakktábla mezőit két színnel a szokásos módon sötétre és világosra. Ekkor bármely két szomszédos mező ellenkező színű, ezért ha egy bolha ugrik, akkor más színű mezőre ugrik, mint ahol eredetileg volt. De a sakktábla oldala páratlan hosszúságú, ezért a táblának páratlan sok () mezője van és így valamelyik színből, például sötétből (ha a bal alsó mező sötét) több van, mint világosból. Eszerint a sötét mezőn álló bolhák az ugrás után kevesebb mezőre érkeznek, így valamelyik világos mezőn egynél több bolha landol.
Megjegyzés:Valójában azt bizonyítottuk be, hogy semmilyen páratlan oldalú sakktáblán sem lehet így ugratni a bolhákat. Ennek a feladatnak egy ismertebb verziója, hogy páratlan oldalú sakktáblát nem lehet lefedni (egyrétűen) -es dominókkal. Azt könnyű belátni, hogy minden páros oldalú sakktábla lefedhető.
Bizonyítsuk be, hogy a következő számok irracionálisak!
Indirekt módon tegyük fel, hogy racionális. Ekkor megadható két egész szám, és úgy, hogy
Feltehetjük, hogy mindkét egész szám pozitív és a hányadosuk már nem egyszerűsíthető, azaz és relatív prím számok. Az egyenlőséget -tel beszorozva
Eszerint osztható -mal. Mivel prímszám ezért is osztható -mal,
, ahol egy pozitív egész szám.
Az előző gondolatmenethez hasonlóan azt kapjuk, hogy is osztható -mal. Ez ellentmond annak, hogy és relatív prím.
Megjegyzés:Ugyanez a bizonyítás helyett tetszőleges prímszámra is elmondható: ha prímszám, akkor irracionális. Valójában -ről csak azt használtuk ki, hogy nem osztható -nél nagyobb négyzetszámmal, azaz előáll különböző prímszámok szorzataként. A bizonyítást tovább gondolva megkaphatjuk azt a tételt, hogy pozitív egész esetén négyzetszám vagy irracionális.
Indirekt módon tegyük fel, hogy racionális szám.
De akkor és is racionális szám. Ez ellentmond az előző 1.75. feladat állításának!
Indirekt módon tegyük fel, hogy
ahol és két relatív prím pozitív egész szám. Mivel és két különböző prímszám, ezért osztható -tal, . Innen
és így is osztható -tal, ami ellentmondás.
Indirekt módon tegyük fel, hogy
ahol és két relatív prím pozitív egész szám.
Innen azt kapjuk, hogy osztható -vel, pedig osztható -mal, azaz
ahol és két pozitív egész szám.
Innen kapjuk, hogy , és ezért is osztható -mal, ami ellentmondás.
Legyen és . Bizonyítsuk be, hogy a
sorozatnak van -nél kisebb tagja!
Indirekt módon bizonyítunk. Tegyük fel, hogy minden estén . Ekkor
Ez az utolsó, egyenlőtlenség könnyen belátható.
De akkor az választással , ami ellentmondás.
Megjegyzés: mivel a bizonyítás indirekt, formálisan csak azt láttuk be, hogy van
egyezrednél kisebb tagja a sorozatnak, azt nem, hogy az egymilliomodik tag kisebb mint egyezred. Ahhoz, hogy ezt is belássuk, módosítani kell az indirekt feltevést arra, hogy
