Exercise 5

Prädikatenlogik

Prädikatenlogische Axiome

K25

Sei eine Struktur, eine Belegung, und Terme und eine Variable. Sei .

Zeigen Sie: .

Mit (oder auch ) ist jene Belegung gemeint, die erfüllt und sonst mit übereinstimmt.

Beziehen Sie sich in Ihrem Beweis auf die induktive Definition der Substitution .

Die Substitutionsaxiome setzen voraus, dass die Substitution „erlaubt“ ist: Keine Variable von wird durch die Substitution gebunden. Beispielsweise darf man in nicht durch substituieren und erhalten.

Diese Einschränkung ist nötig:

Dabei ist eine Variable. Die Erweiterung wertet Terme rekursiv aus.

Substitution

Beweis durch strukturelle Induktion über .

Induktionshypothese

Seien Terme, für die für alle gilt:

Induktionsanfang

Substitution via Syntax:

Substitution via :

mit

Substitution via Syntax:

Substitution via :

mit Konstantensymbol

Substitution via Syntax:

Substitution via :

Induktionsschritt

Sei ein -stelliges Funktionssymbol. Dann gilt:

K26+

Geben Sie in einer geeigneten Sprache eine möglichst einfache Formel an, sowie einen Term , eine Struktur und eine Belegung , sodass mit die Werte und verschieden sind.

Finden Sie eine Formel und einen verbotenen Term , sodass nicht allgemeingültig ist, und geben Sie auch ein konkretes Gegenbeispiel an.

Nochmals die Erfüllungsrelation

K27

Wählen Sie eine geeignete Sprache und geben Sie eine Formel in dieser Sprache ohne freie Variable an, sodass für jede endliche nichtleere Menge die folgenden Aussagen äquivalent sind:

1. Die Anzahl der Elemente von ist gerade.
2. Es gibt eine Struktur mit Universum , sodass .

Hinweis: Bijektion.

Gesucht: , erzeugt aus , sodass:

Oder äquivalent:

Sei , beliebig. Man konstruiere ein als

K28

Seien geschlossene Formeln. Zeigen Sie:

1. genau dann, wenn .
2. Sei eine Menge von geschlossenen Formeln. genau dann, wenn .
3. Sei eine Menge von geschlossenen Formeln. genau dann, wenn .

(1)

Zu zeigen ist . Wir beweisen beide Richtungen durch eine Äquivalenzkette.

Auswertung der Implikation

Seien eine beliebige Struktur und eine beliebige Belegung. Dabei wertet in aus.
Nach Definition der Wahrheitsfunktion:

Folglich:

Diese Äquivalenz gilt für jedes ; sie kann daher auch unter den folgenden Allquantoren verwendet werden.

Äquivalenzkette

Hier durchläuft alle Strukturen der Sprache:

(2) mit geschlossene Formelmenge

Definition

Definition

Observation

Seien eine beliebige Struktur und eine beliebige Belegung. Dann gilt:

Da beliebig waren, gilt diese Äquivalenz für alle Strukturen und Belegungen. Durch Allquantifizierung beider Seiten und die obigen Definitionen der Folgerung erhalten wir:

(3) mit geschlossene Formelmenge

Definition

Definition

Seien , beliebig.

Da immer unwahr ist, muss die Prämisse auch unwahr sein.

Da beliebig waren, gilt das für alle, d.h.:

K29

Ist für alle Formeln und allgemeingültig?

Ist allgemeingültig? Dabei ist ein einstelliges Relationssymbol.

K30

Seien Sätze, eine Theorie und eine Struktur.

1. Gilt: genau dann, wenn oder ?
   Hinweis: Wirklich so einfach, wie es aussieht.
2. Gilt: genau dann, wenn oder ?
   Hinweis: Es reicht, wenn Sie betrachten; Sie können aber auch die Gruppenaxiome oder dergleichen verwenden.
3. Wie ist das mit und an Stelle von ?