Kis matematikai szintézis [PDF]

Zitiervorschau

POLYGON JEGYZETTÁR Csákány Béla

KIS MATEMATIKAI SZINTÉZIS

KIS MATEMATIKAI SZINTÉZIS

Ez a könyv az Oktatási Minisztérium által kiírt, Felsőoktatási Pályázatok Irodája által lebonyolított felsőoktatási tankönyvtámogatási program támogatásával jelent meg

IT A T Á S I

x V L IN IS Z T E R IU M

Csákány Béla

KIS MATEMATIKAI SZINTÉZIS

POLYGON Szeged, 2003

IP®IW(BdDRí jJHBYfM m rÁm Szerkeszti:

K urusa Á r p á d

Lektorálta:

D r . H a jn a l P é te r A MÁT. TUD. KANDIDÁTUSA

ISSN 1417— 0590 K iadja az S Z T E B O L Y A I IN T É Z E T a P O L Y G O N jegyzetsorozataként Felelős vezető: Kincses János főszerkesztő Bolyai Intézet Szeged, A radi vértanúk tere 1 ., 6720 e-m ail: polygon@ rnath.u-szeged.hu http: / / w w w .m ath .u-szeged.hu / polygon / © D r . Csákány Béla, 2003.

Előszó Az utóbbi évtizedekben legalább ötszáz mai matematikatanár utolsó egye­ temi vizsgáját ültem végig figyelmesen, s eközben a vizsgázók temérdek örömet és bosszúságot szereztek nekem. Most a vizsgáztatást ideje abbahagynom; helyette megpróbálok magam vizsgázni, remélve, hogy ezzel sokaknak segíthetek. Ez a könyv tizennyolc fejezetből áll, amelyek kölcsönösen egyértelmű mó­ don megfelelnek a szegedi matematikatanár-jelöltek sok év óta szokásos záróvizsga­ tételeinek. Ezekhez járul még egy függelék a számfogalom felépítéséről, amelynek a tartalmát — bár nem vizsgatétel — hasznos is, illik is ismerni. A fejezetek mindegyike azt a kis előadást tartalmazza, amelyet jómagam tartanék a tekinté­ lyes vizsgabizottság előtt az éppen kihúzott vizsgatételről, ha valamely csoda — vagy rendelet — folytán holnap újból tanári záróvizsgát kellene tennem. Sajátsá­ gos lenne a helyzet, s ez magyarázza a könyv furcsaságait, amelyekről a következő bevezetésben — reményem szerint olvasóim hasznára, de mindenképpen a magam mentségére — részletesebben is írok. Javasolom is, hogy aki idáig eljutott az olva­ sásban, a bevezetést feltétlenül olvassa el, különösen akkor, ha az egész könyvet el akarja olvasni. Hálás vagyok záróvizsgáztató kollégáimnak, Csörgő Sándornak, Hajnal Péter­ nek, Hatvani Lászlónak, Kincses Jánosnak, Megyesi Lászlónak és Totik Vilmosnak önzetlen és alapos munkájukért, amellyel a fejezeteket elolvasták, megbírálták és korrigálták. Hajnal Péter az elkészült teljes kéziratot is végigolvasta, s hosszú lenne elmondani, milyen jót tettek a szövegnek az ő értő megjegyzései, javaslatai. Mivel szakkönyv előszavának szokásos eleme a köszönetnyilvánítás, szeretném megismé­ telni és aláhúzni, hogy tényleg és nagyon hálás vagyok mindnyájuknak. Speciális köszönet illeti Juhász Rozáliát, feleségemet, a geometria-tételekről folytatott be­ szélgetésekért és az ábrák elkészítéséért. Ha a szövegben mégis maradtak hibák, az csak az én figyelmetlenségemnek vagy önfejűségemnek tulajdonítható. Szeged, 2003. június 15-én.

Tartalom jegyzék E lő s z ó .......................................................................................................................................... i B e v e z e té s .................................................................................................................................. 1 1. K om b in a torik a .....................................................................................................................5

1. 1 .

Teljes in d u k ció......................................................................................................... 5

1.2.

Egyszerű összeszámlálási feladatok.................................................................... 7

1.3.

Nevezetes sz á m o k ....................................................................................................9

1.4.

Binomiális tétel és e g y e b e k ................................................................................ 11

1.5.

G rá fo k .......................................................................................................................12

1 .6 .

Gráfelméleti p ro b lé m á k .......................................................................................15

2. Algebrai e g y e n le te k ......................................................................................................... 18 2.1.

Polinom , polinom gyűrü........................................................................................18

2 .2 .

Az alaptétel és következm ényei.................................................

2.3.

G y ök k ép letek ......................................................................................................... 24

2.4.

Szerkeszthetőség.................................................................................................... 26

22

3. A z egész s z á m o k ............................................................................................................. 28 3.1.

O szth atóság.............................................................................................................28

3.2.

Az alaptétel.............................................................................................................31

3.3.

P rím szám ok.............................................................................................................32

3.4.

K on gruenciák ......................................................................................................... 33

3.5.

Számelméleti függvén yek.................................................................................... 35

4. C s o p o r t o k ...........................................................................................................................38 4.1.

C soportm űveletek................................................................................................. 38

4.2.

P é ld á k .......................................................................................................................40

4.3.

Csoportelm életi alapfogalm ak ........................................................................... 41

4.4.

Iz o m o rfia ................................................................................................................. 45

4.5.

Direkt szorza t......................................................................................................... 47

5. Lineáris egyen letren dszerek ..........................................................................................49 5.1.

Egyenletek, egyenletrendszerek.........................................................................49

5.2.

Gauss-féle elim in á ció............................................................................................50

5.3.

D eterm ináns........................................................................................................... 52

Tartalomjegyzék

iii

5.4. Vektoregyenlet, mátrixegyenlet.................................................................... 55 6 . Lineáris algebra.......................................................................................................... 59 6.1. Vektor, vektortér..............................................................................................59 6.2. Bázis, dim enzió................................................................................................ 62 6.3. Lineáris leképezések és mátrixok.................................................................. 65 7. Geometriai transzform ációk....................................................................................69 7.1. A síkgeometria axiómarendszere...................................................................69 7.2. Izom etriák......................................................................................................... 71 7.3. Hasonlóságok és affinitások............................................................................75 7.4. Térizometriák................................................................................................... 77 7.5. Kollineációk.......................................................................................................78 8 . Analitikus g eo m e tria ................................................................................................ 80 8.1. Koordináták bevezetése..................................................................................80 8.2. Vektoralgebra................................................................................................... 84 8.3. Alakzatok egyenletei....................................................................................... 86 8.4. Baricentrikus koordináták..............................................................................88 8.5. Transzformációk leírása..................................................................................89 9. Nemeuklideszi geom etriák.......................................................................................91 9.1. Projektív geom etria.........................................................................................91 9.2. A projektív sík koordinátázása..................................................................... 94 9.3. Kúpszeletek a projektív geometriában........................................................ 97 9.4. Az inverzív s ík ..................................................................................................99 9.5. Hiperbolikus síkgeometria............................................................................101 10. G örbék......................................................................................................................104 10.1. Kúpszeletek..................................................................................................... 104 10.2. Bézier-görbék..................................................................................................109 10.3. T érgörbék........................................................................................................112 10.4. E gyebek........................................................................................................... 115 11. Sorozatok, so ro k ....................................................................................................117 11.1. Sorozatok.........................................................................................................117 11.2. Sorok................................................................................................................ 120 11.3. Hatványsorok, függvénysorok...................................................................... 121 12. Függvények.............................................................................................................127 12.1. A függvény fogalm a.......................................................................................127 12.2. Elemi függvények.......................................................................................... 129 12.3. Függvény határértéke................................................................................... 131 12.4. Függvény grafikonja...................................................................................... 132 12.5. Folytonosság................................................................................................... 133

IV

Tartalomjegyzék

13. D ifferenciálás........................................................................................................... 137 13.1. Differenciálhányados.......................................................................................137 13.2. Függvénydiszkusszió...................................................................................... 142 13.3. Parciális és totális differenciálás.................................................................. 145 14. Integrálás.................................................................................................................. 148 14.1. Határozott integrál.................................................................. 148 14.2. Határozatlan integrál..................................................................................... 151 14.3. Lebesgue-integrál............................................................................................ 154 14.4. Többváltozós függvény integrálja................................................................ 156 15. M érték ........................................................................................................................160 15.1. Jordán-m érték..................................................................................................160 15.2. Terület, térfog a t.............................................................................................. 162 15.3. Lebesgue-mérték..............................................................................................166 15.4. ívhossz, felszín................................................................................................. 168 16. V alószín ű ség.............................................................................................................171 16.1. Valószínűségi kísérlet...................................................................................... 171 16.2. Valószínűségi m ező.......................................................................................... 172 16.3. A valószínűségi mező általános fogalm a..................................................... 175 16.4. A nagy számok törvén ye............................................................................... 178 16.5. Véletlen v á lto zó k .............................................................................................179 17. H alm azok.................................................................................. 184 17.1. Alapfogalm ak................................................................................................... 184 17.2. Szám osság......................................................................................................... 185 17.3. Rendezett halmazok........................................................................................190 17.4. Antinóm iák....................................................................................................... 192 18. Matematikai lo g ik a ................................................................................................ 195 18.1. Nyelvek és struktúrák.....................................................................................195 18.2. ítéletkalkulus....................................................................................................199 18.3. Függvény kalkulus........................................................................... 201 18.4. E gyebek .............................................................................................................203 S zá m ok .............................................................................................................................206 1. 2.

Természetes szám ok.......................................................................................206 Egész és racionális szám ok ............................................................................208

3. Valós szám ok ....................................................................................................210 4. Komplex szám ok............................................................................................. 213 Név- és tá rg ym u ta tó................................................................................................... 217

Bevezetés Elterjedt és nem teljesen alaptalan vélekedés, hogy a matematikához istenadta tehetség kell. Azokban, akik matematikatanárnak készülnek, ez bizonyára megvan, hiszen ha nem lettek volna jó feladatmegoldók az iskolában, aligha merték volna ezt a pályát választani. Hogy ez a sok gyerekben meglévő, és az élet minden területén kamatoztatható adottság minél előbb kibontakozzék, annak nem elhanyagolható feltétele — habár nem szükséges és nem is elegendő — hogy a matematikát olyan tanártól tanulják, aki ki tudja fejleszteni a bennük lappangó tehetséget. Könyvünk szeretne segíteni abban, hogy erre felkészült tanárok tanítsák a matematikát. E magas célja mellett van egy földhözragadtabb is: összefoglalni, szintetizálni az egyetemen hallott matematikai anyagot, hogy a tanárjelölt megfelelően elren­ dezett tudás birtokában mehessen el az utolsó egyetemi megmérettetésre, a záró­ vizsgára. Ezt a szintézist a hallgató nem kaphatja meg az egyes féléves előadások során, és nincsenek külön szintetizáló előadások sem. Könyvünk azok számára lesz a leghasznosabb, akik maguk is megpróbálkoznak a szintézissel, végiggondolják, miről beszélhetnének a 18 vizsgatétel kapcsán, s utána szembesítik elképzeléseiket a könyv fejezeteivel. Akinek erre nem jut ereje, vagy ideje, azon a könyv még mindig segíthet. Persze, többet segít annak, aki nem az utolsó két hétben próbálja memorizálni a tartalmát, hanem legalábbis a záróvizsga előtti félév során rendsze­ resen tanulmányozza. Reménykedem azonban, hogy a könyv még azok számára is nyújt kapaszkodót, akik csak azért jutottak el a záróvizsgáig, mert a vizsgaeredmény olyan véletlen változó, amelynek nagy a szórása. Belőlük is válhat jó matematikatanár. Bárki megkérdezhetné: hát ennyi az egész, amit egy leendő középiskolai ta­ nárnak tudnia kell? Hiszen ezt a kétszáz oldalt „be lehet vágni” tíz nap alatt, aztán el lehet menni vizsgázni belőle. Attól tartok, hogy ez nem így van. Ez a könyv főleg azoknak szól, akik a tartalmát, vagy annak legalább 90 százalékát, egyszer vagy kétszer, kollokviumra vagy szigorlatra készülve részletekben már meggondolták, megtanulták, aztán, meglehet, nagy részét el is felejtették. De a tudás nem vész el, csak lapul az agysejtek szövetében. A könyv egyik célja, hogy ezt a rejtőzködő tudást életre keltse.

2

Bevezetés

Matematika záróvizsgán a diákok nagy többsége — szerencsére — életében egyszer esik át, ezért az esemény titokzatosnak látszik: mit kell ott tudni, hogyan zajlik az egész? Néhány gyakran feltett kérdésre itt is válaszolhatunk. Minek a bizonyítását kérdezhetik a záróvizsgán? Ritka eset, hogy bizonyítást kérdeznek, s ha igen, akkor is csak olyan egyszerű és alapvető dolgokét, mint pl. azét, hogy végtelen sok prímszám van. Azt viszont értékelni szokták, ha a vizsgázó nevezetes összefüggések ismertetésekor, amelyek bizonyításának történetesen létezik egy-két mondatban összefoglalható alapgondolata, ezeket a mondatokat minden külön ké­ rés nélkül elmondja. Ebből baj nem lehet; olyan vizsgáztatóval még nem ültem együtt, aki erre így reagálna: „Igen? Akkor fejtse csak ki ezt teljes részletesség­ gel!” . Az a megjegyzés elképzelhető, hogy „hát erre nem egészen pontosan tetszik emlékezni... mi a következő dolog, amiről beszélni akar?” Hogy még ez se fordul­ jon elő, sok jelentős tétel kimondása után egy-két (de legfeljebb három) mondatban utalunk a bizonyítás ötletére. Ha egy állításról ebben a könyvben csak annyit ol­ vashatunk, hogy „igazolható” , akkor az állítás igazolását komoly vizsgáztató — aki még világosban szeretne hazaérni — nem fogja kérni. A matematika egyetemi tananyagban szereplő fejezeteit többféleképpen le­ het és szokás tárgyalni. Semmi sem biztosítja, hogy az olvasó tanára ugyanazt a felépítést használta, mint e könyv szerzője. (Azt sem, hogy ugyanazokat a jelölé­ seket használta.) Ne aggódjunk emiatt. Mint Pascal írta Fermatnak, „az igazság ugyanaz Toulouse-ban, mint Párizsban” ; a különböző felépítések'és jelölések mögött ugyanaz a matematikai igazság áll. Gyakran a kissé különböző definíciók mögött is: egy kedves kollégám pl. a 0-t természetes számnak tekinti, én meg nem. Ezt sem egymástól, sem az esetleg más véleményen levő diáktól nem szoktuk rossz néven venni. Bizonyos ismereteinket — pl. a vektorokra vonatkozókat — több vizsgaté­ tellel kapcsolatban is „bevethetjük” . Ezek egyik-másika könyvünkben is többször szerepel, néha több oldalról megközelítve.Sok esetben hivatkozunk egy másik vizs­ gatételre, amelyben az éppen tárgyalt összefüggés ugyancsak előfordul. Az általános és középiskolák szokásos matematika-anyagára esetenként mint iskolai matematikára utalunk. Az „iskolai” jelző nem fejez ki sem lebecsülést, sem elismerést — azért van rá szükségünk, hogy a záróvizsga anyagának és a leendő tanár által megtanítandó anyagnak a kapcsolataira rámutassunk. Mindenképpen célszerű záróvizsga előtt az általános és középiskolai anyagot is feleleveníteni (a számokra vonatkozó ismereteket pedig a könyv függelékében átnézni — ha valakiről a záróvizsgán derül ki, hogy nem tud komplex számokkal számolni, reménytelen azzal védekeznie, hogy „az nem vizsgatétel” ). Az iskolai tananyagot illetően a jelen könyv nem nyújt segítséget; ki-ki szedje elő iskolai tankönyveit. Ugyancsak hasznos lehet Varga Tamás Matematika című lexikonjának forgatása (Műszaki Könyvkiadó,

Bevezetés

3

2001). Emellett a használatban lévő matematikai képlettárat sem árt végignézni. Egyes tényeket kétféleképpen is megfogalmazunk, nemcsak biztosabb felele­ venítésük, hanem a matematikai szakzsargon gyakorlása céljából is (ami sohasem árt és sohasem késő). A tanárjelöltek záróvizsgája bizonyos értelemben nyelvvizsga is: egyebek között azt méri, a vizsgázók milyen szinten beszélik szakterületük ma­ gyar nyelvét. Ehhez segítséget jelenthet, ha formailag különböző, de ugyanolyan jelentésű matematikai mondatokat mutatunk be. Ha valaki valamelyik fejezetben olyan ismeretekkel is találkozik, amelyeket eddigi vizsgáira készülve még sohasem kellett elsajátítania, ezeket is olvassa végig. Hátha a vizsgáztató fel sem tételezi, hogy a szóban forgó fontos (?) anyag vé­ letlenül minden tantárgyból kimaradt. Lehet, hogy ez tényleg így volt, de kissé kényelmetlen ezt a körülményt a vizsga során bizonygatni. Sajnálatos módon az egyik leggyakoribb szó e könyvben a definíciók igéje, a „nevezzük” . Nagyon sok fogalomra kell emlékezni egy záróvizsgán. Még azt az enyhítő elvet sem alkalmazhattam, amely természetes egy tudományos monográfia esetében: ott csak azokat a fogalmakat definiálják, amelyekre a könyv hátralévő részében is szükség lesz. Kutató számára gazdaságos stratégia lehet, ha csak az éppen folyó kutatásához szükséges ismereteket sajátítja el. Tanárt „hallottam róla” jellegű ismeretek is segíthetik munkájában. Hogyan vizsgázzunk? Elárulok egy titkot: a vizsgáztató bizottság akkor bol­ dog, ha a vizsgázó szájából olyan előadást hall, amelybe nem kell tíz másodper­ cenként belekérdezni. (így van ezzel többnyire a vizsgázó is.) És a vizsgáztató lelkiállapota befolyásolhatja az egyébként bizonyára nagy objektivitással megálla­ pított érdemjegyet. Természetesen, senki se igyekezzék a következő 18 kis előadást mondatról mondatra megtanulni, inkább próbáljon ezekhez hasonló tartalmú kis előadásokat önmaga (és a bizottság) számára önállóan összeállítani. Merjünk a vizsgán egyszerű dolgokról is beszélni! Ne féljünk attól, hogy a bi­ zottság ezt gyenge felkészülésünk jelének tekinti. Matematikus vizsgáztatót szak­ mailag értelmes mondatszövéssel sokkal inkább el lehet bűvölni, mint bonyolult anyag „felmondásával” . Az persze előfordulhat, hogy pl. a halmaz szemléletes fogalmának olyan részletes ismertetését, amilyet a 17. fejezet elején találunk, a vizsgáztatók félbeszakítják, és megkérik a vizsgázót, térjen át az anyag valamely hangsúlyosabb részére. Ez más fejezetekre is vonatkozik. Jó néhány fejezet tar­ talmaz aprólékoskodónak tűnő bevezetést, amelynek átolvasása segítheti a jobb megértést, de amelyet vizsgázás közben magam is valószínűleg egy-két mondatba sűrítenék. A vizsgáztatók — csakúgy, mint a tanulók — nagyra értékelik a stabil tudást. Aki a vizsgán a tanár arckifejezését vizsgálva próbálja újra fogalmazni mondatait, jó esetben is csak szánalmat vált ki. Sajátítsuk el olyan mértékben az anyagot,

4

Bevezetés

hogy a vizsga izgalmai közepette is merjünk egy kicsit gondolkozni a feltett kérdé­ seken. Törekedjünk erre céltudatosan, hogy később tanárként se szeppenjünk meg értelmes diákjaink váratlan kérdéseitől. Ez a könyv nem tankönyv, nem arra szolgál, hogy korábban nem is hallott tényeket és kapcsolataikat belőle tanuljuk meg. Nem is monográfia: nem vezérfonal valamely szőkébb szakterület önálló tanulmányozásához. Ez a könyv csak emlékez­ tető, segédlet arra, hogy már hallott dolgokat felidézzünk (erre a célra záróvizsga után is megfelel), illetve rendszerezzünk. Ha nincs mire emlékeztessen, még akkor is tájékoztat arról, mit kellett volna megtanulni korábban, és ez sem haszontalan. Tankönyvben, monográfiában elképzelhetetlen, hogy olyan fogalmat használjunk, amelynek a definíciója 50 oldallal később következik. Itt ez természetes; gondoljunk csak arra, hogy a halmazelmélet és a matematikai logika — tehát a matematika alapjai — a két utolsó vizsgatétel. Másrészt, ez a könyv nem tudós tanár kollégáimnak szól. Ha mégis kézbeve­ szik, ne botránkozzanak meg azt tapasztalván, hogy hiába keresnek benne egyes, szakmai körökben közismert matematikai igazságokat, másoknak meg csak egy­ szerű speciális esetét találják. Fájó szívvel, de kihagytam belőle még az algebra — saját szakterületem — számos olyan gyöngyszemét is, amelyet pedig a tanul­ mányai ötödik évéhez eljutott egyetemi hallgató nagyobb nehézség nélkül el tudna sajátítani. Lehetetlen egy rövid könyvecskét úgy megírni, hogy minden benne le­ gyen, amit egy leendő középiskolai matematikatanárnak tudnia illik. Ami benne van, arra is érvényes Hurwitz intése: „A matematika tanítása közben mindig igazat mondjunk, és csak az igazat, de ne mindig a teljes igazságot.” Ennek megfelelően őrizkedtem attól, hogy az emlékezetben tartandó fogalmakat a legtömörebben de­ finiáljam, s attól is, hogy a tételeket legélesebb alakjukban mondjam ki. Feltűnhet, hogy folytonosan differenciálhatóságot kötök ki olyan helyen, ahol az állítás vala­ mivel kevesebb feltevésből is következik. Másik példa: a csoportműveletet nem úgy definiálom, mint olyan asszociatív műveletet, amelyre vonatkozóan létezik legalább egy olyan baloldali egységelem, amelyre vonatkozóan minden elemnek van legalább egy baloldali inverze. Pedig ezek az apróságok az analízis meg az algebra szakem­ bere számára nagyon szépek, csak éppen nem tartoznak a leendő matematikatanár mindennapos szakmai fegyverzetéhez. Végül egy apró gyakorlati tanács: van tárgymutató, forduljunk hozzá, ha fo­ galmakkal vagy tételek elnevezésével van problémánk. A tárgymutató egyben név­ mutató; abban is segít, hogy a jeles tudósok nevével fémjelzett összefüggések vagy módszerek felfedezésének korszakáról is legyen elképzelésünk. (Ha nincs évszám, mindig huszadik századi matematikusról van szó.)

1. Kombinatorika Egykor elterjedt vélemény szerint a kombinatorika a véges halmazok elmélete. Az ilyen tömör definíció hozzávetőleges eligazításnak megfelel, de kiegészítések nél­ kül keveset mond. A matematikai analízis mibenlétét két fontos, bár távolról sem kizárólagos fejezetének, az integrál- és differenciálszámításnak a megemlítésével érzékeltethetjük. A kombinatorikáról is használhatóbb képet adunk, ha úgy jelle­ mezzük, mint a diszkrét matematika egyik ágát, amelynek nagy (de ugyancsak nem kizárólagos) területei az összeszámlálási problémák és a gráfelmélet. A „diszkrét” jelző arra utal, hogy a kombinatorika nem „folytonos” matematika: hasonlóan az algebrához és eltérően az analízistől, nem tartozik alapfogalmai közé a környezet. 1.1. Teljes indukció. Az összeszámlálási feladatok adott véges halmaz(ok)ból valamilyen módon képezett dolgok — pl. bizonyos tulajdonságú függvények — halmaza elemei számának (más szóval, számosságának) kiszámítására vonatkoz­ nak. Egy konkrét összeszámlálási feladat megoldása rendszerint egy természetes szám, egy általános feladaté pedig egy formula, amelybe természetes számokat he­ lyettesíthetünk. Másrészt, tetszőleges n elemű halmazt célszerűen „ábrázolhatunk” az 1, 2 ,..., n természetes számok halmazával — ez csak annyit jelent, hogy halma­ zunk elemeit megszámozzuk, s rájuk a hozzájuk tartozó számmal hivatkozunk. (Ez az eljárás azért célszerű, mert a természetes számok rendezését és a rajtuk végezhető műveleteket is felhasználhatjuk az összeszámlálási feladatok megoldása közben.) Mindezek alapján kézenfekvő, hogy a természetes számok tulajdonságait, különösképpen pedig a teljes indukció axiómája néven ismert alaptulajdonságukat lépten-nyomon alkalmaznunk kell: Jelölje N az összes természetes számok halmazát. Ha N valamely M részhal­ maza — tartalmazza az 1 számot, és — valahányszor tartalmazza a tetszőleges n számot, mindannyiszor tartal­ mazza n -I- 1-et is, akkor M — N. Ebből következik hogy természetes számokra vonatkozó állítások bizonyításá­ nál használhatjuk a teljes indukció módszerét:

6

Kombinatorika

Legyen A olyan állítás, amelyben szerepel az n természetes szám, s amelynek minden n természetes számra van értelme. Ekkor A valójában állítások egy végtelen sorozatának a logikai konjunkciója: A ( l ) A A ( 2) A . . . A A(n) A . . . , ahol pl. A(2) azt az állítást jelenti, amely A-ból úgy áll elő, hogy benne n-t 2-vel helyettesítjük. Ha — A( l ) igaz, és — abból a feltevésből, hogy valamely n-re A{n) igaz, be tudjuk látni, hogy A{n + 1) is igaz, akkor A minden természetes számra igaz. (Indokolás: válasszuk a teljes indukció axiómájában szereplő M -nek mindazon n természetes számok halmazát, amelyekre A{ri) igaz.) Egyszerűbben, ha egy természetes számokra vonatkozó állításról belátjuk, hogy igaz az 1 természetes számra, továbbá belátjuk, hogy valahányszor az állítás igaz valamely természetes számra, mindannyiszor igaz a rá következő természetes számra is, akkor ezzel bebizonyítottuk, hogy az állítás minden természetes számra igaz. (A két belátandó állítást nevezhetjük indukciós alapnak és indukciós lépésnek, az utóbbiban szereplő feltevést indukciós feltevésnek.) A teljes indukció módszerének számos változatát használjuk. Ha pl. csak azt tudjuk, hogy a tekintett állítás igaz n = 10-re, de az indukciós lépést meg tudjuk tenni, akkor csak arra következtethetünk, hogy az állítás minden 10-nél nem kisebb természetes számra igaz. Előfordulhat, hogy az indukciós lépésben nről csak n 4- 2-re tudunk lépni; ekkor csak arra következtethetünk, hogy az állítás minden páratlan számra (vagy, az előző példában, minden 10-nél nem kisebb páros számra) igaz. Ha azonban tudjuk, hogy A ( l ) is, A { 2) is igaz, akkor az A{n) => A( n 4- 2) indukciós lépésből következik A helyessége minden természetes számra. Az indukciós bizonyítás két része helyett elegendő azt belátnunk, hogy ( 1) bármely n-re, ha az igazolandó állítás igaz minden n-nél kisebb természetes számra, akkor igaz n-re is. (Persze, A( l ) igazságának követelménye az (1) mondatban is benne van, de az indukciós lépésben több feltételt használhatunk ki.) Néha a következőt bizonyítjuk, ami (l)-gyel ekvivalens: ( 2) Ha az állítás nem igaz n-re, akkor van olyan n-nél kisebb k természetes szám, amelyre úgyszintén nem igaz. Világos, hogy ha az állítás nem igaz valamely n-re, (2)-ből következik, hogy létezik természetes számokból álló végtelen szigorúan monoton csökkenő számso­ rozat, ami lehetetlen. Az ilyen „indirekt teljes indukciós” bizonyítást „végtelen leszállásnak” (a francia descente infinie tükörfordítása) nevezzük. A teljes indukció tipikus alkalmazása természetes-szám-változót tartalmazó képletek érvényességének igazolása. Erre példa az első n négyzetszám összegét

7

1.2. Egyszerű összeszámlálási feladatok

megadó képlet, amelyet az integrálásba való bevezetéskor parabolaív alatti terület meghatározására használunk. Egyszerű (geometriai) összeszámlálási feladat: leg­ feljebb hány részre bontja n egyenes a síkot? A megoldáshoz — azaz a keresett számot szolgáltató képlet megadásához — megvizsgáljuk az n = 1, 2 , 3 , . . . eseteket mindaddig, amíg sejtésünk nem támad a képletre vonatkozóan (a sejtést a teljes indukció módszere nem szolgáltatja!). Ezután a sejtést teljes indukcióval igazol­ hatjuk. (Oldjuk meg a feladatot!) Teljes indukcióval olyan állítások is „támadhatók” , amelyek pl. természetes szám-párokra vonatkoznak; egyszerű példa az (rrm)n = x mn azonosság igazolása minden m-re és n-re. Ugyancsak teljes indukcióval láthatjuk be néhány apró, a hétköznapi józan ész számára magától értetődő, de fontos észrevétel helyességét is, amelyeket gyakran használunk kombinatorikai (és egyéb matematikai) meggondolásokban. Ilyen pl. a skatulya-elv két változata: Ha n < k, és n skatulyába k golyót rakunk, akkor legalább egy skatu­ lyába legalább két golyó kerül. Ha n < k, és n golyót k skatulyába rakunk, akkor legalább egy skatu­ lyába nem jut golyó. A skatulya-elvvel rokon, sokszor alkalmazott állítás: n elemű halmaznak ugyan­ annyi elemű halmazba való leképezése akkor és csak akkor injektív (kölcsönösen egyértelmű), ha szürjektív (azaz „ráképezés” ). (Lássuk be teljes indukcióval!) A skatulya-elv használható változata (általánosítása) a következő állítás is: Ha mn < k és n skatulyába k golyót teszünk, akkor legalább egy skatulyába m-nél több golyó kerül. Példa a skatulya-elv alkalmazására: mutassuk meg, hogy ha az első 200 természetes szám közül kiválasztunk 101-et, a kiválasztottak között biztosan lesz legalább két relatív prím szám. 1.2. Egyszerű összeszámlálási feladatok.

Ilyen feladatok megoldásához gyak­

ran szükségünk lehet a következő — alapelveknek is tekinthető — megállapításokra (ezért mindig gondoljunk arra, nem használhatnánk-e valamelyiket): — Ha két halmaz között létezik bijekció (=bijektív leképezés), akkor ugyanannyi elemük van (=számosságuk egyenlő). — Idegen halmazok egyesítésének számossága egyenlő számosságaik összegével. — Halmazok halmazelméleti szorzatának számossága egyenlő számosságaik szor­ zatával. A legegyszerűbb összeszámlálási feladatok leképezések (függvények) halmaza­ inak számosságára vonatkoznak. Hány különböző leképezése van egy k elemű hal­ maznak egy n elemű halmazba? Világos, hogy a válasz független attól, hogy mik a tekintett halmazok elemei, ezért gondolhatunk a k = { ! , . . . , & } és n = { 1, . . . , n }

8

Kombinatorika

halmazokra. Egy-egy ilyen ip : k —> n leképezést a

táblázattal (mátrixszal) adhatunk meg, ahol az első sor mindegyik i eleme alatt az 1 . ,n elemek egyike áll, mégpedig i' = •••,Pk csupa különböző Fermat-féle prímek. A 2P — 1 alakú prímszámokat, ahol a p kitevő is prím, Mer senne-féle prí­ meknek nevezzük. Segítségükkel írhatók le a páros tökéletes számok. Tökéletes számon olyan természetes számot értünk, amely egyenlő nála kisebb pozitív osztói összegével. Példák: 6 , 28, 496. A páros tökéletes számok pontosan azok a számok, amelyeknek az alaptétel szerinti prímhatványszorzat alakja 2P - 1( 2P — 1), ahol a második tényező prímszám. Nem ismeretes, hogy létezik-e végtelen sok Mersenneféle prím, ezért azt sem tudjuk, van-e végtelen sok páros tökéletes szám. Az sincs még eldöntve, létezik-e páratlan tökéletes szám. Egy másik nagy megoldatlan prob­ léma a 18. század közepén felmerült Goldbach-sejtés bizonyítása. A sejtés szerint minden 2-nél nagyobb páros szám előállítható két prímszám összegeként. Ezzel egyenértékű a sejtés másik alakja: minden 5-nél nagyobb egész szám előállítható három prímszám összegeként. Annyit sikerült bebizonyítani (a 20. században), hogy létezik olyan V, hogy minden V-nél nagyobb egész négy prímszám összege, másrészt létezik olyan 5 egész, hogy minden egész szám legfeljebb S számú prím­ szám összege. V létezését Vinogradov, S létezését Snirelman mutatta meg, aki azt is belátta, hogy S < 800000. Ma valamivel többet tudunk: S < 20. 3.4. Kongruenciák. Minden m természetes számhoz megadható egy ekviva­ lenciareláció az összes egész számok halmazán: tekintsük ekvivalensnek az a és b számokat, ha m-mel való maradékos osztásuk maradéka egyenlő. Ha ez teljesül, azt mondjuk, hogy a kongruens b-vel modulo m, és a következőt írjuk: a = b (mód m). Magát az így bevezetett relációt modulo m kongruenciának nevezzük. A kongru­ enciákat az oszthatósági reláción keresztül is bevezethetjük: a = b (mód m) m \a - 6.

Számelmélet

34

A kongruenciákat a műveletek megőrzik: bármely m természetes számra és a, b, c, d egészekre a = b (mód m)

és

c = d (mód m) ==> a + c = 6 + d (mód m),

és hasonló igaz összeadás helyett kivonásra és szorzásra is. Az osztással nincsenek ennyire jó viszonyban a kongruenciák, az oszthatósági relációval való kapcsolatuk­ ból következik azonban, hogy, ha d \a, b, m, akkor a = b (mód m) 3 = 3 (mód ^-j), d d d speciálisan, ha c és m relatív prímek, akkor ac = be (mód m) => a = b (mód m). Ismerve a kongruenciák tulajdonságait, nem nehéz igazolnunk az iskolai ma­ tematikában tanult oszthatósági szabályokat. Pl. a 11-gyel való oszthatóság szük­ séges és elegendő feltétele (a számjegyek váltakozó előjellel vett összege osztható

11-gyel) abből következik, hogy 10 = - 1 (mód 11), s ezért 10 hatványai váltakozva ± l-g y e l kongruensek a l l modulusra vonatkozóan. Lineáris kongruencián ( 2)

ax = b (mód m)

alakú jelsorozatot értünk, a ( 2) lineáris kongruencia megoldásai pedig azok az egész számok, amelyeket x helyére írva érvényes kongruenciát kapunk. Az, hogy u meg­ oldása ( 2)-nek, azt jelenti, hogy m \ au — 6, azaz van olyan v egész, hogy u és v együtt megoldását képezi az ax —m y = b lineáris diophantoszi egyenletnek. Ez az észrevétel a lineáris kongruencia megoldásai megkeresésének feladatát — röviden, a lineáris kongruencia megoldását — visszavezeti a lineáris diophantoszi egyenlet megoldására. Eszerint (2)-nek akkor és csak akkor van megoldása, ha (a, m ) | b, s ekkor egy u megoldás a-n és m-en végzett euklideszi algoritmus segítségével ki is számítható. Az összes megoldások pedig az u-val modulo kongruens összes egész számok. Az adott m számmal való maradékos osztásnál ugyanazt a maradé­ kot adó összes egész számok halmazát modulo m maradékosztálynak nevezzük. ( 2) megoldásai tehát egyetlen modulo maradékosztályt alkotnak. Ha több lineáris kongruencia van megadva, és ezek közös megoldásai után érdeklődünk, akkor szimultán kongruenciarendszerről beszélünk. A megoldható­ ságnak triviális szükséges feltétele, hogy külön-külön mindegyik kongruenciának létezzék megoldása. Ha ez így van, akkor — mivel mindegyik kongruencia összes

35

3.5. Számelméleti függvények

megoldásai egy maradékosztályt alkotnak valamilyen modulusra nézve — a szimul­ tán kongruenciarendszer a következő alakba írható át: x = &i (mód m i) x = &2 (mód 7712)

x = bk (mód TYik) Az a legegyszerűbb eset, amikor a modulusok páronként relatív prímek. Ilyenkor létezik megoldás, és az összes megoldások egyetlen maradékosztályt alkotnak modulo rrii7n2 ■. .mjt. Ez a kínai maradéktétel. (Azért hívjuk így, mert egy közel két évezredes kínai szövegben is előfordult ilyen feladat.) 3.5. Számelméleti függvények. így nevezzük az olyan függvényt, amelynek értelmezési tartománya a természetes számok halmaza, értékei pedig (bármilyen) számok. Ha pl. minden természetes számhoz pozitív osztói számát, vagy ezek össze­ gét rendeljük, akkor számelméleti függvényeket definiáltunk. Ezeket megfelelően a v ill. a betűk jelölik. Minden számelméleti függvény megadása egy számsorozatot ad meg, ti. a függvény 1,2 -----számokon felvett értékeinek a sorozatát. (Nem meg­ lepő persze, hogy általában másfajta sorozatokat vizsgálnak az analízisben, mint a számelméletben.) Két relatív prím szám szorzatának összes osztóit megkapjuk, mégpedig mind­ egyiket egyszer, ha minden lehetséges módon képezzük egy-egy osztójuk szorza­ tát. Innen következik, hogy, ha (a, 6) = 1, akkor v(ab) = u(a)v(b), és hasonló­ képpen cr(ab) = a(a)a(b). Az ilyen — tehát relatív prím számok szorzatán té­ nyezőnként kiszámítható — számelméleti függvényeket gyengén multiplikatívnak nevezzük. Mivel bármely n természetes szám alaptétel szerinti p\l . . . p ek prím­ hatványszorzat alakjában a különböző prímhatvány tényezők relatív prímek, gyen­ gén multiplikatív / függvény értékét az n helyen / {pl1) .. •f ( p kk) adja. Ezért pl. v(n) = (ei + 1) . . . (ek 4- 1). A a függvény gyenge multiplikativitását pedig a páros tökéletes számokat leíró (már említett) képlet megtalálásához lehet felhasználni. Egy további jól alkalmazható számelméleti függvény az Euler-féle függvény, amelynek értéke az n helyen az n-nél nem nagyobb, hozzá prím természetes számok száma. A klasszikus Euler-féle kongruenciatétel azt mondja ki, hogy, ha (a, m) = 1, akkor a*(m> = 1 (mód m). Ennek speciális esete a „kis” Fermat-tétel ha p prím és p\a (ami másképpen azt jelenti, hogy (a ,p ) = 1), akkor o p_1 = 1 (mód p). Ez a tétel nem jel­ lemzi a prímszámokat; vannak olyan m számok, hogy m nem prím, és mégis

36

Számelmélet

am~ i = 1 (mód m), minden m -mel relatív prím a-ra. Ezek az álprímek vagy Carmichael-számok; belőlük is végtelen sok van, a legkisebb 561. Ellenben egy másik klasszikus kongruenciatétel csak prímszámokra igaz. Ez Wilson tétele: ha p prím, akkor (p — 1) ! = —1 (mód p). A

0 ), akkor p{n) = ( —l ) k.

4. Csoportok 4.1. Csoportmüveletek. Az algebra a matematikának az az ága, amely a műveletekkel felszerelt halmazokkal foglalkozik. Műveletnek a H halmazon olyan leképezést nevezünk, amely minden H -ból képezett elem-n-eshez H egy elemét rendeli, a művelet tehát a H n halmaznak H -ba való leképezése. Itt n bármely természetes szám lehet, a legfontosabb eset azonban az, amikor n = 2. Ekkor a művelet binárisnak vagy kétváltozósnak mondjuk — valójában ekkor a művelet egy kétváltozós függvény H -n, amelynek érkezési halmaza is H. Természetes példák az összeadás és a szorzás az összes természetes számok N halmazán. A kivonás nem művelet az N halmazon, mert pl. olyan számpárhoz, amelynek a második eleme nagyobb, a kivonás nem rendel természetes számot. Ezt a tényt úgy szoktuk kife­ jezni, hogy a kivonás nem végezhető el a természetes számok halmazában (persze, bármely két természetes számnak van különbsége, csak az nem mindig természetes szám). Az osztás sem végezhető el — azaz nem művelet — N-ben. Az összes egész számok Z halmazában már elvégezhető a kivonás, de az osztás még ott sem. Am pl. a pozitív racionális számok Q + halmazában elvégezhető a szorzás is, az osztás is; igaz, ebben a halmazban viszont a kivonás nem végezhető el. A számok összeadása asszociatív művelet: ha a, b, c tetszőleges számok, (a + b) + c = a + (6 + c). Ezt magától értetődőnek tekintjük, pedig nem minden művelet asszociatív, pl. már a kivonás sem: (3 — 2) — 1 3 — (2 — 1). Asszoci­ atív műveletek: a számok szorzása, adott halmaz önmagába való leképezéseinek szorzása (két leképezés szorzata az a leképezés, amely egymás utáni elvégzésükkel valósítható meg), azonos típusú négyzetes mátrixok szorzása, stb. Tekintsük a szorzást a pozitív racionális számok Q + halmazában. Minden r € Q + számra igaz r ■ 1 = r, továbbá minden r-hez van olyan szám Q +-ban, amelynek ?’-rel vett szorzata éppen 1 (ti. az 1fr szám). Ebből a megállapítás­ ból következik, hogy Q +-ban az osztás is elvégezhető: a/b = a • (1 fb). Hasonló megfigyelést végezhetünk az adott típusú nemelfajuló (azaz 0-tól különböző determinánsú) négyzetes mátrixok szorzására vonatkozóan is: minden A mátrixra igaz A - E = A ( é s E - A = A is), továbbá, ha \A\ ^ 0, akkor van olyan A ~ l mátrix, hogy A •A ~ l = E (és A ~ l ■A = E). Itt a zárójelbe tett kiegészítések nem teljesen

39

4-1. Csoportműveletek

nyilvánvalóak, mert a mátrixok szorzása nem kommutatív: A ■B — B ■A nem min­ den A, B mátrixpárra teljesül. Ezért mátrixok esetén kétféle „osztás” is végezhető, igaz, nem minden mátrixpáron: az A és B mátrixok hányadosának tekinthetjük az A •B ~ l és a B ~ l •A mátrixot is. A matematikában lépten-nyomon találkozunk olyan műveletekkel, amelyek az előző két példán is megfigyelt tulajdonságokkal rendelkeznek. Ezért célszerű e tulajdonságok együttes előfordulásának külön nevet adni. Ez a név a csoport. Legyen H nemüres halmaz, amelyen meg van adva egy művelet. A műveletet jelölje o ; tehát a művelet által az a, b e H elempárhoz rendelt elem jele legyen a o b. Azt mondjuk, hogy H csoportot alkot a o műveletre nézve, vagy másképpen, o csoportművelet a H halmazon, ha ( 1) o asszociatív; ( 2) van olyan e £ H , hogy minden a £ H -ra a o e = e o a = a (az ilyen e elemet a H csoport — vagy a o művelet — egység elemének nevezzük); (3) minden a £ H -hoz létezik olyan a' € H, hogy a o a ' = a ' o a = e (az ilyen a' elemet az a elem inverzének nevezzük). Az inverzről beszélve nem kell említeni, hogy az e egységelemre vonatkozó inverzről van szó, mert csoportnak csak egy egységeleme van: ha e\ is, e-i is egy­ ségeleme, akkor e\ = e\ o — e2. Nem véletlen, hogy a két bevezető példában a szorzásnak nevezett csoportművelet mellett ott van annak inverz művelete, az osztás is. Ez minden csoportra igaz: inverz műveletnek tekinthetjük az a, b elem­ párhoz az a o b ~ l elemet rendelő műveletet, de épp így a hozzájuk a 6-1 o a elemet rendelő műveletet is; ha a csoport művelete kommutatív, akkor persze ez a két művelet ugyanaz. (Mindamellett, amikor a tanulók a szorzás után az osztással is­ merkednek, az egyik műveletet osztásnak, a másikat bennfoglalásnak nevezik, ami elvileg sem kifogásolható, az ismerkedést pedig bizonyára elősegíti.) Észrevéve, hogy a o b ~ l nem más, mint az x ob= a egyenlet megoldása, b 1 o a pedig a bo x = a egyenlet megoldása, megállapíthatjuk, hogy bármely csoportban ezeknek az egyen­ leteknek mindig (azaz minden a és b csoportelemre) van megoldása. A kiemelt egyenletek megoldhatósága tehát az inverz művelet (vagy, ha a művelet nem kom­ mutatív, az inverz műveletek) elvégezhetőségét jelenti. (Van-e inverz művelete a hatványozásnak?)

40

Csoportok

Ha egy művelet olyan, hogy ezek az egyenletek mindig megoldhatók, akkor a műveletet invertálhatónak nevezzük. Látjuk, hogy minden csoportművelet invertálható. Asszociatív műveletekre ennek a megfordítása is igaz: ha egy asszociatív művelet invertálható, akkor az csoportművelet. (Egységelem és inverzek létezését kell igazolni; megsejthetjük és számolással igazolhatjuk, hogy bármely a elemre az a o x = a egyenlet megoldása egységelem lesz, a „6 o x = egységelem” egyenlet megoldása pedig b inverze). A csoport definíciója tehát a következő, az eredetivel ekvivalens alakban is kimondható: a H nemüres halmaz csoportot alkot a o műve­ letre nézve, ha o asszociatív és invertálható. (A számtani közép képzése művelet a racionális számok halmazán. Csoportművelet-e?) A csoportfogalmon alapul másik két klasszikus algebrai struktúrafajta, a gyűrű és a test definíciója. Példaként idézzük fel a számtest (egyik lehetséges) definícióját: számok egy halmaza pontosan akkor test, ha csoport az összeadásra nézve (ahonnan következik, hogy van additív egységeleme, tehát tartalmazza a 0 számot), és a 0-tól különböző elemeinek halmaza csoport a szorzásra nézve. 4.2. Példák. Csoportokkal a matematika minden területén találkozunk. íme egy sereg példa csoportműveletre: — az összeadás — az (összes) egész (racionális, valós, komplex) számok, — az egész (racionális, valós, komplex) együtthatós polinomok, — az egész (racionális, valós, komplex) számokból álló, rögzített típusú négyzetes mátrixok halmazán, — a szorzás — a 0-tól különböző valós (komplex) számok — a pozitív racionális (valós) számok, — az 1 abszolút értékű komplex számok, — rögzített n-re az összes n-edik komplex egységgyökök halmazán, — a szorzás a rögzített típusú, nemzérus determinánsú (vagy 1 abszolút értékű determinánssal, vagy 1 értékű determinánssal) rendelkező mátrixok halmazán, valamint ennek az összes ortogonális mátrixokból álló részhalmazán (a —1 determinánsú mátrixok nem alkotnak csoportot; miért?), — a leképezésszorzás — adott véges halmaz összes permutációinak, valamint tetszőleges adott halmaz összes bijektív transzformációinak a halmazán, — a sík összes izometriáinak (azaz távolságtartó transzformációinak) hal­ mazán,

4.3. Csoportelméleti alapfogalmak

41

— a sík összes mozgásainak (azaz irányítástartó izometriáinak) halmazán, — a tér összes olyan izometriáinak (vagy mozgásainak) halmazán, amelyek egy adott ponthalmazt (pl. az összes egész koordinátájú pontok halma­ zát, egy adott gömb felületét alkotó pontok halmazát, vagy egy síklapú testet, speciálisan szabályos testet) önmagába visznek át, — az összeadás a [0 , 1] intervallumon értelmezett valós függvények (vagy folyto­ nos függvények, vagy differenciálható függvények) halmazán, — a szorzás a [0 , 1] intervallumon értelmezett és ott sehol sem 0 értékű valós függvények halmazán, — a leképezésszorzás mindazoknak a [0 , 1] intervallumon értelmezett szigorúan monoton növekvő, folytonos valós függvényeknek a halmazán, amelyek a 0 és 1 helyen megfelelően a 0 és 1 értéket veszik fel. Példáinkban számok szorzása esetén az egységelem mindig az 1 szám, függ­ vények szorzásánál a konstans 1 függvény, mátrixok szorzásánál az egységmátrix; ös jzeadásnál a 0 szám, a zérusmátrix, ill. a konstans 0 függvény; leképezésszorzás­ nál az identikus leképezés (utolsó példánkban ez az y = x függvény). A 0-t ad­ ditív (=összeadásra vonatkozó) egységelemként is említhetjük, megkülönböztetve a multiplikatív (szorzásra vonatkozó) egységelemtől. Hasonlóképpen beszélhetünk számok (mátrixok, függvények) additív és multiplikatív inverzéről. Szám additív inverze az ellentettje (vagy negatívja), multiplikatív inverze a reciproka. Az / függ­ vény additív inverze a z i ^ —f { x ) , multiplikatív inverze az x ■—* függvény, a leképezésszorzásra vonatkozó inverze utolsó példánkban az a függvény, amelyet a matematikai analízisben is / inverz függvényének nevezünk. (Vegyük figyelembe, hogy egyváltozós függvényekből összetett függvény képzése nem más, mint rajtuk a leképezésszorzás elvégzése.) Ha a H csoport művelete kommutatív, H -t Ábel-csoportnak nevezzük. Leg­ egyszerűbb példáink, amelyekben a művelet neve összeadás, mind Abel-csoportok. Innen ered az a gyakorlat, hogy Abel-csoportokat vizsgálva műveletüket rendsze­ rint összeadásnak nevezzük, és így is jelöljük. Ez az additív jelölés, ami maga után vonja, hogy az egységelemet 0 , az a elem inverzét —a jelöli. Ha pedig nem Abel-csoportokról beszélünk (vagy legalábbis nem kötjük ki előre, hogy csak Abelcsoportokról lesz szó), akkor a művelet szokásos neve szorzás, és ennek megfelelő a jelölése is ( multiplikatív jelölés, ilyenkor a csoport egységelemét az 1 jellel jelöljük). Bármely csoportban indukcióval bevezet­ hetjük a természetes szám kitevőjű hatványozást: a € H -ra a 1 = a, és ha n > 1, an = a n_1 •a. Ekkor bármely m, n természetes számokra igaz az 4 .3 . C s o p o r te lm é le ti a la p fo g a lm a k .

42

Csoportok

azonosság, amit ugyancsak n szerinti indukcióval láthatunk be. Ha értelmet aka­ runk tulajdonítani az a csoportelem bármilyen (tehát nem csak pozitív) egész kitevős hatványának, ezt úgy célszerű tennünk, hogy a most látott, jól használ­ ható azonosság a kiterjesztett hatvány-fogalomra is érvényben maradjon. (Azt a gondolatot, hogy valamely definíció érvényességi körét úgy célszerű kiterjeszteni, hogy valamely rá vonatkozó összefüggés a kiterjesztés után is érvényben maradjon, permanencia-elvnek nevezhetjük.) így, ha a°-t akarjuk bevezetni, az csak olyan cso­ portelem lehet, amelyre a°a1 = a 0+1 = a 1, azaz a°a = a. ebből pedig jobbról a~lgyel szorozva kapjuk, hogy a° = 1. (Nem azt bizonyítottuk, hogy a° = 1, hanem azt, hogy a permanencia-elv alapján a°-t 1-nek kell definiálnunk!) Ehhez hasonlóan láthatjuk be, hogy a -1 -et a inverzének, és bármely n természetes számra a~n-t a ~ l n-edik hatványának kell definiálnunk. A 0 kitevős és negatív egész kitevős hatvá­ nyokat ilyen módon minden csoportban bevezethetjük, nem csak a 0-tól különböző számokon. (Indukcióval azt is bebizonyíthatjuk, hogy bármely csoportban, bár­ mely m, n természetes számokra igaz az (am)n = amn azonosság. Bevezethető!-e ebből kiindulva minden csoportban a törtkitevőjű hatványok?) Ha egy G csoportnak valamely H részhalmaza ugyancsak csoport a G-beli csoportműveletre nézve, akkor azt mondjuk, hogy H részcsoportja G-nek. így pl.: — A páros számok additív csoportja részcsoportja az egész számok additív cso­ portjának, az pedig a racionális számok additív csoportjának. — Véges halmaz összes páros permutációi is részcsoportot alkotnak a halmaz tel­ jes permutációcsoportjában. Ezt a halmaz alternáló csoportjának nevezzük. (Minden permutáció transzpozíciók — két elemet felcserélő, a többit válto­ zatlanul hagyó leképezések — szorzata; a permutáció páros, ha páros számú transzpozíció szorzata.) — a sík mozgásainak csoportja részcsoportja a sík izometriái csoportjának, — kocka mozgáscsoportja — azaz a kockát önmagába átvivő mozgások csoportja — részcsoportja a kocka köré írható gömb mozgáscsoportjának. (Kérdés: hány eleme lehet egy krumpli — mint ponthalmaz — mozgáscsoportjának? És egy tojásénak?) Csoport részhalmazának elemeiből és azok inverzeiből akárhány tényezős szor­ zatokat képezhetünk. Az így keletkező csoportelemek halmaza részcsoport, ame­ lyet az adott halmaz által generált részcsoportnak nevezünk, magát a halmazt pedig e részcsoport generátorrendszerének nevezzük. Pl. {1 } generátorrendszere az (összes) egész számok additív csoportjának, míg a { 4 , 6} halmaz az összes páros számok alkotta részcsoportot generálja (vagyis annak a generátorrendszere). Véges halmaz összes transzpozíciói a halmaz teljes permutációcsoportját generálják — ezt néhány sorral előbb, másképpen, már megfogalmaztuk. Ha csoport egy H részcso­

4.3. Csoportelméleti alapfogalmak

43

portját annak valamely S részhalmaza generálja, akkor H a csoport legszűkebb olyan részcsoportja (vagy, ami ugyanazt jelenti, összes olyan részcsoportjának kö­ zös része), amely az S halmazt tartalmazza. Példáink között vannak véges és végtelen csoportok, ti. olyanok, amelyeknek véges számú, ill. végtelen sok eleme van. Alkalmas véges csoportok vizsgála­ tára visszavezethető az a nevezetes probléma, hogy mely magasabb fokú algebrai egyenletek oldhatók meg alapműveletek és egész kitevős gyökvonás véges számú alkalmazásával. Ezért a véges csoportok elmélete igen gazdag. A legelső általános érvényű megállapítás véges csoportokról még a 18. századból ered: Lagrange tétele: Véges G csoport bármely H részcsoportja elemeinek száma osztója G elemei számának. A bizonyításhoz azt kell megfigyelni, hogy ha H min­ den elemét megszorozzuk a csoport egy rögzített a elemével, ugyanarról az oldalról, mondjuk jobbról, akkor a keletkező szorzatok halmaza — amelyet H a-val jelölhe­ tünk, és H szerinti jobboldali mellékosztálynak nevezünk — ugyanannyi elemű, mint H ; másrészt, ha a és 6 különböző elemei G-nek, akkor a Ha és Hb mellékosz­ tályok vagy egyenlők, vagy idegenek. Ezért, ha a H szerinti különböző jobboldali mellékosztályok számát megszorozzuk H elemeinek a számával, akkor G elemei szá­ mát kapjuk; az utóbbi tehát osztható H elemeinek számával. Csoport elemeinek a számát a csoport rendjének nevezzük. Emellett beszélünk csoport elemének a rendjéről is: ha az a elem n-edik hatványa a csoport egységeleme, de n-nél kisebb kitevőjű hatványai mind különböznek az egységelemtől, akkor azt mondjuk, hogy a rendje n (ha ilyen n nem létezik, akkor a végtelen rendű). Véges csoportban nincs végtelen rendű elem, és a két rend-fogalom között a következő kapcsolat van. Ha egy G csoport a elemének rendje n, akkor az a, a2, . . . ,a n = 1 elemek mind különbözők és egy n rendű ciklikus részcsoportot alkotnak G-ben. ( Ciklikusnak nevezzük a csoportot, ha egyetlen eleme összes hatványaiból áll.) Ha ezt a megállapítást Lagrange tételével egybevetjük, a következőt kapjuk: véges csoport bármely elemének rendje osztója a csoport rendjének. Ebből látható, hogy r rendű csoport bármely elemének r-edik hatványa az egységelem (valóban, ha a rendje n, akkor r = nk, ahol k egész, és ezért ar = ank = (an)k = l k = 1). Ennek a ténynek speciális esete Euler nevezetes számelméleti tétele: ha (a, m) = 1, akkor a ^ az egyenletrendszer determinánsa, dj (j = 1, . . . , n) pedig annak a mátrixnak a determinánsa, amelyet úgy kapunk, hogy az egyenletrendszer mátrixában a j-edik oszlop helyébe a szabad tagokból álló oszlopot írjuk. Ezeket a megfigyeléseket foglalja össze Cramer szabálya: A szabályos lineáris egyenletrendszernek létezik megoldása, egyetlen megoldása van, és azt az Xj = (j = 1, . . . ,n) képlet szolgáltatja. A Gauss-féle eliminációval kapcsolatban kiderült, hogy az általános lineáris egyenletrendszernek vagy nincs megoldása, vagy egyetlen megoldása van, vagy pe­ dig végtelen sok megoldása van. Hogy melyik eset mikor lép fel, az egyenletrendszer mátrixának rangja segítségével is eldönthetjük. A Kronecker-Capelli-tétel meg­ mondja, hogy az egyenletrendszer megoldható-e. A Gauss-elimináció közben vég­ zett elemi átalakítások az egyenletrendszer mátrixának rangját változatlanul hagy­ ják, így ez a rang k (a Gauss-elimináció ismertetésénél használt jelöléssel). Ezért a megoldható általános lineáris egyenletrendszernek akkor van egyetlen megoldása, ha mátrixának rangja egyenlő ismeretlenéinek számával, és akkor van végtelen sok megoldása, ha mátrixának rangja kisebb ismeretlenéi számánál. A lineáris egyenletrendszer homogén, ha szabad tagjai mind eltűnnek. („Homogén” egyneműt jelent; ebben az esetben a tagok annyiban egyneműek, hogy mind egyetlen ismeretlen tényezőt tartalmaz.) Ha ( 1) homogén (azaz &i = . . . = bn = 0), akkor a csupa 0 szám-n-es megoldása (l)-nek; ezt triviális megoldásnak nevezzük. Homogén lineáris egyenletrendszernek tehát mindig van triviális megol­ dása, és ha mátrixának rangja egyenlő ismeretlenéi számával, akkor nincs is más megoldása, különben végtelen sok megoldása van. Az a tény, hogy két, ugyan­ azt a polinomfüggvényt megadó n-edfokú polinom együtthatói ugyanazok (lásd a 2. tételt), azon múlik, hogy a polinomfüggvények értékét n + 1 különböző helyen felírva a két polinom megfelelő együtthatóinak különbségeire egy homogén lineá­ ris egyenletrendszert kapunk, amelynek determinánsa (Vandermonde-féle és ezért) nem zérus; ennélfogva az egyenletrendszernek csak triviális megoldása van. Az ( 1) egyenletrendszer szabad tagjainak oszlopa egy m dimenziós vektor, is­ meretlenéit pedig egy n dimenziós oszlopalakban felírt ismeretlen vektornak — rö-

5.4■ Vektoregyenlet, mátrixegyenlet

57

viden oszlopvektomak — tekinthetjük. Ha minden n dimenziós oszlopvektort balról megszorzunk egy rögzített m x n típusú A mátrixszal, akkor eredményül mindig m dimenziós oszlopvektort kapunk. Az A-val való szorzás tehát az n dimenziós (komplex) vektorteret az m dimenziós komplex vektortérbe képezi le; az is látható, hogy az ilyen leképezés mindig lineáris (azaz felcserélhető az összeadással és a skalárral való szorzásokkal). Az általános lineáris egyenletrendszer megoldhatóságára és megoldásaira vonatkozó feladatok eszerint átfogalmazhatok vektorterek lineáris leképezéseire vonatkozó feladatokká, a következő módon: Adott az n dimenziós vektortérnek egy $ lineáris leképezése az m dimenziós vektortérbe, és adott egy m dimenziós (3 vektor. Kérdések: van-e olyan n dimenziós vektor, amelyet a (3 vektorba képez le, s ha igen, hány ilyen vektor van, és hogyan számíthatók ki ezek. A Kronecker-Capelli-tétel, a Gauss-féle elimináció és Cramer szabálya lényegében ezekre a kérdésekre válaszolnak, jóllehet vektorterekre nem tartalmaznak közvet­ len utalást. A homogén lineáris egyenletrendszer esetében (3 a zérusvektor, amely minden lineáris leképezésnél a zérusvektor képe; az összes megoldások ekkor a line­ áris leképezés magját alkotják, amely a lineáris leképezés értelmezési tartományát alkotó vektortérnek altere. Homogén lineáris egyenletrendszer megoldásai tehát mindig alteret alkotnak. (Ez közvetlenül is belátható, megmutatva, hogy homogén lineáris egyenletrendszer megoldásainak összege is, c-szerese — „ skalárszorosa” — is megoldás, tehát bármely lineáris kombinációjuk is megoldás.) A megoldások altere n - k dimenziós, ahol k a tekintett lineáris leképezés mátrixának (azaz az egyenletrendszer mátrixának) rangja. Ez a megállapítás a vektorterek lineáris le­ képezéseire vonatkozó dimenziótétel speciális esete. Az általános lineáris egyenletrendszer megoldásainak halmaza majdnem ugyanilyen egyszerűen jellemezhető. Tekintsük ugyanis az (1) egyenletrendszert A • £ = (3 alakban, és nevezzük (l)-hez tartozó homogén lineáris egyenletrendszer­ nek az A • £ = 0 egyenletrendszert. Ha 7 egy rögzített megoldása (l)-nek, és S tetszőleges n dimenziós vektor, 7 + ő akkor és csak akkor megoldása (l)-nek, ha S megoldása az (l)-hez tartozó homogén lineáris egyenletrendszernek. (Erről be­ helyettesítéssel egyből meggyőződhetünk.) Részletesebben: az általános lineáris egyenletrendszer összes megoldásait (és csak ezeket) megkapjuk, ha egy rögzített megoldásához hozzáadjuk a hozzátartozó homogén lineáris egyenletrendszer összes megoldásait. (Ez szebben hangzik, ha a magyar matematikai szaknyelv hagyomá­ nyait ápolva „rögzített megoldás” helyett „partikuláris megoldás” -t, „összes meg­ oldások” helyett „általános megoldás” -t mondunk.) A megoldások halmaza tehát 7 4- W alakú, ahol 7 vektor, W pedig altér. Bármely vektortérben az ilyen alakú részhalmazokat affin altereknek nevezzük. (A közönséges euklideszi térben a síkok affin alterek: adott sík pontjai, mint vektorok, úgy kaphatók meg, hogy közülük egyhez hozzáadjuk, egy az origón átmenő sík összes pontjait — azaz egy két di­

58

Lineáris egyenletrendszerek

menziós alteret. Persze egy pont, egy egyenes, vagy az egész tér is affin altér.) A lineáris egyenletrendszerek geometriai jelentése tehát: ezek az affin alterek egyen­ letrendszerei (ill. egyenletei, ha egyetlen mátrixegyenletnek tekintjük őket).

6. Lineáris algebra

6 .1. V ektor, vektortér. Vannak olyan egyszerű matematikai és fizikai objektu­ mok ill. mennyiségek, amelyek nem írhatók le egyetlen számmal. Az anyagi pontra ható erőt vagy a mozgó pont sebességét egy-egy szakasszal adhatjuk meg, mivel azonban a sebességnek nemcsak nagysága van, amelyet a szakasz hossza (tehát egyetlen valós szám) ír le, hanem iránya is, ahhoz, hogy egyidejűleg a — mondjuk egyenes vonalon mozgó — pont mozgásirányát is leírjuk, a sebességet szemléltető szakasz két végét meg kell különböztetnünk: egyik a kezdőpont, innen halad a mozgó pont a szakasz másik vége, a végpont irányában. Ha egy szakasznak ilyen módon megkülönböztetjük a két végét, akkor irányított szakasznak nevezzük. Tegyük fel, hogy a tekintett irányított szakaszok egy síkban helyezkedik el, amelyben ki van jelölve egy derékszögű koordinátarendszer. Megállapodunk ab­ ban, hogy az olyan irányított szakaszokat, amelyek egymásba a tartalmazó sík párhuzamos eltolásával átvihetők, egy és ugyanazon vektornak tekintjük. A vektor fogalmat tehát úgy kapjuk, hogy a sík összes irányított szakaszainak a halmazán vesszük az „egymásba párhuzamos eltolással átvihető” relációt, amely ekvivalencia­ reláció; ennek az osztályai a vektorok. Bármely irányított szakasz a sík párhuzamos eltolásával olyan irányított szakaszba vihető át, amelynek kezdőpontja a koordiná­ tarendszer origója. Ezért minden vektor kezdőpontjának tekinthetjük az origót is. A vektorokkal való ismerkedéskor szokás a tetszőleges irányított szakaszt kötött vektornak, ezek ekvivalenciaosztályait szabad vektoroknak, az ekvivalenciaosztály origó kezdőpontú reprezentánsát pedig (az origóra vonatkozó) helyvektornak vagy helyzetvektornak nevezni. A helyzetvektor origótól különböző végpontjának koor­ dinátái a vektort egyértelműen meghatározzák, a vektor megadása tehát egy valós számpár megadását jelenti. Hasonló meggondolással kapjuk a térbeli irányított szakaszból a térbeli vektor fogalmát; ez valós számhármassal adható meg. Ter­ mészetes általánosítás ezután bármely n természetes számra a valós szám-n-eseket vektoroknak, mégpedig n méretű (vagy, gyakrabban használt szóval, n-dimenziós) vektoroknak nevezni. (A szám-n-esek úgy is felfoghatók, mint az { 1, . . . , n} halmaz leképezései, esetünkben a valós számok halmazába.)

60

Lineáris algebra

Erőket (és sebességeket) össze lehet adni és tetszőleges c valós számmal meg lehet szorozni. Eközben az őket szemléltető vektorokon az összeadás eredményét ugyancsak szemléletesen megadhatjuk: Két helyzet vektor, a és b, tekinthető egy parallelogramma két szomszédos oldalának (a parallelogramma lehet „elfajuló” is: szomszédos oldalai eshetnek ugyanarra az egyenesre), s ekkor a + b a parallelo­ grammának az az átlója lesz, amelynek kezdőpontja az origóban van. Az a vektor c-szerese mindig a-val azonos állású, c > 0 esetén azonos irányú, c < 0 esetén el­ lentétes irányú, hosszúsága pedig a hosszúságának |c|-szerese (speciálisan, a ( -c )a vektor — mint helyzetvektor — az origón átmenő ugyanazon egyenesen van, mint ca, de annak az origón túli félegyenesén). Ha a vektorokat (pl.) számhármasok­ nak tekintjük, akkor összeadásukhoz a megfelelő komponenseiket össze kell adnunk (elsőt az elsővel, stb.), számmal való szorzásukhoz pedig minden komponensüket külön-külön meg kell szorozni azzal a számmal. Bármely n-re, ugyanilyen szabállyal adhatjuk össze és szorozhatjuk számmal az n dimenziós vektorokat. Röviden: az n dimenziós vektorok összeadását és számmal való szorzását komponensenként vég­ ezzük. A vektorok összeadásának a következő tulajdonságai vannak: asszociatív, kommutatív, létezik additív egységelem (ti. a (0, . . . , 0 ) vektor), és minden vek­ tornak van additív inverze ((a i , . . . , an ) additív inverze a (—o i , . . . , —a„) vektor). Összefoglalva: bármely n-re az n-dimenziós vektorok Abel-csoportot alkotnak. Ha vektorokról gondolkodva számokat is használunk, azokat megkülönböztetésül skalároknak mondjuk. Az összes vektorok megszorzása ugyanazzal a c skalárral: ez az összes vektorok halmazának önmagába való leképezése. Az összeadás és a ska­ lárral való szorzás szabályából kitűnik, hogy az összeadást és a skalárokkal való szorzásokat a következő szabályok kapcsolják össze: minden a, b vektorra és c, d skalárra (1) (c -I- d) a = ca + da, (2) c(a + b) = ca -f eb, (3) (cd)a = c(da),

(4) l a = a. Az eddigi megfigyelések szolgáltatják a vektortér (nevű algebrai struktúra) általános fogalmát. Legyen adva egy T test. A V halmazt T fölötti vektortérnek nevezzük ha értelmezve van rajta egy összeadásnak nevezett művelet, amelyre nézve V Abel-csoport, és a T test minden t eleméhez hozzá van rendelve egy v ív (v e V ) leképezés úgy, hogy minden a, b € V-re és minden c, d G T-re teljesül (1), (2), (3) és (4). Vektortér elemeit az általános esetben is nevezhetjük vektoroknak, a T test elemeit pedig skalároknak. Ezek a vektorok sok esetben igen távol vannak a vek­

6.1. Vektor, vektortér

61

torfogalom bevezetéséhez használt irányított szakaszoktól, de még a szám-n-esektől is. Ha T a valós számok vagy a komplex számok teste, akkor V -t megfelelően valós vektortérnek, vagy komplex vektortérnek nevezzük. További példák vektortérre: — az egyváltozós valós együtthatós polinomok (hasonlóan a komplex együttha­ tósok és a tetszőleges T test feletti polinomok is — mindegyik a megfelelő test feletti vektortér); — valós vektorteret alkotnak az összes egyváltozós valós függvények (valamint a folytonos és a differenciálható valós függvények is); — valós vektorteret alkotnak az összes komplex számok (általánosabban, ha a Ti test tartalmazza a T testet, akkor a Ti test egyszersmind vektortér is T felett). Mindezekben az esetekben az összeadást és a skalárokkal való szorzásokat a termé­ szetes módon végezzük, pl. a komplex számtest elemeit a komplex számokkal való számolás szabályai szerint szorozzuk a (skalárnak tekintett) valós számokkal. Az előző példákban a vektortér elemeit nemcsak a skalárokkal, hanem egy­ mással is korlátlanul szorozhatjuk. Ez nem szükségszerű: a legfeljebb n-edfokú polinomok (valamely T testből vett együtthatókkal) vektorteret alkotnak T fe­ lett, ám ezeket a polinomok szorzási szabálya szerint szorozva n-nél magasabb fokú polinomokat is kaphatunk eredményül. A szám-n-esek vektorterében azon­ ban bármely két vektoron elvégezhető a skalárszorzásnak nevezett eljárás, amely egyrészt nem tévesztendő össze a skalárokkal való szorzásokkal, másrészt nem „igazi” szorzás, mert bármely két vektorhoz nem vektort, hanem skalárt rendel, az ( ai , a2, ... , a n) • (fei, 62, • • •, bn) = ai&i + 0262 -\---- + anbn szabály szerint. Síkbeli vektorok, vagyis számpárok skalárszorzata egyenlő bosszúságaik és az általuk be­ zárt szög koszinuszának szorzatával. Ez egyből következik pl. a Pitagorasz-tételből és a szögek különbségének koszinuszára vonatkozó összefüggésből, a skalárszorzat ilyen jellemzése azonban térbeli vektorokra is érvényes. A vektortér definíciója mutatja, hogy a skalárokkal való szorzások bizonyos tulajdonságai hasonlók a számok körében megszokott szorzáséihoz. Pl. az (1), (2) és (3) tulajdonságok formailag megegyeznek a disztributivitással és az asszociativitással, csak éppen itt nem egyetlen szorzás műveletről, hanem (skalárral való szorzásnak nevezett) leképezésekről van szó. Továbbá bármely c skalárra és a vek­ torra ca = 0 (a vektortér additív egységeleme, a nullavektor) akkor és csak akkor, ha c = 0 (a T test egységeleme) vagy a = 0. Érvényes - a = (—1) no, mindannyi­ szor \a — an\< e. (Más beszédmód ugyanerre: \a - an\< £ minden elég nagy n-re teljesül, vagy, majdnem minden n-re teljesül.) Az ilyen no számot £-hoz tartozó küszöbszámnak nevezzük. Nem minden sorozatnak van határértéke; ha van, azt mondjuk, hogy a sorozat konvergens, s ha ez a határérték a, akkor azt mondjuk, hogy a sorozat a-hoz tart, más szóval: a-hoz konvergál. A nem konvergens sorozatot divergensnek nevezzük. Példák: A mértani sorozat konvergens, ha hányadosának abszolút értéke kisebb egynél és ekkor O-hoz tart; ha a hányados 1, akkor a mértani sorozat az első (azaz bármelyik) eleméhez tart; különben divergens. A számtani sorozat csak akkor konvergens, ha különbsége 0. A konvergens {an} sorozat ha­ tárértéke egyértelműen meghatározott. Jele: lim an. (A „limes” latin szó határt n —>oo

jelent.) Ha egy sorozat konvergens, akkor korlátos, azaz léteznek olyan k és K valós számok, hogy a sorozat egyetlen tagja sem kisebb k- nál és egyetlen tagja sem na­ gyobb AT-nál; ilyenkor k és K a sorozat alsó, ill. felső korlátja. Ha egy sorozatból bármilyen módon tagokat hagyunk el, de úgy, hogy végtelen sorozat maradjon (a megmaradó tagok sorrendjét megtartjuk!), akkor az így kapott sorozatot az ere­ deti sorozat részsorozatának nevezzük. Konvergens sorozat minden részsorozata is konvergens, limesze pedig ugyanaz, mint az eredeti sorozaté. Divergens sorozatnak lehet konvergens részsorozata; mindig ez a helyzet, ha a divergens sorozat korlátos. Minden korlátos sorozatnak van ugyanis konvergens részsorozata; ez a nevezetes Bolzano— Weierstrass-tétel.

Sorozat torlódási helye az olyan c szám, amelynek bármely (c — £, c + £) (e valós pozitív) környezetében a sorozatnak végtelen sok eleme van. Sorozat tor­ lódási helyei éppen a sorozat (konvergens) részsorozatainak a limeszei. Ezért a Bolzano— Weierstrass-tétel azt jelenti, hogy minden korlátos sorozatnak van tor­ lódási helye. (Ennél több is igaz: minden korlátos sorozatnak van legnagyobb és legkisebb torlódási helye.) Magát a tételt „oroszlánfogással” lehet igazolni: Ha k és K a sorozat alsó és felső korlátja, felezzük a [k, K ] zárt intervallumot, a felező­ pontot mindkét feléhez hozzászámítva. Valamelyik félintervallumban a sorozatnak végtelen sok tagja van; azt megint felezzük meg, és így tovább a végtelenségig. Egyetlen olyan c szám van, amelyet a felezés során kapott (sorozatunk végtelen sok elemét tartalmazó) zárt intervallumok mindegyike tartalmaz; ezt a valós számok Dedekind-féle tulajdonsága biztosítja. Válasszuk ki mindegyik intervallumból a so­ rozat egy tagját, kisebb intervallumból nagyobb indexűt. Az így kapott részsorozat c-hez konvergál. Egy {an} sorozat monoton növekvő, ill. monoton csökkenő, ha ni < n2 esetén

119

11.2. Sorok

ani < a„2, Ül. ani > an2. Minden monoton korlátos sorozat konvergens: ha pl. monoton csökkenő, legnagyobb alsó korlátja létezik (ugyancsak a Dedekind-féle tulajdonság miatt), s az lesz a határértéke. Az

{d + ir }

(i)

sorozatról — általános tagját a binomiális tétellel felírva — belátható, hogy mo­ noton növekvő és felülről korlátos. Ezért van határértéke. Ez a határérték a ma­ tematika egyik leggyakrabban előforduló konstans mennyisége; jele e, tizes szám­ rendszerbeli felírása a 2, 718... számjegyekkel kezdődik. Az e szám irracionális, sőt transzcendens is (azaz nem gyöke egyetlen racionális együtthatós legalább első­ fokú algebrai egyenletnek sem). Ugyancsak e-hez tart minden olyan sorozat, amely úgy keletkezik, hogy (l)-ben n-et valamely plusz végtelenbe tartó sorozat n-edik tagjával helyettesítjük. Sorozat konvergenciájához — a korlátossággal ellentétben — a monotonitás (azaz „ monotonság” ) nem szükséges (példa: lim = 0). A konvergens sorozatok jellemezhetők a Cauchy-féle konvergenciakritérium által: Egy sorozat akkor és csak akkor konvergens, ha bármely pozitív e-hoz létezik olyan no, hogy a sorozat bármely két, no-nál nagyobb indexű tagjának távolsága (= különbségük abszolút értéke) kisebb, mint e. A Cauchy-féle konvergenciakri­ tériumnak eleget tevő, racionális számokból álló sorozatok határértéke nem szük­ ségképpen racionális szám; ilyen sorozatok határértékei kimerítik az összes valós számokat. (Igaz-e, hogy egész számokból álló sorozat határértéke csak egész szám lehet? Mi a helyzet a valós számokkal, ill. a pozitív valós számokkal?) Sorozat konvergenciájának belátására gyakran alkalmazhatjuk a rendőrelvet. ha {an} és {6n} ugyanahhoz a c számhoz konvergál, és {cn} olyan sorozat, hogy minden n-re (vagy akár csak minden elég nagy n-re) an < Cn < bn, akkor {cn} is chez konvergál (éppúgy, ahogyan a kapitányságra tartó két rendőr által közrefogott törvényszegő is kénytelen ugyanoda tartani). Sorozatokon a vektorok komponensenkénti összeadásához hasonlóan végezhe­ tünk műveleteket (ha a sorozatokat számelméleti függvényeknek tekintjük, akkor ez nem más, mint függvények pontonkénti összeadása). Konkrétabban: bármely {an}, {6„} sorozatokra {an} db {6n} = {an ± bn}, {an} • {6n} = { an • &„}, és (ha a {&n} sorozat tagjai között nincs zérus), = { f 11-}. Konvergens sorozatok összege, különbsége, szorzata ugyancsak konvergens, és limesze megfelelően a tekintett so­ rozatok limeszeinek összege, különbsége és szorzata. Ugyanez igaz hányadosra is, a mondott megszorításon túl még azt az esetet is kivéve, amikor lim bn = 0; ekkor 71—>00

vagy lim an ^ 0, amikor is a hányadossorozat divergens, vagy pedig a számlálók n —>oo

sorozata is 0-hoz tart, s akkor a hányadossorozat konvergenciájáról — az {an} és {&„} sorozatokra vonatkozó további ismeretek nélkül — semmit sem állíthatunk.

120

Sorozatok, sorok

Bármely sorozatból képezhetjük első n tagja összegét, minden n € N-re. így az {an} sorozatból egy másik, {sn} sorozatot kapunk, ahol sn az öi H ---- 1 -an összeget jelöli. Ha {sn} konvergens és határértéke s, akkor azt mondjuk, hogy az cii+a.2-\----- ban-\---- végtelen sor konvergens, és összege 5; ellenkező esetben a végtelen sort divergensnek mondjuk. A tekintett végtelen sort röviden an jelöli. Az s í , . . . , sn, . .. összegeket e sor részletösszegeinek nevezzük. Ha egy sor részletösszegeinek sorozata minden határon túl nő (más szóval plusz végtelenbe tart, ami azt jelenti, hogy bármely pozitív M számhoz létezik olyan no € N kü­ szöbszám, hogy az no-nál nagyobb indexű részletösszegek mind nagyobbak M-nél), akkor azt mondjuk, hogy a tekintett (divergens) sor összege plusz végtelen. Ehhez hasonlóan értelmezzük a mínusz végtelen összegű sort. Példa: tekintsük a 0, Í42857 végtelen (szakaszos) tizedestörtet. Ez nem más, mint a 0) 3^, 10q00, .. . sorozatból képezett végtelen sor, amelynek részletösszegei 0; 0, 1; 0, 14; 0, 142; 0, 1428; ... , összege pedig az a szám, ame­ lyet ez a végtelen tizedestört fejez ki (azaz y). Ugyanígy, bármely végtelen tize­ destört tekinthető végtelen sornak; részletösszegeinek a sorozata mindig monoton növő és korlátos, ezért van összege, és a végtelen tizedestört ezt az összeget jelenti. A nemzérus kezdőtagú a\, a\q, a\q2, . . . végtelen mértani sorozatból képezett végtelen mértani sor divergens, ha |r/| > 1; máskülönben konvergens, és összege, S = a i/ ( l - q) (ugyanis n-edik részletösszege 9) = 1>0 > O, \ 0, ha x irracionális függvénynek (a „kis” Riemann-függvénynek) mindenütt van határértéke, de ez a racionális helyeken különbözik az értékétől. (Ez a határérték mindenütt 0, mert bármely számot tőle különböző racionális számokkal egyre jobban megközelíteni csak egyre nagyobb nevezőjű törtekkel lehet, hiszen adott számnál kisebb pozitív nevezőjű tört csak véges sok van.) Triviális példa: az f x, harr ^ 0, x i—> < \ 1, ha x = 0 függvénynek minden x helyen x a határértéke, amely a 0 helyen különbözik a függvény értékétől.

Függvények

132

A függvény határértékének Heine-féle definíciójával ekvivalens a Cauchy-féle definíció: Azt mondjuk, hogy az / függvény határértéke az a helyen a c szám, ha bármely pozitív e valós számhoz van olyan pozitív 5 valós szám, hogy valahányszor valamely, az / értelmezési tartományához tartozó és a-tól különböző a' valós számra teljesül |a - a'| < S, mindannyiszor teljesül |f(a) —c\ < e is. Beszélhetünk függvény végtelen határértékéről is, valamint függvény határér­ tékéről a végtelenben. A „végtelen” nem szám és nem is számosság, ezek a fogalmak tehát nem speciális esetei a már bevezetett határérték-fogalomnak, s ezért külön definiálandók. Azt mondjuk, hogy az / függvény határértéke az a helyen plusz végtelen (írásban: lim f(x) = +oo), ha minden olyan a i , a 2, . . . számsorozatra, x —►a

amely a-hoz konvergál, de egyetlen eleme sem a, az /(a i), / ( ö2), .. . számsoro­ zat minden határon túl nő; hasonló a mínusz végtelen (—00) határérték jelentése. Másrészt azt mondjuk, hogy az / függvény határértéke a plusz végtelenben c (írás­ ban: lim f ( x ) = c; itt + 00 helyett egyszerűen 00 is írható), ha minden olyan x —*+oo

ai, ű2, . . . számsorozatra, amely minden határon túl nő, az /(a 1 ), /( / ( ö i ) < / ( a 2);

(1)

szigorúan monoton növekvő, ha grafikonja balról jobbra haladva emelkedik, vagyis

12.5. Folytonosság

133

(1) „ < ” helyett „ < ” -bel is teljesül. Hasonló a monoton csökkenő és a szigorúan mo­ noton csökkenő függvények definíciója. Ha /-ről csak azt állítjuk, hogy (1) bizonyos számhalmazba (pl. intervallumba) eső ai, a.2 helyekre teljesül, akkor azt mondjuk, hogy f monoton (növekvő) azon az számhalmazon. Periodikus az / függvény, ha van olyan pozitív c szám, hogy minden a valós számra f{a -f c) = /(a); ilyenek a trigonometrikus függvények, az {x} (x törtrésze) függvény, stb. Függvény kap­ csolata inverzével ugyancsak szembetűnik grafikonjaikon: ezek egymás tükörképei az y = x egyenesre (az identikus függvény grafikonjára) vonatkozóan. Ebből az is látszik, hogy ha egy / monoton növekvő vagy csökkenő függvénynek van inverz függvénye, akkor az is (megfelelően) monoton növekvő vagy csökkenő (/ értékkész­ letén). Összetett függvény grafikonja általában nem keletkezik ilyen szépen a belső és külső függvény grafikonjából, de pl. az ax + b és az a(x -F 6) összetett (lineáris) függvények grafikonját az iskolai matematikában is „származtatjuk” az ax és az x + a függvények grafikonjából. Az / függvény folytonos az a helyen, ha minden olyan < 2i , a 2, . . . végtelen számsorozatra, amely a-hoz konvergál, az / ( ö i ) ,/ ( ö2), ... so­ rozat /(a)-hoz konvergál. Ez a folytonosság Heine-féle definíciója. Ha a pontja és torlódási pontja / értékkészletének, akkor / folytonossága az a helyen azt je­ lenti, hogy /-nek az a helyen van határértéke és az megegyezik / ottani értékével. Ahogyan függvény határértékét két különböző de ekvivalens módon vezettük be, a folytonosság definícióját is megadhatjuk másképpen: 1 2 .5 .

F olyton osság.

Az / függvény folytonos az a helyen, ha bármely pozitív £-hoz van olyan pozitív o

x —>a

(2 ) az /, g függvények az a hely valamely környezetében (esetleg az a hely kivé­ telével) differenciálhatok, (3) létezik lim f '( x ) és lim a

x—

akkor f/g -nek létezik határértéke az a helyen és az egyenlő f'/g' határértéké­ vel ugyanott. (Szemléletesen ez eléggé természetes, lásd az 20.b ábrát.) Pl.: lin^ si^x _ üj-n co^x _ Ugyanilyen feltételek mellett az a helyen (mondjuk, plusz) végtelen határértékű függvények hányadosának is létezik határértéke ott,

Differenciálás

142

mégpedig derivált függvényeik határértékének hányadosa ott. Végül a (plusz vagy mínusz) végtelenben 0 vagy végtelen határértékű függvények hányadosának határ­ értékére hasonló összefüggés érvényes a feltételek teljesülése esetén. 13 .2 . F üggvén ydiszk usszió. Azt mondjuk, hogy az egyváltozós valós / függ­ vénynek helyi (másképpen lokális) maximuma van a co helyen, ha van co-nak olyan K környezete, hogy minden c 6 K -ra f(c) < /(co); ilyenkor /(c0) a lokális ma­ ximum. Hasonlóan definiáljuk a helyi minimumot; ezek és a helyi maximumok a helyi szélsőértékek. Az / függvény maximuma (minden jelző nélkül, de ha mégis hangsúlyozni akarjuk, hogy nem lokális maximumról van szó, akkor a „globális” jelzőt használjuk) valamely / intervallumon az M szám, ha van olyan cq G I, hogy /(co) = M , és minden c G I -re /(c) < M; hasonló értelmet tulajdonítunk a minimumnak ill. a szélsőértéknek intervallumon. Függvény szélsőértékei egy in­ tervallumon nem szükségképpen léteznek, pl. sem ^-nek, sem x 2-nek nincs sem maximuma, sem minimuma a (0,1) nyílt intervallumon (sem lokális, sem globáli;); tudjuk azonban, hogy zárt intervallumon folytonos függvénynek (globális) maxi­ muma is, minimuma is van a tekintett zárt intervallumon. Függvény vizsgálatát szokás a függvény diszkussziójának nevezni; ha ezt a szót használjuk, akkor ezen rendszerint a függvény értelmezési tartomány, értékkészlet, szélsőértékek, folyto­ nosság, monotonság, és ezekhez hasonló szempontok szerinti vizsgálatát értjük; lényegében a függvény olyan tulajdonságainak a vizsgálatát, amelyek ismeretében a függvény grafikonját el tudjuk képzelni és, legalább durván, fel is tudjuk vázolni. A diszkusszióhoz jól használható a függvény deriváltja. Ha az / függvénynek létezik deriváltja valamely (a, b) intervallumon, akkor a következő két állítás ekvivalens: — / monoton növekvő az (a, b) intervallumon.

— f ' ( c) > 0, ha c G (a, 6). Természetesen, ha állításainkban „monoton csökkenő” , ill. „ < ” szerepel, ak­ kor is ekvivalensek. (A szigorú monoton növekedésnek és a derivált pozitív elő­ jelének nincs ilyen egyszerű kapcsolata: pl. az x 3 függvény mindenütt szigorúan monoton növekvő, de a 0 helyen deriváltjának értéke 0.) Abból a feltevésből, hogy / differenciálhányadosa valamely cq helyen pozitív (negatív), nem következik, hogy co-nak van olyan környezete, amelyen / monoton növekvő (csökkenő). Ellenpélda: f(x) = |( x - f x 2(l-t-cos ^ )) . Ez a riasztónak tűnő függvény nincs ugyan értelmezve a jobb oldali formula által a 0 helyen, de ott 0 a határértéke, s ezzel kiegészítve mindenütt differenciálható. Mint a 21.a ábrán látjuk, grafikonja beszorul az § egye­ nes és az x 2 + | parabola grafikonja közé, így a rendőrelv szerint /'(0) = \ > 0. Legyen un = - 7==, vn = /--■ ------ Akkor létezik 0-hoz bármilyen közeli un és v 2n7r

y (2 n —1)7r

vn, továbbá un < vn, de behelyettesítés mutatja, hogy f{u n) > f {y n), tehát /

13.2. Függvény diszkusszió

143

grafikonja végtelen sok hullámot vet, miközben az origóhoz közeledik. (Ha csak olyan u, v számokat tekintünk, amelyekre u < 0 < v, akkor mindig f (u ) < f(v), és ez valóban következik /'(0) > 0-ból.) Függvényünk arra is példa, hogy zárt intervallumon mindenütt differenciálható függvény deriváltja nem szükségképpen folytonos az intervallum minden pontjában. Ám a derivált függvénynek mégis van egy olyan jótulajdonsága, amely közös a zárt intervallumon folytonos függvények­ kel: ha f'(a) < d < /'(&), akkor van olyan c az (a, b) intervallumban, hogy f'(c ) = d

(Darboux tétele).

Az előző bekezdés első állításából következik, hogy ha az (a, b)-n mindenütt differenciálható / függvénynek az intervallum valamely c helyén szélsőértéke van, akkor ott / deriváltjának értéke 0. Ennek a megfordítása nem igaz; ugyancsak az x 3 függvény cáfolja. Ha azonban / derivált függvényének létezik a derivált függvénye (/ második deriváltja, amelynek jele f " ) és az is folytonos a c helyen (a szokásos szóhasználattal: / kétszer folytonosan differenciálható), akkor f'(c) = 0 esetén /"(c) előjele megmondja, maximuma vagy minimuma van-e /-nek a c helyen: ha f"{c) < 0 (ami biztosan ig£iz, ha / ' a c hely valamely környezetében csökkenő — más szóval, / ' a c helyen csökkenően halad át), a szélsőérték maximum, ha pedig f"(c) > 0, akkor minimum. Ha viszont f"(c) is eltűnik, akkor meg kell vizsgálni a harmadik deriváltat is a c helyen, hogy eldöntsük, van-e ott szélsőérték. Az / függvény n-edik (másképpen: n-edrendű) deriváltjának szokásos jele / (n). Ha f'(c) = f"(c) = ... = /(fc-1)(c) = 0, és f ^ ( c ) ^ 0, akkor /-nek aszerint van vagy nincs szélsőértéke a c helyen, hogy k páros-e vagy páratlan. Ha szélsőértéke van ott, akkor /^ előjele ugyanúgy mondja meg, hogy az maximum, vagy minimum-e, mint a k = 2 esetben. (Mindezek a megállapítások lokális maximumokra vonatkoznak.)

Differenciálás

144

Függvény második deriváltjának előjeléből következtethetünk a függvény kon­ vex vagy konkáv voltára. Szigorúan konvex az / függvény az [a, 6] intervallumon, ha bármely a < r < s < t < b helyekre f ( s ) < / (r)+ (s —r ). Ez azt jelenti, hogy az / függvény grafikonja az [a, 6] intervallum minden [r, t] részintervallumán az (r,/(r)) és (t, f ( t )) pontokat összekötő húr (= szelőszakasz) alatt halad. Ha a definícióban < helyett csak < a követelmény, akkor egyszerűen konvex függvény­ ről beszélünk. „Konvex” szemléletesen (és magyarul) azt jelenti, hogy „domború” , pontosabban alulról domború (ti. konvex függvény grafikonja lefelé domborodik). Hasonlóan definiáljuk a szigorúan konkáv és konkáv (azaz alulról homorú grafikonú) függvényt. (Vigyázat! Ponthalmazt akkor nevezünk konvexnek, ha bármely két pontjával együtt az azokat összekötő egyenes szakasz minden pontját is tar­ talmazza. Pozitív értékű függvény pontosan akkor konkáv egy intervallumon, ha a felülről a grafikonja által határolt görbevonalú trapéz konvex; lásd a 21.b áb­ rát). A konvexség definíciójából — amelyben differenciahányadosok szerepelnek — látható, hogy ha az (a, 6) intervallumon f"(x) > 0 (azaz a függvény deriváltja monoton növekvő ott), akkor a függvény konvex ott, és ennek a megfordítása is igaz. Az x 3 függvény első és második deriváltja is eltűnik a 0 helyen. A negatív féle­ gyenesen x 3 szigorúan konkáv, a pozitívon szigorúan konvex. Általában, ha c olyan hely, hogy egy /, valamely c-t tartalmazó intervallumon differenciálható függvény ott konvexből konkáwá, vagy konkávból konvexszé változik, akkor azt mondjuk, hogy f-nek a c helyen inflexiós pontja van — a (c, f (c )) pont / grafikonjának infle­ xiós pontja. Inflexiós pontban a függvény második deriváltja mindig eltűnik. Ez a tulajdonság egymagában nem jellemzi az inflexiós pontokat, ha azonban van olyan n természetes szám, hogy az / függvény legalább 2n + 1-szer differenciálható, és f'(c) = f " ( c ) = ... = / (2n^(c) = 0, de /(2n+1)(c) ^ 0, akkor /-nek c-ben inflexiós pontja van. (Gondoljunk az x 2n+1 függvényre!) Függvény magasabb rendű deriváltjai nemcsak a függvénydiszkusszió szem­ pontjából fontosak, hanem a függvény hatványsorának együtthatóiban is szere­ pelnek (lásd a 11. tételt). Kiszámításuknak nincs különös nehézsége. Mégis, a hosszadalmas számolást egyszerűsítik az összeg és szorzat n-edik deriváltjára vo­ natkozó szabályok. Nyilvánvaló, hogy összeg (és különbség) n-edik deriváltját is tagonként képezzük. Szorzat deriváltját pedig az

(/s )(n) = £ i= 0

( " V ' V ”-0 '

'

szabállyal számíthatjuk ki (ahol az / függvényt jelöli). Ennek érvényessé­ gét ugyanúgy láthatjuk be teljes indukcióval, mint a kéttagú összeg pozitív egész

13.3. Parciális és totális differenciálás

145

kitevős hatványaira vonatkozó binomiális tételt. (Az utóbbit Newton-féle bino­ miális tételnek, a magasabb rendű deriváltakra vonatkozó szabályt pedig Leibnizszabálynak is nevezzük.) 1 3 . 3 . P arciá lis é s t o t á l i s d iffe r e n c iá lá s . Két- és többváltozós függvények érté­ kei változásának sebességét is leírhatjuk bizonyos belőlük képezett függvényekkel, amelyeket ugyancsak derivált vagy differenciálhányados-függvényeknek nevezünk. Az ezekre vonatkozó legfontosabb összefüggések már kétváltozós függvények ese­ tére is megfogalmazhatók, s ezek esetében még van szemléletes tartalmuk is; ezért csak a kétváltozós (valós) függvények differenciálszámításáról lesz szó. Kétválto­ zós függvény értelmezési tartománya a (derékszögű koordinátarendszerrel ellátott) S (= xy) sík valamely ponthalmaza, amelynek minden pontját egy (a, 6) valós számpár adja meg. Ha a koordinátarendszert az origón átmenő, R függvény előállítható lép­ csős függvények egyenletesen konvergens sorozatának határfüggvényeként. Az / OO

Vn •m(yn) sor abszolút kon-

lépcsős függvényt integrálhatónak nevezzük, ha a 71=1

vergens; ilyenkor ezt az összeget nevezzük / integráljának az M halmazon (jele JM f). A g : M —>R függvény Lebesgue-integrálható, ha létezik M-en értelmezett integrálható lépcsős függvényeknek olyan {/n} egyenletesen konvergens sorozata, amelynek a határ függvénye g. Ekkor a lim f .r f n határérték létezik és független az { f n} függvénysorozat választásától. Ezt a határértéket nevezzük g Lebesgueintegráljának az m halmazon. Lépcsős függvény Lebesgue-integrálja egyenlő a rá vonatkozóan előzetesen definiált integráljával. A Lebesgue-integrál néhány fontos tulajdonsága: — Adott [a, 6] intervallumon Riemann-integrálható függvény Lebesgueintegrálható ott, és Lebesgue-integrálja egyenlő Riemann-integráljával. — Ha az /, g : M —> R függvények értékei csak 0 mértékű halmazon különböz­ nek (más szóval, majdnem mindenütt egyenlők), akkor f és g vagy mindketten Lebesgue-integrálhatók vagy egyikük sem, és ha Lebesgue-integrálhatók, ak­ kor Lebesgue-integráljuk egyenlő. (A Dirichlet-függvény [0, l]-en majdnem mindenütt egyenlő a konstans 1 függvénnyel, ezért Lebesgue-integrálható, és Lebesgue-integrálja 1.) — Ha {/„} az M halmazon értelmezett valós függvényeknek olyan sorozata, amely majdnem mindenütt konvergál valamely / függvényhez, és létezik

156

Integrálás

olyan Lebesgue-integrálható g függvény, amely a sorozatba tartozó függvé­ nyek mindegyikét abszolút értékben pontonként majorálja (azaz minden n-re és minden x € M - re |/n(x)| < p(x)), akkor / Lebesgue-integrálható M-en és Lebesgue-integrálja egyenlő az { f M f nj sorozat határértékével. (Ez Lebesgue tétele függvénysorozat tagonkénti integrálhatóságáról; a benne szereplő f n függvények Lebesgue-integráljának létezése a majoráns függvényre vonat­ kozó feltevésből következik. A Riemann-féle integrálás és a határátmenet — azaz határfüggvény-képzés — nem cserélhető fel ilyen csekély követelmények mellett, bár egyenletes konvergencia esetén felcserélhető a két művelet.) — Ha az / függvény Lebesgue-integrálható az M halmazon, akkor Lebesgueintegrálható M minden mérhető részhalmazán is. — A Lebesgue-integrál cr-additív, abban az értelemben, hogy ha / Lebesgueintegrálható M-en, és A, A \, . . . , An, .. . C M , ahol A a páronként idegen A \ , . . . , A n, . . . mérhető halmazok egyesítése, akkor f A f = ^2/a /■ n

(Hogyan változik egy szakaszon integrálható függvény integrálja ott, ha (1) egy helyen, (2) véges számú helyen, (3) megszámlálhatóan végtelen sok helyen meg­ változtatjuk a függvény értékét. Mit mondhatunk két különböző folytonos függ­ vény integráljáról ugyanazon határok között, ha tudjuk, hogy pontonkénti különb­ ségük sehol sem negatív? Ugyanazok-e a válaszok Riemann-féle és Lebesgue-féle integrál esetén?) 1 4 . 4 . T ö b b v á l t o z ó s f ü g g v é n y i n t e g r á lja . Az egyváltozós függvények integrá­ lása területszámításon túl pl. görbe vonal ívhosszának, forgástest (vagyis valamely görbe alkalmas tengely körüli megforgatásával kapott felület által határolt test) térfogatának és felszínének kiszámítására is használható (lásd a 10. és 15. tételt), továbbá a valószínűségszámításban is fontos szerepe van (16. tétel). Ugyancsak lépten-nyomon alkalmazzák a fizikában. (A legegyszerűbb példa: egyenes vonalon mozgó pont által adott időintervallumban megtett út a pont sebességének — ami az idő függvénye — integrálja.) Ezeken túl vannak olyan feladatok, amelyekben többváltozós függvények szerepelnek, s hasonlóan a Riemann-féle integrálszámí­ táshoz, ezen függvények értékeinek felhasználásával képezett alsó és felső összegek közé eső számot keresünk. Legyen pl. f(x,y) valamely, az I = [a, 6] x [c, d] téglala­ pon értelmezett valós függvény; keressük annak a H testnek a térfogatát, amelyet a mondott téglalap, az annak oldalegyenesein átmenő, xy síkra merőleges négy sík, és a z = f(x, y) egyenletnek eleget tevő (x , y, z ) pontok alkotta felület — amelyet ebben az esetben is nevezhetünk az / függvény grafikonjának — határol. Tekintsük az [a, b] és a [c, d] intervallum egy-egy beosztását; ezek együtt meghatározzák a tég­ lalap egy felbontását résztéglalapokra. Minden ilyen résztéglalapon vegyük f(x, y) ott felvett értékeinek alsó határát, s ezt szorozzuk meg a résztéglalap területével,

14-4■ Többváltozós függvény integrálja

157

majd összegezzük az így kapott szorzatokat. Ezt nevezzük az /(x, y) függvényhez és a tekintett beosztásokhoz tartozó alsó (közelítő) összegnek; hasonlóan definiáljuk a felső (közelítő) összeget. Bármely beosztáspár esetén a felső összeg egy H- 1 tar­ talmazó síklapú test térfogata, míg az alsó összeg egy olyan síklapú testé, amelyet H tartalmaz. Ha egyetlen olyan v szám létezik, hogy bármely beosztáspár esetén az ahhoz a beosztáspárhoz tartozó s alsó összegre és S felső összegre s < v < S tel­ jesül, akkor v-t nevezzük H térfogatának és egyben f(x,y) Riemann-integráljának a tekintett téglalapon. Jele: / f(x,y)d(x,y). Ezt az integrált — megkülönböz­ tetésül az egyváltozós függvény integráljától — területi integrálnak nevezhetjük. Az integrálás tartománya téglalap helyett lehet más (síkbeli) P ponthalmaz is, ha az Jordan-mérhető (ekkor az integrált f(x,y)d(x,y) jelöli). Ebben az eset­ ben résztéglalapok helyett olyan Jordan-mérhető részhalmazokat kell használnunk, amelyek egyesítése P, és csak határpontjaik (lehetnek) közösek. A P halmaz ilyen részhalmazokra való felbontásának finomságán a benne részt vevő részhalmazok átmérőinek felső határát értjük (ponthalmaz átmérője a benne lévő pontpárok tá­ volságainak felső határa). Értelemszerűen definiálhatók az oszcillációs összegek, és területi integrálra is bebizonyítható Darboux tétele. A területi integrál is additív és lineáris. A következő állítás a szukcesszív integrálás tétele, amely a területi integrál kiszámításáról szól; bár gyengébb feltételek mellett is igaz, az egyszerűség kedvéért folytonos függvényekre és téglalaptartományra mondjuk ki. Ha /(x, y) folytonos valamely / = [a, 6] x [c, d] téglalapon, akkor

Itt szukcesszíve — magyarul: egymás után — integráljuk f-e t, mint egyváltozós függvényt, először bármelyik változója szerint azon változó határai között, majd a kapott határozott integrált, amely a másik változó függvénye, integráljuk a másik változó határai között. Hasonló meggondolásokkal kettőnél több változós függvények integrálját is értelmezhetjük. A Lebesgue-integrál is bevezethető két- és többváltozós függvé­ nyekre, és rendelkezik az említett alapvető jótulajdonságokkal, köztük a szukcesszív integrálás lehetőségével. Kétváltozós f ( x , y ) függvényt nemcsak síkbeli tartományon, hanem síkbeli L vonal (síkgörbeív) mentén is integrálhatunk. Az eljárás az egyváltozós függvény (x tengelyen elhelyezkedő) szakaszon való integrálásának általánosítása: most a tekintett síkgörbén készítünk beosztásokat, amelyekkel az L görbét ívdarabokra bontjuk, majd — az egyes ívdarabokon véve /(x, y) értékének alsó ill. felső ha­ tárát, ezeket megszorozva a tekintett ívdarab ívhosszával és összegezve — most

158

Integrálás

is elkészíthetjük az alsó és felső (közelítő) összegeket. Az f(x, y) függvény adott vonal menti integrálja az összes alsó és felső összegek közé eső szám — ha ez egyet­ len. Ezt az ívhossz szerinti görbementi integrálnak nevezzük; ezt alkalmazzuk pl. inhomogén sűrűségű anyagból készített (vagy változó vastagságú) drót tömegének a kiszámítására. Ettől eltér a koordináta szerinti görbementi integrál, amelyet úgy kapunk, hogy két kétváltozós függvényt tekintünk, p = p(x, y)-t és q = q{x , y)-1, elkészítjük a beosztásokat, de az alsó és felső (közelítő) összegek megalkotásához az egyes ívda­ rabokon felvett függvényértékek alsó és felső határát nem az ívdarab hosszúságával szorozzuk, hanem p esetén az ívdarab végpontjai abszcisszáinak különbségével, q esetén pedig ordinátáik különbségével (azaz mindkét esetben az ívdarabnak a meg­ felelő koordinátatengelyre való merőleges vetülete hosszával). így két különböző integrált kapunk: az JLpdx és f L qdy integrálokat. Ezek összegét nevezzük p-hez,

—* (x(t ), y(t)) leképezés az [u , v] intervallumot / grafikon­ jának vizsgált ívébe viszi át (ami azt is maga után vonja, hogy x{u) = a, x(v) = b). Ekkor az imént kapott integrált helyettesítéssel számíthatjuk ki: x helyébe az x(t) függvényt helyettesítve az JJ a/ 1 + { f{x {t) )) 2 x'{t)dt alakra hozhatjuk, ami mini­ mális átalakítással a végleges /J y/(x'(t) ) 2 + (y'(t))2dt ívhosszképletet szolgáltatja. Jó tudni, hogy a képlet akkor is használható, ha tetszőleges folytonosan differenci­ álható x(t) és y(t ) valós függvényekből indulunk ki, nem téve fel, hogy az általuk meghatározott görbe valamely valós függvény grafikonja. Hasonló ívhosszképlet vezethető le térbeli görbék ívhosszára is. A képlet drámai egyszerűséggel szolgáltatja a kör kerületét: az első síknegyedet átszelő egységkörnegyed ívhossza a képlet szerint J02 %/cos2 1 + sin2 tdt, ami ránézésre mutatja a helyes | értéket. Túl egyszerűnek tűnik, nincs ebben csalás? Bizony, van, mert az integrálás felső határának kijelöléséhez már tudnunk kellett, hogy az egységkör kerülete 2 tt. Nem csaltunk viszont a kör területének kiszámítá­ sakor — ahhoz is csak a kör kerületét kellett előre ismernünk. Nincs azonban baj: a 7T számot az egységkör félkerületének mértékeként definiálhatjuk, értékét pedig a beleírt törtvonalak összhosszúságának felső határaként, és így számíthatjuk ki, helyesebben mondva így is kiszámíthatjuk. A felszín az ívhossznál nehezebben vizsgálható. Várhatnánk, hogy sima fe­ lület egyszerű határvonallal rendelkező darabjának a felszíne definiálható a beléírt nyílt poliéderek (azaz síklapú testek felületeinek önmagába visszatérő térbeli töröttvonallal határolt darabjai) területösszegének felső határaként. Ez azonban nem igaz: ismeretes (Schwarz), hogy ez a felső határ még olyan egyszerű felületre sem létezik, mint egyenes körhenger palástja. Ez nem jelenti azt, hogy az egye­ nes körhengernek nincs felszíne, csak azt jelenti, hogy a beírt sokszögek módszere, amely görbeívek ívhosszának kiszámításához megfelelő, felületekre nem vihető át. Bizonyos felületek esetében azonban — és ilyen az egyenes körhenger palástja is — a felszín integrálszámítással kiszámítható. Ez igaz bármely forgástest palást­

170

Mérték

jára. E felületek úgy keletkeznek, hogy valamely f ( x ) folytonosan differenciálható f(x) valós függvény grafikonjának az a és 6 abszcisszaértékek közötti ívét az x tengely körül megforgatjuk. Ha a grafikon bármely húrját vele forgatjuk, az egy csonkakúp palástját írja le. Tetszőleges beírt töröttvonalat forgatva görbénkkel együtt, a keletkező csonkakúppalástokból álló felület annál jobban megközelíti a forgástest palástját, minél közelebb vesszük fel egymáshoz a húrok végpontjainak abszcisszaértékeit (azaz minél jobban finomítjuk a beírt húrok alkotta töröttvo­ nalat). Emlékezve / grafikonja ívhosszának képletére, adódik, hogy a forgástest palástjának felszínét a 2 n Ja f(x)y/l + (f'(x))2dx képlet adja meg.

16. Valószínűség

1 6 . 1 . V a l ó s z í n ű s é g i k ísérle t. Egy pénzdarab feldobásának két eredménye lehet: fej vagy írás. Ha az érme hibátlan és feldobáskor jól megpörgetjük, akkor egy valószínűségi kísérletet hajtunk végre, amelynek lehetséges eredményei a „fej” és „írás” véletlen események. Végeztessük el egy emberrel — mondjuk — ezerszer ezt a valószínűségi kísérletet, majd ugyanezt végeztessük el ezer emberrel fejenként egyszer, és legyen a kísérletek kimenetele az első esetben k fej és 1000 — k írás, a második esetben l fej és 1000 - l írás. Ha pl. k = 317 és Z = 511, elkerülhetetlenül az a gyanúnk támad, hogy a magányos pénzdobáló vagy hamis pénzt használ, vagy a pörgetés mikéntje kifogásolható. Tapasztalatunk és józan belátásunk egyaránt azt sugallja, hogy a tekintett kísérlet kimenetele az eseteknek körülbelül felében fej lesz, akár egyetlen ember végzi el sokszor ugyanazt kísérletet, akár sok ember egyesével, a többi — nagyjából ugyanannyi — esetben pedig írás. Itt a józan belátás a következőt jelenti: a pénzérmét elhanyagolható magas­ ságú lapos körhengernek tekintjük, amely feldobáskor 15-20 fordulatot tesz átmé­ rője körül; továbbá elfogadjuk, hogy ha ez a henger feldobáskor k számú félfordu­ latot tesz, akkor a kísérlet kimenetele csak attól függ, hogy feldobáskor hogy állt az érme és k páros-e vagy páratlan. Ámde e két körülmény egyikét sem tudjuk számításba venni a kísérlet kimenetelének megjóslásához. Feltételezzük ugyanis, hogy a dobáskor tisztességesen nem „állítjuk be” az érmet, és nem vagyunk zseniá­ lis zsonglőrök; ekkor pedig a pénzfeldobás ugyanazt jelenti, mint vaktában rábökni egy 30-40 körüli számra, amelynek valóban nincs több oka arra, hogy páros le­ gyen, mint arra, hogy páratlan. Olyan esetben pedig, amikor kimenetelként csak fej és írás lehetséges, és semmilyen figyelembe vehető körülmény nem utal arra, melyik fog bekövetkezni, elvárhatjuk, hogy közel ugyanannyiszor legyen fej a kísér­ let eredménye, mint ahányszor írás. Az esetleges eltérést a figyelembe nem vehető körülmények indokolják: a kéz remegése, az asztallap egyenetlenségei, stb.

Lényegében ugyanilyen egyszerű valószínűségi kísérlet egy szabályos játék­ kocka feldobása. Nyugodtan megkockáztathatjuk: ekkor a hat lehetséges véletlen kimenetel („egyes” , „kettes” , stb.) mindegyike a dobások körülbelül egyhatodában

172

Valószínűség

fog bekövetkezni. A kockadobás hat lehetséges, egymást kölcsönösen kizáró kime­ netele mellett természetes dolog eseménynek tekinteni azt is, ha pl. a kockadobás eredménye kettőnél nagyobb, vagy, ha az eredmény páros szám. Általánosabban, ha egy valószínűségi kísérletnek véges sok kimenetele van és ezek halmaza Cl, akkor eseménynek nevezzük kimenetelek bármely H C Cl halmazába tartozó kimenetel bekövetkezését. A H esemény bekövetkezése eszerint abban áll a kísérlet elvég­ zésekor, hogy H egy eleme jön ki. Az események A összessége tehát a véges Cl összes részhalmazainak a halmaza, amelyben a szokásos halmazelméleti műveletek természetes kapcsolatban vannak az események bekövetkezésével. E műveletekre nézve A halmazalgebrát alkot, ami azt jelenti, hogy Cl € A, s ha A, B € A, ak­ kor AU B, A n B, B - A := B \ A, Ac = Cl - A e A. A mindig bekövetkező Cl eseményt bizonyos vagy biztos eseménynek, a soha be nem következő 0 eseményt pedig lehetetlen eseménynek nevezzük. Ha egy pénzfeldobásos kísérletsorozatban 100 do­ básból pl. 47 fej fordul elő, azt mondjuk, hogy a „fej” esemény relatív gyakorisága abban a kísérletsorozatban Általában, ha Cl egy valószínűségi kísérlet kimene­ teleinek véges halmaza és A az Cl összes részhalmazainak az osztálya, akkor n-szer (függetlenül, aminek a jelentését ezután tisztázzuk) megismételve a kísérletet és 5n(A)-vel jelölve az A e A esemény bekövetkezéseinek a számát, az Sn{A)/n há­ nyadost az A esemény relatív gyakoriságának nevezzük. A relatív gyakoriság tehát a [0,1] intervallumba eső racionális szám, amely ugyanazon valószínűségi kísérlet­ sorozat még egyszeri elvégzésénél rendszerint az előzőtől különböző értéket vesz fel, hiszen maga is véletlen: adott n-szeri ismétléssorozat esetén az események A halmazalgebráján értelmezett véletlen függvény. Általános azonban az a — példá­ inkban is megmutatkozó — jelenség, hogy egy valószínűségi kísérlet többszöri soro­ zatos végrehajtásakor minden egyes lehetséges véletlen esemény relatív gyakorisága valamely szám körül ingadozik, és általában annál kevésbé tér el attól a számtól, minél hosszabb a kísérletsorozat, vagyis minél nagyobb a fentebbi n. A valószínű­ ségszámításnak magára a valószínűségre vonatkozó axiómáit úgy határozzuk meg, hogy ezt a számot nevezhessük az illető esemény valószínűségének. Részletesebben, a valószínűséget olyan P : ^4. —> [0,1] halmazfüggvényként kívánjuk bevezetni, hogy tetszőleges A 6 A eseményre a fent megfogalmazott tapasztalati tény matematikai tételként legyen bizonyítható, vagyis (a független kísérletsorozat fogalmának alkal­ mas kidolgozása után) fennálljon, hogy Sn(A)/n valamilyen értelemben P(A)-hoz tart, ha n —>oo. Mint kiderül, ezt éppen azáltal lehet elérni, hogy a relatív gyakori­ ság függvénytulajdonságait leutánozzuk, vagyis az A > —>Sn(A)/n halmazfüggvény — rövidebben írva 5n(-)/n — tulajdonságait posztuláljuk A P(A)-ra (más szó­ val Sn(-)/n tulajdonságait fogadjuk el A P(A ) definiáló tulajdonságainak). 1 6 .2 . V alószín ű ségi m ez ő .

16.2. Valószínűségi mező

173

Véges sok kimenetellel bíró valószínűségi kísérlet esetén tehát feltesszük, hogy a kísérlethez adva van a kimenetelek nemüres Q halmaza, az eseménytér, az ese­ mények véges A = 2n = {A : A C Í7} algebráján pedig adva van egy P nemnegatív, additív halmazfüggvény (azaz P (A ) > 0, A e A , és ha A\, A^,. . . , e A páronként idegen halmazok — tehát egymást mint események kizárják — , akkor P(U j=iAj) = £ * = 1P (A j)) úgy, hogy P (íí) = 1. A P(i4) számot az A € A esemény valószínűségének, a kísérletet leíró (0, A , P ) hármast pedig (véges) való­ színűségi mezőnek nevezzük. — — — — —

A valószínűségi mező axiómáinak közvetlen következményei: Minden A eseményre igaz P (A C) = 1 — P (A), speciálisan az 0 = ílc lehetetlen esemény valószínűsége 0. Minden A eseményre igaz 0 < P (A ) < 1. Ha A C fi, akkor P (A ) < P (B), és P(J5 - A) = P (B) - P(A). Minden A, B eseményre igaz P (A U B) = P (A ) + P (B) —P (A D B). Az előző azonosság indukcióval nyerhető kiterjesztése az általános szitafor­ mula, amely szerint tetszőleges A i , ... ,An eseményekre

P ( ^ u - U i,) ^ ( - 1 ) ‘« k= 1

£

P ( 4 n n •• • n

l< ji< ---< jk < n

(Ez formailag csak abban különbözik a kombinatorikai szitaformulától, hogy benne számosság helyett valószínűség szerepel.) Egy véges (Í7, A, P) valószínűségi mezőt klasszikusnak nevezünk, ha minden kimenetel valószínűsége egyenlő. Ekkor Q minden részhalmaza esemény, és bár­ mely A esemény valószínűsége egyenlő az A-hoz tartozó kimenetelek számának és az összes kimenetelek számának hányadosával (vagy, ahogyan a valószínűségszá­ mítás egyik nagy megalapozója, Jacob Bernoulli fogalmazta, az A szempontjából kedvező esetek számának és az összes lehetséges esetek számának hányadosával). E számok kiszámításához tipikusan valamilyen kombinatorikai összeszámlálási fel­ adatot kell megoldani, ezért ilyenkor kombinatorikus valószínűségszámítási problé­ máról beszélünk. Egy példa: Dobjunk egyidejűleg két kockát n-szer. Számítsuk ki annak a pn valószínűségét, hogy eközben legalább egy alkalommal két hatost dobunk. A lehetséges esetek száma 36n. Egyszerűbb a két hatos szempontjából kedvezőtlen esetek számát kiszámítani: 35n (mindkét esetben ismétléses variációkat számlálunk össze). Ezért pn = 1 — (| |)n. Innen könnyű meghatározni azt a legkisebb n do­ básszámot, amely mellett 1/2-nél nagyobb a valószínűsége (vagy ahogyan köznapi nyelven mondják, 50%-nál több az esélye) annak, hogy legalább egyszer két hatost

174

Valószínűség

dobunk; ez a dobásszám történetesen 25-nek adódik. Ugyanezt a feladatot más­ képpen is megfogalmazhatjuk: Két urna mindegyikében hat, 1-től 6-ig számozott golyó van. Mindkét urnából kiveszünk egy-egy golyót (találomra, hiszen az urnákba nem látunk be). A kivett golyókat visszarakjuk, megint kiveszünk egvet-egyet, és így tovább. Számos kombinatorikus valószínűségszámítási feladat átfogalmazható ilyen ún. umaproblémává. A most bemutatott feladatban visszatevéses mintavétel történt. Egy kockát 4-szer kell feldobni ahhoz, hogy valószínűbb legyen legalább egy hatos dobás előfordulása, mint az, hogy egyszer sem dobunk hatost. Pascal Fermatnak írott egyik levelében megemlíti, hogy ennek alapján de Méré lovag a két kockára vonatkozó fenti feladatban 24 dobást várt volna, és azt, hogy 25 a helyes megol­ dás, az „aritmetika ellentmondásának” tekintette. Emiatt szokás a jelenségre „de Méré paradoxonként” hivatkozni, avagy a problémát de Méré lovagnak tulajdoní­ tani, annak ellenére, hogy mindezeket a kérdéseket már Cardano sikeresen tárgyalta az előző században. Pascal és Fermat nevezetes levelezése 1654-ben a valószínaségszámítás, mint önálló matematikai diszciplína kezdetét jelenti. A levelezés lő témája a méltányos osztozkodás problémája volt (amelyet a legenda szintén de Mérének tulajdonít, bár ez már Pacioli Summa arithmetica című müvében is sze­ repelt, számos hibás megoldást eredményezve Fermat és Pascal levelezése előtt): Egy játékot két játékos egyenlő esélyekkel játszik, ugyanakkora téttel. Megálla­ podnak, hogy az viszi el a másik tétjét, aki előbb nyer n számú játszmát. Játszani kezdenek, de abba kell hagyniuk a játékot egy olyan ponton, amikor az első já­ tékos még csak n — a, a második n — b számú játszmát nyert (1 < a, 6 < n). Hogyan osztozzanak meg méltányosan a téteken? A megoldás kulcsa annak közös felismerésében rejlett, hogy a méltányos osztozkodásnak azon valószínűségeknek az arányában kell történnie, amelyekkel az az első és a második játékos megnyerné az egész sorozatot, ha a játékot folytatni tudnák. Pascal a problémát növekvő a és 6-ben rekurzívan oldotta meg; Fermat elegánsabb megoldása szerint a kívánt arány X)fc=a_1 (a f^_1)/zZfc=o (a+fc_1)> ez vezette Pascalt a binomiális együtt­ hatók „háromszögének” vizsgálatára. Másik példa: Mi a valószínűsége annak az eseménynek, hogy ötös lottószelvé­ nyünkkel két találatot érünk el? A lehetséges esetek száma (99), a kedvező eseteké (2) d f ) • (közönséges) kombinációkat kellett megszámlálnunk. Ez a feladat is átfogalmazható urnaproblémává (mi több, ez ténylegesen urnaprobléma, hiszen lottóhúzáskor a számokat tartalmazó golyókat egy urnaszerű tartályból veszik ki, amelybe csak azért lehet belelátni, hogy mindenki lássa: a számokat a húzó nem ismerheti fel). A lottóhúzásnál visszatevés nélküli mintavétel történik. Harmadik példa (párosítási probléma, Montmort): Az 1,.... ,n számozású kár­ tyákat jól megkeverjük és az egész paklit sorban kirakjuk. Mennyi a pn>k valószí­

175

16.3. A valószínűségi mező általános fogalma

nűsége annak, hogy pontosan k kártya jön ki a jelének megfelelő sorszámú helyen (k = 0 , 1 , . . . , n)? Ha Aj jelöli azt az eseményt, hogy a j jelű kártya a j-adik helyen jön ki, azaz, hogy a j-edik helyen párosítás van, akkor, feltéve, hogy az összes n! sorrend egyformán valószínű, annak a pn>o = P ( .A i n . . . n A £) való­ színűségére, hogy semelyik helyen nincs párosítás, a szitaformulával adódik, hogy pn,o — X^i=o(—iy / j" Ezért, ha Nn^ jelöli a kérdéses eseményre nézve kedvező esetek számát, akkor Nn,fc __ (fe)-^n-fc.O _ (fc) (n ~ ^)-Pn-fc,0 _

^n,k

n\

n\

n\

(~ 1)J

k\ ^

3=0

j\

J

Látjuk, hogy bármely rögzített A; — 0, 1, 2, . . . esetén lim pn k = e_1 /k\. Speciálin—*oo ’ san, 1 /e-hez tart annak a valószínűsége, hogy egyetlen kártya sem kerül a jelének megfelelő helyre. (Később bevezetett szóhasználattal: ezek a határértékek egy 1 vá ható értékű Poisson-eloszlású véletlen változó eloszlását határozzák meg.) 1 6 .3 . A v a l ó s z í n ű s é g i m e z ő á lt a l á n o s f o g a l m a . Klasszikus valószínűségi mező­ vel leírható kísérlet esetén már Fermat és Pascal meggyőzték egymást arról, hogy ha a kísérletet (függetlenül) addig ismételjük, amíg abban egy p = P ( / i ) valószínű­ ségű esemény be nem következik, akkor (1 - p)k~lp annak a valószínűsége, hogy a szükséges ismétlések száma A>val egyenlő, k = 1 , 2, __ Világos, hogy az ismétlés­ sorozatnak, mint kísérletnek végtelen sok kimenetele van, így ezt a kísérletet véges valószínűségi mező már nem írhatja le. Ugyanez a helyzet a játékos csődjének prob­ lémájánál is, amelyet szintén Pascal vetett fel: a játékos olyan játékok sorozatát jáísza egy bankkal, amelyek mindegyikét p valószínűséggel nyeri meg, a bank pedig 1 - p valószínűséggel, és minden játék után a játékos egy dukátot kap a banktól, ha ő nyert, és egy dukátot ad a banknak, ha a bank nyert: mennyi a valószínűsége, hogy a játékos csődbe jut, ha kezdetben a dukátja van. a banknak pedig 6? Végtelen sok kimenetele van egy pont választásának is pl. valamely [a, 6] (a < b) intervallumból. Már a 18. században természetesnek tartották az egyenletességi hipotézis szerinti pontválasztás modelljét, vagyis annak a feltételezését, hogy egy H halmazból találomra választott pont H bármely részhalmazába való beleesésének a valószínűsége arányos a részhalmaz mértékével. Szükség van tehát a valószínűségi kísérlet matematikai fogalmának olyan kiterjesztésére (tehát a való­ színűségi mező fogalmának olyan általánosítására), amely végtelen sok kimenetelt és eseményt is magába foglalhat. Mivel pl. [a, 6] nem minden részhalmazának létezik mértéke, nem várható, hogy a bevezetendő általános valószínűségi mező­ fogalom értelmében az eseménytér minden részhalmaza is esemény legyen (sőt, bizonyos kísérleteknél még azt sem lehet megkívánni, hogy a maguk a kimenetelek

Valószínűség

176

események legyenek). A szükséges általános axiomatizálás — vagyis a valószínű­ ségi mezők tulajdonságainak végtelen eseménytérre is alkalmazható összefoglalása — Kolmogorovtól ered: Tetszőleges valószínűségi kísérlet esetén feltesszük, hogy a kísérlethez adva van a kimenetelek nemüres fi halmaza, az eseménytér, továbbá adva van fi részhalma­ zainak valamely A cr-algebrája (ami azt jelenti, hogy bármely A, A\, A 2 , ... 6 A esetén Ac G A és U^T1A n e A, valamint fi e A), amelyhez tartozó részhalmazok az események, végül A- n adva van egy P valószínűségi mérték, tehát egy nemnegatív, cr-additív halmazfüggvény, amelyre P (fi) = 1. (Azt mondjuk, hogy a P halmazfüggvény a-additív, ha P(A ) > 0 , valahányszor A & A, és ha A\, A 2 , .. . € A egymást páronként kizáró események, akkor P(U ^=1An) = E ^ L i P (A n).) A P(A) számot az A 6 A esemény valószínűségének, a kísérletet leíró (fl,A,P) hármast pedig valószínűségi mezőnek nevezzük. Egy kísérlet eseményeinek a-algebrája zárt a halmazelméleti műveletek meg­ számlálható sokszor történő végrehajtására. A cr-additív valószínűség nyilván (végesen is) additív, és egy A cr-algebrán adott nemnegatív, (végesen) additív P halmazfüggvény akkor és csak akkor cr-additív, ha valahányszor A\ D A 2 2 olyan A-beli halmazok, hogy = 0, mindannyiszor lim P (A n) = 0. n —*oo

A valószínűségelmélet Kolmogorov-féle axiomatizálása a fentiek szerint egy mondatban összefoglalható: feltesszük, hogy bármely valószínűségi kísérlethez adva van egy (fi, A, P) valószínűségi mező (amely a kísérletet leírja). A valószínűség fentebb felsorolt tulajdonságain túl teljesül még az is, hogy — Ha A i D A 2 3 • • • és B\ C B 2 Q ■ • • tetszőleges, a „maga után vonásra” nézve a jelzett módon monoton eseménysorozatok, akkor lim P (A „) = P(n£L : Afc) n —*00

és lim P(H n) = P(u2T1ő fc). n —>00

— Tetszőleges A i , A 2, . . . € A eseményekre P(U ^=1A/:) < E fc li p (^A:), azaz a P mérték megszámlálhatóan szubadditív. Egy valószínűségi mező tehát egy olyan speciális mértéktér, ahol az alaphal­ maz mértéke 1. Másrészről, visszatérve az egyenletességi hipotézis szerinti pont­ választásra, ha a H halmaz az egyenes (vagy a sík, vagy még általánosabban, a d-dimenziós tér) Lebesgue-mérhető részhalmaza, amelynek pozitív és véges a mér­ téke, fi a Lebesgue-mérték a H halmazon, A a H halmaz Lebesgue-mérhető rész­ halmazainak 0 esetén lim P n 71— >OO

Sn(A) n

P{A) < £

= 1.

Mai szóhasználattal ez a a nagy számok {gyenge) törvényeinek legegyszerűbb alakja. Ugyancsak a binomiális eloszlás tulajdonságait használva jutott el Moivre az első lokális centrális határeloszláshoz, miszerint ha lim (kn — np)/n2/3 —>0, akkor n —> 71—>00

oo esetén teljesül a

(1)

=

aszimptotikus egyenlőség, vagyis a két oldal hányadosa 1-hez tart. Ennek jelenté­ séről a következőkben még lesz szó. Ebből további munkával következik a Moivre-Laplace-tétel, a centrális határeloszlástétel legegyszerűbb formája, amely Bernoulli törvényét messzemenően finomítja: lim P n 71— ►OO

y/n V p ( 1 ~P)

Sn{A) n

lim P n 71— >OC

( Sn(A) - np \y/np( 1 - p)

$(x)

minden valós ar-re, ahol ( 2)

f — oc

e 2 dt.

J

16 .5 . V életlen vá lto zó k. Valószínűségi kísérlet eredményeként számok is elő­ állhatnak, pl. a fenti Sn{A), vagy n kocka feldobásakor az egyes kockákkal dobott számok összege. Az így keletkező számot egy véletlen változó (másképpen való­ színűségi változó) értékének nevezzük. Mindkét tekintett véletlen változó tehát olyan függvény, amelyek minden kimenetelhez egy valós számot (példáinkban ra­ cionális, ill. természetes számot) rendel. E függvény értékkészletét nevezzük a szóbanforgó valószínűségi változó értékkészletének. Valamivel általánosabban, egy valószínűségi mező eseményterén értelmezett X függvényt diszkrét véletlen (vagy valószínűségi) változónak nevezünk, ha értékkészlete véges vagy megszámiálhatóan végtelen és mindazok a kimenetelek, amelyekre X egy rögzített értéket vesz fel, eseményt alkotnak. Az utóbbi feltétel biztosítja, hogy a diszkrét valószínűségi

180

Valószínűség

változó bármely lehetséges értéke előfordulásának legyen valószínűsége. Végtelen értékkészletü diszkrét valószínűségi változóra példa az ismétlések X száma, ame­ lyek ahhoz kellenek, hogy egy pozitív valószínűségű esemény bekövetkezzen; itt X a oo értéket is felveheti, nulla valószínűséggel. Ha az értékkészletre vonatkozó számossági feltételt elhagyjuk, a véletlen változó még általánosabb fogalmához ju­ tunk; ekkor azt követeljük meg, hogy minden x valós számra azok a kimenetelek, amelyeken X értéke nem nagyobb mint x, eseményt alkossanak. Ha az X diszkrét valószínűségi változó értékkészlete {xi , X2, ...}, akkor ezek­ hez a lehetséges értékekhez tartozó p\ = P (X = xi), P2 = P ( A = X2 ), valószínűség-sorozatot, ahol a tagok összege 1, az X eloszlásának nevezzük. Egy p valószínűségű A esemény 5 n(A) gyakoriságának (n,p)-paraméteres binomiális eloszlását már említettük. Az ötös lottó húzásán az egyetlen szelvénnyel játszó já­ tékos találatainak száma is egy Y véletlen változó, és P(Y" = k) = (j£) (585A.)/ (95°), k = 0,1,3,4, 5; ez egy hipergeometrikus eloszlású valószínűségi változó. Ha X diszkrét véletlen változó az xi , X2, ... lehetséges értékekkel és a rendre ezekhez tartozó pi,P2 , • • • eloszlással, és X értékét n-szer függetlenül megfigyeljük (mérjük), akkor gyakran észrevehető, hogy — Sn(j)-ve 1 jelölve Xj gyakoriságát — a mérési eredmények véletlen (Sn(l)x i -I- Sn(2)x2 + • • •)/n átlaga valamely kons­ tans szám körül ingadozik, ha n nő. Ezt a számot kívánjuk X várható értékeként értelmezni; jele E(A). Minthogy a nagy számok törvénye szerint minden j -re az Sn(j)/n relatív gyakoriság pj = P(X = Xj ) körül van, X várható értékének definíciója E(X) = x j P j (ha ez értelmes, vagyis ha ez a sor abszolút konver­ gens). Természetesen, ha X-nek csak véges sok lehetséges értéke van, akkor E(X), a megfelelő súlyozott véges összeg, mindig létezik. Egy X véletlen változó vár­ ható értéke körüli átlagos ingadozásának nagyságát jellemezhetjük X szórásával, amelyen a D ( I ) = y j E([X - E(X)]2) számot értjük, ha ez véges. A binomiális eloszlású Sn(A ) változó várható értéke és szórása a képletből a binomiális együtthatók egyszerű átalakításával kiszámítható; E (Sn(A)) = np és D (5 n(A)) = \Jnp{l — p). Ez még egyszerűbben adódik, ha észrevesszük, hogy Sn(A) = X\ H------h X n, ahol Xj = 1 vagy 0 aszerint, hogy az A a j-edik ismétlésre bekövetkezik vagy sem (j = 1 , . . . , n), és használjuk a várható érték linearitását va­ lamint azt, hogy független véletlen változók összegének szórásnégyzete megegyezik a tagok szórásnégyzetei összegével. Hasonlóan (de kevésbé egyszerűen) nyerhető a lottótalálatok számának, mint hipergeometrikus eloszlású valószínűségi változó­ nak a várható értéke: a szórása pedig valamivel több mint |. Ezek a példák mutatják, hogy véletlen változó várható értéke nem szükségképpen tartozik értékkészletéhez. Végtelen értékkészletü valószínűségi változónak pedig nem is mindig létezik várható értéke.

181

16.5. Véletlen változók

Egy tetszőleges X valós értékű véletlen változó eloszlásfüggvényén az F{x) = P(X < x) = P({u> e Q : X(u) < z}), x e R, függvényt értjük, amelyről megmutatható, hogy az egész M számegyenesen nemcsökkenő, jobbról folytonos, lim F{x) = 0 és lim F(x) = 1. Ebből a függvényből elvben mindent kiolvashaX — ►— CX)

x —> o o

tünk, amit csak X-ről ebben a tárgyban kérdezni lehet. Ha X diszkrét az x\, X2 , ... lehetséges értékekkel, akkor F(x) = Y^{j:Xi 0 véges szám, röviden N(/i, a2) eloszlású, ha X eloszlása folytonos az

f(t) =

=

e B, A B jelsorozatokat, ahol A és B tetszőleges formulák, — a 3xA és VxA jelsorozatokat, ahol A tetszőleges formula, x tetszőleges válto­ zójel. Csak az olyan jelsorozat formula, amelyet e három szabály véges számú alkal­ mazásával építhetünk fel. Ha valamely x változó szerepel az A formulában, akkor azt mondjuk, hogy a 3xA formulában (és hasonlóképpen a VxA formulában) x a kvantorral le van kötve, röviden, x kötött változó. Az x változót az A V B for­ mulában akkor és csak akkor tekintjük kötöttnek, ha A-ban is, 5-ben is kötött. A nem kötött változókat a formula szabad változóinak nevezzük. A mondottak alapján bármely formula bármely változójáról eldönthető, hogy kötött vagy sza­ bad változója-e a formulának. Az olyan formulát, amely nem tartalmaz szabad változót, zárt formulának nevezzük. Példa: ha a csoportelmélet nyelvét egy két­ változós és egy egyváltozós függvényjelt tartalmazó, konstans jelek és relációjelek nélküli nyelvnek tekintjük (habár, mint láttuk, ezt a nyelvet kiegészíthetjük az e konstansjellel is, de kiderülne, hogy e helyett mindig írhatunk x x - 1 -et), akkor (y_1)xy, xy , yx kifejezések; xy = yx formula, amelyben mindkét változó szabad; Vx Vy (xy = yx) zárt formula. A természetes nyelvek hasznosak (és érdekesek), mert segítségükkel a való­ ságról (vagy valamilyen képzelt világról) beszélhetünk: a nyelv mondatai esemé­ nyeknek vagy összefüggéseknek felelnek meg, s többnyire az is kiderül, helyesen tükrözik-e a nyelvi jelenségek a valóságot (vagy legalábbis törekedünk ennek a ki­ derítésére). A csoportelmélet nyelve a valóságnak egy eléggé szűk szeletéről, a csoportoknak nevezett algebrai struktúrákról való beszélgetésre alkalmas, és en­ nek a nyelvnek a tárgyával való kapcsolatáról matematikailag pontos kijelentése­ ket tehetünk. Hasonló igaz az előzőkben bevezetett nyelvek mindegyikére. Hogy ezeknek az általános kijelentéseknek értelmet adjunk, a nyelvek után be kell ve­ zetnünk a — velük kapcsolatba hozható — struktúrák fogalmát is. Ha adott egy L nyelv, L-struktúrán egy M halmazt értünk, amelyen minden L-beli n változós függvényjelnek meg van feleltetve egy n változós művelet, minden L-beli n váltó-

198

Matematikai logika

zós reláció jelnek egy n-változós reláció (azaz M N-nek egy részhalmaza), és minden L-beli konstansjelnek M egy eleme. Ezt a megfeleltetést L interpretációjának ne­ vezzük M-ben. Különböző interpretációkkal keletkező struktúrákat különbözőknek tekintünk. Ha világos, hogy mi az L nyelv, akkor röviden csak struktúráról be­ szélünk. (Matematikai logikai szövegekben találkozhatunk az individuum-változó és individuum-tartomány szavakkal. Ezek megfelelően változó jelt és struktúrát jelentenek.) Az olyan függvényt, amely L változójeleinek a halmazát M -be képezi le (vagyis minden változójelnek egy Aí-beli érték adását), értékelésnek nevezzük. Az értékelést kiterjeszthetjük az összes kifejezésekre (a felépítésükben használt függ­ vényjelek száma szerinti indukcióval). Ha ezután egy A atomi formulában végezzük el a változók értékelését (ami a benne szereplő változóknak M-beli érték adását jelenti), akkor az atomi formulából egy, M elemeire vonatkozó állítás lesz, ami vagy azt fejezi ki, hogy az M struktúrában két kifejezés értéke az adott értékelés mellett ugyanaz, vagy pedig azt, hogy bizonyos változók értékei valamely M-en értelmezett (a tekintett interpretációnál fellépő) relációban vannak egymással. Ezt az állítást a szóban forgó atomi formula jelentésének nevezhetjük. Az első esetben, ha annak a két kifejezésnek az értéke az M struktúrában valóban egyenlő, akkor azt mondjuk, hogy A a tekintett értékelés mellett igaz, különben A a tekintett értékelés mellett nem igaz, egy szóval hamis. Ezzel A-nak igazságértéket tulajdonítunk, ti. az igaz és hamis igazságértékek egyikét. (Ne feledjük: változó és kifejezés értéke mindig a struktúra egy eleme, igazságértéke nincs; másrészt, atomi formulának értéke nincs, de igazságértéke van, ti. jelentése van, amelyről a struktúra és az értékelés ismere­ tében eldönthető, hogy igaz, vagy hamis.) Ezután minden formulának tetszőleges értékelésnél igazságértéket fogunk adni. Előbb azonban figyeljük meg, hogy amikor értékelést végzünk, minden válto­ zójelhez a tekintett struktúra valamely elemét rendeltük értékként, s nem vezettünk be olyan (másfajta) változójeleket, amelyek pl. a struktúra valamely részhalmazát vehetnék fel értékként (jóllehet bizonyos állítások kifejezéséhez ezekre is szükségünk lehet — pl. „csoport bármely két részcsoportjának közös része is részcsoport” ). Ezért a bevezetett nyelveket elsőrendű nyelveknek nevezzük, megkülönböztetésül az olyan bonyolultabb nyelvektől, amelyek jelkészletéhez „ halmazváltozó-jelek” (vagy általánosabban, függvény- és relációváltozó jelek — miért általánosabb ez a fogal­ mazás?) is tartoznak. Az ilyeneket is tartalmazó nyelvek a másodrendű nyelvek. Az egyetemi matematikai logikai „törzsanyagban” csak az elsőrendű nyelvek szere­ pelnek. Ám a matematikai gyakorlatban gyakran előfordulnak másodrendű nyelven felírt formulák. Példa: a teljes indukció Peano-féle axiómája halmazváltozót tar­ talmaz („bármely k számra és bármely olyan M halmazra, hogy (1 € M és ha n e M, akkor n' G M ), érvényes k G M ” ).

199

18.2. ítéletkalkulus

A logikai műveletjelek bevezetésekor említettük, hogy milyen logikai kapcso­ latok jelzésére használatosak. Ez, részletesebben, a következőt jelenti: Megállapo­ dunk abban, hogy az A és B atomi formulákból képezett Aw B formulának va­ lamely értékelésnél pontosan akkor adjuk az „igaz” igazságértéket, ha ugyanannál az értékelésnél^. igaz vagy B igaz, és ehhez hasonlóan definiáljuk A V B igazságér­ tékét akkor is, ha A és B tetszőleges olyan formulák, amelyek igazságértékét már tudjuk. Ugyanezzel a meggondolással definiáljuk A A B, A —> B, A B és ->A igazságértékét bármely értékelésnél. Mielőtt a kvantort tartalmazó formuláknak is adnánk igazságértéket, tegyük fel, hogy csupa kvantormentes formulákat kell vizsgálnunk, valamely rögzített értékelés mellett. Ezek jelentései állításoknak egy halmazát szol­ gáltatják, amelyek mindegyike vagy igaz, vagy hamis. Természetes kérdés, hogy az így kapott állítások közül bizonyosak igazságértékéből hogyan következtethe­ tünk mások igazságértékére, anélkül, hogy állításaink jelentését figyelembe ven­ nénk. Amit erre vonatkozóan meg tudunk állapítani, az bármely fentebb definiált nyelvre alkalmazható lesz. Ezért most azzal az egyszerűbb helyzettel foglalkozunk, amikor olyan állítások vannak adva, amelyek igaz vagy hamis volta eldönthető, de nem korlátozzuk ezen állítások jelentését (tehát nem írjuk elő, mint az eddigiek­ ben, hogy az állítás jelentése csak valamely érvényes egyenlőség, vagy valamilyen reláció fennállása lehet). Az ilyen állításokat ítéleteknek nevezzük. ítélet tehát a következő mondat is: „A Holdon vannak emberek” . Ennek igazsága — pl. a hírszolgálatból — eldönthető. Ugyanúgy, mint az előző bekezdésben, igazságértéket tulajdoníthatunk a következő furcsa állításnak is (tehát az is ítélet): „A Holdon vannak emberek vagy kétszer kettő négy” . (Igaz, vagy hamis?) Az ítéletek logikai szempontból való vizsgálatához is egy egyszerű nyelvre van szükségünk, amelyet az ítéletkalkulus nyelvének nevezünk. Ennek a jelei: 18.2. ítéletkalkulus.

— ítéletváltozó-jelek: A i ,A 2, ...; ha csak néhányra van szükségünk, írhatunk helyettük A-1 , B-1 , stb. — logikai műveletjelek:

V, A, —

«-».

Az ítéletkalkulus nyelvét zérusrendű nyelvnek is szokták nevezni. Az ítéletkalkulus formulái azok a jelsorozatok, amelyek ítéletváltozó-jelekből (és az egyér­ telműséget biztosító zárójelekből) az utóbbi öt műveletjel végesszámú alkalmazá­ sával keletkeznek. Az ítéletkalkulusbeli értékelés csak igazságértékekre vonatkozik (nincsenek közönséges változó jelek, sem struktúrák): az ítéletváltozó-jeleknek tet­ szőleges igazságértékeket adunk, s a logikai műveletjelet is tartalmazó formulák igazságértékét a következő táblázatok alapján számíthatjuk ki:

Matematikai logika

200

A

—1

i h

h i

i h

i h i h h h

V

i h

i h i i i h

-» i

i h

h i h i i

i h

i h i h h i

A táblázatok mutatják, hogy pl. az A A B ítélet pontosan akkor igaz, ha A is igaz, B is igaz, tehát a A logikai műveletjel valóban az „és” kötőszót jelenti. Két ponton a táblázatok tartalma nem ennyire magától értetődő. Az A V B ítélet akkor is igaz, ha A és B közül csak az egyik igaz, az ítéletlogika tehát a „vagy” szónak a lehetséges és szokásos két értelme közül a megengedőt alkalmazza és nem a kizárót (az utóbbit a mindennapi nyelvben egyébként rendszerint a „vagy” két­ szeres használatával fejezzük ki, pl. „vagy iszik, vagy vezet” ). Az A —» B ítélet mindig igaz, ha A hamis — ez meglepő lehet. Gondoljunk azonban a tréfás szegedi mondásra, amely szerint „ha Vásárhelyi Pál meghallja, hogy a városháza órája üti a tizenkettőt, akkor mindig megemeli a kalapját” . Ez természetesen igaz állítás, mert a szobor nem hall. A logikai műveletjeleket úgy is felfoghatjuk, mint algebrai műveletek jeleit az {i, h} kételemű halmazon. Ilyen minőségükben nevük is van: -i a negáció, A a konjunkció, V a diszjunkció, —* az implikáció és az ekvivalencia. Közülük kettő is elég lenne, a többiek kifejezhetők pl. a konjunkció és a negáció segítségével. Valójá­ ban egy is elég, pl. az a művelet, amely a (h, h) párhoz az i értéket rendeli, a többi három párhoz pedig a h értéket. Ez a „sem-sem” művelet, mert értéke pontosan akkor igaz, ha sem az egyik, sem a másik változója nem igaz. (Lássuk be, hogy „a vagy 6” így fejezhető ki vele: „sem sem a, sem b, sem sem a, sem 6” !) Persze, a többi műveletek is bonyolultan állíthatók elő a sem-sem függvénnyel. A két­ elemű halmazon értelmezett (akárhány változós) műveleteket Boole-függvényeknek nevezzük. Ezek mind előállíthatok a konjunkció és negáció (vagy a diszjunkció és negáció) segítségével. A Boole-függvények nemcsak az ítéletkalkulus, hanem a szá­ mítógépek számára is fontosak, mert a számítógépek mindent Boole-függvényeken keresztül számítanak ki. Az olyan formulát, amely minden értékelésnél igaz, tautológiának nevez­ zük. Mivel n ítéletváltozót tartalmazó formulának 2n különböző értékelése van, mindig eldönthető, hogy egy formula tautológia-e. Nyilvánvalóan tautológia az formula. Ezt „ a kizárt harmadik elvének” nevezzük, mert azt jelenti, hogy bármely állítás vagy igaz vagy nem igaz, harmadik lehetőség nincs. Nevezetes ta­ utológia: (A A (A —> B )) —> B. Ha két formula ugyanazoknál az értékeléseknél igaz, akkor azt mondjuk, hogy a két formula ekvivalens. Az A és B formulák ak­ kor és csak akkor ekvivalensek, ha A «-> B tautológia. Nevezetes ekvivalenciák (tautológiává átírva): ->(A A B) ->A V -(A V B) ->A A -*B. Ezek a De Morgan-azonosságok. Ezeket is használva bebizonyítható, hogy az A \ ,. . . , An ítéletváltozókból képezett minden formula ekvivalens egy olyan formulával, amely

18.3. Függvénykalkulus

201

csupa A\ A A!2 A . . . A A'n alakú tagok diszjunkciója, ahol minden i-re A!i = Ai vagy A\ = ->A i. Az utóbbit a tekintett formula teljes diszjunktív normálalakjának nevezzük. A konjunkció és diszjunkció szerepét felcserélve hasonlóan vezethető be formula teljes konjunktív normálalakja. Az ítéletkalkulus logikai (vagy szemantikai, azaz jelentés-tani) következmény­ fogalma: ha 5 formulák egy halmaza és A egy formula, azt mondjuk, hogy A logikai következménye S-nek, ha minden olyan értékelésnél, amelynél minden 5-hez tartozó formula igaz, A is igaz. Jelölése: 5 f= A. Kívánatos, hogy találjunk olyan eljárást, amellyel 5 minden logikai következménye előállítható 5-hez tartozó formulákból. Egy ilyen eljárás eredménye olyan Ai, A2 , . . . , Ak formulasorozat lehet, amelyben az utolsó formula A, és minden z = 1 , 2 ,.. ., k-ra a következő három lehetőség közül legalább egy teljesül: — A i G 5, — Ai tautológia, — Ai kisebb indexű A-kból valamely levezetési szabállyal keletkezik, azaz olyan szabállyal, amely biztosítja, hogy ha valamely értékelésnél a mondott kisebb indexű A-k mind igazak, akkor Ai is igaz. Az ilyen formulasorozatot A bizonyításának nevezzük 5-6Ó7; ha létezik ilyen, azt mondjuk, hogy A levezethető S-ből, vagy másképpen, A szintaktikai (azaz nyelv­ tani) következménye S-nek. Jelölése: 5 h A. Elegendő a következő egyetlen leve­ zetési szabályt alkalmaznunk: ha valamely értékelésnél A és A —> B igaz, akkor B is igaz (ez belátható a példaként említett tautológiából). E szabály (középkori eredetű latin) neve: modus ponens, ami kb. állító (következtetési) módot jelent. Érvényes az ítéletkalkulus teljességi tétele: Bármely 5 formulahalmazra és A formulára A szemantikai következménye 5-nek akkor és csak akkor, ha A szintakti­ kai következménye 5-nek. (Tömörebben: 5 (= A