Let $F\_2$ denote the free group of rank 2. Does anybody have a fast proof that the subgroup membership problem is undecidable for $F\_2 \times F\_2$? I saw a really fast proof last semester that started with a group with undecidable word problem and used that group to construct subgroups of $F\_2 \times F\_2$, but I've lost my notes from the talk. I tried looking at the original proof from the 1960's but I couldn't get an English translation. Thanks!



showing the subgroup membership problem is undecidable for $F_2 \times F_2$
First, $F\_2 \times F\_2$ contains a copy of $F\_n \times F\_n$ for all $n \geq 1$, so it is enough to find such a group inside $F\_n \times F\_n$ for some $n$. Let $G$ be a finitely generated group with an unsolvable word problem and let $S$ be a generating set for $G$. Let $f : F(S) \times F(S) \rightarrow G \times G$ be the product of the natural projection $F(S) \rightarrow G$ with itself. Let $\Delta < G \times G$ be the diagonal subgroup, and define $H = f^{-1}(\Delta)$. Then $(x,y) \in H$ if and only if $x$ and $y$ define the same element of $G$, so it is clear that you can't solve the membership problem for $H$.


EDIT : If $G$ has a finite presentation with relations $R$, then $H$ is actually finitely generated. Indeed, I claim that $H$ is generated by the union of the sets $\{(x,x) | x \in S\}$ and $\{(r,1) | r \in R\}$ and $\{(1,r) | r \in R\}$. The only potential problem with this is that $R$ only normally generates the kernel of the projection $F(S) \rightarrow G$. However, observe that for $w \in F(S)$ and $r \in R$, the element $(wrw^{-1},1) = (w,w)(r,1)(w^{-1},w^{-1})$ is in the subgroup generated by the purported generating set, and similarly for $(r,wrw^{-1})$.


