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.

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

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

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

In this paper we analyze the relationship between o-minimal structures and the notion of ω-saturated one-dimensional t.t.t structures. We prove that if removing any point from such a structure splits it into more than one definably connected component then it must be a one-dimensional simplex of a finite number of o-minimal structures. In addition, we show that even if removing points doesn’t split the structure, additional topological assumptions ensure that the structure is locally o-minimal. As a corollary we obtain the result that if an ω-saturated one-dimensional t.t.t structure admits a topological group structure then it is locally o-minimal. We also prove that the number of connected components in a definable family is uniformly bounded, which implies that an elementary extension of an ω-saturated one-dimensional t.t.t structure is t.t.t as well.

We extend our work on difference randomness. Each component of a difference test is a Boolean combination of two r.e. open sets; here we consider tests in which the kth component is a Boolean combination of g(k) r.e. open sets for a given recursive function g. We use this method to produce an alternate characterization of weak Demuth randomness in terms of these tests and further show that a real is weakly Demuth random if and only if it is Martin-Löf random and cannot compute a strongly prompt r.e. set. We conclude with a study of related lowness notions and obtain as a corollary that lowness for balanced randomness is equivalent to being recursive.

Varieties of the Fan Theorem have recently been developed in reverse constructive mathematics, corresponding to different continuity principles. They form a natural implicational hierarchy. Some of the implications have been shown to be strict, others strict in a weak context, and yet others not at all, using disparate techniques. Here we present a family of related Kripke models which separates all of the as yet identified fan theorems.

The set theory ΚΡΠN+1 for ΠN+1-reflecting universes is shown to be ΠN+1-conservative over iterations of ΠN-recursively Mahlo operations for each N ≥ 2.

Regular groups and fields are common generalizations of minimal and quasi-minimal groups and fields, so the conjectures that minimal or quasi-minimal fields are algebraically closed have their common generalization to the conjecture that each regular field is algebraically closed. Standard arguments show that a generically stable regular field is algebraically closed. Let K be a regular field which is not generically stable and let p be its global generic type. We observe that if K has a finite extension L of degree n, then P(n) has unbounded orbit under the action of the multiplicative group of L.

Known to be true in the minimal context, it remains wide open whether regular, or even quasi-minimal, groups are abelian. We show that if it is not the case, then there is a counter-example with a unique nontrivial conjugacy class, and we notice that a classical group with one nontrivial conjugacy class is not quasi-minimal, because the centralizers of all elements are uncountable. Then, we construct a group of cardinality ω1 with only one nontrivial conjugacy class and such that the centralizers of all nontrivial elements are countable.

This paper addresses the structures (M, ω) and (ω, SSy(M)), where M is a nonstandard model of PA and ω is the standard cut. It is known that (ω, SSy(M)) is interpretable in (M, ω). Our main technical result is that there is an reverse interpretation of (M, ω) in (ω, SSy(M)) which is ‘local’ in the sense of Visser [11]. We also relate the model theory of (M, ω) to the study of transplendent models of PA [2].

This yields a number of model theoretic results concerning the ω-models (M, ω) and their standard systems SSy(M, ω), including the following.

• $\left( {M,\omega } \right) \prec \left( {K,\omega } \right)$ if and only if $M \prec K$ and $\left( {\omega ,{\rm{SSy}}\left( M \right)} \right) \prec \left( {\omega ,{\rm{SSy}}\left( K \right)} \right)$.

• $\left( {\omega ,{\rm{SSy}}\left( M \right)} \right) \prec \left( {\omega ,{\cal P}\left( \omega \right)} \right)$ if and only if $\left( {M,\omega } \right) \prec \left( {{M^{\rm{*}}},\omega } \right)$ for some ω-saturated M*.

• $M{ \prec _{\rm{e}}}K$ implies SSy(M, ω) = SSy(K, ω), but cofinal extensions do not necessarily preserve standard system in this sense.

• SSy(M, ω)=SSy(M) if and only if (ω, SSy(M)) satisfies the full comprehension scheme.

• If SSy(M, ω) is uniformly defined by a single formula (analogous to a β function), then (ω, SSy(M, ω)) satisfies the full comprehension scheme; and there are models M for which SSy(M, ω) is not uniformly defined in this sense.

We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations R, S, a componentwise reducibility is defined by

R ≤ S ⇔ ∃f ∀x, y [x R y ↔ f (x) S f (y)].

Here, f is taken from a suitable class of effective functions. For us the relations will be on natural numbers, and f must be computable. We show that there is a ${\rm{\Pi }}_1^0$-complete equivalence relation, but no ${\rm{\Pi }}_k^0$-complete for k ≥ 2. We show that ${\rm{\Sigma }}_k^0$ preorders arising naturally in the above-mentioned areas are ${\rm{\Sigma }}_k^0$-complete. This includes polynomial time m-reducibility on exponential time sets, which is ${\rm{\Sigma }}_2^0$, almost inclusion on r.e. sets, which is ${\rm{\Sigma }}_3^0$, and Turing reducibility on r.e. sets, which is ${\rm{\Sigma }}_4^0$.

Define a second order tree to be a map between trees (with fixed codomain). We show that many properties of ordinary trees have analogs for second order trees. In particular, we show that there is a notion of “definition by recursion on a well-founded second order tree” which generalizes “definition by transfinite recursion”. We then use this new notion of definition by recursion to prove an analog of Lusin’s Separation theorem for closure spaces of global sections of a second order tree.

We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity of these sets for the standard notions of finite learning, learning in the limit, behaviorally correct learning and anomalous learning in the limit. In proving the ${\rm{\Sigma }}_5^0$-completeness result for behaviorally correct learning we prove a result of independent interest; if a uniformly computably enumerable family is not learnable, then for any computable learner there is a ${\rm{\Delta }}_2^0$ enumeration witnessing failure.

In recent years, much work in descriptive set theory has been focused on the Borel complexity of naturally occurring classification problems, in particular, the study of countable Borel equivalence relations and their structure under the quasi-order of Borel reducibility. Following the approach of Louveau and Rosendal for the study of analytic equivalence relations, we study countable Borel quasi-orders.

In this paper we are concerned with universal countable Borel quasi-orders, i.e., countable Borel quasi-orders above all other countable Borel quasi-orders with regard to Borel reducibility. We first establish that there is a universal countable Borel quasi-order, and then establish that several countable Borel quasi-orders are universal. An important example is an embeddability relation on descriptive set theoretic trees.

Our main result states that embeddability of finitely generated groups is a universal countable Borel quasi-order, answering a question of Louveau and Rosendal. This immediately implies that biembeddability of finitely generated groups is a universal countable Borel equivalence relation. The same techniques are also used to show that embeddability of countable groups is a universal analytic quasi-order.

Finally, we show that, up to Borel bireducibility, there are ${2^{{\aleph _0}}}$ distinct countable Borel quasi-orders, which symmetrize to a universal countable Borel equivalence relation.

We examine the reverse-mathematical strength of several theorems in classical and effective model theory concerning first-order theories and their number of models. We prove that, among these, most are equivalent to one of the familiar systems RCA0, WKL0, or ACA0. We are led to a purely model-theoretic statement that implies WKL0 but refutes ACA0 over RCA0.