Timeline for Examples of statements with a high quantifier complexity
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27, 2017 at 4:19 | comment | added | Dmytro Taranovsky | @Gro-Tsen The thrust of the question is about irreducible quantifier complexity, but I do not mind a few broader examples of natural statements with many alternating quantifiers. Still, your answer (which I personally found interesting) should have been explicit about the kind of quantifier complexity it illustrates. | |
| Sep 26, 2017 at 15:00 | comment | added | Gro-Tsen | @EmilJeřábek I interpret "the complexity could be […] or something else entirely" as the sign that the question shouldn't be taken too narrowly as one of these hierarchies. Especially as the first paragraph is also fairly broad, and others have interpreted things in various ways (e.g., Noam Elkies's comment about chess, which, of course, is finistic in nature). But I agree that the logic tags suggest a more narrow interpretation, in which case my pedagogical example is indeed off-topic. | |
| Sep 26, 2017 at 14:16 | comment | added | Emil Jeřábek | Well, bounded quantifiers are ignored in the hierarchies explicitly mentioned in the question, it’s not just my point of view. | |
| Sep 26, 2017 at 10:59 | comment | added | Gro-Tsen | @EmilJeřábek You could also point out that the statement is provable, so it is equivalent to $0=0$ with no quantifiers at all. :-) (This is more or less what you do in your second comment.) I fully appreciate that from a logician's point of view, bounded quantifiers are irrelevant, but if we are to gauge the mental or pedagogical difficulty of a theorem, I don't think we should ignore them, and OP's formulation wasn't too clear on what he wanted. | |
| Sep 26, 2017 at 9:21 | comment | added | Emil Jeřábek | Actually, I don’t know how exactly do you want to represent the regular language $L$, but if it is given in a natural representation as a finite automaton or regular expression, then $p$ is also bounded in terms of the input. Thus the statement is only $\Pi_1$. | |
| Sep 26, 2017 at 9:15 | comment | added | Emil Jeřábek | The 4th quantifier is bounded, hence the last three quantifiers collapse, and the complexity is only $\Pi_3$. | |
| Sep 26, 2017 at 9:09 | history | answered | Gro-Tsen | CC BY-SA 3.0 |