Normal closure of a finite set

Question

I am studying a proof that states that in every finitely presented residually finite group $G=\langle X \mid R \rangle $ the word problem is solvable.

At some point it states that we can enumerate all words equal to $1$ in $G$ (that means we can enumerate all words for the normal closure of $R$ in $F(X)$.) Why is this possible?

The normal closure is the kernel of $\nu : F(X) \to G$ but I don't see why this should be finite.

Answer 1

It certainly isn't finite! But it is enumerable. That is, possibly countable, but with the bonus property that some computer program can tell you if any given word is in the list.

For instance, the even natural numbers are enumerable, as witnessed by the following program

def isEven(n):
  return n % 2 == 0

Similarly, you can check if a given word is in the normal closure of $R$. How? Well every element of the normal closure is a finite product of conjugates of elements of $R$. We can enumerate all the elements of $G$ by looking at words in the generators $X$, and then we can enumerate all the conjugates of words in $R$ since there's finitely many, and then we can enumerate all the finitely many products of conjugates too.

You have to be a bit careful to make sure you actually hit everything, but it's doable with standard tricks. Here's the idea:

i = 0
while(true):
  ws = [all tuples of length <= i from R] # note there's finitely many
  gs = [all tuples of length <= i from X] # note there's finitely many
  for (r1,...,rn) in ws:
    for g1 ... gn in gs: 
      print(r1^g1 r2^g2 ... rn^gn)
  i += 1

The "residually finite" condition tells you how to check that a given element doesn't appear on this list. But I'm not entirely sure how right now.

---

I hope this helps ^_^