[FOM] From Compactness to Completeness

[G. Aldo Antonelli]

On 12/24/10 9:00 AM, John Burgess wrote:

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

When I first learned this as an undergraduate (in the old country, as 
they say) the proof of completeness proceeded through compactness and 
what we called 'weak completeness' i.e. the statement that any validity 
is provable.

The usual Henkin proof of compactness requires a weak version of choice, 
as Burgess points out. In turn, compactness implies that if T entails A, 
then a finite T' already does, so T'-->A is valid, hence provable.

Interestingly perhaps, "weak completeness" also requires a combinatorial 
principle, viz., König's lemma, in order to extract a counter-model from 
a non-terminating truth tree.

I have some recollection that this strategy was credited to H Hermes, 
"Enumerability, Decidability, Computability" (1965) but I have no access 
to the book now.

-- Aldo


*****************************************
G. Aldo Antonelli
Professor of Philosophy
University of California, Davis
http://philosophy.ucdavis.edu/antonelli
antonelli at ucdavis.edu +1 530 554 1368