Matematikai bizonyítás

A Wikipédiából, a szabad lexikonból.

Egy matematikai bizonyítás a matematika tudományában érvényesnek vagy igaznak tartott kijelentések érvényessége demonstrálásának, igazolásának módja. Elvileg pusztán abban különbözik a többi tudomány igazolási módszerétől, hogy matematikai természetű kijelentésekre használják. Gyakorlatilag azonban sokkal szigorúbban és következetesebben alkalmazza azt a módszert, melyet Descartes fejtett ki először az Értekezések a módszerről című könyvében, és mely a tudományos kutatás gyakorlatával szemben támaszt követendő eljárásként.

A matematikában az igaz kijelentések igaz volta kizárólag gondolati úton, matematikai bizonyítással fedhető fel. A matematikai bizonyítással igaznak minősített kijelentéseket matematikai tételeknek nevezik.

Tartalomjegyzék

1 Formális és informális bizonyítás
2 Történeti áttekintés
3 Bizonyítási módszerek
4 Direkt bizonyítások
5 Indirekt bizonyítás
6 Egzisztenciabizonyítások
7 További levezetési lépések
- 7.1 Láncszabály
8 Matematikai bizonyítási módszerek

[szerkesztés] Formális és informális bizonyítás

Egy matematikai bizonyítás, vagy annak részletei lényegében abból állnak, hogy igaznak elfogadott kijelentéseket alapul véve kimondják egy másik kijelentés igaz voltát is. Az igazság átöröklésének ezen mozzanatait levezetési lépéseknek nevezik, melyeknek létjogosultsága a levezetési szabályok sokaságában rögzített feltételek alapján minősíthető helyesnek. Hogy miből származik a tételek igazsága, azt a matematikusok közössége döntő többsége, Frege és Hilbert bizonyításelméleti kutatásaira alapozva a következőképpen látja:

Az A kijelentés bizonyítása lényegében nem más, mint állítások egy olyan véges

(A₁,A₂, A₃, ...,A_n)

sorozata, melyenek utolsó eleme az A kijelentés és melynek tetszőleges B eleme vagy matematikai axióma vagy olyan kijelentés, ami előtt a sorozatban szerepel egy ' ha C, akkor B ' alakú kijelentés C-vel együtt. Eszerint a levezetések úgy származtatják át az axiómákról a tételre az érvényességet, hogy csupa olyan ' ha ..., akkor ... ' lépésekből álló láncokból állnak, ahol az legelső mondat axióma, az utolsó mondat pedig maga a tétel. A levezetések megalkotását a levezetési szabályok és módszerek, például az esetszétválasztás szabálya vagy az indirekt bizonyítás elve segítik.

Ez utóbbi, a legszélesebb körben elfogadott nézetet nevezik formalista álláspontnak. Kétség kívül eredményezi a tételek érvényességét, és jól körülhatárolt fogalmai révén vizsgálhatóvá, kutathatóvá teszi a bizonyítások témakörét. A matematikai logikában ennek az eljárásnak a formális megfogalmazásaként definiálják a formális rendszerbeli levezetést.

Ezzel szemben például Kalmár László – aki maga is a matematikai logika kiemelkedő tudósa volt – felhívja a figyelmet a formalista szemlélet hiányosságaira. A tételek igazolásához hozzátartozik az, hogy az alkalmazásaikban működjenek, használhatóak legyenek.

Lakatos Imre sokkal messzebbre megy állásfoglalásában. Szerinte egy matematikai bizonyítás elvégzése esetén a fent vázolt eljárás kivitelezése csak a feladat töredéke. Egy tételt bizonyítani annyit tesz, mint olyan matematikai fogalomtárat és levezetési eszközrendszert kialakítani, mely a tétel – formalista értelemben vett – levezethetőségének elégséges (és lehetőleg szükséges) feltételeit biztosítja. A matematikai tevékenységben a kihívást nem levezetések megtalálása, hanem olyan elmélet találása, mely egyszerre biztosítja az addig elfogadott tételek és a bizonyítani kívánt igaz tétel – formalista értelemben vett – levezethetőségét. Lakatos álláspontjának igazolását a Gödel tételekben látja. A tételek metodológiai következménye, hogy semilyen releváns matematikai elméletet nem lehet egyetlen formális rendszer keretében leírni, mert mindig megfogalmazhatók lesznek benne olyan állítások, melyeknek igaz vagy hamis voltáról levezetéssel vagy cáfolással nem leszünk képes meggyőződni.

[szerkesztés] Történeti áttekintés

Lásd még: A logika története, A matematikafilozófia története.

Egy állítás melletti érvelés elfogadott menetét és az alkalmazható technikákat a Szókratész korabeli görög filozófusok alakították ki. A matematikai állítások melletti érvelés mai napig elfogadott formáit Arisztotelész Organonjában és Eukleidész Elemek című művében, illetve néhol Platón műveiben találhatjuk meg elsőként. Ezekben a művekben elvi, a logikai érvelésben elkövetett hibát nem találhatunk, annál inkább találunk azonban hézagokat, hiányzó láncszemeket a bizonyításokban. A XIX. század nagy matematikusai és logikusai (Cauchy, Weierstrass, Abel, Bolzano, Frege) mutattak rá arra, hogy nem elegendő a bizonyítást hihetőnek, elfogadhatónak ítélni, alaposan elemzés alá kell vetni a bizonyítás lépéseit magukat is. Ekkor alakult ki a szigorú bizonyításelemzés eljárása, mely a matematika tudománymetodológiájának legjellegzetesebb sajátossága.

[szerkesztés] Bizonyítási módszerek

Bár a levezetés fenti definíciója egyfajta egyenes út szemléletes képét mutatja, mely az axiómáktól a tételig vezet, valójában egy A állítás levezetésénél az egyedi lépésekben nagyon sok addigi tételt felhasználnak. Itt inkább arra kell gondolni, hogy egy adott $\mbox{ }_{\mathcal{T}}$ matematikai elmélet (például az euklideszi geometria vagy a számelmélet) összes tételként ismert állításának következménye A. Ezt így jelöljük:

$\mathcal{T}:\mathbf{A}$ vagy $\mathcal{T}\vdash\mathbf{A}$

Nem kell azonban a bizonyításokat ténylegesen az axiómákig visszavezetni, valójában ez lehetetlen is lenne. Ehelyett elegendő megmutatni, hogy ha valamely A kijelentés levezethető, akkor milyen lépésekkel kell kiegészíteni a levezetését ahhoz, hogy a B kijelentés is levezethető legyen. Azt, hogy az A állítás levezethetőségéből következik a B állítás levezethetősége (tehát a levezetési lépést) a következőképpen jelöljük:

$\frac{\;\mathcal{T}:\mathbf{A}\;}{\mathcal{T}:\mathbf{B}}$

A bizonyításokat vizsgálva egyfajta kettősségre bukkanhatunk. Az egyik típus, amikor lépésről lépésre előrehaladva építjük föl az A bizonyításából a B bizonyítását, vigyázva természetesen arra, hogy a levezetési lépéseket jól végezzük és az igazság öröklődjön az egyik lépésről a másikra. Ezt nevezik direkt bizonyításnak. A másik típus az amikor egy állítás ellenkezőjének lehetetlenségét demonstráljuk – amúgy szintén aprólékos levezetési lépésenként. Ez az indirekt bizonyítás. A kettősség megjelenése a ókori görög deduktív matematika kialakulása idejére tehető, amikor két eltérő igazolási mód vetélkesdett egymással, a konstruktív bizonyítás (a thalészi kongruenciabizonyítás) és a Parmenidész által egyedüli igazolási módnak tartott, a lehetetlenre történő visszavezetést alkalmazó érvelés (redukció ad abszurdum).

[szerkesztés] Direkt bizonyítások

A matematikai állítások (legalapvetőbb, de már értelmes) logikai szerkezete a következő lehet:

$\mathbf{A}\vee\mathbf{B}$ azaz 'A vagy B'

$\mathbf{A}\wedge\mathbf{B}$ azaz 'A és B'

$\mathbf{A}\Rightarrow\mathbf{B}$ azaz 'ha A, akkor B'

$\neg\mathbf{A}$ azaz 'nem A'

$(\forall x)\mathbf{A}(x)$ azaz 'minden x-re A'

$(\exists x)\mathbf{A}(x)$ azaz 'van olyan x, ami A'

Amikor levezetünk egy állítást, ezek közül kerül ki a levezetés utolsó eleme, a konklúzió. A bizonyítás tevékenysége előtt (levezetés keresésekor) mindig azt kell először eldönteni, hogy mi a tétel állításának (igaznak titulálásának) elégséges feltétele. Az alábbiakban összefoglaljuk, hogy mik a fenti alakú kijelentések állításának feltételei, ha direkt bizonyítást végzünk. A ¬A alakú állításokat külön tárgyaljuk.

Tagadás nélküli kijelentések állításának feltételei
Állítás	Levezetési lépés	Szavakban
A ∨ B	$\frac{\mathcal{T}:\mathbf{A}}{\mathcal{T}:\mathbf{A}\vee\mathbf{B}},\;\;\frac{\mathcal{T}:\mathbf{B}}{\mathcal{T}:\mathbf{A}\vee\mathbf{B}}$	az A ∨ B diszjunkciót állíthatjuk, ha legalább az egyik tagja levezethető
A ∧ B	$\frac{\mathcal{T}:\mathbf{A},\mathbf{B}}{\mathcal{T}:\mathbf{A}\wedge\mathbf{B}}$	az A ∧ B konjunkciót állíthatjuk, ha mindkét tagja levezethető
A ⇒ B	$\frac{\mathcal{T}\cup\{\mathbf{A}\}:\mathbf{B}}{\mathcal{T}:\mathbf{A}\Rightarrow\mathbf{B}}$	az A ⇒ B implikációt állíthatjuk, ha a T elmélethez A-t (axiómaként) hozzávéve, az új T U A elméletben levezethető B, azaz, ha A segítségével levezethető B, akkor levezethető a 'ha A, akkor B' kijelentés. (Dedukciótétel)
(∀x)A	$\frac{\mathcal{T}:\mathbf{A}(x)}{\mathcal{T}:(\forall x)\mathbf{A}(x)}$ x tetszőleges	Azaz ha tetszőleges, semmilyen kölönleges tulajdonsággal nem rendelkező x-re A(x) levezethető, akkor a ' minden x-re A(x) ' kijelentés is. (Generalizáció)
(∃x)A	$\frac{\mathcal{T}:\mathbf{A}(t)}{\mathcal{T}:(\exists x)\mathbf{A}(x)}$ adott t-vel	(∃x)A(x), azaz 'létezik olyan x, ami A '-t állíthatjuk, ha van olyan t dolog, melyet A(x)-ben az x helyére téve levezethető kijelentést kapunk

Negatív kijelentéseket (¬A alakúakat) is le lehet vezetni direkt bizonyítás segítségével. Ezek állításának feltételei a matematikai bizonyításokban a klasszikus logika szabályai alapján főként a kizárt harmadik törvényére való hivatkozáh útján történik. Konkrétan a negációra vonatkozó De Morgan azonosság és a kettős tagadás törvénye lesz az, amely segítségével átfogalmazhatjuk a negatív kijelentéseket:

$\mathcal{T}:\neg\mathbf{A}\wedge\neg\mathbf{B}\;\Leftrightarrow\;\neg(\mathbf{A}\vee\mathbf{B})$

$\mathcal{T}:\neg\mathbf{A}\vee\neg\mathbf{B}\;\Leftrightarrow\;\neg(\mathbf{A}\wedge\mathbf{B})$

$\mathcal{T}:\mathbf{A}\wedge\neg\mathbf{B}\;\Leftrightarrow\;\neg(\mathbf{A}\Rightarrow\mathbf{B})$

$\mathcal{T}:\mathbf{A}\;\Leftrightarrow\;\neg\neg\mathbf{A}$

$\mathcal{T}:(\forall x)\neg\mathbf{A}\;\Leftrightarrow\;\neg(\exists x)\mathbf{A}(x)$

$\mathcal{T}:(\exists x)\neg\mathbf{A}\;\Leftrightarrow\;\neg(\forall x)\mathbf{A}(x)$

Ezt segíti néhány negációt is tartalmazó levezetési lépés.

Negatív kijelentések direkt bizonyításban
Állítás	Levezetési lépés	Szavakban
Kontrapozíció	$\frac{\mathcal{T}: \neg\mathbf{B}\Rightarrow \neg\mathbf{A}}{\mathcal{T}:\mathbf{A}\Rightarrow\mathbf{B}}$	Ha nem B, akkor nem A, tehát ha (mégis) A, akkor lehetetlen, hogy ne legyen B.
Modus tollens	$\frac{\mathcal{T}:\mathbf{A}\Rightarrow\mathbf{B},\neg\mathbf{B}}{\mathcal{T}:\neg\mathbf{A}}$	A csak akkor, ha B is. De nem B, így A sem.
Diszjunktív szillogizmus	$\frac{\mathcal{T}:\mathbf{A}\vee\mathbf{B},\neg\mathbf{A}}{\mathcal{T}:\mathbf{B}}$	A vagy B. De nem A, tehát B.

[szerkesztés] Indirekt bizonyítás

Az indirekt bizonyítás lényegében a ¬ A kijelentés levezethetőségének feltételét adja meg. Eszerint:

Indirekt bizonyítás

$\frac{\mathcal{T}\cup\{\mathbf{A}\}:\mathbf{B}\wedge\neg\mathbf{B}}{\mathcal{T}:\neg\mathbf{A}}$

Azaz, ha az az elmélet, melyet úgy nyerünk, hogy az A kijelentést axiómaként hozzávesszük T-hez (azaz az a feltevés, hogy A igaz) ellentmondásra vezet (B∧¬B), akkor A lehetetlen, hogy levezethető legyen, sőt cáfolható, azaz ¬A levezethető.

Az indirekt bizonyítást úgy tűnhet, csak a negatív ítéletekre (¬A alakú ítéletekre) alkalmazhatjuk. A klasszikus logikában azonban érvényes a kettős negáció törlése:

A kettős negáció törlése

$\frac{\mathcal{T}:\neg\neg\mathbf{A}}{\mathcal{T}:\mathbf{A}}$

Ha nem igaz, hogy nem A, akkor A.

Eszerint azonban minden állítás bizonyítható indirekten is, hiszen csak a ¬¬A-ra kell alkalmaznunk a sémát, majd a kettős tagadást törölve nyerhetjük A-t. Világos, hogy ez egyfajta bizonytalanságot okozhat atekintetben, hogy milyen módon álljunk hozzá a tételek bizonyításához.

Megjegyezzük, hogy az intuicionista vagy konstruktivista logikában a kettős tagadást nem lehet törölni, így ott indirekten tényleg csak a negatív kijelentéseket lehet bizonyítani.

[szerkesztés] Egzisztenciabizonyítások

Fő szócikk: egzisztenciabizonyítás

Az egzisztencabizonyításokon a (∃x)A(x), azaz 'létezik olyan x, ami A ' alakú tételek bizonyítását értjük. Valójában nem sorolandók külön kategóriába, ezeket is lehet indirekten és direkten is bizonyítani. Ám sokszor fontosnak tartják számontartani, hogy milyen bizonyítással igazolták a levezethetőséget.

[szerkesztés] Konstruktív egzisztenciabizonyítás

Ezesetben a létezést úgy igazolják, hogy mutatnak olyan t dolgot, mely A tulajdonságú. Lényeges persze, hogy milyen módon teszik ezt. A konstruktivitásnak többfajta változata létezik.

[szerkesztés] Indirekt egzisztenciabizonyítás

Olyan egzisztenciaállítás bizonyítása, mely az indirekt bizonyítás végén a következő sémával vezeti le a létezést:

$\frac{\mathcal{T}:\neg\neg(\exists x)\mathbf{A}(x)}{\mathcal{T}:(\exists x)\mathbf{A}(x)}$

Ekkor egy dolog létezését úgy szándékoznak bizonyítani, hogy belátják, nem létezése lehetetlen – bár nem mutatják fel, a kívánt tulajdonságú dolgot.

[szerkesztés] Tiszta egzisztenciabizonyítás

Hasonlóan az előzőhöz, olyan egzisztenciabizonyítás, mely nem jár együtt a keresett matematikai objektum felmutatásával. Az indirekt egzisztenciabizonyításon kívül ilyen például a kiválasztási axióma felhasználásával való igazolás, sőt, szigorúan véve minden egzisztenciát állító axiómából való bizonyítás. Az ilyen állítások nem egy A(t) alakú kijelentésből vezetnek le B(k) alakú kijelentést (igazolva ezzel egy k objektumról, hogy B tulajdonságú), hanem a pusztán formális (∃x)A(x) alakúból a szintén pusztán formális (∃x)B(x) alakú kijeletést.

[szerkesztés] További levezetési lépések

Az előzőekben azt foglatuk össze, hogy mi a különböző logikai kijelentések állításának elégséges feltétele. Az alábbiakban végigvesszük, hogy mire lehet következtetni a különböző logikai szerkezetű állításokból.

Állításokból levonható következtetések
Állítás	Levezetési lépés	Szavakban
A ∨ B Az esetszétvélasztás szabálya	$\frac{\;\mathcal{T}:\mathbf{A}\vee\mathbf{B},\;\mathbf{A}\Rightarrow\mathbf{C},\;\mathbf{B}\Rightarrow\mathbf{C}}{\mathcal{T}:\mathbf{C}}$	A vagy B, de ha A, akkor (is) C, és ha B, akkor (is) C, tehát C .
A ∧ B	$\frac{\;\mathcal{T}:\mathbf{A}\wedge\mathbf{B} }{\mathcal{T}:\mathbf{A}}$ illetve $\frac{\;\mathcal{T}:\mathbf{A}\wedge\mathbf{B} }{\mathcal{T}:\mathbf{B}}$	A és B. Tehát A, illetve B .
A ⇒ B Modus ponens	$\frac{\;\mathcal{T}:\mathbf{A}\Rightarrow\mathbf{B},\;\mathbf{A}}{\mathcal{T}:\mathbf{B}}$	Ha A, akkor B. De A, tehát B .
(∀x)A(x)	$\frac{\;\mathcal{T}:(\forall x)\mathbf{A}(x) }{\mathcal{T}:\mathbf{A}(t)}$ tetszőleges t-vel.	Minden A,így t is A .
(∃x)A(x)	$\frac{\mathcal{T}:(\exists x)\mathbf{A}(x), \mathcal{T}\cup\{\mathbf{A}(x)\}:\mathbf{B}}{\mathcal{T}:\mathbf{B}}$	A tulajdonságú dolog létezéséből következik B. De létezik A tulajdonságú dolog, tehát B

[szerkesztés] Láncszabály

$\frac{\;\mathcal{T}:\mathbf{A}\Rightarrow\mathbf{B},\;\mathbf{B}\Rightarrow\mathbf{C}}{\mathcal{T}:\mathbf{A}\Rightarrow\mathbf{C}}$

Szavakban ez a következő lépés. Ha A, akkor B, ha (pedig) B, akkor C, így ha A, akkor (mindenképpen) C .

[szerkesztés] Matematikai bizonyítási módszerek

A matematikában sajátos, nemlogikai levezetési eljárások is használatosak. Egy-egy témakörben, például a számelméletben, a kombinatorikában vagy a halmazelméletben kitüntetett szerepük van.

[szerkesztés] Teljes indukció

Fő szócikk: teljes indukció

Ha egy tulajdonságot minden természetes számra bizonyítani akarunk, akkor legtöbb esetben a teljes indukció valamely variánsá alkalmazzuk. Legyen tehát A olyan, a természetes számokra vonatkozó állítás, melyet minden természetes számra bizonyítani akarunk. A módszert a következő lépések levezetéséből áll:

Kezdő lépés – igazoljuk, hogy 0-ra teljesül A, azaz az aritmetikában bizonyítható A(0)
Indukciós lépés – feltesszük, hogy egy tetszőleges n természetes számra igaz és bebizonyítjuk, hogy ezesetben a rákövetkezőjére, azaz n + 1-re is igaz lesz A. Tehát belátjuk, hogy az aritmetikában tétel a (∀n)(A(n) ⇒ A(n+1)) kijelentés.

Mindezek után kijelenthetjük, hogy minden természetes számra fennáll A, azaz az aritmetikában (∀n)A(n) tétel.

$\frac{\mathfrak{Ari}:\mathbf{A}(0),\;(\forall n)(\mathbf{A}(n)\Rightarrow\mathbf{A}(n+1))}{\mathfrak{Ari}:(\forall n)\mathbf{A}(n)}$

$\mbox{ }_{\mathfrak{Ari}}$ az aritmetika elméletét jelöli.

[szerkesztés] Végtelen leszállás – descente infinie

Fő szócikk: végtelen leszállás

A végtelen leszállás egyfajta indirekt bizonyítás, mely a természetes számok jólrendezési tulajdonságát használja ki. A jólrendezési tulajdonság kizárja, hogy legyen végtelen, szigorúan monoton csökkenő, természetes számokból álló sorozat. Tegyük fel, hogy igazolni akarjuk az A természetes számokra vonatkozó kijelentést. A bizonyítási eljárás pedig a következő.

Igazoljuk, hogy tetszőleges olyan n természetes szám, amire nem teljesül A, létezik egy m < n természetes szám is, amire szintén nem teljesül A.

Ez elegendő alapot szolgáltat arra, hogy állíthassuk: A minden természetes számra igaz. Ugyanis ha lenne olyan szám, amire nem teljesül A, akkor rekurzióval definiálhatnán egy végtelen, szigorúan monoton csökkenő sorozatot, ami azonban nem létezhet.

$\frac{\mathfrak{Ari}:(\forall n)(\neg\mathbf{A}(n)\Rightarrow(\exists m)(m<n \wedge\neg\mathbf{A}(m))}{\mathfrak{Ari}:(\forall n)\mathbf{A}(n)}$

A végtelen leszállás alkalmazható minden jólrendezett halmazra is, hiszen jólrendezett halmazban nem létezhet végtelen leszálló transzfinit sorozat.

[szerkesztés] Skatulyaelv

Fő szócikk: skatulyaelv

Ha van n darab hely (skatulya), ahol elhelyzünk n+1 tárgyat (golyót), akkor lesz olyan hely, ahol legalább 2 golyót találunk.

Másként n elem n+1-ed rendű ismétléses kombinációi mind olyanok, hogy legalább egy elem biztos ismétlődik.

Ahhoz, hogy a logika nyelvén megfogalmazzuk a skatulya elvet, numerikus kvantivfikációt kell használnunk, azaz, hogy létezik legalább k darab dolog, ami teljesít egy A tulajdonságot:

$(\exists_{k}\, x)\mathbf{A}(x)$

A másik, amit alkalmaznunk kell, az a kizáró vagy, azaz a 'vagy ..., vagy ...' logikai művelete:

$\mathbf{A}\oplus\mathbf{B}$

Eszerint a következtetési szabály ezesetben az, hogy n darab A₁, A₂,..., A_n kijelentés esetén:

$\frac{\mathcal{T}:(\forall x)(\bigvee\limits_{i=1}^n\mathbf{A}_i(x)\Rightarrow\bigoplus\limits_{i=1}^n\mathbf{A}_i(x)), (\exists_{n+1}\,x)\bigvee\limits_{i=1}^n\mathbf{A}_i(x)}{\mathcal{T}:\bigvee\limits_{i=1}^n(\exists_{2}\,x)\mathbf{A}_i(x)}$

Ebben az értelemben a skatulyaelv nem konstruktív, hiszen nem tudjuk – általában nem tudhatjuk –, hogy a fenti konklúzióbeli diszjunkció mely tagjai teljesülnek. Másrész viszont mivel véges sok doboz van, egy egyszerű véges eljárással – a dobozok felnyitásával – megállapíthatjuk, hogy melyik dobozban van legalább két golyó.

Lásd még: Elemi kombinatorika

A lap eredeti címe "http://hu.wikipedia.org../../../m/a/t/Matematikai_bizony%C3%ADt%C3%A1s.html"

Kategória: Matematika