Proofs that monadic second order logic is not compact

119 Views Asked by At

I was reading this comment by Simone on this answer to this question.

The comment is reproduced below, emphasis mine.

Well, It's not an extension that uses the notation you use, but all axioms remain and all theorems of FOL remain true. Plural logic loses compactness.

I find this interesting because I intuitively think of plural logic as a well-behaved cousin of FOL, but don't know how to square this intuition with Lindström's theorem.

Plural logic is very similar to monadic second-order logic, so I'd like to restrict attention to monadic second-order logic. I'd also like to restrict attention to the full semantics since I strongly suspect that, with the Henkin semantics, monadic second order logic is a paraphrase of multi-sorted FOL and is thus sompact already.

I'm curious if there's a simple go-to example of an infinite family of sentences in monadic second-order logic that's finitely satisfiable but not satisfiable.

I'm also curious more generally if there's an alternative method of proving non-compactness that doesn't require us to cook up an example (or appeal to Lindström's theorem, which seems excessively powerful for such an application).


Here's my attempt to prove the theorem myself. I'm not sure that the $\varphi$ in my construction below really succeeds in ruling out every nonstandard model of arithmetic. It's also possible that there's a much easier way to prove this that I'm not seeing (assuming that it's even true).

Consider the language of Peano arithmetic plus a new constant symbol $c$.

Let $\Phi$ be the first-order axioms of Peano Arithmetic; $\Phi$ is infinite.

Let $W$ be $\{ c > 0, c > 1, c > 2, c > 3 \cdots \}$. I'm going to use $W$ to give me a nonstandard integer.

Let $\varphi$ be the proposition promising me a unique inductive set containing $0$.

$$ \varphi \;\; \text{is} \;\; \exists! U \mathop. 0 \in U \land (\forall x\mathop. x \in U \to x + 1 \in U) $$

I claim that the standard model of Peano Arithmetic with a suitably large standard integer chosen as the value for $c$ is a model of all finite subsets of $\Phi \cup W \cup \{\varphi\}$.

I claim that $\varphi$ insists that the model of any $\Delta \ni \varphi$ is standard.

I further claim that any model of PA in which $W \cup \Phi$ holds is nonstandard.

Therefore $\Phi \cup W \cup \{ \varphi \}$ is unsatisfiable.

Therefore compactness fails for monadic second-order logic.