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?

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

1 Answer 1


No, it does not satisfy compactness anymore.

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

  • $\begingroup$ Hi @noah-schweber, many thanks for your answer. If I understand you correctly, you say that a theory that only has just one (infinite) model do not satisfy compactness, I am trying to see why this is the case. I suppose that, in this particular example, you might be able to extend PA+{every number is standard} with some other axioms that might make it insat (whereas any finite subset of such axioms would be sat). However, I do not see how you can "kill" the standard arithmetic model with some infinite set of axioms. Can you help me on this, please? $\endgroup$
    – 441Juggler
    Oct 11, 2020 at 14:27
  • 1
    $\begingroup$ @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. $\endgroup$ Nov 12, 2020 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.