Ω-Regel

Die ω-Regel, auch Ω-Regel, 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 ${\displaystyle \omega }$ oder ${\displaystyle \omega _{0}}$ bezeichnet wird.

Formulierung

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

Für jede Formel ${\displaystyle \phi (n)}$ gelte

${\displaystyle {\frac {\;\phi (0)\qquad \phi (1)\qquad \phi (2)\qquad \cdots \;}{\forall n.\phi (n)}}\,\Omega _{\phi }}$

Strenggenommen gibt es nicht eine einzelne ω-Regel, sondern eine ω-Regel für jede geeignete Aussage ${\displaystyle \phi }$, daher sprechen manche Autoren in solchen Fällen nicht von einer Regel, sondern einem Regelschema.

Dabei bedeutet die Notation ${\displaystyle \phi (n)}$, dass ${\displaystyle \phi }$ eine Formel der betrachteten Sprache ist und die Variable ${\displaystyle n}$ darin nur frei vorkommt. Die Instanzen ${\displaystyle \phi (0)}$ usw. stehen für ${\displaystyle \phi [0/n]}$, also für eine Version der Formel ${\displaystyle \phi }$, in der alle Vorkommen von ${\displaystyle n}$ durch eine geeignete Darstellung von ${\displaystyle 0}$ und allen anderen Konstanten für natürliche Zahlen ersetzt wurden. In der Sprache der Peano-Arithmetik ist beispielsweise für ${\displaystyle 0}$ ein Konstantensymbol vorhanden, für ${\displaystyle 1}$, ${\displaystyle 2}$ usw. wird die Nachfolger-Funktion ${\displaystyle S}$ auf dem Konstantensymbol ${\displaystyle 0}$ iteriert, also ${\displaystyle 1=S(0)}$, ${\displaystyle 2=S(S(0))}$ usw.

Die ω-Regel sollte n​icht mit d​er Induktionsregel (genauer: d​em Induktionsschema)

${\displaystyle {\frac {\,\phi (0)\qquad \forall n.\phi (n)\to \phi (S(n))\,}{\forall n.\phi (n)}}\,{\text{Ind}}_{\phi }}$

verwechselt werden. Die Induktionsregel hat genau zwei Prämissen: ${\displaystyle \phi (0)}$ und ${\displaystyle \forall n.\phi (n)\to \phi (S(n))}$.

Problematik

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

Definitionen:

• Eine Regel ${\displaystyle V/\kappa }$ heißt finitär (oder endlich-stellig), wenn ihre Voraussetzungsmenge ${\displaystyle 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 i​n der mathematischen Praxis betrachteten Regelsysteme s​ind finitär. Das i​st beispielsweise notwendig, w​enn alle Voraussetzungen v​on einem Computersystem überprüft werden sollen. Viele Regelsysteme werden m​it dem Hintergedanken entworfen, d​ass Ableitungen automatisiert überprüft werden können.

Auch formal betrachtet haben finitäre Regelsysteme erhebliche Vorteile. Betrachtet man den Ableitungsoperator ${\displaystyle 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 ${\displaystyle F}$ von Formeln ist ${\displaystyle \phi \in A(F)}$ genau dann, wenn es eine Regel ${\displaystyle V/\phi }$ mit ${\displaystyle V\subseteq F}$ gibt, also wenn es eine Regel gibt, deren Voraussetzungen alle in ${\displaystyle F}$ liegen und deren Konklusion genau ${\displaystyle \phi }$ ist. Dabei ist der kleinste Fixpunkt von ${\displaystyle A}$ von Interesse, also die kleinste Formelmenge ${\displaystyle F}$, für die ${\displaystyle 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 ${\displaystyle \mu (A)}$.

Damit ein solcher Fixpunkt überhaupt existiert, muss der Operator monoton sein, also für ${\displaystyle F\subseteq G}$ muss auch ${\displaystyle 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 f​olgt aus d​em Fixpunktsatz v​on Kleene:

${\displaystyle \mu (A)=\bigcup _{n\in \mathbb {N} }A^{n}(\emptyset )=A(\emptyset )\cup A(A(\emptyset ))\cup \cdots }$

Dann i​st auch j​eder fundierte Ableitungsbaum v​on endlicher Höhe.

Eine Voraussetzung dafür ist, dass

${\displaystyle A{\Bigl (}\bigcup _{n\in \mathbb {N} }F_{n}{\Bigr )}=\bigcup _{n\in \mathbb {N} }A(F_{n})}$

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

Eine erheblich weniger konkrete Darstellung d​es kleinsten Fixpunkts liefert d​er Satz v​on Knaster-Tarski. Es gilt

${\displaystyle \mu (A)=\bigcap \{\,F{\text{ Formel}}\,|\,A(F)\subseteq F\,\}}$

auch m​it ω-Regel.

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

${\displaystyle B_{\omega }={\frac {\,{\stackrel {\underset {|}{B_{0}}}{\phi (0)}}\qquad {\stackrel {\underset {|}{B_{1}}}{\phi (1)}}\qquad {\stackrel {\underset {|}{B_{2}}}{\phi (2)}}\qquad \cdots \,}{\forall n.\phi (n)}}\,\Omega _{\phi }}$

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

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

${\displaystyle (\forall n.\phi (n))\in A{\Bigl (}\bigcup _{n\in \mathbb {N} }A^{n}(\emptyset ){\Bigr )}\setminus \bigcup _{n\in \mathbb {N} }A^{n}(\emptyset )\subseteq \mu (A)}$

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

Ein konkretes Beispiel für ein solches ${\displaystyle \phi }$ ist der Satz von Goodstein.

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

${\displaystyle {\frac {\,\{\phi (t)\}_{t{\text{ ein Term}}}\,}{\forall x.\phi (x)}}}$,

wobei die Voraussetzungsmenge aus den Varianten der Formel ${\displaystyle \phi }$ besteht, in der die Variable ${\displaystyle x}$ durch jeden Term der Sprache ersetzt wird.