# Which logic is stronger? SOL or $\frak{L}_{\infty,\infty}$?

Both second-order logic($\mathsf{SOL}$) and infinitary first-order logic $\frak{L}_{\infty,\infty}$ are proper extensions of first-order logic($\mathsf{FOL}$), that is, are extensions of a $\mathsf{FOL}$ and also strictly stronger than it in expressive power. It is natural to ask, are they comparable? If so, which one is more powerful?

• This related question asks whether second order logic is more expressive than infinitary logic and, if so, how arbitrary sentences from infinitary logic can be translated to sentences in second-order logic. Apr 27, 2013 at 15:09

While Model-theoretic logics is indeed a wonderful source, for this particular question it's overkill. The logics $$\mathfrak{L}_{\infty,\infty}$$ and $$SOL$$ are incomparable in a precise sense.

One direction is easy. $$\mathfrak{L}_{\infty,\infty}$$ pins down every structure up to isomorphism: if $$\mathcal{A}$$ has cardinality $$\kappa$$ then there is an $$\mathfrak{L}_{\kappa^+,\kappa^+}$$-sentence $$\varphi_\mathcal{A}$$ whose models are exactly those structures isomorphic to $$\mathcal{A}$$.

• Note that in the case $$\kappa=\omega$$ we have a serious improvement in Scott's isomorphism theorem, which says that $$\mathfrak{L}_{\omega_1,\omega}$$ (which is vastly better-behaved than $$\mathfrak{L}_{\omega_1,\omega_1}$$) is enough. That's not true in general beyond $$\omega$$, though.

By contrast, $$SOL$$ doesn't do this for the simple fact that it's too small - although it's quite difficult to find a structure SOL can't pin down, we know there must be one (indeed, there has to be one of cardinality $$\le 2^{\aleph_0}$$).

More generally, $$\mathfrak{L}_{\infty,\infty}$$ is too large to be a sublogic of any set-sized logic.

It's also the case that $$SOL$$ is not a sublogic of $$\mathfrak{L}_{\infty,\infty}$$, although this takes slightly more thought.

The key is:

If $$\varphi$$ is an $$\mathfrak{L}_{\infty,\infty}$$-sentence in the empty language, then there is a $$\kappa$$ such that either $$\varphi$$ holds of every structure of cardinality $$>\kappa$$ or $$\varphi$$ fails of every structure of cardinality $$>\kappa$$.

This is a good exercise, and in fact we can just take $$\kappa=\vert\varphi\vert+\aleph_0$$.

By contrast, this is clearly false for $$SOL$$. For example, there is an $$SOL$$-sentence in the empty language which is true in exactly those structures whose cardinality is an infinite successor cardinal: "The domain is infinite and there is some subset $$A$$ of the domain not in bijection with the whole such that every subset of the domain containing $$A$$ is either in bijection with $$A$$ or in bijection with the whole domain."

That said, while neither logic contains the other there are definitely comparisons we can draw. On the whole I'd say that $$SOL$$ captures much more set theory than $$\mathfrak{L}_{\infty,\infty}$$, and so in that sense is arguably more powerful (and less well-behaved); on the other hand, the logical equivalence relation for $$\mathfrak{L}_{\infty,\infty}$$ is finer than that for $$SOL$$ (it's just $$\cong$$ after all), so when we focus on individual structures as opposed to classes of structures or background set-theoretic facts $$\mathfrak{L}_{\infty,\infty}$$ thoroughly dominates.

• None of the infinitary logics $\mathcal{L}_{\kappa\lambda}$ is a sublogic of second-order logic for cardinality reasons (class of sentences); on the other hand second-order logic can't be a sublogic of any infinitary logic because it's not a sublogic of $\mathcal{L}_{\infty\infty}$. Is it correct? Jan 14, 2022 at 17:22
• @UmbertoCavasinni Yes, that's right. Jan 14, 2022 at 17:23

I know it can sometimes be a bit irritating to give references to books here, when they may not be readily available. But Barwise and Feferman's Model-Theoretic Logics is now freely available from Project Euclid, and contains a wealth of information about infinitary and second-order logics. Chapter 9 of the classic book on second-order logic by Stewart Shapiro, sadly not so freely available, summarises many results (they are quite sensitive to the cardinality of the infinitary languages).