# Why does one need to specify that the language is "well-orderable" for first order logic to be complete?

While reading Wikipedia I noticed the phrase "well-ordered language" in the following related to Gödel's completeness theorem:

The completeness theorem then says that for any first-order theory T with a well-orderable language, and any sentence s in the language of T

if s is a semantic consequence of T then s is a syntactic consequence of T.

Why did the authors need to specify a "well-ordered language" and what are the characteristics of a first order language that show that it is well-ordered?

Wikipedia contributors. (2019, June 10). Gödel's completeness theorem. In Wikipedia, The Free Encyclopedia. Retrieved 20:07, June 19, 2019, from https://en.wikipedia.org/w/index.php?title=G%C3%B6del%27s_completeness_theorem&oldid=901289398

• They are just being overtechnical. For a non-well-orderable language one needs an uncountable alphabet, and has to work in a set theory without the axiom of choice. Not a language most ever met, or care about. Jun 19 '19 at 20:29
• @Conifold The link does explain what a well-ordered language is but not why it is needed for the completeness proof. Jun 20 '19 at 12:10
• To run (transfinite) induction on the set of formulas when constructing its model, see an example on Quora. Jun 20 '19 at 15:46

## 1 Answer

It is quite common to assume ZFC as the unspoken system in which mathematical claims are to be understood. In that case, it would be unnecessary to specify "well-orderable", because the axiom of choice is (over ZF) equivalent to the statement that every set is well-orderable.

The typical proof of the completeness theorem proceeds by constructing a model "by brute force". If the language is well-orderable, then so is the set of formulae. So we can go through the true formulae one step at a time, and built our model accordingly. Without a well-order, we lose this option.

How much choice is necessary for the completeness of course is a different question, and I believe one best asked on MathOverflow.

• That makes sense. I can see how we could use induction on the length of the formulas and that this would require being able to well-order those formula. Jun 20 '19 at 15:55