% 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: n0$ 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 $i0$;
\[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 {\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}