Let $G, H$ be finitely presented groups with decidable word problems.
Can there be a homomorphism $f:G\to H$ such that there is no algorithm deciding given $w\in H$ whether $f^{-1}(w)$ is empty or not?
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ Yes: take $G=\{1\}$ and $H$ to be a f.p. group with non-solvable word problem. (I assume the input is a word in a free group above $H$, otherwise the question doesn't make sense, unless $H$ is assumed to have solvable word problem.) $\endgroup$– YCorCommented Apr 21, 2021 at 16:42
-
2$\begingroup$ @YCor thank you the question is corrected $\endgroup$– user178109Commented Apr 21, 2021 at 16:45
-
4$\begingroup$ Now it's assumed that $H$ has solvable word problem. Then every homomorphism is computable (and determined by the image of generators) if I'm correct. So the question is to find a f.p. group $H$ and a f.g. subgroup of $H$ with non-solvable membership problem. This exists with $H=F_2\times F_2$. Namely take $F_2\to Q$ homomorphism onto a f.p. group with non-solvable word problem, and $\mathrm{Im}(f)$ to be $\{(x,y)\in F_2\times F_2:f(x)=f(y)\}$. $\endgroup$– YCorCommented Apr 21, 2021 at 16:47
-
1$\begingroup$ Perhaps a definition of computable homomorphism is needed since inputs and outputs should belong to appropriate says for doing such things. Do you mean that the finite presentation is fixed and you want an algorithm which gives you a word representing an element of the image? In that case, as @YCor poined or the function is automatically computable since sums Turing machine knows a word representing the image of each generator and hence can compute a word representing the image of every element. $\endgroup$– Benjamin SteinbergCommented Apr 21, 2021 at 17:25
-
1$\begingroup$ In any case the generalized word problem as @YCor points out is a special case of your problem since if H has decidable word problem and K is any finitely generated subgroup you can choose G a finitely generated free group on a generating set for K and map it onto K in the obvious way. Then the membership problem for K is equivalent to your problem for the map from G to K viewed as a map to H. $\endgroup$– Benjamin SteinbergCommented Apr 21, 2021 at 17:28
|
Show 1 more comment