Timeline for Examples of statements with a high quantifier complexity
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27, 2017 at 6:09 | comment | added | Bjørn Kjos-Hanssen | Actually it's $\Pi^0_4$ because the $\exists h$ turns out, after the fact, to be equivalent to $\forall h$, if $h$ is a total computable function that diverges to $\infty$ as $n\to\infty$... | |
| Sep 27, 2017 at 4:37 | comment | added | Dmytro Taranovsky | Do you happen to know whether the number of quantifiers is irreducible? For example, is the set of infinitely often computably traceable $A ≤_T 0'$ $Σ^0_5$-complete (under reasonable coding)? | |
| Sep 24, 2017 at 19:25 | history | answered | Bjørn Kjos-Hanssen | CC BY-SA 3.0 |