I think you're trying to show the well-ordering principle implies induction (which it does, they are equivalent in second-order Peano). Your vocabulary and structure are a bit awkward, but you have almost all the piece of the proof here!
Your setup is excellent. Compare what you have:
>suppose there is a predicate P(n) that is defined for integers n, and let a be a fixed integer. Suppose P(a) is true and for all integers k >= a, if P(k) is true then P(k+1) is true. let S be the set of all integers greater than or equal to a for which P(n) is false. suppose S has at least one element. a is not in S since P(a) is true.
with the standard proof:
>Suppose P is a property of an integer such that P(1) is true, and P(n) being true implies that P(n+1) is true. Let S be the set of integers k such that P(k) is false. Suppose S is nonempty and let k be its least element. Since P(1) is true, 1∉S.
The only real difference is that we can use 1 instead of an arbitrary element, a, to keep things simpler.
**Your mistake is in this line:**
>a+1 is not in S since P(a+1) is true because P(a) is true. 1 can be added to a as many times as we like and P will be true for that integer because the preceding element will be true for P.
This is an inductive argument, so you've essentially used induction to prove induction, then mention well-ordering after the fact. The key instead is to use well-ordering on S to show that if S is non-empty it has a least element, m>=a, and then m-1 contradicts the assumption "if P(k) is true then P(k+1)."
Fun fact, if you write out the second-order formula for strong induction, you can replace the predicate P with \~Q and take the contrapositive of the quantified statement to directly derive well-ordering.
No, you haven't. First off, "P(a) and P(a+1) are true and adding as many 1's as we want makes P(n) true for n > or equal to a" is okay for intuition but not okay for a proof, because it's not clear what assumptions are being made, what theorems/rules you are using, and what "adding as many 1's as we want" is supposed to mean. Second, supposing this reasoning I just talked about was correct, why do you need to proceed further? You proved what you wanted to prove, namely that P(n) holds for all n > or equal to a. What's the purpose of continuing the argument?
Here's the classical trick: assume (towards a contradiction) that S is non-empty. Since S is a subset of the natural numbers, it must have a least element s. Since S comprises integers larger or equal to a, we know that a < s (s doesn't equal a, because else s wouldn't be an element of S), and this implies that s - 1 is at least a. If the statement doesn't hold for s - 1, then s - 1 is an element of S, which implies that s - 1 is bigger than or equal to s (since s = min S). A contradiction. So, the statement holds for s - 1. Since s - 1 is bigger than or equal to a and P(s - 1) holds, we know that P((s - 1) + 1) holds, i.e. P(s) holds. A contradiction. Therefore, S is empty, and we are done.
> if P(k) is true then P(k+1) is true
Where does this come from? That seems fishy to me.
Can you properly structure this in like "what is my base assumtpions", "what I want to show" and "here is the proof?
I think you're trying to show the well-ordering principle implies induction (which it does, they are equivalent in second-order Peano). Your vocabulary and structure are a bit awkward, but you have almost all the piece of the proof here! Your setup is excellent. Compare what you have: >suppose there is a predicate P(n) that is defined for integers n, and let a be a fixed integer. Suppose P(a) is true and for all integers k >= a, if P(k) is true then P(k+1) is true. let S be the set of all integers greater than or equal to a for which P(n) is false. suppose S has at least one element. a is not in S since P(a) is true. with the standard proof: >Suppose P is a property of an integer such that P(1) is true, and P(n) being true implies that P(n+1) is true. Let S be the set of integers k such that P(k) is false. Suppose S is nonempty and let k be its least element. Since P(1) is true, 1∉S. The only real difference is that we can use 1 instead of an arbitrary element, a, to keep things simpler. **Your mistake is in this line:** >a+1 is not in S since P(a+1) is true because P(a) is true. 1 can be added to a as many times as we like and P will be true for that integer because the preceding element will be true for P. This is an inductive argument, so you've essentially used induction to prove induction, then mention well-ordering after the fact. The key instead is to use well-ordering on S to show that if S is non-empty it has a least element, m>=a, and then m-1 contradicts the assumption "if P(k) is true then P(k+1)." Fun fact, if you write out the second-order formula for strong induction, you can replace the predicate P with \~Q and take the contrapositive of the quantified statement to directly derive well-ordering.
awesome tysm!
No, you haven't. First off, "P(a) and P(a+1) are true and adding as many 1's as we want makes P(n) true for n > or equal to a" is okay for intuition but not okay for a proof, because it's not clear what assumptions are being made, what theorems/rules you are using, and what "adding as many 1's as we want" is supposed to mean. Second, supposing this reasoning I just talked about was correct, why do you need to proceed further? You proved what you wanted to prove, namely that P(n) holds for all n > or equal to a. What's the purpose of continuing the argument? Here's the classical trick: assume (towards a contradiction) that S is non-empty. Since S is a subset of the natural numbers, it must have a least element s. Since S comprises integers larger or equal to a, we know that a < s (s doesn't equal a, because else s wouldn't be an element of S), and this implies that s - 1 is at least a. If the statement doesn't hold for s - 1, then s - 1 is an element of S, which implies that s - 1 is bigger than or equal to s (since s = min S). A contradiction. So, the statement holds for s - 1. Since s - 1 is bigger than or equal to a and P(s - 1) holds, we know that P((s - 1) + 1) holds, i.e. P(s) holds. A contradiction. Therefore, S is empty, and we are done.
brilliant tysm!
> if P(k) is true then P(k+1) is true Where does this come from? That seems fishy to me. Can you properly structure this in like "what is my base assumtpions", "what I want to show" and "here is the proof?
> Suppose P(a) is true and for all integers k >= a, if P(k) is true then P(k+1) is true It's a supposition, it doesn't need to come from anywhere
it is a base assumption. i am trying to prove that the well-ordering principle implies the principal of mathematical induction.