We examine the reverse mathematics and computability theory of a form of Ramsey's theorem in which the linear n-tuples of a binary tree are colored.

Each relational structure X has an associated Gaifman graph, which endows X with the properties of a graph. If x is an element of X, let Bn(x) be the ball of radius n around x. Suppose that X is infinite, connected and of bounded degree. A first-order sentence ϕ in the language of X is almost surely true (resp. a.s. false) for finite substructures of X if for every x ∈ X, the fraction of substructures of Bn(x) satisfying ϕ approaches 1 (resp. 0) as n approaches infinity. Suppose further that, for every finite substructure, X has a disjoint isomorphic substructure. Then every ϕ is a.s. true or a.s. false for finite substructures of X. This is one form of the geometric zero-one law. We formulate it also in a form that does not mention the ambient infinite structure. In addition, we investigate various questions related to the geometric zero-one law.

In partial answer to a question posed by Arnie Miller [4] and X. Caicedo [2] we obtain sufficient conditions for an ℒω1,ω theory to have an independent axiomatization. As a consequence we obtain two corollaries: The first, assuming Vaught's Conjecture, every ℒω1,ω theory in a countable language has an independent axiomatization. The second, this time outright in ZFC, every intersection of a family of Borel sets can be formed as the intersection of a family of independent Borel sets.

An o-minimal expansion of an ordered group is called semi-bounded if there is no definable bijection between a bounded and an unbounded interval in it (equivalently, it is an expansion of the group by bounded predicates and group automorphisms). It is shown that every such structure has an elementary extension N such that either N is a reduct of an ordered vector space, or there is an o-minimal structure , with the same universe but of different language from N, with (i) Every definable set in N is definable in , and (ii) has an elementary substructure in which every bounded interval admits a definable real closed field.

As a result certain questions about definably compact groups can be reduced to either ordered vector spaces or expansions of real closed fields. Using the known results in these two settings, the number of torsion points in definably compact abelian groups in expansions of ordered groups is given. Pillay's Conjecture for such groups follows.

Higman essentially showed that if A is any language then SUBSEQ(A) is regular, where SUBSEQ(A) is the language of all subsequences of strings in A. Let s1,s2,s3,… be the standard lexico-graphic enumeration of all strings over some finite alphabet. We consider the following inductive inference problem: A(s1),A(s2),A(s3),…, learn, in the limit, a DFA for SUBSEQ(A). We consider this model of learning and the variants of it that are usually studied in Inductive Inference: anomalies, mind-changes, teams, and combinations thereof.

This paper is a significant revision and expansion of an earlier conference version [10].

Khutoretskii's Theorem states that the Rogers semilattice of any family of c.e. sets has either at most one or infinitely many elements. A lemma in the inductive step of the proof shows that no Rogers semilattice can be partitioned into a principal ideal and a principal filter. We show that such a partitioning is possible for some family of d.c.e. sets. In fact, we construct a family of c.e. sets which, when viewed as a family of d.c.e. sets, has (up to equivalence) exactly two computable Friedberg numberings μ and ν, and μ reduces to any computable numbering not equivalent to ν. The question of whether the full statement of Khutoretskii's Theorem fails for families of d.c.e. sets remains open.

We develop the theory of generically stable types, independence relation based on nonforking and stable weight in the context of dependent theories.

In this paper, we investigate the extent to which techniques used in [10], [2], and [3]—developed to prove coloring theorems at successors of singular cardinals of uncountable cofinality—can be extended to cover the countable cofinality case.

We prove that Kreisel's Conjecture is true, if Peano arithmetic is axiomatised using minimality principle and axioms of identity (theory PAM). The result is independent on the choice of language of PAM. We also show that if infinitely many instances of A(x) are provable in a bounded number of steps in PAM then there exists . The results imply that PAM does not prove scheme of induction or identity schemes in a bounded number of steps.

In this paper it is shown that the global statement that the dominating number for κ is less than 2κ for all regular κ, is internally consistent, given the existence of 0#. The possible range of values for the dominating number for κ and 2κ which may be simultaneously true in an inner model is also explored.

We use a reverse Easton forcing iteration to obtain a universe with a definable well-order, while preserving the GCH and proper classes of a variety of very large cardinals. This is achieved by coding using the principle , at a proper class of cardinals κ. By choosing the cardinals at which coding occurs sufficiently sparsely, we are able to lift the embeddings witnessing the large cardinal properties without having to meet any non-trivial master conditions.

The Rainbow Ramsey Theorem is essentially an “anti-Ramsey” theorem which states that certain types of colorings must be injective on a large subset (rather than constant on a large subset). Surprisingly, this version follows easily from Ramsey's Theorem, even in the weak system RCA0 of reverse mathematics. We answer the question of the converse implication for pairs, showing that the Rainbow Ramsey Theorem for pairs is in fact strictly weaker than Ramsey's Theorem for pairs over RCA0. The separation involves techniques from the theory of randomness by showing that every 2-random bounds an ω-model of the Rainbow Ramsey Theorem for pairs. These results also provide as a corollary a new proof of Martin's theorem that the hyperimmune degrees have measure one.

We prove that every Turing degree a bounding some non-GL2 degree is recursively enumerable in and above (r.e.a.) some 1-generic degree.

We use the Low Basis Theorem of Jockusch and Soare to show that all computable algebraic fields are d-computably categorical for a particular Turing degree d with d′ = 0″, but that not all such fields are 0′-computably categorical. We also prove related results about algebraic fields with splitting algorithms, and fields of finite transcendence degree over ℚ.

Relations between some theories of semigroups (also known as theories of strings or theories of concatenation) and arithmetic are surveyed. In particular Robinson's arithmetic Q is shown to be mutually interpretable with TC, a weak theory of concatenation introduced by Grzegorczyk. Furthermore, TC is shown to be interpretable in the theory F studied by Tarski and Szmielewa, thus confirming their claim that F is essentially undecidable.

We prove that if an equicharacteristic valued field has a ℤ-group as its value group and admits quantifier elimination in the main sort of the prototypical Denef-Pas style language then it is henselian. In fact the proof of this suggests that a reasonable class of Denef-Pas style languages is natural with respect to henselianity.

We study satisfiability and infinite-state model checking in ICPDL, which extends Propositional Dynamic Logic (PDL) with intersection and converse operators on programs. The two main results of this paper are that (i) satisfiability is in 2ΕΧΡΤΙΜΕ, thus 2ΕΧΡΤΙΜΕ-complete by an existing lower bound, and (ii) infinite-state model checking of basic process algebras and pushdown systems is also 2ΕΧΡΤΙΜΕ-complete. Both upper bounds are obtained by polynomial time computable reductions to ω-regular tree satisfiability in ICPDL, a reasoning problem that we introduce specifically for this purpose. This problem is then reduced to the emptiness problem for alternating two-way automata on infinite trees. Our approach to (i) also provides a shorter and more elegant proof of Danecki's difficult result that satisfiability in IPDL is in 2ΕΧΡΤΙΜΕ. We prove the lower bound(s) for infinite-state model checking using an encoding of alternating Turing machines.

We prove that degrees that are low for Kurtz randomness cannot be diagonally non-recursive. Together with the work of Stephan and Yu [16], this proves that they coincide with the hyperimmune-free non-DNR degrees, which are also exactly the degrees that are low for weak 1-genericity.

We also consider Low(ℳ, Kurtz), the class of degrees a such that every element of ℳ is a-Kurtz random. These are characterised when ℳ is the class of Martin-Löf random, computably random, or Schnorr random reals. We show that Low(ML, Kurtz) coincides with the non-DNR degrees, while both Low(CR, Kurtz) and Low(Schnorr, Kurtz) are exactly the non-high, non-DNR degrees.

We prove that it is decidable of a finite algebra whether it has a near-unanimity term operation, which settles a ten-year-old problem. As a consequence, it is decidable of a finite algebra in a congruence distributive variety whether it admits a natural duality.

We solve a longstanding question of Rosenstein, and make progress toward solving a long-standing open problem in the area of computable linear orderings by showing that every computable η-like linear ordering without an infinite strongly η-like interval has a computable copy without nontrivial computable self-embedding.

The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.