= Solution
An isomorphism-invariant <Markov property of finitely presented groups> $\rho$ has two finitely presented witnesses: a group $A_+$ with $\rho$, and a group $A_-$ which cannot embed in any finitely presented group having $\rho$. In symbols,
$$
\boxed{A_+\text{ has }\rho,\qquad A_-\hookrightarrow B\Longrightarrow B\text{ does not have }\rho.}
$$
The second condition is an obstruction to embedding, stronger than merely saying that $A_-$ itself fails the property.
Let $U$ be a fixed finitely presented <group> with unsolvable <word problem for a group>. Form the finitely presented <free product> $P=U*A_-$. Given a word $w$ in the generators of $U$, apply part (a) to this $P$ and $w$, and output the finite presentation of
$$
B(w)=A_+*P(w).
$$
If $w=1$ in $U$, it is also $1$ in $P$, so $P(w)$ is trivial and $B(w)\cong A_+$ has $\rho$. If $w\ne1$ in $U$, its image stays nontrivial in the <free product> $P$, and $P$ embeds in $P(w)$. Therefore $A_-$ embeds in $B(w)$, which cannot have $\rho$. We have the effective equivalence
$$
\boxed{B(w)\text{ has }\rho\quad\Longleftrightarrow\quad w=1\text{ in }U.}
$$
An algorithm recognizing whether an arbitrary <finite group presentation> has $\rho$ would decide the unsolvable <word problem for a group> $U$. This contradiction proves the <Adian–Rabin theorem>: no <Markov property of finitely presented groups> is algorithmically decidable.
Back to article page
