# Complete Extensions of First Order Logic (or Language)

Lindstrom's theorem states that any extension of 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?

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

-
+1: nice question. The title, however, could be made more descriptive. –  Pete L. Clark Aug 3 '10 at 15:12
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? –  John Goodrick Aug 3 '10 at 18:12
@John Goodrick: yes, or it may mean that there exists an algorithm that generates all tautologies –  Sergei Tropanets Aug 3 '10 at 18:24
@Sergei: OK, I see. This makes sense, but I don't think this terminology is currently standard. –  John Goodrick Aug 3 '10 at 18:34

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

-
Thanks very much! –  Sergei Tropanets Aug 3 '10 at 18:43
You mean "Model theoretic logics" by Feferman and Barwise, not Baldwin? –  Sergei Tropanets Aug 3 '10 at 19:04
oops. That's correct. –  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.

-
Thanks very much! –  Sergei Tropanets Aug 3 '10 at 18:44

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.

-
I read it. But I didn't notice any discussion of complete extensions there. –  Sergei Tropanets Aug 3 '10 at 18:29
I guess my answer was relating to your third question (the second one that is numbered (2)). –  Stefan Geschke Aug 31 '10 at 10:12