German Title: Multiples Permitting und beschränkte Turingreduzierbarkeiten

Preview

PDF, English Download (965kB) | Terms of use

Abstract

We look at various properties of the computably enumerable (c.e.) not totally ω-c.e. Turing degrees. In particular, we are interested in the variant of multiple permitting given by those degrees. We define a property of left-c.e. sets called universal similarity property which can be viewed as a universal or uniform version of the property of array noncomputable c.e. sets of agreeing with any c.e. set on some component of a very strong array. Using a multiple permitting argument, we prove that the Turing degrees of the left-c.e. sets with the universal similarity property coincide with the c.e. not totally ω-c.e. degrees. We further introduce and look at various notions of socalled universal array noncomputability and show that c.e. sets with those properties can be found exactly in the c.e. not totally ω-c.e. Turing degrees and that they guarantee a special type of multiple permitting called uniform multiple permitting. We apply these properties of the c.e. not totally ω-c.e. degrees to give alternative proofs of well-known results on those degrees as well as to prove new results. E.g., we show that a c.e. Turing degree contains a left-c.e. set which is not cl-reducible to any complex left-c.e. set if and only if it is not totally ω-c.e. Furthermore, we prove that the nondistributive finite lattice S7 can be embedded into the c.e. Turing degrees precisely below any c.e. not totally ω-c.e. degree. We further look at the question of join preservation for bounded Turing reducibilities r and r′ such that r is stronger than r′. We say that join preservation holds for two reducibilities r and r′ if every join in the c.e. r-degrees is also a join in the c.e. r′-degrees. We consider the class of monotone admissible (uniformly) bounded Turing reducibilities, i.e., the reflexive and transitive Turing reducibilities with use bounded by a function that is contained in a (uniformly computable) family of strictly increasing computable functions. This class contains for example identity bounded Turing (ibT-) and computable Lipschitz (cl-) reducibility. Our main result of Chapter 3 is that join preservation fails for cl and any strictly weaker monotone admissible uniformly bounded Turing reducibility. We also look at the dual question of meet preservation and show that for all monotone admissible bounded Turing reducibilities r and r′ such that r is stronger than r′, meet preservation holds. Finally, we completely solve the question of join and meet preservation in the classical reducibilities 1, m, tt, wtt and T.

Translation of abstract (German)

Wir betrachten verschiedene Eigenschaften der aufzählbaren nicht vollständig ω-aufzählbaren (not totally ω-c.e.) Turing-Grade. Wir interessieren uns insbesondere für die Varianten des multiplen Permittings, die diese Grade ermöglichen. Wir definieren eine Eigenschaft links-aufzählbarer Mengen, die wir universelle Ähnlichkeitseigenschaft (universal similarity property) nennen und die man als universelle oder uniforme Version jener Eigenschaft Array-nichtberechenbarer aufzählbarer Mengen, mit jeder aufzählbaren Menge auf einer Komponente eines Very-Strong-Arrays übereinzustimmen, auffassen kann. Mithilfe eines multiplen Permitting-Arguments beweisen wir, dass die Turing-Grade der links-aufzählbaren Mengen mit der universellen Ähnlichkeitseigenschaft mit den aufzählbaren nicht vollständig ω-aufzählbaren Turing-Graden übereinstimmen. Weiterhin definieren und betrachten wir verschiedene Begriffe der sogenannten universellen Array-Nichtberechenbarkeit (universal array noncomputability) und zeigen, dass aufzählbare Mengen mit diesen Eigenschaften genau in den aufzählbaren nicht vollständig ω-aufzählbaren Turing-Graden liegen und dass sie eine spezielle Art des multiplen Permittings ermöglichen, die wir uniformes multiples Permitting (uniform multiple permitting) nennen. Wir wenden diese Eigenschaften der aufzählbaren nicht vollständig ω-aufzählbaren Turing-Grade an, um alternative Beweise bekannter Ergebnisse, die diese Grade betreffen, zu führen und um neue Ergebnisse zu beweisen. Beispielsweise zeigen wir, dass ein aufzählbarer Turing-Grad genau dann eine links-aufzählbare Menge enthält, die nicht cl-reduzierbar auf eine komplexe links-aufzählbare Menge ist, wenn er nicht vollständig ω-aufzähbar ist. Außerdem beweisen wir, dass der nichtdistributive endliche Verband S7 genau unterhalb jedes aufzählbaren nicht vollständig ω-aufzählbaren Grades in die aufzählbaren Turing-Grade eingebettet werden kann. Wir betrachten außerdem die Frage nach der Join-Erhaltung für beschränkte Turing-Reduzierbarkeiten r und r′ sodass r stärker als r′ ist. Join-Erhaltung gilt für zwei Reduzierbarkeiten r und r′, wenn jeder Join in den aufzählbaren r-Graden auch ein Join in den aufzählbaren r′- Graden ist. Wir betrachten die Klasse der monotonen zulässigen (uniform) beschränkten Turing- Reduzierbarkeiten, das heißt, der reflexiven und transitiven Turing-Reduzierbarkeiten, deren Use- Funktion durch eine Funktion beschränkt ist, die in einer (uniform berechenbaren) Familie streng monoton steigender berechenbarer Funktionen liegt. Diese Klasse enthält zum Beispiel die ibT-Reduzierbarkeit und die cl-Reduzierbarkeit. Das Hauptergebnis des dritten Kapitels besagt, dass Join-Erhaltung für cl und eine echt stärkere monotone zulässige uniform beschränkte Turing- Reduzierbarkeit nicht gelten kann. Wir gehen auch auf die duale Frage nach der Meet-Erhaltung ein und zeigen, dass diese für alle monotonen zulässigen beschränkten Turing-Reduzierbarkeiten r und r′ gilt, sodass r stärker als r′ ist. Abschließend beantworten wir die Frage nach der Join- und Meet-Erhaltung in den klassischen Reduzierbarkeiten 1, m, tt, wtt und T vollständig.