0

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

Improve this question
3
  • 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, 2019 at 20:29
  • @Conifold The link does explain what a well-ordered language is but not why it is needed for the completeness proof.
    – Frank Hubeny
    Jun 20, 2019 at 12:10
  • To run (transfinite) induction on the set of formulas when constructing its model, see an example on Quora.
    – Conifold
    Jun 20, 2019 at 15:46

1 Answer 1

Reset to default
2

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.

Improve this answer
1
  • 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.
    – Frank Hubeny
    Jun 20, 2019 at 15:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .