Hogyan fogjunk oroszlánt?

A matematika legkülönfélébb ágaiban előfordulnak olyan tételek, amelyek valamilyen matematikai objektum létezését állítják. Az ilyen tételeket egzisztencia-tételeknek¹ is nevezik.

Ebben a cikkben olyan eszközöket vizsgálunk meg, amelyek egzisztencia-tételek bizonyításához használhatóak, leginkább a valós analízis körében.

Először kimondunk néhány tipikus egzisztencia-tételt. Ezek részben szemléltetések, részben pedig eszközök lesznek más egzisztencia-tételek bizonyításához.

Tétel. Létezik olyan pozitív valós szám, amelynek a négyzete 2.

A legkisebb felső korlát tétele. Ha a valós számokból álló H halmaz felülről korlátos és nem üres, akkor a felső korlátai között van legkisebb.²

Bolzano-Weierstrass tétel. Tetszőleges korlátos x₁,x₂,... számsorozatnak van torlódási pontja.³

Borel fedési tétele. Ha egy [a; b] zárt intervallumot lefedünk akárhány nyílt intervallummal, akkor a nyílt intervallumok közül kiválasztható véges sok, ami még mindig lefedi az [a; b] intervallumot.

Az algebra alaptétele. Minden legalább elsőfokú, valós vagy komplex együtthatós polinomnak van komplex gyöke.

Ezekben a tételekben közös, hogy egy speciális tulajdonságú szám létezését állítják egy bizonyos halmazban. Egyedül a Borel-tétel látszik kivételnek, de ezt a következőképpen is megfogalmazhatjuk:

Borel fedési tételének átfogalmazása. Ha adott akárhány nyílt intervallum, és ezek közül semelyik véges sok nem fedi le az [a; b] intervallumot, akkor létezik olyan c szám az [a; b] intervallumban, amelyet egyik nyílt intervallum sem tartalmaz.

I. módszer: intervallum-felezés

Ezt a módszert nagyon szemléletesen mutatja be egy klasszikus példázat.

Feladat: Fogjunk a sivatagban oroszlánt. Ehhez rendelkezésünkre áll egy oroszlánjelző műszer, ami a sivatag bármelyik részletéről megállapítja, hogy van-e benne oroszlán.

Megoldás: Két részre osztjuk a sivatagot, és mindkét felét lemérjük a műszerrel. Ha az egész sivatagban van oroszlán, akkor legalább az egyik felében szintén van. Kiválasztjuk az egyik ilyen fél sivatagot, a másik felét eldobjuk. A fél sivatagot ismét két részre osztjuk; az egyik részt (amiben van oroszlán) megtartjuk, a másik részt ismét eldobjuk. A felezgetést akkor hagyjuk abba, amikor a megmaradt sivatag darab már elég kicsi (azaz csupán egyetlen homokszemből áll), és akkor ráborítunk egy ketrecet. Ezzel megfogtuk az oroszlánt.

A gyakorlatban az oroszlán az a matematikai objektum, aminek a létezését bizonyítani akarjuk, például egy speciális tulajdonságú szám. A sivatag az a halmaz, amelynek elemei között keressük a kérdéses objektumot, legtöbbször egy intervallum. Az intervallumot természetesen nem elég véges sokszor két részre osztani. Végtelen sok felezésre van szükség, hogy végül csak egyetlen szám maradjon.

Sajnos a ,,megoldásban'' komoly hiányosságok vannak. Ahhoz, hogy kijelenthessük: megfogtuk az oroszlánt, a következő három kérdést kell tisztáznunk:

K1. Biztosak lehetünk-e abban, hogy egyáltalán fogtunk valamit?

K2. Csak egyvalamit fogtunk?

K3. Hogyan győződhetünk meg róla, hogy oroszlánt fogtunk, és nem valami mást?

Ezeknek a kérdéseknek a megválaszolása nélkül a ,,megoldás'' utolsó mondata közönséges blöff.

Tanulságképpen nézzük meg, mire jutottak volna az ókori görögök a -vel.

Akhilleusz és a

Az ókori görögök csak a racionális számokat ismerték, és tragikus felismerés volt számukra, hogy nincs olyan racionális szám, aminek a négyzete 2, holott a geometriában szükségük lett volna ilyen távolságra.

Képzeljük el, hogy Akhilleusz, a mesebeli görög hős megpróbálja megtalálni azt a racionális számot, amelynek négyzete 2. Akhilleusz úgy találja, hogy az 1 túl kicsi (a négyzete kisebb, mint 2), a 2 viszont túl nagy. Ezért úgy dönt, hogy a számot az (1; 2) intervallumban keresi.

Ezután kipróbálja a számot, és megállapítja, hogy ez is túl nagy, mert a négyzete , ami nagyobb 2-nél. Ezért a -t és a nála nagyobb számokat eldobja, és csak az intervallummal foglalkozik tovább. Ezután az számot próbálja ki (túl kicsi), majd a -ot (túl kicsi), és így tovább. Közben az intervallum, amelyben a -t keresi, egyre fogy:

,   ,   ,   ,   ,  ... .

Akhilleusznak elég sok ideje van, és az intervallum-felező lépést végtelen sokszor elvégzi. Közben kidobja az összes olyan racionális számot, aminek a négyzete nagyobb 2-nél, és azokat is, amelyeknek a négyzete kisebb 2-nél.

Ekkor kellemetlen meglepetés éri: Az összes racionális számot kidobta, nem maradt egy sem.

A valós számok axiómarendszere

Akhilleusz problémáján úgy lehet segíteni, hogy a racionális számokon kívül további számokat vezetünk be. Az nyilván kevés, ha csak egy új számot (a -t) találunk ki, szükség van még -ra, -re, az 1,01001000100001... tizedes törtre és még rengeteg más számra. Az új számokkal mit is akarnánk mást, mint számolni, tehát a jól megszokott alapműveleteket és a rendezést (a kisebb-nagyobb relációt) ki akarjuk terjeszteni az ,,új'' számokra is.

A racionális számok kiegészítésére több konstrukció is létezik. Vannak természetesnek nevezhető konstrukciók, például mondhatjuk azt, hogy ezentúl a végtelen tizedes törteket nevezzük számoknak. Ennek a konstrukciónak az a hátránya, hogy a műveleteket - különösen a szorzást - nagyon nehéz definiálni. Vannak kevésbé természetes konstrukciók, amelyek nem annyira szemléletesek, de lényegesen könnyebb a műveleteket definiálni; ilyenek például a racionális számok Dedekind-szeletei⁴ vagy a racionális számokból készített Cauchy-sorozatok ekvivalencia-osztályai.⁵

Magukat az új számokat ,,valós'' (azaz létező) számoknak fogjuk hívni. Most nem az a célunk, hogy a lehetséges konstrukciókat tanulmányozzuk, vagy hogy az egyik konstrukciót előnyben részesítsük a többivel szemben. Inkább nem mondjuk meg, hogy milyen objektumokat nevezünk valós számnak, hanem csak a legfontosabb tulajdonságaikat soroljuk fel. Ezeket a tulajdonságokat hívjuk a valós számok axiómáinak.

Az axiómákat négy csoportra oszthatjuk:

I. Testaxiómák. Létezik két kétváltozós művelet, az összeadás és a szorzás, valamint két különböző kitüntetett szám, a 0 és az 1 a következő tulajdonságokkal:

T1. Tetszőleges a, b valós számokra a+b=b+a.
T2. Tetszőleges a, b, c valós számokra (a+b)+c=a+(b+c).
T3. Tetszőleges a valós számra a+0=a.
T4. Tetszőleges a valós számhoz létezik olyan b valós szám, amelyre a+b=0.
T5. Tetszőleges a, b valós számokra a^.b=b^.a.
T6. Tetszőleges a, b, c valós számokra (a^.b)^.c=a^.(b^.c).
T7. Tetszőleges a valós számra a^.1=a.
T8. Tetszőleges 0-tól különböző a valós számhoz létezik olyan b valós szám, amelyre a^.b=1.
T9. Tetszőleges a, b, c valós számokra (a+b)^.c=(a^.c)+(b^.c).

Általában, egy algebrai struktúrát testnek nevezünk, ha teljesülnek ezek az axiómák. Testet alkotnak például a 0,1,2 számok, ha az összeadást és a szorzást modulo 3 végezzük (pl. 2+2=1), vagy például a racionális törtfüggvények.

A testaxiómákból bebizonyítható az összes jól ismert műveleti azonosság, és sok más érdekes tétel, például az, hogy egy polinomból ki lehet emelni a gyöktényezőket.

II. Rendezési axiómák: Létezik egy < reláció a következő tulajdonságokkal:

R1. Tetszőleges a, b számokra az a=b, a<b és b<a állítások közül pontosan az egyik teljesül.
R2. Ha az a, b, c számokra a<b és b<c, akkor a<c.
R3. Ha az a, b, c számokra a<b, akkor a+c<b+c.
R4. Ha az a, b, c számokra a<b és 0<c, akkor a^.c<b^.c.

Egy struktúrát rendezett testnek hívunk, ha teljesülnek rá a test- és rendezési axiómák.

Érdekesség, hogy nem mondtuk ki, hogy 0<1; ezt az axiómákból be lehet bizonyítani.

Ezek után definiálhatjuk a pozitív egész számokat: 1, 1+1, 1+1+1 stb. A rendezési axiómák garantálják többek között azt is, hogy ezek a számok különbözőek.

III. Arkhimédészi axióma: Tetszőleges valós számnál van nagyobb pozitív egész szám.

Ez az állítás nem következik a korábbiakból. Például a racionális törtfüggvények között lehet definiálni egy < relációt úgy, hogy rendezett testet alkossanak, de ne teljesüljön az Arkhimédészi axióma.

IV. Cantor-axióma: Egymásba skatulyázott zárt intervallumok sorozatának mindig van közös pontja. Más szóval, ha adott két számsorozat: a₁a₂... és b₁b₂... úgy, hogy tetszőleges n-re a_nb_n, akkor az [a₁; b₁][a₂; b₂][a₃; b₃]... intervallumoknak van közös eleme.

Az Arkhimédészi és a Cantor-axióma megadja a választ a K1 és K2 kérdésekre. Tegyük fel, hogy az [a₀; b₀] intervallumból indultunk ki. Az intervallum felosztásakor a felezőpontot ne dobjuk ki; ezáltal egy zárt intervallumokból álló [a₀; b₀][a₁; b₁][a₂; b₂]... sorozatot kapunk, amelyben az n-edik intervallum hossza b_n-a_n=. Ezeknek az intervallumoknak a Cantor-axióma szerint van közös eleme.

Ha az intervallumoknak legalább két közös eleme van: c és d, ahol c<d, akkor minden n-re [c; d][a_n; b_n] teljesül. Ebből következik, hogy d-cb_n-a_n=, azaz 2ⁿ<. Ez azonban azt jelenti, hogy a szám minden 2-hatványnál - és ezáltal minden pozitív egésznél - nagyobb, ami ellentmond az Arkhimédészi axiómának. Tehát a K1 és a K2 kérdésekre igen a válasz.

Első bizonyítás a létezésére

Most már minden szükséges eszköz rendelkezésünkre áll, hogy bebizonyítsuk a létezését.

Akhilleuszhoz hasonlóan definiálunk egy intervallumsorozatot. Legyen [a₀; b₀]=[1; 2]. Ha [a_n; b_n]-et már definiáltuk, akkor vizsgáljuk meg, hogy nagyobb-e mint 2. Ha >2, akkor legyen [a_n+1; b_n+1]=. Ellenkező esetben legyen [a_n+1; b_n+1]=. Ezzel egy olyan

[a₀; b₀] [a₁; b₁] [a₂; b₂]...

intervallum-sorozatot definiáltunk, amelyben tetszőleges n-re a_n²2 és b_n²2.

Az intervallumsorozatnak létezik egyetlen közös eleme; jelöljük ezt c-vel. Már csak azt kell bebizonyítanunk, hogy a K3 kérdés szavaival c egy oroszlán, azaz c²=2.

Tetszőleges n-re igaz, hogy c²b_n² és a_n²2, ezért

c²-2b_n²-a_n²=(b_n-a_n)(b_n+a_n)<^.(2+2)=.

Ha a c²a_n² és b_n²2 egyenlőtlenségből indulunk ki, akkor pontosan ugyanezt kapjuk (2-c²)-re. A két eredmény együtt azt állítja, hogy

|c²-2|<.

Az Arkhimédészi axióma miatt a szám tetszőleges pozitív számnál kisebb lesz, ha n elég nagy, ezért |c²-2| nem lehet pozitív. |c²-2| tehát 0, azaz c²=2.

A legkisebb felső korlát tétele

Ugyanezzel a módszerrel bizonyíthatjuk be a legkisebb felső korlát tételét.

Legyen L₀ egy olyan szám, amely nem felső korlátja H-nak (Ilyen létezik, mert H nem üres), és legyen K₀ egy felső korlát. A K₀-nál nagyobb számok is mind felső korlátok, ezért biztosan L₀<K₀.

A legkisebb felső korlátot nyilván a [L₀; K₀] intervallumban érdemes keresnünk. Ezt az intervallumot fogjuk felezgetni.

Ha már definiáltuk az [L_n; K_n] intervallumot, akkor vizsgáljuk meg, hogy felső korlátja-e H-nak. Ha igen, akkor legyen [L_n+1; K_n+1]=[L_n; ]. Ha nem felső korlát, akkor legyen [L_n+1; K_n+1]=[; K_n].

Az így definiált

[L₀; K₀] [L₁; K₁] [L₂; K₂]...

intervallumsorozatban tetszőleges n-re K_n felső korlátja a H halmaznak, L_n pedig nem felső korlátja.

Az intervallumoknak létezik pontosan egy közös eleme, legyen ez M. Azt kell bebizonyítanunk, hogy M felső korlátja H-nak, és nincs M-nél kisebb felső korlát.

Legyen h a H halmaz egy tetszőleges eleme. Bármely n pozitív egészre K_n felső korlát, ezért hK_n; másrészt ML_n. Ebből következik, hogy

h-MK_n-L_n=.

Ebből az Arkhimédészi axióma miatt következik, hogy h-M nem lehet pozitív, vagyis hM. Ezzel igazoltuk, hogy M felső korlát.

Legyen K egy tetszőleges felső korlátja H-nak. Ekkor tetszőleges n esetén MK_n a konstrukció miatt és L_n<K, mert a K-nál nem kisebb számok mind felső korlátok; ezért

M-K<K_n-L_n=.

Ebből következik, hogy M-K nem lehet pozitív, azaz MK. Az M számnál tehát nincs kisebb felső korlát.

A legkisebb felső korlátot latin kifejezéssel szuprémumnak is nevezzük, a H halmaz szuprémumát (legkisebb felső korlátját) sup H-val jelöljük. A tétel párja a legnagyobb alsó korlát tétele: Tetszőleges nem üres, alulról korlátos halmaznak létezik legnagyobb alsó korlátja. Ezt infimumnak is nevezzük, jele inf H.

Ha a halmaznak létezik legnagyobb illetve legkisebb eleme (maximuma illetve minimuma), akkor ez természetesen azonos a halmaz szuprémumával illetve infumumával. Maximuma és minimuma nincs minden halmaznak, viszont szuprémuma és infimuma minden nem üres és korlátos halmaznak van.

Érdekesség, hogy a valós számok axiómarendszerében az Arkhimédészi és a Cantor-axióma helyett a legkisebb felső korlát tételét is kimondhatjuk. A test- és rendezési axiómákból, valamint a legkisebb felső korlát tételéből nagyon könnyű bebizonyítani a Cantor- és az Arkhimédészi axiómát.

A legkisebb felső korlát tétele ezen kívül egy másik nagyon fontos eszköz egzisztencia-tételek bizonyítására.

II. módszer: a legkisebb felső korlát tételének alkalmazása

Egy autóút mentén a bokrok között oroszlánok bújtak el (legalább egy). Feladat: fogjunk meg legalább egy oroszlánt. Ismét rendelkezésünkre áll egy műszer, amely az autóút bármely szakaszára meg tudja mondani, hogy van-e ott oroszlán.

Megoldás: Minden egyes pontban állapítsuk meg, hogy az út hátralevő részén van-e oroszlán. Ha van, tegyünk ki egy ,,Oroszlánveszély'' feliratú táblát. Ahol a táblák elfogynak, ott bújt el egy oroszlán.

Tegyük fel, hogy egy [a; b] intervallumban keresünk egy bizonyos c számot, és az intervallum bármelyik eleméről valamilyen módszerrel meg tudjuk állapítani, hogy a keresett c-nél kisebb vagy nagyobb. A c-nél nem nagyobb számok azok a helyek, ahova ,,táblát teszünk''; ezeket a számokat összegyűjtjük egy T halmazban. Az a hely, ahol ,,a táblák elfogynak'', a T halmaz szuprémuma.

A szuprémum egyértelműen létezik, viszont ismét meg kell vizsgálnunk, hogy oroszlán-e, azaz rendelkezik-e a kívánt tulajdonságokkal.

A továbbiakban a két módszer alkalmazásaként bebizonyítjuk a bevezetőben kimondott tételeket.

Második bizonyítás a létezésére

A -t ismét a [1,2] intervallumban keressük. Azok a számok nem nagyobbak -nél, amelyek négyzete nem nagyobb 2-nél, ezért legyen

T={t[1,2]: t²2}

és c=sup T. A T halmaz nem üres, mert például 1 T. Ugyanakkor felülről korlátos, például a 2 egy felső korlátja. Ezért a c szám definíciója értelmes.

Azt akarjuk igazolni, hogy c²=2.

Tetszőleges 0< <1 esetén c- nem felső korlátja T-nek, (c a legkisebb felső korlát), ezért létezik olyan t T elem, amelyre c- <tc. Felhasználva, hogy t T esetén t²2,

c²-2c²-t²=(c-t)(c+t)<^.(2+2)=4.

Hasonlóképpen, mivel c a legkisebb felső korlát, c+ nem eleme a T halmaznak, ezért (c+)²>2, amiből következik, hogy

2-c²<(c+)²-c²=2c+²<5.

Azt kaptuk, hogy tetszőleges 0<<1 esetén |c²-2|<5. Ez pedig csak úgy lehetséges, ha |c²-2| nem pozitív, azaz c²=2.

A Bolzano-Weierstrass tétel bizonyítása intervallum-felezéssel

Definiálunk egy olyan [a₀; b₀] [a₁; b₁] [a₂; b₂]... intervallum-sorozatot, amelyre tetszőleges n esetén [a_n; b_n] az x₁,x₂,... sorozatnak végtelen sok elemét tartalmazza.

Legyen [a₀; b₀] egy olyan intervallum, amely a teljes x₁,x₂,... sorozatot tartalmazza.

Ha az [a_n; b_n] intervallumot már definiáltuk, és az végtelen sok elemet tartalmaz az x₁,x₂,... sorozatból, akkor az és intervallumok közül legalább az egyik szintén végtelen sok elemet tartalmaz. Az egyik ilyet válasszuk [a_n+1; b_n+1]-nek.

A [a_n; b_n] intervallumoknak létezik egy közös c eleme. Azt állítjuk, hogy ez torlódási pont. Tetszőleges >0 esetén létezik egy olyan n szám, amelyre [a_n; b_n](c-; c+). Az [a_n; b_n] intervallum végtelen sok elemet tartalmaz az x₁,x₂,... sorozatból; ezeket a (c-; c+) intervallum is tartalmazza.

A Bolzano-Weierstrass tétel bizonyítása a legkisebb felső korlát tételével

Legyen az x₁,x₂,... sorozat egy alsó illetve felső korlátja A illetve B. Legyen T azoknak a t valós számoknak a halmaza, amelyekre a [t; B] intervallum végtelen sok elemet tartalmaz az x₁,x₂,... sorozatból. Ez a halmaz nem üres, például A T, és felülről korlátos, például B egy felső korlátja. Létezik tehát legkisebb felső korlátja; legyen ez c.

Tetszőleges >0 esetén c+ nem eleme a T halmaznak (nagyobb c-nél, a felső korlátnál), ezért a [c+; B] intervallum csak véges sok elemet tartalmaz az x₁,x₂,... sorozatból.

A c- szám viszont nem felső korlát (kisebb c-nél, a legkisebb felső korlátnál), ezért létezik egy olyan t>c- szám, ami eleme T-nek. Ez azt jelenti, hogy a [t; B](c-; B] intervallum végtelen sok elemet tartalmaz az x₁,x₂,... sorozatból.

összefoglalva, tetszőleges esetén a (c-; B] intervallum végtelen sok, a [c+; B] intervallum viszont csak véges sok elemet tartalmaz az x₁,x₂,... sorozatból; ebből következik, hogy a két intervallum különbsége, (c-; c +) is végtelen sokat tartalmaz.

Borel fedési tételének bizonyítása intervallum-felezéssel

Tegyük fel, hogy az [a,b] intervallumot nem lehet lefedni véges sok nyílt intervallummal. Definiálunk egy olyan [a₀; b₀] [a₁; b₁] [a₂; b₂]... intervallum-sorozatot, amelyre tetszőleges n esetén az [a_n; b_n] intervallum nem fedhető le véges sok nyílt intervallummal.

Legyen [a₀; b₀]=[a; b]. Ha már definiáltuk [a_n; b_n]-et, és ez nem fedhető le véges sok nyílt intervallummal, akkor az és intervallumok közül legalább az egyiket szintén nem lehet véges sok nyílt intervallummal lefedni. Az egyik ilyet válasszuk [a_n+1; b_n+1]-nek.

A [a_n; b_n] intervallumoknak létezik egy közös c eleme. Tegyük fel, hogy c eleme egy I nyílt intervallumnak. Ekkor elég nagy n esetén [a_n; b_n]I. Ez viszont ellentmondás, mert I egyedül lefedi az [a_n; b_n] intervallumot. A c számot tehát egyik nyílt intervallum sem tartalmazza.

Borel fedési tételének bizonyítása a legkisebb felső korlát tételével

Tegyük fel ismét, hogy az [a,b] intervallumot nem lehet lefedni véges sok nyílt intervallummal. Legyen T azoknak a [a; b]-beli t számoknak a halmaza, amelyekre a [t; b] intervallum nem fedhető le véges sok nyílt intervallummal. A T halmaz nem üres, például a T, másrészt felülről korlátos. Legyen c=sup T.

Ha c-t egyik nyílt intervallum sem tartalmazza, kész vagyunk. Tegyük tehát fel, hogy c-t tartalmazza egy (u; v) nyílt intervallum. Ekkor c<v miatt v nem eleme T-nek, és a [c; b] intervallum lefedhető véges sok nyílt intervallummal. Ezek (u; v)-vel együtt az (u; b] intervallumot is lefedik. Tehát tetszőleges t>u esetén a [t; b] intervallum lefedhető véges sok nyílt intervallummal. Ebből következik, hogy u is felső korlátja T-nek, ami ellentmond annak, hogy c a legkisebb felső korlát.

Az algebra alaptétele

¹ A latin egzisztencia szó jelentése: létezés

² A H halmaznak a K szám felső korlátja, ha H-nak nincs K-nál nagyobb eleme. Egy halmaz felülről korlátos, ha létezik felső korlátja.

³ Egy sorozatnak a c szám torlódási pontja, ha tetszőleges pozitív esetén a sorozatnak végtelen sok eleme esik a (c-; c +) intervallumba.

⁴ A HQ halmazt a racionális számok Dedekind-szeletének hívjuk, ha tetszőleges q₁<q₂ racionális számokra q₂ H esetén q₁ H. Egy ilyen szelet megfelel annak, hogy a racionális számok halmazát egy valós számnál ,,elvágjuk''.

⁵ A q₁,q₂,... sorozatot Cauchy-sorozatnak hívjuk, ha tetszőleges >0-hoz létezik olyan n₀ pozitív egész, hogy tetszőleges m,n>n₀ esetén |q_n-q_m|< . A q₁,q₂,... és r₁,r₂,... Cauchy-sorozatokat ekvivalensnek nevezzük, ha (q_n-r_n)0.