|
Ok, stupid me for not looking at wikipedia on the proof of validity for mathematical induction.
http://en.wikipedia.org/wiki/Mathematical_induction <--- scroll down to Proof or reformulation of mathematical induction and then the Generalization part.
Quick question, or clarification rather. Unforutnately I'm obsessing over induction at the moment (and have been since I made the first post refering to mathematical induction, and it not being "inductive" but rather deductive in nature)... and am stuck on the transfinite induction step if anyone care to help out with it... I've gotton this far working it out all over again... 
Peano's Axiom
There is a relational system <Nat, 0, s>, which satisfies the following axioms:
- There is a special element of Nat denoted by 0.
- s is the successor function from Nat to Nat
- s is one-one
- ~ (∀ k ∈ Nat : s(k) == 0)
- The Induction Axiom
Let S be any subset of Nat,
IF: (i ) (0 ∈ S) and (ii) (∀ k ∈ Nat) ∧ (∃ k ∈ S) ⇒ (s(k) ∈ S)
THEN: S == Nat
These three "assumptions"
- Nat is well-ordered.
- ∀ k, n ∈ Nat: (k == 0) ∨ (k == n +1)
- ∀ n ∈ Nat: (n << n +1)
Now the proof goes:
- We have a proposition P(n) defined on Nat where n is any natural number.
- ∃ m ∈ Nat: m < n
- S ⊆ Nat: (k ∈ Nat ∧ k < m)
- P(base case) is shown to be true.
- P(k) is shown to be true. (or that P is true for S)
- P(m) is shown to be true.
Now the last step left is to show that P(n) is true via 'Transfinite induction.' That's the step in the proof that not making any sense at the moment. 
Notation:
- ∃ <-- existential quantifier
- ∀ <-- universal quantifier
- ~ <-- negation
- ∧ <-- conjunction
- ∨ <-- disjunction
- ⇒ <-- implication
- ⇔ <-- material equivalence
- == <-- (mathematicaly) equality
- != <-- not equal
- <, > <-- less than, greater than
- ≤, ≥ <-- less than or equal, greater than or equal
- ∈ <-- is a member
- ⊆ <-- is a subset
- ø <-- empty set
- Nat <-- the set of natural numbers
EDIT: Oh, do not bother explaining it in words as language is a very poor medium for expressing complex concepts. Formal proofs only, or at least psuedo-formal.
___________________
"The Greatest enemy of knowledge is not ignorance, it is the illusion of knowledge." -Stephen Hawking
"First they came for the communists, and I did not speak out— because I was not a communist;
Then they came for the socialists, and I did not speak out— because I was not a socialist;
Then they came for the trade unionists, and I did not speak out— because I was not a trade unionist;
Then they came for the Jews, and I did not speak out— because I was not a Jew;
Then they came for me— and there was no one left to speak out for me." -Martin Niemöller
|