Quantifizieren über Teilmengen in Prädikatenlogik erster Stufe

Question

Wieso lässt sich in der Prädikatenlogik erster Stufe nicht über alle Teilmengen einer Menge quantifizieren (so wie es z.B. Voraussetzung für die Peano-Axiome ist)? Der Ausdruck

∀x Rxy ⇒ Qx

ist nach meinem Verständnis korrekt, wenn x und y Variabel- und R und Q Relationssymbole bzw. Prädikate sind. Nimmt man für R nun "... ist Teilmenge von ...", dann quantifiziert man doch über alle x, welche Teilmengen der Menge y sind, also über alle Teilmengen von y, oder?

Answer 1

> Wieso lässt sich in der Prädikatenlogik erster Stufe nicht über alle Teilmengen einer Menge quantifizieren

Weil so etwas dann "Prädikatenlogik zweiter Stufe" heißt.

> ... über alle x, welche Teilmengen der Menge y sind, ...

Laut  Prädikatenlogik erster Stufe müssen x und y Elemente des selben Universums sein. Du möchtest mittels Peano-Axiomen die natürlichen Zahlen axiomatisieren. Dein Universum soll also aus den natürlichen Zahlen bestehen. Wenn du R als Teilmengen-Beziehung auffasst, dann sagst du mit "∀x Rxy ⇒ Qx" unter anderem "Aus 5⊆3 folgt Q5". Welches der Peano-Axiome soll das sein? Mit anderen Worten: was ist deine  Interpretation von Q?

Comments

Vielen Dank für die Antwort, leuchtet ein, zumindest so halb :P An und für sich spricht doch nichts dagegen, dass sich Mengen, Elemente dieser Mengen und wiederum deren Elemente im selben Diskursuniversum befinden, schließlich ist "∈" ja bloß eine Relation, die zum Funktionieren der Mengenlehre nicht weiter definiert werden muss. Ist der springende Punkt also der, dass sich dasselbe Objekt in derselben Relation zwei mal an unterschiedlicher Stelle befindet?

x ∈ y ∈ z bzw.
∈(x, y) ∧ ∈(y, z)

Oder kommt den Mengen selbst eine Art "Sonderstellung" zu? Letzteres macht für mich wenig sinn, da sich die ZF-Mengenlehre selbst ja in der Prädikatenlogik erster Stufe interpretieren lässt.

Q könnte in meiner Frage unabhängig der Peano-Axiome bspw. ∀a Rab sein, wobei x dann entsprechend für b eingesetzt würde.

---

Hier ein paar Definitionen.

Definition (Term).

1. Jede Variable ist ein Term.
2. Wenn f ein n-stelliges Funktionssymbol ist, und t₁...t_n Terme sind, dann ist f(t₁, ..., t_n) ein Term.

Definition (Formel der Prädikatenlogik erster Stufe).

1. Ist R ein n-stelliges Relationssymbol und t₁...t_n Terme, dann ist Rt₁...t_n eine Formel der der Prädikatenlogik erster Stufe.
2. Sind φ und ψ Formeln der der Prädikatenlogik erster Stufe und x eine Variable, dann sind auch  ∃x φ, (¬φ) und (φ ∧ ψ) Formeln der der Prädikatenlogik erster Stufe.

Definition (Interpretation einer Prädikatenlogischen Formel erster Stufe). Eine Interpretation einer Formel φ ist eine Struktur bestehend aus

1. einem Universum U
2. einer Relation S_i⊆Uⁿ für jedes n-stellige Relationssymbol R_i, das in der Formel vorkommt
3. einer Funktion s_i : Uⁿ→U für jedes n-stellige Funktionssymbol f_i, das in der Formel vorkommt.
4. einer Belegung der freien Varaiblen, das heißt einer Abbildung b: V→U von der Menge der Varaiblen V in das Universum.
   

Aus einer Formel φ und einer dazu passenden Interpretation I kann man dann den Wahrheitswert von φ unter I bestimmen. Auf die Regeln, wie das geht, möchte ich hier nicht genauer eingehen. Aber auch so stellt sich die Frage, wie du auf Basis dieser Definitionen zum Beispiel einen vollständigen angeordneten Körper axiomatisieren möchtest. Angeordnete Körper sind offensichtlich kein Problem, aber vollständigkeit wird landläufig so formuliert, dass es zu zwei beliebigen Teilmengen M und N des angeordneten Körper, in denen alle Elemente von M kleiner als alle Elemente von N sind, es ein x gibt, das größer als alle Elemente von M und kleiner als alle Elemente von N ist. Das ist in Prädikantenlogik zweiter Stufe offensichtlich kein Problem, weil über M und N quantifiziert werden kann.

---

Verstehe ich richtig, dass eine Menge hier wie ein einstelliges Prädikat behandelt werden kann, welches genau dann wahr ist, wenn das Argument Teil der Menge ist? Das heißt es ist zwar in Ordnung in der Prädikatenlogik erster Stufe über Mengen zu quantifizieren, setzt aber eine Logik höherer Stufe voraus, sobald ich diese Mengen als Prädikat auf Argumente anwende?

Beispiel:

∀x Px ist ein gültiger Ausdruck der Prädikatenlogik erster Stufe, auch wenn x eine Menge ist, während

∀x ∀y Qxy → y∈x eine Logik höherer Stufe voraussetzt, da y∈x hier gleichbedeutend mit x(y) ist und somit über ein Prädikat quantifiziert wird?

---

Es gibt Subjekte aus einer Menge \(\omega\) und dann Praedikate aus \(\cal{P}(\omega\times\ldots\times\omega)\). Wenn Du hier eine Formel hinknallst, dann musst Du dazusagen, welche Variablen Subjektsvariablen und welche Praedikatsvariablen sein sollen. Ohne eine solche Angabe macht die Formel keinen Sinn, und man kann auch keinen nachtraeglich ergruenden. Wenn Du das hast, schaust Du, ob Quantifizierung ueber Praedikatsvariablen vorkommt. Wenn ja, dann Praedikatenlogik zweiter Stufe. Wenn nein, dann Praedikatenlogik erster Stufe.

---

> Verstehe ich richtig, dass eine Menge hier wie ein einstelliges Prädikat behandelt werden kann

Ja. Und mehrstellige Prädikate können wie Teilmengen des Kreuzprodukte des Universums behandelt werden.

> setzt aber eine Logik höherer Stufe voraus, sobald ich diese Mengen als Prädikat auf Argumente anwende?

Richtig.

> ∀x ∀y Qxy → y∈x eine Logik höherer Stufe voraussetzt

Zunächst ein mal ist festzuhalten, dass in meiner Definition von prädikatenlogischen Formeln weder → noch ∀ vorkommt. Beides kann leicht repariert werden, (φ→ψ) ist äquivalent zu ¬(φ ∧(¬ψ)) und ∀x φ ist äquivalent zu  ¬∃x (¬φ). Das komische ∈-Zeichen kann aber nicht mithilfe der vorhandenen Zeichen dargstellt werden. Dem Anschein nach handelt es sich bei dem Zeichen um ein zweistelliges Relationssymbol, dem dann in einer Interpretation eine Relation zugeordnet werden muss. Diese Relation muss aus U×U sein, wegen der Zweistelligkeit.

Answer 2

∀x Rxy ⇒ Qx

....

Nimmt man für R nun "... ist Teilmenge von ...", dann quantifiziert man doch über alle x, welche Teilmengen der Menge y sind, also über alle Teilmengen von y, oder?

Das kannst Du so machen und es ist immer noch Praedikatenlogik erster Stufe. Du darfst nur nicht noch zusaetzlich ueber die Elemente von x oder y quantifizieren, denn dann haettest Du schon zwei Stufen: Die Elemente der Mengen und die Mengen selber. Schau Dir das Induktionsaxiom an. Da wird sowohl ueber Mengen von natuerlichen Zahlen als auch ueber natuerliche Zahlen selber quantifiziert. Deshalb braucht man dafuer Praedikatenlogik zweiter Stufe, nicht weil man ueber Mengen quantifiziert. Wenn man nur das tut, gibt es nur eine Stufe und Praedikatenlogik erster Stufe reicht wie in Deinem Beispiel aus.