Timeline for Examples of statements with a high quantifier complexity
Current License: CC BY-SA 4.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Aug 23, 2023 at 2:51 | history | suggested | C7X | CC BY-SA 4.0 |
Greek letters in MathJax, and MarkDown
|
| Aug 22, 2023 at 22:24 | review | Suggested edits | |||
| S Aug 23, 2023 at 2:51 | |||||
| Apr 11, 2020 at 23:13 | answer | added | Bjørn Kjos-Hanssen | timeline score: 2 | |
| Jun 7, 2019 at 6:12 | comment | added | bof | @PeterHeinig By "automate in $n$ moves" do you mean something like this (for $n=6$)? | |
| Jun 5, 2019 at 11:15 | comment | added | Dave L Renfro | Excerpt from p. 322 (and/or p. 323?) of Theory of Recursive Functions and Effective Computability by Hartley Rogers (1987, 2nd edition; also appears in 1967 1st edition): As has been occasionally remarked, the human mind seems limited in its ability to understand and visualize beyond four or five alternations of quantier. Indeed, it can be argued that the inventions, subtheories, and central lemmas of various parts of mathematics are devices for assisting the mind in dealing with one or two additional alternations of quantier. | |
| Jun 5, 2019 at 8:04 | answer | added | Joel David Hamkins | timeline score: 11 | |
| Jun 5, 2019 at 4:46 | answer | added | none | timeline score: 4 | |
| Oct 2, 2017 at 10:44 | answer | added | Alec Rhea | timeline score: 2 | |
| Oct 1, 2017 at 14:05 | comment | added | user111966 | Not the fact that some statement with a large number of quantifiers is not semantically equal to an assertion with fewer quantifiers. | |
| Sep 30, 2017 at 17:17 | comment | added | Peter Heinig | To add more context to the "Checkmate"-comment: the set of all legal positions which are helpmate in $\leq n$ moves, for example, for any given $n$, would nevertheless merely be $\Sigma_1$, since then there aren't any alternating quantifiers; the class of all positions which are 'checkmate in $\leq n$ moves' is indeed $\Sigma_{2n-1}$; another aspect: by symmetry, one is led to a kind of chess problem which I would guess is impossible, though I do not know how to prove it: 'automate' in $\leq n$ moves, i.e. mate unavoidable no matter what moves. | |
| Sep 28, 2017 at 5:55 | comment | added | Joshua Grochow | I'd be shocked to see an answer with (fixed) k > 5. Related (although somewhat outdated/incorrect, but still maybe of interest): cstheory.stackexchange.com/a/11403/129 | |
| Sep 26, 2017 at 9:09 | answer | added | Gro-Tsen | timeline score: 9 | |
| Sep 26, 2017 at 4:06 | answer | added | Vaughn Climenhaga | timeline score: 9 | |
| Sep 26, 2017 at 1:52 | comment | added | Noam D. Elkies | "Checkmate in at most $n$ moves" unwinds to $2n-1$ alternating quantifiers, though this might not qualify as mathematical . . . | |
| Sep 26, 2017 at 1:16 | history | edited | Dmytro Taranovsky | CC BY-SA 3.0 |
added three additional examples
|
| Sep 24, 2017 at 19:25 | answer | added | Bjørn Kjos-Hanssen | timeline score: 8 | |
| Sep 24, 2017 at 19:23 | history | edited | Peter Heinig |
Added two relevant tags.
|
|
| Sep 24, 2017 at 19:05 | answer | added | user44143 | timeline score: 23 | |
| Sep 24, 2017 at 16:10 | comment | added | Peter Heinig | Tangentially relevant is the nice expository article Jouko Väänänen: How complicated can structures be?. Nieuw Archief voor Wiskunde. Juni 2008. Note that $\bigcap\bigcup$-alternations, while not strictly speaking 'quantifier-alternations' are 'quantifier-alternations-in-disguise'. | |
| Sep 24, 2017 at 15:59 | comment | added | Wojowu | I'm not entirely sure how to put this in your question's framework, but in this paper a function growing like the $5$-th Busy Beaver function is described, so some corresponding statement should have complexity $\Sigma^0_5$. | |
| Sep 24, 2017 at 15:13 | history | asked | Dmytro Taranovsky | CC BY-SA 3.0 |