Well-foundedness is not a first order property.

698 Views Asked by At

In the book 'Logic, Induction and Sets' by Thomas Foster I read the following in page 100 (Section 'The language of predicate logic'):

"We can show that well-foundedness is not a first-order property (there is no first-order theory whose models are precisely those binary structures $\langle X,R\rangle$ where $R$ is a well-founded relation)".

A proof of this can be found here: Why isn't there a first-order theory of well order?. It uses the compactness theorem.

Now, I'm willing to think there are still theories whose models possess a well-founded relation. Is Pearno Arithmetic one of them? What about ZF? In this case however well-foundedness could not be solely derived from the axiom of foundation/induction.

1

There are 1 best solutions below

1
On BEST ANSWER

The standard model of Peano Arithmetic -- that is, the usual natural numbers whose Platonic existence most of us believe in instinctively -- is well-founded.

However, thanks to Gödel (or just compactness) we know that PA has non-standard models, and a non-standard model of PA is not well-founded. In particular, since arithmetic on elements that can be written as numerals is fully given by the defining axioms for addition and multiplication, any non-standard model must have an element $c$ that does not equal any numeral. And then $$ c, c-\bar1, c-\bar2, c-\bar3, c-\bar4, \ldots, c-\bar n, \ldots $$ is an infinitely descending sequence. (It can't ever stop unless $c$ actually equals one of the $\bar n$s, which by assumption it doesn't).

The situation with ZF and its various extensions is much the same: While the "standard" model (which we believe in mostly by intuition, if we believe it at all) is supposedly well-founded, one can easily use compactness to produce a model that is not well-founded, by essentially the same reasoning as for PA. (Assuming, of course, that ZF is consistent at all).


In general, it is easy to write a theory whose models are all finite. For such a theory, of course, all models are well-founded.

However, as long as a theory allows for models where there are infinite ascending chains of the relation in question (or merely if there are models with arbitrarily long finite chains), then the compactness argument you link to shows that this theory must have an ill-founded model.