[FOM] From Compactness to Completeness
G. Aldo Antonelli
antonelli at ucdavis.edu
Fri Dec 24 12:27:01 EST 2010
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
More information about the FOM
mailing list