Well Ordering Principle

[altt-gaming]

Question

The well ordering principle states that every non-empty subset of the natural
numbers contains a smallest element.
(1) Write the statement of the well ordering principle using symbols.
(2) Prove carefully that the well ordering principle implies the principal of
mathematical induction. That is, suppose the P(n) is a predicate about
natural numbers n. Suppose that P(1) is true, and suppose also that for
all n in N, P(n+1) is true if P(n) is true. Using the well ordering principle
prove that then P(n) is true for all n. (Hint: consider the set of natural
numbers n for which P(n) is false.)

I understand the first part:

1) A subset of N, A not = empty set, for all a in A, there exists b in A, such that b|a >= 1 (not sure how to write these with symbols on the forum)

2) The toughest part of this exercise is to figure out a proper predicate as P(n). I was thinking something along the lines of:

for A subset of N, for A = {0,1,2,...,n}, but what exactly could I prove with mathematical induction and well ordering principle other than what I proved in part 1?

 

[daon]

There is more than one way to write that statement "in symbols." One way would be:

\(\displaystyle \emptyset \neq A \subset \mathbb{N} \,\, \Rightarrow \,\, \exists n_0 \in A \,\, s.t. \,\, \forall n \in A, n_0 \le n.\)

P(n) could be any statement. You are assuming the well-ordering principle is true, P(1) is true, and P(n) => P(n+1). You want to show P(n) is true for all n.

Suppose there was a number k such that P(k) is false. Then the set {n | P(n) = false} is a nonempty subset of the natural numbers. It must then have a least element.

Can you finish from here?

 

[altt-gaming]

I guess i'm not understanding the question. Am I supposed to take the well ordering principle as the statement to prove via mathematical induction?

If P(k) was false, then wouldn't mathematical induction not work on P(n) and I would come up with a proof against the statement P(n)?

 

[daon]

No, your task is to prove the proposition of mathematical induction. The above proof I started is called an indirect proof or proof by contradiction. Assume P(k) is false for some k, then end up with P(k) is true using the assumptions that 1. The Well-ordeing principle holds, and 2. P(1) is true and P(n)=>P(n+1).