# Does FOL extended with least-fixed points satisfy the Compactness Theorem?

I am aware that first-order logics (FOL) satisfies the compactness theorem. That is, if a FOL theory is insatisfiable, a finite subset of the axioms of such theory is insatisfiable too.

Is it the case that FOL extended with least-fixed point (LFP) satisfies the compactness theorem too?

• Chapter 4 of these lecture notes indicates that the answer is negative. Sep 28, 2020 at 22:51

Least fixed point operators can let us define, for example, the standard part of a model of $$\mathsf{PA}$$. The standard part of a model $$\mathfrak{A}=(A;+^\mathfrak{A},\times^\mathfrak{A},0^\mathfrak{A},1^\mathfrak{A})$$ of $$\mathsf{PA}$$ is just the smallest subset of $$A$$ containing $$0^\mathfrak{A}$$ and closed under $$n\mapsto n+^\mathfrak{A}1^\mathfrak{A}$$. But this is exactly a least fixed point definition: the standard part of $$\mathfrak{A}$$ is the least fixed point of the operator $$\Phi(P): x=0\vee\exists y(P(y)\wedge y+1=x).$$
This in turn lets us pin down the standard model of $$\mathsf{PA}$$ up to isomorphism by the theory $$\mathsf{PA}$$ + "Every element is standard." But this contradicts compactness: no compact logic can ever pin down an infinite structure up to isomorphism (this is really just the observation that the upwards Lowenheim-Skolem theorem is just a compactness corollary).
• @441Juggler Sorry, I just saw this. This is a standard trick for applying compactness - expand the language. Consider the language of $\mathsf{PA}$ augmented by a new constant symbol $c$, and let $T$ be the theory gotten by adding to $\mathsf{PA}$ each sentence of the form $c>\underline{n}$ for $n\in\mathbb{N}$, where $\underline{n}$ is the numeral corresponding to $n$ (so e.g. $\underline{3}$ is the term $(1+1)+1$). Then $T$ is finitely consistent, hence satisfiable, but if we let $M$ be a model of $T$ then $M$ (or rather, $M$'s reduct to the language of arithmetic) must be nonstandard. Nov 12, 2020 at 16:14