Try proving stuff.

Ie: Let N be the natural numbers, defined (slightly informally) as:

0 is an element of N

For each element x in N, succ(x) is an element of N.

"=" is an equivalence relation on elements of N (look up what an equivalence relation is)

"+" is an operator that takes two values from N, and returns a value from N. Ie, for a, b from N, a+b is an element of N.

"*" is an operator that takes two values from N, and returns a value from N. Ie, for a, b from N, a*b is an element of N.

1 = succ(0)

For each element a in N, a+0 = a

For each element a, b in N, a+b = b+a

For each element a, b in N, a+succ(b) = succ(a+b), and succ(a)+b = succ(a+b)

For each element a in N, a*1 = a

For each element a, b in N, a*b = b*a

For each element a, b in N, a*succ(b) = a*b + a, and succ(a)*b = a*b+b

For each element a, b, c in N, a*(b+c) = a*b + a*c

For each element a in N, a < succ(a)

For each element a, b in N, a<b is the same as b>a, and a<=b is the same as b>=a

For each element a, b in N, a<=b means a<b or a=b

For each element a, b in N, either a<b or a>=b.

For each element a, b, c in N, if a<b and b<c, then a<c.

For each element a, b in N, if a<b, then a<succ(b).

...

I think that is more than enough to give you the natural numbers, but I left out induction.

So your task:

Prove that the Well Ordering Principle is implies the Principle of Mathematical Induction.

Well Ordering Principle: Let X be some subset of N. Then there is an element a from X such that for all elements b of X, a<=b.

Principle of Mathematical Induction: Let P(x) be some property of elements of N.

If P(0) is true, and ( For all elements a of N, P(a) is true implies P(succ(a)) is true ), then:

For all elements a of N, P(a) is true

Step 2: Define the "Principle of strong induction" to be:

Let P(x) be some property of elements of N.

If P(0) is true, and for each element a from N ((For each element b < a from N, P(b) is true) implies P(a) is true), then

For each element a of N, P(a) is true.

Show that The Principle of Mathematical Induction implies the Principle of Strong induction.

Step 3: show that the Principle of Strong Induction implies the Well Ordering Principle.

Note that this implies that the three principles are equivalent, as assuming any one of them proves the other 2!

I think that was, roughly, the very first proof assignment given to me at university. I

think the prof did one of the 3 steps in class, and we did the other 2.

Can you think of how to approach this?