[FOM] From Compactness to Completeness

[T.Forster@dpmms.cam.ac.uk]

I think if the language is countable you don'tneed KL, surely?

  Merry Christmas

      tf


On Dec 24 2010, G. Aldo Antonelli wrote:

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