Prädikatenlogische Theorien

Prädikatenlogische Theorien (erster Stufe) sind Mengen geschlossener Formeln, die auch alle, aus eben dieser Menge logisch folgerbaren Formeln enthalten. Diese Definition und die folgende Bemerkungen stammen aus den Folien (Meyer 2013) zur Vorlesung Logik. Wenn im Folgenden von Theorien und (geschlossenen) Formeln gesprochen wird, sind Formeln und Theorien über einer Signatur S gemeint.

• T_Σ ist die von Σ erzeugte Theorie, die genau aus den Folgerungen aus Σ besteht.
• Ist M eine Struktur, dann ist T_M (auch Th(M) ) die Theorie von M. Sie enthält genau die von M erfüllten (geschlossenen) Formeln
• Theorien, die sowohl die Formel A als auch ¬A enthalten, heißen inkonsistent
• Vollständig heißen Theorien, die (für jede geschlossene Formel A) A oder ¬A enthalten
• Eine Menge Ax, die eine Theorie Σ erzeugt, also T_Ax = Σ, ist deren Axiomensystem oder Axiomatisierung
  • Existiert ein solches Axiomensystem, heißt die Theorie axiomatisierbar
  • Ist ein solches Axiomensystem aufzählbar, heißt die Theorie aufzählbar axiomatisierbar
  • Ist ein solches Axiomensystem endlich, heißt die Theorie endlich axiomatisierbar

Ich werde nun einige Beweise über Theorien und unter Verwendung der vorgestellten Definitionen vorstellen.

Es gibt nur eine inkonsistente Theorie

Sei T eine inkonsistene Theorie. Nach Definition enthält T sowohl die Formel A als auch ¬A. Somit ist T unerfüllar und jede geschlossene Formel kann daraus gefolgert werden. Nach der Defition von Theorien sind diese Formeln auch alle in der Theorie enthalten. Folglich ist jede inkonsistene Theorie gerade die Menge aller geschlossenen Formeln (einer Signatur S).

Theorien von Modellen sind vollständig und konsistent

Theorien von Modellen sind konsistent

Wäre die Theorie eines Modells inkonsistent, würde sie sowohl A als auch ¬A enthalten. Dies kann jedoch nicht sein, da das Modell ja nur eine der beiden Formeln erfüllen kann und somit kann auch nur eine der beiden Formeln in der Theorie dieses Modells sein.

Theorien von Modellen sind vollständig

Wäre eine Theorie eines Modells nicht vollständig, gäbe es eine Formel A so, dass weder A noch ¬A in der Theorie sind. Erfüllt das Modell die Formel A nicht, muss es ¬A erfüllen und ¬A wäre in der Theorie des Modells.

Vollständige, aufzählbar axiomatisierbare Theorien sind entscheidbar

Ist eine Theorie aufzählbar axiomatisierbar, so lässt auch durch Verwendung des deduktiven System F die Theorie selbst aufzählen. Da die Theorie vollständig ist, wird nach endlicher Zeit A oder ¬A beim Aufzählen genannt. Dann kann der Entscheidungsalgorithmus halten und entsprechend antworten.

Vollständigkeit und Konsistenz

Behauptung:Eine Theorie Σ ist vollständig ⇔ mit jeder geschlossenen Formel A ist T_{Σ ∪ {A}} oder T_{Σ ∪ {¬A}} inkonsistent

„⇒ “: Da die Theorie vollständig ist, betrachtet folgende Fallunterscheidung alle möglichen Fälle (für jede geschlossene Formel A):

• A ∈ Σ: A, ¬A ∈ Σ ∪ {¬A} und daher ist T_{Σ ∪ {¬A}} inkonsistent
• ¬A ∈ Σ: A, ¬A ∈ Σ ∪ {A} und daher ist T_{Σ ∪ {A}} inkonsistent

Somit wurde gezeigt, dass mit jeder geschlossenen Formel A T_{Σ ∪ {A}} oder T_{Σ ∪ {¬A}} inkonsistent ist.

„⇐ “: Für jede geschlossene Formel A ist T_{Σ ∪ {A}} oder T_{Σ ∪ {¬A}} inkonsistent.

• T_{Σ ∪ {¬A}} ist inkonsistent: Σ ∪ {¬A} muss unerfüllbar sein. Nach Satz der Vorlesung gilt: Σ ⊧ A. Da Σ eine Theorie ist, A ∈ Σ
• T_{Σ ∪ {A}} ist inkonsistent: Σ ∪ {A} muss unerfüllbar sein. Nach Satz der Vorlesung gilt: Σ ⊧ ¬A. Da Σ eine Theorie ist, ¬A ∈ Σ

Somit wurde gezeigt, dass für jede geschlossene Formel A: A oder ¬A ∈ Σ. Σ ist also vollständig.

---

---