Person: Carl, Merlin
Email Address
ORCID
Birth Date
Job Title
Last Name
First Name
Name
Search Results
Models of true arithmetic are integer parts of models of real exponentation
Exploring further the connection between exponentiation on real closed fields and the existence of an integer part modelling strong fragments of arithmetic, we demonstrate that each model of true arithmetic is an integer part of an exponential real closed field that is elementarily equivalent to the real numbers with exponentiation and that each model of Peano arithmetic is an integer part of a real closed field that admits an isomorphism between its ordered additive and its ordered multiplicative group of positive elements. Under the assumption of Schanuel’s Conjecture, we obtain further strengthenings for the last statement.
Recognizable sets and Woodin cardinals : Computation beyond the constructible universe
We call a subset of an ordinal λrecognizableif it is the unique subset xof λfor which some Turing machine with ordinal time and tape and an ordinal parameter, that halts for all subsets of λas input, halts with the final state 0. Equivalently, such a set is the unique subset xwhich satisfies a given Σ1formula in L[x]. We further define the recognizable closurefor subsets of λ by closing under relative recognizability for subsets of λ.
We prove several results about recognizable sets and their variants for other types of machines. Notably, we show the following results from large cardinals.
•Recognizable sets of ordinals appear in the hierarchy of inner models at least up to the level Woodin cardinals, while computable sets are elements of L.
•A subset of a countable ordinal λis in the recognizable closure for subsets of countable ordinals if and only if it is an element of the inner model M∞, which is obtained by iterating the least measure of the least fine structural inner model M1with a Woodin cardinal through the ordinals.
Admissibles in Gaps
We consider clockable ordinals for Infinite Time Turing Machines (ITTMs), i.e., halting times of ITTMs on the empty input. It is well-known that, in contrast to the writable ordinals, the set of clockable ordinals has ‘gaps’. In this paper, we show several results on gaps, mainly related to the admissible ordinals they may properly contain. We prove that any writable ordinal can occur as the order type of the sequence of admissible ordinals in such a gap. We give precise information on their ending points. We also investigate higher rank ordinals (recursively inaccessible, etc.). Moreover, we show that those gaps can have any reasonably effective length (in the sense of ITTMs) compared to their starting point.
Einige Bemerkungen Kurt Gödels zur Mengenlehre
Im Folgenden werden einige Bemerkungen zum Mengenbegriff aus Gödels Notizbüchern Philosophie I Maximen 0 und Maximen VI diskutiert. Dabei wird gezeigt, dass Gödel mit einem philosophischen und einem logischen Mengenbegriff arbeitet, welche sich jedoch aufeinander beziehen. Gödels iterativer Mengenbegriff wird schließlich ausführlich erörtert.
Infinite time recognizability from generic oracles and the recognizable jump operator
By a theorem of Sacks, if a real x is recursive relative to all elements of a set of positive Lebesgue measure, x is recursive. This statement, and the analogous statement for non-meagerness instead of positive Lebesgue measure, have been shown to carry over to many models of transfinite computations in: Notre Dame Journal of Formal Logic , to appear, arXiv:1307.0160 [math.LO]. Here, we start exploring another analogue concerning recognizability rather than computability. For a notion of relativized recognizability (introduced in: Annals of Pure and Applied Logic 165 (9) (2014), 1353–1532, for ITRMs and generalized here to various other machine types), we show that, for Infinite Time Turing Machines (ITTMs), if a real x is recognizable relative to all elements of a non-meager Borel set Y , then x is recognizable. We also show that a relativized version of this statement holds for Infinite Time Register Machines (ITRMs). This extends our work in: Evolving Computability: 11th Conference on Computability in Europe , 2015, pp. 137–145, where we obtained the (unrelativized) result for ITRMs. We then introduce a jump operator for recognizability, examine its set-theoretical content and show that the recognizable jumps for ITRMs and ITTMs are primitive-recursively equivalent, even though these two models are otherwise of vastly different strength. Finally, we introduce degrees of recognizability by considering the transitive closure of relativized recognizability and connect it with the recognizable jump operator to obtain a solution to Post’s problem for degrees of recognizability.