How many recursively definable groups are there on $\mathbb{N}$?

74 Views Asked by At

How many non-isomorphic, (non-free), non-trivial, recursively definable groups are there on $\mathbb{N}$? I know we can at least get 1. Let $F:\mathbb{N} \to \mathbb{Z}$ be the "natural bijection". By this, I mean: $$F(0)=0$$ Now, if $n$ is even: $$F(n)=\frac{n}{2}$$ And if $n$ odd: $$F(n)=-\frac{n+1}{2}$$ Consider $(\mathbb{N}, \triangle)$ where we $n \triangle m=F^{-1}(F(n)+F(m))$. Note that $(\mathbb{N},\triangle)\cong (\mathbb{Z},+)$ as group structures.

Note also, since we are working with recursively definable groups, there is no more that $\aleph_0$ many. So, I know that there is at least one and at most countably many.

2

There are 2 best solutions below

8
On BEST ANSWER

For any integer $n$, take the direct sum of $\mathbb{Z}_n$ and countably many copies of $\mathbb{Z_2}$.

We can find an explicit injection by looking at integers of the form $$2^kp_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\cdots,$$ ("infinite" product), where $0\le k\le n-1$, the $p_i$ are the odd primes, and $e_i=0$ or $e_i=1$ for all $i$, with only finitely many of the $e_i$ equal to $1$. The addition is defined in the natural way. To get a recursive bijection with the natural numbers, map the $m$-th integer of the type described above to $m$.

0
On

Even easier than the free group comment.

Pick $n\in\mathbb N, n>1$. For each $k\in\mathbb N$, write $k$ in base $n$, yielding an infinite sequence of digits from $0$ to $p-1$. Treat this as an element of $\mathbb Z/p\mathbb Z$. Add two numbers by the same algorithm you'd normally add by, but don't carry the ones.

Then you get groups of the form: $\bigoplus_{i\in\mathbb N} \mathbb Z/\mathbb nZ$.

For different $n$, this yields non-isomorphic groups because in each group, since there are elements of degree $n$ and no elements of any higher degree.