Lindstrom's theorem states that any extension of first order logic (FOL) more expressible than FOL fails to have either compactness or Lowenheim-Skolem. When I first read Lindstrom's theorem my first reaction was: "Does it mean incompleteness of any more expressible extension of FOL? And why this obviously important question isn't discussed in standard logic texts?" Standard extensions (such as second order logic) in fact are incomplete. After some attempts of proving incompleteness I found reference to Vaught's paper in which he proves completeness of extension of FOL by adding quantifier Qx = "there are uncountably many x such that..." It would be very interesting (at least for me) to understand complete extensions in general. Such an extensions may be of great importance, for instance, for computer science, because FOL isn't enough expressive for its purposes.

So, my questions are:

1) Do you know some other examples of complete FOL extensions?

2) Are there some results concerning characterization of complete FOL extensions?

3) Do you know any people, papers, books... studying general properties of FOL extensions?

Thanks in advance.

  • 4
    $\begingroup$ +1: nice question. The title, however, could be made more descriptive. $\endgroup$ Aug 3 '10 at 15:12
  • 2
    $\begingroup$ I know what it means for a deductive system or a set of axioms to be complete, but what does it mean for a logic to be complete? Does this mean that there exists a deductive system which is strong enough to produce all tautologies, and for which one can computably check whether or not a finite string is a valid proof? $\endgroup$ Aug 3 '10 at 18:12
  • $\begingroup$ @John Goodrick: yes, or it may mean that there exists an algorithm that generates all tautologies $\endgroup$ Aug 3 '10 at 18:24
  • 2
    $\begingroup$ @Sergei: OK, I see. This makes sense, but I don't think this terminology is currently standard. $\endgroup$ Aug 3 '10 at 18:34
  • $\begingroup$ Since this was asked in 2010, that uncountable quantifier $Q$ has become more important. See Kirby’s “note on the axioms for Zilber’s pseudo-exponential fields”, arxiv.org/pdf/1006.0894.pdf $\endgroup$
    – Matt F.
    Mar 1 '20 at 19:04
  1. Shelah has some nice results on complete extensions of first order logic. For example, he introduced cofinality quantifiers in which the truth value of a given formula (Qxy)Phi(x,y,a) is determined by the cofinality of the linear order of pairs (x,y) satisfying Phi. It turned out that such logics are complete (in addition to other nice model-theoretic properties). You may find these results (and much more) in the following paper: http://www.ams.org/journals/tran/1975-204-00/S0002-9947-1975-0376334-6/S0002-9947-1975-0376334-6.pdf

  2. You should check the book "Model theoretic logics" by Feferman and Baldwin (although it's a pretty old book). As far as name-dropping goes, you should also check the works of Barwise. You may also check this nice survey paper: http://www.math.ucla.edu/~asl/bsl/1001/1001-004.ps

  • $\begingroup$ You mean "Model theoretic logics" by Feferman and Barwise, not Baldwin? $\endgroup$ Aug 3 '10 at 19:04
  • $\begingroup$ oops. That's correct. $\endgroup$
    – Haim
    Aug 3 '10 at 20:56

There are some model theorists currently studying extensions of first-order logic, mainly in the setting of so-called Abstract Elementary Classes (or AECs). An AEC is a class of structures with a given signature (as in model theory) equipped with a distinguished "strong substructure relation" which satisfies some of the same axioms as the elementary substructure relation between models in first-order logic.

The study of AECs in a sense generalizes both infinitary logics like $L_{\omega_1, \omega}$ (where one is allowed to form countably infinite conjunctions and disjunctions) and the logic $L(Q)$ with a quantifier for "there exists uncountably many." For a recent and thorough exposition of all of this, you should look at John Baldwin's AMS monograph Categoricity, which is avaialbe here.


Bumping an old question, I think it's relevant that Lindstrom actually had a second theorem:

No proper strengthening of FOL has the downward Lowenheim-Skolem property and a r.e. set of validities.

(This latter condition is what the OP calls "complete" - note that we're not assuming the existence of any proof system, it's purely a hypothesis on the "end-of-the-day" complexity.)

Put another way, downward Lowenheim-Skolem is a fundamental barrier to completeness beyond FOL. We can replace dLS here with a more technical property designed to do exactly what we need from dLS, but I'm not sure how valuable that is in this context and I don't know of any fundamentally different properties we can use in its place, so I'll provocatively claim (until my silliness is revealed) that dLS is the fundamental barrier to completeness beyond FOL.

The proof of both Lindstrom theorems can be found in Ebbinghaus-Flum-Thomas; they're very similar, but the second also brings in Trakhtenbrot's theorem. Incidentally, this paper by Barwise is a wonderful summary of various Lindstrom-style theorems. It's been a while since I read it and at a glance it doesn't discuss completeness very directly, but I can't help but mention it here.


Lindstrom's theorem is discussed in the Logic textbook by Ebbinghaus, Flum and Thomas. This is fairly standard in Germany and a translation into English exists.

  • $\begingroup$ I read it. But I didn't notice any discussion of complete extensions there. $\endgroup$ Aug 3 '10 at 18:29
  • $\begingroup$ I guess my answer was relating to your third question (the second one that is numbered (2)). $\endgroup$ Aug 31 '10 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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