Is infinitary first-order logic strictly more expressive than weak second-order logic?

Question

Let $\mathcal{L}_{\omega_1 \omega}$ be infinitary first-order logic (i.e. first-order logic with countable disjunctions and conjunctions), and let $\mathcal{L}_{II}^w$ be 'weak' second-order logic, i.e. second-order logic where the second-order quantifiers are interpreted as ranging over only finite subsets and relations of the domain of a structure.

I have proved that $\mathcal{L}_{\omega_1 \omega}$ is at least as expressive as $\mathcal{L}_{II}^w$ (written: $\mathcal{L}_{II}^w \leq \mathcal{L}_{\omega_1 \omega}$), in the sense that if $S$ is any symbol set and $\varphi$ is any $\mathcal{L}_{II}^w(S)$-sentence, then there is a $\mathcal{L}_{\omega_1 \omega}(S)$-sentence $\varphi'$ with the same models: i.e. if $\mathfrak{A}$ is any $S$-structure, then $\mathfrak{A} \models_w \varphi$ iff $\mathfrak{A} \models \varphi'$ (where $\models_w$ is the satisfaction relation for $\mathcal{L}_{II}^w$).

I am now wondering whether the converse is also true: i.e. are $\mathcal{L}_{\omega_1 \omega}$ and $\mathcal{L}_{II}^w$ equally expressive, or is $\mathcal{L}_{\omega_1 \omega}$ strictly more expressive than $\mathcal{L}_{II}^w$? I have a very weak intuition that $\mathcal{L}_{\omega_1 \omega}$ will be strictly more expressive, because it seems intuitively false that a countably infinite disjunction of weak second-order formulas will (in general) be equivalent to a single weak second-order formula. However, I do not yet see how to prove this (if it is even true).

One difficulty in deciding whether $\mathcal{L}_{\omega_1 \omega} \leq \mathcal{L}_{II}^w$ is that both logics satisfy (or fail to satisfy) many of the same properties: in particular, they both satisfy the downward Lowenheim-Skolem theorem (for individual sentences), and they both fail to satisfy the compactness theorem. I have yet to personally come across a significant property that distinguishes them.

If a solution to the problem of whether $\mathcal{L}_{\omega_1 \omega} \leq \mathcal{L}_{II}^w$ is known, I would greatly appreciate a hint (rather than a full solution, unless the solution is too complex or unintuitive to be easily reached by just a hint). Thanks!

Answer 1

To avoid a triviality, I'll restrict to finite signatures below. In an infinite signature we get a silly affirmative answer, since we can whip up an $\mathcal{L}_{\omega_1,\omega}$-sentence saying something about infinitely many symbols while $\mathcal{L}_{II}^w$-sentences can only use finitely many symbols.

---

Your suspicion is right: $\mathcal{L}_{\omega_1,\omega}$ is vastly stronger than $\mathcal{L}_{II}^w$. There are a few ways to tackle this.

One way to do this is note that $\mathcal{L}_{II}^w$ satisfies in fact the full downward Lowenheim-Skolem theorem, while $\mathcal{L}_{\omega_1,\omega}$ does not. But neither of those points is really trivial, and in fact there's a purely elementary argument.

Specifically, we prove the following:

There is a size-$2^{\aleph_0}$ set $\mathfrak{S}$ of structures such that each structure in $\mathfrak{S}$ is described up to isomorphism by a single $\mathcal{L}_{\omega_1,\omega}$-sentence.

(In fact much more is true - every countable structure is pinned down up to isomorphism by some $\mathcal{L}_{\omega_1,\omega}$-sentence - but that's a serious theorem.)

If we can prove this we'll be done since there are only countably many $\mathcal{L}_{II}^w$-sentences in the first place. Really, all we need to do here is computing the essential cardinality of $\mathcal{L}_{\omega_1,\omega}$ - that is, the number of $\mathcal{L}_{\omega_1,\omega}$-sentences up to logical equivalence - but we might as well prove this even stronger fact.

In case it's hard to see how to start this, here's a hint:

Note that there's a single $\mathcal{L}_{\omega_1,\omega}$-sentence $\eta$ describing $(\mathbb{N};1,+)$ up to isomorphism. Now think about expansions of that structure.

And here's the full solution:

Add a unary relation $U$ to the signature. For each set $A\subseteq\mathbb{N}$, consider the $\{1,+,U\}$-sentence $$\eta\wedge\forall x(U(x)\leftrightarrow\bigvee_{a\in A}x=1+...+1\mbox{ ($a$ times)}).$$

---

Incidentally, from that solution we get an easy proof that $\mathcal{L}_{\omega_1,\omega}$ does not have the full dLS-property:

The point is that we can think about possible expansions as elements of a larger structure - and so we can put all the structures in $\mathfrak{S}$ into a single structure, which has to be uncountable but is described up to isomorphism by a $\mathcal{L}_{\omega_1,\omega}$-theory. Specifically, consider a two-sorted structure, one sort of which corresponds to $(\mathbb{N},<)$ and the other sort of which corresponds to a collection of subsets of $\mathbb{N}$, and consider for each $A\subseteq\mathbb{N}$ the sentence saying that $A$ occurs in the second sort.