Timeline for Examples of statements with a high quantifier complexity
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 4, 2018 at 5:12 | comment | added | InquilineKea | are t and s interchangeable here? | |
| Oct 2, 2017 at 19:11 | comment | added | cody | This is a beautiful example of how mathematical language captures logical complexity! In "almost periodic function": the "periodic" captures 2-4 quantifiers (depending on how we understand "function") and the "almost" captures another one. And in the statement "arbitrarily good aproximation" also hides 2 quantifiers in a very intuitive manner. | |
| Sep 27, 2017 at 22:23 | history | edited | user44143 | CC BY-SA 3.0 |
added 111 characters in body
|
| Sep 25, 2017 at 13:11 | comment | added | Emil Jeřábek | @FrancoisZiegler I'm not disputing your comment, I just wanted to point out that the last quantifier alternation in the original answer is superfluous. | |
| Sep 25, 2017 at 2:37 | comment | added | Dmytro Taranovsky | @FrancoisZiegler On further analysis, 'almost periodic' is only $Π^0_3$ after all. Using uniform continuity of $f$, the quantification over $s$ can be done over a finite (dependent on $ε$) domain, so the last three quantifiers can be merged into one. Still notable as an example where high quantifier complexity is used but avoidable. | |
| Sep 25, 2017 at 0:05 | comment | added | Dmytro Taranovsky | @FrancoisZiegler Right. $Σ_{n=1}^∞ \sin(x/2^{n^2})$ satisfies $∀ε>0 ∃t>1 ∀x \, |f(x+t)−f(x)|<ε$ but is unbounded and hence not almost periodic. Almost periodicity looks like a great example for this question, especially if the quantifier counts cannot be reduced. | |
| Sep 24, 2017 at 22:41 | comment | added | Francois Ziegler | @EmilJeřábek Yes, but let me try again: I believe the “first definition” above is itself oversimplified, it should be $$\forall \epsilon>0\, \exists t>0\ \forall a\ \exists s \in [a,a+t]\ \forall x\, |f(x+s)-f(x)| \leqslant \epsilon.$$ | |
| Sep 24, 2017 at 20:04 | comment | added | Emil Jeřábek | As far as I can see, you get an equivalent definition if you replace ${}<\epsilon$ by ${}\le\epsilon$. This is a universal property, hence the complexity drops down to 3 quantifiers. | |
| Sep 24, 2017 at 19:18 | comment | added | Peter Heinig | [...] And there are results to the effect that known classes can be axiomatized more 'succinctly' than one might expect, see. e.g. [O. Pikhurko,J. Spencer,O. Verbitsky: Succinct definitions in the first order theory of graphs. Annals of Pure and Applied Logic 139 (2006) 74-109] I don't have reason to doubt that 'almost periodic functions' needs at that many quantifiers, yet I don't know how to prove it. | |
| Sep 24, 2017 at 19:16 | comment | added | Peter Heinig | It is so nice to see someone dare answer this question via a natural class of mathematical structures; however, do you know a proof that there might not be some equivalent axiomatization, with smaller quantifier-alternatioin number, of the class $\mathbb{K}\subset\mathbb{R}^{\mathbb{R}}$ of almost-periodic functions. I don't really believe that there is, but so far I cannot see why 5 is the minimum. The one you gave is only one 'representative', so to speak. [...] | |
| Sep 24, 2017 at 19:05 | history | answered | user44143 | CC BY-SA 3.0 |