Ω-Regel

Die ω-Regel, auch Carnap’s Rule, ist eine unendlich-stellige Ableitungs- oder Schlussregel (genauer: ein Regelschema) in verschiedenen erweiterten Regelsystemen oder Kalkülen der Arithmetik, mit der All-Aussagen über natürliche Zahlen abgeleitet werden können. Der griechische Buchstabe ω ist ein übliches Symbol für die kleinste unendliche Ordinalzahl, die mit $ω$ oder $ω_{0}$ bezeichnet wird.

Formulierung

Die ω-Regel^[1] kommt in Kalkülen vor, deren Sprache die natürlichen Zahlen hinreichend gut beschreiben kann, sodass die Symbole $0$ (null), $1$ (eins), $2$ (zwei) usw. eine sinnvolle Bedeutung haben. In der üblichen Darstellung von Schlussregeln hat die ω-Regel folgende Definition:

Für jede Formel $ϕ (n)$ gelte

\frac{ϕ (0) ϕ (1) ϕ (2) \dots}{\forall n . ϕ (n)} Ω_{ϕ}

Strenggenommen gibt es nicht eine einzelne ω-Regel, sondern eine ω-Regel für jede geeignete Aussage $ϕ$ , daher sprechen manche Autoren in solchen Fällen nicht von einer Regel, sondern einem Regelschema.^[2]

Dabei bedeutet die Notation $ϕ (n)$ , dass $ϕ$ eine Formel der betrachteten Sprache ist und die Variable $n$ darin nur frei vorkommt. Instanzen wie $ϕ (0)$ stehen für $ϕ [0 / n]$ , also für eine Version der Formel $ϕ$ , in der alle Vorkommen von $n$ durch den links vom Schrägstrich stehenden Term ersetzt wurden; im Beispiel $ϕ [0 / n]$ ist das eine geeignete Darstellung von $0$ . In der Sprache der Peano-Arithmetik ist beispielsweise für $0$ ein Konstantensymbol vorhanden, für $1$ , $2$ usw. wird die Nachfolger-Funktion $S$ auf dem Konstantensymbol $0$ iteriert, also $1 = S (0)$ , $2 = S (S (0))$ usw.

Weil unendlich viele Prämissen erst als herleitbar nachgewiesen sind, bevor auf die Schlussformel übergegangen werden darf, nennt man dieses Regelschema auch halbformal oder einen Halbformalismus.^[3]

Die ω-Regel sollte nicht mit der Induktionsregel (genauer: dem Induktionsschema)

\frac{ϕ (0) \forall n . ϕ (n) \to ϕ (S (n))}{\forall n . ϕ (n)} {Ind}_{ϕ}

verwechselt werden. Die Induktionsregel hat genau zwei Prämissen: $ϕ (0)$ und $\forall n . ϕ (n) \to ϕ (S (n))$ ; die ω-Regel hat jedoch unendlich viele Prämissen.

Problematik

Allgemein haben Schlussregeln die Form $V / κ$ , wobei $V$ eine Menge von Formeln ist, die als Voraussetzung interpretiert werden und $κ$ als die Konklusion. Die ω-Regel (genauer: jede Instanz des ω-Regelschemas) hat allerdings unendlich viele Voraussetzungen: Konkret ist $V = {ϕ (0), ϕ (1), ϕ (2), \dots}$ .

Definitionen:

Eine Regel $V / κ$ heißt finitär (oder endlich-stellig), wenn ihre Voraussetzungsmenge $V$ endlich ist.
Eine Menge von Regeln (Regelsystem) heißt finitär, wenn jede einzelne Regel finitär ist; dabei ist unerheblich, ob die Menge der Regeln selbst endlich ist (meist ist sie es nicht).

Die meisten in der mathematischen Praxis betrachteten Regelsysteme sind finitär. Das ist beispielsweise notwendig, wenn alle Voraussetzungen von einem Computersystem überprüft werden sollen. Viele Regelsysteme werden mit dem Hintergedanken entworfen, dass Ableitungen automatisiert überprüft werden können.

Auch in formaler Hinsicht haben finitäre Regelsysteme erhebliche Vorteile. Betrachtet man den Ableitungsoperator $A$ zu einem Regelsystem, der eine Menge von Formeln auf die Menge der mit dem Regelsysteme ableitbaren Formeln abbildet, das heißt, für eine Menge $F$ von Formeln ist $ϕ \in A (F)$ genau dann, wenn es eine Regel $V / ϕ$ mit $V \subseteq F$ gibt, also wenn es eine Regel gibt, deren Voraussetzungen alle in $F$ liegen und deren Konklusion genau $ϕ$ ist. Dabei ist der kleinste Fixpunkt von $A$ von Interesse, also die kleinste Formelmenge $F$ , für die $F = A (F)$ gilt, da er genau die Formeln enthält, für die es einen fundierten Ableitungsbaum gibt. (Fundiert heißt, dass jeder Zweig im Ableitungsbaum endlich ist.) Für diesen kleinsten Fixpunkt schreibt man $μ (A)$ .

Damit ein solcher Fixpunkt überhaupt existiert, muss der Operator monoton sein, also für $F \subseteq G$ muss auch $A (F) \subseteq A (G)$ gelten. (Mit mehr Annahmen darf es nicht weniger Konklusionen geben.) Jeder Regeloperator ist monoton, solange keine Regeln existieren, die Urteile aufheben, was in üblichen Regelsystemen nicht der Fall ist.

Für finitäre Regelsysteme folgt aus dem Fixpunktsatz von Kleene:

μ (A) = ⋃_{n \in ℕ} A^{n} (\emptyset) = A (\emptyset) \cup A (A (\emptyset)) \cup \dots

Dann ist auch jeder fundierte Ableitungsbaum von endlicher Höhe.

Eine Voraussetzung dafür ist, dass

A (⋃_{n \in ℕ} F_{n}) = ⋃_{n \in ℕ} A (F_{n})

für alle aufsteigenden Ketten $F_{1} \subseteq F_{2} \subseteq \dots$ von Formelmengen gilt. (Mit dem Vereinigungssymbol als Grenzwert gelesen, bedeutet die Voraussetzung, dass der Operator $A$ mit Grenzwerten vertauschbar ist. Daher wird diese Eigenschaft als Stetigkeit bezeichnet.) Mit der ω-Regel schwächen sich aber die Eigenschaften des Ableitungsoperators $A$ auf $⋃_{n \in ℕ} A (F_{n}) \subseteq μ (A)$ ab.

Eine erheblich weniger konkrete Darstellung des kleinsten Fixpunkts liefert der Satz von Knaster-Tarski. Es gilt

μ (A) = ⋂ {F Formel | A (F) \subseteq F}

auch mit ω-Regel.

Durch die ω-Regel können unendlich hohe (weiterhin fundierte) Ableitungsbäume entstehen. Für ein einfaches Beispiel für diesen Fall betrachtet man eine Formel $ϕ$ für die gilt, dass der Ableitungsbaum $B_{n}$ von $ϕ (n)$ die Höhe $n$ (oder größer) hat. Da insbesondere $ϕ (n)$ für jedes $n$ ableitbar ist, kann die ω-Regel für $ϕ$ angewendet werden. Der resultierende Ableitungsbaum $B_{ω}$ sieht so aus:

B_{ω} = \frac{\overset{\underset{|}{B_{0}}}{ϕ (0)} \overset{\underset{|}{B_{1}}}{ϕ (1)} \overset{\underset{|}{B_{2}}}{ϕ (2)} \dots}{\forall n . ϕ (n)} Ω_{ϕ}

Der resultierende Baum $B_{ω}$ hat unendliche Höhe, denn für jede infragekommende endliche Höhe $n$ ist mit dem Teilbaum $B_{n}$ plus der Anwendung der ω-Regel die Höhe von $B_{ω}$ mindestens $n + 1$ .

Sind die Ableitungen $B_{n}$ von minimaler Höhe (das heißt, $ϕ (n)$ kann nicht durch einen kleineren Baum als $B_{n}$ abgeleitet werden), so ist

(\forall n . ϕ (n)) \in A (⋃_{n \in ℕ} A^{n} (\emptyset)) ∖ ⋃_{n \in ℕ} A^{n} (\emptyset) \subseteq μ (A)

und insbesondere ist $\forall n . ϕ (n)$ dann nicht ohne ω-Regel aus dem Kalkül beweisbar.

Ein konkretes Beispiel für ein solches $ϕ$ ist der Satz von Goodstein im Kontext der Peanoaxiome plus ω-Regel.

Verallgemeinerungen

In allgemeineren Fassungen ist die ω-Regel nicht auf die natürlichen Zahlen zugeschnitten, sondern läuft über alle Terme der betrachteten Sprache. So formuliert ist die ω-Regel

\frac{{ϕ (t)}_{t ein Term}}{\forall x . ϕ (x)} Ω_{ϕ}

,

wobei die Voraussetzungsmenge aus den Varianten der Formel $ϕ$ besteht, in der die Variable $x$ durch jeden Term der Sprache ersetzt wird.

Weblinks

Carnap Rule in der Encyclopedia of Mathematics

Literatur

Einzelnachweise

↑ Die summative Induktion in der Form der ω-Regel hat David Hilbert 1931 (Math. Ann. 104 (1931), S. 485–494) eingeführt, nachdem er den Gödelschen Beweis für die ω-Unvollständigkeit der axiomatisch aufgebauten Arithmetik kennengelernt hatte (siehe auch Hilberts Werke, Band III, S. 193 und S. 215).
↑ Gerrit Haas: Induktion, unendliche. In: Jürgen Mittelstraß (Hrsg.): Enzyklopädie Philosophie und Wissenschaftstheorie. Zweite Auflage. Band 3, S. 596 f.
↑ Kurt Schütte: Beweistheorie, 1960, S. 168

[1] Die summative Induktion in der Form der ω-Regel hat David Hilbert 1931 (Math. Ann. 104 (1931), S. 485–494) eingeführt, nachdem er den Gödelschen Beweis für die ω-Unvollständigkeit der axiomatisch aufgebauten Arithmetik kennengelernt hatte (siehe auch Hilberts Werke, Band III, S. 193 und S. 215).

[2] Gerrit Haas: Induktion, unendliche. In: Jürgen Mittelstraß (Hrsg.): Enzyklopädie Philosophie und Wissenschaftstheorie. Zweite Auflage. Band 3, S. 596 f.

[3] Kurt Schütte: Beweistheorie, 1960, S. 168

[1]

[2]

[3]

Ω-Regel

Inhaltsverzeichnis

Formulierung

Problematik

Verallgemeinerungen

Weblinks

Literatur

Einzelnachweise

Navigationsmenü

Ω-Regel

Formulierung

Problematik

Verallgemeinerungen

Weblinks

Literatur

Einzelnachweise

Navigationsmenü

Suche