10
$\begingroup$

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.

$\endgroup$
5
  • 4
    $\begingroup$ +1: nice question. The title, however, could be made more descriptive. $\endgroup$ Aug 3, 2010 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, 2010 at 18:12
  • $\begingroup$ @John Goodrick: yes, or it may mean that there exists an algorithm that generates all tautologies $\endgroup$ Aug 3, 2010 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, 2010 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$
    – user44143
    Mar 1, 2020 at 19:04

4 Answers 4

7
$\begingroup$
  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

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

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.

$\endgroup$
0
4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Do you know an example of a fully compact abstract logic that is stronger than FOL and has a computably enumerable set of validities? $\endgroup$ Oct 18, 2023 at 22:27
  • $\begingroup$ @JamesHanson If memory serves, one of Shelah's cofinality things does the trick. I'll see if I can track it down ... $\endgroup$ Oct 18, 2023 at 22:49
  • $\begingroup$ Do you know if there's a variant of Lindström's theorem that says something to the effect of 'FOL is the strongest logic that is compact and set-theoretically absolute'? Likewise with c.e. instead of compact. $\endgroup$ Oct 19, 2023 at 18:09
  • $\begingroup$ @JamesHanson I think Lindstrom's theorem already does that. Given a putative counterexample $\mathcal{L}$ we build a structure with subreducts $\mathcal{A}$,$\mathcal{B}$ which are $\mathcal{L}$-inequivalent but potentially isomorphic (this only uses compactness), but that contradicts absoluteness. $\endgroup$ Oct 19, 2023 at 18:23
  • $\begingroup$ Right, I forgot that the downward LS is the weak version, not the substructure version. $\endgroup$ Oct 19, 2023 at 18:30
1
$\begingroup$

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.

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

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.