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

  • 1
    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.
    – Conifold
    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.
    – Conifold
    Jun 20 '19 at 15:46

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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