Well-Ordering and induction

  • Thread starter kostas230
  • Start date
  • #1
96
3
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 :)
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
961
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).
 
  • #3
TSC
39
1
I thought the well ordering theorem of natural numbers refer to the natural order?
 
  • #4
575
76
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.
 
  • #5
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.
 

Related Threads on Well-Ordering and induction

  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
12
Views
4K
Replies
2
Views
3K
  • Last Post
Replies
4
Views
3K
Replies
2
Views
956
  • Last Post
Replies
8
Views
4K
  • Last Post
Replies
2
Views
570
  • Last Post
Replies
2
Views
5K
Replies
2
Views
3K
Top