Hello I'm self studying and I'm also new to proofs and would like to know whether my proof is rigorous enough for a first course in Abstract Algebra.
I'm asked to proof Induction of the second kind which states that:
Suppose P(n) is a statement about the positive integers and c is some fixed positive integer. Assume
i) P(c) is true
ii) for every $m > c $, if P(k) is true for all k such that $c \leq k < m $ , then P(m) is true
Then P(n) is true for all $n \geq c $
The proof also has to use the well-ordering principle which states that:
Every nonempty subset of the positive integers has a smallest element.
My proof:
First let $M = \{x\mid x \in N \land x>c \land P(x) \text{ is false} \}$
Now we assume M is nonempty. Then by the well-ordering principle there exists a smallest element of M which we'll call $y.$ We know that $P(n)$ for all $c \leq n < y $ is true thus $P(y)$ is true by ii. This is a contradiction thus $M$ is the empty set which means that $P(n)$ is true for all $n \geq c $
I'm self-studying and do not know whether my proof would be acceptable for a intro abstract algebra class. So my questions are:
- Is my proof correct?
- and if it's not correct, why not and how would I prove it then?
- and if it's correcct, is there anything you would change?
Thanks in advance.
Best Answer
As said in the other answer, the proof is almost correct, however I would "fix" it differently.
Namely, nothing is wrong with your set $M$ the way it is, but this only lets you conclude that $P(n)$ is true for $n\gt c$. Now (and that is the missing step, however trivial), you use (i), which says $P(c)$ is true too, to conclude $P(n)$ is true for $n\ge c$.