Důkaz kontradikcí

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 17. března 2021; kontroly vyžadují 65 úprav .

Důkaz „protikladem“ ( lat. conflictio in contrarium ), neboli apagogický nepřímý důkaz [1] , je druh důkazu, při kterém se „důkaz“ určitého úsudku ( důkazní teze ) provádí prostřednictvím vyvrácení negace. tento rozsudek - protiklad [2] . Tato metoda důkazu je založena na pravdivosti zákona dvojí negace v klasické logice .

Tato metoda je velmi důležitá pro matematiku , kde existuje mnoho tvrzení, které nelze dokázat jinak [3] .

Schéma důkazu

Důkaz kontradikcí je schéma:

{\dfrac {\begin{matrix}\left[{\mathcal {\neg A}}\right]&&\left[{\mathcal {\neg A}}\right]\\{\mathcal {B }}&&{\mathcal {\neg B}}\end{matrix}}{\mathcal {A}}}}.

Formalizuje metodu důkazu kontradikcí.

Důkaz tvrzení se provádí následovně. Nejprve se předpokládá, že tvrzení je nepravdivé, a pak se dokáže, že za takového předpokladu by bylo nějaké tvrzení pravdivé , což je zjevně nepravdivé. ${\mathcal {A}}$ ${\mathcal {A}}$ ${\mathcal B}$

Z definice implikace vyplývá , že je-li nepravda, pak je vzorec pravdivý právě tehdy, je-li nepravdivý, proto je výrok pravdivý. ${\mathcal B}$ ${\mathcal {\neg A\Rightarrow B))$ ${\mathcal {\neg A))$ ${\mathcal {A}}$

Výsledný rozpor ukazuje, že původní předpoklad byl chybný, a proto je výrok pravdivý , což je podle zákona dvojí negace ekvivalentní výroku . ${\mathcal {\neg \neg A))$ ${\mathcal {A}}$

V intuicionistické logice není akceptován důkaz kontradikcí, stejně jako nefunguje zákon vyloučeného středu [1] .

Poznámka . Toto schéma je podobné jinému - schématu důkazu redukcí do absurdity . V důsledku toho jsou často zmatení. Přes některé podobnosti však mají odlišný tvar. Navíc se liší nejen formou, ale i podstatou a tato odlišnost je zásadní povahy.

Srovnání metod důkazu od rozporu a redukce k absurditě

Myšlenka potřeby rozlišovat mezi těmito metodami ve výuce matematiky patří Felixovi Aleksandroviči Kabakovovi (1927–2008) , který tuto myšlenku uvedl do praxe za čtyřicet let působení na Matematické fakultě Moskevské státní pedagogické univerzity. .

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Přejděme ke srovnání odpovídajících metod dokazování.

Metoda důkazu kontradikcí je považována za známou metodu důkazu, ale často se termín „důkaz kontradikcí“ používá v různých významech a ve vztahu k různým metodám důkazu. Nejčastěji je metoda důkazu kontradikcí zaměňována s metodou důkazu redukcí do absurdna.

Písmena a will označují libovolné věty a písmeno označuje libovolné konečné množiny vět. Zápis použijeme k označení skutečnosti, že návrh je na základě návrhů oprávněný (prokázaný) nebo logicky vyplývá z . Vztah mezi množinami vět a větami budeme nazývat vztahem logického důsledku . ${\mathcal {A}}$ ${\mathcal {B}}$ ${\text{D))$ ${\text{D}}\Rightarrow {\mathcal {A}}$ ${\mathcal {A}}$ ${\text{D))$ ${\mathcal {A}}$ ${\text{D))$ $\Šipka doprava$

Důkaz kontradikcí je následující. Nechť je požadováno dokázat tvrzení na základě nějakých tvrzení (může se jednat o dříve dokázané věty, axiomy nebo předpoklady). Předpokládáme , že to není pravda, tedy připouštíme , a uvažováním na základě a vyvozujeme rozpor, tedy výrok a jeho negaci . Poté dojdeme k závěru, že předpoklad je nepravdivý, a proto je tvrzení pravdivé . Naše uvažování lze popsat pomocí následujícího neformálního uvažovacího schématu: ${\mathcal {A}}$ ${\text{D))$ ${\mathcal {A}}$ ${\mathcal {\neg A))$ ${\text{D))$ ${\mathcal {\neg A))$ ${\mathcal {B}}$ ${\mathcal {\neg B))$ ${\mathcal {A}}$

{\dfrac {{\text{D)),{\mathcal {\neg A))\Rightarrow {\mathcal {B)){\text{ a G)),{\mathcal {\neg A} }\Šipka doprava {\mathcal {\neg B))}{{\text{D))\Šipka doprava {\mathcal {A)))).

Právě toto schéma by se mělo nazývat schéma dokazující rozpor .

Situace se mění, když je nutné větu vyvrátit , jinými slovy, když věta, která má být dokazována, má tvar (ne ), tedy je záporná věta. ${\mathcal {A}}$ ${\mathcal {\neg A))$ ${\mathcal {A}}$

Například věta vypadá takto: "Neexistuje žádné racionální číslo, jehož druhá mocnina je 2." Dokazuje se to odvozením rozporu z předpokladu, že existuje racionální číslo, jehož druhá mocnina je 2.

Takže, abychom dokázali záporné tvrzení , předpokládáme, že , a vyvozujeme z toho určitý rozpor: a . Neformální schéma popisující takový průběh uvažování vypadá takto: ${\mathcal {\neg A))$ ${\mathcal {A}}$ ${\mathcal {B}}$ ${\mathcal {\neg B))$

{\dfrac {{\text{D)),{\mathcal {A}}\Rightarrow {\mathcal {B}}{\text{ a G)),{\mathcal {A}}\Rightarrow { \mathcal {\neg B))}{{\text{D))\Rightarrow {\mathcal {\neg A)))).

Toto neformální schéma uvažování se obvykle nazývá schéma důkazu redukcí na absurditu nebo redukce na absurditu (z latinského reductio ad absurdum).

Bohužel většinou v pedagogické praxi nerozlišují mezi těmito dvěma schématy, dvěma způsoby důkazu, nejčastěji je oba nazývají důkazem kontradikcí .

Zastavme se u důvodů, proč by tato schémata měla být ještě rozlišována.

Za prvé je zřejmé, že se tato schémata liší čistě graficky, což znamená, že uvažování podle těchto schémat se liší formou. Rozdíly stejné povahy, tedy alespoň ve formě, existují mezi větami a (nebo mezi větami a ). I když se na klasických pozicích domníváme, že tato tvrzení jsou ekvivalentní, skutečnost rozdílu ve formě je stále zřejmá. ${\mathcal {A}}$ ${\displaystyle {\mathcal {\neg {\neg A))))$ ${\mathcal {A\rightarrow B}}$ ${\mathcal {\neg A))\vee {\mathcal {B))$

Někomu se však takové rozlišení může zdát nedostatečné, nepřesvědčivé, aby mohl začít celý tento rozhovor. Přirozeně vyvstávají otázky: jsou tato schémata rovnocenná? jaký je mezi nimi rozdíl v praxi matematických důkazů; Je to rozdíl pouze ve formě nebo i v podstatě?

Abychom odpověděli na první otázku: „Jsou schémata conflictio in contrarium a reductio ad absurdum ekvivalentní? možné na neformální úrovni, aniž by bylo nutné přejít na cestu budování formálního logického systému. Spojení mezi těmito schématy je stanoveno následujícím prohlášením.

❗ SCHVÁLENÍ . Schéma důkazu kontradikcí

{\dfrac {{\text{D)),{\mathcal {\neg A))\Rightarrow {\mathcal {B)){\text{ a G)),{\mathcal {\neg A} }\Rightarrow {\mathcal {\neg B))}{{\text{D))\Rightarrow {\mathcal {A))))

je ekvivalentní kombinaci dvou systémů:

důkaz redukcí na absurditu

{\dfrac {{\text{D)),{\mathcal {A}}\Rightarrow {\mathcal {B}}{\text{ a G)),{\mathcal {A}}\Rightarrow { \mathcal {\neg B))}{{\text{D))\Rightarrow {\mathcal {\neg A))))

a odstranění dvojité negace

{\mathcal {\neg {\neg {A))))\Rightarrow {\mathcal {A)).

Důkaz tohoto tvrzení lze nalézt v knize [4] .

Při dokazování kontradikcí používáme silnější logické prostředky, než když dokazujeme redukcí k absurditě. Je tomu tak proto, že důkaz kontradikcí se v podstatě opírá o pravidlo dvojité negace, zatímco důkaz redukcí do absurdity nikoli. Právě pro tuto okolnost je rozdíl mezi schématy rozporu in contrarium a reductio ad absurdum rozdílem nejen ve formě, ale i v podstatě. Navíc toto rozlišení úzce souvisí s určitými problémy v základech matematiky.

Faktem je, že takové logické zákony, jako je zákon vyloučeného středu , zákon odstranění dvojité negace , schéma ${\mathcal {A\vee \neg A}}$ ${\mathcal {\neg \neg A\supset A))$

{\dfrac {{\text{D)),{\mathcal {\neg A))\Rightarrow {\mathcal {B)){\text{ a G)),{\mathcal {\neg A} }\Rightarrow {\mathcal {\neg B))}{{\text{D))\Rightarrow {\mathcal {A))))

důkazy kontradikcí vedou k neefektivním konstrukcím a důkazům v matematice. Především jde o důkazy tzv. existenčních teorémů , tedy teorémů tvaru: „Existuje taková, že ”: , kde je nějaká vlastnost , která je splněna pro , a prochází určitou množinou známých objektů ( čísla, vzorce atd.). $X$ ${\mathcal {P}}\left(x\right)$ $\left(\exists {x}\right){\mathcal {P}}\left(x\right)$ ${\mathcal {P}}\left(x\right)$ ${\mathcal P}$ $X$ $X$

Efektivním důkazem věty o tvaruje konstrukce objektu(nebo metoda konstrukce tohoto objektu) a důkaz, že tento objekt skutečně má požadovanou vlastnost. Důkaz teorému existence, který nesplňuje tyto podmínky, je považován za neúčinný . $\left(\exists {x}\right){\mathcal {P}}\left(x\right)$ $X$ ${\mathcal P}$

Typickým neefektivním důkazem věty o existenci je důkaz kontradikcí. Opravdu, ať je požadováno prokázat prohlášení ve formě - "existuje předmět , který má vlastnost ". Předpokládejme, že . Úvahou dostáváme nějaký rozpor: a . Odtud na základě schématu reductio ad absurdum docházíme k závěru, že předpoklad je nepravdivý, tj . Dále, odstraněním dvojité negace, získáme a považujeme důkaz za dokončený. Takový důkaz však nekončí postavením alespoň jednoho objektu s požadovanou vlastností, nijak nás nepřibližuje k sestrojení příkladu takového , který je neefektivním důkazem. $\left(\exists {x}\right){\mathcal {P}}\left(x\right)$ $X$ ${\mathcal P}$ ${\displaystyle \neg {\left(\exists {x}\right){\mathcal {P}}\left(x\right)))$ ${\mathcal B}$ ${\mathcal {\neg B))$ $\neg {\neg {\left(\exists {x}\right){\mathcal {P}}\left(x\right)))$ $\left(\exists {x}\right){\mathcal {P}}\left(x\right)$ $X$ ${\mathcal {P}}\left(x\right)$

Příklady důkazů tohoto druhu jsou důkazy teorémů: věty o omezenosti funkce spojité na intervalu (tj. o existenci horní a dolní meze pro funkci spojitou na intervalu); věty o existenci největší a nejmenší hodnoty funkce spojité na intervalu. Tradiční důkaz těchto teorémů kontradikcí neobsahuje konstrukci, která by umožňovala zkonstruovat objekt, jehož existence je ve větě diskutována.

Neefektivní důkazy existence teorémů nejsou uznávány všemi matematiky. Pro matematiky, kteří stojí na tradičních klasických pozicích, je charakteristické, že bez omezení uznávají zákon vyloučeného středu a zákon odstranění dvojité negace . Zanedbávají rozdíly mezi tvrzeními a . Matematici, kteří se nedrží klasických názorů ( intuicionisté a konstruktivisté ), popírají univerzalitu těchto zákonů. Rozdíly mezi tvrzeními a takoví matematici uznávají jako velmi významné, protože tvrzení obecně řečeno považují za slabší než . Důkaz kontradikcí je z jejich pohledu rovněž nepřijatelný, neboť je založen na principu odstranění dvojí negace. ${\mathcal {A\vee \neg A}}$ ${\mathcal {\neg \neg A\supset A))$ $\left(\exists {x}\right){\mathcal {P}}\left(x\right)$ $\neg {\neg {\left(\exists {x}\right){\mathcal {P}}\left(x\right)))$ $\left(\exists {x}\right){\mathcal {P}}\left(x\right)$ $\neg {\neg {\left(\exists {x}\right){\mathcal {P}}\left(x\right)))$ $\neg {\neg {\left(\exists {x}\right){\mathcal {P}}\left(x\right)))$ $\left(\exists {x}\right){\mathcal {P}}\left(x\right)$

Rozdíl mezi schématy rozporu in contrarium a reductio ad absurdum je tedy svou povahou metodologický, dotýkající se problému různého chápání výroků o existenci v matematice, jakož i dalších problémů základů matematiky s nimi souvisejících .

Příklady

V matematice

Důkaz iracionality čísla .

{\sqrt {2}}

Předpokládejme opak: číslo je racionální , to znamená, že je reprezentováno jako neredukovatelný zlomek , kde je celé číslo a je přirozené číslo . Uveďme druhou mocninu předpokládané rovnosti: ${\sqrt {2}}$ ${\frac {m}{n}}$ $m$ $n$

{\sqrt {2}}={\frac {m}{n}}

\Šipka doprava

2={\frac {m^{2}}{n^{2}}}

, odkud .

m^{2}=2n^{2}

Z toho plyne, že sudý , tedy sudý a ; je tedy dělitelné 4, a tedy i sudé. Výsledné tvrzení je v rozporu s neredukovatelností zlomku . Původní předpoklad byl tedy chybný a jedná se o iracionální číslo . $m^{2}$ $m$ $m^{2}$ $n^{2}$ $n$ ${\frac {m}{n}}$ ${\sqrt {2}}$

V každodenním životě

Lékař, který pacientovi vysvětlí, že chřipkou není nemocný, může použít následující úvahu: „Kdybys byl opravdu nemocný chřipkou, měl bys horečku, ucpaný nos atd. Ale ne mít tohle všechno, takže ne a chřipka“ [3] .

Literatura

Timofeeva I. L. Matematická logika. Průběh přednášek: Proc. příspěvek pro vysokoškoláky. - 2. vyd., přepracováno. - M. : KDU, 2007. - 304 s. — ISBN 978-5-98227-307-9 .

Viz také

Snížení do absurdna (apagoga)
Metoda nekonečného sestupu

Poznámky

↑ 1 2 Nepřímé důkazy // Filosofie: Encyklopedický slovník. — M.: Gardariki. Editoval A. A. Ivin . 2004.
↑ Důkaz kontradikcí // Filosofie: Encyklopedický slovník. — M.: Gardariki. Editoval A. A. Ivin . 2004.
↑ 1 2 Důkaz kontradikcí // Velká sovětská encyklopedie : [ve 30 svazcích] / kap. vyd. A. M. Prochorov . - 3. vyd. - M .: Sovětská encyklopedie, 1969-1978.
↑ Timofeeva I. L. Několik poznámek k metodě důkazu kontradikcí // Matematika ve škole - 1994, č. 3. S. 36-38.