„Matematikai bizonyítás” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló |
a kisebb formai javítások |
||
1. sor:
Egy '''matematikai bizonyítás''' a [[matematika]] [[tudomány]]ában érvényesnek vagy [[igaz]]nak 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 [[A matematikafilozófia története#Az újkor matematikafilozófusai (XVI–XVIII. sz.)|módszert]], melyet [[Descartes]] fejtett ki először az ''Értekezések a módszerről'' című könyvében, és melyet 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étel'''eknek nevezik.
== 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:
:<math>\sqrt[4]{4}<\sqrt[3]{3}</math>
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 <math>\mbox{ }_{\Uparrow}</math> 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 <math>x</math> számra <math>\mbox{ }_{\sqrt[4]{x^{4}}\;=\;x}</math>. Ha tehát <math>x=4</math>, akkor teljesül <math>\mbox{ }_{\left(\sqrt[4]{4}\right)^4=4}</math>. Itt tehát egy általános igazság speciális esetével állunk szemben.
<center>
{|
|-
| <math>\sqrt[4]{4}<\sqrt[3]{3}</math>
|
|-
|<math>\Uparrow</math>
|<math>\Leftarrow</math>
|A pozitív <math>x</math>-ekre értelmezett 12. gyök <math>\mbox{ }_{\sqrt[12]{x^{12}}\;=\;x}</math> azonossága miatt
23. sor:
|
|-
|<math>\Uparrow</math>
|<math>\Leftarrow</math>
|A pozitív számok halmazán értelmezett <math>\mbox{ }_{x\mapsto\sqrt[12]{x}}</math> függvény szigorú monotonitása miatt, azaz ha <math>0<x<y</math>, akkor <math>\mbox{ }_{\sqrt[12]{x}<\sqrt[12]{y}}</math>
|-
30. sor:
|
|-
|<math>\Uparrow</math>
|<math>\Leftarrow</math>
|A hatványozás <math>(a^n)^k=a^{nk}</math> azonossága, továbbá a szorzás kommutativitása miatt
|-
37. sor:
|
|-
|<math>\Uparrow</math>
|<math>\Leftarrow</math>
|A 4. és 3. gyök definíciója miatt: <math>\mbox{ }_{\sqrt[4]{x^{4}}\;=\;x}</math> és <math>\mbox{ }_{\sqrt[3]{x^{3}}\;=\;x}</math> pozitív <math>x</math>-re.
|-
44. sor:
|
|}
</center>
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.
<big><big><big>[[Quod erat demonstrandum|■]]</big></big></big>
61. sor:
:[[sorozat (matematika)|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 ''[[#bizonyítási módszerek|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 logika|matematikai logikában]] ennek az eljárásnak a formális megfogalmazásaként definiálják a formális rendszerbeli levezetést.
=== Kritikák ===
86. sor:
:<math>\frac{\;\mathcal{T}:\mathbf{A}\;}{\mathcal{T}:\mathbf{B}}</math>
A matematikai állítások (legalapvetőbb, de már értelmes) logikai szerkezete a következő lehet:
:{|
|-
| diszjunkció (alternáció)
94. sor:
| ' '''A''' vagy '''B''' '
|-
| konjunkció
|<math>\mathbf{A}\wedge\mathbf{B}</math>
| ' '''A''' és '''B''' '
|-
| implikáció (kondicionális)
|<math>\mathbf{A}\Rightarrow\mathbf{B}</math>
|' ha '''A''', akkor '''B''' '
|-
| negáció
|<math>\neg\mathbf{A}</math>
|' nem '''A''' '
|-
| univerzális kvantifikáció
|<math>(\forall x)\mathbf{A}(x)</math>
|' minden ''x''-re '''A''' '
|-
| egzisztenciális kvantifikáció
116. sor:
| egyenlőség (azonosság)
|<math>t=s\,</math>
|' ''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óma|axiómák]] adják meg.
137. sor:
|- align="center"
| '''A''' ⇒ '''B'''
| <math>\frac{\mathcal{T}\cup\{\mathbf{A}\}:\mathbf{B}}{\mathcal{T}:\mathbf{A}\Rightarrow\mathbf{B}}\;\;(\Rightarrow\mathrm{be}) </math>
| '''A''' ⇒ '''B''' levezethető, ha axiómának tekintve '''A'''-t (tehát feltéve '''A'''-t) ebből levezethető '''B''' (''[[dedukciótétel]]'')
|- align="center"
| (∀''x'')'''A'''
| <math>\frac{\mathcal{T}:\mathbf{A}(x)}{\mathcal{T}:(\forall x)\mathbf{A}(x)} \;\;(\forall\mathrm{be})</math>
| (∀''x'')'''A''' levezethető, ha az '''A'''(''x'') nyitott kifejezés levezethető (''[[univerzális generalizáció]]'')
|- align="center"
149. sor:
|- align="center"
| (∃''x'')'''A'''
| <math>\frac{\mathcal{T}:\mathbf{A}(t)}{\mathcal{T}:(\exists x)\mathbf{A}(x)} \;\;(\exists\mathrm{be})</math>
| (∃''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ő
|}
156. sor:
=== 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 <math>\mbox{ }_{\mathcal{T}}</math> elméletről az '''A'''-val, mint axiómával bővített <math>\mbox{ }_{\mathcal{T}\cup\{\mathbf{A}\}}</math> elméletre. Ebben bebizonyítjuk a '''B''' kijelentést, tehát belátjuk, hogy <math>\mbox{ }_{\mathcal{T}\cup\{\mathbf{A}\}\;:\;\mathbf{B}}</math>. Majd a bizonyítást ezzel zárjuk:
164. sor:
== Reductio ad absurdum ==
A ¬ '''A''' kijelentés levezethetőségének feltételét a ''[[reductio ad absurdum]]'' 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
:<math>\mathcal{T}\;:\;\mathbf{C}\!\wedge\!\neg\mathbf{C}</math>
:{|class="wikitable"
174 ⟶ 173 sor:
|- align="center"
| ¬ '''A'''
| <math>\frac{\mathcal{T}\cup\{\mathbf{A}\}:\mathbf{C}\!\wedge\!\neg\mathbf{C}}{\mathcal{T}:\neg\mathbf{A}} \;\;(\neg\mathrm{be})</math>
| 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ó kijelenté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:
187 ⟶ 186 sor:
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:
199 ⟶ 198 sor:
|- align="center"
| '''A'''
| <math>\frac{\mathcal{T}:\mathbf{C}\!\wedge\!\neg\mathbf{C}}{\mathcal{T}:\mathbf{A}}\;\;(\neg\mathrm{ki})</math>
| Azaz, ha az az elmélet ellentmondásos, akkor akármilyen '''A''' kijelentés levezethető belőle.
(''[[ex falso quodlibet]]'')
|}
209 ⟶ 208 sor:
:''Lásd még: [[konstruktív bizonyítás]]''
Az ex falso quodlibet szabályával elérkeztünk a '''konstruktív bizonyítás'''okhoz. 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ű.
:{|class="wikitable"
! (∧ki)
217 ⟶ 216 sor:
| <math>\frac{\mathcal{T}:\mathbf{A}\wedge\mathbf{B}}{\mathcal{T}:\mathbf{A}},
\frac{\mathcal{T}:\mathbf{A}\wedge\mathbf{B}}{\mathcal{T}:\mathbf{B}}</math>
| <math>\cfrac{\mathcal{T}:\mathbf{A}\Rightarrow\mathbf{B},\;\mathcal{T}:\mathbf{A}}{\mathcal{T}:\mathbf{B}}</math>
|<math>\frac{\;\mathcal{T}:(\forall x)\mathbf{A}(x) }{\mathcal{T}:\mathbf{A}(t)}</math>
|}
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ármilyen ''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''<sub>1</sub>)∧'''A'''(''t''<sub>2</sub>)∧'''A'''(''t''<sub>3</sub>)∧… kifejezésre, ahol ''t''<sub>1</sub>, ''t''<sub>2</sub>, ''t''<sub>3</sub>, … 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 egzisztenciális kifejezést ''szelektív''nek nevezzük, azt a bizonyítást, ami (∃''x'')'''A'''-t bizonyítja pedig '''konstruktív egzisztenciabizonyítás'''nak. [[Gödel]] bebizonyította, hogy ha nincsenek az axiómák között diszjunkciók vagy egzisztenciaaxió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:
237 ⟶ 236 sor:
''Ö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 abszurdum]]ot 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)
== 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 frizsiderbe és azt találtuk, 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.)
302 ⟶ 301 sor:
| Kontrapozíció
| <math>\frac{\mathcal{T}: \neg\mathbf{B}\Rightarrow \neg\mathbf{A}}{\mathcal{T}:\mathbf{A}\Rightarrow\mathbf{B}}</math>
| Ha nem '''B''', akkor nem '''A''', tehát ha (mégis) '''A''', akkor lehetetlen, hogy ne legyen '''B'''.
|- align="center"
| Modus tollens
316 ⟶ 315 sor:
== 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.
=== Teljes indukció ===
{{
Ha egy tulajdonságot minden természetes számra bizonyítani akarunk, akkor legtöbb esetben a teljes indukció valamely variánsát 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)
330 ⟶ 329 sor:
=== Végtelen leszállás – descente infinie ===
{{
A végtelen leszállás egyfajta indirekt bizonyítás, mely a természetes számok [[jólrendezés]]i 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, hogy az '''A''' kijelentés az összes természetes számra igaz. Ekkor a bizonyítási eljárás 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'''.
342 ⟶ 341 sor:
=== 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.
348 ⟶ 347 sor:
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 skatulyaelvet, numerikus kvantifikációt kell használnunk, azaz, hogy létezik ''legalább'' ''k'' darab dolog, ami teljesít egy '''A''' tulajdonságot:
:<math>(\exists_{k}\, x)\mathbf{A}(x)</math>
A másik, amit alkalmaznunk kell, az a ''kizáró vagy'', azaz a 'vagy …, vagy …' logikai művelete:
:<math>\mathbf{A}\oplus\mathbf{B}</math>
Eszerint a következtetési szabály ez esetben az, hogy ''n'' darab '''A'''<sub>1</sub>, '''A'''<sub>2</sub>,…, '''A'''<sub>n</sub> kijelentés esetén:
:<math>\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)} </math>
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észt 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#skatulyaelv|Elemi kombinatorika]]
362 ⟶ 361 sor:
{{Link FA|cs}}
{{Link FA|eo}}
[[en:Mathematical proof]]
[[af:Bewys]]
| |||