Revisions to Examples of statements with a high quantifier complexity

Greek letters in MathJax, and MarkDown

Source Link

edit approved Aug 23, 2023 at 2:51

2k
1
9
31

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

The complexity could be $Π^0_k$$\Pi^0_k$, $Π^1_k$$\Pi^1_k$, $Π^V_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 $Π^0_3$$\Pi^0_3$-complete. (Also, there should be natural $Σ^0_4$$\Sigma^0_4$/$Π^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 $Σ^0_4$$\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 $Π^1_3$$\Pi^1_3$ (and equivalent to $Π^1_1-\mathrm{CA}_0$$\Pi^1_1-\mathrm{CA}_0$ over $\mathrm{RCA}_0$).
The axiom of choice is $Π^1_4$$\Pi^1_4$ conservative over ZF (but without large cardinal axioms, it is not $Σ^1_4$$\Sigma^1_4$ conservative).
Existence of a proper class of extendible cardinals is $Π^V_5$$\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:Update: Here are three more examples:

Whether $f(x)$ is continuously differentiable at $x_0$ is $Σ^0_4$$\Sigma^0_4$-complete. By contrast, differentiability at $x_0$ or continuous differentiability on $(a,b)$ is $Π^0_3$$\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 $Π^0_5$$\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 $Π^0_5$$\Pi^0_5$-complete).
In set theory, "$κ$$\kappa$ is ineffable" is $Π^1_3$$\Pi^1_3$ in the second order logic over $V_κ$.

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

The complexity could be $Π^0_k$, $Π^1_k$, $Π^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 $Π^0_3$-complete. (Also, there should be natural $Σ^0_4$/$Π^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 $Σ^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 $Π^1_3$ (and equivalent to $Π^1_1-\mathrm{CA}_0$ over $\mathrm{RCA}_0$).
The axiom of choice is $Π^1_4$ conservative over ZF (but without large cardinal axioms, it is not $Σ^1_4$ conservative).
Existence of a proper class of extendible cardinals is $Π^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 $Σ^0_4$-complete. By contrast, differentiability at $x_0$ or continuous differentiability on $(a,b)$ is $Π^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 $Π^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 $Π^0_5$-complete).
In set theory, "$κ$ is ineffable" is $Π^1_3$ in the second order logic over $V_κ$.

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_κ$.

added three additional examples

Source Link

edited Sep 26, 2017 at 1:16

Dmytro Taranovsky

7.5k
1
22
45

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

The complexity could be $Π^0_k$, $Π^1_k$, $Π^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 $Π^0_3$-complete. (Also, there should be natural $Σ^0_4$/$Π^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 $Σ^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 $Π^1_3$ (and equivalent to $Π^1_1-\mathrm{CA}_0$ over $\mathrm{RCA}_0$).
The axiom of choice is $Π^1_4$ conservative over ZF (but without large cardinal axioms, it is not $Σ^1_4$ conservative).
Existence of a proper class of extendible cardinals is $Π^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 $Σ^0_4$-complete. By contrast, differentiability at $x_0$ or continuous differentiability on $(a,b)$ is $Π^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 $Π^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 $Π^0_5$-complete).

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

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

The complexity could be $Π^0_k$, $Π^1_k$, $Π^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 $Π^0_3$-complete. (Also, there should be natural $Σ^0_4$/$Π^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 $Σ^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 $Π^1_3$ (and equivalent to $Π^1_1-\mathrm{CA}_0$ over $\mathrm{RCA}_0$).
The axiom of choice is $Π^1_4$ conservative over ZF (but without large cardinal axioms, it is not $Σ^1_4$ conservative).
Existence of a proper class of extendible cardinals is $Π^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.

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

The complexity could be $Π^0_k$, $Π^1_k$, $Π^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 $Π^0_3$-complete. (Also, there should be natural $Σ^0_4$/$Π^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 $Σ^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 $Π^1_3$ (and equivalent to $Π^1_1-\mathrm{CA}_0$ over $\mathrm{RCA}_0$).
The axiom of choice is $Π^1_4$ conservative over ZF (but without large cardinal axioms, it is not $Σ^1_4$ conservative).
Existence of a proper class of extendible cardinals is $Π^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 $Σ^0_4$-complete. By contrast, differentiability at $x_0$ or continuous differentiability on $(a,b)$ is $Π^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 $Π^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 $Π^0_5$-complete).