% 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}