12
$\begingroup$

This question is about logical complexity of sentences in third order arithmetic. See Wikipedia for the basic concepts.

Recall that the Continuum Hypothesis is a $\Sigma^2_1$ sentence. Furthermore (loosely speaking) it can't be reduced to a $\Pi^2_1$ sentence, as stated in Emil Jeřábek's answer to Can we find CH in the analytical hierarchy?.

Is there an example of a $\Sigma^2_2$ sentence with no known reduction to a $\Pi^2_2$ sentence? (Equivalently, a $\Pi^2_2$ sentence with no known reduction to a $\Sigma^2_2$ sentence.) I mean that there should be no known reduction even under large cardinal assumptions.

I'd prefer an example that's either famous or easy to state. But to begin, any example will do.

Update: Sentences such as "$\mathfrak{c} \leqslant \aleph_2$" and "$\mathfrak{c}$ is a successor cardinal" are $\Delta^2_2$, meaning that they're simultaneously $\Sigma^2_2$ and $\Pi^2_2$. The reason is that each such sentence (and also its negation) can be expressed in the form "$\mathbb{R}$ has a well-ordering $W$ such that $\phi(W)$" where $\phi$ is $\Sigma^2_2$.

$\endgroup$
1

3 Answers 3

9
$\begingroup$

The Suslin hypothesis is $\Pi^2_2,$ and $T = ZFC + GCH + LC$ (LC an arbitrary large cardinal axiom) does not prove it to be equivalent to any $\Sigma^2_2$ sentence. Suppose toward contradiction $T$ proves SH to be equivalent to $\exists A \subset \mathbb{R} \varphi(A),$ where $\varphi$ is $\Pi^2_1.$ Assume $V \models T.$

We'll use several results from Chapters VIII and X of Devlin and Johnsbraten's The Souslin Problem. There are generic extensions $V[G] \models T+\diamondsuit^*$ and $V[G][H] \models T+SH$ which do not add reals to or collapse cardinals of $V.$ In $V[G][H],$ there is $A \subset \mathbb{R}$ such that $\varphi(A)$ holds and $A' \subset \omega_1$ which codes a bijection between $\mathbb{R}$ and $\omega_1$ as well as $A.$ By downwards absoluteness of $\varphi,$ $A$ witnesses that $V[G][A'] \models SH.$ But we also have $V[G][A'] \models \diamondsuit^*$ by Lemma 4 (pg. 79), which is a contradiction since $\diamondsuit$ negates SH.

$\endgroup$
5
  • $\begingroup$ Thanks, Elliot, but I can only see that Suslin's hypothesis is $\Pi^3_2$, by the following argument. Let's take SH in the form: "The tree $\{0,1\}^{<𝜔_1}$ has no subtree in which every chain and every antichain is countable." A countable ordinal can be represented by a set of natural numbers. So an element of $\{0,1\}^{<𝜔_1}$ can be represented by a set of sets of natural numbers. So a subset of $\{0,1\}^{<𝜔_1}$ can be represented by a set of sets of sets of natural numbers. This gives $\Pi^3_2$. How can we get $\Pi^2_2$? $\endgroup$ Aug 19, 2021 at 12:38
  • 2
    $\begingroup$ @PaulBlainLevy An element $\sigma\in\{0,1\}^{<\omega_1}$ can be coded by a single real: as a pair $\langle A,B\rangle$, where $A$ is a well-ordering of (an initial segment of) $\omega$ with ordertype $\vert\sigma\vert$ and $B$ a subset of the domain of $A$ (thought of as the set of bits on which $\sigma$ takes on value $1$). Of course there is no "canonical" way to assign a code to an element of $\{0,1\}^{<\omega_1}$ in this way, but that's not a problem here. $\endgroup$ Aug 19, 2021 at 14:59
  • $\begingroup$ Thanks @NoahSchweber, your comment makes it clear to me. $\endgroup$ Aug 19, 2021 at 15:55
  • 2
    $\begingroup$ So Elliot didn't fail the count-to-three test. $\endgroup$ Aug 19, 2021 at 16:06
  • $\begingroup$ Thanks, Elliot, for this great example (now that I understand at least the first part). $\endgroup$ Aug 19, 2021 at 16:08
9
$\begingroup$

Here are two non-examples, one erring in each direction:

  • Too simple: "The continuum is an $\aleph$-fixed point," that is $\mathfrak{c}=\aleph_\mathfrak{c}$. This is equivalent of course to $\mathfrak{c}\ge\aleph_\mathfrak{c}$, which means it can be expressed as "There is an $\mathbb{R}$-indexed family of sets of reals of pairwise distinct cardinalities," which is $\Sigma^2_2$. Contra my original guess, however, this does have a $\Pi^2_2$ equivalent observed by Farmer S in the comments below (and I'll add his argument here later when I have more time).

  • Too complicated (so far!): "The continuum is a limit cardinal." This can be expressed in a $\Pi^2_3$ way (which I originally miscounted - thanks to Andreas Blass for bringing this to my attention) as "For every set of reals $X$, either there is a surjection $X\rightarrow\mathbb{R}$ or there is a set of reals $Y$ such that there is no surjection $X\rightarrow Y$ or $Y\rightarrow\mathbb{R}$," and I don't see how to get a $\Sigma^2_3$ equivalent even granting large cardinals. (In particular, note that "The continuum is $\ge$ some uncountable limit cardinal" is easy to express in a $\Sigma^2_2$ way as "There exists an $\omega$-sequence of sets of reals of strictly increasing cardinality," but this doesn't seem to be useful here.)

Of course, the first example doesn't work, and the second example almost certainly doesn't work. That said, I think this is a good indication that general continuum combinatorics is a good place to look for high-complexity third-order sentences.

$\endgroup$
17
  • 1
    $\begingroup$ @PaulBlainLevy Thanks, but I don't think you should accept this just yet - I don't actually have a proof that there isn't a simpler equivalent. $\endgroup$ Aug 18, 2021 at 0:06
  • 4
    $\begingroup$ I should probably be sleeping instead of writing this (and maybe I am sleeping), but your formulation of "$\mathfrak c$ is a limit cardinal" looks $\Pi^2_3$ to me, the relevant quantifiers being "for every X", "there is $Y$", and "there is no surjection". $\endgroup$ Aug 18, 2021 at 2:59
  • 3
    $\begingroup$ @AndreasBlass Oh dear goodness, I failed to count to three. Fixing ... $\endgroup$ Aug 18, 2021 at 3:59
  • 5
    $\begingroup$ Oops, that should have been "for each $z$ with $x<^¢z<^¢y$, $W$ codes a bijection between the predecessors of $x$ and those of $z$". It should also say that if $S$ has a largest element $x$ (wrt the wellorder) then for each $z>^¢x$, $W$ codes a bijection between the predecessors of $x$ and those of $z$. $\endgroup$
    – Farmer S
    Aug 18, 2021 at 11:25
  • 5
    $\begingroup$ @paulgarrett Personally I count "$0$, some, lots, oh dear, what?, twenty, $\omega$." (... $\omega_1^{CK},\omega_1,\omega_2,\mathfrak{c},\kappa$, ...) $\endgroup$ Aug 18, 2021 at 18:22
7
$\begingroup$

(As pointed out by @PaulBlainLevy, the following doesn't meet the requirement that it should have no known reduction even under large cardinal assumptions. But I think it's a natural $\Pi^2_2$ statement, so I'll leave it here.)

Consider the statement "For every set of reals $X$, $X^\#$ exists". (Equivalently, "for every set of reals $X$, there is an elementary embedding $L(\mathbb{R},X)\to L(\mathbb{R},X)$".) I claim it's $\Pi^2_2$ but not $\Sigma^2_2$, at least assuming the consistency of ZFC + "For every set of reals $X$, $X^\#$ exists". (Here I mean that there is a fixed $\Pi^2_2$ formula $\psi$ such that ZFC proves "$\psi$ holds iff $X^\#$ exists for all sets of reals $X$", but this is not the case for $\Sigma^2_2$).

It's $\Pi^2_2$: For given $X$, it is $\Sigma^2_1(\{X\})$ to say that $X^\#$ exists, as $X^\#$ is coded by a real, and one just has to check that for each countable ordinal $\alpha$, the model generated from $\mathbb{R}\cup\alpha$-many indiscernibles is wellfounded, to know that it is correct, and this is all expressed as a projective statement about some set of reals coding everything.

It's not $\Sigma^2_2$ (modulo the consistency mentioned above): For suppose it is, and fix a $\Pi^2_1$ formula $\varphi$ such that ZFC proves that $\exists A\subseteq\mathbb{R}\varphi(A)$ iff $X^\#$ exists for all sets of reals $X$. Assume ZFC + $X^\#$ exists for all sets of reals $X$. Let $A$ witness the $\Sigma^2_2$ statement, and let $A'=(A,W)$ where $W$ is a wellorder of $\mathbb{R}$. Consider $M=L(\mathbb{R},A')$. Then $M\models$ZFC, and $A\in M$, and $\mathbb{R}\subseteq M$, so note the truth of $\varphi(A)$ goes down to $M$. So $M\models\mathrm{ZFC}+V=L(\mathbb{R},A')$+$\exists A\subseteq\varphi(A)$, so models "$(A')^\#$ exists", but this is a contradiction.

$\endgroup$
3
  • 1
    $\begingroup$ Remark: The statement follows from the existence of a measurable cardinal. $\endgroup$
    – Farmer S
    Aug 18, 2021 at 13:01
  • $\begingroup$ Thanks for this cool example, but unfortunately, because the statement follows from the existence of a measurable cardinal, it doesn't meet my requirements. $\endgroup$ Aug 18, 2021 at 13:18
  • $\begingroup$ Oh, yes, I wasn't thinking about that condition. $\endgroup$
    – Farmer S
    Aug 18, 2021 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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