Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Well-ordering in a first-order language

  1. Dec 27, 2011 #1


    User Avatar
    Gold Member

    Is it possible to express well-ordering in a first-order language?

    For example:
    If [itex]X[/itex] is a set and [itex]<[/itex] is a binary relation on [itex]X[/itex] such that [itex](X,<) \vDash \forall x \; \neg(x<x)[/itex] and [itex](X,<) \vDash \forall x \forall y \forall z((x<y \wedge y<z) \rightarrow x<z)[/itex], then [itex](X,<)[/itex] is a partial order.

    If [itex](X,<)[/itex] is a partial order such that [itex](X,<) \vDash \forall x \forall y(x<y \vee x=y \vee y<x)[/itex], then [itex](X,<)[/itex] is a total order.

    I cannot think of a way to express well-ordering in this language. Since the quantifiers range over all of [itex]X[/itex] and there is no obvious way to quantify over subsets of [itex]X[/itex], I am thinking it is not possible to express well-ordering in this way. But it is also possible that I am just not sufficiently clever to think of something.

    Any help?
  2. jcsd
  3. Dec 27, 2011 #2


    User Avatar
    Gold Member

    I think I found an answer to this question. The standard model for [itex](\mathbb{N};0,S,<,+,\times)[/itex] is well-ordered but non-standard models are not. In particular, this means that there is no first-order sentence that expresses well-ordering.
  4. Dec 28, 2011 #3
    Well that much is true, but relying on non-standard models of arithmetic in order to show that the property of being a well-ordering is not expressible in first-order classical logic seems to be a bit of an overkill. A more straightforward argument relies on compactness: call the theory of strict partial ordering with your two axioms SPO and suppose that the set of formulas T expresses the property that < is a well-ordering (M is a model of SPO+T iff < is a well-ordering on the domain of M). Add countably many constants [itex]c_0, c_1, \ldots[/itex] to the language along with the axioms Ax: [itex]c_1 < c_0, c_2 < c_1, \ldots[/itex]. Each finite subset of SPO+T+Ax is satisfiable, hence by compactness, the whole set is satisfiable in some model M. But the set of all realizations of [itex]c_i[/itex] clearly has no minimum in M, which contradicts the definition of T.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook