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.

 

[blue_raver22]

Transfinite induction is a powerful mathematical tool that allows us to prove statements about infinitely large sets. It is based on the concept of ordinal numbers, which are a way of ordering different sizes of infinity.

The idea behind transfinite induction is similar to regular mathematical induction, where we prove a statement for all natural numbers by showing that it holds for the first number (usually 0 or 1) and then assuming it holds for a general number and showing that it also holds for the next number. However, with transfinite induction, we are dealing with infinite sets, so instead of just showing that the statement holds for the next number, we have to show that it holds for the next infinite size.

One example of transfinite induction is proving that every countable set (a set with the same size as the set of natural numbers) has a well-ordering, meaning that its elements can be arranged in a specific order. This can be done by using transfinite induction on the ordinal number ω, which represents the size of the set of natural numbers.

To answer your question about when transfinite induction may not coincide with regular induction, it is important to note that transfinite induction only works for well-ordered sets. If a set is not well-ordered, then regular induction may not be equivalent to transfinite induction. An example of this is trying to prove that every set has a well-ordering using transfinite induction on the ordinal number ω+1, which represents the size of the set of natural numbers plus one additional element. This would not work because the set of natural numbers plus one additional element is not well-ordered, so regular induction is not equivalent to transfinite induction in this case.

I would recommend further exploring the concept of transfinite induction in a book on set theory or mathematical logic. Some suggestions include "Set Theory: An Introduction to Independence Proofs" by Kenneth Kunen and "Mathematical Logic" by Joseph R. Shoenfield. I hope this helps clarify the concept of transfinite induction for you.