Bizonyíthatók

Bizonyíthatók olyan mondatok a formális elméletekben, amelyekre létezik véges levezetés az adott axiómarendszer szabályai alapján. A kifejezés a bizonyítás fogalmát tükrözi: egy állítás akkor bizonyítható, ha az axiómákból és a megengedett levezetési szabályok felhasználásával létezik olyan levezetés, amely a mondatot levonja.

Formális értelemben egy mondat akkor bizonyítható, ha létezik olyan levezetés, amely a kiindulási axiómákból kiindulva a mondatot levonja. A bizonyíthatóság és az igazság fogalma különbözik: egy állítás lehet igaz a modellben, de nem feltétlenül bizonyítható a megadott elmélet keretében.

Gödel szerint erős formális rendszerekben előfordulhat, hogy igaz állításokat nem lehet bizonyítani a rendszer belső következtetései alapján, feltéve a konzisztenciát. Ennek következtében a bizonyíthatók halmaza rekurzíve felsorolható, de nem mindig dönthető.

Nyelvi használatban a "bizonyíthatók" kifejezést általában matematikai és logikai szövegekben alkalmazzák; gyakori példaként említik a Peano-aritmetika alapvető tételeit vagy más, formális elméletek tételrendszerét.