Fix an integer $r \ge 3$. We consider metric spaces on n points such that the distance between any two points lies in $\left\{ {1, \ldots ,r} \right\}$. Our main result describes their approximate structure for large n. As a consequence, we show that the number of these metric spaces is $\left\lceil {{{r + 1} \over 2}} \right\rceil ^{\left( {\matrix{ n \cr 2 \cr } } \right) + o\left( {n^2 } \right)} .$

Related results in the continuous setting have recently been proved by Kozma, Meyerovitch, Peled, and Samotij [34]. When r is even, our structural characterization is more precise and implies that almost all such metric spaces have all distances at least $r/2$. As an easy consequence, when r is even, we improve the error term above from $o\left( {n^2 } \right)$ to $o\left( 1 \right)$, and also show a labeled first-order 0-1 law in the language ${\cal L}_r $, consisting of r binary relations, one for each element of $[r]$ . In particular, we show the almost sure theory T is the theory of the Fraïssé limit of the class of all finite simple complete edge-colored graphs with edge colors in $\left\{ {r/2, \ldots ,r} \right\}$.

Our work can be viewed as an extension of a long line of research in extremal combinatorics to the colored setting, as well as an addition to the collection of known structures that admit logical 0-1 laws.

Jockusch showed that 2-generic degrees are downward dense below a 2-generic degree. That is, if a is 2-generic, and $0 < {\bf{b}} < {\bf{a}}$, then there is a 2-generic g with $0 < {\bf{g}} < {\bf{b}}.$ In the case of 1-generic degrees Kumabe, and independently Chong and Downey, constructed a minimal degree computable from a 1-generic degree. We explore the tightness of these results.

We solve a question of Barmpalias and Lewis-Pye by constructing a minimal degree computable from a weakly 2-generic one. While there have been full approximation constructions of ${\rm{\Delta }}_3^0$ minimal degrees before, our proof is rather novel since it is a computable full approximation construction where both the generic and the minimal degrees are ${\rm{\Delta }}_3^0 - {\rm{\Delta }}_2^0$.

Classically, any structure for a signature ${\rm{\Sigma }}$ may be completed to a model of a desired regular theory ${T}}$ by means of the chase construction or small object argument. Moreover, this exhibits ${\rm{Mod}}\left(T)$ as weakly reflective in ${\rm{Str}}\left( {\rm{\Sigma }} \right)$.

We investigate this in the constructive setting. The basic construction is unproblematic; however, it is no longer a weak reflection. Indeed, we show that various reflectivity principles for models of regular theories are equivalent to choice principles in the ambient set theory. However, the embedding of a structure into its chase-completion still satisfies a conservativity property, which suffices for applications such as the completeness of regular logic with respect to Tarski (i.e., set) models.

Unlike most constructive developments of predicate logic, we do not assume that equality between symbols in the signature is decidable. While in this setting, we also give a version of one classical lemma which is trivial over discrete signatures but more interesting here: the abstraction of constants in a proof to variables.

This article presents two theorems: (1) a generalization of Löb’s Theorem that applies to formal proof systems operating with bounded computational resources, such as formal verification software or theorem provers, and (2) a theorem on the robust cooperation of agents that employ proofs about one another’s source code as unexploitable criteria for cooperation. The latter illustrates a capacity for outperforming classical Nash equilibria and correlated equilibria, attaining mutually cooperative program equilibrium in the Prisoner’s Dilemma while remaining unexploitable, i.e., sometimes achieving the outcome (Cooperate, Cooperate), and never receiving the outcome (Cooperate, Defect) as player 1.

We consider the version of Pure Inductive Logic which obtains for the language with equality and a single unary function symbol giving a complete characterization of the probability functions on this language which satisfy Constant Exchangeability.

We answer several questions posed by Hamkins and Leahy concerning the implicitly constructible universe Imp, which they introduced in [5]. Specifically, we show that it is relatively consistent with ZFC that $$Imp = \neg {\rm{CH}}$$, that $Imp \ne {\rm{HOD}}$, and that $$Imp \models V \ne Imp$$, or in other words, that $\left( {Imp} \right)^{Imp} \ne Imp$.

We investigate the connections between computability theory and Nonstandard Analysis. In particular, we investigate the two following topics and show that they are intimately related.

(T.1) A basic property of Cantor space$2^ $ is Heine–Borel compactness: for any open covering of $2^ $, there is a finite subcovering. A natural question is: How hard is it to compute such a finite subcovering? We make this precise by analysing the complexity of so-called fan functionals that given any $G:2^ \to $, output a finite sequence $\langle f_0 , \ldots ,f_n \rangle $ in $2^ $ such that the neighbourhoods defined from $\overline {f_i } G\left( {f_i } \right)$ for $i \le n$ form a covering of $2^ $.

(T.2) A basic property of Cantor space in Nonstandard Analysis is Abraham Robinson’s nonstandard compactness, i.e., that every binary sequence is “infinitely close” to a standard binary sequence. We analyse the strength of this nonstandard compactness property of Cantor space, compared to the other axioms of Nonstandard Analysis and usual mathematics.

Our study of (T.1) yields exotic objects in computability theory, while (T.2) leads to surprising results in Reverse Mathematics. We stress that (T.1) and (T.2) are highly intertwined, i.e., our study is holistic in nature in that results in computability theory yield results in Nonstandard Analysis and vice versa.

We show that, assuming the existence of the canonical inner model with one Woodin cardinal $M_1 $ , there is a model of $ZFC$ in which the nonstationary ideal on $\omega _1 $ is $\aleph _2 $-saturated and whose reals admit a ${\rm{\Sigma }}_4^1 $-wellorder.

Varieties of the Fan Theorem have recently been developed in reverse constructive mathematics, corresponding to different continuity principles. They form a natural implicational hierarchy. Earlier work showed all of these implications to be strict. Here we reprove one of the strictness results, using very different arguments. The technique used is a mixture of realizability, forcing in the guise of Heyting-valued models, and Kripke models.

We prove that every ultraproduct of p-adics is inp-minimal (i.e., of burden 1). More generally, we prove an Ax-Kochen type result on preservation of inp-minimality for Henselian valued fields of equicharacteristic 0 in the RV language.

We show that for each computable ordinal $\alpha > 0$ it is possible to find in each Martin-Löf random ${\rm{\Delta }}_2^0 $ degree a sequence R of Cantor-Bendixson rank α, while ensuring that the sequences that inductively witness R’s rank are all Martin-Löf random with respect to a single countably supported and computable measure. This is a strengthening for random degrees of a recent result of Downey, Wu, and Yang, and can be understood as a randomized version of it.

The variety of Brouwerian semilattices is amalgamable and locally finite; hence, by well-known results [19], it has a model completion (whose models are the existentially closed structures). In this article, we supply a finite and rather simple axiomatization of the model completion.

We will show it is consistent with GCH that there is a minimal non-σ-scattered linear order which does not contain any real or Aronszajn type. In particular the assumption PFA+ in the main result of [5] is necessary, and there are other obstructions than real and Aronszajn types to the sharpness of Laver’s theorem in [8].

We consider maximal almost disjoint families of block subspaces of countable vector spaces, focusing on questions of their size and definability. We prove that the minimum infinite cardinality of such a family cannot be decided in ZFC and that the “spectrum” of cardinalities of mad families of subspaces can be made arbitrarily large, in analogy to results for mad families on ω. We apply the author’s local Ramsey theory for vector spaces [32] to give partial results concerning their definability.

We obtain an equivalent implicit characterization of Lp Banach spaces that is amenable to a logical treatment. Using that, we obtain an axiomatization for such spaces into a higher order logical system, the kind of which is used in proof mining, a research program that aims to obtain the hidden computational content of mathematical proofs using tools from mathematical logic. As an aside, we obtain a concrete way of formalizing Lp spaces in positive-bounded logic. The axiomatization is followed by a corresponding metatheorem in the style of proof mining. We illustrate its use with the derivation for this class of spaces of the standard modulus of uniform convexity.

A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is ${\rm{\Sigma }}_1^1 $-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel.

We study genericity and randomness with respect to ITTMs, continuing the work initiated by Carl and Schlicht. To do so, we develop a framework to study randomness in the constructible hierarchy. We then answer several of Carl and Schlicht’s question. We also ask a new question one the equality of two classes of randoms. Although the natural intuition would dictate that the two classes are distinct, we show that things are not as simple as they seem. In particular we show that the categorical analogues of these two classes coincide, in contradiction with the natural intuition. Even though we are not able to answer the question for randomness in this article, we delineate and sharpen its contour and outline.

We consider a weak version of Schindler’s remarkable cardinals that may fail to be ${{\rm{\Sigma }}_2}$-reflecting. We show that the ${{\rm{\Sigma }}_2}$-reflecting weakly remarkable cardinals are exactly the remarkable cardinals, and that the existence of a non-${{\rm{\Sigma }}_2}$-reflecting weakly remarkable cardinal has higher consistency strength: it is equiconsistent with the existence of an ω-Erdős cardinal. We give an application involving gVP, the generic Vopěnka principle defined by Bagaria, Gitman, and Schindler. Namely, we show that gVP + “Ord is not ${{\rm{\Delta }}_2}$-Mahlo” and ${\text{gVP}}(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{\Pi } _1 )$ + “there is no proper class of remarkable cardinals” are both equiconsistent with the existence of a proper class of ω-Erdős cardinals, extending results of Bagaria, Gitman, Hamkins, and Schindler.

A new method for blowing up the power of a singular cardinal is presented. It allows to blow up the power of a singular in the core model cardinal of uncountable cofinality. The method makes use of overlapping extenders.