8
$\begingroup$

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?

$\endgroup$
1
  • $\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

6
$\begingroup$

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.

$\endgroup$
2
  • $\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
4
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

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