Word problem for groups: Difference between revisions

Revision as of 00:31, 3 April 2024

Revision as of 00:57, 3 April 2024

Line 199:

The following has been proved by [[Bernhard Neumann]] and [[Angus Macintyre]]:

::A finitely presented group has solvable word problem if and only if it can be embedded in every [[algebraically closed group]].

What is remarkable about this is that the algebraically closed groups are so wild that none of them has a recursive presentation.

Line 205:

The oldest result relating algebraic structure to solvability of the word problem is Kuznetsov's theorem:

::A recursively presented simple group ''<math>S''</math> has solvable word problem.

To prove this let ⟨''<math>\langle X'' |'' R''⟩ \rangle</math> be a recursive presentation for ''<math>S''</math>. Choose ''a'' ∈nonidentity Selement such<math>a \in S</math>, that ''is, <math>a'' ≠\neq 1</math> in ''<math>S''</math>.

If ''<math>w''</math> is a word on the generators ''<math>X''</math> of ''<math>S''</math>, then let:

::<math>S_w = \langle X | R\cup \{w\} \rangle.</math>

Line 225:

::<math>g(w, x) = f_{\langle X | R\cup \{w\} \rangle}(x).</math>

Then because the construction of ''<math>f''</math> was uniform, this is a recursive function of two variables.

It follows that: {{tmath|1=h(w)=g(w, a)}} is recursive. By construction:

Line 235:

\end{cases}</math>

Since ''<math>S''</math> is a simple group, its only quotient groups are itself and the trivial group. Since ''<math>a'' ≠\neq 1</math> in ''<math>S''</math>, we see ''<math>a'' = 1</math> in ''S<submath>wS_w</submath>'' if and only if ''S<submath>wS_w</submath>'' is trivial if and only if ''<math>w'' ≠\neq 1</math> in ''<math>S''</math>. Therefore:

::<math>h(w) =

Line 243:

\end{cases}</math>

The existence of such a function is sufficient to prove the word problem is solvable for ''<math>S''</math>.

This proof does not prove the existence of a uniform algorithm for solving the word problem for this class of groups. The non-uniformity resides in choosing a non-trivial element of the simple group. There is no reason to suppose that there is a recursive function that maps a presentation of a simple groups to a non-trivial element of the group. However, in the case of a finitely presented group we know that not all the generators can be trivial (Any individual generator could be, of course). Using this fact it is possible to modify the proof to show: