beweisbar

Beweisbar ist ein Adjektiv aus Mathematik und Logik, das beschreibt, dass eine Aussage innerhalb eines gegebenen formalen Rahmens bewiesen werden kann. Eine Aussage S ist in einem formalen System F beweisbar, wenn es einen endlichen Beweis gibt, der aus Axiomen von F und aus durch Folgerungsregeln abgeleiteten Formeln besteht und mit S endet.

Beweisbarkeit ist eine syntaktische Eigenschaft, die von einem konkreten System abhängt. Sie bedeutet nicht automatisch absolute Wahrheit; sie besagt lediglich, dass es eine formale Beweiskette im System gibt. Im Gegensatz dazu bezeichnet Wahrheit eine semantische Eigenschaft, die in Modellen der Axiome definiert wird. In vielen etablierten Systemen gilt: Ist etwas beweisbar, so ist es unter Annahme der Korrektheit des Systems auch wahr in allen Modellen.

Die logische Bedeutung von Beweisbarkeit wird durch Gödel deutlich: In jedem hinreichend starken, konsistenten formalen System gibt es Sätze, die wahr sind, aber nicht innerhalb dieses Systems beweisbar sind. Dadurch unterscheiden sich Beweisbarkeit, Wahrheit und Entscheidbarkeit: Es kann sein, dass weder Beweis noch Gegenbeweis algorithmisch gefunden werden kann, insbesondere in unentscheidbaren Systemen.

Der Begriff leitet sich vom deutschen Wort beweisen ab und dem Suffix -bar, das die Möglichkeit ausdrückt. Beweisbarkeit ist daher ein Kernkonzept der formalen Mathematik und der theoretischen Informatik, das die Grenze zwischen dem, was formal ableitbar ist, und dem, was wahr sein könnte, markiert.