6
$\begingroup$

This question is just a curiosity for me as a non-expert. Quite often we ask about decidability of various properties in a group. Often the answer is that the property is undecidable in general. However, what it usually means, as far as I know, that there is a presentation in which this property is undecidable. Are there examples, not-necessarily explicit, such that for all presentations of the group the problem is undecidable?

For instance, is there a finitely presented group such that for all its presentations we cannot decide whether it is trivial?

$\endgroup$
15
  • 4
    $\begingroup$ The decidability of the word problem, for example, is a property of the group, it is independent of the generating set. The same applies to most of the familiar decision problems such as conjugacy problem, isomorphism problem. $\endgroup$
    – Derek Holt
    Feb 14, 2019 at 20:52
  • 2
    $\begingroup$ Most of these issues arise from not clearly stating what is the input to a problem. For example the triviality problem takes as input a presentation and asks if it presents the trivial group. The input is a presentation not a group. Usually for the word problem the group is fixed and the input is just a word over the generators. In this case as Derek says having a decidable word problem is presentation independent. People will often say the uniform problem if the group is part of the input. $\endgroup$ Feb 14, 2019 at 21:25
  • 1
    $\begingroup$ Yes it's moderately obvious. If the word problem is decidable using generators $X$, and you have another set $Y$ of generators, then you can express each element of $Y$ as a word over $X$, and then when you read an input word over $Y$ you just translate it into a word $X$ as you read it and use your existing word problem solver over $X$. $\endgroup$
    – Derek Holt
    Feb 14, 2019 at 21:53
  • 4
    $\begingroup$ I don't think your question in the final paragraph makes sense. If the input is a presentation, then the problem would be to decide whether that presentation defines a trivial group. Either that can be done or it cannot. It doesn't make sense to say that we cannot decide it for all inputs. Decidability applies to the problem as a whole, not to the individual inputs to the problem. $\endgroup$
    – Derek Holt
    Feb 14, 2019 at 22:11
  • 1
    $\begingroup$ A finitely generated group has solvable word problem iff it is isomophic to $\mathbf{N}$ endowed with a computable group law. $\endgroup$
    – YCor
    Feb 14, 2019 at 22:25

2 Answers 2

3
$\begingroup$

I will try to clear up some confusion I see in the question and the OP's answer. Whenever I say "presentation", I mean a finite presentation (one with finitely many generators and finitely many relations), as infinite presentations do not come up.

Computational Decidability

First, every constant function is computable. So for a specific presentation $P$, we can prove that there is an algorithm that outputs whether it is trivial or not, using excluded middle:

  1. If $P$ presents the trivial group, the constant function that outputs "yes" computes the triviality of $P$ correctly.
  2. If $P$ presents a non-trivial group, the constant function that outputs "no" computes the triviality of $P$ correctly.

So we know there exists an algorithm, we just don't know which one it is. (To make a system of logic where this can't happen, a necessary, but not sufficient, criterion is to not allow the use of the principle of excluded middle. I will not comment on this further in the answer.) What people mean by "triviality is undecidable" is that the function from the set of presentations (encoded as natural numbers or finite strings from a finite alphabet) to $\{0,1\}$ that is $1$ on trivial groups and $0$ on non-trivial groups is not a computable function.


Logical Decidability

However, you also ask if there exists a presentation $P$ of a group such that there is no Turing machine that calculates the triviality of $P$ and provides a proof that it is correct. Suitably interpreted, the answer to this question is in fact yes, simply because there exists a presentation $P$ such that there exists no proof (in ZFC) that the group it presents is trivial or non-trivial, assuming ZFC is consistent.

This follows from a particular line of reasoning based on the Halting problem and Gödel's incompleteness theorem that I think I've seen on this site before, though I can't quite remember where (the closest I could find is this).

Firstly, the proof that triviality of a presentation is undecidable actually shows more. In fact, what is shown is that for each Turing machine $M$, there is a presentation $P_M$ that presents a trivial group iff $M$ halts when given an empty input, and the function $M \mapsto P_M$ is computable. For any theory $T$ where the set of axioms is recursively enumerable (e.g. Peano arithmetic, ZFC) there is a Turing machine $M_T$ that, given an empty input, searches through all formal proofs in that theory and halts if it reaches a contradiction (people have actually constructed such a thing -- see the references). If we apply the construction from the proof of the undecidability of the triviality problem, we get a presentation $P_{M_T}$ that presents a trivial group iff $M_T$ halts iff $\lnot\mathrm{Con}(T)$. So we just do this with $T = \mathrm{ZFC}$. Gödel's incompleteness theorem then gives us that ZFC cannot prove whether or not $P_{M_{\mathrm{ZFC}}}$ presents a trivial group.

In your answer, you say that since it is undecidable, $P_{M_{\mathrm{ZFC}}}$ "must be a non-trivial group". If ZFC is consistent, then, by Gödel, $\mathrm{ZFC} + \lnot \mathrm{Con}(\mathrm{ZFC})$ is consistent, and therefore has a model $X$. When $P_{M_{\mathrm{ZFC}}}$ is interpreted in $X$, it presents a trivial group. However, this is because the natural numbers of $X$ and the standard natural numbers do not agree (specifically, about whether $\mathrm{Con}(\mathrm{ZFC})$ is true).

References

The proof the undecidability of the triviality of group presentations is actually in two pieces - the first goes from the halting problem to the word problem for finitely-presented groups, and the second part from the word problem for finitely-presented groups to the triviality of finite presentations. A nice reference for the word problem is Rotman's An Introduction to the Theory of Groups, Chapter 12, which includes enough background on the semigroup version of it as well. For the second part, Rabin's original paper is perfectly good, and for the triviality problem you only need Theorem 1.2, not the more sophisticated Theorem 1.1 (that works for an arbitrary Markov property).

Here are some references for people actually going through and explicitly constructing Turing machines that have the needed property relative to ZFC. Adam Yedidia and Scott Aaronson explicitly constructed a Turing machine that halts iff $\lnot \mathrm{Con}(ZFC + SRP)$ (which implies Con(ZFC), SRP being the existence of a large cardinal with the stationary Ramsey property) using some of Harvey Friedman's work. Building on this, Stefan O'Rear explicitly constructed a Turing machine (with 5349 states) that halts iff $\lnot \mathrm{Con}(\mathrm{ZFC})$. Of course, it would be possible, given some programming effort, to produce a "compiler" from Turing machines to finitely-presented groups and thereby obtain $P_{M_{\mathrm{ZFC}}}$, but as far as I know nobody's done this yet.

$\endgroup$
2
  • $\begingroup$ In your part on logical decidability, do you mean there is a (finite??) presentation $M$ such that, assuming that ZFC is consistent, then both (ZFC and $M$ is a presentation of the trivial group) and (ZFC and $M$ is a presentation of a nontrivial group) are consistent? $\endgroup$
    – YCor
    Jul 28, 2019 at 6:58
  • $\begingroup$ @YCor Yes, exactly, and I've changed the answer to clarify that I always mean a finite presentation. It is even possible to produce such a presentation explicitly, by writing a kind of compiler from Turing machines to finite presentations. $\endgroup$ Jul 28, 2019 at 13:08
0
$\begingroup$

Let me try and summarize my understanding of the comments above. There is a Turing machine that given a presentation of a group will list all the presentations of the group. Thus, if a problem is decidable or positively-decidable (for instance the word-problem) for one presentation it is decidable or positively-decidable for all presentations.

This implies that if you have a presentation that is undecidable whether it is trivial, it must be of a non-trivial group. This means we cannot have an explicit example of such presentation.

Am I right?

$\endgroup$
4
  • $\begingroup$ The problem is that "presentation that is undecidable whether it is trivial" does not make much sense. I presume that by a "trivial presentation" you mean a presentation of the trivial group? But for any given presentation there is an algorithm that decides whether it defines the trivial group, so the property is decidable.Consider Algorithm 1 that outputs "yes" and Algorithm 2 that outputs "no". One of those two algorithms correctly decides whether the group is trivial. So there exists an algorithm that decides whether the group is trivial, and hence the property is decidable. $\endgroup$
    – Derek Holt
    Feb 15, 2019 at 10:55
  • $\begingroup$ @DerekHolt you missed my comment above I would like to machine to produce also a proof. $\endgroup$ Feb 15, 2019 at 11:30
  • 1
    $\begingroup$ But I still don't know what you mean by "a presentation that is undecidable whether it is trivial". $\endgroup$
    – Derek Holt
    Feb 15, 2019 at 12:00
  • $\begingroup$ @DerekHolt it might be a confusion with the set-theoretic decidability. Fix a presentation $P=<S|R>$. Could it be that there are two models $M_1,M_2$ of ZFC, such that $P$ defines the trivial group in $M_1$ and not in $M_2$? It sounds unlikely but... $\endgroup$
    – YCor
    Mar 17, 2019 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.