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?

  • $\begingroup$ 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. $\endgroup$ Apr 27, 2013 at 15:09

2 Answers 2


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.

  • $\begingroup$ 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? $\endgroup$ Jan 14, 2022 at 17:22
  • $\begingroup$ @UmbertoCavasinni Yes, that's right. $\endgroup$ 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).


You must log in to answer this question.

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