We describe the countable ordinals in terms of iterations of Mostowski collapsings. This gives a proof-theoretic bound on definable countable ordinals in Zermelo-Fraenkel set theory ZF.

For every natural number m, the existentially closed models of the theory of fields with m commuting derivations can be given a first-order geometric characterization in several ways. In particular, the theory of these differential fields has a model-companion. The axioms are that certain differential varieties determined by certain ordinary varieties are nonempty. There is no restriction on the characteristic of the underlying field.

This article addresses the question which structures occur as fixed structures of stable structures with a generic automorphism. In particular we give a Galois theoretic characterization. Furthermore, we prove that any pseudofinite field is the fixed field of some model of ACFA, any one-free pseudo-differentially closed field of characteristic zero is the fixed field of some model of DCFA, and that any one-free PAC field of finite degree of imperfection is the fixed field of some model of SCFA.

We study model theoretic properties of valued fields (equipped with a real-valued multiplicative valuation), viewed as metric structures in continuous first order logic.

For technical reasons we prefer to consider not the valued field (K, |·|) directly, but rather the associated projective spaces KPn, as bounded metric structures.

We show that the class of (projective spaces over) metric valued fields is elementary, with theory MVF, and that the projective spaces Pn and are Pm biinterpretable for every n, m ≥ 1. The theory MVF admits a model completion ACMVF, the theory of algebraically closed metric valued fields (with a nontrivial valuation). This theory is strictly stable (even up to perturbation).

Similarly, we show that the theory of real closed metric valued fields, RCMVF, is the model companion of the theory of formally real metric valued fields, and that it is dependent.

The K-trivial sets form an ideal in the Turing degrees, which is generated by its computably enumerable (c.e.) members and has an exact pair below the degree of the halting problem. The question of whether it has an exact pair in the c.e. degrees was first raised in [22, Question 4.2] and later in [25, Problem 5.5.8].

We give a negative answer to this question. In fact, we show the following stronger statement in the c.e. degrees. There exists a K-trivial degree d such that for all degrees a, b which are not K-trivial and a > d, b > d there exists a degree v which is not K-trivial and a > v, b > v. This work sheds light to the question of the definability of the K-trivial degrees in the c.e. degrees.

This paper is devoted to o-minimalism, the study of the first-order properties of o-minimal structures. The main protagonists are the pseudo-o-minimal structures, that is to say, the models of the theory of all o-minimal L-structures, but we start with a more in-depth analysis of the well-known fragment DCTC (Definable Completeness/Type Completeness), and show how it already admits many of the properties of o-minimal structures: dimension theory, monotonicity, Hardy structures, and quasi-cell decomposition, provided one replaces finiteness by discreteness in all of these. Failure of cell decomposition leads to the related notion of a eukaryote structure, and we give a criterium for a pseudo-o-minimal structure to be eukaryote.

To any pseudo-o-minimal structure, we can associate its Grothendieck ring, which in the non-o-minimal case is a nontrivial invariant. To study this invariant, we identify a third o-minimalistic property, the Discrete Pigeonhole Principle, which in turn allows us to define discretely valued Euler characteristics. As an application, we study certain analytic subsets, called Taylor sets.

By the complexity of a finite sequence of 0’s and 1’s we mean the Kolmogorov complexity, that is the length of the shortest input to a universal recursive function which returns the given sequence as output. By initial segment complexity of an infinite sequence of 0’s and 1’s we mean the asymptotic behavior of the complexity of its finite initial segments. In this paper, we construct infinite sequences of 0’s and 1’s with given recursive lower bounds on initial segment complexity which do not compute any infinite sequences of 0’s and 1’s with a significantly larger recursive lower bound on initial segment complexity. This improves several known results about randomness extraction and separates many natural degrees in the lattice of Muchnik degrees.

Many classes of structures have natural functions and relations on them: concatenation of linear orders, direct product of groups, disjoint union of equivalence structures, and so on. Here, we study the (un)decidability of the theory of several natural classes of structures with appropriate functions and relations. For some of these classes of structures, the resulting theory is decidable; for some of these classes of structures, the resulting theory is bi-interpretable with second-order arithmetic.

We prove in particular that, in a large class of dp-minimal theories including the p-adics, definable types are dense amongst nonforking types.

We show that R.J. Thompson’s groups F and T are bi-interpretable with the ring of the integers. From a result by A. Khélif, these groups are quasi-finitely axiomatizable and prime. So, the group T provides an example of a simple group which is quasi-finitely axiomatizable and prime. This answers questions posed by T. Altınel and A. Muranov in [2], and by A. Nies in [12].

We give a uniform construction of free pseudospaces of dimension n extending work in [1]. This yields examples of ω-stable theories which are n-ample, but not n + 1-ample. The prime models of these theories are buildings associated to certain right-angled Coxeter groups.

Let ${\cal N}\left( G \right)$ be the maximal normal definable torsion-free subgroup of a group G definable in an o-minimal structure M. We prove that the quotient $G/{\cal N}\left( G \right)$ has a maximal definably compact subgroup K, which is definably connected and unique up to conjugation. Moreover, we show that K has a definable torsion-free complement, i.e., there is a definable torsion-free subgroup H such that $G/{\cal N}\left( G \right) = K \cdot H$ and $K\mathop \cap \nolimits^ \,H = \left\{ e \right\}$. It follows that G is definably homeomorphic to $K \times {M^s}$ (with $s = {\rm{dim}}\,G - {\rm{dim}}\,K$), and homotopy equivalent to K. This gives a (definably) topological reduction to the compact case, in analogy with Lie groups.

Assuming ω supercompact cardinals we force to obtain a model where the tree property holds both at אω+1, and at אn for all 2 ≤ n < ω. A model with the former was obtained by Magidor–Shelah from a large cardinal assumption above a huge cardinal, and recently by Sinapova from ω supercompact cardinals. A model with the latter was obtained by Cummings–Foreman from ω supercompact cardinals. Our model, where the two hold simultaneously, is another step toward the goal of obtaining the tree property on increasingly large intervals of successor cardinals.

This paper has two parts. In the first one, we prove that an invariant dp-minimal type is either finitely satisfiable or definable. We also prove that a definable version of the (p,q)-theorem holds in dp-minimal theories of small or medium directionality.

In the second part, we study dp-rank in dp-minimal theories and show that it enjoys many nice properties. It is continuous, definable in families and it can be characterised geometrically with no mention of indiscernible sequences. In particular, if the structure expands a divisible ordered abelian group, then dp-rank coincides with the dimension coming from the order.

Fix a language extending the language of ordered fields by at least one new predicate or function symbol. Call an L-structure R pseudo-o-minimal if it is (elementarily equivalent to) an ultraproduct of o-minimal structures. We show that for any recursive list of L-sentences , there is a real closed field satisfying which is not pseudo-o-minimal. This shows that the theory To−min consisting of those -sentences true in all o-minimal -structures, also called the theory of o-minimality (for L), is not recursively axiomatizable. And, in particular, there are locally o-minimal, definably complete expansions of real closed fields which are not pseudo-o-minimal.

This article reports that some robustness of the notions of predicativity and of autonomous progression is broken down if as the given infinite total entity we choose some mathematical entities other than the traditional ω. Namely, the equivalence between normal transfinite recursion scheme and new dependent transfinite recursion scheme, which does hold in the context of subsystems of second order number theory, does not hold in the context of subsystems of second order set theory where the universe V of sets is treated as the given totality (nor in the contexts of those of n+3-th order number or set theories, where the class of all n+2-th order objects is treated as the given totality).

We study computably enumerable equivalence relations (ceers), under the reducibility $R \le S$ if there exists a computable function f such that $x\,R\,y$ if and only if $f\left( x \right)\,\,S\,f\left( y \right)$, for every $x,y$. We show that the degrees of ceers under the equivalence relation generated by $\le$ form a bounded poset that is neither a lower semilattice, nor an upper semilattice, and its first-order theory is undecidable. We then study the universal ceers. We show that 1) the uniformly effectively inseparable ceers are universal, but there are effectively inseparable ceers that are not universal; 2) a ceer R is universal if and only if $R\prime \le R$, where $R\prime$ denotes the halting jump operator introduced by Gao and Gerdes (answering an open question of Gao and Gerdes); and 3) both the index set of the universal ceers and the index set of the uniformly effectively inseparable ceers are ${\rm{\Sigma }}_3^0$-complete (the former answering an open question of Gao and Gerdes).

Let L be a recursive algebraic extension of ℚ. Assume that, given α ∈ L, we can compute the roots in L of its minimal polynomial over ℚ and we can determine which roots are Aut(L)-conjugate to α. We prove that there exists a pair of polynomials that characterizes the Aut(L)-conjugates of α, and that these polynomials can be effectively computed. Assume furthermore that L can be embedded in ℝ, or in a finite extension of ℚp (with p an odd prime). Then we show that subsets of L[X]k that are recursively enumerable for every recursive presentation of L[X], are diophantine over L[X].

We give a model-theoretic account for several results regarding sequences of random variables appearing in Berkes and Rosenthal [12]. In order to do this,

• • We study and compare three notions of convergence of types in a stable theory: logic convergence, i.e., formula by formula, metric convergence (both already well studied) and convergence of canonical bases. In particular, we characterise א0-categorical stable theories in which the last two agree.

• • We characterise sequences that admit almost indiscernible sub-sequences.

• • We apply these tools to the theory of atomless random variables (ARV). We characterise types and notions of convergence of types as conditional distributions and weak/strong convergence thereof, and obtain, among other things, the Main Theorem of Berkes and Rosenthal.

We investigate Talagrand’s construction of an exhaustive pathological submeasure. We consider the forcing associated with this submeasure and we also begin an effort to explicitly describe this construction.