The word problem for a given finitely generated group
is the problem of telling whether a word in the
generators represents the identity element. For any
finitely presented group, this problem has an easy
part: if the word is trivial, then it follows from
the given finitely many relations; hence it is possible
to algorithmically list all trivial words. Thus, in
a group with unsolvable word problem, it is impossible
to algorithmically list the non-trivial words.
For a finitely presented group, it is easy to list all
actions on finite sets: for a proposed action of the
generators, just check whether the relations hold. Hence,
one can algorithmically list all finite quotients of
a finitely presented group. This provides an obvious
way of listing some non-trivial words: put down
those, that represent a non-trivial element in some
finite quotient. A group where this algorithm eventually
finds each non-trivial word is called residually
finite. Residually finite groups have an obvious
solution to the word problem.
The conjugacy problem of telling which words represent
conjugate elements allows for a similar treatment.
In any finitely presented group, it is algorithmically
easy to list all pairs of words representing conjugate
elements. The hard part is to list the pairs of words
representing non-conjugate elements. A group is called
conjugacy separable, if any two non-conjugate elements
stay non-conjugate in some finite quotient. Thus,
finitely presented conjugacy separable groups admit
an obvious solution to the conjugacy problem.
Other classical algorithmic problems can be treated
analogously. Each leads to a corresponding notion of
separability. The problem of telling whether two
finitely generated subgroups are conjugate gives rise
to the notion of subgroup conjugacy separability.
A group is subgroup conjugacy separable if any two
non-conjugate finitely generated subgroups have
non-conjugate images in some finite quotient.
We show that finitely generated free groups and
fundamental groups of closed oriented surfaces are
subgroup conjugacy separable.