Eine Bemerkung Zum Reduktionstyp ∀3 ∃(0, 1)

✍ Scribed by Michael Deutsch

• Publisher: John Wiley and Sons
• Year: 1987
• Tongue: English
• Weight: 379 KB
• Volume: 33
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19870330213

✦ Synopsis

ETNE BEMERKUNG ZUM REDUKTIONSTYP V3 3"(0,1) von MICHAEL DEUTSCH in Bremen (BRD) Im AnschluB an [2] so11 auch fur den wohlbekannten Reduktionstyp V3 3"(0, 1) eine einfache Interpretationsmoglichkeit der einzigen Pradikatenvariableii angegeben werden. Mit der gleichen Methode gelingt es zudem, alle e-stelligen rekursiv aufzahlbaren bzw. koaufzahlbaren Pradikate durch einen Ausdruck aus V3 3-( = ; Q , 1) spektral darzustellen, wobei ebenfalls fur den Ausdruck ein einfaches Standardmodell angegeben werden kann. Das Gleichheitszeichen kann bei geeigneter Modifikation des Begriffs der spektralen Darstellung eliminiert werden. Zu den Bezeichnungen und Begriffen vgl. [a]. Definition. 1. Wir verwenden das folgende mengentheoretische Model1 N E %TI der 'naturlichen Zahlen :

3. Uber einer beliebigen transitiven Teilmenge U %TI schreiben wir z € * y G y * O A ( Z € y V z = y ) . S a t z 1. Z u jedem Ausdruck u der Pradikatenlogik kann man effektiv einen Ausdruck aus V3 3"(0, 1) angeben mit 1) a ist erfiillbar o ist erfullbar 0 / 3 ist iiber einer transitiven Teilmenge U E mit Interpretation von E durch E* erfiillbar. 2) a ist endlich erfiillbar u /3 ist endlich erfiillbar 0/3 ist iiber einer endlichen transitiven Teilmenge U !JJl mit Interpretation von E durch g* erfiillbar. Ausgangspunkt fur den Beweis ist, Satz 2 aus [2]. Im ersten Teil des Satzes kann Definition. 1. Es sei !JJlo die kleinste Teilmenge von %TI, die V : = (0, 1 , 2 } enthalt und in der 14* U 5 !JJl unendlich gewahlt werden. mit T fur n E N stets auch (2, n ) : = (0, I , 2, n + 4) enthalten ist.