# On the strength of higher-logic analogues of $\mathsf{ZFC}$ + Montague's Reflection Principle

Throughout, I work in $$\mathsf{MK}$$ in order to be able to conveniently quantify over logics; if one prefers, we can restrict attention to (say) $$\Sigma_{17}$$-definable logics and work in $$\mathsf{ZFC}$$. By "logic" I mean "regular logic containing $$\mathsf{FOL}$$ and having countably many formulas in a finite language" (for example, $$\mathsf{SOL}$$).

Given a logic $$\mathcal{L}$$, consider the following two $$\mathcal{L}$$-theories $$\mathscr{ZFC}(\mathcal{L})$$ and $$\mathscr{M}(\mathcal{L})$$ defined as follows. We let $$\mathscr{ZFC}(\mathcal{L})$$ be the $$\mathcal{L}$$-theory consisting of

• the "boring" $$\mathsf{ZFC}$$-axioms Pairing, Union, Infinity, Choice, Regularity, and Extensionality, and

• the Separation and Replacement schemes modified to allow formulas coming from $$\mathcal{L}$$.

Note that $$\mathscr{ZFC}(\mathsf{SOL})$$ is not quite the same thing as "second-order $$\mathsf{ZFC}$$." Meanwhile, $$\mathscr{M}(\mathcal{L})$$ is $$\mathscr{ZFC}(\mathcal{L})$$ plus for each $$\mathcal{L}$$-formula $$\varphi(x)$$ the reflection instance $$\forall x[\varphi(x)\rightarrow\exists \alpha(x\in V_\alpha\wedge \varphi(x)^{V_\alpha})].$$

It's easy to state and prove in (first-order!) $$\mathsf{MK}$$ that $$V_\alpha\models\mathscr{ZFC}(\mathcal{L})$$ for every logic $$\mathcal{L}$$ whenever $$\alpha$$ is inaccessible; somewhat conversely, assuming $$\mathsf{V=L}$$ this is optimal already for $$\mathcal{L}=\mathsf{SOL}$$ since $$V_\alpha\models_\mathsf{SOL}\mathscr{ZFC}(\mathsf{SOL})$$ only if $$\alpha$$ is $$L$$-inaccessible.

The situation for $$\mathscr{M}$$ is more complicated. For example, if $$\alpha$$ is the least inaccessible then $$V_\alpha\not\models_\mathsf{SOL}\mathscr{M}(\mathsf{SOL})$$ since the sentence "$$\mathsf{Ord}$$ is inaccessible" is second-order expressible and holds in $$V_\alpha$$ but not in any smaller $$V_\beta$$. Instead, we need to go a bit higher. Say that a cardinal $$\kappa$$ is chromatic iff $$\kappa$$ is an inaccessible limit of inaccessibles and the following holds (letting $$I$$ be the set of inaccessibles $$\le\kappa$$):

For every family $$C=(c_i)_{i\in\omega}$$ of $$2$$-colorings $$c_i: [I]^2\rightarrow 2$$, there is some $$\lambda\le\kappa$$ such that for all inaccessible $$\alpha<\lambda$$ and all $$i\in\omega$$ with $$c_i(\{\alpha,\lambda\})=1$$ there is some $$\beta\in(\alpha,\lambda)$$ with $$c_i(\{\alpha,\beta\})=1$$.

If $$\kappa$$ is a chromatic cardinal, then for every countable logic $$\mathcal{L}$$ there is a $$\lambda<\kappa$$ such that $$V_\lambda\models_\mathcal{L}\mathscr{M}(\mathcal{L})$$. Basically, for a given $$\mathcal{L}$$ with formulas $$(\varphi_i)_{i\in\omega}$$ and inaccessible cardinals $$\alpha<\beta<\kappa$$ we let $$c_i(\{\alpha,\beta\})=1$$ iff $$V_\beta\models\varphi(\alpha)$$. And essentially trivially, this is optimal.

My first question is about chromaticity itself:

Question 1: What are chromatic cardinals in more familiar language?

I suspect chromaticity is much weaker than Mahlo-ness, but I don't immediately see how to prove that.

My second question is about the specific strength of the second-order analogue of $$\mathsf{ZFC}$$ + reflection as indicated above:

Question 2: What is the consistency strength of "There is an inaccessible $$\alpha$$ such that $$V_\alpha\models_\mathsf{SOL}\mathscr{M}(\mathsf{SOL})$$"?

It's easy to see that this is weaker than the existence of a chromatic cardinal; I'm interested in getting a better sense of how much weaker it is.

• Your “not quite the same thing as second-order ZFC” links to another question which itself links to another question in which I think the relevant part is a muddled discussion in the comments to the question. This is a bit hard to follow and nothing is said clearly. So, even if it's not directly germane to the present question, could you add a footnote (here, or to one of the linked questions) briefly explaining the difference between “ZFC with Separation and Replacement schemes modified to allow formulas of second-order logic” and “second-order ZFC” because I thought they were the same? 🙏 Sep 24, 2022 at 20:58
• @Gro-Tsen Second-order $\mathsf{ZFC}$ has the second-order powerset axiom and the second-order (single-sentence) replacement axiom, and is stronger than the first logic asked about in this question. In particular, set models of second-order $\mathsf{ZFC}$ are (up to isomorphism) just the $V_\kappa$s for $\kappa$ strongly inaccessible, whereas the class of models of $\mathfrak{ZFC}(\mathsf{SOL})$ is significantly harder to describe. Sep 24, 2022 at 21:00
• @Gro-Tsen (Sorry, "$\mathfrak{ZFC}$" should be "$\mathscr{ZFC}$" in my previous comment.) See also the first part of this old MSE answer of mine. Sep 24, 2022 at 21:09
• Aaaaah, you're saying “second-order ZFC” has versions of Separation and Replacement where instead of having a scheme over all (first-order) formulas we have a single axiom with the scheme replaced by a second-order quantification; whereas here you consider a scheme over all second-order formulas. Right? But I still fail to see why they're not equivalent: doesn't second-order comprehension ensure that anything we can write with a second-order formula define a second-order object, and conversely, any second-order object can be considered as a single-variable formula? Sep 24, 2022 at 21:24
• Ah wait, when you write a scheme ranging over second-order formulas, do you allow second-order parameters in the formulas in the scheme, which are then outwardly universally quantified just like the first-order parameters are? Sep 24, 2022 at 21:25

The first chromatic cardinal is the first Mahlo cardinal. (Per the connection with the reflection in the question, I assume that in the definition, $$α$$ and the first argument of $$c_i$$ need not be inaccessible.) If we allowed $$c_i$$ for $$i≤δ$$, then the first chromatic cardinal would be the first Mahlo above $$δ$$.
If $$κ$$ is Mahlo, then it is chromatic. Define club $$C⊆κ$$ with $$λ∈C ⇔ ∀α<λ \, ∀i \, \min(\{β>α:c_i(α,β)\})<λ$$ where $$\min(S)$$ is modified to return 0 if $$S$$ is empty. Then any inaccessible $$λ∈C$$ satisfies the desired property.
In the other direction, if $$κ$$ is below the first Mahlo, then there is a one-to-one function that for every inaccessible below $$κ$$ returns a smaller ordinal. For example, pick a club $$D$$ that excludes inaccessibles. If $$β$$ is the least inaccessible above some element of $$D$$, then set $$f(β)=\max(β∩D)$$. Let $$λ=\min(D\setminus β)$$, and if there are inaccessibles in $$(β,λ)$$, let $$λ'$$ be largest inaccessible or limit of inaccessibles $$<λ$$. Set (for example) $$f(λ')=β$$, and analogously to $$D$$ pick a club $$E⊂λ'$$ above $$β$$ that excludes inaccessibles. Analogously proceed by recursion until all inaccessibles are taken care of.
For your second question, despite the power of second order logic, the cardinals in question are precisely inaccessible $$α$$ with $$V_α ≺_{Σ_{1,V}} L_1(V_{α+1})$$, where $$Δ_{0,V}$$ formulas allow querying about $$x$$ whether $$∃α \, x=V_α$$ (for the true $$V$$), and $$L$$ is the constructible hierarchy. $$Σ_{1,V}$$ formulas are upwards absolute, and $$L_1$$ corresponds to definability, so the above reduces to the desired reflection relation. If there is an inaccessible $$λ$$ with $$V_λ ≺_{Σ_2} V$$, then $$α$$ for the question exists for every parameter-free definable $$Δ^V_2$$ logic (even if there are no Mahlos in $$V$$; also, we can allow parameters in $$V_λ$$).
• Sorry, I'm retroactively confused about something. Why are $\Sigma_{1,V}$ formulas upwards absolute? If I understand correctly, even $\Delta_{0,V}$ formulas won't be upwards absolute in general, since being a level of $V$ is not upwards-absolute. Am I missing something? Nov 29, 2022 at 18:06
• @NoahSchweber In the answer, I (perhaps nonstandardly) used $Σ_{1,V}$ to refer to levels of the true $V$ rather than $V$ in the model, but this does not actually matter for $V_α ≺_{Σ_{1,V}} L_1(V_{α+1})$. Nov 30, 2022 at 3:05