Timeline for Decidability: Presentations vs. Groups
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 17, 2019 at 11:31 | comment | added | YCor | @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... | |
| Feb 15, 2019 at 12:00 | comment | added | Derek Holt | But I still don't know what you mean by "a presentation that is undecidable whether it is trivial". | |
| Feb 15, 2019 at 11:30 | comment | added | Yiftach Barnea | @DerekHolt you missed my comment above I would like to machine to produce also a proof. | |
| Feb 15, 2019 at 10:55 | comment | added | Derek Holt | 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. | |
| S Feb 15, 2019 at 10:06 | history | answered | Yiftach Barnea | CC BY-SA 4.0 | |
| S Feb 15, 2019 at 10:06 | history | made wiki | Post Made Community Wiki by Yiftach Barnea |