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.)