Reducibility and Completeness for Sets of Integers

Verff. untersuchen in dieser Arbeit Verallgemeinerungen der von \textit{E. L. Post} eingeführten sogenannten produktiven Mengen [Bull. Am. Math. Soc. 50, 284--316 (1944; Zbl 0063.06328)]. In diesem Zusammenhang werden gewisse Prädikate \(\leq_1\), \(\leq_m\), \(\leq_{tt}\), \(\leq_{btt}\), \(\leq_T\) betrachtet, wobei \(\leq_m\), \(\leq_1\), \(\leq_T\) wie folgt definiert sind: 1. \(\alpha\leq_m\beta\) genau dann, wenn eine rekursive Funktion \(f\) existiert mit \(f(\alpha)\subseteq \beta\), \(f(\alpha')\subseteq \beta'\), (\(\alpha'\): Komplement von \(\alpha\)). 2. \(\alpha\leq_1\beta\) genau dann, wenn zusätzlich die oben erwähnte Funktion \(f\) einseindeutig ist. 3. \(\alpha\leq_T\beta\) genau dann, wenn \(\alpha\) rekursiv in \(\beta\) ist. Die Definitionen von \(\leq_{tt}\) und \(\leq_{btt}\) sind umfangreicher und sollen deshalb hier nicht wiedergegeben werden. Sei \(\leq_R\) eine beliebige der genannten Relationen. \(\leq_R\) ist reflexiv und transitiv und definiert somit eine Halbordnung \(V_R\). Eine Menge \(\alpha\) wird \(R\)-vollständig genannt, wenn sie rekursiv aufzählbar ist (r. a.) und wenn für jedes r. a. \(\beta\) die Beziehung \(\beta\leq_R \alpha\) gilt. Eine Menge heißt \(\gamma\)-produktiv, wenn es eine rekursive Funktion \(f\) gibt, so daß für alle \(x\) gilt: \(f(x)\in (\gamma-\omega_x) \cup (\omega_x-\gamma)\), wo \(\omega_x\) die r. a. Menge mit Gödelnummer \(x\) ist. Von \textit{J. Myhill} wurde gezeigt: \(\alpha\) ist 1-vollständig \(\Leftrightarrow\) \(\alpha\) ist \(m\) vollständig \(\Leftrightarrow\) \(\alpha\) ist r. a. und \(\alpha'\) ist produktiv [Z. Math. Logik Grundlagen Math. 1, 97--108 (1955; Zbl 0065.00105)]. Ziel der Verff. ist es, Charakterisierungen der \(T\)-, \(tt\)-, und \(btt\)-vollständigen Mengen zu erhalten, die dem eben erwähnten Resultat von Myhill entsprechen. Diese Charakterisierungen werden auf systematische Weise gewonnen durch Verwendung eines Prädikates \(Q_R(x,\mu,\nu)\), welches die Eigenschaften hat: 1. \(\alpha\leq_R\beta\) genau dann, wenn es ein rekursives \(f\) gibt, so daß für alle \(x\) gilt: \(x\in\alpha\Leftrightarrow\neg Q_R (f(x),\beta,\beta')\), 2. es gibt ein rekursives \(h\), so daß \(\omega_{h(x_1, x_2)}=\{y\mid Q_R(y, \omega_{x_1}, \omega_{x_1})\) gilt, 3. \(\beta\subseteq\gamma\) und \(Q_R(y,\alpha,\beta)=Q_R(y, \alpha, \gamma)\). Ferner wird Gebrauch gemacht von der Tatsache, daß die \(R\) vollständigen Mengen \(\alpha\) durch die Beziehung \(\kappa\leq_R\alpha\) charakterisiert sind, mit \(\kappa=\{x\mid x\in \omega_x\}\); dies folgt aus der Gültigkeit der Implikationen \(\alpha\leq_1\beta\Rightarrow\alpha\leq_m\beta _\Rightarrow\alpha \leq_{btt}\beta\Rightarrow\alpha \leq_{tt}\beta\Rightarrow\alpha \leq_T\beta\) und der 1-Vollständigkeit von \(\kappa\). Der Hauptsatz der Arbeit lautet: \(\beta\) ist \(R\)-vollständig genau dann, wenn \(\beta\) r. a. ist und wenn ein rekursives \(g\) existiert mit \((x)\) \([Q_R(g(x),\beta,\beta') \Leftrightarrow Q_R(g(x),\beta, \omega_x)]\). Durch Angabe von Prädikaten \(Q_1,Q_m\) für den Fall der 1- bzw. \(m\)-Reduzierbarkeit erhält man durch Anwendung des Hauptsatzes wieder das Resultat von Myhill. Entsprechend werden Prädikate \(Q_{tt}, Q_{btt}\) und \(Q_T\) konstruiert, die obigen Bedingungen 1., 2., 3. genügen. Durch geschickte Definition der \(tt\)-, \(btt\)- und \(T\)-produktiven Mengen werden nun, als Folgen des Hauptsatzes, eine Anzahl Korollare erhalten, von denen die drei wichtigsten zu folgendem Satz zusammengefaßt werden können: \(\beta\) ist \(R\)-vollständig genau dann, wenn \(\beta\) r. a. und \(R\)-produktiv ist (für \(R\) darf \(tt\), \(btt\) oder \(T\) eingesetzt werden). In einem weiteren Abschnitt untersuchen die Verff. das Problem, die Halbordnungen \(V_R\) ordnungsisomorph in \(V_1\) abzubilden. Im Fall der \(T\)- Reduzierbarkeit geschieht das mit Hilfe der sogenannten Sprungoperation, die jedem \(\alpha\) die Menge \(\hat\alpha = \{x \mid x\in \omega_x^\alpha\}\) zuordnet, wo \(\omega_x^\alpha\) die \(\alpha\)-rekursiv aufzählbare Menge mit Gödelnummer \(x\) ist. Es wird gezeigt, daß die Beziehung \(\alpha\leq_T\beta \Leftrightarrow\hat\alpha\leq_1\hat\beta\) gilt, woraus folgt, daß die \(T\)-Reduzierbarkeit mit Hilfe der Sprungoperation und der 1-Reduzierbarkeit definiert werden kann. Durch Angabe geeigneter Funktionen, die für \(V_{tt}\), \(V_{btt}\), \(V_m\) dasselbe leisten wie die Sprungoperation für \(V_T\), wird gezeigt, daß sich auch die zuerst genannten Halbordnungen ordnungsisomorph in \(V_1\) einbetten lassen. Abschließend geben die Verff. einige weitere Reduzierbarkeitsdefinitionen an, und diskutieren kurz deren Eigenschaften.

Cited in

(69)

This page was built for publication: Reducibility and Completeness for Sets of Integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3843613)