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

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

akkor

$S\vdash \neg p.$

vagy más megfogalmazásban

ha

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

akkor

$S\vdash p.$

Itt $\mathbb {F}$ a hamis logikai értéket, p pedig a bizonyítani kívánt állítást jelöli. $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