Quote:
Originally Posted by Mariogs379
Wow. I think I'm following but isn't the only important thing at the end that M is all natural numbers? I guess I'm confused about why S = all natural numbers is important...
S = all natural numbers is important, because that's how you showed (by induction on 'n') that m+1 is in M if m is in M. It's a mini-induction within an induction proof.
Quote:
The proof itself makes sense tho, hard to imagine doing that on my own
When you're proving something like "addition is commutative," you should recognize that you're not allowed to assume pretty much anything. I mean, if you can't even assume that 3+5 = 5+3, what the hell can you assume!?!?
So you can only use axioms and the statements you've proved from the axioms; here, this means a+0 = 0+a (axiom) and associativity (which we proved).
Quote:
I'm also a little bit confused about why you're using these sets, M and S...If I'm using induction to show that some series adds up to (n+1)(n+2)/2 or something, I never really use sets like that...any explanation there?
Thanks again brian
In my opinion, which is worth little since I'm not teaching your class, when you're learning to write proofs, you should have to be extremely explicit with each step of the proof. If I were to do an inductive proof in my thesis, I would not say "Let M = {m in M : P(m)}. First, we show 0 in M. Then we show m in M => (m+1) in M. Therefore M = all naturals." I would say something like
"We prove this by induction on m. For the base case, m=0, the following is true (...). Now assume that the statement is true for some m. We show that it's true for (m+1). (...). This proves the theorem."
But as a student, I think it's good to be pedantic and extremely clear about every step. If you want to show that something is true for all natural numbers, I think it's good to construct the set of numbers for which that something is true and show that it's the naturals (by first showing 0 is in there, and then showing that if 'n' is in there, so is 'n+1').
At least this was the way that I learned inductive proof at first. Actually, the way I learned induction was that
Any set S with the properties
(1) 0 is in S, and
(2) If n is in S, then n+1 is in S.
must contain the natural numbers.
Don't get too hung up on it. Hopefully, though, it makes a bit more sense now.