Ineffective Theory

Mutual Subgroups

Two groups can be proper subgroups of each other. Of course, they can’t be finite groups, but that’s alright.

A good place to start is with the free group on $n$ generators, which I’ll call $F^n$ (nonstandard notation, but fine when $n$ is finite). The free group $F^1$ is isomorphic to the integers under addition, so it isn’t very interesting. Let’s look at $F^2 = \langle x,y\rangle$ and $F^4 = \langle a,b,c,d\rangle$. It is obvious that $F^2 < F^4$. Of course there are multiple such inclusions, but the 12 most natural ones are $(x,y)\mapsto(a,b)$ and the like.

Now let’s construct an injection from $F^4$ to $F^2$, demonstrating that $F^4 < F^2$. A tempting guess is \begin{equation*} \phi : \left\{\begin{matrix} a \mapsto xx\\
b \mapsto xy\\
c \mapsto yy\\
d \mapsto yx\\
\end{matrix}\right.\text. \end{equation*} Alas! This is indeed a group homomorphism, but it is not injective: you can verify that $\phi(b c^{-1} d a^{-1}) = 1$. A more robust encoding scheme (again, far from unique) is given by \begin{equation*} \phi : \left\{\begin{matrix} a \mapsto x^0yx^{-0}\\
b \mapsto x^1yx^{-1}\\
c \mapsto x^2yx^{-2}\\
d \mapsto x^3yx^{-3}\\
\end{matrix}\right.\text. \end{equation*} (To see that this is injective, just think about how you would write a program to “decode” the string in $F^2$.)

Are $F^2$ and $F^4$ isomorphic? No. I like the proof that comes from looking at $\mathrm{Hom}(F^n, \mathbb Z / \mathbb Z_2)$ — that is, the set of all group homomorphisms from $F^n$ to the group with two elements. There are of course $2^n$ such homomorphisms, and that suffices to show that the structure of $F^n$ depends on $n$.

In conclusion: $F^2 < F^4$, $F^4 < F^2$, but $F^2 \not\approx F^4$.

It should be clear that none of this really depends on which free groups were chosen, as long as neither is $F^1$. In fact, we also have the glorious result $F^2 < F^2$ (and the same for any $F^n$ with $n \ge 2$). This is demonstrated by $(x,y)\mapsto(xx,yy)$. ($F^1 < F^1$ is easy to show as well.)