Transfinite Induction: Understanding & Examples

[Hjensen]

I'm a bit confused on the subject of transfinite induction. I've read that it is equivalent to usual induction on the ordinal number ω (presumably a proof of this can be found in a standard book on the subject - any suggestions?)

Does anyone have an example of a case in which this isn't true? In other words where these two forms of induction do not coincide? I can't seem to think of one myself.

 

[Hjensen]

Perhaps I should clarify a few things. By ω I mean the least infinite ordinal, which is identified with \aleph_0.

The idea I have of the two notions being different relies on intuition only. If anyone has a concrete example, you would make my day. Especially if you could include a reference to a proof of the fact that transfinite induction is equivalent to regular induction on the ordinal ω

 

[dcpo]

Transfinite induction allows you to use induction proofs over ordinals greater than \omega, ordinary induction only allows you to prove things over \omega. The key difference is that transfinite induction involves a limit case to take into account limit ordinals i.e. if the property holds for every ordinal before the limit ordinal then it must be shown that it also holds for limit ordinal.

To see why this is important consider the statement 'every ordinal greater than 0 is a successor to some unique ordinal'. This is true for ordinals less than \omega, but is not true in general, e.g. for \omega itself. However, the successor step in an induction proof will be trivially true, so to avoid 'proving' untrue things you need a limit step too for ordinals larger than \omega.

Transfinite induction is trivially equivalent to classical induction over \omega as there are no limit ordinals smaller than \omega.

 

[theorem4.5.9]

Transfinite induction is very close in spirit to that of strong induction. You assume that a statement $P(x)$ is true for every $x<a$, and then show it's true for $x=a$. In typical induction, you are only concerned with the whole numbers, though in transfinite induction you instead look over any other ordinal. The basic mechanics of the approach is the same.