Reduzierungen Unentscheidbarer Formaler Sprachen Über Induktiv Definierten Bereichen

✍ Scribed by Michael Deutsch

• Publisher: John Wiley and Sons
• Year: 1974
• Tongue: English
• Weight: 759 KB
• Volume: 20
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19740201904

✦ Synopsis

REDUZIERUNGEN UNENTSCHEIDBARER FORMALER SPRACHEN UBER INDUKTIV DEFINIERTEN BEREICHEN von ~KICHAEL DEUTSCH in GieBen (BRD) 1. Einleitung Seit [ 121 haben die Untersuchungen zu besonders einfachen Darstellungen aller aufziihlbaren Priidikate iiber N einen gewissen AbschluB erhalten. Keineswegs ab-schlieI3end beantwortet sind jedoch entsprechende Fragestellungen fur andere Bereiche als N . Hier interessieren insbesondere Termmengen und der Bereich der endlichen Mengen von endlickem Rang. Definition. Unter der durch die paarweise verschiedenen Funktorenvariablen To, . . ., r,, ( v 5 0 ; I', an-stellig, an >= 1 , 0 5 7t 6 v ) aus den paarweise verschiedenen Subjektsvariablen * o , . . ., *, , (p 2 0 ) erzeugten Termmenge (im folgenden kurz Termmenge T genannt) versteht man die kleinste Menge von Zeichenreihen, die * o , . . ., *, , und mit beliebigen Zeichenreihen xl,. . ,, xOm auch I',x,. . . x,= enthiilt (0 5 7t _I v ) . Die Funktionen n, : = Ax, . . . x.JRxl . . . x , , , (0 5 7t 5 Y) bezeichnet man als Nachfolgerfunktionen von T, die nullstelligen Funktionen I*, (0 5 x 5 p )

als Ausgangselemente von T.

Beispiele. 1) Fur p = 0 , v = 0, oo = 1 kann man T interpretieren als Menge der natiirlichen Zahlen.

2. Fur p = 0 , v 2 0 , a, = 1 (0 5 ?I 6 v ) kann man T interpretieren als Menge der Wiirter iiber dem Alphabet Po, . . . , r, einschliefllich des leeren Wortes.

3. Fur p = 0, v = 0, a,, = 2 kann man T interpretieren als Menge der Ausdriieke des FITcH-Kalkuls (,,fiTcH-Bereich").

Definition. Unter dem Bereich M der endlichen Mengen von endlichem Rang versteht man den kleinsten Bereich, der die leere Menge 0 enthLlt und gegeniiber der Einermengenbildung und Vereinigungsmengenbildung abgeschlossen ist. M ist damit auch gegeniiber der Durchschnittsmengenbildung abgeschlossen. A x ( . } und Ixy x v y bezeichnet man als Nachfolgerfunktionen von M, I 0 als Ausgangselement von M. M ist interessant als ,,minimale", besonders gesicherte Mengenlehre. Schon seit geraumer Zeit interessiert man sich fur einfache Darstellungen aller aufzahlbaren PrLdikate iiber den angegebenen Bereichen. Zu erwahnen sind hier insbesondere 1) Untersuchungen von FITCH, z. B. [6], [7], 2) RODDINGS Normalform aller aufziihlbaren Priidikate iiber M mit dem Priifix 3) Untersuchungen von SMULLYAN zur Darstellung aller aufziihlbaren Pradikate iiber 3 V WI, Wortmengen durch Verwendung der Verkettungsfunktion [IS].