Skip to main content
5 of 5
Removed parenthetical note as it wasn't correct: expressibility of uncountability over MSO(N,<) does not obviously imply expressibility of uncountability over SOA, as the latter has more formulas.

Can one say that there are equal numbers of sets satisfying formulas in Second Order Arithmetic?

Is there a way of saying in second order arithmetic that the number of sets $X$ such that $\phi$ equals the number of sets $X$ such that $\psi$, where $\phi$ and $\psi$ are formulas with $X$ free, and where we don't care about the distinction between different infinite cardinalities (i.e., number is something in $\omega$ or $+\infty$)?

We can define the concept of there being finitely many $X$ such that $\phi$ in second order logic (or more generally monadic second order logic with an infinity predicate for sets) using the trick in the proof of Proposition 7 of Bárány, Kaiser, and Rabinovich - Expressing cardinality quantifiers in monadic second-order logic over chains, so the only interesting case is where $\phi$ and $\psi$ both have finite numbers of satisfiers.