2
$\begingroup$

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?

2 Answers 2

5

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.

  • 0
    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 )...2012-11-28
  • 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.2012-11-28
  • 0
    And a question arises: Let a set theory $A$ used a formal logic $L$ which based on a meta set theory $B$, and another set theory $A'$ used a formal logic $L'$ which based on a meta set theory $B'$. $L$ and $L'$ looks similar except their meta set theory disagree in some cases. $A$ and $A'$ has similar axioms. Then do they identical? e.g. $ZFC$ defined in FOL based on a set model of $ZFC$ and $ZFC'$ defined in FOL' based on a set model of $ZF+ \lnot AC$, are they the same?2012-11-28
  • 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.2012-11-28
  • 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.2012-11-28
  • 0
    Okay, which branch research properties of the logic itself given a particular language?2012-11-28
  • 0
    Theoretically that would be between logic and set theory without choice, which is an almost empty intersection. You might want to talk to constructivist logicians or topos theorists, but I have no idea about that really. I suppose it greatly depends on the language. If its cardinality is simple enough to manipulate perhaps there are some immediate answers that can be given. The questions are whether or not you would like to limit yourself to a particular case which interests you, or are you asking just out of general curiosity.2012-11-28
  • 0
    Well, general curiosity indeed...2012-11-29
  • 0
    What's more, my supervisor(an applied logician) often advices us that textbooks is unimportant, we should better read latest papers and write innovatively. Actually many latest papers in applied logics do not deeply rely on textbooks since they are introducing new systems and almost zero basics(only need familiar modal logic). However I found to comprehend latest papers involving set theory or model theory, majestic textbooks required...2012-11-29
  • 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.2012-11-29
4

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