Prädikatenlogik/Folgerung/Axiomensysteme/Textabschnitt

Mit Axiomensystemen verbindet man die Vorstellung, dass daraus „wichtige“ weitere Eigenschaften beweisbar sind. In einer jeden Gruppe gelten nicht nur die Gruppenaxiome, sondern auch alle Gesetzmäßigkeiten, die man aus den Gruppenaxiomen folgern kann. Dies wird in der mathematischen Logik durch den Folgerungsbegriff präzisiert.

Definition

Es sei ${}S$ ein Symbolalphabet erster Stufe, ${}\Gamma$ eine Menge von ${}S$-Ausdrücken und ${}\alpha$ ein ${}S$-Ausdruck. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ folgt, geschrieben ${}\Gamma \vDash \alpha$, wenn für jede ${}S$-Interpretation ${}I$ mit ${}I\vDash \Gamma$ auch ${}I\vDash \alpha$ gilt.

Die Folgerungsbeziehung verwendet also (wie schon im aussagenlogischen Kontext) das gleiche Symbol wie die Gültigkeitsbeziehung. Dass aus einer gewissen Ausdrucksmenge ${}\Gamma$ ein gewisser Ausdruck ${}\alpha$ folgt, erfordert eine mathematische Argumentation, die aufzeigt, dass eine Menge mit gewissen zusätzlichen Strukturen, die ${}\Gamma$ erfüllt, stets auch ${}\alpha$ erfüllen muss.

Beispiel

In einer Gruppe ist das inverse Element zu einem jeden Element, das es aufgrund der Definition einer Gruppe geben muss, eindeutig bestimmt. Mathematisch wird dies so bewiesen: Es sei ${}e$ das neutrale Element der Gruppe, sei ${}x\in G$ vorgegeben und seien ${}y,z\in G$ inverse Elemente zu ${}x$, d.h. es gelte ${}yx=xy=e$ und ${}zx=xz=e$. Dann ist insgesamt

${}y=ye=y(xz)=(yx)z=ez=z\,.$

Die Eindeutigkeit des inversen Elementes kann man mit den Symbolen ${}\{e,\mu \}$, wobei ${}e$ eine Konstante und ${}\mu$ ein zweistelliges Funktionssymbol ist, als den Ausdruck

${}\alpha :=\forall x(\forall y(\forall z(\mu yx=e\wedge \mu xy=e\wedge \mu zx=e\wedge \mu xz=e\rightarrow y=z)))\,$

ansetzen, und die obige mathematische Argumentation bedeutet, dass der Ausdruck ${}\alpha$ aus den Gruppenaxiomen ${}\Gamma$ folgt, also die Folgerungsbeziehung

$\Gamma \vDash \alpha$

vorliegt.

Da ein allgemeingültiger Ausdruck ${}\alpha$ in jeder Interpretation gilt, kann man auch sagen, dass ${}\alpha$ aus der leeren Ausdrucksmenge folgt, also ${}\emptyset \vDash \alpha$ gilt. Wenn ${}\alpha _{1},\alpha _{2},\alpha _{3}$ die Gruppenaxiome sind, und ${}\alpha$ die im obigen Beispiel erwähnte Eindeutigkeitsausssage für das inverse Element ist, so ist

$\alpha _{1}\wedge \alpha _{2}\wedge \alpha _{3}\rightarrow \alpha$

allgemeingültig.

Definition

Es sei ${}S$ ein Symbolalphabet und es sei ${}\alpha$ ein ${}S$-Ausdruck in der Prädikatenlogik erster Stufe. Man nennt ${}\alpha$ erfüllbar, wenn es eine ${}S$-Interpretation ${}I$ mit ${}I\vDash \alpha$ gibt.

Für eine Ausdrucksmenge ${}\Gamma$ bedeutet die Erfüllbarkeit, dass die darin enthaltenen Ausdrücke simultan in einer Interpretation erfüllbar sind. Zwischen Allgemeingültigkeit und Erfüllbarkeit besteht die Beziehung, dass ${}\alpha$ genau dann allgemeingültig ist, wenn die Negation ${}\neg \alpha$ nicht erfüllbar ist.

Zwischen Folgerung und Erfüllbarkeit besteht der folgende Zusammenhang.

Lemma

Es gilt ${}\Gamma \vDash \alpha$ genau dann, wenn ${}\Gamma \cup \{\neg \alpha \}$ nicht erfüllbar ist.

Beweis

Siehe Aufgabe.

$\Box$