Measuring the classification difficulty of countable torsion free abelian groups

Greg Hjorth

September 27, 2001

1 THE PROBLEM

\underline{Question:} Can we hope to classify countable torsion free abelian groups?

Already a few remarks should be made about this question.

First of all the word “classify” is somewhat plastic in its meaning. Someone might for instance take the question to mean whether there is any sense at all in which we can understand countable torsion free abelian groups, and I am sure “classification” takes on different hues across different guilds and mathematical specialties.

I will take the word “classify” to mean ”completely classify by some class of invariants.” Here I have in mind something like the Ulm invariants for countable abelian p-groups or Baer’s classification for the rank one case.

Secondly one might wonder about the restriction to this particular class of groups. Here I would respond by saying that we cannot hope to classify everything, and some restrictions probably are inevitable. Abelian groups represent the topic of this conference, and should be easier and more hopeful than general groups; and the choice of torsion free further removes potentially distracting details. As for confining ourselves to the countable case, cardinality ℵ_{0}, I would mention the kinds of set theoretical complexities which can arise when one considers uncountable discrete structures. Frequently one is led into independence results, and considering subtle combinatorial properties, such as the behavior of the non-stationary ideal, and even classification schemes which would be virtually perfect in the countable case, such as the Ulm invariants, may begin to fail when we pass to ℵ_{1}.

Even granting these restrictions, we may want to take a sceptical stance. After all, if a classification scheme was going to be found then surely it would have made itself known already.

So perhaps it would be better to ask:

\underline{Question:} What would establish that there is no way to completely classify countable torsion free abelian groups?

Some possible answers:

\underline{Answer 1:} (An appeal to empirical evidence.) No classification scheme has been forthcoming. We have waited long enough. It is safe to assume that nothing here is possible.

For some people this will already this will already be enough. And if this is your position, then the remainder of the talk is unlikely to hold much interest.

Personally I am inclined to at least look for a deeper explanation of this empirical fact, so let me push on:

\underline{Answer 2:} We may be able to reduce some other truly horrendous classification problem to that of countable torsion free abelian groups. For instance, perhaps there is a way we can show them to be as hard to classify as general countable groups.

Still this is a little bit question begging, since we might then want some confirmation of the intuition that general countable groups are unclassifiable.

\underline{Answer 3:} Perhaps we can develop an abstract theory of invariants, and show that there is no reasonable way to assign certain classes of objects, such as the Ulm invariants or Baer’s invariants for rank one, as complete invariants.

In fact, it turns out, following work of Friedman, Kechris, Louveau, Stanley, and others, that such a theory has been developed. In this talk I want to discuss how that theory bears on the classification problem for countable torsion free abelian groups.

The meaning of reasonable is subject to some negotiation. I will begin by considering the explication which takes a reasonable reduction to be one that is Borel in some appropriate Borel structure.

Other explications are possible. For instance, absolutely Σ ∼_{1}^{HC}, as discussed several sections below. Or using reductions in L(ℝ). And there are various other exotic classes that logicians find natural to consider. The Borel category has the advantage of being one which is widely used mathematically and does indeed include most commonly accepted classification schemes.

However the reader would not go too far wrong to simply think of a reasonable classification as being one which does not make an egregious appeal to the existence of a well ordering of ℝ in assigning its invariants.

2 SPACES OF ABELIAN GROUPS

\underline{Definition:} Let AbGrp = \{H = (+^{H}, −(·)^{H}) ∈ ℕ^{ℕ×ℕ} × ℕ^{ℕ}|H defines an abelian group structure on ℕ}.

In the discrete topology, ℕ is a separable completely metrizable space. Thus ℕ^{ℕ×ℕ} and ℕ^{ℕ} are separable completely metrizable spaces in the product spaces, as is ℕ^{ℕ×ℕ} × ℕ^{ℕ}. We call this kind of space a Polish space.

AbGrp is a closed subset of a Polish space, and hence again Polish in the subspace topology.

\underline{Definition:} TFA= \{H ∈ AbGrp : H is torsion free\} and TFA_{n} = \{H ∈ TFA : H has rank ≤ n}.

Again TFA is a closed subset of AbGrp, and hence again Polish. TFA_{n} is not closed, but instead G_{δ} – that is to say, defined by a countable intersection of open sets – and hence Polish.^{1}

There are other ways in which we can model these objects. For instance, in Simon Thomas’ papers^{2} he takes the space of subgroups of ℚ^{n} to provide a Borel structure on the torsion free abelian groups of rank ≤ n. It turns out that from the point of view of the kinds of questions we will be considering, such choices are immaterial. All the known ways of providing a Borel structure give the same results.

\underline{Definition:} For X, Y Polish, a function f : X → Y is Borel if for any open set O we have f^{−1}[O] is Borel – that is to say, in the σ-algebra generated by the open sets.

3 A FIRST APPROXIMATION: SMOOTHNESS

\underline{Definition:} An equivalence relation E on a Polish space X is smooth (Mackey^{3}) or tame or concretely classifiable (Kechris) if there is a Borel function

f : X → Y,

for some Polish space Y, such that ∀x_{1}, x_{2} ∈ X

x_{1}Ex_{2} iff f(x_{1}) = f(x_{2}).

\underline{E.g.} If we take Y = ℝ, then this would correspond to assigning real numbers as complete invariants.

1For a proof of the general fact that a G_{δ} subset of a Polish space is again Polish one can see Kechris’ Classical descriptive set theory. This is also a good reference for other general facts about Polish spaces and Borel sets.

2See for instance On the complexity of the classification problem for torsion-free abelian groups of rank two, to appear in Acta Mathematica or On the complexity of the classification problem for torsion-free abelian groups of finite rank, to appear in the Bulletin of Symbolic Logic

3See Infinite dimensional group representations, Bulletin of the American Mathematical Society, vol. 69(1965)

\underline{Alas:} Almost no real life equivalence relations are smooth.^{4}

\underline{E.g.} ≅ |_{TFA_{1}} (isomorphism of rank 1 torsion free abelian groups) is not smooth.^{5}

4 A BETTER APPROXIMATION: BOREL RE-DUCIBILITY

\underline{Definition:} For E, F equivalence relations on Polish X, Y, we write

E ≤_{B} F

if there is a Borel function f : X → Y such that ∀x_{1}, x_{2} ∈ X

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

In other words, for any x ∈ X, [f(x)]_{F} (the F -equivalence class of f(x)) is a complete invariant for [x]_{E}.

We can then write E <_{B} F if E ≤_{B} F holds but F ≤_{B} E fails.

\underline{E.g} Consider \{0, 1\}^{ℕ} =_{df} 2^{ℕ}, the space of infinite binary sequences in the product topology. For x⃗ = (x_{0}, x_{1}, ...), y⃗ = (y_{0}, y_{1}, ...), set

x⃗E_{0}y⃗

if

∃N∀n > N(x_{n} = y_{n}).

So this is the equivalence relation of eventual agreement, and under the natural identification of 2^{ℕ} with P(ℕ) (the power set of ℕ), one has

2^{ℕ}/E_{0} ∼ P(ℕ)/Finite.

Sets considered up to finite difference are not totally unreasonable objects to try to assign as complete invariants, and indeed there is the following classical theorem:

4One of the few exceptions to this lament, and something very much in the mind of George Mackey, is given by the irreducible unitary representations of countable finite by abelian groups considered up to isomorphism. They are smooth.

5An elementary proof of this fact can be found in the exercises at the end of §3.1 of Classification and orbit equivalence relations, G. Hjorth, AMS Surveys and Monograph Series, Rhode Island, 2000.

A sceptical reader might be concerned that the inability to assign reals or points in some other concrete space as complete invariants for rank 1 TFA groups is purely an artifact of our decision to work in the Borel category. This would be a very reasonable concern.

It turns out not to be the case. The same obstruction reappears even considering much more generous class of functions, but a full discussion of this would require an excursion into foundational issues.

\underline{Theorem:} (In effect, Baer) ≅ |_{TFA_{1}} ≤_{B} E_{0}.

Indeed, this is precise. One can also show E_{0} ≤_{B}≅ |_{TFA_{1}}. And indeed it was shown by Harrington, Kechris, and Louveau^{6} that E_{0} corresponds to the next level of classification difficulty after smoothness.

For a few years it was open whether the same thing is true for rank 2. This was ultimately shown to be false.

\underline{Theorem:} (Hjorth) ^{7} ≅ |_{TFA_{2}} ≰ E_{0}.

And thus in particular we would have to look well beyond E_{0} in order to find complete invariants for ≅ |_{TFA}, the infinite dimensional case.

\underline{Definition:} For x, y ∈ 2^{ℕ×ℕ}, set xF_{2}y if

{x(n, ·)|n ∈ ℕ} = {y(n, ·)|n ∈ ℕ};

that is to say, ∀n_{2}∃n_{2}, n_{3}∀m

x(n_{1}, m) = y(n_{2}, m),
x(n_{3}, m) = y(n_{1}, m).

Thus F_{2}-equivalence classes correspond to something like countable sets of reals.^{8}

\underline{Fact:} At each n, ≅ |_{TFA_{n}} ≤_{B} F_{2}.

This is proved as so: For each H a rank n torsion free abelian group, and g⃗ = g_{1}, ..., g_{n} ∈ H, we let θ_{0}(H, g⃗) = {(k_{1}, ...k_{n}, ℓ) ∈ ℤ^{n+1} : ℓ divides k_{1} · g_{1} + k_{2} · g_{2} + ...k_{n} · g_{n}}. Then

θ(H) = {θ_{0}(H, g⃗) : g⃗ ∈ H^{n}}

6L. Harrington, A.S. Kechris, A. Louveau, A Glimm-Effros dichotomy for Borel equivalence relations, Journal American Mathematical Society, vol. 3(1990), pp. 903–928.

7See Around nonclassifiability for countable torsion free abelian groups, Abelian groups and modules (Dublin, 1998), pp. 269–292, Trends Math., Birkhuser, Basel, 1999. Here I should mention as an aside that Simon Thomas has recently shown that for every n we have

≅ |_{TFA_{n}} <_{B} ≅ |_{TFA_{n+1}},

thereby subsuming this earlier result.

I would have been inclined to consider this the final word on the abstract question of the classification difficulty of the finite rank TFA groups, but after the talk someone pointed out a further issue which is unresolved. We do not know whether ≅ |_{TFA_{2}} lies directly after E_{0} in this hierarchy of classification difficulties – that is to say, if E <_{B} ≅ |_{TFA_{2}}, must it be the case that E ≤_{B} E_{0}?

8Here and beyond I am somewhat lazily assuming that the sequence (x(n, ·))_{n∈ℕ} has no repetitions, and thus xF_{2}y if and only if {x(n, ·)|n ∈ ℕ} = {y(n, ·)|n ∈ ℕ}; in fact it can be argued that we lose no generality if we restrict our attention to x for which the sequence n ↦ x(n, ·) is one to one.

gives us an element of P_{ℵ_{0}}(ℕ^{n+1}) as a complete invariant. It is not a big step to turn these invariants into elements of P_{ℵ_{0}}(ℕ), and from there to pass to a Borel reduction to the equivalence relation F_{2}.

The general rule of thumb is that any class of countable structures which are in some sense finitely generated or in some sense have finite rank are reducible to F_{2} by a Borel function.^{9}

So we might at least hope that something like countable sets of reals can stand as complete invariants for ≅ |_{TFA}.

\underline{Definition:} For x, y ∈ 2^{ℕ^{n+1}}, set

xF_{n+1}y

if

{[x(m, ·, ...)]_{F_{n}}|m ∈ ℕ} = {[y(m, ·, ...)]_{F_{n}}|m ∈ ℕ}.

In other words, F_{2}-equivalence classes correspond to something like elements of P_{ℵ_{0}}(ℕ), F_{3}-equivalence classes correspond to elements of P_{ℵ_{0}}(P_{ℵ_{0}}(ℕ)), and so on.

In fact, as given by Friedman and Stanley^{10} one can iterate this definition out through the countable ordinals, and define F_{α} for each α < ω_{1}. They also observe:

\underline{Theorem:} (Friedman-Stanley) For each n,

F_{n} <_{B} F_{n+1}.

At this point we can finally give the chief negative result regarding the isomorphism relation on countable torsion free abelian groups.

\underline{Theorem:} (Hjorth^{11}) For every n,

F_{n} ≤_{B}≅ |_{TFA}.

Combining this with Friedman-Stanley:

\underline{Corollary:} At every n,

≅ |_{TFA} ≰_{B} F_{n}.

9For a discussion of results in this direction, as well as general schemes for classifying countable structures, one can see 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.

10A Borel reducibility theory for classes of countable structures, Journal of Symbolic Logic, vol. 54(1989), pp. 894–914

11Torsion free abelian groups, available on line at

www.math.ucla.edu/^greg/research.html

(And as might be expected, this goes out through the ordinals. At every countable α, F_{α} <_{B}≅ |_{TFA}.)

5 WHAT WE WOULD ULTIMATELY WANT TO PROVE

\underline{Definition:} For L a countable language, with relations R_{1}, R_{2}, ..., having arities a(1), a(2), ..., and function symbols F_{1}, F_{2}, .... having arities b(1), b(2), ..., we let Mod(L) be the space

∏_{i} 2^{ℕ^{a(i)}} × ∏_{j} ℕ^{ℕ^{b(j)}}.

We can define the isomorphism relation, ≅ |_{Mod(L)}, on this space in the obvious way.

We then say an isomorphism invariant K ⊂Mod(L) is said to be universal if given any other countable L′ we have

≅ |_{Mod(L′)} ≤_{B}≅ |_{K}.

\underline{E.g.1} Graphs on ℕ can be viewed as a subset of 2^{ℕ^{2}}. It is a folklore result that the isomorphism relation on this class of countable structures is universal.

\underline{E.g.2} (Friedman-Stanley) Countable linear orderings are universal in this sense.

\underline{E.g.3} (? folk?) Isomorphism on countable groups is universal.

\underline{E.g.4} (Camerlo-Gao) Countable Boolean algebras are universal.

So....

\underline{Question:} Are countable torsion free abelian groups universal?

Here I have to admit – with great shame and hanging of the head – that I had previously announced in print^{12} a positive solution to this problem. The proof was flawed, though it turns out that the result above regarding the F_{α}’s is coming close, since they play a special role in the general investigation of isomorphism of countable structures.

\underline{Theorem:} (Dana Scott^{13}) For each countable language L there are Borel sets (A_{α})_{α∈ℵ_{1}} such that:

12Around the classification of countable torsion free abelian groups, Dublin proceedings, as cited above.

13See Invariant Borel sets, Fundamenta Mathematica, vol. 56(1964) pp. 117–128.

(a) the space of L-structures with underlying set ℕ equals

⋃_{α∈ℵ_{1}} A_{α};

(b) at each α,

≅ |_{⋃_{β≤α} A_{α}} ≤_{B} F_{α}.

There are various consequences of his result which can probably be considered folklore. For instance, a Borel set of countable structures has a Borel isomorphism relation if and only if it is Borel reducible to some F_{α}, if and only if it is included in some ⋃_{β<α} A_{β}, some countable α.

\underline{Question:} (Friedman-Stanley) Let L be a countable language and let K ⊂ Mod(L) be an isomorphism invariant Borel subset. Suppose at each α < ℵ_{1} we have

F_{α} ≤_{B}≅ |_{K}.

Must ≅ |_{K} be universal?

Therefore, at the very least, we can say that either countable torsion free abelian groups are universal, or their failure to be represents an entirely new phenomena.

6 DETAILS

\underline{Definition:} A function F is absolutely Σ ∼_{1}^{HC} if:

(a) there is x ∈ 2^{ℕ} and ψ in the language of set theory such that

F (a) = b

if and only if there is a countable transitive structure M containing a, b, x and satisfying

M ⊧ ψ(a, b, x);

(b) (this part is more technical) the formulation of (a) continues to define a total function through all generic extension.

Following Gödel’s work we know that (a) alone is not sufficient to guarantee a function is nicely behaved. For instance a function satisfying (a) alone from ℝ to ℝ may fail to be Lebesgue measurable.

It is a kind of folklore result that if we add (b) in addition then we do indeed obtain all the nice properties we could hope for – such as being universally measurable.^{14} For various purposes these kinds of functions actually give a kind of better fit to the notion of reasonable reduction or reasonable schema of classification.

14See for instance § 9.1Classification and orbit equivalence relations, cited above.

\underline{E.g.1} For p a prime, TA_{p} = \{H ∈ AbGrp|H is a p−group\}, there is an absolutely Σ ∼_{1}^{HC}

U : TA_{p} → 2^{<ω_{1}}

such that

H_{1} ≅ H_{2} ⇔ U(H_{1}) ≅ U(H_{2}).

This comes out of the Ulm classification of p-groups.

\underline{E.g.2} For any countable language L, there is an absolutely Σ ∼_{1}^{HC}

S : Mod(L) → HC (the hereditarily countable sets)

such that

M_{1} ≅ M_{2} ⇔ S(M_{1}) = S(M_{2}).

(D. Scott) Moreover we can write

HC = ⋃_{α<ℵ_{1}} V_{α} ∩ HC

and think of V_{α} ∩ HC as being a subset of the F_{α}-equivalence classes.

Here I would be more optimistic about a limited conjecture:

\underline{Conjecture:} ≅|_{TFA} is universal with respect to absolutely Σ ∼_{1}^{HC} functions. That is to say, for any countable language L, we may reduce ≅ |_{Mod(L)} to ≅ |_{TFA} by the use of an absolutely Σ ∼_{1}^{HC}.

7 SOMETHING ABOUT THE PROOFS

The argument that F_{2} ≤_{B}≅ |_{TFA} at least is very simple. Indeed somewhat misleadingly so. F_{2}-equivalence classes can be coded up in countable structures just using unary predicates, and the model theory without relations or functions is extremely simple. For F_{3} and beyond relations are necessary, and the proof of F_{3} ≤_{B}≅ |_{TFA} is more involved that than the sketch below.

I will also further simplify this sketch by skipping over any argument that the reduction is Borel.

Let (q_{n})_{n∈ℕ}, (p_{n})_{n∈ℕ} be sequences of distinct primes. For x ∈ 2^{ℕ×ℕ}, for which we can assume (x(n, ·))_{n∈ℕ} is one to one, we define an abelian group G_{x} as follows: At each ℓ ∈ ℕ we set

g_{x,ℓ} ∈ G_{x}

so that g_{x,ℓ} is divisible by all powers of p_{n} if x(ℓ, n) = 1 and divisible by all powers of q_{n} if x(ℓ, n) = 0. We then let G_{x} be the abelian group generated by these {g_{x,ℓ} : ℓ ∈ ℕ} and all the divisors we have just insisted on.

The isomorphism type of G_{x} encodes [x]_{F_{2}} ∼ {x(ℓ, ·) : ℓ ∈ ℕ}. We can reconstruct the latter from the former.

Here goes.

Say that g ∈ G_{x} is good if for all n either g is divisible by all powers of p_{n} or it is divisible by all powers of q_{n}. Then for g ∈ G_{x} good we let

d(g) ∈ 2^{ℕ}

be defined by

(d(g))(n) = 1

if and only if g is divisible by all powers of p_{n}.

And then one indeed obtains

{x(ℓ, ·)|ℓ ∈ ℕ} = {d(g)|g ∈ G_{x} good}.

The other details are routine, and thus it is shown that

F_{2} ≤_{B}≅ |_{TFA}

Here we can get some insight by recalling a general fact (see the Friedman, Stanley paper cited above):

\underline{Fact:} There is no absolutely Σ ∼_{1}^{HC} function

θ : 2^{ℕ×ℕ} → 2^{<ω_{1}}

such that

xF_{2}y ⇔ θ(x) = θ(y).

In particular this gives a result first obtained by Garvin Melles using very different means:

\underline{Corollary:} (Melles) We cannot classify countable torsion free abelian groups by elements of 2^{<ω_{1}} using absolutely Σ ∼_{1}^{HC} functions.^{15}

15G. Melles, One cannot show from ZFC that there is an Ulm-type classification of the countable torsion-free abelian groups, Set theory of the continuum (Berkeley, CA, 1989), pp. 293–309, Mathematical Sciences Research Institute Publications, 26, Springer, New York, 1992.