So, I am not entirely sure what belongs in here so I thought I would share a very elegant proof I came across recently, due to one K.A. Mihailova, from 1958.

Background: Let $\displaystyle G=\langle X; R\rangle$ be a group given in terms of generators and relations. It is a natural question to ask, given two words $\displaystyle U(X)$ and $\displaystyle V(X)$,

$\displaystyle \textnormal{is }U\equiv V \text{ mod }R \textnormal{ ?}$

Unfortunately, this is a question which is insoluble in general: it is called the word problem for groups (note that this is equivalent to asking "$\displaystyle \textnormal{is }U(X)\equiv 1 \text{ mod }R\text{?}$").

For more details, and examples, see wiki. Note that some of the examples there are finitely presented.

This is a driving question in group theory: Hyperbolic groups, probably the most studied class of groups of today, were defined so as to have soluble word (and conjugacy) problem*.

However, Free groups are nice. A word is freely equal to the trivial word if and only if it is the trivial word after freely reducing it. Free reduction is a finite process, so we have an algorithm to determine if a word is the trivial word or not. Similarly, two words are conjugate if and only if, after cyclically reducing them, they are cyclic shifts of one another. Finally, two free groups are isomorphic if and only if they are of the same rank - they are generated by the same number of elements. In fact, it is a theorem that every question you could want to know about free groups can be answered.

That said, the direct product of two free groups is not nice. This is counter-intuitive: free groups are nice, and so (surely) is the direct product! So presumably the direct product of two free groups is nice, no?

Question: For all $\displaystyle H\leq F_2\times F_2$ finitely generated does there exist an algorithm to determine,

$\displaystyle \textnormal{given }h \in F_2\times F_2\textnormal{ is }h \in H\text{?}$

Answer: No.

Solution: Firstly, note that $\displaystyle F_2\times F_2$ contains a copy of $\displaystyle F_n\times F_n$ for all $\displaystyle n\in\mathbb{N}\cup\{\infty\}$. This is because $\displaystyle F_n\leq F_2$ (which is well-known). So it is enough to prove the result for $\displaystyle F_n\times F_n$ for some $\displaystyle n\in \mathbb{N}$.

So, let $\displaystyle G=\langle X; R\rangle$ be a finitely presented group with insoluble word problem. Let $\displaystyle \phi: F(X) \times F(X)\rightarrow G\times G$ in the natural way. Let $\displaystyle \Delta = \{(g, g): g\in G\}$ be the diagonal subgroup and let $\displaystyle H=\Delta\phi^{-1}$, the pre-image of $\displaystyle \Delta$ under $\displaystyle \phi$. It is clearly a subgroup of $\displaystyle F(X) \times F(X)$. Then,

$\displaystyle (g, h) \in H \Longleftrightarrow g=h \textnormal{ in }G$.

However, as $\displaystyle G$ has insoluble word problem you cannot solve the membership problem for $\displaystyle H$.

That is the elegant bit of the proof over. One now has to prove that $\displaystyle H$ is finitely generated, which comes from the fact that $\displaystyle G$ is finitely presented. It is sufficient to show that,

$\displaystyle H=\langle (x, x), (1, r), (r, 1): x\in X, r \in R\rangle$

(where $\displaystyle G=\langle X; R\rangle$) which I shall leave as an exercise (it isn't too hard). Alternatively, you can find all this here.

The key point to take away is this: the direct product isn't nice...

*Basically, Gromov took an old algorithm, called Dehn's algorithm, which solved these two problems and found the most general class of groups which it would work for.