Indirekt bizonyítás

A matematikában és a logikában indirekt bizonyításnak nevezzük azt a fajta bizonyítást, amelyben feltesszük a bizonyítani kívánt állítás tagadását, majd ebből szabályos logikai lépések útján ellentmondásra jutunk valamilyen ismert ténnyel. Ez a bizonyítástípus alkalmazása az általánosabb reductio ad absurdum gondolatmenetnek.

Formális leírása

A matematikai logika nyelvén az indirekt bizonyítás az alábbi séma szerint működik:

Ha

${\displaystyle S\cup \{p\}\vdash \mathbb {F} }$

akkor

${\displaystyle S\vdash \neg p.}$

vagy más megfogalmazásban

ha

${\displaystyle S\cup \{\neg p\}\vdash \mathbb {F} }$

akkor

${\displaystyle S\vdash p.}$

Itt ${\displaystyle \mathbb {F} }$ a hamis logikai értéket, p pedig a bizonyítani kívánt állítást jelöli. ${\displaystyle S}$ igaznak feltételezett állítások valamilyen halmazát (például egy matematikai terület axiómáit) jelenti.

Példa

Az indirekt bizonyítási módszer egyik legismertebb alkalmazása a négyzetgyök 2 irracionalitásának Euklidésztől származó bizonyítása.

Források

• Kristóf János: Az analízis logikai alapjai. [2014. február 3-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014. február 1.)

További információk

• Alice és Bob - 12. rész: Alice és Bob rendet tesz