axiomatisierbar

Axiomatisierbar (axiomatisierbar) bezeichnet in der formalen Logik die Eigenschaft einer Theorie T in einer gegebenen Sprache, dass T durch eine Menge A von Sätzen axiomatisiert werden kann, sodass T genau die logischen Folgerungen aus A ist. Formal ausgedrückt gilt: T = Th(A). Die Menge A wird als Axiomensystem oder Axiomatisierung bezeichnet und kann endlich oder unendlich sein.

Eine weitere Unterscheidung betrifft die Effektivität: Ist A rekursiv aufzählbar, also durch einen Algorithmus schrittweise aufgezählt, so spricht man von einer rekursiv axiomatisierbaren (effektiv axiomatisierbaren) Theorie. Ist A nicht rekursiv aufzählbar, bleibt T axiomatisierbar, besitzt aber keine rekursiv auffindbare Präsentation. Eine Theorie, für die es eine endliche Axiomensammlung gibt, heißt finitely axiomatizable.

Beispiele: Die Peano-Arithmetik PA ist rekursiv axiomatisierbar. Die Theorie der wahren Aussagen über natürliche Zahlen Th(N,+,×) ist axiomatisierbar (durch die Menge aller wahren Sätze), aber nicht rekursiv aufzählbar. Die Theorie der reell abgeschlossenen Körper (RCF) ist vollständig und entscheidbar und besitzt eine rekursiv aufzählbare Axiomatisierung, die durch ein unendliches Axiomenschema beschrieben wird.

Bedeutung: Axiomatisierbarkeit ist keine Garantie für Entscheidbarkeit oder Vollständigkeit. Eine rekursiv axiomatisierbare Theorie kann unentscheidbar und unvollständig sein (beispielsweise PA). Umgekehrt gibt es auch axiomatisierbare Theorien, die entscheidbar oder vollständig sind.