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

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!

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.

• So, would I be correct in saying that these arguments would also show that if $\mathcal{L}$ is any logical system whatsoever with only countably many sentences (over each symbol set), then it will NOT be the case that $\mathcal{L}_{\omega_1 \omega} \leq \mathcal{L}$? Apr 9, 2020 at 14:17
• @User7819 Yes, exactly. Apr 9, 2020 at 14:37