% LaTeX Report Template - using defaults
\documentclass{article}
\usepackage{amssymb}
\usepackage{latexsym}
% Set the beginning of a LaTeX document
\begin{document}
\def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}
\def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}}
\title{Measuring the classification difficulty of
countable torsion free abelian groups} % Enter your title between curly braces
\author{Greg Hjorth} % Enter your name between curly braces
\date{\today} % Enter your date or \today between curly braces
\maketitle
\section{THE PROBLEM} % Enter section title between curly braces
\bigskip
\underline{Question:} Can we hope to classify countable torsion free abelian groups?
\bigskip
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 $\aleph_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 $\aleph_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:
\bigskip
\underline{Question:} What would establish that there is no way to completely classify
countable torsion free abelian groups?
\bigskip
Some possible answers:
\bigskip
\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.
\bigskip
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:
\bigskip
\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.
\bigskip
Still this is a little bit question begging, since we might then want some
confirmation of the intuition that general countable groups are unclassifiable.
\bigskip
\underline{Answer 3:} Perhaps we can develop an abstract theory of invariants, and show that
there is no {\it reasonable} way to assign certain classes of objects, such as
the Ulm invariants or Baer's invariants for rank one, as complete invariants.
\bigskip
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 {\it reasonable} is subject to some negotiation. I will begin
by considering the explication which takes a {\it reasonable reduction} to be one
that is Borel in some appropriate Borel structure.
\def\R{\mathbb R}
Other explications are possible. For instance, absolutely $\Ubf{\Sigma}^{\rm HC}_1$,
as discussed several sections below.
Or using reductions in $L(\R)$. 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 {\it reasonable
classification} as being one which does not make an egregious appeal to the
existence of a well ordering of $\R$ in assigning its invariants.
\bigskip
\def\N{\mathbb N}
\section{SPACES OF ABELIAN GROUPS}
\bigskip
\underline{Definition:} Let AbGrp $=\{H=(+^H, -(\cdot)^H)\in \N^{\N\times\N}\times
\N^\N| H$ defines an abelian group structure on $\N\}$.
\bigskip
In the discrete topology, $\N$ is a separable completely metrizable space.
Thus $\N^{\N\times\N}$ and $\N^\N$ are separable completely metrizable spaces
in the product spaces, as is $\N^{\N\times\N}\times
\N^\N$. We call this kind of space a {\it Polish space}.
AbGrp is a closed subset of a Polish space, and hence again Polish in the
subspace topology.
\bigskip
\underline{Definition:} TFA$=\{H\in{\rm AbGrp}: H$ is torsion free$\}$ and TFA$_n=\{H
\in {\rm TFA}: H $ has rank $\leq n\}$.
\bigskip
\def\Q{\mathbb Q}
Again TFA is a closed subset of AbGrp, and hence again Polish. TFA$_n$ is not
closed, but instead $G_\delta$ -- that is to say, defined by a countable intersection
of open sets -- and hence Polish.\footnote{For a proof of the general fact that
a $G_\delta$ subset of a Polish space is again Polish one can see Kechris'
{\bf Classical descriptive set theory}. This is also a good reference for
other general facts about Polish spaces and Borel sets.}
There are other ways in which we can model these objects. For instance, in
Simon Thomas' papers\footnote{See for instance
{\it On the complexity of the classification problem for torsion-free abelian groups of rank two}, to appear in {\bf Acta Mathematica} or
{\it On the complexity of the classification problem
for torsion-free abelian groups of finite rank,} to appear in the
{\bf Bulletin of Symbolic Logic}}
he takes the space of subgroups of $\Q^n$ to provide a
Borel structure on the torsion free abelian groups of rank $\leq 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.
\bigskip
\underline{Definition:} For $X, Y$ Polish,
a function $f: X\rightarrow Y$ is Borel if for any
open set $O$ we have
$f^{-1}[O]$ is Borel -- that is to say,
in the $\sigma$-algebra generated by the open sets.
\bigskip
\section{A FIRST APPROXIMATION: SMOOTHNESS}
\bigskip
\underline{Definition:} An equivalence relation $E$ on a Polish space $X$ is {\it smooth}
(Mackey\footnote{See {\it Infinite dimensional group representations},
{\bf Bulletin of the American Mathematical Society}, vol. 69(1965)})
or {\it tame} or {\it concretely classifiable} (Kechris) if there is a
Borel function
\[f: X\rightarrow Y,\]
for some Polish space $Y$, such that $\forall x_1, x_2\in X$
\[x_1 E x_2 {\: \rm iff } \: f(x_1)=f(x_2).\]
\bigskip
\underline{E.g.} If we take $Y=\R$, then this would correspond to assigning real numbers
as complete invariants.
\bigskip
\underline{Alas:} Almost no real life equivalence relations are smooth.\footnote{One
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 {\it are} smooth.}
\bigskip
\underline{E.g.} $\cong|_{{\rm TFA}_1}$ (isomorphism of rank 1 torsion free abelian
groups) is {\it not} smooth.\footnote{An elementary proof of this fact can be
found in the exercises at the end of $\S$3.1 of {\bf 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.}
\bigskip
\section{A BETTER APPROXIMATION: BOREL REDUCIBILITY}
\bigskip
\underline{Definition:} For $E, F$ equivalence relations on Polish
$X, Y$, we write
\[E\leq_B F\]
if there is a Borel function $f:X\rightarrow Y$ such that $\forall x_1, x_2\in X$
\[x_1 E x_2\Leftrightarrow f(x_1) F f(x_2).\]
In other words, for any $x\in 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\leq_B F$ holds but $F\leq_B E$ fails.
\bigskip
\underline{E.g} Consider $\{0,1\}^\N=_{\rm df} 2^\N$, the space of
infinite binary sequences in the product topology. For $\vec x=(x_0, x_1,...),
\vec y=(y_0, y_1,...)$, set
\[\vec x E_0 \vec y\]
if
\[\exists N\forall n> N (x_n=y_n).\]
So this is the equivalence relation of eventual agreement, and under the
natural identification of $2^\N$ with ${\cal P}(\N)$ (the power set of $\N$),
one has
\[2^\N/E_0\sim {\cal P}(\N)/{\rm 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:
\bigskip
\underline{Theorem:} (In effect, Baer) $\cong|_{{\rm TFA}_1}\leq_B E_0$.
\bigskip
Indeed, this is precise. One can also show $E_0\leq_B\cong|_{{\rm TFA}_1}$.
And indeed it was shown by Harrington, Kechris, and Louveau\footnote{L. Harrington,
A.S. Kechris, A. Louveau, {\it A Glimm-Effros dichotomy for Borel equivalence relations},
{\bf Journal American Mathematical Society,}
vol. 3(1990), pp. 903--928. } that $E_0$ corresponds to the {\it 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.
\bigskip
\underline{Theorem:} (Hjorth) \footnote{See {\it Around nonclassifiability for countable torsion
free abelian groups,}
{\bf Abelian groups and modules (Dublin, 1998)},
pp. 269--292, Trends Math., Birkhäuser, Basel, 1999. Here I should mention as an aside that
Simon Thomas has recently shown that for every $n$ we have
\[\cong|_{{\rm TFA}_n}<_B \cong|_{{\rm 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
$\cong|_{{\rm TFA}_2}$ lies {\it directly after} $E_0$ in this hierarchy of classification
difficulties -- that is to say, if $E<_B \cong|_{{\rm TFA}_2}$, must it be the case that
$E\leq_B E_0$?}
$\cong|_{{\rm TFA}_2}\not\leq E_0$.
\bigskip
And thus in particular we would have to look well beyond $E_0$ in
order to find complete invariants for $\cong|_{{\rm TFA}}$, the infinite dimensional
case.
\bigskip
\underline{Definition:} For $x, y\in 2^{\N\times\N}$, set $xF_2 y$ if
\[\{x(n, \cdot)|n\in\N\}=\{y(n, \cdot)|n\in\N\};\]
that is to say, $\forall n_2\exists n_2, n_3\forall m$
\[x(n_1, m)=y(n_2, m),\]
\[x(n_3, m)=y(n_1, m).\]
\bigskip
Thus $F_2$-equivalence classes correspond to something like countable sets of
reals.\footnote{Here and beyond I am somewhat lazily assuming that
the sequence $(x(n,\cdot))_{n\in\N}$ has no repetitions, and thus $x F_2 y$ if and
only if $\{x(n, \cdot)|n\in\N\}=\{y(n, \cdot)|n\in\N\}$; in fact it can be argued that
we lose no generality if we restrict our attention to $x$ for which the sequence
$n\mapsto x(n, \cdot)$ is one to one.}
\bigskip
\underline{Fact:} At each $n$, $\cong|_{{\rm TFA}_n}\leq_B F_2$.
\bigskip
\def\Z{\mathbb Z}
This is proved as so: For each $H$ a rank $n$ torsion free abelian group,
and $\vec g= g_1,..., g_n\in H$, we let $\theta_0(H, \vec g)=\{(k_1,...k_n, \ell)\in
\Z^{n+1}: \ell$ divides $k_1\cdot g_1+k_2\cdot g_2+...k_n\cdot g_n\}$. Then
\[\theta(H)=\{\theta_0(H, \vec g): \vec g\in H^n\}\]
gives us an element of ${\cal P}_{\aleph_0}(\N^{n+1})$ as a complete invariant.
It is not a big step to turn these invariants into elements of ${\cal P}_{\aleph_0}(\N)$,
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 {\it finitely generated} or in some sense have {\it finite rank} are
reducible to $F_2$ by a Borel function.\footnote{For a discussion of results in
this direction, as well as general schemes for classifying countable structures, one
can see G. Hjorth, A.S. Kechris, {\it Borel equivalence relations and
classifications of countable models,}
{\bf Annals of Pure and Applied Logic,}
vol. 82(1996), pp. 221--272.}
So we might at least hope that something like {\it countable sets of reals} can
stand as complete invariants for $\cong|_{\rm TFA}$.
\bigskip
\underline{Definition:} For $x, y\in 2^{\N^{n+1}}$, set
\[x F_{n+1} y\] if
\[\{[x(m, \cdot,...)]_{F_n}|m\in\N\}=\{[y(m,\cdot,...)]_{F_n}|m\in\N\}.\]
\bigskip
In other words, $F_2$-equivalence classes correspond to something like elements
of ${\cal P}_{\aleph_0}(\N)$, $F_3$-equivalence classes correspond to elements of
${\cal P}_{\aleph_0}({\cal P}_{\aleph_0}(\N))$, and so on.
In fact, as given by Friedman and Stanley\footnote{{\it A Borel reducibility
theory for classes of countable structures,} {\bf Journal of Symbolic Logic,}
vol. 54(1989),
pp. 894--914} one can iterate this definition out through the countable
ordinals, and define $F_\alpha$ for each $\alpha < \omega_1$. They also observe:
\bigskip
\underline{Theorem:} (Friedman-Stanley) For each $n$,
\[F_n <_B F_{n+1}.\]
\bigskip
At this point we can finally give the chief negative result regarding the isomorphism
relation on countable torsion free abelian groups.
\bigskip
\underline{Theorem:} (Hjorth\footnote{{\it Torsion free abelian groups},
available on line at
\centerline{\texttt{www.math.ucla.edu/\^{}greg/research.html}}}) For every $n$,
\[F_n\leq_B \cong|_{\rm TFA}.\]
\bigskip
Combining this with Friedman-Stanley:
\bigskip
\underline{Corollary:} At every $n$,
\[\cong|_{\rm TFA}\not\leq_B F_n.\]
\bigskip
(And as might be expected, this goes out through the ordinals. At every countable $\alpha$,
$F_\alpha <_B \cong|_{\rm TFA}.$)
\bigskip
\section{WHAT WE WOULD ULTIMATELY WANT TO PROVE}
\bigskip
\underline{Definition:} For ${\cal 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$({\cal L})$ be the space
\[\prod_i 2^{\N^{a(i)}}\times \prod_j \N^{\N^{b(j)}}.\]
We can define the isomorphism relation, $\cong|_{{\rm Mod}({\cal L})}$, on this
space in the obvious way.
We then say
an isomorphism invariant $K\subset$Mod$({\cal L})$ is said to be {\it universal}
if given any other countable ${\cal L}'$ we have
\[\cong|_{{\rm Mod}({\cal L}')}\leq_B \cong|_K.\]
\bigskip
\underline{E.g.1} Graphs on $\N$ can be viewed as a subset of $2^{\N^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.
\bigskip
So....
\bigskip
\underline{Question:} Are countable torsion free abelian groups universal?
\bigskip
Here I have to admit -- with great shame and hanging of the head -- that I had
previously announced in print\footnote{{\it Around the classification of countable
torsion free abelian groups}, Dublin proceedings, as cited above.} a positive solution to
this problem. The proof was flawed, though it turns out that the result above
regarding the $F_{\alpha}$'s is coming close, since they play a
special role
in the general investigation of isomorphism of countable structures.
\bigskip
\underline{Theorem:} (Dana Scott\footnote{See
{\it Invariant Borel sets,}
{\bf Fundamenta Mathematica,} vol. 56(1964) pp. 117--128.})
For each countable language ${\cal L}$ there are Borel sets
$(A_\alpha)_{\alpha\in \aleph_1}$ such that:
\leftskip 0.4in
\noindent (a) the space of
${\cal L}$-structures with underlying set $\N$ equals
\[\bigcup_{\alpha\in\aleph_1} A_\alpha;\]
\noindent (b) at each $\alpha$,
\[\cong|_{\bigcup_{\beta\leq \alpha}A_\alpha}\leq_B F_\alpha.\]
\leftskip 0in
\bigskip
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_\alpha$, if and only if it is included in some $\bigcup_{\beta<\alpha}A_\beta$,
some countable $\alpha$.
\bigskip
\underline{Question:} (Friedman-Stanley) Let ${\cal L}$ be a countable language and let
$K\subset {\rm Mod}({\cal L})$ be an isomorphism invariant Borel subset. Suppose
at each $\alpha< \aleph_1$ we have
\[F_\alpha \leq_B \cong|_K.\]
Must $\cong|_K$ be universal?
\bigskip
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.
\bigskip
\section{DETAILS}
\underline{Definition:} A function $F$ is {\it absolutely} $\Ubf{\Sigma}_1^{\rm HC}$ if:
\leftskip 0.4in
\noindent (a) there is $x\in 2^\N$ and $\psi$ in the language of set theory such
that
\[F(a)=b\]
if and only if there is a countable transitive structure ${\cal M}$
containing $a, b, x$ and satisfying
\[{\cal M}\models \psi(a, b, x);\]
\noindent (b) (this part is more technical) the formulation of (a) continues to
define a total function through all generic extension.
\leftskip 0in
\bigskip
Following G\"{o}del's work we know that (a) alone is not sufficient to guarantee
a function is {\it nicely behaved}. For instance a function satisfying (a) alone
from $\R$ to $\R$ 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.\footnote{See for instance
$\S$ 9.1{\bf Classification and orbit equivalence
relations}, cited above.} For various purposes these kinds of functions actually
give a
kind of better fit to the notion of {\it reasonable reduction} or {\it reasonable
schema of classification}.
\bigskip
\underline{E.g.1} For $p$ a prime, TA$_p=\{H\in {\rm AbGrp}| H {\rm \: is \:
a \: } p{\rm -group}\}$, there is an
absolutely $\Ubf{\Sigma}_1^{\rm HC}$
\[U: {\rm TA}_p\rightarrow 2^{<\omega_1}\]
such that
\[H_1\cong H_2 \Leftrightarrow U(H_1)\cong U(H_2).\]
This comes out of the Ulm classification of $p$-groups.
\bigskip
\underline{E.g.2} For any countable language ${\cal L}$, there is an
absolutely $\Ubf{\Sigma}_1^{\rm HC}$
\[S: {\rm Mod}({\cal L})\rightarrow {\rm HC}\:\:{\rm (the \: hereditarily \: countable \: sets)}\]
such that
\[{\cal M}_1\cong {\cal M}_2\Leftrightarrow S({\cal M}_1)=S({\cal M}_2).\]
(D. Scott) Moreover we can write
\[{\rm HC}=\bigcup_{\alpha<\aleph_1}V_{\alpha}\cap {\rm HC}\]
and think of $V_\alpha\cap {\rm HC}$ as being a subset of the $F_\alpha$-equivalence
classes.
\bigskip
Here I would be more optimistic about a limited conjecture:
\bigskip
\underline{Conjecture:} ${\cong}|_{\rm TFA}$ is universal with respect to
absolutely $\Ubf{\Sigma}_1^{\rm HC}$ functions. That is to say, for any countable
language ${\cal L}$, we may reduce $\cong|_{{\rm Mod}({\cal L})}$ to
$\cong|_{\rm TFA}$ by the use of an absolutely $\Ubf{\Sigma}_1^{\rm HC}$.
\bigskip
\section{SOMETHING ABOUT THE PROOFS}
The argument that $F_2\leq_B \cong\:|_{\rm 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\leq_B \cong|_{\rm 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.
\bigskip
\def\G{\cal G}
Let $(q_n)_{n\in\N}, (p_n)_{n\in\N}$ be sequences of distinct primes. For $x\in 2^{\N\times
\N}$, for which we can assume $(x(n, \cdot))_{n\in\N}$ is one to one,
we define an abelian group ${\G}_x$ as follows: At each $\ell\in\N$ we set
\[g_{x,\ell}\in{\G}_x\]
so that $g_{x,\ell}$ is divisible by all powers of $p_n$ if $x(\ell, n)=1$ and divisible
by all powers of $q_n$ if $x(\ell, n)=0$. We then let ${\G}_x$ be the abelian group generated
by these $\{g_{x,\ell}: \ell\in\N\}$ and all the divisors we have just insisted on.
The isomorphism type of ${\G}_x$ encodes
$[x]_{F_2}\sim\{x(\ell, \cdot): \ell \in\N\}$.
We can reconstruct the latter from the
former.
Here goes.
Say that $g\in{\G}_x$ is {\it 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\in{\G}_x$ good we let
\[d(g)\in 2^\N\]
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(\ell, \cdot)|\ell\in\N\}=\{d(g)| g\in {\G}_x{\rm \: good}\}.\]
The other details are routine, and thus it is shown that
\[F_2\leq_B \cong|_{\rm TFA}\]
\bigskip
Here we can get some insight by recalling a general fact (see the Friedman, Stanley paper
cited above):
\bigskip
\underline{Fact:} There is no absolutely $\Ubf{\Sigma}_1^{\rm HC}$ function
\[\theta: 2^{\N\times\N}\rightarrow 2^{<\omega_1}\]
such that
\[x F_2 y\Leftrightarrow \theta(x) =\theta(y).\]
\bigskip
In particular this gives a result first obtained by Garvin Melles using very
different means:
\bigskip
\underline{Corollary:} (Melles) We cannot classify countable torsion free abelian
groups by elements of $2^{<\omega_1}$ using
absolutely $\Ubf{\Sigma}_1^{\rm HC}$ functions.\footnote{G. Melles,
{\it One cannot show from ZFC that there is an Ulm-type classification of the
countable torsion-free abelian groups,} {\bf Set theory of
the continuum (Berkeley, CA, 1989)}, pp. 293--309,
Mathematical Sciences Research Institute Publications, 26, Springer, New York, 1992.}
% Set the ending of a LaTeX document
\end{document}