Skip to content
Axiomatic Wiki
Theorem·T18

The naturals are well ordered

The usual order on the natural numbers is a well order.

The usual order on the naturals is a well order: is , is , and .
In words
The natural numbers under their usual order satisfy every requirement of a well order: the order is reflexive, antisymmetric and transitive, any two naturals are comparable, and any nonempty set of naturals has a smallest member.
Rests onF02F03F04F06F08F09F11F12F14A01A02A06A08
Never needed: F05 · F10 · F13 · A03 · A04 · A05 · A07 (computed from the citation graph, not asserted).

Proof

  1. 1
    Partial order (D051). Recall and (D029). Reflexive: since . Antisymmetric: if and with , then and , contradicting L16 (at most one holds); so . Transitive: from and , if either step is an equality substitute (F14); otherwise and give (L15 (ii)); either way .
  2. 2
    Total (D052). For , L16 gives , , or ; the first two yield and the third yields . So any two naturals are comparable.
  3. 3
    Well ordered (D054). Let with . By the well-ordering principle there is with for every ; this is a least element of . As was arbitrary, every nonempty subset has a least element, so is a well order.
∎

Remarks

This repackages the well-ordering principle, proved earlier from the ZFC axioms, as the statement that is a well order in the abstract sense; it is the smallest infinite well order, the order type of the ordinal . Its being well ordered is the same fact that licenses induction and strong induction on the naturals.
Wikipedia ↗Nat.lt_wfRel ↗
Propose an edit1 published revision