Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The proof of compactness and completeness of $\mathscr{FOL}$ (with Hilbert system) used Zorn's lemma. And Zorn's lemma is equivalent to the Axiom of choice in $ZF$.

So my question is can they be proved without Zorn's lemma, or is first-order logic incompact and incomplete consistent with $ZF$ without AC?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

The answer is that it is consistent that completeness and compactness of FOL fail in some models of ZF, and that they are provable from a slightly weakened choice principle which is The Boolean Prime Ideal theorem (and its many many useful equivalences).


The compactness theorem for FOL is equivalent to the completeness theorem for FOL in ZF. Both are equivalent to the Boolean Prime Ideal theorem, which in turn is equivalent to many more useful principles such as the ultrafilter lemma, and Tychonoff theorem for Hausdorff spaces.

There are models in which all these fail, so it is consistent indeed. For example, all the above imply that every set can be linearly ordered. In models where some sets cannot be linearly ordered they fail.

One example is a model in which there is a countable collection of pairs whose product is empty. Indeed if every set could be linearly ordered, the union of these pairs could have been linearly ordered and we could fix one ordered and choose the minimal element from every pair, and the product would not be empty then.

One can directly prove this as a compactness argument. Let $S$ be the union of all the pairs. Let $T$ be the theory which states that the universe is linearly ordered, and for every $s\in S$ we add a constant $c_s$ and the axiom which says that $c_s\neq c_t$ whenever $t\neq s$. Every finite fragment of the theory is consistent, simply because a finite set of axioms would correspond to a finite collection of the pairs which can be linearly ordered without any use of the axiom of choice (and the existence of a model implies consistency, it's the other direction which requires choice). However the entire theory does not have a model because a model of the theory would have to be a linear ordering of $S$ which, as we remarked above, is contradictory to the fact that the pairs have an empty product.

I should also remark that for a countable, or generally well-orderable language (including variables and what have you) the compactness theorem is true in ZF.

share|improve this answer
    
Well, theories of formal logic rely on set theories; on the other hand, many set theories used formal logic in foundation(e.g. Axiom of Comprehension )... –  Popopo Nov 28 '12 at 8:48
1  
Yes, and? :-) There is a very fine and delicate line of distinction when talking about such results. It's a set model of a set-logic with; or a class universe with meta-logic. –  Asaf Karagila Nov 28 '12 at 8:49
1  
You are asking whether or not two FOL theories which are identical (so they are the same theory) in identical languages which have different meta theories behave the same? So in one model of ZF they behave like this and in another like that? If you are truly interested in the theories then a model theorist could probably answer better about complete types and completion of the theory, etc. If you are interested in the properties of the logic itself given a particular language it's a different story. –  Asaf Karagila Nov 28 '12 at 9:31
1  
I also think that if you attempt to truly understand these things you are ought to work on your set theory and logic basis before attempting to understand deeper things. It is a common mistake that one can understand deep implications and deep understandings of mathematics even without a good grasp on the basis. I was a firm believer that one can do that. Until I had to write my thesis and I learned that one has to truly understand what's going on in order to truly understand what's going on. –  Asaf Karagila Nov 28 '12 at 9:32
1  
I see. Interesting advice. I'm not sure if I agree. But that's a whole other story. If you truly want to understand these things you will have to study set theory from books, after you have a reasonable grasp on set theory you can move to set theory without choice. Even then, though, without learning forcing you are unlikely to be able to understand many consistency results deeply. Congratulations, you've reached the point in mathematics where shallow answers are useless and one has to study hard to understand new things. –  Asaf Karagila Nov 29 '12 at 8:09

As it turns out, the compactness and completeness theorems are weak versions of AC. See here.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.