How to show that Second Order Logic is more expressive than Weak Second Order Logic

Question

Im following the definitions from the book Mathematical Logic by Ebbinghaus.

Definition of Second Order Logic

Definition of Weak Second Order Logic

Definition of 'Expressiveness'

I'm trying to show that $\mathscr{L}_{\rm II}^w \leq \mathscr{L}_{\rm II}$. To do this, by the above definitions we need to show that for every symbol set $S$ and sentence $\phi\in L_{\rm II}^w(S)$, there is a sentence $\psi\in L_{\rm II}(S)$ such that ${\rm Mod}^S_{\mathscr{L}_{\rm II}^w}(\phi) = {\rm Mod}^S_{\mathscr{L}_{\rm II}}(\psi)$, i.e., for all $S$-structure $\mathfrak{A}$ we have that $\mathfrak{A}\vDash_{\mathscr{L}_{\rm II}^w} \phi$ iff $\mathfrak{A}\vDash_{\mathscr{L}_{\rm II}} \psi$.

I thought about by induction on the structure of $\phi$ because if $\phi \equiv \exists X\phi'$, then

\begin{align*} \mathfrak{A}\vDash_{\mathscr{L}_{\rm II}^w} \exists X\phi' & \text{ iff there is a finite $C\subseteq A^n$ such that } \mathfrak{A}_{\frac{C}{X}}\vDash_{\mathscr{L}_{\rm II}^w} \phi' \qquad (\text{by definition})\\ & \text{ iff there is a finite $C\subseteq A^n$ such that } \mathfrak{A}_{\frac{C}{X}}\vDash_{\mathscr{L}_{\rm II}} \psi' \qquad (\text{by I.H.})\\ & \Rightarrow \mathfrak{A}\vDash_{\mathscr{L}_{\rm II}} \exists X\psi'. \end{align*}

The problem is when we try to prove the converse since $\mathfrak{A}\vDash_{\mathscr{L}_{\rm II}} \exists X\psi'$ provides us an arbitrary subset $C\subseteq A^n$ that may not be finite.

Answer 1

The translation is indeed slightly more complicated than what you're setting up.

The point is that SOL can express that a given set is finite$^1$. This lets us set up the quantifier clause for our translation as $$(\exists X\varphi)'=\exists X[X\mbox{ is finite}\wedge \varphi'].$$

---

$^1$This actually has a slight subtlety. If we assume the axiom of choice, then "$X$ is finite" is equivalent to "$X$ has no non-surjective self-injection" (called Dedekind-finiteness), which is clearly SOL-expressible. On the other hand, it's consistent with set theory without choice that there are Dedekind-finite infinite sets. So if we want an approach that works without the axiom of choice, more care is needed. Since this is a cute puzzle, I've spoilered a solution:

"$X$ is finite" is equivalent to "There is a binary relation on $X$ which is both a well-ordering and a co-well-ordering." Alternatively, you could just say "$X$ is Dedekind-finite and well-orderable." (If you're interested in the complexity of choiceless characterizations finiteness, see the discussion here.)