Entscheidbarkeit der Theorie der Linearen Ordnung in Logiken mit Mächtigkeitsquantoren bzw. mit Chang-Quantor

✍ Scribed by Heinrich Herre; Helmut Wolter

• Publisher: John Wiley and Sons
• Year: 1979
• Tongue: English
• Weight: 834 KB
• Volume: 25
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19790251906

✦ Synopsis

ENTSCHEIDBARKEIT DER THEORIE DER LINEAREN ORDNUNG I N LOGIKEN MIT ~CHTIGKEITSQUANTOREN BZW. MIT CHANG-QUANTOR von HEINRICH HERRE und HELMUT WOLTER in Berlin (DDR) 1. Einleitung I n [l] und [ 2 ] ist die Entscheidbarkeit der Theorie der linearen Ordnung in dcr Logik LQ,, mit dem zusatzlichen Quantor ,,es gibt N, viele" gezeigt worden, wobei N, als regular vorausgesetzt wurde. Fur x = 0 folgt dieses Resultat schon aus den Ergebnissen von M. 0. RABIN [6]. Fur x = 1 hat H. P. TUSCHIK [7] einen anderen Beweis angegeben. Er zeigte weiterhin in [8], da13 die in Frage stehende Theorie entscheidbar bleibt, wenn man sie in einer Logik mit endlich vielen Quantoren Q,, n < 0 , betrachtet. Die vorliegende Arbeit ist eine Weiterfuhrung von [l] und [ 2 ] fur den Pall, daB K, singular ist, woraus dann schlieSlich die Entscheidbarkeit der Theorie der linearen Ordnung in LQ* fur beliebiges x und in LQ, folgt, falls QC der Chang-Quantor i&. Bhnlich wie in [a] wird mit Hilfe gewisser Erzeugungsregeln eine rekursiv aufzahlbare Menge M , von Ordnungstypen definiert, deren LQw-Theorien rekursiv aufzahlbar sind. Die hier benotigten Operationen sind jedoch komplizierter als die in [2]. Unter Verwendung von spieltheoretischen Methoden wird gezeigt, da13 M , in der Klasse aller geordneten Mengen bezuglich LQ_ dicht liegt! Aus der Vollstandigkeit von LQo> folgt schlieBlich die Behauptung.