0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Chapter 4 of these lecture notes indicates that the answer is negative. $\endgroup$
    – Watercrystal
    Commented Sep 28, 2020 at 22:51

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented 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$
    – Noah Schweber
    Commented Nov 12, 2020 at 16:14

Your Answer

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

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