Can the Well-Ordering Theorem Prove the Axiom of Induction?

[kostas230]

The well ordering theorem states that every non-empty set has a least element for some ordering (<). This means that if we take the set of natural numbers, by considering the Peano Axioms ONLY, we can find an order (<) (not necessarily the usual one) in which the set of natural numbers N has a least element (again, not necessarily 0).

Now, suppose we take a number system N', which satisfies the Peano Axioms except the Axiom of Induction. Due to the Well-Ordering Theorem, we can find an order "<" in which N' has a least element. Can we show that the Axiom of Induction does not hold under this relation or at least make any progress on that? Thanks :)

 

[HallsofIvy]

No, we can't- the "well- ordering" property implies induction. Of course, that is an induction using the order,
"an order (<) (not necessarily the usual one)", not necessarily based on the usual order. That is, if this "not necessarily the usual" order has first element a, then "induction" would be
1) prove the statement is true for x= a
2) prove that if a statement is true for some x then if is true for x+ (where x+ is the "next element" in this order).

 

[TSC]

I thought the well ordering theorem of natural numbers refer to the natural order?

 

[gopher_p]

Let $N'$ be the disjoint union of $N_1$ and $N_2$ where $N_1,N_2=\mathbb{N}$. Define the total order $<'$ on $N'$ by $a<'b$ iff $a\in N_1$ and $b\in N_2$ or $a,b\in N_i$ and $a<_ib$ in $N_i$, where $<_i$ is the standard order on $N_i$. Define $S':N'\rightarrow N'$ by $y=S'(x)$ iff $y=S_i(x)$, where $S_i:N_i\rightarrow N_i$ is the standard successor function. Basically, $N'$ is just two copies of $\mathbb{N}$ stacked end-to-end with the "natural" order and successor function.

Then $N'$ with $S'$ is a model of the Peano Axioms without the induction axiom that is well ordered by $<'$. The induction axiom is, in fact, false for $N'$.

If you make a similar construction with $\mathbb{N}$ and $\mathbb{Z}$ (instead of two copies of $\mathbb{N}$), with $\mathbb{N}$ before $\mathbb{Z}$, then you get a model of the Peano Axioms without induction that is not well-ordered.


Keep in mind that the Well-ordering Theorem is a (true) statement in ZFC about the existence of a well-ordering for every set. It's not really applicable to most questions that one might have about Peano Arithmetic; it's kinda ... external. The Well-ordering Principle is a statement about natural numbers with a specific order, expressible in Peano arithmetic, and true only because the induction axiom is true; i.e. minus the induction axiom, well-ordering need not hold.

 

[Martin Rattigan]

The well ordering theorem states that every non-empty set has a least element for some ordering (<).

To avoid spreading confusion it might be worth pointing out that this is not what the well ordering theorem states. It is equivalent to the weaker statement that every set can be totally ordered.