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 A matematikai bizonyítás fogalma
2 Formális és informális bizonyítás
- 2.1 Kritikák
- 2.2 Szociálkonstruktivizmus
3 Történeti áttekintés
4 Bizonyítási módszerek
5 Direkt bizonyítás
- 5.1 Dedukciótétel
6 Redukció ad abszurdum
7 Konstruktív bizonyítás
8 Nemkonstruktív bizonyítás – a kizárt harmadik elve
9 Speciális matematikai bizonyítási módszerek

[szerkesztés] A matematikai bizonyítás fogalma

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. Tekintsük példaként a következő állítást:

$\sqrt[4]{4}<\sqrt[3]{3}$

A kijelentés igazságát a következő gondolatmenettel igazolhatjuk.

Bizonyítás. Kiindulunk a 64 < 81 kétségbevonhatatlan matematikai igazságból (legalul) és kimutatjuk, hogy az állítás igaz. Közben - ezek a $\mbox{ }_{\Uparrow}$ jelű közbevetések – már igazoltnak tekinthető matematikai tételekre hivatkozunk. Például a legalsó mozzanatnál felhasználjuk, hogy tetszőleges pozitív $x$ számra $\mbox{ }_{\sqrt[4]{x^{4}}\;=\;x}$ . Ha tehát $x = 4$ , akkor teljesül $\mbox{ }_{\left(\sqrt[4]{4}\right)^4=4}$ . Itt tehát egy általános igazság speciális esetével állunk szemben.

$\sqrt[4]{4}<\sqrt[3]{3}$
$\Uparrow$	$\Leftarrow$	A pozitív $x$ -ekre értelmezett 12. gyök $\mbox{ }_{\sqrt[12]{x^{12}}\;=\;x}$ azonossága miatt
$\sqrt[12]{\left(\sqrt[4]{4}\right)^{12}}<\sqrt[12]{\left(\sqrt[3]{3}\right)^{12}}$
$\Uparrow$	$\Leftarrow$	A pozitív számok halmazán értelmezett $\mbox{ }_{x\mapsto\sqrt[12]{x}}$ függvény szigorú monotonitása miatt, azaz ha $0 < x < y$ , akkor $\mbox{ }_{\sqrt[12]{x}<\sqrt[12]{y}}$
$\left(\sqrt[4]{4}\right)^{12}<\left(\sqrt[3]{3}\right)^{12}$
$\Uparrow$	$\Leftarrow$	A hatványozás $(a n) k = a n k$ azonossága, továbbá a szorzás kommutativitása miatt
$\left(\left(\sqrt[4]{4}\right)^4\right)^3<\left(\left(\sqrt[3]{3}\right)^3\right)^4$
$\Uparrow$	$\Leftarrow$	A 4. és 3. gyök definíciója miatt: $\mbox{ }_{\sqrt[4]{x^{4}}\;=\;x}$ és $\mbox{ }_{\sqrt[3]{x^{3}}\;=\;x}$ pozitív $x$ -re.
$64=4^3<3^4=81\,$

Tehát igaz állításból (64 < 81 és a felhasznált műveleti szabályok) igaz következtetésekkel eljutottunk a kívánt állításig. ■

Egy matematikai bizonyítás végét általában a ■ szimbólummal jelölik.

A legalsó sorból a következőre tehát így jutottunk el: ha a=c és b=d és a<b, akkor c<d, de a=c és b=d, tehát c<d. Vagyis adott egy „ha A, akkor B” alakú általános érvényű szabály. Tudjuk, hogy jelen esetben A, azaz a feltétel igaz, ezalapján tehát kijelenthetjük, hogy B, azaz a konklúzió is igaz. Az ilyen alakú gondolatmenetek láncolatát nevezzük (logikai) bizonyításnak.

Meg kell jegyeznünk, hogy az előbbi bizonyításban ugyan az igazság „felfelé áramlik” (az alsó állításról az eggyel fenntebbire öröklődik az igaz minősítés), de az ötlet, a gondolat „lefelé halad”. A fő kérdés, hogy mi biztosítaná az állítás igazságát. Erre a kérdésre keresünk választ, és az első gondolat, hogy emeljük a 4 és 3 legkisebb közös többszöröse azaz 12-nek hatványára az egyenlőtlenséget, ezzel biztosítva, hogy összehasonlítható legyen a két szám. Ha ez utóbbi igaz lenne, akkor az állítás is. A bizonyítások kiötlésével, pszichológiájával foglalkozó témakör az úgy nevezett heurisztika, melynek fontosságára többek közt Pólya György hívta fel a figyelmet.

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

Az, hogy miből származik a tételek igazsága – jobban mondva bizonyítottsága, bizonyíthatósága – azt a matematikusok közösségének 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.

[szerkesztés] Kritikák

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.

Brouwer és követői az intuicionisták arra mutatnak rá, hogy a matematikai tételek bizonyítása emberi tevékenység. Nem elég elvi úton igazolni, hogy létezik egy, a fenti értelemben vett bizonyításnak nevezett véges formulasorozat. Egy bizonyítás csak akkor érvényes, ha ezt a formulasorozatot már valaki végiggondolta – szemben például Gödel teljeségi tételével, melyben csak a bizonyathatóságok vannak igazolva de nem bizonyítottságok. A matematikai tételek csak akkor érvényesek, ha bizonyításaik közvetlen kapcsolatban vannak a matematika alapintuíciójával a természetes számokkal elméletével.

[szerkesztés] Szociálkonstruktivizmus

Lakatos Imre sokkal messzebbre megy állásfoglalásában. Szerinte egy matematikai bizonyítás elvégzése esetén a fent vázolt formális eljárás kivitelezése csak a feladat töredéke. Egy tételt bizonyítani sokkal több mint a levezetését megalkotni, éspedig bizonytani 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 a levezetések megtalálása jelenti, hanem olyan elmélet megalkotá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 matematikai állítások (legalapvetőbb, de már értelmes) logikai szerkezete a következő lehet:

diszjunkció (alternáció)	$\mathbf{A}\vee\mathbf{B}$	' A vagy B '
konjunkció	$\mathbf{A}\wedge\mathbf{B}$	' A és B '
implikáció (kondicionális)	$\mathbf{A}\Rightarrow\mathbf{B}$	' ha A, akkor B '
negáció	$\neg\mathbf{A}$	' nem A '
univerzális kvantifikáció	$(\forall x)\mathbf{A}(x)$	' minden x-re A '
egzisztenciális kvantifikáció	$(\exists x)\mathbf{A}(x)$	' van olyan x, ami A '
egyenlőség (azonosság)	$t=s\,$	' t egyenlő (azonos) s-sel '

Ezeken kívül a matematika nagyon sok nemlogikai, „szakmai” kifejezést is tartalmaz, például a részhalmaz (⊆), eleme (∈), oszthatóság (.|.), ... szimbólumokat. Ezekkel is lehet mondatokat képezni, melyek értelmét vagy ezek definíciója, vagy a rájuk vonatkozó axiómák adják meg.

Az alábbiakban összefoglaljuk, hogy milyen elevezetési szabályok biztosítják ezeknek az állításoknak a helyességét.

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élkedett 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ás

Pozitív egy kijelentés, ha nincs benne tagadás (¬). Ezek levezetése alkotja a direkt bizonyítások mintapéldányait. Az alábbi szabályok együttesét a lentebb említendő, hozzájuk tartozó kiküszöbölési szabályokkal együtt pozitív logikának nevezzük.

Állítás	Az állítás feltétele	Megjegyzés
A ∧ B	$\frac{\mathcal{T}:\mathbf{A},\mathcal{T}:\mathbf{B}}{\mathcal{T}:\mathbf{A}\wedge\mathbf{B}}\;\;(\wedge\mathrm{be})$	A ∧ B levezethető, ha A is és B is levezethető
A ⇒ B	$\frac{\mathcal{T}\cup\{\mathbf{A}\}:\mathbf{B}}{\mathcal{T}:\mathbf{A}\Rightarrow\mathbf{B}}\;\;(\Rightarrow\mathrm{be})$	A ⇒ B levezethető, ha axiómának tekintve A-t (tehát feltéve A-t) ebből levezethető B (dedukciótétel)
(∀x)A	$\frac{\mathcal{T}:\mathbf{A}(x)}{\mathcal{T}:(\forall x)\mathbf{A}(x)} \;\;(\forall\mathrm{be})$	(∀x)A levezethető, ha az A(x) nyitott kifejezés levezethető (univerzális generalizáció)
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}} \;\;(\vee\mathrm{be})$	A ∨ B levezethető, ha vagy A, vagy B levezethető
(∃x)A	$\frac{\mathcal{T}:\mathbf{A}(t)}{\mathcal{T}:(\exists x)\mathbf{A}(x)} \;\;(\exists\mathrm{be})$	(∃x)A levezethető, ha az A(x) nyitott kifejezésben az x helyére valamely t dolgot helyettesítve az A(t) kijelentés levezethető

Ezeket a szabályokat a logikai jelek bevezetési szabályának nevezik, erre utal a (jel be) jelölés.

[szerkesztés] Dedukciótétel

Az egyik legtipikusabb direkt bizonyítási lépés a dedukciótétel, mely az informális levezetések során a következőképpen jelenik meg. Egy ' ha A, akkor B ' feltételes állítást akarunk bizonyítani. Ekkor azt mondjuk, hogy

„tegyük fel, hogy A igaz”

ezzel azt jelezzük, hogy az A állítást úgy fogjuk tekinteni, mintha igaz jobban mondva axióma lenne. A formális elméletben ez azt jelenti, hogy áttérünk a $\mbox{ }_{\mathcal{T}}$ elméletről az A-val, mint axiómával bővített $\mbox{ }_{\mathcal{T}\cup\{\mathbf{A}\}}$ elméletre. Ebben bebizonyítjuk a B kijelentést, tehát belátjuk, hogy $\mbox{ }_{\mathcal{T}\cup\{\mathbf{A}\}\;:\;\mathbf{B}}$ . Majd a bizonyítást ezzel zárjuk:

„tehát feltéve A-t, teljesül B, vagyis ha A, akkor B”.

Ezzel jelezzük, hogy a dedukciótételt alkalmazzuk és levezettük ' ha A, akkor B '-t.

[szerkesztés] Redukció ad abszurdum

A ¬ A kijelentés levezethetőségének feltételét a redukció ad abszurdum vagyis a lehetetlenre való visszavezetés szabálya adja meg. Ez az indirekt bizonyítások központi lépése. Alkalmazásánál felhasználjuk az ellentmondásos elmélet illetve az ellentmondás fogalmát. Ellentmondásosnak nevezünk egy T elméletet, ha létezik olyan C kijelentés, hogy a C ∧ ¬C (C és nem C) állítás levezethető T-ben, azaz ha

$\mathcal{T}\;:\;\mathbf{C}\!\wedge\!\neg\mathbf{C}$

Állítás	Az állítás feltétele	Megjegyzés
¬ A	$\frac{\mathcal{T}\cup\{\mathbf{A}\}:\mathbf{C}\!\wedge\!\neg\mathbf{C}}{\mathcal{T}:\neg\mathbf{A}} \;\;(\neg\mathrm{be})$	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, akkor ¬A levezethető. (redukció ad abszurdum)

A szabály az informális levezetésekben a következőképpen működik. Egy ¬A alakú tagadó kijlentést akarunk bizonyítani. Ekkor azt mondjuk, hogy

„tegyük fel, hogy A mégis igaz”

ezzel azt juttatjuk kifejezésre, hogy áttérünk arra az elméletre, melyben A axióma ( T U {A} ). Ebből a feltételezésből ellentmondásra jutunk, azaz találunk egy olyan kijelentést, mely a negációjával együtt levezethető a bővítésben. Majd azt mondjuk:

„lehetetlen tehát, hogy A igaz legyen, így ¬A igaz”

amivel azt juttatjuk kifejezésre, hogy a redukció ad abszurdum elvt kívánjuk használni és T-ből ¬A -ra következtetünk.

A pozitív kijelentésekre vonatkozó levezetési szabályokat ezzel kiegészítve kapjuk a (negatív kijelentések kezelésére is alkalmas) minimális logikát. Ebben érvényes az a tétel, hogy ellentmondásos elméletben minden negatív kijelentés levezethető:

ha T ellentmondásos, akkor ¬A levezethető

hiszen tetszőleges A-ra, ha T ellentmondásos, akkor T U {A} is az és így T-ből következik ¬A.

Ezt a tételt tetszőleges kijelentésre is megkövetelhetjük:

ha T ellentmondásos, akkor A levezethető

ezt az ex falso quodlibet vagyis a „hamisból minden következik” szabályát:

Állítás	Az állítás feltétele	Megjegyzés
A	$\frac{\mathcal{T}:\mathbf{C}\!\wedge\!\neg\mathbf{C}}{\mathcal{T}:\mathbf{A}}\;\;(\neg\mathrm{ki})$	Azaz, ha az az elmélet ellentmondásos, akkor akármilyen A kijelentés levezethető belőle. (ex falso quodlibet)

A szabály hasznavehetetlenné teszi az ellentmondásos elméleteket, hiszen ezekben minden állítás egyszerre cáfolható és bizonyítható is. (Minden és mindennek az ellenkezője is igaz). A szabály tekinthető a ¬ jel kiküszöbölési szabályának.

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

Lásd még: konstruktív bizonyítás

Az ex falso quodlibet szabályával elérkeztünk a konstruktív bizonyításokhoz. A bizonyítások során arra is szükségünk van, hogy összetett kifejezésekből másokra következtessünk. Az A ∧ B, A ⇒ B, (∀x)A alakú kijelentéseknél ez egyszerű.

(∧ki)	(⇒ki)	(∀ki)
$\frac{\mathcal{T}:\mathbf{A}\wedge\mathbf{B}}{\mathcal{T}:\mathbf{A}}, \frac{\mathcal{T}:\mathbf{A}\wedge\mathbf{B}}{\mathcal{T}:\mathbf{B}}$	$\cfrac{\mathcal{T}:\mathbf{A}\Rightarrow\mathbf{B},\;\mathcal{T}:\mathbf{A}}{\mathcal{T}:\mathbf{B}}$	$\frac{\;\mathcal{T}:(\forall x)\mathbf{A}(x) }{\mathcal{T}:\mathbf{A}(t)}$

Tehát ha A ∧ B levezethető, akkor mind A, mind B levezethető. Ha A ⇒ B levezethető és A is, akkor B is. Végül, ha (∀x)A(x) levezethető, akkor akármlyen t-t helyettesítve x helyére A(t) levezethető. Megjegyezzük, hogy a 'minden' kvantor tekinthető végtelen sok tagú konjunkciónak is, ha azt gondoljuk, hogy csak megszámlálhatóan sok dolog (szám) létezik. Ekkor (∀x)A(x)-re gondolhatunk úgy is, mint valamiféle A(t₁)∧A(t₂)∧A(t₃)∧... kifejezésre, ahol t₁, t₂, t₃, ... az összes dolgot jelöli.

Furcsa, de általában egy matematikai bizonyításban nem igaz az a következtetés, hogy ha A ∨ B bizonyítható, akkor vagy 'A bizonyítható, vagy B bizonyítható, illetve, hogy ha bizonyítható (∃x)A, akkor van olyan t dolog, amire bizonyítható A(t). Ha mégis ez a helyzet, akkor a 'vagy'-ot illetve az egziszetnciális kifejezést szelektívnek nevezzük, azt a bizonyítást, ami (∃x)A-t bizonyítja pedig konstruktív egzisztenciabizonyításnak. Gödel bebizonyította, hogy ha nincsenek az axiómák között diszjunkciók vagy egzisztenciaxiómák, akkor a konstruktív bizonyításokban a diszjunktív és egzisztenciális állítások mindig szelektívek.

Ezen szabályok helyett a kevésbé éles következő kiküszöbölési következtetéseket fogalmazták meg:

(∨ki)	(∃ki)
$\frac{\mathcal{T}\!\cup\!\{\mathbf{A}\}\!:\!\mathbf{C},\,\mathcal{T}\!\cup\!\{\mathbf{B}\}\!:\!\mathbf{C},\,\mathcal{T}:\mathbf{A}\vee\mathbf{B}}{\mathcal{T}:\mathbf{C}}$	$\frac{\mathcal{T}:(\exists x)\mathbf{A}(x), \mathcal{T}\cup\{\mathbf{A}(x)\}:\mathbf{C}}{\mathcal{T}:\mathbf{C}}$

A (∨ki) szabályt az esetszétválasztás szabályának nevezik. Megjegyezzük, hogy a (∃x)A tekinthető végtelen sok tagú diszjunkciónak is, ha azt gondoljuk, hogy csak megszámlálhatóan sok dolog (szám) létezik. Ekkor (∃x)A(x)-re gondolhatunk úgy is, mint valamiféle A(t₁)∨A(t₂)∨A(t₃)∨... kifejezésre, ahol t₁, t₂, t₃, ... az összes dolgot jelöli. Természetesn nem tudható, hogy melyik dolog az, amelyik teljesíti az A tulajdonságot, éppen ez okozza a konstruktivitás problémáját.

Összefoglalva.

A direkt bizonyítás (pozitív kijelentésekre) szabályai:

GP = (∧be)(∧ki)(∨be)(∨ki)(⇒be)(⇒ki)(∀be)(∀ki)(∃be)(∃ki)

A minimális következtetések szabályai ehhez a redukció ad abszurdumot teszik:

GM = GP + (¬be)

A konstruktív (vagy intuicionista) bizonyítás ehhez a hamisból minden következik sémáját veszi fel:

GI = GM + (¬ki)

[szerkesztés] Nemkonstruktív bizonyítás – a kizárt harmadik elve

Az A ∨ B esetén általában nem igaz az, hogy ha levezethető A ∨ B, akkor vagy A levezethető, vagy B levezethető. Erre egy nevezetes eset a következő. Az

A ∨ ¬A (TND)

állítás nem azért teljesül, mert levezettük akár A-t akár ennek tagadását, hanem egyszerűen elemi logikai intuíciónk mondatja velünk, hogy a vagy A, vagy nem A kijelentés logikai igazság – ez a klasszikus logikában a kizárt harmadik elve vagy a tertium non datur elve. (Például a „vagy van joghurt a hűtőben, vagy nincs” mondat nem azért igaz, mert benéztünk a fridzsiderbe és azt találuk, hogy van illetve, hogy nincs joghurt, hanem ez egy pusztán elvi okokból érvényesnek tartott kijelentés. Természetesen ez egy olyan episztemológiai kérdés, mely vita tárgyát képezheti.)

Az A ∨ ¬A kijelentés annyira evidens, hogy új szabálynak vehetnénk fel. Hogy azonban mégis a levezetésekben használt módon tegyék ezt, egy ekvivalens megfogalmazást választottak. Ez a kettős tagadás törlésének elve:

A kettős negáció törlése (¬¬)
$\frac{\mathcal{T}:\neg\neg\mathbf{A}}{\mathcal{T}:\mathbf{A}}$

Szemléletes megfogalmazásban: ha nem igaz, hogy nem igaz, akkor igaz. Ezzel együtt sem a diszjunktív, sem az egzisztenciális kifejezések nem lesznek szelektívek. Lássuk a (TND) levezetését és azt, hogy ez valóban nem lesz konstrutív bizonyítás! Először ¬¬(A ∨ ¬A)-t látjuk be redukció ad abszurdummal, majd töröljük a kettős tagadást:

$\underline{ \{\neg(\mathbf{A}\vee\neg\mathbf{A})\}\cup\{\;\mathbf{A}\}\;:\;\mathbf{A}}_{\;(\vee\mathrm{be})}$

$\underline{\{\neg(\mathbf{A}\vee\neg\mathbf{A})\}\cup\{\;\mathbf{A}\}\;:\;\mathbf{A}\vee\neg\mathbf{A} }_{\;(\wedge\mathrm{be})}$

$\underline{\{\neg(\mathbf{A}\vee\neg\mathbf{A})\}\cup\{\;\mathbf{A}\}\;:\;(\mathbf{A}\vee\neg\mathbf{A})\wedge\neg(\mathbf{A}\vee\neg\mathbf{A})}_{\;(\mathrm{RA})}$

$\underline{ \{\neg(\mathbf{A}\vee\neg\mathbf{A})\}\;:\;\neg\mathbf{A}}_{\;(\vee\mathrm{be})}$

$\underline{ \{\neg(\mathbf{A}\vee\neg\mathbf{A})\}\;:\;\mathbf{A}\vee\neg\mathbf{A}}_{\;(\wedge\mathrm{be})}$

$\underline{ \{\neg(\mathbf{A}\vee\neg\mathbf{A})\}\;:\;(\mathbf{A}\vee\neg\mathbf{A})\wedge(\mathbf{A}\vee\neg\mathbf{A})}_{\;(\mathrm{RA})}$

$\underline{\;\neg\neg(\mathbf{A}\vee\neg\mathbf{A})}_{\;(\mathrm{\neg\neg})}$

$\mathbf{A}\vee\neg\mathbf{A}$

A szabály elfogadásával minden állítás indirekten is igazolható lesz, az ellentmondásra való visszavezetés korlátlanul használható:

Az indirekt bizonyítás elve
$\frac{\mathcal{T}\cup\{\neg\mathbf{A}\}:\mathbf{C}\!\wedge\!\neg\mathbf{C}}{\mathcal{T}:\mathbf{A}}$

Szintén korlátlanul lépnek érvénybe a de Morgan-azonosságok és a többi tagadó állítás:

$\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)$

Néhány további negációt is tartalmazó levezetési lépés.

Á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.

Így kapjuk a klasszikus logika bizonyítási szabályait, vagyis a KL = GI + (¬¬) rendszert.

[szerkesztés] Speciális 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ánk 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