Skip to main content
3 of 5
Name of "here"
LSpice
  • 12.9k
  • 4
  • 45
  • 69

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.