Ordinal algebras. Appendices by Chen-Chung Chang and Bjarni Jónsson. (English) Zbl 0072.00201

Tarski, Alfred

Studies in Logic and the Foundations of Mathematics. Amsterdam: North-Holland Publishing Co. 133 p. (1956).

Sei \(A\) ein Bereich von Dingen, die im weiteren mit \(a, b, \ldots,\) eventuell mit \(a_\kappa, b_\lambda, c_\mu\), usw. bezeichnet werden, wobei \(\kappa, \lambda, \mu, \nu\) Ordinalzahlen einschließlich \(\vartheta\) und \(\omega\) seien. In \(A\) komme ein ausgezeichnetes Element \(\emptyset\), vor und es seien in \(A\) eine einstellige Operation \({}^*\), eine zweistellige Operation \(\oplus\) und eine Operation \(\sum\), deren Argumente endliche oder nach \(\omega\) geordnete unendliche Folgen \([a_\kappa]\) von Elementen aus \(A\) sind, erklärt; gegen diese Operationen sei \(A\) abgeschlossen und es seien folgende Postulate erfüllt: (Zur Abkürzung benutzen wir die bekannten logischen Zeichen in der Formulierung).
I. \(\displaystyle\sum_{\kappa<0} a_\kappa = \emptyset\), \(\displaystyle\sum_{\kappa<1} a_\kappa = a_0\).
II. Assoziativität: \(\displaystyle\mu < \omega\, \& \,\nu\le \omega \rightarrow \sum_{\kappa<\mu + \nu} a_\kappa = \sum_{\kappa<\mu} a_\kappa \oplus \sum_{\kappa<\mu} a_{\mu + \kappa}\)
III. Verfeinerungspostulat: \(\displaystyle\sum_{\kappa<\omega} a_\kappa = b \oplus c \,\& \,c\ne \emptyset \rightarrow (\exists\ d) (\exists\ e) (\exists\ \mu) (\mu < \omega \,\& \,\sum_{\kappa<\mu} a_\kappa \oplus d = b \,\& \,a_\mu = d\oplus e \,\&\, e \oplus \sum_{\kappa<\omega} a_{\mu+1+\kappa} = c\).
IV. Restbildungspostulat: \(\displaystyle(\forall \kappa) (a_\kappa = b_\kappa \oplus a_{\kappa + 1}) \rightarrow (\exists\ c) (\forall \kappa) (a_\kappa = \sum_{\lambda<\omega} b_{\kappa+\lambda} \oplus c)\).
V. \(a^{**} = a\).
VI. \((a \oplus b)^* = b^* \oplus a^*\).
Ein solches System \(A\) von Dingen nennt Verf. eine „ordinal algebra“.
In Kap. 1 (und einem Appendix von Chen-Chung Chang) wird eine große Anzahl von Folgerungen aus diesem Postulatensystem hergeleitet, die in dem Sinne als arithmetisch bezeichnet werden, als sie Umformungen von Ausdrücken, gebildet mit den Grundoperationen, sowie Äquivalenzen zwischen solchen Ausdrücken etc. zum Inhalt haben, nicht aber Beziehungen zwischen verschiedenen Modellen des Postulatensystems usw. Viele dieser Gesetze sind aus der Literatur als Sätze über Ordnungstypen bekannt, worauf vom Verf. jeweils hingewiesen wird; hier erscheinen diese Sätze jedoch in einem wohlüberlegten deduktiven Rahmen gemeinsam als Folgerungen des Postulatensystems. Dieses erhält seine Stärke vor allem durch die Axiome III und IV, aber natürlich auch durch die Verwendung des Ordinalzahlbegriffes bis einschließlich \(\omega\) und des Begriffes der Folge von Elementen aus \(A\). Dadurch bekommt diese Theorie einen stark nichtelementaren Charakter und von diesem Standpunkt aus erscheint es vielleicht nicht als so günstig, von einer „Algebra“ zu sprechen, eine Sammelbezeichnung, die vielleicht auf elementare Axiomensysteme (über Operationen) zu beschränken wäre.
Im folgenden sei eine (subjektive) Auswahl aus den abgeleiteten Gesetzen (nicht in der Reihenfolge ihrer Ableitung) angegeben.
(1) Erklärt man \(\displaystyle \sum_{\kappa<\mu}{}^* a_\kappa =_{DF}\left(\sum_{\kappa<\mu} a_\kappa^*\right)^*\) und \(a\oplus^* b =_{Df} (a^+\oplus b^*)^*\) so ergibt sich speziell \(\emptyset^* = \emptyset\), \(a\oplus^* b = b\oplus a\), \(\displaystyle \sum_{\kappa<\nu}{}^* a_\kappa = \sum_{\kappa<\nu} a_{\nu-1-\kappa}\) mit \(\nu < \omega\) und man erhält aus einer gegebenen ordinal algebra bezüglich der mit \({}^*\) versehenen Operationen eine duale Algebra, die hinsichtlich der Abbildung \(f(x) = x^*\) isomorph der ursprünglichen ist.
(2) Postulat III gestattet (unter Verwendung des Auswahlaxioms) wie lt. Verf. W. Hanf bewies, folgende Verallgemeinerung: Sei \(\displaystyle \sum_{\kappa<\omega} a_\kappa = \sum_{\kappa<\omega} b_\kappa\), wobei in den Folgen \([a_\kappa]\) und \([b_\kappa]\) immer wieder von \(\emptyset\) verschiedene Glieder vorkommen mögen, dann gibt es eine unendliche Folge \([c_\kappa]\) und zwei strikt monoton steigende unendliche Folgen \([\mu_\kappa]\) und \([\nu_\kappa]\) von Ordinalzahlen \(< \omega\) derart, daß für jedes \(\kappa < \omega\), \(\displaystyle a_\kappa = \sum_{\lambda < \mu_{\kappa + 1} - \mu_\kappa} c_{\mu_\kappa +\lambda}\) und \(\displaystyle b_\kappa = \sum_{\lambda < \nu_{\kappa + 1} - \nu_\kappa} c_{\nu_\kappa +\lambda}\) ist.
(3) Das \(\nu\)-fache \(a\nu\) eines Elementes \(a\) wird als \(\displaystyle \sum_{\kappa<\nu} a_\kappa\), wobei alle \(a_\kappa = a\) sind, erklärt. Eine Kleiner-Gleichbeziehung \(\le\) wird durch folgende Definition eingeführt: \(a\le b \leftrightarrow_{Df}(\exists c) (a \oplus c = b)\); durch Dualisierung im Sinne von (1) erhält man \(a \le^* b \leftrightarrow (\exists c) (c\oplus a = b)\). Einige einfache Gesetze lauten: \[ a^* \nu = a \nu, \quad a\omega = a\oplus a\omega; \]
\[ \mu < \omega \,\&\, \nu < \omega \leftrightarrow a(\mu + \nu) = a\mu \oplus a\nu\,\&\, a(\mu\nu) = (a\mu)\nu; \]
\[ b\le \sum_{\kappa < \omega} a_\kappa \,\&\, b \ne \sum_{\kappa < \omega} a_\kappa \rightarrow (\exists \mu) \left(\mu < \omega \,\&\, b \le \sum_{\kappa < \mu} a_\kappa\right); \]
\[ \sum_{\kappa < \mu} a_\kappa = \emptyset \leftrightarrow (\forall \lambda) (\lambda < \mu \rightarrow a_\lambda = \emptyset); \]
\[ a\le b \,\&\, b\le^*a \rightarrow a=b, a\le c\,\&\, b\le c \rightarrow a\le b \vee b\le a, \]
\[ a\omega \le b \leftrightarrow (\forall \kappa)(\kappa < \omega \rightarrow a\kappa\le b). \]
(4) Kürzungsgesetze: \(\mu< \omega \,\&\, a \oplus c\mu = b \oplus c\mu \rightarrow a\oplus c = b \oplus c\), \(0 < \mu < \omega \,\&\, a\mu = b\mu \rightarrow a = b\) und analog für Ungleichungen.
(5) Absorptionsgesetze: \[ a\oplus b = b \leftrightarrow a\mu \oplus b = b \leftrightarrow a\oplus b\mu = b\mu \leftrightarrow a\omega \le b; \]
\[ a\oplus b\oplus c = b \leftrightarrow a\oplus b = b\oplus c = b \leftrightarrow a\omega \le b \,\&\, c^*\omega \le ^* b \leftrightarrow (\exists d) (a\omega \oplus d\oplus c^*\omega = b). \]
(6) Satz von Euklid: Seien \(\mu, \nu < \omega\) relativ prim und \(a\mu = b\nu\), dann gibt es ein \(c\), so daß \(a = c\nu\) und \(b = c\mu\).
(7) Die Menge \(RC\) aller „rekursiven“ Elemente von \(A\) wird als Durchschnitt aller Mengen \(X\subseteq A\), die den folgenden drei Bedingungen genügen, erklärt:
i) \((\forall a) (a = x\oplus y \,\&\, y\ne\emptyset \rightarrow x\in X .\rightarrow. a\in X)\),
ii) \((\forall a) (a = x\oplus y \,\&\, x\ne\emptyset \rightarrow y\in X .\rightarrow. a\in X)\),
iii) \((\forall a) (\forall b) (a\in X\,\&\, b\in X \rightarrow a\oplus b\in X)\).
Es zeigt sich, daß \(RC \subseteq A\) selbst eine ordinal algebra und zwar eine subalgebra von \(A\) ist. Ferner ergibt sich (mit Auswahlaxiom) das folgende Kriterium für die Gültigkeit des kommutativen Gesetzes:
\[ \begin{split} a\in RC \vee b\in RC .\rightarrow. a\oplus b = b\oplus a\leftrightarrow (\exists c) (b\omega \oplus c\oplus b^*\omega = a) \vee \\ (\exists c) (a\omega \oplus c \oplus a^*\omega = b) \vee (\exists c) (\exists \mu) (\exists \nu) (\mu < \omega \,\&\, \nu< \omega \,\&\, a = c\mu \,\&\, b = c\nu). \end{split} \]
(8) Neben anderen Ergebnissen wird in dem Appendix von Chang zu dem vom Verf. bewiesenen Satz \(a\in RC \,\&\, a = a\oplus b\oplus a \rightarrow a = \emptyset\) die folgende Verallgemeinerung gezeigt: \[ a\in RC \,\&\, a\mu = c \oplus \sum_{\kappa < \mu} (a\oplus b_\kappa) \oplus a \oplus d \rightarrow a= \emptyset. \]
Um in die Vielfalt solcher Gesetze eine gewisse Übersicht zu bringen, bemüht sich der Verf., gewisse Gestalten arithmetischer Gesetze, wie z. B. die unter (4) und (5) genannten, herauszuheben. Zusätzlich wäre es erwünscht gewesen, wenn gleich zu Anfang ein oder zwei einfache, aber doch genügend reichhaltige Modelle dieser Theorie, gebildet z. B. aus Wohlordnungstypen und deren Inversen, angegeben worden wären, an Hand derer der Leser eine gewisse Konkretisierung und Bewertung der Sätze erhalten hätte.
Im Kap. 2, zu dem ein Appendix von Bjarni Jónsson eine Ergänzung darstellt, führt Verf. zunächst folgende Operationen für Typen von (zweistelligen) Relationen ein. Der leeren Relation \(\Lambda\) wird der Typus \(\emptyset\) zugeordnet; als \(\alpha^*\) gilt der Typus der Relationen \(S\), für die \(\alpha\) der Typus ihrer Konversen ist. Zur Erklärung der Summe \(\alpha + \beta\) zweier Typen \(\alpha, \beta\) von Relationen \(R, S\) werden diese zuerst in einfacher Weise in zwei zu \(R\) bzw. \(S\) typengleiche „fremde“ Relationen \(R'\) bzw. \(S'\) überführt, d. h. Relationen für die – \(F(R) \) bezeichne das Feld von \(R\) – \(F(R') \cap F(S') = \Lambda\) ist. \(\alpha + \beta\) soll dann der Typus der Relationen \(T\) sein, die sich mit zwei fremden Relationen \(R,S\) des Typus \(\alpha, \beta\) in der Form \(T = R + S\), mit \(R + S =_{Df} R \cup S \cup [F(R)\times F(S)]\), darstellen lassen. In analoger Weise wird die Summe \(\displaystyle \sum_{\kappa < \mu} \alpha_\kappa\) einer wohlgeordneten endlichen oder unendlichen Folge \([\alpha_\kappa]\) von Typen \(\alpha_\kappa\) von Relationen \(R_\kappa\) erklärt.
Die definierten Begriffe \(a\nu, a \le b, a \le^* b\) und „rekursives Element“ aus Kap. 1 gestatten nicht nur eine formale Übertragung, sondern haben eine genuine Deutung im Bereich der Relationen, z. B. heiße \(R\) ein Anfangs- bzw. Endstück einer Relation \(S\), wenn es eine Relation \(T\), die zu \(R\) fremd ist, gibt, so daß \(R + T = S\) bzw. \(T + R = S\) ist. Für Typen \(\alpha, \beta\) von Relationen \(R, S\) drückt sich dieser Sachverhalt durch \(\alpha \le \beta\) bzw. \(\alpha \le^* \beta\) aus. Ein Satz aus Kap. 1 wie \(a\le b \,\&\, a \le^*b \rightarrow a = b\) erhält in der Relationensprache die Deutung: Sind \(R\) und \(S\) reflexive Relationen und \(R\) isomorph einem Anfangstück von \(S\) und \(S\) isomorph einem Endstück von \(R\), dann sind \(R\) und \(S\) isomorph.
In der ordinal algebra \(OT\) bilden die Typen von „verstreuten“ Relationen, das sind diejenigen, die keine dichte Teilrelation enthalten, den Bereich der rekursiven Elemente.
Für die ordinal algebra \(RT\) stellt sich der Bereich der rekursiven Elemente als Bereich aller Typen von Relationen, die sich in gewisser Weise als Summe unzerlegbarer Typen von Relationen darstellen lassen, heraus. Dabei heißt eine Relation unzerlegbar hinsichtlich der Summenbildung \(+\), wenn \(R \ne \Lambda\) und für alle zueinander fremden Relationen \(S\) und \(T\), für die \(R = S+T\) gilt, \(S = \Lambda\) oder \(T = \Lambda\) folgt. Daß jeder Typus einer reflexiven Relation in bestimmter Weise eindeutig als Summe von unzerlegbaren Typen von Relationen darstellbar ist, bildet das Hauptergebnis des Appendix von Jónsson. Abschließend erwähnen der Verf. und Jónsson noch Verallgemeinerungen des Typenbegriffs einer Relation derart, daß man sich von der Einschränkung auf Typen reflexiver Relationen für die Anwendung der Theorie in Kap. 1 befreien kann.
Die ganze Monographie ist klar abgefaßt und enthält eine große Anzahl interessanter Zusatzbemerkungen und Hinweise auf Zusammenhänge mit anderen algebraischen Fragen.

Reviewer: Gert H. Müller

MSC:

03-02	Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03E10	Ordinal and cardinal numbers