Bizonyíthatóság
Bizonyíthatóság (provability) az elméleti logikában annak a tulajdonsága, hogy egy mondat véges bizonyítással előállítható egy adott axiomatikus rendszerben. A leggyakoribb példák közé tartozik a Peano-aritmetika (PA) vagy a ZFC. Egy mondat akkor bizonyítható, ha létezik egy formális bizonyítási sor, amely az axiómákból és az inferenciákból levezeti φ-t. A bizonyíthatóságot gyakran jelöljük Pr_T(⌜φ⌝)-val: φ bizonyítható T-ben.
A bizonyíthatóság formalizálása aritmetizálható: a Gödel-féle számkódolás révén belülről beszélhetünk a bizonyításokról. Ennek köszönhetően a rendszer
Gödel-féle eredmények megvilágítják a bizonyíthatóság korlátait: ha T konszisztens és elegendően kifejező, léteznek olyan φ-k, amelyek
A bizonyíthatóság megkülönböztethető az igazságtól: bizonyíthatónak lenni nem feltétlenül jelenti a szemantikailag igaz állítást, és fordítva.