Principle of transfinite induction?

Question

Could anyone please explain what such principle is?

Answer 1

The principle of mathematical induction relies on the fact that every positive integer has an immediate succesor, namely the given number plus one. The way it works is that if you have a sequence of statements P(1), P(2), ... and you know that

1. P(1) is true
2. Whenever P(n) is true, then P(n+1) must be true

then you can deduce that P(n) is true for every positive integer n. Why? Simply because P(1) is true, and therefore P(2) is true by #2. And so, P(3) is true since P(2) is true... etc. Given any fixed n (say 10,000), you can deduce that P(n) is true in finitely many steps.

Okay, now say you have a family of statements P(a) where a ranges over the elements of some set A. We'd like a principle of induction for showing that all the statements P(a) are true. The problem is that A does not have the "immediate successor" property.

The solution? The well-ordering principle says that we can order the elements of set A so that every nonempty subset B of A has a least element. In particular, if A is nonempty, then there is a minimal element a_0. Now consider the set of elements of A which are greater than a_0. If this is nonempty, then it has a minimal element. Call this a_1. This is the immediate successor of a_0.

So, the principle of transfinite induction works just like usual induction once you choose a well-ordering of the indexing set A:

If you know that

1. P(a_0) is true
2. Whenever P(a) is true, then P(a') is true, where a' is the immediate successor of a.

then you can deduce that P(a) is true for all a in A.

Now, this is somewhat dubious in the sense that given a particular a, it may take infinitely many deductions to show that P(a) is true by starting with the fact that P(a_0) is true.

Nonetheless, mathematicians accept transfinite induction as a valid way to prove theorems. (The logic is fine, but a solution by transfinite induction does not give an effective (i.e. algorithmic) solution to the problem.)

Answer 2

You need to take this in two steps.
First is to look at the principle of mathematical induction. Here is a good explanation..........
http://en.wikipedia.org/wiki/Mathematical_induction

Next move on to transfinite induction. Once again, here is a good explanation..............
http://en.wikipedia.org/wiki/Transfinite_induction

Mathematical induction is a form of logical, deductive reasoning done in such a way that mathematicians will nod their heads and agree with it.

Answer 3

it seems to me that transfinite indution is the same as induction.

First proove that some statement (over integeres) is correct for all n < N

Next given that the statement holds for n < N
Proof that it also holds for n+1 ( the induction step )

et voila c'est tout

Answer 4

to confuse you...