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.

We analyze the models $L[T_{2n} ]$, where $T_{2n}$ is a tree on $\omega \times \kappa _{2n + 1}^1 $ projecting to a universal ${\rm{\Pi }}_{2n}^1 $ set of reals, for $n > 1$. Following Hjorth’s work on $L[T_2 ]$, we show that under ${\rm{Det}}\left( {{\rm{}}_{2n}^1 } \right)$, the models $L[T_{2n} ]$ are unique, that is they do not depend of the choice of the tree $T_{2n}$. This requires a generalization of the Kechris–Martin theorem to all pointclasses${\rm{\Pi }}_{2n + 1}^1$. We then characterize these models as constructible models relative to the direct limit of all countable nondropping iterates of${\cal M}_{2n + 1}^\# $. We then show that the GCH holds in $L[T_{2n} ]$, for every $n < \omega $, even though they are not extender models. This analysis localizes the HOD analysis of Steel and Woodin at the even levels of the projective hierarchy.

We show that the polynomial translation of the classical propositional normal modal logic S4 into the intuitionistic propositional logic Int from Fernández is incorrect. We give a modified translation and prove its correctness, and provide implementations of both translations to allow others to test our results.

We investigate some versions of amoeba for tree-forcings in the generalized Cantor and Baire spaces. This answers [10, Question 3.20] and generalizes a line of research that in the standard case has been studied in [11], [13], and [7]. Moreover, we also answer questions posed in [3] by Friedman, Khomskii, and Kulikov, about the relationships between regularity properties at uncountable cardinals. We show ${\bf{\Sigma }}_1^1$-counterexamples to some regularity properties related to trees without club splitting. In particular we prove a strong relationship between the Ramsey and the Baire properties, in slight contrast with the standard case.

The concept of jointness for guessing principles, specifically ${\diamondsuit _\kappa }$ and various Laver diamonds, is introduced. A family of guessing sequences is joint if the elements of any given sequence of targets may be simultaneously guessed by the members of the family. While equivalent in the case of ${\diamondsuit _\kappa }$, joint Laver diamonds are nontrivial new objects. We give equiconsistency results for most of the large cardinals under consideration and prove sharp separations between joint Laver diamonds of different lengths in the case of θ-supercompact cardinals.

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$.

We introduce a mouse whose derived model satisfies $AD_ + {\rm{\Theta }} \ge \theta _{\aleph _2 } $. More generally, we will introduce a class of large cardinal properties yielding mice whose derived models can satisfy properties as strong as $AD_ + {\rm{\Theta }} = \theta _{\rm{\Theta }} $.

A sequence of graphs is FO-convergent if the probability of satisfaction of every first-order formula converges. A graph modeling is a graph, whose domain is a standard probability space, with the property that every definable set is Borel. It was known that FO-convergent sequence of graphs do not always admit a modeling limit, but it was conjectured that FO-convergent sequences of sufficiently sparse graphs have a modeling limits. Precisely, two conjectures were proposed:

1. 1. If a FO-convergent sequence of graphs is residual, that is if for every integer d the maximum relative size of a ball of radius d in the graphs of the sequence tends to zero, then the sequence has a modeling limit.

2. 2. A monotone class of graphs ${\cal C}$ has the property that every FO-convergent sequence of graphs from ${\cal C}$ has a modeling limit if and only if ${\cal C}$ is nowhere dense, that is if and only if for each integer p there is $N\left( p \right)$ such that no graph in ${\cal C}$ contains the pth subdivision of a complete graph on $N\left( p \right)$ vertices as a subgraph.

In this article we prove both conjectures. This solves some of the main problems in the area and among others provides an analytic characterization of the nowhere dense–somewhere dense dichotomy.

We study the two model-theoretic concepts of weak saturation and weak amalgamation property in the context of accessible categories. We relate these two concepts providing sufficient conditions for existence and uniqueness of weakly saturated objects of an accessible category ${\cal K}$. We discuss the implications of this fact in classical model theory.

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.

Motivated by the search for a logic for polynomial time, we study rank logic (FPR) which extends fixed-point logic with counting (FPC) by operators that determine the rank of matrices over finite fields. While FPR can express most of the known queries that separate FPC from Ptime, almost nothing was known about the limitations of its expressive power.

In our first main result we show that the extensions of FPC by rank operators over different prime fields are incomparable. This solves an open question posed by Dawar and Holm and also implies that rank logic, in its original definition with a distinct rank operator for every field, fails to capture polynomial time. In particular we show that the variant of rank logic ${\text{FPR}}^{\text{*}}$ with an operator that uniformly expresses the matrix rank over finite fields is more expressive than FPR.

One important step in our proof is to consider solvability logic FPS which is the analogous extension of FPC by quantifiers which express the solvability problem for linear equation systems over finite fields. Solvability logic can easily be embedded into rank logic, but it is open whether it is a strict fragment. In our second main result we give a partial answer to this question: in the absence of counting, rank operators are strictly more expressive than solvability quantifiers.

The classical Halpern–Läuchli theorem states that for any finite coloring of a finite product of finitely branching perfect trees of height ω, there exist strong subtrees sharing the same level set such that tuples in the product of the strong subtrees consisting of elements lying on the same level get the same color. Relative to large cardinals, we establish the consistency of a tail cone version of the Halpern–Läuchli theorem at a large cardinal (see Theorem 3.1), which, roughly speaking, deals with many colorings simultaneously and diagonally. Among other applications, we generalize a polarized partition relation on rational numbers due to Laver and Galvin to one on linear orders of larger saturation.

A category has the amalgamation property (AP) if every pushout diagram has a cocone, and the joint embedding property (JEP) if every finite coproduct diagram has a cocone. We show that for a finitely generated category I, the following are equivalent: (i) every I-shaped diagram in a category with the AP and the JEP has a cocone; (ii) every I-shaped diagram in the category of sets and injections has a cocone; (iii) a certain canonically defined category ${\cal L}\left( {\bf{I}} \right)$ of “paths” in I has only idempotent endomorphisms. When I is a finite poset, these are further equivalent to: (iv) every upward-closed subset of I is simply-connected; (v) I can be built inductively via some simple rules. Our proof also shows that these conditions are decidable for finite I.

In this article we explore some properties of H-structures which are introduced in [2]. We describe a construction of H-structures based on one-dimensional asymptotic classes which preserves pseudofiniteness. That is, the H-structures we construct are ultraproducts of finite structures. We also prove that under the assumption that the base theory is supersimple of SU-rank one, there are no new definable groups in H-structures. This improves the corresponding result in [2].

Let an oracle be called low for prefix-free complexity on a set in case access to the oracle improves the prefix-free complexities of the members of the set at most by an additive constant. Let an oracle be called weakly low for prefix-free complexity on a set in case the oracle is low for prefix-free complexity on an infinite subset of the given set. Furthermore, let an oracle be called low and weakly for prefix-free complexity along a sequence in case the oracle is low and weakly low, respectively, for prefix-free complexity on the set of initial segments of the sequence. Our two main results are the following characterizations. An oracle is low for prefix-free complexity if and only if it is low for prefix-free complexity along some sequences if and only if it is low for prefix-free complexity along all sequences. An oracle is weakly low for prefix-free complexity if and only if it is weakly low for prefix-free complexity along some sequence if and only if it is weakly low for prefix-free complexity along almost all sequences. As a tool for proving these results, we show that prefix-free complexity differs from its expected value with respect to an oracle chosen uniformly at random at most by an additive constant, and that similar results hold for related notions such as a priori probability. Furthermore, we demonstrate that on every infinite set almost all oracles are weakly low but are not low for prefix-free complexity, while by Shoenfield absoluteness there is an infinite set on which uncountably many oracles are low for prefix-free complexity. Finally, we obtain no-gap results, introduce weakly low reducibility, or WLK-reducibility for short, and show that all its degrees except the greatest one are countable.

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 provide dichotomy results characterizing when two disjoint analytic binary relations can be separated by a countable union of ${\bf{\Sigma }}_1^0 \times {\bf{\Sigma }}_\xi ^0$ sets, or by a ${\bf{\Pi }}_1^0 \times {\bf{\Pi }}_\xi ^0$ set.

An equation to compute the dp-rank of any abelian group is given. It is also shown that its dp-rank, or more generally that of any one-based group, agrees with its Vapnik–Chervonenkis density. Furthermore, strong abelian groups are characterised to be precisely those abelian groups A such that there are only finitely many primes p such that the group A / pA is infinite and for every prime p, there are only finitely many natural numbers n such that $\left( {p^n A} \right)[p]/\left( {p^{n + 1} A} \right)[p]$ is infinite.

Finally, it is shown that an infinite stable field of finite dp-rank is algebraically closed.

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 give examples of calculi that extend Gentzen’s sequent calculus LK by unsound quantifier inferences in such a way that (i) derivations lead only to true sequents, and (ii) proofs therein are nonelementarily shorter than LK-proofs.