ESTSCHEIDBARBEIT DER THEORIE DER LINEBREN ORDNUNG I N LQ1 von H. HERRE und H. WOLTER in Berlin (DDR) 1. Einleitung I n [l] zeigte A. EHRENFEUCHT die Entscheidbarkeit der elementaren Theorie der linearen Ordnung. H. LA~CHLI und J. LEONARD erhielten in [3] mit anderen Methoden das gleiche Ergebnis. Spater zeigten LAUCHLI [2] und M. RABIN [5], dal3 die Theorie der linearen Ordnung sogar in der monadischen schwachen Logik bzw. die der abzahlbaren Modelle in der monadischen Logik 2. Stufe entscheidbar ist. S. SHELAH bewies in [6] die Unentscheidbarkeit der Theorie der Ordnung der reellen Zahlen in der 2. Stufe und damit auch die Unentscheidbarkeit der Theorie aller geordneten Mengen in dieser Logik . Es erhebt sich nun die Frage. ob die Klasse der geordneten Mengen in den Logiken LQ eine entscheidbare Theorie besitzt, wobei L eine elementare Logik mit einem zweistelligen Relationenzeichen fur die Ordnung ist und LQ aus L durch Hinzunahme eines Machtigkeitsquantors Q entsteht.
Fiir Q = Qo (es gibt unendlich viele, so dup . . .) folgt die Entscheidbarkeit aus den Ergebnissen in [2], denn in der schwachen Logik 2. Stufe ist Qo durch Qoz ~( x ) +-+ 3X VZ(X E X c-* ~( x ) ) definierbar, wobei ~( x ) ein elementarer Ausdruck und X eine Mengenvariable ist. beantwortet. Fur Q = Q1 wird die Frage der Entscheidbarkeit in der vorliegenden Arbeit positiv Die Beweisidee entspricht im wesentlichen der in [3]. Mit Hilfe gewisser Erzeugungsregeln wird eine rekursiv aufzahlbare Menge M von Ordnungstypen gebildet, deren LQ1-Theorien rekursiv aufzahlbar sind. Unter Verwendung von spieltheoretischen Methoden wird gezeigt, daB M in der Klasse aller geordneten Mengen bzgl. LQl dicht liegt, d. h., daB eine in einer geordneten Menge erfiillbare Aussage schon in einem Element aus N erfiillt wird. Aus der Vollstandigkeit von LQ, erhalt man schliel3lich die Entscheidbarkeit der in Frage stehenden Theorie. Die in [3] verwendeten Methoden und Ergebnisse miissen fur das vorliegende Problem auf Grund der starkeren Ausdrucksfahigkeit von LQI an vielen Stellen stark modifiziert und verfeinert werden (vgl. [7]).
Fur die metatheoretischen Betrachtungen setzen wir die Zermelo-Fraenkel-Mengenlehre mit Kontinuumhypothesel) voraus, unabhiingig davon, ob alle Axiome wirklich benotigt werden. Kurdinalzahleiz seien ordinale Anfangszahlen. 1) Wir benotigen nur, daI3 eine geordnete Menge A der Machtigkeit o1 existiert, so daI3 auch jedes Teilintervall von A die Machtigkeit o1 besitzt und daI3 es eine abzahlbare in A dicht liegende Teilmenge gibt.
18 Ztschr. f. math. Logik