5
$\begingroup$

I'm looking for the following:

(1) an example of a $\Pi^1_1$ class-theoretic sentence that has no known equivalence to a $\Sigma^1_1$ sentence, even if large cardinal hypotheses or reflection principles are assumed.

(2) an example of a $\Pi^1_2$ class-theoretic sentence that has no known equivalence to a $\Sigma^1_2$ sentence, even if large cardinal hypotheses or reflection principles are assumed.

Admttedly, "large cardinal hypothesis" and "reflection principle" are not well-defined, so these questions are rather vague.

I am assuming impredicative Comprehension (Kelley-Morse class theory) and all forms of choice.

The best answer I currently have for (1) is Vopenka's principle ("every proper class of directed graphs has either a member with a nontrivial endomorphism or two distinct members with a homomorphism between them"). But this is often considered a large cardinal hypothesis, so it's not a good answer.

I don't have any answer for (2).

$\endgroup$
5
  • 1
    $\begingroup$ This question is about second-order set theory. I recently asked a similar question about second-order arithmetic, and another one about third-order arithmetic. $\endgroup$ Sep 2, 2021 at 22:09
  • 3
    $\begingroup$ Global Choice is $\Sigma^1_1$. If $\mathsf{GBc}$ proves it is $\Pi^1_1$, then it is absolute between models of $\mathsf{GBc}$ with the same sets. However, every model of $\mathsf{GBc}$ is contained in a model, whose sets are the same with the original model, of $\mathsf{GBc}$ with Global Choice. Hence every model of $\mathsf{GBc}$ satisfies Global Choice, and so $\mathsf{GBc}$ proves Global Choice, a contradiction. $\endgroup$
    – Hanul Jeon
    Sep 2, 2021 at 22:32
  • $\begingroup$ Thanks @Hanul Jeon, but I want to assume all forms of choice. I've edited the question to make that clear. $\endgroup$ Sep 2, 2021 at 22:56
  • 1
    $\begingroup$ To remove ambiguity about what choice, reflection, and large cardinal principles are, it might be easier to work in an ambient model of ZFC and ask about models of the form $(V_{\kappa}, V_{\kappa+1}),$ where $\kappa$ is assumed to have large cardinal properties. $\endgroup$ Sep 3, 2021 at 3:34
  • $\begingroup$ What about „There is a wellorder of the classes which is $\Pi^1_1$-definable in a set parameter“, where „wellorder“ is just in the internal sense that there is no class coding a strictly descending $\omega$-sequence? This is $\Pi^1_2$, and I don’t see an easy way to express it in $\Sigma^1_2$, though I‘m not sure. It is consistent with multiple Woodin cardinals, as it holds in the context mentioned by @ElliotGlazer mentioned above, if the background universe is a short extender mouse, and $\kappa$ inaccessible there. $\endgroup$
    – Farmer S
    Sep 3, 2021 at 10:14

2 Answers 2

4
$\begingroup$

Much as described by @ElliotGlazer above, let's consider the question for models of the form $(V_\kappa,V_{\kappa+1})$, assuming ZFC in the background, considering all such where $\kappa$ is inaccessible in the background.

Then with respect to this particular class of models, a $\Pi^1_2$, non-$\Sigma^1_2$ statement is "There is a wellorder of the proper classes, which $\Pi^1_1$-definable from some set parameter". (However, the proof that it is not $\Sigma^1_2$ breaks if we replace "inaccessible" with "weakly compact", and I don't know what the situation is if we do this.)

For $\Pi^1_2$ it is a direct computation: First, note that set-quantifiers are absorbed by class quantifiers, so we can say the "There is a $\Pi^1_1$ formula $\varphi$ and set parameter $p$" at the front. Then just say that $\varphi(p,X,Y)$ defines a strict linear order $<^*$ of the classes, and for every class $C$ coding a sequence $\left<C_n\right>_{n<\omega}$ of classes, there is $n<\omega$ such that $\neg(C_{n+1}<^*C_n)$.

If $V=L$ is the background universe, there is such a wellorder of $V_{\kappa+1}$. For given $X,Y\subseteq V_\kappa$, just say "For every set $Z\subseteq V_\kappa$ coding a model $M$ satisfying ZF$^-$ + "$\kappa$ is the largest cardinal" with $V_\kappa\cup\{X,Y\}\subseteq M$, we have $M\models$"$X<_LY$". (We automatically get wellfoundedness of $M$, using the inaccessibility of $\kappa$ in $L$.) This generalizes to when $V$ is a short extender premouse which is iterable in some larger universe, so it is consistent with many Woodin cardinals.

Now let us show that the statement is not equivalent to a $\Sigma^1_2$ (uniformly in the context mentioned above). For suppose it is, with $\Sigma^1_2$ formula $\psi$. Force over the background universe to add a Cohen subset $X\subseteq\kappa$ (i.e. with conditions of size ${<\kappa}$). Then $V_\kappa^{V[X]}=V_\kappa^V$, and if $A\in V_{\kappa+1}$ and $\varphi$ is $\Pi^1_1$ and $(V_\kappa,V_{\kappa+1})\models\varphi(A)$, then $(V_\kappa,V_{\kappa+1}^{V[X]})\models\varphi(A)$. (This is a standard fact: letting $\neg\varphi(A)$ be $\exists B\subseteq V_\kappa\ [\varrho(B,A)]$ where $\varrho$ is $\Sigma^1_0$, and $\tau$ be a name for a witness, working in $V$, where the forcing is $\kappa$-closed, we can construct a filter $G$ which meets enough sets that $B=\tau_G\in V$ also witnesses the statement, a contradiction.) Therefore $\Sigma^1_2$ truth also goes up to $V[X]$, so $(V_\kappa,V_{\kappa+1}^{V[X]})\models\psi$. So we have a wellorder of $V_{\kappa+1}^{V[X]}$ which is definable over $V[X]$ from a parameter in $p\in V_\kappa\subseteq V$, but then by homogeneity of the forcing, we get $X\in V$, a contradiction.

Remark (correcting remark in earlier version): If we started with $V=L$, then $\kappa$ is not weakly compact in $V[X]$.


(Edit): For $\Pi^1_1$: Consider the statement $\psi$, which says "There are stationarily many ordinals $\alpha$ such that $2^{\alpha^+}>\alpha^{++}$". This is $\Pi^1_1$, but I claim that if a Mahlo cardinal is consistent then it is not $\Sigma^1_1$ w.r.t. inaccessibility, i.e. in the sense above. (But like in the $\Pi^1_2$ case, I don't know about w.r.t. higher large cardinal properties for $\kappa$.)

(Remark: An earlier version had a gap in the argument regarding the value of $2^{\alpha^+}$ in $L[G]$ for singular cardinals $\alpha$. It is filled in now.)

For suppose $\kappa$ is Mahlo, hence Mahlo in $L$. Force over $L$ to arrange that in $L[G]$, $\kappa$ is Mahlo, $2^{\alpha}\leq\alpha^{++}$ for all $\alpha<\kappa$, the set $T_{++}$ of inaccessibles $\alpha<\kappa$ such that $2^{\alpha^+}=\alpha^{++}$ is stationary, and the set $T_{+++}$ of inaccessibles $\alpha<\kappa$ such that $2^{\alpha^+}=\alpha^{+++}$ is also stationary, and $2^{\alpha^+}=\alpha^{++}$ for singular cardinals $\alpha<\kappa$. For this, first partition the inaccessibles $\alpha<\kappa$ into disjoint stationary sets $T_{++},T_{+++}$. Then force with Easton support product $\mathbb{P}$ of forcings $\mathbb{P}_\alpha$ for $\alpha\in T_{+++}$, where $\mathbb{P}_\alpha$ adds $\alpha^{+++}$ many Cohen subsets of $\alpha^+$, with conditions of size $\alpha$, in the usual way.

Claim: $\mathbb{P}$ preserves all cardinals and cofinalities, and in $L[G]$, we have $2^{\alpha^+}=\alpha^{++}$ for all singular cardinals $\alpha$ and all $\alpha\in T_{++}$, and $2^{\alpha^+}=\alpha^{+++}$ for all $\alpha\in T_{+++}$; therefore $L$ and $L[G]$ also have the same inaccessible cardinals $<\kappa$. Also, $\mathbb{P}$ is $\kappa$-cc, and then it follows that for every club $C\subseteq\kappa$ with $C\in L[G]$, there is a sub-club $D\subseteq C$ with $D\in L$, and therefore $\mathbb{P}$ preserves stationarity for subsets of $\kappa$, and $\kappa$ is Mahlo in $L[G]$.

Proof: These are standard calculations, but here we go: For $\beta<\kappa$, write $\mathbb{P}\upharpoonright\beta$ for the restriction of the product to indices $\alpha\in T_{+++}\cap\beta$, and $G\upharpoonright\beta$ for the corresponding generic, and likewise $\mathbb{P}\upharpoonright[\beta,\kappa)$ to indices $\alpha\in T_{+++}\cap[\beta,\kappa)$, etc. So $\mathbb{P}\cong(\mathbb{P}\upharpoonright\beta)\times(\mathbb{P}\upharpoonright[\beta,\kappa))$. Note that $\mathbb{P}\upharpoonright[\beta,\kappa)$ is $(\beta+1)$-closed, so does not change $\mathcal{H}_{\beta^+}$, and in particular does not collapse $\beta$ (or $\beta^+$). Now $L[G]=L[G\upharpoonright[\beta,\kappa)][G\upharpoonright\beta]$. Suppose $\beta$ is regular in $L$. We want to see that $\beta$ is regular in $L[G]$. If $\beta$ is inaccessible in $L$ then as the product is Easton and by GCH, $\mathbb{P}\upharpoonright\beta$ has cardinality $\beta$ in $L$ and is $\beta$-cc in $L$, and hence also has these properties in $L[G\upharpoonright[\beta,\kappa)]$ (since these properties only depend on $\mathcal{H}_{\beta^+}$), and therefore $\beta$ is still regular in $L[G]$. So suppose $\beta=\gamma^+$ where $\gamma$ is an $L$-cardinal. We may assume that $\mathbb{P}\upharpoonright\beta$ has cardinality $\geq\beta$ in $L$. If there is an $L$-inaccessible $\delta$ such that $\beta<(\delta^{+\omega})^L$ just factor at $\delta$, using that $\mathbb{P}\upharpoonright\delta$ has cardinality $\delta$ in $L$ and $\Delta$-system calculations to see $\beta$ remains regular. Otherwise, we get that $\gamma$ is a singular limit of inaccessibles in $L$ and $\beta=\gamma^{+L}$ is the cardinality of $\mathbb{P}\upharpoonright\gamma$ in $L$. We may assume that $\beta$ is the least $L$-regular such that $\xi=\mathrm{cof}^{L[G]}(\beta)<\beta$. So $\xi$ is an $L$-regular and $\xi<\gamma<\beta$. But now we can factor $\mathbb{P}$ into $(\mathbb{P}\upharpoonright\xi)\times(\mathbb{P}\upharpoonright[\xi,\kappa))$. Since $\mathbb{P}\upharpoonright[\xi,\kappa)$ is $(\xi+1)$-closed in $L$, we get $L[G\upharpoonright[\xi,\kappa)]\models$"$\mathrm{cof}(\beta)\neq\xi$", and also by the minimality of $\beta$, all $L$-regulars $<\gamma$ are still regular in $L[G]$, hence also in $L[G\upharpoonright[\xi,\kappa)]$, and all $L$-inaccessibles $<\gamma$ are still inaccessible in both models, so $\mathbb{P}\upharpoonright\xi$ has cardinality $<\beta$ in $L$ and in $L[G\upharpoonright[\xi,\kappa)]$. So if $\beta$ is regular in $L[G\upharpoonright[\xi,\kappa)]$, then it is still regular in $L[G]$, a contradiction. So there must be $\beta'\in(\xi,\beta)$ such that $\beta$ has cofinality $\beta'$ in $L[G\upharpoonright[\xi,\kappa)]$. But then $\beta'$ is regular in $L$ and $\mathrm{cof}^{L[G]}(\beta')=\mathrm{cof}^{L[G]}(\beta)=\xi<\beta'$, contradicting the minimality of $\beta$.

So we have preservation of cardinals, cofinalities, and inaccessibles $<\kappa$; also the fact that $\mathbb{P}$ is $\kappa$-cc is as above, so $\kappa$ remains inaccessible. It follows immediately that for $\alpha\in T_{+++}$, $L[G]\models 2^{\alpha^+}\geq\alpha^{+++}$. To see $L[G]\models$"$2^{\alpha^+}\leq\alpha^{+++}$" for all $\alpha<\kappa$, and $L[G]\models$"$2^{\alpha^+}=\alpha^{++}$" for $\alpha\in T_{++}\cup S$, where $S$ is the set of singular cardinals $<\kappa$, use cardinality calculations and factoring as above. (If $\gamma\in T_{++}\cup S$, then $\mathbb{P}\upharpoonright\gamma$ has cardinality $\leq\gamma^{+L}$ in $L$, and since $\gamma\notin T_{+++}$, factoring at $\gamma$ therefore does the job.)

So $V_{\kappa+1}^{L[G]}\models\psi$. Now suppose $\psi$ is equivalent to a $\Sigma^1_1$ statement $\varphi$ w.r.t. inaccessibility, and $\varphi=\exists A\subseteq V_\kappa\ \varrho(A)$, where $\varrho$ has only set quantifiers. Since $L[G]\models\psi$ + "$\kappa$ is Mahlo" (hence inaccessible), we get $V_{\kappa+1}^{L[G]}\models\varphi$, so fix a witness $A\in L[G]$.

Now force over $L[G]$ to add a club subset of $T_{++}\cup S$, with conditions $p$ being closed subsets of $T_{++}\cup S$, ordered by extension. Note $T_{+++}$ is disjoint from $T_{++}\cup S$. It is shown in Jech/Woodin "Saturation of the closed unbounded filter on the set of regular cardinals" that this forcing is $\kappa$-distributive, so adds no $<\kappa$-sequences (the proof is easy: for each regular cardinal $\lambda<\kappa$, there is a dense subset of the forcing which is $\lambda$-closed: consider the set of conditions $p$ with $\sup p>\lambda$). Let $C$ be the generic club. Then we get $V_\kappa^{L[G,C]}=V_\kappa^{L[G]}$ and $\kappa$ is inaccessible in $L[G,C]$. However, because $C\subseteq T_{++}\cup S$, and since $V_\kappa$ was preserved, we get $L[G,C]\models$"$2^{\alpha^+}=\alpha^{++}$" for all $\alpha\in C$, and therefore $L[G,C]\models\neg\psi$. But also because $V_\kappa$ was preserved, $\Sigma^1_1$ truth passes upward from $L[G]$ to $L[G,C]$, so $L[G,C]\models\varphi$. Since $\kappa$ is inaccessible in $L[G,C]$, this is a contradiction.

$\endgroup$
9
  • $\begingroup$ Thanks @FarmerS. Just to be clear, there's no large cardinal hypothesis on $\kappa$ for which this statement is known to be $\Sigma^1_2$? I'm not asking for proof that it isn't $\Sigma^1_2$. $\endgroup$ Sep 3, 2021 at 20:09
  • 1
    $\begingroup$ I don't know. - $\endgroup$
    – Farmer S
    Sep 3, 2021 at 20:29
  • 1
    $\begingroup$ The same argument works for „$\kappa$ is Woodin“, or any $\Pi^1_1$ strengthening of inaccessibility. $\endgroup$
    – Farmer S
    Sep 3, 2021 at 20:39
  • $\begingroup$ This seems to answer (2) then. Does anyone have a suggestion for (1), please? $\endgroup$ Sep 3, 2021 at 21:23
  • 1
    $\begingroup$ @PaulBlainLevy That's implied by Vopenka's principle, since SCH holds above a strongly compact cardinal. $\endgroup$ Sep 17, 2021 at 4:44
4
$\begingroup$

Let's work in GBC for definiteness. In analogy with combinatorics on $\omega_1$, define an $\mathsf{ORD}$-tree to be a (proper class sized) tree of height $\mathsf{ORD}$ so that each level is set sized. Such a tree is Souslin if all of its chains and antichains are set sized as well.

By essentially the same arguments as in the case of any regular $\kappa$, the class-sized forcing consisting of normal binary trees ordered by end-extension adds an $\mathsf{ORD}$-Souslin tree generically while preserving GBC (and KM if it held in the ground model). Moreover the forcing does not add sets so it cannot change any first order property of the model.

Conversely, in unpublished work, Joel David Hamkins and I discovered that any countable model of GBC has an expansion with the same first order part satisfying GBC plus ``there are no $\mathsf{ORD}$-Souslin trees". This model won't satisfy KM even if it held in the ground model, for what it's worth.

The point being, similar to the case of any regular $\kappa$, the existence of an $\mathsf{ORD}$-Souslin tree is independent of GBC and neither the existence of such a tree nor the non-existence of such a tree has any first order consequences over GBC as a base theory.

Now, for a fixed $\mathsf{ORD}$-tree $T$, to say that "$T$ is Souslin" is a $\Pi^1_1$ statement (with $T$ as a parameter of course) since we're really saying ``for all $A \subseteq T$ if $A$ is a chain or an antichain then it is set sized". It's also properly $\Pi^1_1$. If it were equivalent to a $\Sigma^1_1$ sentence then it would be absolute to class-forcing extensions preserving GBC (or KM if that's your ground model theory). But, since we can add a class-sized branch (and antichain) by forcing with $T$, just like in the case on $\omega_1$ this is not true. Some work is needed to show that forcing with the tree preserves GBC/KM but this is in fact true and is essentially a consequence of the fact that the tree is $\mathsf{ORD}$-c.c. and adds no sets.

It follows that to say, for a fixed $\mathsf{ORD}$-tree $T$ that "$T$ is not Souslin" is properly $\Sigma^1_1$.

Clearly we have that to say "there is an $\mathsf{ORD}$-Souslin tree" is $\Sigma^1_2$. I would assume, given the above that it is properly so, but I haven't been able to dot the i's and cross the t's on such a proof.

$\endgroup$
10
  • $\begingroup$ Thanks! Another nice answer for (2). And it has the advantage of not referring to syntax. $\endgroup$ Sep 7, 2021 at 22:50
  • $\begingroup$ But (1) is still unresolved. I'm looking for a sentence, so parameters are excluded. $\endgroup$ Sep 7, 2021 at 22:52
  • 1
    $\begingroup$ But don't large cardinal properties of $\mathrm{Ord}$ prove there is such a satisfaction class? $\endgroup$
    – Farmer S
    Sep 9, 2021 at 17:24
  • 1
    $\begingroup$ I'm pretty sure KM proves that for every $X$ there is a satisfaction class for the language expanded by $X.$ It certainly holds for $(V_{\kappa}, V_{\kappa+1}),$ $\kappa$ inaccessible. $\endgroup$ Sep 9, 2021 at 20:08
  • 1
    $\begingroup$ True, it looks like KM is enough. $\endgroup$
    – Farmer S
    Sep 9, 2021 at 21:05

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.