Die Ausdrücke und Formeln von ℒ

Definition (Ausdrücke)

Ein Ausdruck von ℒ ist eine Liste s₀ s₁ s₂ … s_n, in der jedes s_i ein Zeichen von ℒ ist.

So ist z. B. )v₁=↔))∀ ein Ausdruck von ℒ.

Wir verwenden auch alle Buchstaben, die wir bislang für Mengen verwendet haben, als Variablenzeichen. Dies dient lediglich der Bequemlichkeit. Schreiben wir im Folgenden z. B. „sei A ein Ausdruck der Form x = y“, so sind mit x, y immer Variablenzeichen gemeint, d. h. es gibt i, j, sodass A die Zeichenkette v_i = v_j ist.

Definition (Primformeln und Formeln)

Die Primformeln oder atomaren Formeln von ℒ sind festgelegt durch:

(i)	Jeder Ausdruck der Form „x = y“ oder „x  ∈  y“ ist eine Primformel.

(ii)	Keine weiteren Ausdrücke sind Primformeln.

Die Formeln von ℒ sind festgelegt durch:

(i)	Jede Primformel ist eine Formel.

(ii)	Ist φ eine Formel, so ist auch ¬ φ eine Formel.

(iii)

Sind φ und ψ Formeln, so sind auch (φ ∧ ψ), (φ ∨ ψ), (φ → ψ) und (φ ↔ ψ) Formeln.

(iv)	Ist x eine Variable und φ eine Formel, so sind auch ∀x φ und ∃x φ Formeln.

(v)	Keine weiteren Ausdrücke sind Formeln.

Im Folgenden verwenden wir zumeist kleine griechische Buchstaben für Formeln.

Damit sind die wesentlichen Bestandteile von ℒ definiert. ℒ wird auch als die Prädikatenlogik erster Stufe für die Symbolmenge {  ∈  } bezeichnet.

Für die Junktoren würden bereits z. B. ¬ und ∧ genügen, denn ∨, →, ↔ lassen sich mit diesen Junktoren in ihrer gewünschten Bedeutung einführen. Ebenso ließe sich z. B. der Existenzquantor mit Hilfe des Allquantors einführen:

	φ ∨ ψ	= ¬ (¬ φ ∧ ¬ ψ),
	φ → ψ	= ¬ φ ∨ ψ,
	φ ↔ ψ	= (φ → ψ) ∧ (ψ → φ),
	∃x φ	= ¬ ∀x ¬ φ.

Beschränkt man sich in der Sprache auf ¬, ∧ und ∀, so sind diese vier Gleichungen einfach Definitionen von ∨, →, ↔, ∃. In unserer reichhaltigeren Sprache sind φ ∨ ψ und ¬ (¬ φ ∧ ¬ ψ) usw. verschiedene Formeln, die jedoch logisch äquivalent sind, d. h. wir können φ ∨ ψ genau dann formal beweisen, wenn wir ¬ (¬ φ ∧ ¬ ψ) formal beweisen können. (Zum formalen Beweisbegriff s.u.)

Wir wollen Klammern wo immer möglich sparen, und vereinbaren hierzu die folgende Bindungsstärke der Quantoren und Junktoren:

¬, ∧, ∨, →, ↔ (in absteigender Bindungsstärke).

Also bedeutet φ ∧ ψ → χ die Formel (φ ∧ ψ) → χ, und nicht φ ∧ (ψ → χ).

Weiter schreiben wir oft

∀x₁ ∀x₂ … ∀x_n φ kurz als ∀x₁, … , x_n φ.

Ebenso für den Existenzquantor.

Unsere Sprache erlaubt keine Formeln der Gestalt ∀x  ∈  y φ, ∃x  ∈  y φ, wie sie in obiger Analyse von „R ist eine Relation“ auftauchen. Wir führen hierzu zwei Abkürzungen ein, die sehr häufig verwendet werden:

	∀x  ∈  y φ	= ∀x (x  ∈  y → φ),
	∃x  ∈  y φ	= ∃x (x  ∈  y ∧ φ).