The word problem for groups preceded PH Theorem as a practical undecidability result

Question

The Paris-Harrington theorem is often cited as the first practical instance of an undecidable problem since it doesn't depend on self-reference or diagonalization and is an interesting mathematical question in its own right. But why isn't the unsolvability of the word problem on groups considered for that distinction? It came two decades before PH theorem. Am I misunderstanding some subtle difference between the two ideas? Or is PH overshadowing the unsolvability for the word problem on groups in the history of undecidability logic?

Answer 1

You're conflating undecidability in the proof-theoretic sense (= independence) with undecidability in the algorithmic sense (= incomputability). These are related but distinct notions. The relationship between the two is discussed at some length at MathOverflow. Note that there is further terminological "bleed" between the two topics - e.g. "diagonalization" a la the unsolvability of the Halting Problem or a la the diagonal lemma - so one has to be careful.

Here are two important notes:

• Independence is always relative to a background theory, while incomputability is absolute. Strictly speaking, we shouldn't say for example that the Godel(-Rosser) sentence is independent - rather, the GR-sentence of an appropriate theory $T$ is independent of that same theory $T$.

  • OK fine, in some - usually older - logic papers and books you will find the phrase "absolutely undecidable" or similar. But this refers to the fundamentally vague notion of "independent of any 'reasonable' base theory" (what does 'reasonable' mean exactly?), and moreover seems to have fallen out of favor.

• Incomputability does yield instances of independence! Knowing that there is a finitely presented group $G=\langle A\vert R\rangle$ with incomputable word problem tells us (for instance) that if $\mathsf{ZFC}$ is arithmetically sound then there is some word on $A$ which is not $R$-trivial but which $\mathsf{ZFC}$ cannot prove is not $R$-trivial; moreover, looking at the proof of the undecidability of the word problem we can even whip up a specific example word. However, this example will not be particularly natural. Moreover, this is really only a one-way phenomenon, since in general there is no way to attach a decision problem to a single sentence.

Getting back to your original post, the point about PH is that it represents a single yes/no question which is reasonably natural and carries no obvious "logical baggage" but which is independent from first-order Peano arithmetic.