Bevis genom motsägelse

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 mars 2021; kontroller kräver 65 redigeringar .

Bevis "genom motsägelse" ( lat. contradictio in contrarium ), eller apagogiskt indirekt bevis [1] , är en typ av bevis där "beviset" av en viss bedömning ( bevisuppsats ) genomförs genom att vederlägga negationen av denna dom - antites [2] . Denna bevismetod är baserad på sanningen i lagen om dubbel negation i klassisk logik .

Denna metod är mycket viktig för matematik , där det finns många påståenden som inte kan bevisas på annat sätt [3] .

Bevisschema

Ett schema för bevis genom motsägelse är ett schema:

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

Den formaliserar bevismetoden genom motsägelse.

Beviset för påståendet utförs enligt följande. Först görs antagandet att påståendet är falskt, och sedan bevisas det att under ett sådant antagande skulle något påstående vara sant , vilket uppenbarligen är falskt. ${\mathcal {A}}$ ${\mathcal {A}}$ ${\mathcal B}$

Det följer av definitionen av implikation att om det är falskt så är formeln sann om och endast om det är falskt, därför är påståendet sant. ${\mathcal B}$ ${\mathcal {\neg A\Högerpil B))$ ${\mathcal {\neg A))$ ${\mathcal {A}}$

Den resulterande motsägelsen visar att det ursprungliga antagandet var fel, och därför är påståendet sant , vilket enligt lagen om dubbel negation är likvärdigt med påståendet . ${\mathcal {\neg \neg A))$ ${\mathcal {A}}$

I intuitionistisk logik accepteras inte bevis genom motsägelse, precis som lagen om den uteslutna mitten inte fungerar [1] .

Anmärkning . Detta system liknar ett annat - till systemet för bevis genom reducering till absurditet . Som ett resultat är de ofta förvirrade. Men trots vissa likheter har de en annan form. Dessutom skiljer de sig inte bara i form, utan också i huvudsak, och denna skillnad är av grundläggande karaktär.

Jämförelse av bevismetoder från motsägelse och reducering till absurditet

Idén om behovet av att skilja mellan dessa metoder i matematikundervisningen tillhör Felix Aleksandrovich Kabakov (1927–2008) , som omsatte denna idé i praktiken under fyrtio års arbete vid den matematiska fakulteten vid Moscow State Pedagogical University .

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

Låt oss gå vidare till att jämföra motsvarande bevismetoder.

Metoden att bevisa genom motsägelse anses vara en välkänd bevismetod, men ofta används termen "bevis genom motsägelse" i olika betydelser och i relation till olika bevismetoder. Oftast förväxlas metoden för bevis genom motsägelse med metoden för bevis genom reducering till absurditet.

Bokstäverna och kommer att beteckna godtyckliga meningar, och bokstaven betecknar godtyckliga ändliga uppsättningar meningar. Vi kommer att använda notationen för att beteckna det faktum att förslaget är motiverat (bevisat) utifrån förslagen eller logiskt följer av . Relationen mellan uppsättningar av meningar och meningar kommer att kallas relationen av logisk konsekvens . ${\mathcal {A}}$ ${\mathcal {B}}$ ${\text{D))$ ${\text{D}}\Rightarrow {\mathcal {A}}$ ${\mathcal {A}}$ ${\text{D))$ ${\mathcal {A}}$ ${\text{D))$ $\Höger pil$

Beviset genom motsägelse är som följer. Låt det krävas att bevisa ett påstående baserat på några påståenden (dessa kan vara tidigare bevisade satser, axiom eller antaganden). Vi antar att det inte är sant, d.v.s. vi erkänner , och genom att resonera, baserat på och , härleder vi en motsägelse, d.v.s. propositionen och dess negation . Efter det drar vi slutsatsen att antagandet är falskt, och därför är påståendet sant . Vårt resonemang kan beskrivas med hjälp av följande informella resonemangsschema: ${\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{ och G)),{\mathcal {\neg A} }\Rightarrow {\mathcal {\neg B))}{{\text{D))\Rightarrow {\mathcal {A))))

Det är detta schema som bör kallas för motsägelsebevis .

Situationen förändras när det är nödvändigt att motbevisa domen , med andra ord när domen som ska bevisas har formen (inte ), d.v.s. är en negativ dom. ${\mathcal {A}}$ ${\mathcal {\neg A))$ ${\mathcal {A}}$

Till exempel ser meningen ut så här: "Det finns inget rationellt tal vars kvadrat är 2." Det bevisas genom att härleda en motsägelse från antagandet att det finns ett rationellt tal vars kvadrat är 2.

Så, för att bevisa det negativa påståendet om , vi antar att , och härleda en viss motsägelse: och . Ett informellt schema som beskriver ett sådant resonemangsförlopp ser ut så här: ${\mathcal {\neg A))$ ${\mathcal {A}}$ ${\mathcal {B}}$ ${\mathcal {\neg B))$

{\dfrac {{\text{D)),{\mathcal {A}}\Rightarrow {\mathcal {B}}{\text{ och G)),{\mathcal {A}}\Rightarrow { \mathcal {\neg B))}{{\text{D))\Högerpil {\mathcal {\neg A))))

Detta informella resonemangsschema brukar kallas systemet för bevis genom reducering till absurditet eller reducering till absurditet (från latin reductio ad absurdum).

Tyvärr skiljer de vanligtvis inte i undervisningspraktik mellan dessa två scheman, två metoder för bevis, som oftast kallar dem båda för bevis genom motsägelse .

Låt oss uppehålla oss vid skälen till att dessa system fortfarande bör särskiljas.

För det första är det uppenbart att dessa scheman skiljer sig rent grafiskt, vilket gör att resonemanget enligt dessa scheman skiljer sig åt i form. Skillnader av samma karaktär, det vill säga åtminstone i form, finns mellan meningar och (eller mellan meningar och ). Även om vi, på de klassiska ståndpunkterna, tror att dessa uttalanden är likvärdiga, är faktumet med skillnaden i form fortfarande uppenbart. ${\mathcal {A}}$ ${\displaystyle {\mathcal {\neg {\neg A))))$ ${\mathcal {A\rightarrow B}}$ ${\mathcal {\neg A))\vee {\mathcal {B))$

Men en sådan distinktion kan för någon verka otillräcklig, föga övertygande för att starta hela denna konversation. Naturligtvis uppstår frågor: är dessa system likvärdiga? vad är skillnaden mellan dem i praktiken av matematiska bevis; Är denna skillnad bara i form eller också i huvudsak?

För att svara på den första frågan: "Är systemen contradictio in contrarium och reductio ad absurdum likvärdiga?" möjligt på en informell nivå, utan att gå över till vägen att bygga ett formellt logiskt system. Kopplingen mellan dessa system fastställs av följande uttalande.

❗ GODKÄNNANDE . System av bevis genom motsägelse

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

motsvarar kombinationen av två system:

bevis genom reducering till absurditet

{\dfrac {{\text{D)),{\mathcal {A}}\Rightarrow {\mathcal {B}}{\text{ och G)),{\mathcal {A}}\Rightarrow { \mathcal {\neg B))}{{\text{D))\Högerpil {\mathcal {\neg A))))

och avlägsnande av dubbel negation

{\mathcal {\neg {\neg {A))))\Högerpil {\mathcal {A)).

Beviset för detta påstående finns i boken [4] .

När vi bevisar genom motsägelse använder vi starkare logiska medel än när vi bevisar genom reducering till absurditet. Detta beror på att bevis genom motsägelse i huvudsak bygger på regeln om dubbel negation, medan bevis genom reduktion till absurditet inte gör det. Just på grund av denna omständighet är skillnaden mellan systemen contradictio in contrarium och reductio ad absurdum en skillnad inte bara i form utan också i huvudsak. Dessutom är denna distinktion nära relaterad till vissa problem i matematikens grunder.

Faktum är att sådana logiska lagar som lagen om den uteslutna mitten , lagen om avlägsnande av dubbel negation , schemat ${\mathcal {A\vee \neg A}}$ ${\mathcal {\neg \neg A\upset A))$

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

bevis genom motsägelse leder till ineffektiva konstruktioner och bevis i matematik. Först och främst hänvisar detta till bevisen för de så kallade existenssatserna , d.v.s. satser av formen: "Det finns sådana att ": , där finns någon egenskap som är uppfylld för , och går genom en viss uppsättning kända objekt ( siffror, formler etc.). $x$ ${\mathcal {P}}\left(x\right)$ $\left(\exists {x}\right){\mathcal {P}}\left(x\right)$ ${\mathcal {P}}\left(x\right)$ ${\mathcal P}$ $x$ $x$

Ett effektivt bevis på formsatsenär konstruktionen av ett objekt(eller en metod för att konstruera detta objekt) och beviset att detta objekt faktiskt har den nödvändiga egenskapen. Ett bevis på existenssatsen som inte uppfyller dessa villkor anses vara ineffektivt . $\left(\exists {x}\right){\mathcal {P}}\left(x\right)$ $x$ ${\mathcal P}$

Ett typiskt ineffektivt bevis på existenssatsen är bevis genom motsägelse. Låt det faktiskt krävas för att bevisa ett uttalande av formen - "det finns ett objekt som har egenskapen ". Låt oss anta det . Genom att resonera får vi en viss motsägelse: och . Härifrån drar vi, i kraft av schemat reductio ad absurdum , slutsatsen att antagandet är falskt, dvs. Vidare, genom att ta bort den dubbla negationen, får vi och betraktar beviset som komplett. Ett sådant bevis slutar dock inte med konstruktionen av minst ett objekt med den nödvändiga egenskapen; det för oss inte på något sätt närmare att konstruera ett exempel som , d.v.s. är ett ineffektivt bevis. $\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)$

Exempel på bevis av detta slag är bevis för satser: satser om begränsningen av en funktion som är kontinuerlig på ett intervall (det vill säga om förekomsten av övre och nedre gränser för en funktion som är kontinuerlig på ett intervall); satser om förekomsten av de största och minsta värdena av en funktion kontinuerligt på ett intervall. Det traditionella beviset för dessa satser genom motsägelse innehåller inte en konstruktion som gör att man kan konstruera det objekt vars existens diskuteras i satsen.

Ineffektiva bevis på existenssatsningar erkänns inte av alla matematiker. För matematiker som står på traditionella klassiska positioner är det karakteristiskt att utan några begränsningar erkänna lagen om den uteslutna mitten och lagen om borttagande av dubbel negation . De försummar skillnaderna mellan påståendena och . Matematiker som inte ansluter sig till klassiska åsikter ( intuitionister och konstruktivister ) förnekar dessa lagars universalitet. Skillnader mellan påståenden och sådana matematiker erkänner som mycket betydande, med tanke på påståendet , generellt sett, svagare än . Bevis genom motsägelse, ur deras synvinkel, är också oacceptabelt, eftersom det bygger på principen om att ta bort dubbel negation. ${\mathcal {A\vee \neg A}}$ ${\mathcal {\neg \neg A\upset 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)$

Således är skillnaden mellan scheman contradictio in contrarium och reductio ad absurdum metodologisk till sin natur, vilket påverkar problemet med olika förståelse av påståenden om existens i matematik, såväl som andra problem med matematikens grunder relaterade till dessa .

Exempel

I matematik

Bevis på irrationaliteten hos ett nummer .

{\sqrt {2}}

Antag motsatsen: talet är rationellt , det vill säga det representeras som ett irreducerbart bråk , där är ett heltal och är ett naturligt tal . Låt oss kvadrera den förmodade jämlikheten: ${\sqrt {2}}$ ${\frac {m}{n}}$ $m$ $n$

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

\Höger pil

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

, varifrån .

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

Av detta följer att jämn , därav jämn och ; därför är delbart med 4, och därmed även jämnt. Det resulterande uttalandet motsäger bråkets irreducerbarhet . Därför var det ursprungliga antagandet fel och är ett irrationellt tal . $m^{2}$ $m$ $m^{2}$ $n^{2}$ $n$ ${\frac {m}{n}}$ ${\sqrt {2}}$

I vardagen

Läkaren, som förklarar för patienten att han inte är sjuk av influensa, kan använda följande resonemang: "Om du verkligen var sjuk i influensa, då skulle du ha feber, täppt näsa, etc. Men du har inte har allt detta, så du inte och influensa" [3] .

Litteratur

Timofeeva I. L. Matematisk logik. Föreläsningskurs: Proc. bidrag för universitetsstuderande. - 2:a uppl., reviderad. - M. : KDU, 2007. - 304 sid. — ISBN 978-5-98227-307-9 .

Se även

Reducera till det absurda (apagog)
Metod för oändlig nedstigning

Anteckningar

↑ 1 2 Indirekt bevis // Filosofi: Encyclopedic Dictionary. — M.: Gardariki. Redigerat av A. A. Ivin . 2004.
↑ Bevis genom motsägelse // Filosofi: Encyclopedic Dictionary. — M.: Gardariki. Redigerat av A. A. Ivin . 2004.
↑ 1 2 Bevis genom motsägelse // Stora sovjetiska encyklopedin : [i 30 volymer] / kap. ed. A. M. Prokhorov . - 3:e uppl. - M . : Soviet Encyclopedia, 1969-1978.
↑ Timofeeva I. L. Några anmärkningar om metoden för bevis genom motsägelse // Mathematics at School - 1994, nr 3. S. 36-38.