33
$\begingroup$

What are some natural properties, definitions, and statements that require many alternating quantifiers?

The complexity could be $\Pi^0_k$, $\Pi^1_k$, $\Pi^V_k$, or something else entirely, as long $k$ is not too small, and the statement is naturally viewed for a fixed $k$, as opposed to a part of a schema that works independent of $k$. More obscure/complicated examples require a higher $k$ to qualify.

Here are five examples:

  • Definition/existence of a limit (and many related concepts) is $\Pi^0_3$-complete. (Also, there should be natural $\Sigma^0_4$/$\Pi^0_4$-complete properties related to limits, but I have not really found them -- except for the next item.)

  • I conjecture that existence of an $n^{1+o(1)}$ algorithm for a given decision problem is $\Sigma^0_4$-complete (even if the problem is in P and coded as such).

  • "Every closed set is the union of a countable set and a perfect set" is $\Pi^1_3$ (and equivalent to $\Pi^1_1-\mathrm{CA}_0$ over $\mathrm{RCA}_0$).

  • The axiom of choice is $\Pi^1_4$ conservative over ZF (but without large cardinal axioms, it is not $\Sigma^1_4$ conservative).

  • Existence of a proper class of extendible cardinals is $\Pi^V_5$.

First order logic allows an arbitrary number of quantifiers, but other than through schemas (which can often be viewed as an approximation to a single higher order quantifier), mathematical practice rarely uses many alternating quantifiers. So rarely that quantifiers were not formalized in a general form until the second half of the 19th century. The high quantifier complexity of limits is essentially the reason that limits were not formally defined until after much of mathematical analysis was developed. However, 'rarely' does not mean 'never', and the question is to identify some of the exceptions.

Update: Here are three more examples:

  • Whether $f(x)$ is continuously differentiable at $x_0$ is $\Sigma^0_4$-complete. By contrast, differentiability at $x_0$ or continuous differentiability on $(a,b)$ is $\Pi^0_3$.

  • Given a countable metric space (coded by an enumeration of all points and distances) that we are promised is locally complete (or even complete), whether the space is locally compact is $\Pi^0_5$-complete. Note that a metric space is locally compact iff it is locally complete (which for countable spaces is $Π^1_1$-complete) and every point has a totally bounded neighborhood (which for countable spaces is $\Pi^0_5$-complete).

  • In set theory, "$\kappa$ is ineffable" is $\Pi^1_3$ in the second order logic over $V_κ$.

$\endgroup$
8
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Wojowu
    Sep 24, 2017 at 15:59
  • 2
    $\begingroup$ 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'. $\endgroup$ Sep 24, 2017 at 16:10
  • 4
    $\begingroup$ "Checkmate in at most $n$ moves" unwinds to $2n-1$ alternating quantifiers, though this might not qualify as mathematical . . . $\endgroup$ Sep 26, 2017 at 1:52
  • 1
    $\begingroup$ 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 $\endgroup$ Sep 28, 2017 at 5:55
  • 2
    $\begingroup$ @PeterHeinig By "automate in $n$ moves" do you mean something like this (for $n=6$)? $\endgroup$
    – bof
    Jun 7, 2019 at 6:12

8 Answers 8

22
$\begingroup$

My favorite example is the 5-quantifier definition of an almost-periodic function: $f$ is almost-periodic iff $$\forall \epsilon>0\, \exists t>0\ \forall a\ \exists s \in [a,a+t]\ \forall x\, |f(x+s)-f(x)| \leqslant \epsilon.$$

Using the fact that almost periodic functions are uniformly continuous, one can show that this is equivalent to a 3-quantifier property. The 5-quantifier definition remains the more natural one, especially for the purpose of stating the above fact.

So Bohr's theorem that every almost-periodic function has arbitrarily good appropximations by trigonometric polynomials is naturally written as a 6-quantifier statement.

PS Thanks to @FrancoisZiegler and @DmytroTaranovsky for sorting me out on this.

$\endgroup$
9
  • 6
    $\begingroup$ 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. [...] $\endgroup$ Sep 24, 2017 at 19:16
  • 3
    $\begingroup$ 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. $\endgroup$ Sep 24, 2017 at 20:04
  • 4
    $\begingroup$ @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.$$ $\endgroup$ Sep 24, 2017 at 22:41
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 25, 2017 at 0:05
  • 3
    $\begingroup$ 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. $\endgroup$
    – cody
    Oct 2, 2017 at 19:11
10
$\begingroup$

Consider the statement:

  • "Neither player has a winning strategy in the game of Tic-tac-toe."

This is a natural statement, often asserted and believed, and the most natural formulation of it has complexity $\Sigma_9\wedge\Pi_9$.

To be sure, statements about game strategies often generally involve very high quantifier complexity. The assertion that player I has a winning strategy in a game of length $k$, after all, is most naturally a $\Sigma_k$ assertion, of the form:

"There is a move for player I, such that for any reply, there is a further move for player I, such that for any reply, there is a further move,... after which player I has won the game."

In the case of tic-tac-toe, the game has at most nine moves, and so we have nine quantifiers in the statement. The assertion that neither player has a winning strategy is equivalent, by the fundamental theorem of finite games, to the assertion that both players have drawing strategies.

Longer games naturally give rise to assertions with even more quantifiers. For example, the corresponding statement about chess would have enormous quantifier complexity, bounded essentially by the length of the longest chess game.

Meanwhile, of course, one can subsume the first-order quantifiers into a higher-order quantifiers by talking about strategies. This amounts to trading high first-order quantifier complexity for low higher-order quantifier complexity.

$\endgroup$
1
  • 1
    $\begingroup$ Ah, I see now that checkmate-in-n moves is mentioned already in the comments on the original question. $\endgroup$ Jun 5, 2019 at 8:06
8
$\begingroup$

One example from dynamical systems is the specification property, which needs 5 quantifiers. It was introduced by Rufus Bowen in the 1970s to study equilibrium measures of dynamical systems; for example, it implies that the limiting distribution of periodic orbits is the unique measure that maximizes entropy as long as the system is expansive. It comes in various versions, which are not quite all equivalent, but let me ignore these subtleties and just quote one.

Given a compact metric space $X$, a continuous map $f\colon X\to X$ has the specification property if $\forall\epsilon>0$, $\exists T>0$ such that $\forall (x_1,n_1),\dots,(x_\ell,n_\ell)\in X\times \mathbb{N}$, $\exists y\in X$ such that $\forall 1\leq k\leq \ell$ and $0\leq j < n_k$, we have $d(f^{N_k + j}(y),f^j(x_k)) < \epsilon$, where $N_k = \sum_{i=1}^{k-1} (n_i + T)$, and we also have $f^{N_\ell+n_\ell+T}(y)=y$.

Roughly speaking it says that any finite collection of orbit segments can be shadowed by a periodic orbit that takes a bounded time $T$ to transition from each one to the next, and that $T$ depends only on how precise the shadowing is required to be.

$\endgroup$
1
  • 2
    $\begingroup$ The specification property is $Π^0_3$. Using compactness, there is an algorithm that given $X$, $f$, $ϵ$ and $T$, will run forever iff the property holds for $ϵ$ and $T$ (using $≤ϵ$ in place of $<ϵ$). (Regarding $∃y∈X$, for compact spaces, existence of an element satisfying a $Π^0_1$-property is $Π^0_1$.) Still, I find the specification property interesting. $\endgroup$ Sep 27, 2017 at 4:09
8
$\begingroup$

The pumping lemma (for rational languages) states that

  • for every rational language $L \subseteq \Sigma^*$ (over a finite alphabet $\Sigma$),

  • there exists an integer $p$ such that,

  • for every word $w\in L$ with $|w|\geq p$,

  • there exists a factorization $w = xyz$ such that $|y|\geq 1$ and $|xy|\leq p$ and

  • for every $i\geq 0$ we have $xy^iz\in L$.

So it has quantifier complexity $5$.

I like this example because it is not too sophisticated, but still pedagogically interesting. I teach an elementary course in formal languages theory in which this lemma is discussed, and many students have difficulty coming to terms with it (or how to use it) because of the quantifier subtlety; so it's worth taking the time to explain the logic. I try to emphasize (in a sort of game-theoretic point of view) that, when you apply a result like this, you get to choose every object that is introduced with "for all" but those quantified by "there exists" are imposed upon you (whereas when proving such a result, things are the other way around). Despite this, many students continue to believe they can choose the factorization they want.

$\endgroup$
6
  • 1
    $\begingroup$ The 4th quantifier is bounded, hence the last three quantifiers collapse, and the complexity is only $\Pi_3$. $\endgroup$ Sep 26, 2017 at 9:15
  • 3
    $\begingroup$ @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. $\endgroup$
    – Gro-Tsen
    Sep 26, 2017 at 10:59
  • 2
    $\begingroup$ Well, bounded quantifiers are ignored in the hierarchies explicitly mentioned in the question, it’s not just my point of view. $\endgroup$ Sep 26, 2017 at 14:16
  • 1
    $\begingroup$ @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. $\endgroup$
    – Gro-Tsen
    Sep 26, 2017 at 15:00
  • 2
    $\begingroup$ @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. $\endgroup$ Sep 27, 2017 at 4:19
7
$\begingroup$

In computability theory, a set of integers $A$ is infinitely often computably traceable if there is a computable function $h$ such that for all functions $g\le_T A$ ($g$ computable from $A$), there is a computable sequence $T$ of finite sets $T_n$, $n\ge 0$, such that for infinitely many $n$, $g(n)\in T_n$, and for all $n$ the size of $T_n$ is at most $h(n)$.

If you unpack this it is $\Sigma^0_5$: there is an $h$ such that for all $g$ there is a $T$ such that for all $m$ there is an $n>m$ with $g(n)\in T_n$.

$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$ Sep 27, 2017 at 4:37
  • 1
    $\begingroup$ 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$... $\endgroup$ Sep 27, 2017 at 6:09
3
$\begingroup$

My favorite is still the Hilbert-Waring theorem. It is only $\Pi_3^0$ but it is a natural statement understandable by anyone, that has a venerable mathematical history.

$\endgroup$
2
$\begingroup$

I believe the notion of a pseudo-convergent sequence in an Abelian group with valuation is a good candidate -- it is a generalization of the notion of convergent sequences and limits over the reals.

Let $\mathbb{G}$ be an additively written ordered Abelian group with extended value class $EVC(\mathbb{G})$ ordered by anti-inclusion, and valuation $\nu:\mathbb{G}\rightarrow EVC(\mathbb{G})$. Also let $\lambda$ be a non-zero limit ordinal, with $\{g_\alpha\}_{\alpha<\lambda}$ a $\lambda$-termed sequence in $\mathbb{G}$. We say that $\{g_\alpha\}_{\alpha<\lambda}$ is pseudo-convergent in $\mathbb{G}$ relative to $\nu$ iff for all $\alpha<\beta<\gamma<\lambda$, $$\nu(g_\alpha-g_\beta)\prec\nu(g_\beta-g_\gamma).$$ Further, $x$ is a pseudo-limit of $\{g_\alpha\}_{\alpha<\lambda}$ iff $$\nu(g_\alpha-x)=\nu(g_\alpha-g_{\alpha+1})$$ for all $\alpha<\lambda$.

$\endgroup$
1
$\begingroup$

The Interchange lemma in the theory of formal languages has a $\Pi_5$ form:

$\forall L$, if $L$ is a context-free language, then

$\exists c$, $c$ is a positive integer, such that

$\forall n\ge 2$, $R\subseteq L\cap\{0,1\}^n$, $2\le m\le n$,

$\exists Z\subseteq R$, $Z=\{z_1,\dots,z_k\}$, $z_i=w_ix_iy_i$, $k\ge \frac{|R|}{c(n+1)^2}$, and lengths $a,b,c$, such that

$\forall i,j$ with $1\le i,j\le k$, [$|w_i|=|w_j|$, etc. etc.]

The most famous application is to let $L$ be the set of not-square-free words, assume it's context-free, and then carefully choose $R$ and $n$ so as to get a contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.