Timeline for Is the diagonal of finitely presented groups computable?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 28, 2021 at 9:57 | vote | accept | CommunityBot | ||
| Apr 23, 2021 at 7:53 | history | edited | HJRW | CC BY-SA 4.0 |
Corrected typo.
|
| Apr 23, 2021 at 5:04 | comment | added | James E Hanson | @Oniqa Checking to see if a finite presentation exists is therefore $\Sigma^0_3(G)$, which implies that checking to see if no such finite presentation exists is $\Pi^0_3(G)$. So all told, deciding if a given group has a finite presentation takes at most $3$ Turing jumps above the complexity of the group itself. I don't know if this is optimal, but usually these kinds of things aren't any easier than a naïve calculation like this. (Although I also may have miscounted.) | |
| Apr 23, 2021 at 5:03 | comment | added | James E Hanson | @Oniqa Checking to see if the subgroup generated by the $\bar{a}$ is the whole group is a $\Pi^0_2(G)$ condition (for every element of the group, there exists a product...), so checking to see if a given choice of presentation is in fact a presentation is $\Pi^0_2(G)$. | |
| Apr 23, 2021 at 5:03 | comment | added | James E Hanson | @Oniqa To see this, note that checking to see that the subgroup satisfies the generators is $\Delta^0_0(G)$, but checking to see that the subgroup only satisfies those generators is $\Pi^0_1(G)$ (for any pair of words in $\bar{a}$ whose products in $G$ are not equal, there is no derivation from the generators that implies they must be equal). | |
| Apr 23, 2021 at 5:03 | comment | added | James E Hanson | @Oniqa I guess it doesn't really matter that much. Suppose you're given a group as an oracle $G$. If you pick some finite set $\bar{a}$ of elements and some relations on those, checking to see if those relations give a presentation of the subgroup generated by $\bar{a}$ is a $\Pi^0_1(G)$ condition. | |
| Apr 23, 2021 at 4:40 | comment | added | James E Hanson | @Oniqa What data are you using to represent the group? Are we talking about arbitrary computable groups? Or do you mean relative to the group as an oracle? | |
| Apr 22, 2021 at 22:42 | history | edited | Michael Hardy | CC BY-SA 4.0 |
added 3 characters in body
|
| Apr 22, 2021 at 20:34 | history | edited | HJRW | CC BY-SA 4.0 |
Added details of the 1-2-3 theorem.
|
| Apr 22, 2021 at 11:51 | comment | added | HJRW | @Oniqa: that question is above my pay-grade, unfortunately! | |
| Apr 22, 2021 at 11:00 | comment | added | user178109 | So then at which level in the arithmetical hiearchy is the claim that a given group is finitely presentable? Seems like an oracle for the halting problem couldn't solve that? | |
| Apr 22, 2021 at 10:11 | history | edited | HJRW | CC BY-SA 4.0 |
Corrected minor error and added reference.
|
| Apr 22, 2021 at 8:47 | history | answered | HJRW | CC BY-SA 4.0 |