Premium
Entscheidbarkeit von Theorien in Logiken mit verallgemeinerten Quantoren
Author(s) -
Herre Heinrich,
Wolter Helmut
Publication year - 1975
Publication title -
mathematical logic quarterly
Language(s) - German
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19750210131
Subject(s) - citation , computer science , information retrieval , library science
A. MOSTOWSKI und A. TARSKX haben in [7] die Entscheidbarkeit der elementaren Thwrie der wohlgeordneten Mengen mit Hilfe der Elimination der Quantoren nachgevric~cn. Wegen der dort' vorgenommenen definitorischen Erweiterung des zugrundegelcgt en Formalismus durch neue zweistellige Relationssymbole ergab sich beim Eliminat ionsverfahren tine Vielzahl von Fallunterscheidungen, so da13 der volle Beweis nicht vcroffentlicht wurde. M. RABIN hat u. a. in [8] mit automatentheoretischen Hilfsmitt eln die Entgcheidbarkeit der Nachfolgertheorie mit mehreren Nachfolgern in der schwachen monadischen Logik der 2. Stufe nachgewiesen und als Korollar die En t schcidbarkeit dcr Theorie der wohlgeordneten Mcngcn in -Epo erhalten. Hierbei ist 9, ( x Ordinalzahl) cin Formalismus, der aus dem elementaren Formalismus 2' durch Hinzimahmc eines neuen Quantors Q, hcrvorgcht, welcher als Machtigkeitsquantor ,,es pibt N, viele . . ." intcrpretiert wird (vgl. A. MOSTOWSKI [S]). I n [9] hat A. B. SLOMSON mit spieltheoretischen Hilfsmitteln gezeigt , daB die Theoric der wohlgeordnetcn Menpcm auch in Y, und in Y C entscheidbar ist, falls x > 0 und LZC aus 9 durch Hinzunahme des h ~ ~ a Q u a n t o r s Q(.hervorgeht.