Person: Carl, Merlin
Models of true arithmetic are integer parts of models of real exponentation
2021, Carl, Merlin, Krapp, Lothar Sebastian
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.
Randomness via infinite computation and effective descriptive set theory
2018-08-01, Carl, Merlin, Schlicht, Philipp
Recognizable sets and Woodin cardinals : Computation beyond the constructible universe
2018, Carl, Merlin, Schlicht, Philipp, Welch, Philip
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
2017-05-12, Carl, Merlin, Durand, Bruno, Lafitte, Grégory, Ouazzani, Sabrina
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.
Reachability for infinite time Turing machines with long tapes
2020, Carl, Merlin, Rin, Benjamin, Schlicht, Philipp
Taming Koepke's Zoo
2018-07-03, Carl, Merlin, Ouazzani, Sabrina, Welch, Philip
The Bolzano-Weierstrass theorem in generalised analysis
2018, Carl, Merlin, Galeotti, Lorenzo, Löwe, Benedikt
Einige Bemerkungen Kurt Gödels zur Mengenlehre
2019, Carl, Merlin, Engelen, Eva-Maria
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.
Some Observations on Infinitary Complexity
2018-07-03, Carl, Merlin
Infinite time recognizability from generic oracles and the recognizable jump operator
2017-08-07, Carl, Merlin
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.