, The equivalence is given by the conjunction of Theorem V.59 and V, vol.58
, Let z ? 2 ? . The following are equivalent: 1. z is generic over L ? , 2. z is ITTM-decidable generic, 3. z is co-ITTM generic
, Let z be a real generic over L ? . Let M be a machine that halts on a co-meager set. By Corollary V.59.1 we have that the set {x ? 2 ? : ? x > ?} is meager. Note also that if z is generic over L ? we have L ? (x) ? 1 L ? (x) together with L ? (x) ? 2 L ? (x). Thus the set {x ? 2 ? : ? x > ?} is actually also meager, The implications (3) ? (2) and (2) ? (1) are trivial. Thus, it remains only to prove
, By admissibility of ?, there must exists ? < ? such that the set {? : ? ? ?? < ? M (x) ? [?]} is already a dense set of strings. It follows that {x ? 2 ? : M (x) ? [?]} is co-meager in a dense open set and thus comeager. Furthermore its complement is a union of nowhere dense closed sets with Borel code in L ?, particular the set {? : ? ? ?? M (x) ? [?]} must be a dense set of strings
, Thus z also is co-ITTM generic
Logical analysis of some theorems of combinatorics and topological dynamics, Logic and Combinatorics, vol.65, pp.125-156, 1987. ,
A comparison of various analytic choice principles, 2019. ,
A model-theoretic approach to ordinal analysis, The Bulletin of Symbolic Logic, vol.3, issue.1, pp.17-52, 1997. ,
The model-theoretic ordinal analysis of theories of predicative strength, The Journal of Symbolic Logic, vol.64, issue.1, pp.327-349, 1999. ,
Admissible sets and structures, vol.7, 2017. ,
A short proof of Hindman's theorem, J. Comb. Theory, Ser. A, vol.17, pp.384-386, 1974. ,
Continuous higher randomness, Journal of Mathematical Logic, vol.17, issue.01, p.1750004, 2017. ,
Continuous higher randomness, J. Math. Log, vol.17, issue.1, pp.1750004-53, 2017. ,
Bad oracles in higher computability and randomness ,
A galois connection between turing jumps and limits, 2018. ,
Effective choice and boundedness principles in computable analysis, Bulletin of Symbolic Logic, vol.17, pp.73-117, 2011. ,
Weihrauch degrees, omniscience principles and weak computability, Journal of Symbolic Logic, vol.76, pp.143-176, 2011. ,
Borel choice ,
The Bolzano-Weierstrass Theorem is the jump of Weak König's Lemma, Annals of Pure and Applied Logic, vol.163, issue.6, pp.623-625, 2012. ,
, , 2017.
On the algebraic structure of Weihrauch, 2016. ,
Randomness and degree theory for infinite time register machines, Computability, vol.5, issue.2, pp.181-196, 0209. ,
Infinite computations with random oracles, Notre Dame Journal of Formal Logic, vol.58, issue.2, p.2013 ,
Randomness via infinite computation and effective descriptive set theory, Journal of Symbolic Logic, vol.83, issue.2, pp.766-789, 2018. ,
, Weak yet strong" restrictions of Hindman's Finite Sums Theorem. arXiv e-prints, 2016.
, New bounds on the strength of some restrictions of Hindman's Theorem. arXiv e-prints, 2017.
Density of the Medvedev lattice of ? 0 1 classes, Arch. Math. Logic, vol.42, issue.6, pp.583-600, 2003. ,
Lowness of higher randomness notions, Israel J. Math, vol.166, issue.1, pp.39-60, 2008. ,
Randomness in the higher setting, The Journal of Symbolic Logic, vol.80, issue.4, pp.1131-1148, 2015. ,
Recursion Theory: Computational Aspects of Definability, vol.8, 2015. ,
Set theory and the continuum hypothesis. Courier Corporation, 2008. ,
Ultrafilters: Some old and some new results, Bull. Amer. Math. Soc, vol.83, issue.4, pp.417-455, 1977. ,
, Constructibility, vol.6, 2017.
Algorithmic Randomness and Complexity. Theory and Applications of Computability, 2010. ,
Effectiveness of Hindman's Theorem for Bounded Sums, pp.134-142, 2017. ,
A note on the hyperarithmetical hierarchy, J. Symbolic Logic, vol.35, issue.3, pp.429-430, 1970. ,
Uniformly defined descending sequences of degrees, J. Symbolic Logic, vol.41, issue.2, pp.363-367, 1976. ,
Subsystems of set theory and analysis, 1967. ,
Two observations concerning infinite time turing machines, BIWOC, pp.44-47, 2007. ,
Proof of mostowski's conjecture, Journal of Symbolic Logic, vol.29, issue.2, pp.103-104, 1964. ,
Hindman's coloring theorem in arbitrary semigroups, Journal of Algebra, vol.395, 2013. ,
Ramsey's theorem for n-parameter sets, Transactions of the American Mathematical Society, vol.159, pp.257-292, 1971. ,
, Ramsey Theory. Wiley Series in Discrete Mathematics and Optimization, 1990.
Higher randomness and genericity. Forum of Mathematics, vol.5, p.31, 2017. ,
Metamathematics of First-Order Arithmetic. Perspectives in Logic, 2017. ,
Infinite time turing machines, The Journal of Symbolic Logic, vol.65, issue.02, pp.567-604, 2000. ,
Recursive pseudo-well-orderings, Transactions of the American Mathematical Society, vol.131, issue.2, pp.526-543, 1968. ,
Finite sums from sequences within cells of a partition of N, J. Comb. Theory, Ser. A, vol.17, issue.1, pp.1-11, 1974. ,
Algebra in the Stone-?ech compactification, De Gruyter Expositions in Mathematics, vol.27, 1998. ,
Randomness via effective descriptive set theory, Journal of the London Mathematical Society, vol.75, issue.2, pp.495-508, 2007. ,
Rapidly growing ramsey functions, Annals of Mathematics, vol.113, issue.2, pp.267-314, 1981. ,
Searching for an analogue of ATR 0 in the Weihrauch lattice, 2018. ,
Dividing by Zero -How Bad Is It, Really?, 41st Int. Sym. on Mathematical Foundations of Computer Science (MFCS 2016), vol.58, 2016. ,
Randomness and genericity in the degrees of unsolvability, Dissertation Abstracts International Part B: Science and Engineering, vol.42, issue.9, 1982. ,
Notions of weak genericity, The Journal of symbolic logic, vol.48, issue.03, pp.764-770, 1983. ,
, Some computability-theoretic reductions between principles around ATR 0 . arXiv e-prints, 2019.
Sur les ensembles non mesurables b et l'emploi de la diagonale cantor, CR Acad. Sci, vol.181, pp.95-96, 1925. ,
The definition of random sequences, Information and Control, vol.9, pp.602-619, 1966. ,
Higher randomness and forcing with closed sets, LIPIcs-Leibniz International Proceedings in Informatics, vol.25, 2014. ,
On the pi11-separation principle, Math. Log. Q, vol.54, pp.563-578, 2008. ,
Open questions in reverse mathematics, The Bulletin of Symbolic Logic, vol.17, issue.3, pp.431-454, 2011. ,
, André Nies. Computability and Randomness. Oxford Logic Guides, 2009.
The proof-theoretic strength of Ramsey's theorem for pairs and two colors, 2015. ,
Higher recursion theory. Perspectives in mathematical logic, 1990. ,
Subsystems of Second Order Arithmetic. Perspectives in Logic, 2009. ,
Hyperarithmetical quantifiers, Fundamenta Mathematicae, vol.48, issue.3, pp.313-320, 1960. ,
Descending sequences of degrees, The Journal of Symbolic Logic, vol.40, issue.1, pp.59-61, 1975. ,
Hindman's theorem: an ultrafilter argument in second order arithmetic, J. Symb. Log, vol.76, issue.1, pp.353-360, 2011. ,
A simple proof and some difficult examples for hindman's theorem, Notre Dame J. Formal Logic, vol.53, issue.1, pp.53-65, 2012. ,
The length of infinite time turing machine computations, Bulletin of the London Mathematical Society, vol.32, issue.2, pp.129-136, 2000. ,
Characteristics of discrete transfinite time turing machine models: Halting times, stabilization times, and normal form theorems, Theoretical Computer Science, vol.410, pp.426-442, 2009. ,