A good background in ordinal numbers generally will be very helpful for understanding this post. I will not attempt to improve on the three-part series penned by Mark Chu-Carroll over at Good Math, Bad Math. For better or worse, I'll assume the reader understands that material and go from there below the fold.

Transfinite recursion is the process of defining a function over all of the ordinals. Recursive definitions are fairly common at the level of the finite. For example, the factorial function (identified by a bang, for example, 3!) comes up in pretty much any college level math class that mentions probability. Factorials can be defined recursively. You start off saying 0! = 1. Then, for any integer n > 0, n! = n * (n-1)!. Thus,

1! = 1 * 0! = 1 * 1 = 1.This is not the only way to define n!, but it is a useful way. This definition consisted of two steps: the definition for 0, and the definition for any number given the value for the immediately previous number.

2! = 2 * 1! = 2 * 1 = 2.

3! = 3 * 2! = 3 * 2 = 6.

4! = 4 * 3! = 4 * 6 = 24.

5! = 5 * 4! = 5 * 24 = 120.

With transfinite recursion, the same basic idea applies: for any particular ordinal ω, you use the definitions of some or all the ordinals β where β < ω to define the function on ω. If you can do that as a single definition, so much the better, but often these definitions consist of three steps: define the function for the first ordinal (0), define the function for each ordinal that has a direct predecessor (the are called successor ordinals), and define the function for ordinals that have predecessors, but no direct predecessor (these are called limit ordinals). As you might have noticed, the first two steps are the same as we saw for the definition of factorial. I will be using transfinite recursion to start with a single truth t, and generate from that a maximal collection of consistent truths T that derive from t. "Maximal" means: given any collection T

_{x}of truths derived from t, T

_{x}is a subset of T.

The first step of the transfinite recursion is simple: T

_{0}= {t}. T

_{0}is very obviously derived from t.

Edit: In my discussion in the next paragraph, I glected to account for the fact that T

_{β+1}will contain every truth in T

_{β}even without being unioned. This is corrected.

The next step will be to define T

_{β+1}given some T

_{β}derived from t. Of course, I will use the definition offered by Dr. Vallicella in his proof, otherwise there would be no point to this. T

_{β}will consist of truths, {t

_{β,1}, . . . , t

_{β,i}, t

_{β,i+1}, . . ., t

_{β,ω}} that derive from t. Consider the power set P(T

_{β}) of T

_{β}. The truth t

_{β,1}in T

_{β}will be a member of some of T

_{β}'s subsets but not of others. Thus, t

_{β,1}ε {t

_{β,1}, t

_{β,2}}, and t

_{β,1}~ε { } are both truths. In general, for each subset s in the power set P(T

_{β}) there will be a truth of the form t

_{β,1}ε s or t

_{β,1}~ε s. You can denote whichever of these statements is true by q(t

_{β,1},s). We then define T

_{β+1}= {q(t

_{β,i},s) | t

_{β,i}ε T

_{β}and s ε P(T

_{β})} union {t}, and say that T

_{β+1}is also derived from t. This is the process Dr. Vallicella uses to generate a larger set. Note that since every statement of T

_{β}is repeated in T

_{β+1}, T

_{β}is a subset of T

_{β+1}.

Before we move on, lets look at T

_{1}and T

_{2}. T

_{0}has two subsets, {} and {t}, and one element, {t}. t ε {t} (we can call this truth t

_{1,1}) and t ~ε {} (we can call this truth t

_{1,2}). Then, T

_{1}= {t, t

_{1,1}, t

_{1,2}}. T

_{1}has eight subsets: {}, {t}, {t

_{1,1}}, {t

_{1,2}}, {t, t

_{1,1}}, {t, t

_{1,2}}, {t

_{1,1}, t

_{1,2}}, and {t, t

_{1,1}, t

_{1,2}}. With three elements of T

_{1}and eight subsets of T

_{1}, we can generate 24 true statements of the form t

_{2,j}, 1<= j <= 24, two of which were in T

_{1}(left as an exercise for the interested reader). T

_{2}will consist of these 24 statements, and t, for twenty-five truths. In case you are curious, there are 25*2^25+25 (i.e. 838,860,825) statements in T

_{3}.

The third step is simple. For any limit ordinal ω, T

_{ω}is the union of all the T

_{β}where β < ω. Since all the statements of each T

_{β}are derived from t by the process in the previous paragraph, every element of T

_{ω}is derived from t.

The (proper) class of all of all ordinals is commonly called Ω. So, for each ω ε Ω, we have defined T

_{ω}. T is the union of all the T

_{ω}over all the ω ε Ω. T is now the maximal collection of truths derived from t. Since for any ordinal ω, #(T

_{ω}) >= #(ω) (that is, T

_{ω}at least as many elements as ω), T has more elements than any ordinal. Therefore, T must be a proper class. I'll discuss what this means in my next post.

## No comments:

Post a Comment