Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples.

We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. In this paper, we calculate the degree of the isomorphism problem for Abelian p-groups of bounded Ulm length. The result is a sequence of classes whose isomorphism problems are cofinal in the hyperarithmetical hierarchy. In the process, new back-and-forth relations on such groups are calculated.

This note answers a questions from [2] by showing that considered up to Borel reducibility, there are more essentially countable Borel equivalence relations than countable Borel equivalence relations. Namely:

Theorem 0.1. There is an essentially countable Borel equivalence relation E such that for no countable Borel equivalence relation F (on a standard Borel space) do we have

The proof of the result is short. It does however require an extensive rear guard campaign to extract from the techniques of [1] the following

Messy Fact 0.2. There are countable Borel equivalence relationssuch that:

(i) eachExis defined on a standard Borel probability space (Xx, μx); each Ex is μx-invariant and μx-ergodic;

(ii) forx1 ≠ x2 and A μxι -conull, we haveExι/Anot Borel reducible toEx2;

(iii) if f: Xx → Xxis a measurable reduction ofExto itself then

(iv)

is a standard Borel space on which the projection function

is Borel and the equivalence relation Ê given by

if and only ifx = x′ andzExz′ is Borel;

(V)

is Borel.

We first prove the theorem granted this messy fact. We then prove the fact.

(iv) and (v) are messy and unpleasant to state precisely, but are intended to express the idea that we have an effective parameterization of countable Borel equivalence relations by points in a standard Borel space. Examples along these lines appear already in the Adams-Kechris constructions; the new feature is (iii).

Simon Thomas has pointed out to me that in light of theorem 4.4 [5] the Gefter-Golodets examples of section 5 [5] also satisfy the conclusion of 0.2.

We construct the finitely generated free algebras and determine the free spectra of varieties of linear equivalential algebras and linear equivalential algebras of finite height corresponding, respectively, to the equivalential fragments of intermediate Gödel-Dummett logic and intermediate finite-valued logics of Gödel. Thus we compute the number of purely equivalential propositional formulas in these logics in n variables for an arbitrary n ∈ ℕ.

We consider exponentially large finite relational structures (with the universe {0, 1}n ) whose basic relations are computed by polynomial size (n O(1)) circuits. We study behaviour of such structures when pulled back by P/poly maps to a bigger or to a smaller universe. In particular, we prove that:

1. If there exists a P/poly map g: {0, 1}n → {0, 1}m , n < m, iterable for a proof system then a tautology (independent of g) expressing that a particular size n set is dominating in a size 2n tournament is hard for the proof system.

2. The search problem WPHP. decoding RSA or finding a collision in a hashing function can be reduced to finding a size m homogeneous subgraph in a size 22m graph.

Further we reduce the proof complexity of a concrete tautology (expressing a Ramsey property of a graph) in strong systems to the complexity of implicit proofs of implicit formulas in weak proof systems.

Orthogonality between two stably embedded definable sets is preserved under the addition of constants.

I prove a version of Schanuel's conjecture for Weierstrass equations in differential fields, answering a question of Zilber, and show that the linear independence condition in the statement cannot be relaxed.

Define to be the smallest cardinality of a function f: X→Y with I, X, Y, ⊆ 2ω such that there is no Borel function g ⊇ f. In this paper we prove that it is relatively consistent with ZFC to have b < where b is, as usual, smallest cardinality of an unbounded family in Ωω. This answers a question raised by Zapletal.

We also show that it is relatively consistent with ZFC that there exists X ⊆ 2ω such that the Borei order of X is bounded but there exists a relatively analytic subset of X which is not relatively coanalytic. This answers a question of Mauldin.

We solve a major open problem concerning algorithmic properties of products of ‘transitive’ modal logics by showing that products and commutators of such standard logics as K4, S4, S4.1, K4.3, GL, or Grz are undecidable and do not have the finite model property. More generally, we prove that no Kripke complete extension of the commutator [K4, K4] with product frames of arbitrary finite or infinite depth (with respect to both accessibility relations) can be decidable. In particular, if l1 and l2 are classes of transitive frames such that their depth cannot be bounded by any fixed n < ω, then the logic of the class {5ℑ1 × ℑ2 ∣ ℑ1 ∈ l1, ℑ2, ∈ l2} is undecidable. (On the contrary, the product of, say, K4 and the logic of all transitive Kripke frames of depth ≤ n, for some fixed n < ω, is decidable.) The complexity of these undecidable logics ranges from r.e. to co-r.e. and Π11-complete. As a consequence, we give the first known examples of Kripke incomplete commutators of Kripke complete logics.

This paper is devoted to the proof of the following upward categoricity theorem: Let be a tame abstract elementary class with amalgamation, arbitrarily large models, and countable Löwenheim-Skolem number. If is categorical in ℵ then is categorical in every uncountable cardinal. More generally, wc prove that if is categorical in a successor cardinal λ+ then is categorical everywhere above λ+.

We define a notion of genericity for arbitrary subgroups of groups interpretable in a simple theory, and show that a type generic for such a group is generic for the minimal hyperdefinable supergroup (the definable hull). In particular, at least one generic type of the definable hull is finitely satisfiable in the original subgroup. If the subgroup is a subfield. then the additive and the multiplicative definable hull both have bounded index in the smallest hyperdefinable superfield.

It is proved that all groups of finite U-rank that have the descending chain condition on definable subgroups are totally transcendental. A corollary is that any stable group that is definable in an o -minimal structure is totally transcendental of finite Morley rank.

Non-perfect separably closed fields are stable, and not superstable. As a result, not all types can be ranked. We develop here a new tool, a “semi-rank”, which takes values in the non-negative reals, and gives a sufficient condition for forking of types. This semi-rank is built up from a transcendence function, analogous to the one considered by Kolehin in the context of differentially closed fields. It yields some orthogonality and stratification results.