EINE VERSCHARFUNG EINES SATZES VON KOSTYRKO ZUR REDUKTIONSTHEORIE MIT EINER ANWENDUNG AUF DIE SPEKTRALE DARSTELLUNG VON PRADIKATEY von MICHAEL DEUTSCH in Bremen (BRD) 5 1. Zur Reduktionstheorie des Entseheidungsproblems Als Verschiirfung eines bekannten Resultates von KOSTYRKO (vgl. [S]) beweisen wir S a t z 1. Zu jedem Ausdruck a der Pradikatenlogik mit Identitat kann man effektiv einen Ausdruck B aus V3" V(0, 1) angeben mit 1) a ist erfullbar, c> /? ist erfullbar, ist uber einer transitiven Teilmenge U von YJ bei Interpretation der einzigen Pradikatenvariablen E durch g erfullbar.
2 ) M ist endlich erfullbar,
-s p ist endlich erfullbar, o p ist uber einer endlichen transitiven Teilmenge U von )751 bei Interpretation von E durch E -erfullbar. B e m e r k u n g e n . 1. Zu den Bezeichnungen und Begriffen in diesem Aufsatz vgl. [4]. Die gemaB [4], S. 5$l, gegebenenfalls oben angebrachten Zusatzc ,,YJl" bzw. ,,o" werden hier jedoch bei dm jeweiligen Abkiirzungen unten angefiigt. 2 . Eine Teilmenge U Unter der transitiven Hulle einer Teilmenge M s I;ln verstehen wir den Durchschnitt aller transitiven Mengen V 3. Als Ausdruck a kann ein beliebiger typentheoretischer Ausdruck vorgegeben werden, sofern man fur die Modelle Nichtstandardontologien zu1aBt. 4. fi kann natiirlich auch uber Teilmengen von N mit Interpretation von E durch go interpretiert werden. Der Beweis des Satzes liefert dann Schranken fur die inneren Quantoren. Ausgangspunkt fur den Beweis ist wiederum Satz 2 aus [4]. Statt mit N" und YJll arbeiten wir mit den folgenden Modellen N und YJl , , der natiirlichen Zahlen bzw. endlichen Folgen von naturlichen Zahlen :
- O : = 0 , n + I : = n v { n } . 2 . Es sei %TIo die kleinste Teilmenge von YJl, die 0 enthalt und in der mit x fur jedes n E N stets auch (x, n ) : = ( 2 , x, n + 4) enthalten ist.