% LaTeX Article Template - using defaults
\documentclass{article}[12pt]

\usepackage{amssymb}
\usepackage{latexsym}
\pagestyle{myheadings}
\markright{G. Hjorth}

     

\usepackage{amssymb}
\usepackage{latexsym}




% Set left margin - The default is 1 inch, so the following
% command sets a 1.25-inch left margin.
\setlength{\oddsidemargin}{-0.15in}

% Set width of the text - What is left will be the right margin.
% In this case, right margin is 8.5in - 1.25in - 6in = 1.25in.
\setlength{\textwidth}{6.5in}
     
% Set top margin - The default is 1 inch, so the following
% command sets a 0.75-inch top margin.
\setlength{\topmargin}{-0.1in}

% Set height of the header
\setlength{\headheight}{0.3in}

% Set height of the text
\setlength{\textheight}{8.1in}

% Set vertical distance between the text and the
% bottom of footer
\setlength{\footskip}{0.8in}



% Set the beginning of a LaTeX document
\begin{document}

%\large
     
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{subclaim}[theorem]{Subclaim}



     \newenvironment{proof}[1][Proof]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\hfill$\Box$\end{trivlist}}
     \newenvironment{definition}[1][Definition]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
     \newenvironment{example}[1][Example]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
     \newenvironment{remark}[1][Remark]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
     \newenvironment{notation}[1][Notation]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
     \newenvironment{question}[1][Question]{\begin{trivlist}
     \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}



\def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}}
\def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}}
\def\R{{\mathbb R}}
\def\C{{\mathbb C}}
\def\V{{\mathbb V}}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\K{{\mathbb K}}
\def\B{{\mathbb B}}
\def\P{{\mathbb P}}
\def\Q{{\mathbb Q}}
\def\o{{\omega}}
\def\oo{{\omega^{\omega}}}
\def\lo{{\omega^{<\omega}}}
\def\d{{\dot{\bigcup}}}
\def\h{{\cal H}}
\def\no{\noindent}
\def\nh{|\! |}
\def\a{{\mathcal A}}
\def\b{{\mathcal B}}
\def\l{{\mathcal L}}
\def\n{{\mathcal N}}
\def\m{{\mathcal M}}
\def\p{{\mathcal P}}
\def\h{{\mathcal H}}
\def\co{{\mathcal O}}
\def\t{{\mathcal T}}
\def\c{{\mathcal C}}
\def\g{{\mathcal G}}

\title{\huge The isomorphism relation on countable torsion free abelian groups}         
\author{Greg Hjorth}        % Enter your name between curly braces
\date{\today}          % Enter your date or \today between curly braces
\maketitle



\abstract{The isomorphism relation on countable torsion free abelian groups 
is non-Borel.} 

%\tableofcontents   


\section{Introduction} 
\label{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 \cite{TFA} 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 \cite{misery}. 

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 \cite{misery}. 

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

\begin{definition} Let $E$ and $F$ be Borel equivalence relations on Polish spaces 
$X$ and $Y$. We write 
\[E\leq_B F\] 
if there is a Borel function 
\[\theta: X\rightarrow Y\] 
such that for all $x_1, x_2\in X$ 
\[x_1 E x_2\Leftrightarrow \theta(x_1) F \theta(x_2).\] 
\end{definition} 

For $\l$ a countable language we can form, as described in \cite{hjkelo}, the 
Polish space $X_\l$ of $\l$ structures with underlying set $\N$. 
For $\l$ consisting of a single binary operation, $+$, 
the torsion free abelian groups form a closed invariant subset TFA$\subset X_\l$. 

Our main result is that 

\begin{theorem} For $\l'$ a countable language and $C\subset X_{\l'}$ a Borel set such that 
the isomorphism relation on $C$, $\cong\!|_C$, is Borel, we always have 
\[\cong\!|_C\leq_B \cong\!|_{\rm TFA}.\] 
\end{theorem} 

In particular this implies that $\cong\!|_{\rm TFA}$ is non-Borel, answering a question 
raised in \cite{friedmanstanley}. However we leave open the question which the authors of 
\cite{friedmanstanley} correctly identify as most fundamental: 

\begin{question} Let $\l'$ be a countable language. Do we necessarily have 
\[\cong\!|_{\l'}\leq_B \cong\!|_{\rm TFA}{\rm ?}\] 
\end{question} 

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 \cite{hjkelo} and \cite{hjorthkechris}. Between them these papers should 
also provide the technical background and an explanation of notation not adequately 
defined below. 


\newpage 





\section{Group eplags} 
\label{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 {\it 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 $\N$ into torsion free abelian groups 
considered up to isomorphism. 

Although 2.5 and the coding techniques of $\S$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_{\aleph_0}(\p({\N}))$ 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\in\N}$. Then given 
$\{a_n: n\in\N\}\subset \p(\N)$ we can describe a subgroup of 
$\Q^{\N}$, where the element $\delta_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\in a_n$. With suitable 
care this can be done so that the {\it isomorphism type} of the 
corresponding group only depends on the set $\{a_n: n\in\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\in a_n\}$, for some $n\in\N$. 

The case of $\p_{\aleph_0}(\p({\N}))$ 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. 

\begin{definition} A {\it graph} is a pair $(V, E)$ where $V$ is a set 
and $E$ is a subset of the unordered pairs 
\[\{\{v, w\}: v, w\in V, v\neq w\}\]
of elements in $V$. 
\end{definition} 

\begin{notation} $\P$ denotes the set of primes 
\end{notation} 

\begin{definition} A {\it prime labeled graph} is a triple $(V, E, f)$ where 
$(V, E)$ is a graph and 
\[f:V\cup E\rightarrow \P.\] It is said to be {\it excellent} if 

\leftskip 0.4in 

\no (i) $f[V]\cap f[E]=\emptyset$; that is to say, vertices and edges are always 
assigned distinct primes; 

\no (ii) for any $p\in\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. 

\leftskip 0in 

I will use the acronym {\it eplag} for excellent prime labeled graph. 
\end{definition} 

\begin{definition} Given an eplag $(V, E, f)$ we we define the corresponding 
{\it group eplag,} denoted 
\[\g(V, E, f).\] 
We first consider the group consisting of all formal sums 
\[\sum_{v\in V_0} q_v\cdot v,\] 
where $V_0$ is a finite subset of $V$ and $(q_v)_{v\in 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=\sum_{v\in V_0}\frac{k_v \cdot v}{f(v)^{\ell_v}} + 
\sum_{\{v, w\}\in E_0}\frac{n_{\{v, w\}}\cdot (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\}}\in \Z$, $\ell_v, m_{\{v, w\}}\in \N$. 
\end{definition} 

In other words, $\g(V, E, f)$ can be thought of as isomorphic to 
a subgroup of the direct sum 
\[\bigoplus_V \Q,\] 
in the product group structure, where we insist that each $\chi_{\{v\}}$ 
(the characteristic function of $\{v\}$, taking $\chi_{\{v\}}(w)=1$ when 
$w=v$, and assuming value $0$ otherwise) is divisible by all powers of $f(v)$ while 
each $\chi_{\{v\}}+\chi_{\{w\}}$ is divisible by all powers of $f(\{v, w\})$ for 
$\{v, w\}\in E$. 
In particular every element of $\g(V, E, f)$ 
can be written in the form 
\[\sum_{v\in V_1} q_v\cdot v\] 
for some finite $V_1\subset V$ and associated collection $\{q_v: v\in V_1\}$ 
of rationals. 



\begin{definition} Let $\g(V, E, f)$ be an eplag and 
\[\rho: V\rightarrow \{-1, 0, 1\}\] 
a function. We define a resulting homomorphism 
\[\varphi_\rho: \g(V, E, f)\rightarrow \Q\] 
by 
\[\varphi_\rho(\sum_{v\in V_0}q_v \cdot v)=
\sum_{v\in V_0}q_v\rho(v) .\] 
\end{definition} 

\begin{definition} Let $g(V, E, f)$ be a group eplag and let $p$ be 
a prime. A  
homomorphism 
\[\psi: \g(V, E, f)\rightarrow \Q\] 
is {\it $p$-mindful} if there is some 
\[\rho: V\rightarrow\{-1, 0,1\}\] 
with 
\[\rho (w_0)= - \rho(w_1)\] 
all $\{w_0, w_1\}\in E\cap f^{-1}[\{p\}]$ 
and 
\[\psi=\varphi_\rho\] as above. 
\end{definition} 

\begin{lemma} 
\label{note} 
If 
\[C\subset V\] 
is a connected component of $(V, f^{-1}[\{p\}])$ containing some given vertex $v$ 
and 
\[\varphi_0, \varphi_1: \g(V, E, f)\rightarrow \Q\] 
are $p$-mindful homomorphisms with $\varphi_0(v), \varphi_1(v)$ both non-zero, 
then for any $g\in\g(V, E, f)$ of the form 
\[g=\sum_{v\in C_0}q_v\cdot v\] 
with $C_0$ a finite subset of $C$, we have 
\[\varphi_0(g)=0\] 
if and only if 
\[\varphi_1(g)=0.\] 
\end{lemma} 

\begin{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\in C\}$. 
Each of these homomorphisms is the mirror image of the other, in the sense 
that $\varphi_0(g)=-\varphi_1(g)$ all $g$ in their common domain. 
\end{proof} 

\begin{lemma} 
\label{note2} Suppose $C_1, C_2,...C_k$ are distinct 
connected components of 
$(V, f^{-1}[\{p\}]\cap E)$ and for each $i\leq k$ we have 
\[g_i=\sum_{v\in V_i} r_v\cdot v\] 
for some $V_i\subset C_i$.  Suppose 
\[g=g_1+g_2+...g_k.\]
Then the following statements are 
equivalent:  

\smallskip 

\leftskip 0.4in 

(I) $g$  
takes the value 
\[\varphi(g)=0\] for each $p$-mindful $\varphi$.  

\smallskip 

(II) Each $g_i$ takes the value 
\[\varphi(g_i)=0\] 
for each $p$-mindful $\varphi$. 

\leftskip 0in 

\end{lemma} 

\begin{proof} 
Since if ${\cal F}$ enumerates the components of 
$(V, f^{-1}[\{p\}]\cap E)$, then any $p$-mindful $\varphi$ may be written as a 
sum 
\[\varphi: g\mapsto \sum_{C\in {\cal F}}\varphi_C(g)\] 
where each $\varphi_C$ is $p$-mindful and assumes the value 0 
outside of $C$. 
\end{proof} 




\begin{lemma} 
\label{1.4} 
Let $\g(V, E, f)$ be a group eplag, $p\in\P$, $v\in V$. Then there is a function 
\[\rho: V\rightarrow \{-1, 0,1\}\] 
such that 

\leftskip 0.4in 

\no (i) $\rho(w)\neq 0$ if and only if there are 
\[v_0, v_1, ..., v_k\in V,\] 
each 
\[\{v_i, v_{i+1}\}\in  f^{-1}[\{p\}]\cap E,\] 
and 
\[v_0=v, v_k=w;\] 
in other words, $\rho$ takes non-zero values exactly on the component of 
$(V, f^{-1}[\{p\}]\cap E)$ containing $v$; 

\no (ii) for $\{w_0, w_1\}\in f^{-1}[\{p\}]\cap E$ we have 
\[\rho(w_0)=-\rho(w_1);\] 
in other words, $\rho$ provides a two coloring of the component on which it is 
non-zero. 

\leftskip 0in 

\end{lemma} 

\begin{proof} This is essentially a restatement of the well known fact that every 
tree admits a two coloring. 
\end{proof} 

\begin{lemma} 
\label{induction} 
Let $(V, E, f)$ be an eplag. Suppose $p\in\P$ and 
$(T, f^{-1}[\{p\}]\cap \{\{v, w\}: v, w\in T\})$ is a finite subtree of 
$(V, f^{-1}[\{p\}]\cap E)$ and 
\[g\in \g(V, E, f)\] 
has the form 
\[g=\sum_{v\in T} r_v\cdot v\] 
for rationals $\{r_v: v\in T\}$. 
Suppose $\varphi(g)=0$ for every $p$-mindful homomorphism 
\[\varphi:\g(V, E, f)\rightarrow \Q.\] 

Then $g$ is divisible by every power of $p$. 
\end{lemma} 

\begin{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\cdot v$ we can always define a $p$-mindful 
homomorphism $\varphi$ which assumes a value $\varphi(v)=1$; and certainly 
zero is divisible by all powers of $p$. 

%If $|T|=2$ then 
%\[g=q\cdot w + r\cdot v,\] 
%where 
%\[\{w, v\}\in E\cap f^{-1}[\{p\}],\] 
%and we must have $q=r$, and then it is immediate from the 
%definition of the group eplag that $g$ is divisible by all powers of $p$. 

So now suppose 
\[g=\sum_{v\in T} r_v\cdot v,\] 
$|T|=n+1\geq 2$, and that the lemma has been proved for any trees $T'$ with 
$|T'|\leq n$. Then we may choose a node $v_0\in T$ that is terminal; let $v_1$ 
be the unique vertex in $T$ with $\{v_0, v_1\}\in f^{-1}[\{p\}]$. 
We can let 
\[h=r_{v_0}\cdot v_0 + r_{v_0}\cdot 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 
$\varphi(h)=0$ for every $p$-mindful homomorphism $\varphi$. Thus by assumption on 
$g$ 
\[\varphi(g-h)=0\] 
for every $p$-mindful homomorphism $\varphi: \g(V, E, f)\rightarrow \Q$, 
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$. 
\end{proof} 





In the proof of the following proposition we use without explicit mention {\it 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}=\sum_{i\leq k}\frac{n_i}{(p_i)^{m_i}},\] 
then for some $i\leq k$ we have 
\[p_i=p.\]





\begin{proposition} 
\label{1.6} 
Let $\g(V, E, f)$ be a group eplag, $p\in\P$, 
$V_0\subset V$ finite, $g\in\g(V, E,f)$ of 
the form 
\[g=\sum_{v\in V_0}q_v\cdot v,\] 
where each $q_v\neq 0$. 
Then $g$ is divisible by all powers of $p$ in $\g(V, E,f)$ if and only if either: 

\leftskip 0.4in 

\no (i) $V_0\subset V\cap f^{-1}[\{p\}]$; or, 

\no (ii) for each $p$-mindful homomorphism 
\[\varphi: \g(V, E, f)\rightarrow \Q\] 
we have 
\[\varphi(g)=0.\]
\end{proposition} 

\begin{proof} For notational simplicity let us assume each $q_v\in \Z$. 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$. 

\smallskip 

\no ($\Leftarrow$): First suppose (i) holds. Then it is immediate from the definitions that 
for each $v\in V_0$ and $n\in\N$ we have 
\[p^{-n}\cdot v \in\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\cap f^{-1}[\{p\}])$ such that 
\[g=g_1+g_2+...+g_k\] 
where each $g_i$ is a rational linear combination 
of $\{v: v\in 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 
\ref{note2} we 
may as well assume that $k=1$; that is to say, $g$ is contained in a single component of 
$(V, E\cap f^{-1}[\{p\}])$. 

With this in hand, we can write 
\[g=\sum_{v\in T}\ell_v\cdot v\] 
where $T\subset V$ is finite and 
\[(T, f^{-1}[\{p\}]\cap \{\{v, w\}: v, w\in T\})\] 
forms a tree. 
And then we are done by appealing to \ref{induction}. 

\smallskip 

\no ($\Rightarrow$): Assume for a contradiction that (i) and (ii) both fail. 



\smallskip 

\no {\bf Claim(1):} There is $h\in G$ such that 
\[\varphi(h)=0\] for every $p$-mindful homomorphism $\varphi: \g(V, E, f)\rightarrow \Q$ 
and is such that if 
\[h+g=\sum_{v\in W}r_v\cdot v\] 
is a representation of $g+h$ with each $r_v\neq 0$ for $v\in W$, then we have that for 
each connected component $C$ of $(V, f^{-1}[\{p\}])$ there is {\it at most one} 
$v\in W\cap C$. 

\smallskip 

\no {\bf Proof of claim:} 
For each connected component $C$ of $(V, f^{-1}[\{p\}]\cap E)$ that meets $V_0$ 
choose some single $v_C\in C$ and a 2-coloring 
\[\rho_C: C\rightarrow\{-1, 1\}\] of the 
tree 
\[(C, f^{-1}[\{p\}]\cap \{\{w_1, w_2\}\in E: w_1, w_2\in C\})\] 
with $\rho_C(v_C)=1$.  
We then let 
\[h_C=\sum_{v\in C\cap V_0}-q_v\cdot v 
+\sum_{v\in C\cap V_0}q_v\rho_C(v)\cdot v_C.\]
By \ref{note} we have that for any $p$-mindful homomorphism $\varphi$  
\[\varphi(h_C)=0.\] Thus if we let ${\cal F}$ enumerate the connected 
components of $(V, f^{-1}[\{p\}]\cap E)$ meeting $V_0$, then 
\[h=\sum_{C\in{\cal F}}h_C\] 
is as required. 

\hfill (Claim$\Box$) 

\smallskip 

Thus by the already proved direction $\Leftarrow$ 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\neq 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\}]\cap E)$ 
there is at most a single vertex $w_C$ with 
\[w_C\in V_0\cap C\] 
in the representation of $g$. 
Thus for some finite collection ${\cal H}$ of connected components of 
$(V, f^{-1}[\{p\}])$ and some finite collection $(a_C)_{C\in{\cal H}}$ 
of integers we have 
\[g=\sum_{C\in{\cal 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}=\sum_{v\in V_1} \frac{k_v\cdot v}{f(v)^{\ell_v}}
+\sum_{\{v, w\}\in E_1}\frac{n_{\{v, w\}}(v+w)}{f(\{v, w\})^{m_{\{v, w\}}}},\] 
for finite $V_1\subset V$, $E_1\subset E$, each $m_{\{v, w\}}>0$, each $n_{\{v, w\}}$ 
indivisible by $f(\{v, w\})$. 
For each $C\in{\cal H}$ let $T_C\subset C$ be the smallest possible subtree 
of $(V, f^{-1}[\{p\}])$ such that if $\{v_0, v_1\}\in E_1$ with $v_0, v_1\in C$  
then 
\[v_0, v_1\in T_C.\] 


\smallskip 


\no {\bf Claim(2):} $f^{-1}[\{p\}]\cap V=\emptyset$. 

\smallskip 

\no {\bf 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=\sum_{v\in W_1}\frac{b_v\cdot 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\}\in E$, each $b_v\in \Z$, and each $c_v\in\N$. 
In particular then the assumption of $g$'s unlimited divisibility by $p$ 
along with our hypothesis that some $v\in V_0$ has 
$f(v)\neq p$ implies that there is some $w$ with 
\[\{w, v\}\in E\] 
and  
\[f(\{w, v\})=p.\] 
Then by the definition of {\it excellent} prime labeled graph we must have 
\[f^{-1}[\{p\}]\cap V=\emptyset.\] 

\hfill (Claim$\Box$) 

\smallskip 

\no {\bf Claim(3):} For no $C\in \h$ do we have 
\[T_C=\emptyset;\] 
that is to say, for every $C\in\h$ there is some $v_0, v_1\in C$ 
with 
\[{\{v_0, v_1\}}\in E_1.\] 

\smallskip 

\no {\bf Proof of claim:} Since for each $C\in\h$ we may write 
\[\frac{g}{p^n}= 
\frac{{a_C}\cdot w_C}{p^n} + 
\sum_{v\in V_0, v\neq w_C} \frac{q_v\cdot v}{p^n}\] 
and 
\[\frac{g}{p^n}=
\sum_{v\in V_1} \frac{k_v\cdot v}{f(v)^{\ell_v}}
+\sum_{\{v, w\}\in E_1}\frac{n_{\{v, w\}}\cdot (v+w)}{f(\{v, w\})^{m_{\{v, w\}}}},\] 
and since each ${a_C}$ is indivisible by $p^n$, we see that 
for any $C\in\h$ there is some $v$ with 
\[\{v, w_C\}\in E_1,\] 
\[f(\{v, w_C\})=p.\] 


\hfill (Claim$\Box$) 

So let us choose $C_0\in\h$ and $v_0\in T_{C_0}$ with 
$v_0\neq w_{C_0}$ but $v_0$ terminal in 
$T_{C_0}$ -- that is to say, there is exactly one 
other $v_1\in T_{C_0}$ with $\{v_0, v_1\}\in 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}=\sum_{C\in\h}\frac{a_C\cdot w_C}{p^n},\] 
and 
using $v_0\neq w_C$ all $C\in\h$ we see that 
\[\frac{k_{v_0}\cdot v_0}{f(v_0)^{\ell_{v_0}}} 
+\sum_{\{v_0, w\}\in 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\in V: w\neq v_0\},\] 
and thus 
\[\frac{k_{v_0}}{f(v_0)^{\ell_{v_0}}} + 
\sum_{\{v_0, w\}\in 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\}\in 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)^{\ell_{v_0}}} + 
\frac{n_{\{w_0, v_0\}}}{p^{m_{\{w_0, v_0\}}}} + 
\sum_{i\leq N} \frac{n_i}{p_i^{m_i}} =0.\] 
Since $f(v_0)\neq p$ we have at last reached a contradiction. 





\end{proof}


\newpage 










\section{Coding hereditarily countable sets} 

\begin{definition} Following \cite{hjkelo}, 
we define $\p^{\alpha}(\N)$ by 
induction on $\alpha<\omega_1$. We begin with 
\[\p^0(\N)=\N\] 
and then inductively define 
\[\p^\alpha(\N)\] for $\alpha>0$ 
to be 
\[\bigcup_{\beta<\alpha}\p^\beta(\N)\] 
along with 
the set of all countable subsets of 
\[\bigcup_{\beta<\alpha}\p^\beta(\N).\] 
For 
\[A\in \bigcup_{\alpha<\omega_1}\p^\alpha(\N)\] 
we let Rk$(A)$ be the least $\alpha$ such that 
\[A\in \p^\alpha(\N).\] 

We also define TC$(A)$ in the following way. If $A=m\in\p^0(\N)$ 
we define TC$(A)$ to be the set $\{n: n<m\}$. 
We then continue inductively, so that when $A\in\p^\alpha(\N)$ some 
$\alpha>0$ then 
\[{\rm TC}(A)=A\cup(\bigcup_{B\in A}{\rm TC}(B)).\] 
\end{definition} 

\begin{notation} For the rest of this section fix $\alpha$ a countable ordinal 
and a collection of distinct primes 
\[\{p_\beta: \beta\leq \alpha, \beta\neq 0\}\cup\{q_n: n\in\N\}\cup \{\hat{q}_{\gamma, \beta}: 
\gamma<\beta\leq \alpha\}\cup \{\bar{p}_{\gamma, \beta}: 
\gamma<\beta\leq \alpha\}.\] 
\end{notation} 

The goal of this section is to show that given this ordinal $\alpha$ and 
this collection 
of primes we can canonically associate to each $A\in \p^\alpha(\N)$ a corresponding 
torsion free abelian 
group 
\[\h_A\] 
such that 
\[A_0=A_1\] 
if and only if 
\[\h_{A_0}\cong \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\in\p^{\alpha+1}(\N)$, 
and verify that 
\[{\rm TC}(A_1)\neq {\rm TC}(A_2)\] 
implies 
\[\g_{A_1}\not\cong \g_{A_2}.\] 
We then can define for $A\in \p^\alpha(\N)$ 
\[\h_A=\g_{\{A\}\cup{\rm TC}(A)}\] 
and check that indeed 
\[A_1=A_2\Leftrightarrow \h_{A_1}\cong \h_{A_2}.\] 

\begin{definition} For $A\in\p^{\alpha+1}(\N)$ we let 
$V_A$ consist of all 
\[\langle A_1, A_2, ..., A_n\rangle\] 
where 

\leftskip 0.4in 

\no (i) $n\in\N$; 

\no (ii) each $A_i\in {\rm TC}(A)$; 

\no (iii) Rk$(x_{i+1})<$ Rk$(x_i)$ each $i<n$. 

\leftskip 0in 

We let $E_A$ consist of all pairs 
\[\{\langle A_1, A_2, ..., A_n\rangle, 
\langle A_1, A_2, ..., A_n, A_{n+1}\rangle\},\] 
where $\langle A_1, ..., A_n, A_{n+1}\rangle\in V_A$. 
We define a prime labeling 
\[f_A: V_A\cup E_A\rightarrow \P\] as follows:- 
\[f(\langle A_1,...,A_n\rangle)=q_m\] 
if Rk$(A_n)=0$ and $A_n$ is the natural number $m$; 
\[f(\langle A_1,...,A_n\rangle)=p_\beta\] 
if Rk$(A_n)=\beta>0$; 
\[f(\{\langle A_1, A_2, ..., A_n\rangle, 
\langle A_1, A_2, ..., A_n, A_{n+1}\rangle\})=\hat{q}_{\gamma, \beta}\] 
if Rk$(A_n)=\beta$, Rk$(A_{n+1})=\gamma$, and $A_{n+1}\in A_n$; 
\[f(\{\langle A_1, A_2, ..., A_n\rangle, 
\langle A_1, A_2, ..., A_n, A_{n+1}\rangle\})=\bar{p}_{\gamma, \beta}\] 
if Rk$(A_n)=\beta$, Rk$(A_{n+1})=\gamma$, and $A_{n+1}\notin A_n$. 

\end{definition} 

Thus $(V_A, E_A, f_A)$ is an eplag
%\footnote{There is a formal difficulty here. 
%Literally speaking, we may have failed the requirement that $V_A$ and $E_A$ be 
%disjoint, since the usual Kuratowski device for explicating the pairing function 
%could well put say $\langle A_1, A_2\rangle\in A$ for $A_1, A_2\in A$. I ask that 
%the reader work with some definition of the pairing function which will ensure 
%$\langle A_1, A_2, ..., A_n\rangle\notin \p^\alpha(\N)$ for any 
%$A_1, A_2,...A_n\in\p^\alpha(\N)$.} 
for any $A\in \p^{\alpha+1}(\N)$; and from this 
eplag we can pass to the corresponding group. 



\begin{definition} For any $A\in \p^{\alpha+1}(\N)$ we let 
\[\g_A=\g(V_A, E_A, f_A),\] 
as defined in the last section. 
\end{definition} 

\begin{definition} For any $A\in \p^{\alpha+1}(\N)$ 
and $\beta<\alpha$ we 
define the notions of $\beta$-good and a corresponding 
$\beta^{\rm th}$ evaluation function $\pi_{\beta}$ by 
a simultaneous induction. 

We say that $g\in \g_A$ is {\it 0-good} if for some $m\in\N$ $g$ is 
divisible in $\g_A$ by all powers of $q_m$; we then let 
\[\pi_{0}(g)=m;\] 
note that by construction there is at most one such 
$m$, and hence $\pi_0(g)$ is well defined for $g$ 0-good. 
For $\beta>0$ we say that $g$ is $\beta$-good if it is divisible by all powers 
of $p_\beta$ and for all $\gamma<\beta$ and all 
$\gamma$-good $h$ we have either 

\leftskip 0.4in 

\no (a) there is a $\gamma$-good $h'$ with 
\[\pi_{\gamma}(h)=\pi_{\gamma}(h')\] 
and $g+h'$ divisible by all powers of $\hat{q}_{\gamma, \beta}$, or 

\no (b) there is a $\gamma$-good $h'$ with 
\[\pi_{\gamma}(h)=\pi_{\gamma}(h')\] 
and $g+h'$ divisible by all powers of $\bar{p}_{\gamma, \beta}$. 

\leftskip 0in 

We then let $\pi_{\beta}(g)$ be the set of all $\pi_{\gamma}(h)$ such that 
$\gamma<\beta$, $h$ is $\gamma$-good, and $g+h$ is divisible by all 
powers of $\hat{q}_{\gamma, \beta}$. 

\end{definition} 

Literally of course all these definitions should be made with explicit reference to 
$A$. We should define $\beta$-good {\it in $\g_A$} and we should write something like 
$\pi_{\g_A,\gamma}$ to show the dependence of the evaluation map on the group $\g_A$. 

In practice the intention will be clear. 


\begin{lemma} 
\label{2.6} 

(a) Suppose 
\[g=\sum_{i\leq k} r_i\cdot v_i\in\g_A\] 
is $\beta$-good,  
where each $r_i\in \Q$, $r_i\neq 0$, $v_i\neq v_j$ for $i\neq j$, each 
\[v_i=\langle A_1^i, A_2^i,..., A_{\ell(i)}^i\rangle.\] 
Then for all $i, j\leq k$ 
\[A^i_{\ell(i)}=A^j_{\ell(j)},\] 
and 
\[{\rm Rk}(A^i_{\ell(i)})=\beta,\] 
and for $A^*$ the common value of the $A^i_{\ell(i)}$ we have 
\[\pi_{\beta}(g)=A^*.\] 

(b) If $\langle A_1, A_2, ..., A_\ell\rangle \in V_A$ with {\rm Rk}$(A_\ell)=\beta$, 
then $\langle A_1, A_2,..., A_\ell\rangle$ is $\beta$-good and 
\[\pi_{\beta}(\langle A_1,...,A_\ell\rangle)=A_\ell.\] 

\end{lemma} 

\begin{proof} We prove these by simultaneous induction. 
The base case $\beta=0$ follows quickly from the definitions and 2.5. 
So let us assume instead that $\beta>0$ and that the 
lemma is established for all $\gamma<\beta$. 

First suppose that 
\[g=\sum_{i\leq k} r_i\cdot v_i\in \g_A\] 
is $\beta$-good, each $r_i$ a non-zero rational, 
each 
\[v_i=\langle A_1^i, ..., A^i_{\ell(i)}\rangle,\] 
with $v_i\neq v_j$ for $i\neq j$, 
and let us assume for a contradiction that 
\[\hat{A}\in A^0_{\ell(0)}\setminus A^1_{\ell(1)}.\] 
It follows from the definition of goodness that each 
\[\langle A_0^i,..., A_{\ell(i)}^i\rangle\] 
is divisible by all powers of $p_\beta$, and hence, by 
2.5, at each $i$ we have 
Rk$(A^i_{\ell(i)})=\beta$. 

Thus $\hat{A}$ must have Rk$(\hat{A})=\gamma$, some $\gamma<\beta$. 
And then by the inductive assumption 
\[\langle \hat{A}\rangle\] 
is $\gamma$-good with 
\[\pi_{\gamma}(\langle \hat{A}\rangle)=\hat{A}.\] 
Then by the definition of 
$\beta$-goodness of $g$ there is some $\gamma$-good $h$ with 
\[\pi_{\gamma}(h)=\hat{A}\] 
and $g+h$ either divisible by every power of $\hat{q}_{\gamma, \beta}$ 
or divisible by every power of $\bar{p}_{\gamma, \beta}$. 
Assume for simplicity that it is divisible by every power of 
$\hat{q}_{\gamma, \beta}$; the other case is similar. 
We can write 
\[h=\sum_{i\leq k'}s_i\cdot w_i,\] 
each $w_i\in V_A$, $s_i$ a non-zero rational, $w_i\neq w_j$ for $i\neq j$. 
Then by inductive assumption applied to the $\gamma$-goodness of $h$ we 
have each $w_i$ of the form 
\[w_i=\langle B_1^i, B_2^i,..., B_{\ell'(i)}^i, \hat{A}\rangle.\] 

At this point we can define 
\[\rho: V_A\rightarrow \{-1, 0, 1\}\] 
by 
\[\rho(\langle A^1_0,..., A^1_{\ell(1)}\rangle)=1,\] 
and for any $B\in A^1_{\ell(1)}$ 
\[\rho(\langle A^1_0,..., A^1_{\ell(1)}, B\rangle)=-1,\] 
but 
\[\rho(v)=0\] 
for all other $v\in V_A$. 
Then $\varphi_\rho$ defined by 
\[\sum q_v\cdot v\mapsto \sum q_v \rho(v)\] 
provides a $\hat{q}_{\gamma, \beta}$-mindful 
homomorphism which assumes the 
value 
\[\varphi_\rho(g+h)=r_1\neq 0,\] 
contradicting proposition 2.5's criteria for infinite 
$\hat{q}_{\gamma,\beta}$ divisibility. 

To complete the inductive step we also need to note that (b) 
holds for any $\langle A_1,.., A_\ell\rangle \in V_A$ with 
Rk$(A_\ell)=\beta$. This follows routinely from the definition 
of $\beta$-good and the inductive assumption. 





\end{proof} 



\begin{corollary} 
\label{2.7} {\rm TC}$(A_1)\neq${\rm TC}$(A_2)$ implies $\g_{A_1}\not\cong \g_{A_2}$. 
\end{corollary} 

\begin{proof} Since 
\[\{\pi_{\beta}(g): g\in\g_{A_1}, g {\rm \: is\:} \beta-{\rm good}, 
\beta\leq \alpha\}={\rm TC}(A_1),\]  
\[\{\pi_{\beta}(g): g\in\g_{A_2}, g {\rm \: is\:} \beta-{\rm good}, 
\beta\leq \alpha\}={\rm TC}(A_2),\] 
and for any group $G$ the set 
\[\{\pi_\beta(g): g\in G, g {\rm \: is\:} \beta-{\rm good}, 
\beta\leq \alpha\}\] 
is an invariant of the isomorphism type of $G$. 

\end{proof} 

Now for any $A\in \p^\alpha(\N)$ we can define 
\[\h_A=\g_{\{A\}\cup{\rm TC}(A)}\] 
to obtain an assignment 
\[\p^\alpha(\N)\hookrightarrow {\rm TFA}/\cong\] 
\[A\mapsto \h_A\]
which injects $\p^\alpha(\N)$ 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^\alpha(\N)|\leq 2^{\aleph_0}$. The important point is that this injection 
is, in the sense made precise shortly, {\it reasonably definable}. 



\section{Coding} 

We recall a method of coding elements of $\p^\alpha(\N)$ by 
equivalence classes in a Polish space. 


\begin{definition} 
Following \cite{hjkelo} we let $\l(\alpha)$ be the language 
generated by unary relation 
$(R_\beta)_{\beta\leq \alpha}$, 
binary relations $\epsilon, E, F$, and constant 
symbols $v_0, (r_n)_{n\in\N}$. We let $X_{\l(\alpha)}$ be the Polish space of 
$\l(\alpha)$ structures equipped with the usual topology generated by 
quantifier free formulas. 
We then let $P^\alpha$ be the subspace consisting of structures 
\[\m=\langle \N; r_0, r_1,..., v_0, \epsilon, E, F, R_0, R_1,..., R_\beta,...R_\alpha\rangle,\] 
where:- 

(i) $\N$ is partitioned by the relations $(R_\beta)_{\beta\leq\alpha}$; the constant terms 
$(r_n)_{n\in\N}$ enumerate $R_0$ without repetitions; $R_\alpha=\{v_0\}$; 

(ii) $E$ is an irreflexive symmetric relation on $\N\setminus R_0$; 

(iii) $E$ provides a tree structure on $\N\setminus 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\rightarrow 
\N\setminus 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_\gamma(x)$ holds exactly when $x$ has rank $\gamma$ 
in this tree; in particular, $v_0$ has rank $\alpha$; 

(iv) $F\subset R_0\times R_1$. 

With this all in place we can assign an evaluation 
\[\nh x\nh\] 
to each $x\in \N$, with 
\[\nh x\nh =n\] 
if $x\in R_0$ and $x=r_n$, 
while 
\[\nh x\nh =\{n\in\N: F(r_n, x)\}\] 
for $x\in R_1$ (and hence $x$ terminal in the tree structure on $\N\setminus R_0$); 
and 
\[\nh x\nh =\{\nh y\nh : {\rm the \: shortest \: path \: from \:} v_0 
{\rm \: to \: } y {\rm \: passes\: through \:} x\}.\] 

(v) We require that $\epsilon$ satisfy 
\[x\epsilon y \Leftrightarrow \nh x\nh \in \nh y\nh.\] 

With all this in place we can finally define 
\[\nh \m\nh =\nh v_0\nh.\] 
\end{definition} 

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 $\nh x\nh^\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^\alpha(\N)$ 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\in\p^\alpha(\N)$ and some representative 
of $B_1$ appears below a representative of $B_2$ if and only if $B_1\in B_2$; we 
deliberately allow that a given $B\in$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_\gamma$'s 
layer $\m$ into sediments based on the rank of the represented sets. 


The $\epsilon$ relation comes along for free, simply recapitulating the relation $\nh y\nh\in \nh x\nh$. 
I leave it only because it appeared in \cite{hjkelo}. 

Following 1.2-1.5 of 
\cite{hjkelo} we have that $P^\alpha$ is a Borel subset of $X_{\l(\alpha)}$, and hence a standard 
Borel set in its own right, and that 
\[\{\nh \m\nh : \m\in P^\alpha\}=\p^\alpha(\N),\] 
and that the set of 
\[(x, y, \m)\in \N\times\N\times P^\alpha\] such that 
\[\nh x\nh =\nh y\nh \] (calculated 
from the point of view of $\m$) is Borel as a subset of $\N\times\N\times X_{\l(\alpha)}$. 
If we let $\cong_\alpha$ be the isomorphism relation on elements of $P^\alpha$ then we 
have for all $\m,\n\in P^\alpha$ that 
\[\m\cong \n\Leftrightarrow \nh\m\nh=\nh\n\nh.\] 

\begin{definition} For each $\m\in P^\alpha$ let $S_0(\m)$ be the set of $x\in\N$ such that 
for all smaller natural numbers $y\in\N$ we have $\nh x\nh\neq \nh y\nh$. 
\end{definition} 

Thus $(\nh x\nh)_{x\in S_0(\m)}$ enumerates without repetitions the 
set $\{\nh \m\nh\}\cup$TC$(\nh\m\nh)$. From the above remarks we have that 
\[\{(x, \m)\in \N\times P^\alpha: x\in S_0(\m)\}\] 
is Borel as a subset of $\N\times X_{\l(\alpha)}$. 

\begin{definition} Let 
\[\pi: \N^{<\N}\hookrightarrow \N\] 
be the usual G\"{o}del pairing function, providing a bijection between $\N^{<\N}$ 
and $\N$. Then for $\m\in P^\alpha$ we let 
\[S_1(\m)=\{\pi(x_1, x_2,..., x_n): {\rm each \:} x_i\in S_0(\m), {\rm \: and \: for \:} 
i<n {\rm \: we \: have \:} {\rm Rk}(\nh x_i\nh ) > {\rm Rk}(\nh x_{i+1}\nh )\}.\] 
\end{definition} 

Again the set of 
\[\{(a, \m)\in \N\times P^\alpha: a\in S_1(\m)\}\] 
is Borel as are 
\[\{(\pi(x_1, ..., x_n), \pi(x_1, ..., x_n, x_{n+1}), \m)\in N\times\N\times \P^\alpha:\]
\[\pi(x_1, ..., x_n), \pi(x_1, ..., x_n, x_{n+1})\in\m,
\nh x_{n+1}\nh\in \nh x_n\nh \}\] 
and 
\[\{(\pi(x_1, ..., x_n), \pi(x_1, ..., x_n, x_{n+1}), \m)\in \N\times\N\times \P^\alpha:\]
\[\pi(x_1, ..., x_n), \pi(x_1, ..., x_n, x_{n+1})\in\m,
\nh x_{n+1}\nh\notin \nh x_n\nh \}.\] 
And clearly from the definition of $P^\alpha$ we have that for each $\beta\leq \alpha$ 
that the set of 
\[\{(\pi(x_1, ..., x_n), \m)\in \N\times P^\alpha: \pi(x_1, ..., x_n)\in S_1(\m), 
{\rm Rk}(\nh x_n \nh)=\beta\}\] 
is Borel for any $\beta\leq \alpha$. 

And thus all the sets of the form 
\[\{(p, a, \m): a\in S_1(\m), a=\pi(x_1,..., x_n) {\rm \: some\:} n, x_1,...,x_n,\] 
\[{\rm with \: Rk}(\nh x_n\nh )=\beta, {\rm \: some \:}  
p_\beta=p\},\] 
\bigskip 

\[\{(p, a, \m): a\in S_1(\m), a=\pi(x_1,..., x_n) {\rm \: some\:} n, x_1,...,x_n,\]
\[{\rm with \: Rk}(\nh x_n\nh )=0, \nh x\nh =m, q_m=p\},\] 
\bigskip 
\[\{(p, a,b, \m): a,b\in S_1(\m), a=\pi(x_1,..., x_n), 
b=\pi(x_1,..., x_n, x_{n+1})\] 
\[{\rm \: some\:} n, x_1,...,x_n, x_{n+1},
{\rm with \: Rk}(\nh x_n\nh )=\beta, 
{\rm with \: Rk}(\nh x_{n+1}\nh )=\gamma, \] 
\[{\rm \: and \: with \:} \nh x_{n+1}\nh \in \nh x_n\nh, 
\hat{q}_{\gamma, \beta}=p\},\] 
\bigskip 
and 
\bigskip 
\[\{(p, a,b, \m): a,b\in S_1(\m), a=\pi(x_1,..., x_n), 
b=\pi(x_1,..., x_n, x_{n+1})\]
\[ {\rm \: some\:} n, x_1,...,x_n, x_{n+1}, 
{\rm with \: Rk}(\nh x_n\nh )=\beta, 
{\rm\: with \: Rk}(\nh x_{n+1}\nh )=\gamma, \] 
\[{\rm \: and \: with \:} \nh x_{n+1}\nh \notin \nh x_n\nh, 
\bar{p}_{\gamma, \beta}=p\},\] 
are Borel. 

Thus it follows that the set $M$ of all sequences 
\[(\m, (r_1, a_1), (r_2,a_2),...,(r_\ell, a_\ell))\in P^\alpha\times (\Q\times\N)^{<\N}\] 
such that 

\leftskip 0.4in 

\no (i) $(a_1, a_2,..., a_\ell)$ is a strictly increasing sequence of integers; 

\no (ii) each $a_i=\pi(x^i_1, ..., x^i_{N(i)})$ some $N(i), x_1^i, ..., x^i_{N(i)}\in\N$, 

\no (iii) $\sum_{i\leq \ell} r_i\cdot \langle \nh x_1^i\nh , \nh x_2^i\nh,..., \nh x^i_{N(i)}\nh \rangle 
\in \g_{\{\nh \m\nh\}\cup{\rm TC}(\nh \m\nh)}$ 

\leftskip 0in 

\no is Borel. Moreover we obtain then that the induced group structure on the fibers gives rise to 
a Borel subset of $M\times M\times M$, in the sense that the set of all 
\[(\m, (a_1, r_1),..., (a_\ell, r_\ell), (b_1, s_1),..., (b_k, s_k), 
(c_1, t_1),..., (c_m, t_m))\] 
such that 

\leftskip 0.4in 

\no (i) $(\m,  (a_1, r_1),..., (a_\ell, r_\ell))$, $(\m, (b_1, s_1),..., (b_k, s_k)), 
(\m, (c_1, t_1),..., (c_m, t_m))$ are in $M$, 

\no (ii) each 
\[a_i=\pi(x^i_1, ..., x^i_{N(i)})\] some $N(i), x_1^i, ..., x^i_{N(i)}\in\N$, 
each 
\[b_i=\pi(y^i_1, ..., y^i_{M(i)})\] 
some $M(i), y_1^i, ..., y^i_{M(i)}\in\N$, 
each 
\[c_i=\pi(z^i_1, ..., z^i_{L(i)})\] 
some $L(i), y_1^i, ..., y^i_{L(i)}\in\N$. and 




\no (iii) 
\[\sum_{i\leq \ell} r_i\cdot \langle \nh x_1^i\nh , \nh x_2^i\nh,..., \nh x^i_{N(i)}\nh \rangle + 
\sum_{i\leq k} s_i\cdot \langle \nh y_1^i\nh , \nh y_2^i\nh,..., \nh y^i_{M(i)}\nh \rangle 
=
\sum_{i\leq m} t_i\cdot \langle \nh z_1^i\nh , \nh z_2^i\nh,..., \nh z^i_{L(i)}\nh \rangle\] 
in $ \g_{\{\nh \m\nh\}\cup{\rm TC}(\nh \m\nh)}$, 

\leftskip 0in 

\no is Borel. 



Let $Y$ denote the space $(\Q\times\N)^{<\N}$, in its usual Borel structure. $M$ is a Borel subset of 
$X_{\l(\alpha)}\times Y$ with countable sections. Thus\footnote{See 18.10 \cite{kechris} for 
a proof of this classical theorem; indeed, \cite{kechris} is probably the 
right reference for all the descriptive set theory used here.} 
we can produce a countable sequence of 
Borel functions $(f_n)_{n\in\N}$, each 
\[f_n: P^\alpha\rightarrow Y,\] 
such that for any $\m\in P^\alpha $ 
\[(f_n(\m))_{n\in\N}\] 
enumerates without repetition the set of $y\in Y$ such that 
\[(\m, y)\in M.\] 
Thus, again using the uniformization theorem for Borel subsets of the plane with countable 
sections, we may find a Borel function 
\[\theta: P^\alpha\rightarrow \N^{\N\times \N}\] 
such that for all $\m\in P^\alpha$ and $\ell, m, n\in\N$ 
\[f_\ell(\m)+f_m(\m)=f_n(\m)\] 
if and only if 
\[(\theta(\m))(\ell, m)=n;\] 
and thus $\theta(\m)$ provides an abelian group structure on $\N$ isomorphic 
to $ \g_{\{\nh \m\nh\}\cup{\rm TC}(\nh \m\nh)}$. 

\newpage 

\section{So what?} 

\begin{definition} Let TFA be the set of all 
\[G: \N\times\N\rightarrow \N\] 
which provide an torsion free abelian on the natural numbers. 
We let $\cong|_{\rm TFA}$ be the isomorphism relation on TFA, so that 
\[G_1\cong|_{\rm TFA} G_2\] 
if and only if there is some permutation $\psi$ of the natural numbers such that 
for all $m, n\in\N$ 
\[\psi(G_1(m,n))=G_2(\psi(m), \psi(n)).\]  
\end{definition} 

If we equip $\N^{\N\times\N}$ with the usual product topological structure 
then 
TFA becomes a Borel set. The last section showed that for all $\alpha<\omega_1$ 
\[\cong_\alpha\leq_B \cong\!|_{\rm TFA}.\] 
Thus by 

\begin{theorem} (Harrington) There is no Borel equivalence relation $E$ with 
\[\cong_\alpha\leq_B E\] 
all $\alpha<\omega_1$. (See \cite{hjkelo} 5.11 for a proof.) 
\end{theorem} 

\no we have therefore that $\cong\!|_{\rm TFA}$ non-Borel. 

Harrington's argument can be used to show that there is no Borel $E$ with each 
$\cong_\alpha$ {\it absolutely $\Ubf{\Delta}^1_2$ reducible}\footnote{In the sense of 
$\S$9.1 of \cite{classification}} reducible to $E$, and thus we obtain under very 
general notions of reducibility that not only is $\cong_{\rm TFA}$ not Borel but 
it is not even reducible to any Borel equivalence relation. 

It is known, as found for instance in \cite{friedman}, that if $C $ is a Borel class of 
countable structures with $\cong\!|_C $ Borel, then there is some $\alpha<\omega_1$ with 
\[\cong\!|_C\leq_B \cong_\alpha.\] 
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 
\cite{friedmanstanley} showed that there is no absolutely $\Ubf{\Delta}^1_2$ 
assignment of elements of 
\[2^{<\omega_1}\] 
as complete invariants for elements of $P^2$ up to $\cong_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 \cite{melles} on the basis of very different reasoning. 

And we may continue in this fashion. Similar arguments show that $\cong_3$ is not 
absolutely $\Ubf{\Delta}^1_2$ reducible to $\p_{\aleph_0}(2^{<\omega_1})$, the set of 
countable subsets of $2^{<\omega_1}$, and thus that the torsion free abelian groups 
cannot be assigned elements of $\p_{\aleph_0}(2^{<\omega_1})$ as complete invariants. 

And so on. 




\newpage 

\begin{thebibliography}{99} 

\bibitem{friedman} H. Friedman, {\it Borel and Baire reducibility,} 
preprint, 1999. 

\bibitem{friedmanstanley} H. Friedman, L. Stanley, {\it A Borel 
reducibility theory for classes of countable structures,} 
{\bf Journal of Symbolic Logic,} vol. 54(1989), 899-914. 

\bibitem{TFA} G. Hjorth, {\it Around nonclassifiability for 
countable torsion free abelian groups,} in {\bf Proceedings of the modules and 
abelian groups conference in Dublin,} 
Trends in Mathematics, Birkh\"{a}user Verlag, Basel, 1999. 

\bibitem{classification} G. Hjorth, 
{\bf Classification and orbit equivalence relations,} 
AMS, Rhode Island, 2000. 


\bibitem{misery} G. Hjorth, 
{\it Invariants for measure preserving transformations,} 
{\bf Fundamenta Mathematicae,}  
vol. 169(2000), pp. 51-84. 

\bibitem{hjorthkechris} 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. 

\bibitem{hjkelo} G. Hjorth, A.S. Kechris, A. Louveau, 
{\it Borel equivalence  relations induced by actions of the 
symmetric group,} {\bf Annals of Pure and Applied Logic,} 
vol. 92(1998), pp. 63-112. 


\bibitem{kechris} A.S. Kechris, {\bf Classical descriptive set theory,} 
Springer-Verlag, New York, 1995. 

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





\end{thebibliography}

\leftskip 0.5in







greg@math.ucla.edu

\bigskip



MSB 6363

UCLA

CA 90095-1555

\leftskip 0in

\end{document}