The isomorphism relation on countable torsion free abelian groups

Greg Hjorth

September 13, 2002

Abstract

The isomorphism relation on countable torsion free abelian groups is non-Borel.

1 Introduction

This notes makes a comment on the isomorphism relation of countable torsion free abelian groups of infinite rank. We show that any Borel isomorphism relation on a class of countable structures may be embedded into the isomorphism relation of countable torsion free abelian groups.

In [3] a stronger result was announced, to the effect that we may actually embed the isomorphism relation of an arbitrary class of countable structures. A proof was there promised to be given in [5].

That proof, alas, was mistaken. This note instead gives a weaker a result, which as it turns out is now irrelevant to the main direction of [5].

Before going further into the details we need to recall a basic concept for this area:

Definition Let E and F be Borel equivalence relations on Polish spaces X and Y. We write

E ≤_{B} F

if there is a Borel function

θ : X → Y

such that for all x_{1}, x_{2} ∈ X

x_{1}Ex_{2} ⇔ θ(x_{1})F θ(x_{2}).

For L a countable language we can form, as described in [7], the Polish space X_{L} of L structures with underlying set ℕ. For L consisting of a single binary operation, +, the torsion free abelian groups form a closed invariant subset TFA⊂ X_{L}.

Our main result is that

Theorem 1.1 For L′ a countable language and C ⊂ X_{L′} a Borel set such that the isomorphism relation on C, ≅|_{C}, is Borel, we always have

≅|_{C} ≤_{B} ≅|_{TFA}.

In particular this implies that ≅ |_{TFA} is non-Borel, answering a question raised in [2]. However we leave open the question which the authors of [2] correctly identify as most fundamental:

Question Let L′ be a countable language. Do we necessarily have

≅|_{L′} ≤_{B} ≅|_{TFA}?

In this present paper I will largely skip over giving a detailed introduction or providing extensive motivation. I feel that such an introduction has already been given in [7] and [6]. Between them these papers should also provide the technical background and an explanation of notation not adequately defined below.

G. Hjorth 2

2 Group eplags

This section is devoted to a painful and detailed development of a new class of infinite rank torsion free abelian groups. The central technical lemma appears at 2.5, giving an analysis of when a given element from one of these group eplags is infinitely divisible by a given prime. This technical lemma enables the section after to embed countable iterations of the power set of ℕ into torsion free abelian groups considered up to isomorphism.

Although 2.5 and the coding techniques of §3 defy easy summary, it might be helpful to make a couple of brief remarks about the philosophy of the proof. This can be most easily described considering the case of just embedding P_{ℵ_{0}}(P(ℕ)) into the isomorphism relation on torsion free abelian groups.

A way in which we might effect such an encoding is to first enumerate infinitely many distinct primes, (p_{n})_{n∈ℕ}. Then given {a_{n} : n ∈ ℕ} ⊂ P(ℕ) we can describe a subgroup of ℚ^{ℕ}, where the element δ_{n} (the function taking value 1 at n and zero elsewhere) is infinitely divisible by a prime p if and only if p = p_{i} for some i with i ∈ a_{n}. With suitable care this can be done so that the isomorphism type of the corresponding group only depends on the set {a_{n} : n ∈ ℕ} and so that for each non-zero g in the group, the primes infinitely dividing g will either be empty or equal to {p_{i} : i ∈ a_{n}}, for some n ∈ ℕ.

The case of P_{ℵ_{0}}(P(ℕ)) is misleadingly simple, because at this level every object being coded is a subset of some predetermined countable set. In the general case we need to be able to build up sets of sets, and sets of sets of sets, and so on, without any previously described limitations. The complications required for this further coding are reflected in 2.5 and 3.1 below.

Definition A graph is a pair (V, E) where V is a set and E is a subset of the unordered pairs

{{v, w} : v, w ∈ V, v ≠ w}

of elements in V.

Notation ℙ denotes the set of primes

Definition A prime labeled graph is a triple (V, E, f) where (V, E) is a graph and

f : V ∪ E → ℙ.

It is said to be excellent if (i) f[V] ∩ f[E] = ∅; that is to say, vertices and edges are always assigned distinct primes; (ii) for any p ∈ ℙ

(V, f^{−1}[{p}])

contains no cycles; in other words, if we restrict our attention to edges labeled by a single prime then the resulting graph is a union of disjoint trees.

I will use the acronym eplag for excellent prime labeled graph.

Definition Given an eplag (V, E, f) we we define the corresponding group eplag, denoted

G(V, E, f).

We first consider the group consisting of all formal sums

∑_{v∈V_{0}} q_{v} · v,

where V_{0} is a finite subset of V and (q_{v})_{v∈V_{0}} is a corresponding array of non-zero rationals; we add elements in this group in the obvious way, and thus it becomes a torsion free abelian group. We then let G(V, E, f) be the abelian group consisting of all elements that may be represented in the form

g = ∑_{v∈V_{0}} \frac{k_{v} · v}{f(v)^{ℓ_{v}}} + ∑_{\{v,w\}∈E_{0}} \frac{n_{\{v,w\}} · (v + w)}{f(\{v, w\})^{m_{\{v,w\}}}} ,

where V_{0} is a finite subset of V, E_{0} is a finite subset of E, where each k_{v}, n_{{v,w}} ∈ ℤ, ℓ_{v}, m_{{v,w}} ∈ ℕ.

In other words, G(V, E, f) can be thought of as isomorphic to a subgroup of the direct sum

⨁_{V} ℚ,

in the product group structure, where we insist that each χ_{{v}} (the characteristic function of {v}, taking χ_{{v}}(w) = 1 when w = v, and assuming value 0 otherwise) is divisible by all powers of f(v) while each χ_{{v}}+χ_{{w}} is divisible by all powers of f({v, w}) for {v, w} ∈ E. In particular every element of G(V, E, f) can be written in the form

∑_{v∈V_{1}} q_{v} · v

for some finite V_{1} ⊂ V and associated collection {q_{v} : v ∈ V_{1}} of rationals.

Definition Let G(V, E, f) be an eplag and

ρ : V → {−1, 0, 1}

a function. We define a resulting homomorphism

φ_{ρ} : G(V, E, f) → ℚ

by

φ_{ρ}( ∑_{v∈V_{0}} q_{v} · v) = ∑_{v∈V_{0}} q_{v}ρ(v).

Definition Let g(V, E, f) be a group eplag and let p be a prime. A homomorphism

ψ : G(V, E, f) → ℚ

is p-mindful if there is some

ρ : V → {−1, 0, 1}

with

ρ(w_{0}) = −ρ(w_{1})

all {w_{0}, w_{1}} ∈ E ∩ f^{−1}[{p}] and

ψ = φ_{ρ}

as above.

Lemma 2.1 If

C ⊂ V

is a connected component of (V, f^{−1}[{p}]) containing some given vertex v and

φ_{0}, φ_{1} : G(V, E, f) → ℚ

are p-mindful homomorphisms with φ_{0}(v), φ_{1}(v) both non-zero, then for any g ∈ G(V, E, f) of the form

g = ∑_{v∈C_{0}} q_{v} · v

with C_{0} a finite subset of C, we have

φ_{0}(g) = 0

if and only if

φ_{1}(g) = 0.

Proof The point is that there are only two possible 2-colorings of (C, f^{−1}[{p}]) by {−1, 1}, and hence only two possible non-trivial p-mindful homomorphisms for the subgroup of G(V, E, f) generated by {w : w ∈ C}. Each of these homomorphisms is the mirror image of the other, in the sense that φ_{0}(g) = −φ_{1}(g) all g in their common domain. □

Lemma 2.2 Suppose C_{1}, C_{2}, ...C_{k} are distinct connected components of (V, f^{−1}[{p}] ∩ E) and for each i ≤ k we have

g_{i} = ∑_{v∈V_{i}} r_{v} · v

for some V_{i} ⊂ C_{i}. Suppose

g = g_{1} + g_{2} + ...g_{k}.

Then the following statements are equivalent:

(I) g takes the value

φ(g) = 0

for each p-mindful φ.

(II) Each g_{i} takes the value

φ(g_{i}) = 0

for each p-mindful φ.

Proof Since if F enumerates the components of (V, f^{−1}[{p}] ∩ E), then any p-mindful φ may be written as a sum

φ : g ↦ ∑_{C∈F} φ_{C}(g)

where each φ_{C} is p-mindful and assumes the value 0 outside of C. □

Lemma 2.3 Let G(V, E, f) be a group eplag, p ∈ ℙ, v ∈ V. Then there is a function

ρ : V → {−1, 0, 1}

such that (i) ρ(w) ≠ 0 if and only if there are

v_{0}, v_{1}, ..., v_{k} ∈ V,

each

{v_{i}, v_{i+1}} ∈ f^{−1}[{p}] ∩ E,

and

v_{0} = v, v_{k} = w;

in other words, ρ takes non-zero values exactly on the component of (V, f^{−1}[{p}] ∩ E) containing v; (ii) for {w_{0}, w_{1}} ∈ f^{−1}[{p}] ∩ E we have

ρ(w_{0}) = −ρ(w_{1});

in other words, ρ provides a two coloring of the component on which it is non-zero.

Proof This is essentially a restatement of the well known fact that every tree admits a two coloring. □

Lemma 2.4 Let (V, E, f) be an eplag. Suppose p ∈ ℙ and (T, f^{−1}[{p}] ∩ {{v, w} : v, w ∈ T }) is a finite subtree of (V, f^{−1}[{p}] ∩ E) and

g ∈ G(V, E, f)

has the form

g = ∑_{v∈T} r_{v} · v

for rationals {r_{v} : v ∈ T }. Suppose φ(g) = 0 for every p-mindful homomorphism

φ : G(V, E, f) → ℚ.

Then g is divisible by every power of p.

Proof We prove the lemma by induction on the cardinality |T | of T. If this is 1, then g would have to be the zero element of the group, since for g = q · v we can always define a p-mindful homomorphism φ which assumes a value φ(v) = 1; and certainly zero is divisible by all powers of p.

So now suppose

g = ∑_{v∈T} r_{v} · v,

|T | = n + 1 ≥ 2, and that the lemma has been proved for any trees T′ with |T′| ≤ n. Then we may choose a node v_{0} ∈ T that is terminal; let v_{1} be the unique vertex in T with {v_{0}, v_{1}} ∈ f^{−1}[{p}]. We can let

h = r_{v_{0}} · v_{0} + r_{v_{0}} · v_{1};

it follows from the definition of G(V, E, f) that h is divisible by all powers of p; and it follows from the definition of mindfulness that φ(h) = 0 for every p-mindful homomorphism φ. Thus by assumption on g

φ(g − h) = 0

for every p-mindful homomorphism φ : G(V, E, f) → ℚ, and so by inductive assumption g − h is divisible by every power of p. But then g must also be divisible by every power of p. □

In the proof of the following proposition we use without explicit mention this consequence of unique factorization: If p, p_{0}, p_{1}, ..., p_{k} are non-zero primes, n, n_{0}, ..., n_{k}, are non-zero integers, n not divisible by p, and m, m_{0}, ..., m_{k} are positive integers and

\frac{n}{p^{m}} = ∑_{i≤k} \frac{n_{i}}{(p_{i})^{m_{i}}} ,

then for some i ≤ k we have

p_{i} = p.

Proposition 2.5 Let G(V, E, f) be a group eplag, p ∈ ℙ, V_{0} ⊂ V finite, g ∈ G(V, E, f) of the form

g = ∑_{v∈V_{0}} q_{v} · v,

where each q_{v} ≠ 0. Then g is divisible by all powers of p in G(V, E, f) if and only if either: (i) V_{0} ⊂ V ∩ f^{−1}[{p}]; or, (ii) for each p-mindful homomorphism

φ : G(V, E, f) → ℚ

we have

φ(g) = 0.

Proof For notational simplicity let us assume each q_{v} ∈ ℤ. We can make this simplifying assumption since the euclidean algorithm shows that g is divisible by every power of p if and only if every integer multiple of g is divisible by every power of p. (⇐): First suppose (i) holds. Then it is immediate from the definitions that for each v ∈ V_{0} and n ∈ ℕ we have

p^{−n} · v ∈ G(V, E, f),

and hence g is indeed divisible by every power of p.

So instead let us suppose (ii) holds. Note that we can find finitely many components of W_{1}, W_{2}, ..., W_{k} of (V, E ∩ f^{−1}[{p}]) such that

g = g_{1} + g_{2} + ... + g_{k}

where each g_{i} is a rational linear combination of {v : v ∈ W_{i}}. Then g will be divisible by all powers of p if each g_{i} is divisible by each power of p. Thus by 2.2 we may as well assume that k = 1; that is to say, g is contained in a single component of (V, E ∩ f^{−1}[{p}]).

With this in hand, we can write

g = ∑_{v∈T} ℓ_{v} · v

where T ⊂ V is finite and

(T, f^{−1}[{p}] ∩ {{v, w} : v, w ∈ T })

forms a tree. And then we are done by appealing to 2.4. (⇒): Assume for a contradiction that (i) and (ii) both fail. Claim(1): There is h ∈ G such that

φ(h) = 0

for every p-mindful homomorphism φ : G(V, E, f) → ℚ and is such that if

h + g = ∑_{v∈W} r_{v} · v

is a representation of g + h with each r_{v} ≠ 0 for v ∈ W, then we have that for each connected component C of (V, f^{−1}[{p}]) there is at most one v ∈ W ∩ C. Proof of claim: For each connected component C of (V, f^{−1}[{p}]∩E) that meets V_{0} choose some single v_{C} ∈ C and a 2-coloring

ρ_{C} : C → {−1, 1}

of the tree

(C, f^{−1}[{p}] ∩ {{w_{1}, w_{2}} ∈ E : w_{1}, w_{2} ∈ C})

with ρ_{C}(v_{C}) = 1. We then let

h_{C} = ∑_{v∈C∩V_{0}} −q_{v} · v + ∑_{v∈C∩V_{0}} q_{v}ρ_{C}(v) · v_{C}.

By 2.1 we have that for any p-mindful homomorphism φ

φ(h_{C}) = 0.

Thus if we let F enumerate the connected components of (V, f^{−1}[{p}] ∩ E) meeting V_{0}, then

h = ∑_{C∈F} h_{C}

is as required.

(Claim□)

Thus by the already proved direction ⇐ of the proposition we have that h is divisible by every power of p. And hence also g + h. Moreover g + h fails (ii) since g fails (ii). In particular, g + h ≠ 0.

Hence, after possibly replacing g by g + h we may make the simplifying assumption that for each connected component C of (V, f^{−1}[{p}] ∩ E) there is at most a single vertex w_{C} with

w_{C} ∈ V_{0} ∩ C

in the representation of g. Thus for some finite collection H of connected components of (V, f^{−1}[{p}]) and some finite collection (a_{C})_{C∈H} of integers we have

g = ∑_{C∈H} a_{C}w_{C}.

Choose some sufficiently large n that no a_{C} is divisible by p^{n} – and thus the coefficient of a_{C} appearing in

\frac{g}{p^{n}}

must have a power of p in its denominator. g is divisible by p^{n} in G(V, E, f), and thus we may write

\frac{g}{p^{n}} = ∑_{v∈V_{1}} \frac{k_{v} · v}{f(v)^{ℓ_{v}}} + ∑_{\{v,w\}∈E_{1}} \frac{n_{\{v,w\}}(v + w)}{f(\{v, w\})^{m_{\{v,w\}}}} ,

for finite V_{1} ⊂ V, E_{1} ⊂ E, each m_{{v,w}} > 0, each n_{{v,w}} indivisible by f({v, w}). For each C ∈ H let T_{C} ⊂ C be the smallest possible subtree of (V, f^{−1}[{p}]) such that if {v_{0}, v_{1}} ∈ E_{1} with v_{0}, v_{1} ∈ C then

v_{0}, v_{1} ∈ T_{C}.

Claim(2): f^{−1}[{p}] ∩ V = ∅. Proof of claim: Inspecting the definition of G(V, E, f) we see that every h in the group may be written in the form

h = ∑_{v∈W_{1}} \frac{b_{v} · v}{(f(v)f(\{w_{0,v}, v\})f(\{w_{1,v}, v\})...f(\{w_{k(v),v}, v\}))^{c_{v}}}

where each {w_{i,v}, v} ∈ E, each b_{v} ∈ ℤ, and each c_{v} ∈ ℕ. In particular then the assumption of g’s unlimited divisibility by p along with our hypothesis that some v ∈ V_{0} has f(v) ≠ p implies that there is some w with

{w, v} ∈ E

and

f({w, v}) = p.

Then by the definition of excellent prime labeled graph we must have

f^{−1}[{p}] ∩ V = ∅.
(Claim□)

Claim(3): For no C ∈ H do we have

T_{C} = ∅;

that is to say, for every C ∈ H there is some v_{0}, v_{1} ∈ C with

{v_{0}, v_{1}} ∈ E_{1}.

Proof of claim: Since for each C ∈ H we may write

\frac{g}{p^{n}} = \frac{a_{C} · w_{C}}{p^{n}} + ∑_{v∈V_{0},v≠w_{C}} \frac{q_{v} · v}{p^{n}}

and

\frac{g}{p^{n}} = ∑_{v∈V_{1}} \frac{k_{v} · v}{f(v)^{ℓ_{v}}} + ∑_{\{v,w\}∈E_{1}} \frac{n_{\{v,w\}} · (v + w)}{f(\{v, w\})^{m_{\{v,w\}}}} ,

and since each a_{C} is indivisible by p^{n}, we see that for any C ∈ H there is some v with

{v, w_{C}} ∈ E_{1},
f({v, w_{C}}) = p.
(Claim□)

So let us choose C_{0} ∈ H and v_{0} ∈ T_{C_{0}} with v_{0} ≠ w_{C_{0}} but v_{0} terminal in T_{C_{0}} – that is to say, there is exactly one other v_{1} ∈ T_{C_{0}} with {v_{0}, v_{1}} ∈ E. This is possible since T_{C_{0}} is a finite tree and since, by the above claim, it has at least two elements. Referring back to the representation

\frac{g}{p^{n}} = ∑_{C∈H} \frac{a_{C} · w_{C}}{p^{n}} ,

G. Hjorth 8

and using v_{0} ≠ w_{C} all C ∈ H we see that

\frac{k_{v_{0}} · v_{0}}{f(v_{0})^{ℓ_{v_{0}}}} + ∑_{\{v_{0},w\}∈E_{1}} \frac{n_{\{v_{0},w\}}(v_{0} + w)}{f(\{v_{0}, w\})^{m_{\{v_{0},w\}}}} ,

can be expressed as a linear combination of

{w ∈ V : w ≠ v_{0}},

and thus

\frac{k_{v_{0}}}{f(v_{0})^{ℓ_{v_{0}}}} + ∑_{\{v_{0},w\}∈E_{1}} \frac{n_{\{v_{0},w\}}}{f(\{v_{0}, w\})^{m_{\{v_{0},w\}}}} = 0.

But now the assumption on v_{0} gives us a single w_{0} with {v_{0}, w_{0}} ∈ E_{1}, f({v_{0}, w_{0}}) = p.

Thus we obtain primes p_{1}, p_{2}, ..., p_{N} distinct from p with

\frac{k_{v_{0}}}{f(v_{0})^{ℓ_{v_{0}}}} + \frac{n_{\{w_{0},v_{0}\}}}{p^{m_{\{w_{0},v_{0}\}}}} + ∑_{i≤N} \frac{n_{i}}{p_{i}^{m_{i}}} = 0.

Since f(v_{0}) ≠ p we have at last reached a contradiction.

□

3 Coding hereditarily countable sets

Definition Following [7], we define P^{α}(ℕ) by induction on α < ω_{1}. We begin with

P^{0}(ℕ) = ℕ

and then inductively define

P^{α}(ℕ)

for α > 0 to be

⋃_{β<α} P^{β}(ℕ)

along with the set of all countable subsets of

⋃_{β<α} P^{β}(ℕ).

For

A ∈ ⋃_{α<ω_{1}} P^{α}(ℕ)

we let Rk(A) be the least α such that

A ∈ P^{α}(ℕ).

We also define TC(A) in the following way. If A = m ∈ P^{0}(ℕ) we define TC(A) to be the set {n : n < m}. We then continue inductively, so that when A ∈ P^{α}(ℕ) some α > 0 then

TC(A) = A ∪ ( ⋃_{B∈A} TC(B)).

Notation For the rest of this section fix α a countable ordinal and a collection of distinct primes

{p_{β} : β ≤ α, β ≠ 0} ∪ {q_{n} : n ∈ ℕ} ∪ {q̂_{γ,β} : γ < β ≤ α} ∪ {p̄_{γ,β} : γ < β ≤ α}.

The goal of this section is to show that given this ordinal α and this collection of primes we can canonically associate to each A ∈ P^{α}(ℕ) a corresponding torsion free abelian group

H_{A}

such that

A_{0} = A_{1}

if and only if

H_{A_{0}} ≅ H_{A_{1}}.

In this section we simply concentrate on describing the construction. It is only in the two following sections that any significance can be attached to the endeavor – the next section observes this particular construction to be suitably “Borel”, and the section after notes consequences for the isomorphism relation on torsion free abelian groups. This present section should really be thought of as one long definition.

We first build a group G_{A}, for each A ∈ P^{α+1}(ℕ), and verify that

TC(A_{1}) ≠ TC(A_{2})

implies

G_{A_{1}} ≅ G̸_{A_{2}}.

We then can define for A ∈ P^{α}(ℕ)

H_{A} = G_{{A}∪TC(A)}

and check that indeed

A_{1} = A_{2} ⇔ H_{A_{1}} ≅ H_{A_{2}}.

Definition For A ∈ P^{α+1}(ℕ) we let V_{A} consist of all

⟨A_{1}, A_{2}, ..., A_{n}⟩

where

(i) n ∈ ℕ;
(ii) each A_{i} ∈ TC(A);
(iii) Rk(x_{i+1}) < Rk(x_{i}) each i < n.

We let E_{A} consist of all pairs

{⟨A_{1}, A_{2}, ..., A_{n}⟩, ⟨A_{1}, A_{2}, ..., A_{n}, A_{n+1}⟩},

where ⟨A_{1}, ..., A_{n}, A_{n+1}⟩ ∈ V_{A}. We define a prime labeling

f_{A} : V_{A} ∪ E_{A} → ℙ

as follows:-

f(⟨A_{1}, ..., A_{n}⟩) = q_{m}

if Rk(A_{n}) = 0 and A_{n} is the natural number m;

f(⟨A_{1}, ..., A_{n}⟩) = p_{β}

if Rk(A_{n}) = β > 0;

f({⟨A_{1}, A_{2}, ..., A_{n}⟩, ⟨A_{1}, A_{2}, ..., A_{n}, A_{n+1}⟩}) = q̂_{γ,β}

if Rk(A_{n}) = β, Rk(A_{n+1}) = γ, and A_{n+1} ∈ A_{n};

f({⟨A_{1}, A_{2}, ..., A_{n}⟩, ⟨A_{1}, A_{2}, ..., A_{n}, A_{n+1}⟩}) = p̄_{γ,β}

if Rk(A_{n}) = β, Rk(A_{n+1}) = γ, and A_{n+1} ∉ A_{n}.

Thus (V_{A}, E_{A}, f_{A}) is an eplag for any A ∈ P^{α+1}(ℕ); and from this eplag we can pass to the corresponding group.

Definition For any A ∈ P^{α+1}(ℕ) we let

G_{A} = G(V_{A}, E_{A}, f_{A}),

as defined in the last section.

Definition For any A ∈ P^{α+1}(ℕ) and β < α we define the notions of β-good and a corresponding β^{th} evaluation function π_{β} by a simultaneous induction.

We say that g ∈ G_{A} is 0-good if for some m ∈ ℕ g is divisible in G_{A} by all powers of q_{m}; we then let

π_{0}(g) = m;

note that by construction there is at most one such m, and hence π_{0}(g) is well defined for g 0-good. For β > 0 we say that g is β-good if it is divisible by all powers of p_{β} and for all γ < β and all γ-good h we have either

(a) there is a γ-good h′ with

π_{γ}(h) = π_{γ}(h′)

and g + h′ divisible by all powers of q̂_{γ,β}, or

(b) there is a γ-good h′ with

π_{γ}(h) = π_{γ}(h′)

and g + h′ divisible by all powers of p̄_{γ,β}. We then let π_{β}(g) be the set of all π_{γ}(h) such that γ < β, h is γ-good, and g + h is divisible by all

powers of q̂_{γ,β}.

Literally of course all these definitions should be made with explicit reference to A. We should define β-good in G_{A} and we should write something like π_{G_{A},γ} to show the dependence of the evaluation map on the group G_{A}.

In practice the intention will be clear.

Lemma 3.1 (a) Suppose

g = ∑_{i≤k} r_{i} · v_{i} ∈ G_{A}

is β-good, where each r_{i} ∈ ℚ, r_{i} ≠ 0, v_{i} ≠ v_{j} for i ≠ j, each

v_{i} = ⟨A_{1}^{i}, A_{2}^{i}, ..., A_{ℓ(i)}^{i}⟩.

Then for all i, j ≤ k

A_{ℓ(i)}^{i} = A_{ℓ(j)}^{j},

and

Rk(A_{ℓ(i)}^{i}) = β,

and for A^{∗} the common value of the A_{ℓ(i)}^{i} we have

π_{β}(g) = A^{∗}.

(b) If ⟨A_{1}, A_{2}, ..., A_{ℓ}⟩ ∈ V_{A} with Rk(A_{ℓ}) = β, then ⟨A_{1}, A_{2}, ..., A_{ℓ}⟩ is β-good and

π_{β}(⟨A_{1}, ..., A_{ℓ}⟩) = A_{ℓ}.

Proof We prove these by simultaneous induction. The base case β = 0 follows quickly from the definitions and 2.5. So let us assume instead that β > 0 and that the lemma is established for all γ < β.

First suppose that

g = ∑_{i≤k} r_{i} · v_{i} ∈ G_{A}

is β-good, each r_{i} a non-zero rational, each

v_{i} = ⟨A_{1}^{i}, ..., A_{ℓ(i)}^{i}⟩,

with v_{i} ≠ v_{j} for i ≠ j, and let us assume for a contradiction that

Â ∈ A_{ℓ(0)}^{0} \ A_{ℓ(1)}^{1}.

It follows from the definition of goodness that each

⟨A_{0}^{i}, ..., A_{ℓ(i)}^{i}⟩

is divisible by all powers of p_{β}, and hence, by 2.5, at each i we have Rk(A_{ℓ(i)}^{i}) = β.

Thus Â must have Rk(Â) = γ, some γ < β. And then by the inductive assumption

⟨Â⟩

is γ-good with

π_{γ}(⟨Â⟩) = Â.

Then by the definition of β-goodness of g there is some γ-good h with

π_{γ}(h) = Â

and g +h either divisible by every power of q̂_{γ,β} or divisible by every power of p̄_{γ,β}. Assume for simplicity that it is divisible by every power of q̂_{γ,β}; the other case is similar. We can write

h = ∑_{i≤k′} s_{i} · w_{i},

each w_{i} ∈ V_{A}, s_{i} a non-zero rational, w_{i} ≠ w_{j} for i ≠ j. Then by inductive assumption applied to the γ-goodness of h we have each w_{i} of the form

w_{i} = ⟨B_{1}^{i}, B_{2}^{i}, ..., B_{ℓ′(i)}^{i}, Â⟩.

At this point we can define

ρ : V_{A} → {−1, 0, 1}

by

ρ(⟨A_{0}^{1}, ..., A_{ℓ(1)}^{1}⟩) = 1,

and for any B ∈ A_{ℓ(1)}^{1}

ρ(⟨A_{0}^{1}, ..., A_{ℓ(1)}^{1}, B⟩) = −1,

but

ρ(v) = 0

for all other v ∈ V_{A}. Then φ_{ρ} defined by

∑ q_{v} · v ↦ ∑ q_{v}ρ(v)

provides a q̂_{γ,β}-mindful homomorphism which assumes the value

φ_{ρ}(g + h) = r_{1} ≠ 0,

contradicting proposition 2.5’s criteria for infinite q̂_{γ,β} divisibility.

To complete the inductive step we also need to note that (b) holds for any ⟨A_{1}, .., A_{ℓ}⟩ ∈ V_{A} with Rk(A_{ℓ}) = β. This follows routinely from the definition of β-good and the inductive assumption.

□

Corollary 3.2 TC(A_{1}) ≠TC(A_{2}) implies G_{A_{1}} ≅ G̸_{A_{2}}.

Proof Since

{π_{β}(g) : g ∈ G_{A_{1}}, g is β − good, β ≤ α} = TC(A_{1}),
{π_{β}(g) : g ∈ G_{A_{2}}, g is β − good, β ≤ α} = TC(A_{2}),

and for any group G the set

{π_{β}(g) : g ∈ G, g is β − good, β ≤ α}

is an invariant of the isomorphism type of G.

□

Now for any A ∈ P^{α}(ℕ) we can define

H_{A} = G_{{A}∪TC(A)}

to obtain an assignment

P^{α}(ℕ) ↪ TFA/ ≅
A ↦ H_{A}

which injects P^{α}(ℕ) into the countable torsion free abelian groups considered up to isomorphism.

But of course the simple existence of such an injection amounts to nothing more than |P^{α}(ℕ)| ≤ 2^{ℵ_{0}}. The important point is that this injection is, in the sense made precise shortly, reasonably definable.

4 Coding

We recall a method of coding elements of P^{α}(ℕ) by equivalence classes in a Polish space.

Definition Following [7] we let L(α) be the language generated by unary relation (R_{β})_{β≤α}, binary relations ϵ, E, F, and constant symbols v_{0}, (r_{n})_{n∈ℕ}. We let X_{L(α)} be the Polish space of L(α) structures equipped with the usual topology generated by quantifier free formulas. We then let P^{α} be the subspace consisting of structures

M = ⟨ℕ; r_{0}, r_{1}, ..., v_{0}, ϵ, E, F, R_{0}, R_{1}, ..., R_{β}, ...R_{α}⟩,

where:-

(i) ℕ is partitioned by the relations (R_{β})_{β≤α}; the constant terms (r_{n})_{n∈ℕ} enumerate R_{0} without repetitions; R_{α} = {v_{0}};

(ii) E is an irreflexive symmetric relation on ℕ \ R_{0};

(iii) E provides a tree structure on ℕ \ R_{0} with root v_{0}; this tree structure has the property that if we define x <^{∗} y if there is one-to-one f : k + 2 → ℕ \ R_{0} with f(0) = v_{0}, f(k) = y, f(k + 1) = x, then the partial order <^{∗} is wellfounded in the sense of having no infinite descending chain, and R_{γ}(x) holds exactly when x has rank γ in this tree; in particular, v_{0} has rank α;

(iv) F ⊂ R_{0} × R_{1}.

With this all in place we can assign an evaluation

||x||

to each x ∈ ℕ, with

||x|| = n

if x ∈ R_{0} and x = r_{n}, while

||x|| = {n ∈ ℕ : F (r_{n}, x)}

for x ∈ R_{1} (and hence x terminal in the tree structure on ℕ \ R_{0}); and

||x|| = {||y|| : the shortest path from v_{0} to y passes through x}.

(v) We require that ϵ satisfy

xϵy ⇔ ||x|| ∈ ||y||.

With all this in place we can finally define

||M|| = ||v_{0}||.

Some remarks.

First of all this definition suffers from the same formal defect as some earlier definitions. We should literally be writing r_{0}^{M}, r_{1}^{M}, ..., E^{M}, ... and so on to distinguish the relation symbols from the relations which arise in their interpretation in M. And again we should write ||x||^{M} to indicate the dependence of the evaluation on the structure M.

Hopefully the reader will forgive this ellipsis as well as all the earlier defects.

The second remark is to give some motivation. The idea is that we want to represent elements of P^{α}(ℕ) by countable trees. We use the E relation to describe this tree structure. The nodes of the trees correspond to the various sets appearing in the transitive closure of some A ∈ P^{α}(ℕ) and some representative of B_{1} appears below a representative of B_{2} if and only if B_{1} ∈ B_{2}; we deliberately allow that a given B ∈TC(A) may reappear in many different branches of the tree. We give a special status to the natural numbers; they comprise R_{0} and are individually named by the r_{n}’s. The higher R_{γ}’s layer M into sediments based on the rank of the represented sets.

The ϵ relation comes along for free, simply recapitulating the relation ||y|| ∈ ||x||. I leave it only because it appeared in [7].

Following 1.2-1.5 of [7] we have that P^{α} is a Borel subset of X_{L(α)}, and hence a standard Borel set in its own right, and that

{||M|| : M ∈ P^{α}} = P^{α}(ℕ),

and that the set of

(x, y, M) ∈ ℕ × ℕ × P^{α}

such that

||x|| = ||y||

(calculated from the point of view of M) is Borel as a subset of ℕ × ℕ × X_{L(α)}. If we let ≅_{α} be the isomorphism relation on elements of P^{α} then we have for all M, N ∈ P^{α} that

M ≅ N ⇔ ||M|| = ||N ||.

Definition For each M ∈ P^{α} let S_{0}(M) be the set of x ∈ ℕ such that for all smaller natural numbers y ∈ ℕ we have ||x|| ≠ ||y||.

Thus (||x||)_{x∈S_{0}(M)} enumerates without repetitions the set {||M||}∪TC(||M||). From the above remarks we have that

{(x, M) ∈ ℕ × P^{α} : x ∈ S_{0}(M)}

is Borel as a subset of ℕ × X_{L(α)}.

Definition Let

π : ℕ^{<ℕ} ↪ ℕ

be the usual Gödel pairing function, providing a bijection between ℕ^{<ℕ} and ℕ. Then for M ∈ P^{α} we let

S_{1}(M) = {π(x_{1}, x_{2}, ..., x_{n}) : each x_{i} ∈ S_{0}(M), and for i < n we have Rk(||x_{i}||) > Rk(||x_{i+1}||)}.

Again the set of

{(a, M) ∈ ℕ × P^{α} : a ∈ S_{1}(M)}

is Borel as are

{(π(x_{1}, ..., x_{n}), π(x_{1}, ..., x_{n}, x_{n+1}), M) ∈ N × ℕ × ℙ^{α} :
π(x_{1}, ..., x_{n}), π(x_{1}, ..., x_{n}, x_{n+1}) ∈ M, ||x_{n+1}|| ∈ ||x_{n}||}

and

{(π(x_{1}, ..., x_{n}), π(x_{1}, ..., x_{n}, x_{n+1}), M) ∈ ℕ × ℕ × ℙ^{α} :
π(x_{1}, ..., x_{n}), π(x_{1}, ..., x_{n}, x_{n+1}) ∈ M, ||x_{n+1}|| ∉ ||x_{n}||}.

And clearly from the definition of P^{α} we have that for each β ≤ α that the set of

{(π(x_{1}, ..., x_{n}), M) ∈ ℕ × P^{α} : π(x_{1}, ..., x_{n}) ∈ S_{1}(M), Rk(||x_{n}||) = β}

is Borel for any β ≤ α.

And thus all the sets of the form

{(p, a, M) : a ∈ S_{1}(M), a = π(x_{1}, ..., x_{n}) some n, x_{1}, ..., x_{n},
with Rk(||x_{n}||) = β, some p_{β} = p},

{(p, a, M) : a ∈ S_{1}(M), a = π(x_{1}, ..., x_{n}) some n, x_{1}, ..., x_{n},
with Rk(||x_{n}||) = 0, ||x|| = m, q_{m} = p},

{(p, a, b, M) : a, b ∈ S_{1}(M), a = π(x_{1}, ..., x_{n}), b = π(x_{1}, ..., x_{n}, x_{n+1})
some n, x_{1}, ..., x_{n}, x_{n+1}, with Rk(||x_{n}||) = β, with Rk(||x_{n+1}||) = γ,
and with ||x_{n+1}|| ∈ ||x_{n}||, q̂_{γ,β} = p},

and

{(p, a, b, M) : a, b ∈ S_{1}(M), a = π(x_{1}, ..., x_{n}), b = π(x_{1}, ..., x_{n}, x_{n+1})
some n, x_{1}, ..., x_{n}, x_{n+1}, with Rk(||x_{n}||) = β, with Rk(||x_{n+1}||) = γ,
and with ||x_{n+1}|| ∉ ||x_{n}||, p̄_{γ,β} = p},

are Borel.

Thus it follows that the set M of all sequences

(M, (r_{1}, a_{1}), (r_{2}, a_{2}), ..., (r_{ℓ}, a_{ℓ})) ∈ P^{α} × (ℚ × ℕ)^{<ℕ}

such that (i) (a_{1}, a_{2}, ..., a_{ℓ}) is a strictly increasing sequence of integers;

(ii) each a_{i} = π(x_{1}^{i}, ..., x_{N(i)}^{i}) some N(i), x_{1}^{i}, ..., x_{N(i)}^{i} ∈ ℕ,
(iii) ∑_{i≤ℓ} r_{i} · ⟨||x_{1}^{i}||, ||x_{2}^{i}||, ..., ||x_{N(i)}^{i}||⟩ ∈ G_{{||M||}∪TC(||M||)}

is Borel. Moreover we obtain then that the induced group structure on the fibers gives rise to a Borel subset of M × M × M, in the sense that the set of all

(M, (a_{1}, r_{1}), ..., (a_{ℓ}, r_{ℓ}), (b_{1}, s_{1}), ..., (b_{k}, s_{k}), (c_{1}, t_{1}), ..., (c_{m}, t_{m}))

such that (i) (M, (a_{1}, r_{1}), ..., (a_{ℓ}, r_{ℓ})), (M, (b_{1}, s_{1}), ..., (b_{k}, s_{k})), (M, (c_{1}, t_{1}), ..., (c_{m}, t_{m})) are in M, (ii) each

a_{i} = π(x_{1}^{i}, ..., x_{N(i)}^{i})

some N(i), x_{1}^{i}, ..., x_{N(i)}^{i} ∈ ℕ, each

b_{i} = π(y_{1}^{i}, ..., y_{M(i)}^{i})

some M(i), y_{1}^{i}, ..., y_{M(i)}^{i} ∈ ℕ, each

c_{i} = π(z_{1}^{i}, ..., z_{L(i)}^{i})

some L(i), y_{1}^{i}, ..., y_{L(i)}^{i} ∈ ℕ. and

(iii)

∑_{i≤ℓ} r_{i} · ⟨||x_{1}^{i}||, ||x_{2}^{i}||, ..., ||x_{N(i)}^{i}||⟩ + ∑_{i≤k} s_{i} · ⟨||y_{1}^{i}||, ||y_{2}^{i}||, ..., ||y_{M(i)}^{i}||⟩ = ∑_{i≤m} t_{i} · ⟨||z_{1}^{i}||, ||z_{2}^{i}||, ..., ||z_{L(i)}^{i}||⟩

in G_{{||M||}∪TC(||M||)}, is Borel.

Let Y denote the space (ℚ × ℕ)^{<ℕ}, in its usual Borel structure. M is a Borel subset of X_{L(α)} × Y with countable sections. Thus^{1} we can produce a countable sequence of Borel functions (f_{n})_{n∈ℕ}, each

f_{n} : P^{α} → Y,

such that for any M ∈ P^{α}

(f_{n}(M))_{n∈ℕ}

enumerates without repetition the set of y ∈ Y such that

(M, y) ∈ M.

1See 18.10 [8] for a proof of this classical theorem; indeed, [8] is probably the right reference for all the descriptive set theory used here.

G. Hjorth 16

Thus, again using the uniformization theorem for Borel subsets of the plane with countable sections, we may find a Borel function

θ : P^{α} → ℕ^{ℕ×ℕ}

such that for all M ∈ P^{α} and ℓ, m, n ∈ ℕ

f_{ℓ}(M) + f_{m}(M) = f_{n}(M)

if and only if

(θ(M))(ℓ, m) = n;

and thus θ(M) provides an abelian group structure on ℕ isomorphic to G_{{||M||}∪TC(||M||)}.

5 So what?

Definition Let TFA be the set of all

G : ℕ × ℕ → ℕ

which provide an torsion free abelian on the natural numbers. We let ≅ |_{TFA} be the isomorphism relation on TFA, so that

G_{1} ≅ |_{TFA}G_{2}

if and only if there is some permutation ψ of the natural numbers such that for all m, n ∈ ℕ

ψ(G_{1}(m, n)) = G_{2}(ψ(m), ψ(n)).

If we equip ℕ^{ℕ×ℕ} with the usual product topological structure then TFA becomes a Borel set. The last section showed that for all α < ω_{1}

≅_{α}≤_{B} ≅|_{TFA}.

Thus by

Theorem 5.1 (Harrington) There is no Borel equivalence relation E with

≅_{α}≤_{B} E

all α < ω_{1}. (See [7] 5.11 for a proof.)

we have therefore that ≅|_{TFA} non-Borel.

Harrington’s argument can be used to show that there is no Borel E with each ≅_{α} absolutely Δ ∼_{2}^{1} reducible^{2} reducible to E, and thus we obtain under very general notions of reducibility that not only is ≅_{TFA} not Borel but it is not even reducible to any Borel equivalence relation.

It is known, as found for instance in [1], that if C is a Borel class of countable structures with ≅ |_{C} Borel, then there is some α < ω_{1} with

≅|_{C} ≤_{B} ≅_{α} .

Thus we obtain that any such C is Borel reducible to the isomorphism relation on TFA.

We can also factor in the results of Friedman and Stanley, who in [2] showed that there is no absolutely Δ ∼_{2}^{1} assignment of elements of

2^{<ω_{1}}

as complete invariants for elements of P^{2} up to ≅_{2}. Thus in particular one also obtains that there is no Ulm-type classification of torsion free abelian groups – a result first pointed out in [9] on the basis of very different reasoning.

And we may continue in this fashion. Similar arguments show that ≅_{3} is not absolutely Δ ∼_{2}^{1} reducible to P_{ℵ_{0}}(2^{<ω_{1}}), the set of countable subsets of 2^{<ω_{1}}, and thus that the torsion free abelian groups cannot be assigned elements of P_{ℵ_{0}}(2^{<ω_{1}}) as complete invariants.

And so on.

2In the sense of §9.1 of [4]

References

[1] H. Friedman, Borel and Baire reducibility, preprint, 1999.

[2] H. Friedman, L. Stanley, A Borel reducibility theory for classes of countable structures, Journal of Symbolic Logic, vol. 54(1989), 899-914.

[3] G. Hjorth, Around nonclassifiability for countable torsion free abelian groups, in Proceedings of the modules and abelian groups conference in Dublin, Trends in Mathematics, Birkhäuser Verlag, Basel, 1999.

[4] G. Hjorth, Classification and orbit equivalence relations, AMS, Rhode Island, 2000.

[5] G. Hjorth, Invariants for measure preserving transformations, Fundamenta Mathematicae, vol. 169(2000), pp. 51-84.

[6] G. Hjorth, A.S. Kechris, Borel equivalence relations and classifications of countable models, Annals of Pure and Applied Logic, vol, 82(1996), pp. 221-272.

[7] G. Hjorth, A.S. Kechris, A. Louveau, Borel equivalence relations induced by actions of the symmetric group, Annals of Pure and Applied Logic, vol. 92(1998), pp. 63-112.

[8] A.S. Kechris, Classical descriptive set theory, Springer-Verlag, New York, 1995.

[9] G. Melles, One cannot show in ZFC that there is an Ulm-type classification of countable torsion free abelian groups, in Set theory and the continuum, (eds. H. Judah, W. Just, and W.H. Woodin), MSRI publications 26, Spinger-Verlag, New York, 1992.

greg@math.ucla.edu

MSB 6363 UCLA CA 90095-1555