3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Perhaps I've misunderstood, but isn't the answer easily yes? You can express that $\phi$ has exactly $n$ realizers by saying: there is a class $Y$ coding a list of $n$ classes (for example, $Y$ consists of codes of pairs $\langle i,x\rangle$ where $i<n$) such that for each of them $Y_i$ fulfills $\phi$, they are different, and every class fulfilling $\phi$ is one of them. So we can say that $\phi$ and $\psi$ have the same number of realizers just by saying that either there is some $n$ such that they both have exactly $n$ realizers, or for every $n$, neither has exactly $n$ realizers.

If you don't blur the distinction between different infinities, then the answer can be negative. To see this, let $\phi(X)$ be $X=X$, and let $\psi(X)$ assert that $X$ is in $L$, which is expressible in second-order arithmetic. The number of $X$ with $\phi$ is equal to the number of $X$ with $\psi$ just in case the power set of $\mathbb{N}$ is equinumerous with $\omega_1^L$. If we consider the Cohen model $L[G]$ in which CH fails, these cardinalities are different. But by collapsing the continuum to $\omega_1$ again, we make the cardinals the same, without adding any reals, and therefore without changing the truth of any assertion in second-order arithmetic. So we cannot express equi-cardinality in that logic.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yup, that was easy! Thanks for your patience. $\endgroup$
    – Alexander Pruss
    Commented Dec 11 at 21:25
  • 1
    $\begingroup$ And I assume that on the other hand if the continuum hypothesis holds, we can express equicardinality, since we can encode a countable sequence of subsets of the naturals as a set of naturals? $\endgroup$
    – Alexander Pruss
    Commented Dec 12 at 19:50
  • $\begingroup$ Yes, that is right. You can express countability directly, in the style of my answer, and so if there is only one other cardinality, then you can also express that. If CH fails, however, then we cannot (provably) express the different cardinalities, since forcing can make them the same without adding reals and therefore without changing second-order arithmetic. $\endgroup$
    – Joel David Hamkins
    Commented Dec 12 at 23:08
  • 1
    $\begingroup$ Thanks again. I suppose there is still one question in the neighborhood: are there any models where CH fails and where SOA can nonetheless express equicardinality? It would be a neat thing if SOA could express equicardinality iff CH was true. $\endgroup$
    – Alexander Pruss
    Commented Dec 13 at 15:08
  • $\begingroup$ Good question! However, if the perfect set property holds for every uncountable projective set (this is a consequence of PD), then every definable set you are talking about would be either countable or size continuum, in which case equicardinality would be expressible, but CH needn't hold. $\endgroup$
    – Joel David Hamkins
    Commented Dec 13 at 18:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .