Exercise 4

Prädikatenlogik

Die Erfüllungsrelation

K19

Wir betrachten eine Sprache mit einem 2-stelligen Funktionssymbol . Finden Sie Formeln , , , sodass die folgenden Aussagen für alle -Strukturen gelten:

1. genau dann, wenn surjektiv ist.
2. genau dann, wenn injektiv ist.
3. genau dann, wenn bijektiv ist.

Geben Sie eine endliche Struktur an, sodass gilt. Geben Sie eine unendliche Struktur an, sodass gilt.

Surjektive Funktion

Injektive Funktion

(1-3)

Strukturen

Endliche Struktur

Es gibt nur das eine Eingabepaar . Daher ist injektiv und .

Unendliche Struktur

Für alle gilt:

Also ist injektiv und .

K20

Wir betrachten eine Sprache mit dem nichtlogischen Symbol , und die Struktur der natürlichen Zahlen, wo das Symbol durch Addition interpretiert wird. Sei die Belegung, die auf abbildet, alle anderen Variablen auf .

Sei die Formel . Berechnen Sie . Dazu müssen Sie

1. für gewisse Terme den Wert von berechnen, möglicherweise auch den Wert von für gewisse andere Belegungen .
2. für gewisse Formeln den Wert von berechnen, möglicherweise auch den Wert von für gewisse andere Belegungen .

Geben Sie alle solchen Terme und alle solchen Formeln an, sowie die entsprechenden Werte bzw. , und ebenso für alle relevanten .

Solution

bezeichnet eine weitere Belegung, keine Ableitung. Hier sind das die Belegungen mit : Nur der Wert von wird auf gesetzt; alle anderen Variablen behalten ihren Wert aus . Der Existenzquantor prüft damit, ob irgendeine Wahl von die Gleichung erfüllt, statt nur den ursprünglichen Wert zu prüfen.

Der Balken wertet Terme aus, das Dach Formeln.

Für die Terme in der Gleichung gilt:

Für jedes gilt:

Also:

Ü4

Ü4

Dasselbe noch einmal, aber jetzt mit einer geänderten Interpretation: Das Symbol wird jetzt als die übliche Multiplikation auf den natürlichen Zahlen interpretiert.

K21

1. Finde einen Satz, der in genau den Strukturen gilt, die mindestens 3 Elemente haben (damit ist natürlich gemeint: deren Universum genau 3 Elemente hat). Und einen weiteren für „genau 3“. Die Sprache dürfen Sie sich aussuchen.

2. Sei der Satz , und der Satz .

   In welchen der Strukturen gilt bzw. ? (Kurz: bzw. .)

   , , . (Hier wird also das zweistellige Relationssymbol durch die übliche „kleiner“-Relation interpretiert.)

   Die Formel ist eine Abkürzung für .

(1.1) mindestens

Warum keine Allquantoren?

Allquantoren würden verlangen, dass jede Wahl von drei verschiedene Elemente liefert. Verschiedene Variablen dürfen aber dasselbe Element bezeichnen. Für ein beliebiges ist auch die Wahl erlaubt:

Daher wäre die Formel mit drei Allquantoren in jeder nichtleeren Struktur falsch. Die Existenzquantoren verlangen dagegen nur eine Wahl von drei paarweise verschiedenen Elementen.

(1.2) genau

Zu jedem gibt es zwei weitere Elemente ; jedes Element ist eines dieser drei.

(2)

Zwischen liegt . In und liegt dagegen zwischen und kein Element.

ist das kleinste Element von ; und haben kein kleinstes Element.

Sprache der Mengenlehre

K22

Übersetzen Sie die folgenden Formeln in die offizielle Sprache der Mengenlehre. Hier sind nur logische Zeichen erlaubt (Objektvariable wie , Junktoren wie , etc., die Quantoren und , Klammern rund um Formeln) sowie das Symbol . Nicht erlaubt sind , , . Abgesehen von gibt es keine Relationssymbole, und es gibt weder Konstanten noch Funktionssymbole.

1. .
2. , wobei die rechte Seite als definiert ist.
3. (das ungeordnete Paar).
4. , wobei (das geordnete Paar).
5. .
6. .
7. ( ist Funktion von nach ).

(1)

enthält genau die Elemente, die in oder in liegen.

(2)

enthält genau die Elemente, die in mindestens einer Menge liegen.

(3)

enthält genau und ; für ist es eine einelementige Menge.

(4)

enthält genau die Mengen und .

(4) Alternative

Die ersten beiden Konjunkte verlangen ; das dritte schliesst weitere Elemente von aus.

(5)

enthält das in (4) beschriebene geordnete Paar .

(6)

Jedes Element von ist ein geordnetes Paar mit erster Komponente aus und zweiter aus .

(7) Funktion

Jedes erhält genau einen Wert ; enthält nur solche geordneten Paare.

Spracherweiterungen

In diesem Abschnitt seien Sprachen. Das heisst, jedes nichtlogische Symbol in ist auch nichtlogisches Symbol von der gleichen Art, mit der gleichen Stelligkeit in .

Wir können zu einer -Struktur eine -Struktur (mit demselben Universum ) definieren, indem wir die Interpretationen der Symbole in einfach vergessen. nennen wir das -Redukt von . Umgekehrt ist eine Expansion von .

Wenn ein -Satz ist, schreiben wir (nur in diesem Abschnitt) für „ gilt in allen -Strukturen“; und wenn eine -Theorie ist, schreiben wir für „ gilt in allen -Strukturen, die erfüllen“.

K23

Zeige: Sei ein -Satz und eine -Theorie. Dann gilt:

Hinweis: Zeigen Sie (mit Induktion – was für eine Induktion?) den folgenden Satz:

Für jede -Struktur , für jede -Formel und für jede Belegung gilt: genau dann, wenn … .

Observation

Jede -Struktur besitzt ein -Redukt mit demselben Universum .

Behauptung

wobei das -Redukt von ist.

Warum genügt diese Behauptung?

Jede lässt sich durch Interpretation der zusätzlichen Symbole expandieren. Daher kommt jede als Redukt vor.

Warum genügt sie? Angenommen, . Dann:

Rückwärts genauso. Wir nehmen also einen beliebigen Fall, übertragen ihn und erhalten dadurch die zweite Allaussage.

Bei K23 steht für die Wahl von :

Da jede -Struktur als Redukt vorkommt, sind diese Allaussagen genau die gewünschten Gültigkeitsaussagen.

Induktionsanfang

Sei und über beliebig. Dann:

Nach Definition der Erfüllungsrelation ist in jeder Struktur unter jeder Belegung wahr.

Nach Definition der Erfüllungsrelation ist in jeder Struktur unter jeder Belegung falsch.

Seien ein -stelliges Prädikatssymbol und Terme über . Da und die Interpretationen der -Symbole unverändert bleiben:

Warum bleibt die Auswertung gleich?

enthält alle Interpretationen von unverändert. Daher bei gleichem : gleiche Eingaben und gleiche Funktionen gleiche Termwerte. Auch bleibt identisch.

Im mittleren Schritt: gleiche Termwerte und Relation.

Mit der oben gezeigten Gleichheit der Termwerte:

Induktionsschritt

Nach Induktionsannahme gilt für jede Belegung :

Damit:

Nach Induktionsannahme stimmen die Wahrheitswerte von und in beiden Strukturen unter jeder Belegung überein. Daher:

Beide Strukturen haben dasselbe Universum . Die Induktionsannahme gilt auch für jede abgeänderte Belegung :

Ebenso gilt mit demselben Universum und der Induktionsannahme für jedes :

Schluss für die Folgerungsrelation

Die Induktion gilt für und jeden Satz . Da es Sätze sind, entfällt die Belegung:

Damit bleiben Voraussetzung und Schluss jeweils erhalten:

Der letzte Schritt gilt, weil jede -Struktur als Redukt einer Expansion vorkommt.

Spektren

Für jede geschlossene Formel definieren wir das Spektrum als die Menge aller natürlichen Zahlen natürlichen Zahlen , sodass es ein endliches Modell von mit genau Elementen gibt.

Ü5

Ü5

Finden Sie eine prädikatenlogische Sprache und eine geschlossene Formel , in der das Gleichheitszeichen nicht vorkommt, sodass .

K24+

Sei ein Satz, in dem das Gleichheitszeichen nicht vorkommt. Zeigen Sie: Wenn , und , dann .

Wir schreiben für die Menge aller Spektren (für beliebige prädikatenlogische Sprachen). ist eine Untermenge der Potenzmenge von .

Solution

Fixiere ein solches und mit .

Neue Elemente als Kopien

Wir brauchen zusätzliche Elemente. Quantoren erfassen auch diese; deshalb sollen sie sich bei Relationen und Funktionen wie bereits vorhandene Elemente verhalten.

Da , wähle . Sei eine zu disjunkte Menge mit . Wir ordnen jedem neuen Element das alte Element zu:

Jedes bleibt erhalten und hat ; also ist surjektiv.

Für jedes -stellige Funktionssymbol brauchen wir: Erst in auswerten und dann zuordnen soll dasselbe ergeben wie erst zuordnen und dann in auswerten.

Das rechte Ergebnis liegt in , wo nichts ändert. Wir können daher dieses Ergebnis selbst als Funktionswert wählen:

Da und , ist wohldefiniert. Dies ist eine mögliche Wahl; die neuen Elemente müssen nicht als Funktionswerte vorkommen.

Konstanten behalten ihren alten Wert. Relationen sollen nur von den zugeordneten alten Elementen abhängen. Für jedes Konstantensymbol und jedes -stellige Relationssymbol setzen wir:

Termauswertung bleibt nach Zuordnung erhalten

Sei beliebig und , also . Anders als in K23 sind die Termwerte nicht unmittelbar gleich: Für gilt

Deshalb zeigen wir durch strukturelle Induktion über die Gleichheit nach Anwendung von :

Für Variablen und Konstanten:

Für :

Die zweite Gleichheit nutzt die verlangte Verträglichkeit von mit , die dritte die Induktionsannahme für jedes .

Gleichheitsfreie Formeln bleiben wahr bzw. falsch

Strukturelle Induktion über , jeweils für jede Belegung mit :

Für Relationsformeln:

Die mittleren Schritte folgen aus der Definition von und der Terminduktion.

und haben in beiden Strukturen denselben festen Wahrheitswert. Für verwenden wir nur das Junktorenargument aus K23: Nach Induktionsannahme haben die Teilformeln unter in und unter in dieselben Wahrheitswerte. Dieselbe Wahrheitsfunktion liefert daraus denselben Wert.

Für Quantoren beachten wir zuerst:

Beide Belegungen liefern bei den Wert und bei jedem den Wert .
Damit liefert die Induktionsannahme für jedes :

Ein Existenzzeuge liefert also den Zeugen . Umgekehrt kann ein Zeuge selbst als Zeuge in dienen, denn :

Der Wechsel von zu erfasst genau alle Elemente von , weil .

Für die erste Allquantorrichtung sei beliebig:

Der mittlere Schritt nutzt die Induktionsannahme und . Der letzte folgt, weil beliebig war.

Umgekehrt sei beliebig. Dann ist :

Wieder überträgt die Induktionsannahme den einzelnen Fall. Weil beliebig war, gilt die Allaussage auch für alle neuen Elemente.

Der Gleichheitsfall fehlt zu Recht: Für gilt , aber . Bei , wäre daher , obwohl .

Schluss

ist gleichheitsfrei und hat keine freien Variablen. Für eine beliebige Belegung folgt:

Die Formelinduktion liefert den zweiten Schritt. Da ein Satz ist, hängt seine Wahrheit nicht von ab. Damit:

Z6

Zeigen Sie, dass jede endliche Teilmenge von ein Spektrum ist. (Wie definieren Sie „endlich“? Verwenden Sie vollständige Induktion? Wenn ja, geben Sie explizit die Behauptung an, von der Sie und zeigen.)

Z7

Zeigen Sie, dass unter Durchschnitten abgeschlossen ist. (Anleitung: Sei , . Erklären Sie, warum Sie ohne Beschränkung der Allgemeinheit annehmen dürfen, dass die Sprachen zu und disjunkt sind. …)

Z8

Zeigen Sie, dass unter Vereinigungen abgeschlossen ist.

Z9

Zeigen Sie, dass unter Komplementen abgeschlossen ist. (Hinweis: Unklar ob das gilt, siehe „Asser Problem“.)

Z10

Zeigen Sie von möglichst vielen der folgenden Mengen, dass sie Spektren sind: Die Menge der Primzahlen, die Menge aller zusammengesetzten Zahlen (= Nichtprimzahlen ), die Menge aller Quadratzahlen, die Menge aller Zweierpotenzen, die Menge aller Potenzen von , die Menge aller Primzahlpotenzen, die Menge .

Z11

Geben Sie eine (möglichst einfache) Menge an, die kein Spektrum ist.