This paper contains a proof–theoretic account of unification in intermediate logics. It is shown that many existing results can be extended to fragments that at least contain implication and conjunction. For such fragments, the connection between valuations and most general unifiers is clarified, and it is shown how from the closure of a formula under the Visser rules a proof of the formula under a projective unifier can be obtained. This implies that in the logics considered, for the n-unification type to be finitary it suffices that the m-th Visser rule is admissible for a sufficiently large m. At the end of the paper it is shown how these results imply several well-known results from the literature.

Algorithmic randomness was originally defined for Cantor space with the fair-coin measure. Recent work has examined algorithmic randomness in new contexts, in particular closed subsets of 2ɷ ([2] and [8]). In this paper we use the probability theory of closed set-valued random variables (RACS) to extend the definition of Martin-Löf randomness to spaces of closed subsets of locally compact, Hausdorff, second countable topological spaces. This allows for the study of Martin-Löf randomness in many new spaces, but also gives a new perspective on Martin-Löf randomness for 2ɷ and on the algorithmically random closed sets of [2] and [8]. The first half of this paper is devoted to developing the machinery of Martin-Löf randomness for general spaces of closed sets. We then prove some general results and move on to show how the algorithmically random closed sets of [2] and [8] fit into this new framework.

We consider natural ${\rm{\Sigma }}_2^1$ definable analogues of many of the classical statements that have been shown to be equivalent to CH. It is shown that these ${\rm{\Sigma }}_2^1$ analogues are equivalent to that all reals are constructible. We also prove two partition relations for ${\rm{\Sigma }}_2^1$ colourings which hold precisely when there is a non-constructible real.

We show how two iterated products of selection functions can both be used in conjunction with system T to interpret, via the dialectica interpretation and modified realizability, full classical analysis. We also show that one iterated product is equivalent over system T to Spector’s bar recursion, whereas the other is T-equivalent to modified bar recursion. Modified bar recursion itself is shown to arise directly from the iteration of a different binary product of ‘skewed’ selection functions. Iterations of the dependent binary products are also considered but in all cases are shown to be T-equivalent to the iteration of the simple products.

For each Turing machine ${\cal T}$, we construct an algebra $\mathbb{A}$′$\left( {\cal T} \right)$ such that the variety generated by $\mathbb{A}$′$\left( {\cal T} \right)$ has definable principal subcongruences if and only if ${\cal T}$ halts, thus proving that the property of having definable principal subcongruences is undecidable for a finite algebra. A consequence of this is that there is no algorithm that takes as input a finite algebra and decides whether that algebra is finitely based.

We introduce the safe recursive set functions based on a Bellantoni–Cook style subclass of the primitive recursive set functions. We show that the functions computed by safe recursive set functions under a list encoding of finite strings by hereditarily finite sets are exactly the polynomial growth rate functions computed by alternating exponential time Turing machines with polynomially many alternations. We also show that the functions computed by safe recursive set functions under a more efficient binary tree encoding of finite strings by hereditarily finite sets are exactly the quasipolynomial growth rate functions computed by alternating quasipolynomial time Turing machines with polylogarithmic many alternations.

We characterize the safe recursive set functions on arbitrary sets in definability-theoretic terms. In its strongest form, we show that a function on arbitrary sets is safe recursive if and only if it is uniformly definable in some polynomial level of a refinement of Jensen's J-hierarchy, relativized to the transitive closure of the function's arguments.

We observe that safe recursive set functions on infinite binary strings are equivalent to functions computed by infinite-time Turing machines in time less than ωω. We also give a machine model for safe recursive set functions which is based on set-indexed parallel processors and the natural bound on running times.

In this paper, we explore the structure theory of L(ℝ, μ) under the hypothesis L(ℝ, μ) ⊧ “AD + μ is a normal fine measure on ” and give some applications. First we show that “ ZFC + there exist ω2 Woodin cardinals”1 has the same consistency strength as “ AD + ω1 is ℝ-supercompact”. During this process we show that if L(ℝ, μ) ⊧ AD then in fact L(ℝ, μ) ⊧ AD+. Next we prove important properties of L(ℝ, μ) including Σ1 -reflection and the uniqueness of μ in L(ℝ, μ). Then we give the computation of full HOD in L(ℝ, μ). Finally, we use Σ1 -reflection and ℙmax forcing to construct a certain ideal on (or equivalently on in this situation) that has the same consistency strength as “ZFC+ there exist ω2 Woodin cardinals.”

An expansion of a definably complete field either defines a discrete subring, or the image of every definable discrete set under every definable map is nowhere dense. As an application we show a definable version of Lebesgue’s differentiation theorem.

Theorem. Suppose that k = (K, $$\prec_k$$) is an ℵ0-presentable abstract elementary class with Löwenheim–Skolem number ℵ0, satisfying the joint embedding and amalgamation properties in ℵ0. If K has only countably many models in ℵ1, then all are small. If, in addition, k is almost Galois ω-stable then k is Galois ω-stable. Suppose that k = (K, $$\prec_k$$) is an ℵ0-presented almost Galois ω-stable AEC satisfying amalgamation for countable models, and having a model of cardinality ℵ1. The assertion that K is ℵ1-categorical is then absolute.

The Axiom of Strong Condensation, first introduced by Woodin in [14], is an abstract version of the Condensation Lemma of L. In this paper, we construct a set-sized forcing to obtain Strong Condensation for H(ω2). As an application, we show that “ZFC + Axiom of Strong Condensation + ”is consistent, which answers a question in [14]. As another application, we give a partial answer to a question of Jech by proving that “ZFC + there is a supercompact cardinal + any ideal on ω1 which is definable over H(ω2) is not precipitous” is consistent under sufficient large cardinal assumptions.

Presburger arithmetic is the first-order theory of the natural numbers with addition (but no multiplication). We characterize sets that can be defined by a Presburger formula as exactly the sets whose characteristic functions can be represented by rational generating functions; a geometric characterization of such sets is also given. In addition, if p = (p1, . . . , pn) are a subset of the free variables in a Presburger formula, we can define a counting function g(p) to be the number of solutions to the formula, for a given p. We show that every counting function obtained in this way may be represented as, equivalently, either a piecewise quasi-polynomial or a rational generating function. Finally, we translate known computational complexity results into this setting and discuss open directions.

Exploring further the properties of ITRM-recognizable reals started in [1], we provide a detailed analysis of recognizable reals and their distribution in Gödels constructible universe L. In particular, we show that new unrecognizable reals are generated at every index $\gamma \, \ge \,\omega _\omega ^{CK}$. We give a machine-independent characterization of recognizability by proving that a real r is recognizable if and only if it is ${\Sigma _1}$-definable over ${L_{\omega _\omega ^{CK,\,r}}}$ and that $r\, \in \,{L_{\omega _\omega ^{CK,\,r}}}$ for every recognizable real r and show that either every or no r with $r\, \in \,{L_{\omega _\omega ^{CK,\,r}}}$ generated over an index stage ${L_\gamma }$ is recognizable. Finally, the techniques developed along the way allow us to prove that the halting number for ITRMs is recognizable and that the set of ITRM-computable reals is not ITRM-decidable.

We show that the theory of a nondegenerate representation of a C*-algebra ${\cal A}$ over a Hilbert space H is superstable. Also, we characterize forking, orthogonality and domination of types.

The relativized weak pigeonhole principle states that if at least 2n out of n2 pigeons fly into n holes, then some hole must be doubly occupied. We prove that every DNF-refutation of the CNF encoding of this principle requires size $2^{\left( {{\rm{log\ }}n} \right)^{3/2 - \varepsilon } } $ for every ε﹥0 and every sufficiently large n. By reducing it to the standard weak pigeonhole principle with 2n pigeons and n holes, we also show that this lower bound is essentially tight in that there exist DNF-refutations of size $2^{\left( {{\rm{log\ }}n} \right)^{O\left( 1 \right)} } $ even in R(log). For the lower bound proof we need to discuss the existence of unbalanced low-degree bipartite expanders satisfying a certain robustness condition.

We study the strengths of various notions of higher randomness: (i) strong ${\rm{\Pi }}_1^1$randomness is separated from ${\rm{\Pi }}_1^1$randomness; (ii) the hyperdegrees of ${\rm{\Pi }}_1^1$random reals are closed downwards (except for the trivial degree); (iii) the reals z in $NC{R_{{\rm{\Pi }}_1^1}}$ are precisely those satisfying $z \in {L_{\omega _1^z}}$ and (iv) lowness for ${\rm{\Delta }}_1^1$randomness is strictly weaker than that for ${\rm{\Pi }}_1^1$randomness.

In this note we investigate the question when a henselian valued field carries a nontrivial ∅-definable henselian valuation (in the language of rings). This is clearly not possible when the field is either separably or real closed, and, by the work of Prestel and Ziegler, there are further examples of henselian valued fields which do not admit a ∅-definable nontrivial henselian valuation. We give conditions on the residue field which ensure the existence of a parameter-free definition. In particular, we show that a henselian valued field admits a nontrivial henselian ∅-definable valuation when the residue field is separably closed or sufficiently nonhenselian, or when the absolute Galois group of the (residue) field is nonuniversal.

Every complete first order theory has a corresponding complete theory in continuous logic, called the randomization theory. It has two sorts, a sort for random elements of models of the first order theory, and a sort for events. In this paper we establish connections between properties of countable models of a first order theory and corresponding properties of separable models of the randomization theory. We show that the randomization theory has a prime model if and only if the first order theory has a prime model. And the randomization theory has the same number of separable homogeneous models as the first order theory has countable homogeneous models. We also show that when T has at most countably many countable models, each separable model of TR is uniquely characterized by a probability density function on the set of isomorphism types of countable models of T. This yields an analogue for randomizations of the results of Baldwin and Lachlan on countable models of ω1-categorical first order theories.

We develop Fraïssé theory, namely the theory of Fraïssé classes and Fraïssé limits, in the context of metric structures. We show that a class of finitely generated structures is Fraïssé if and only if it is the age of a separable approximately homogeneous structure, and conversely, that this structure is necessarily the unique limit of the class, and is universal for it.

We do this in a somewhat new approach, in which “finite maps up to errors” are coded by approximate isometries.

Let Z2, Z3, and Z4 denote 2nd, 3rd, and 4th order arithmetic, respectively. We let Harrington’s Principle, HP, denote the statement that there is a real x such that every x-admissible ordinal is a cardinal in L. The known proofs of Harrington’s theorem “$Det\left( {{\rm{\Sigma }}_1^1} \right)$ implies 0♯ exists” are done in two steps: first show that $Det\left( {{\rm{\Sigma }}_1^1} \right)$ implies HP, and then show that HP implies 0♯ exists. The first step is provable in Z2. In this paper we show that Z2 + HP is equiconsistent with ZFC and that Z3 + HP is equiconsistent with ZFC + there exists a remarkable cardinal. As a corollary, Z3 + HP does not imply 0♯ exists, whereas Z4 + HP does. We also study strengthenings of Harrington’s Principle over 2nd and 3rd order arithmetic.

We give a new, simplified and detailed account of the correspondence between levels of the Sherali–Adams relaxation of graph isomorphism and levels of pebble-game equivalence with counting (higher-dimensional Weisfeiler–Lehman colour refinement). The correspondence between basic colour refinement and fractional isomorphism, due to Tinhofer [22; 23] and Ramana, Scheinerman and Ullman [17], is re-interpreted as the base level of Sherali–Adams and generalised to higher levels in this sense by Atserias and Maneva [1] and Malkin [14], who prove that the two resulting hierarchies interleave. In carrying this analysis further, we here give (a) a precise characterisation of the level k Sherali–Adams relaxation in terms of a modified counting pebble game; (b) a variant of the Sherali–Adams levels that precisely match the k-pebble counting game; (c) a proof that the interleaving between these two hierarchies is strict. We also investigate the variation based on boolean arithmetic instead of real/rational arithmetic and obtain analogous correspondences and separations for plain k-pebble equivalence (without counting). Our results are driven by considerably simplified accounts of the underlying combinatorics and linear algebra.