[FOM] From Compactness to Completeness

[Alex Blum]

Dear Colleagues,

In answer to my query last year whether compactness implies completeness, I received at least two affirmative replies, see below.
What remains unclear to me is:
1.Why doesn't an incomplete subpart of propositional logic show that this is not true ? And,
2. If I misunderstood, does the implication hold for all logics?
Thank you
Alex      
....................................................... 
From: "John Burgess (by way of Martin Davis <eipye at pacbell.net>)" 
<jburgess at princeton.edu>
To: <fom at cs.nyu.edu>
Sent: Thursday, December 23, 2010 10:29 PM
Subject: Re: [FOM] From Compactness to Completeness


The facts to which Wikipedia is presumably alluding are the
following: (1) To prove completeness in the form of the statement
that any consistent set T of first-order sentences has model, one
needs, if T is uncountable, the axiom of choice, or if one is
careful, a weak version of it, the Boolean prime ideal theorem. (2)
 Compactness follows immediately from completeness, without use of
choice. (3) It is a fairly easy application of compactness to prove
the Boolean prime ideal theorem. Thus all three statements are
equivalent over ZF set theory without choice

From: jean-yves beziau 
To: Foundations of Mathematics 
Sent: Friday, December 24, 2010 4:23 PM
Subject: Re: [FOM] From Compactness to Completeness

The relation between the compactness theorem and the completeness theorem varies depending on specifities.
At the level of abstract logic (no specification of language), we have:
(1) Lindenbaum extension theorem: compactness theorem implies existence of a maximal extension
(2) Axiom of choice: equivalent to (1) as proved by Dzick
(3) Completeness is a corollary of (1) 

I have presented a detailed study of this in my Phd:
Recherches sur la logique universelle, Dpt of Mathematics, University o Paris 7, 1995
and part of it has been published as
"La vériatble portée du théorème de Lindenbaum-Asser", Logique & Analyse , 167-166 (1999), pp.341-359.
The situation is summarized in paricular in a diagram p.350

You can also have a look at:

David W. Miller
Some Restricted Lindenbaum Theorems Equivalent to the Axiom of Choice
Logica universalis 1 (2007), 183-199
http://www.springerlink.com/content/k62ml13t80g76v58/

In the book "completness theory for propositional logics" by W.Pogorzelski and P.Wojtylak
http://www.springer.com/birkhauser/mathematics/book/978-3-7643-8517-0
you will find also many interesting results, in particular the following:

Metatheorem A.4. The following theorems are effectively equivalent:
(i) Stone's representation theorem for Boolean algebras.
(ii) Strong adequacy of the two element Boolean algebra (or matrix M2) for the
classical propositional logic.
(iii) Gödel Malcev's propositional theorem.
(iv) Structural completeness theorem for the classical propositional logic.
(v) Lindenbaum-Los's maximalization theorem.
(vi) Los' theorem on the representation of Lindenbaum-Tarski algebras.
 
...................
Alex Blum
Department of Philosophy
Bar Ilan University