German Title: Suprema und Infima in den partiellen Ordnungen der rekursiv aufzählbaren ibT- und cl-Grade

Preview

PDF, English - main document Download (1MB) | Terms of use

Abstract

A bounded reducibility is a preorder on the power set of the integers which is obtained from Turing reducibility by the additional requirement that, for a reduction of A to B, for every input x the oracle B is only asked oracle queries y < f(x)+1, where f is from some given set F of total computable functions.

The most general example of a bounded reducibility is weak-truth-table reducibility, where F is just the set of all computable functions. In this thesis we study the so-called strongly bounded reducibilites, which are obtained by choosing F={id} and F={id+c: c constant}, respectively (where id is the identity function).

We start by giving a machine-independent characterisation of these reducibilities, define the degree structures of the computably enumerable ibT- and cl-degrees and review some important properties of ibT- and cl-reducibility concerning strictly increasing computable functions (called shifts) and the permitting method.

Then we turn to the degree structures mentioned above, and in particular to existence and nonexistence of joins and meets of a finite set of degrees. As Barmpalias and independently Fan and Lu have shown, these structures are not upper semi-lattices; it is also known that they are not lower semi-lattices. We extend these results by showing that the existence of a join or meet of n degrees does in general not imply the existence of a join or meet, respectively, of any subset containining more than one element of these degrees. We also show that even if deg(A) and deg(B) have a join, there is no uniform way to compute a member of this join from A and B, contrasting the join in the Turing degrees. We conclude this part by looking at the substructure which consists of the degrees of simple sets and show that this structure is not closed with respect to the join operation. This is the dual of a theorem of Ambos-Spies stating that the simple degrees are not closed with respect to meets.

Next, we investigate lattice embeddings into the c.e. r-degrees. Due to an observation of Ambos-Spies, the proof that every finite distributive lattice can be embedded into the computably enumerable Turing degrees carries over to the c.e. r-degrees. We show that the smallest nondistributive lattices N5 and M3 can also be embedded, but only the N5 can be embedded preserving the least element. Since every nondistributive lattice contains at least one of these two lattices as a sublattice, this motivates the conjecture that every finite lattice can be embedded. We show this for two other nondistributive lattices, the S7 und S8.

Finally, we compare the c.e. ibT- and c.e. cl-degrees and prove that these are not elementarily equivalent. To show this, we study under which conditions on two degrees a and c with a<c it holds that there exists a degree b<c such that c is the join of a and b. In this context we also show that, while shifts provide a simple method to produce a lesser r-degree a to some given noncomputable r-degree c, there is no computable shift which uniformly produces such an a with the additional property that no degree b as above exists.

Translation of abstract (German)

Eine beschränkte Reduzierbarkeit ist eine Quasiordnung auf den Teilmengen natürlicher Zahlen, die man durch Einschränkung der Turing-Reduzierbarkeit erhält, indem man zusätzlich verlangt, dass für eine Reduktion von A auf B bei Eingabe x nur Anfragen y < f(x)+1 an das Orakel B gestellt werden dürfen, wobei f aus einer vorgegebenen Menge F total berechenbarer Funktionen stammt.

Das allgemeinste Beispiel einer beschränkten Reduzierbarkeit ist weak-truth-table-Reduzierbarkeit, hierbei besteht F gerade aus allen berechenbaren Funktionen. In der vorliegenden Arbeit werden Ergebnisse über die sogenannten stark beschränkten Reduzierbarkeiten vorgestellt, die man bei Wahl von F={id} bzw. F={id+c: c konstant} erhält (wobei id die Identitätsfunktion ist).

Wir geben zunächst eine maschinenunabhängige Charakterisierung dieser Reduzierbarkeiten an, definieren die zugehörigen Gradstrukturen der rekursiv aufzählbaren ibT- und cl-Grade und rekapitulieren einige wichtige Eigenschaften der ibT- und cl-Reduzierbarkeiten im Zusammenhang mit streng monotonen berechenbaren Funktionen (Shifts) und mit der Permitting-Methode, die im späteren Verlauf von Nutzen sind.

Danach wenden wir uns den obigen Gradstrukturen zu, insbesondere dem Aspekt der Existenz von Suprema und Infima einer endlichen Menge von Graden. Von Barmpalias und unabhängig von Fan und Lu wurde gezeigt, dass die rekursiv aufzählbaren r-Grade für r=ibT und r=cl keinen oberen Halbverband bilden; ebenso ist bekannt, dass es sich um keinen unteren Halbverband handelt. Wir verallgemeinern diese Resultate dahingehend, dass aus der Existenz eines Supremums bzw. Infimums von n Graden im Allgemeinen noch nicht folgt, dass eine echte Teilmenge dieser Grade mit mehr als einem Element ein Supremum bzw. Infimum besitzt. Ferner zeigen wir, dass Suprema von Graden deg(A) und deg(B) selbst im Fall der Existenz nicht in der gleichen Weise uniform aus A und B berechnet werden können wie im Fall der Turing-Reduzierbarkeit. Wir beschließen diesen Teil mit einer Betrachtung der Teilstruktur der Grade einfacher Mengen und weisen nach, dass diese nicht unter Suprema abgeschlossen sind. Dies komplementiert ein entsprechendes Resultat von Ambos-Spies über die Nicht-Abgeschlossenheit unter Infima.

Das folgende Kapitel ist der Untersuchung von Verbandseinbettungen in die rekursiv aufzählbaren r-Grade gewidmet. Nach einer Beobachtung von Ambos-Spies überträgt sich der Beweis, dass jeder endliche distributive Verband in die rekursiv aufzählbaren Turinggrade einbettbar ist, auf die r-Grade. Wir zeigen, dass auch die kleinsten nichtdistributiven Verbände N5 und M3 eingebettet werden können, letzterer allerdings nicht unter Bewahrung des kleinsten Elements. Da jeder nichtdistributive Verband mindestens einen dieser beiden Verbände als Teilverband besitzt, gibt dies Anlass zu der Vermutung, dass jeder endliche Verband eingebettet werden kann. Wir weisen das für zwei weitere nichtdistributive Verbände S7 und S8 nach.

Zum Abschluss wenden wir uns dem Vergleich von der rekursiv aufzählbaren ibT- und cl-Grade zu und zeigen, dass diese nicht elementar äquivalent sind. Dazu untersuchen wir, wann für zwei Grade a und c mit a<c gilt, dass ein Grad b<c derart existiert, dass c das Supremum von a und b ist. In diesem Zusammenhang zeigen wir außerdem, dass, während Shifts eine einfache Methode liefern, zu einem nicht berechenbaren r-Grad c einen echt kleineren r-Grad a anzugeben, dieser nicht uniform so gewählt werden kann, dass kein b wie oben existiert.