Journal of Mathematical Logic

We extend theories of reverse mathematics by a non-principal ultrafilter, and show that these are conservative extensions of the usual theories ACA₀, ATR₀, and .

We prove that in an arbitrary o-minimal structure, every interpretable group is definably isomorphic to a definable one. We also prove that every definable group lives in a cartesian product of one-dimensional definable group-intervals (or one-dimensional definable groups). We discuss the general open question of elimination of imaginaries in an o-minimal structure.

Building on the work of Schimmerling [Coherent sequences and threads, Adv. Math.216(1) (2007) 89–117] and Steel [PFA implies AD^L(ℝ), J. Symbolic Logic70(4) (2005) 1255–1296], we show that the failure of square principle at a singular strong limit cardinal implies that there is a nontame mouse. The proof presented is the first inductive step beyond L(ℝ) of the core model induction that is aimed at getting a model of AD_ℝ + "Θ is regular" from the failure of square at a singular strong limit cardinal or PFA.

We consider effective versions of two classical theorems, the Lebesgue density theorem and the Denjoy–Young–Saks theorem. For the first, we show that a Martin-Löf random real z ∈ [0, 1] is Turing incomplete if and only if every effectively closed class 𝒞 ⊆ [0, 1] containing z has positive density at z. Under the stronger assumption that z is not LR-hard, we show that every such class has density one at z. These results have since been applied to solve two open problems on the interaction between the Turing degrees of Martin-Löf random reals and K-trivial sets: the noncupping and covering problems. We say that f : [0, 1] → ℝ satisfies the Denjoy alternative at z ∈ [0, 1] if either the derivative f′(z) exists, or the upper and lower derivatives at z are +∞ and -∞, respectively. The Denjoy–Young–Saks theorem states that every function f : [0, 1] → ℝ satisfies the Denjoy alternative at almost every z ∈ [0, 1]. We answer a question posed by Kučera in 2004 by showing that a real z is computably random if and only if every computable function f satisfies the Denjoy alternative at z. For Markov computable functions, which are only defined on computable reals, we can formulate the Denjoy alternative using pseudo-derivatives. Call a real zDA-random if every Markov computable function satisfies the Denjoy alternative at z. We considerably strengthen a result of Demuth (Comment. Math. Univ. Carolin.24(3) (1983) 391–406) by showing that every Turing incomplete Martin-Löf random real is DA-random. The proof involves the notion of nonporosity, a variant of density, which is the bridge between the two themes of this paper. We finish by showing that DA-randomness is incomparable with Martin-Löf randomness.

We propose an extension of Aczel's constructive set theory CZF by an axiom for inductive types and a choice principle, and show that this extension has the following properties: it is interpretable in Martin-Löf's type theory (hence acceptable from a constructive and generalized-predicative standpoint). In addition, it is strong enough to prove the Set Compactness theorem and the results in formal topology which make use of this theorem. Moreover, it is stable under the standard constructions from algebraic set theory, namely exact completion, realizability models, forcing as well as more general sheaf extensions. As a result, methods from our earlier work can be applied to show that this extension satisfies various derived rules, such as a derived compactness rule for Cantor space and a derived continuity rule for Baire space. Finally, we show that this extension is robust in the sense that it is also reflected by the model constructions from algebraic set theory just mentioned.

Assume V = L(ℝ, μ) ⊨ ZF + DC + Θ > ω₂ + μ is a normal fine measure on 𝒫_ω1(ℝ). We analyze what sets of reals are determined and in fact show that L(ℝ, μ) ⊨ AD. This arguably gives the most optimal characterization of AD in L(ℝ, μ). As a consequence of this analysis, we obtain the equiconsistency of the theories: "ZFC + there are ω² Woodin cardinals" and "ZF + DC + Θ > ω₂ + there is a normal fine measure on 𝒫_ω1(ℝ)".