Thursday, July 22, 2010

A primer on transfinitie recursion

I am going to discuss a transfinite recursion in this post, as a prelude to filling in the argument from last July pointing out that the attempted argument by Dr. Vallicella against the possible existence of a maximal collection of truths, to which I wrote a response last July. Today, that response seems inadequate, so I intend to do the proof more comprehensively. That way, in the future I can just link to the new post whenever Dr. Vallicella decides to raise this argument again, as he did last week.

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.
2! = 2 * 1! = 2 * 1 = 2.
3! = 3 * 2! = 3 * 2 = 6.
4! = 4 * 3! = 4 * 6 = 24.
5! = 5 * 4! = 5 * 24 = 120.
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.

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 Tx of truths derived from t, Tx is a subset of T.

The first step of the transfinite recursion is simple: T0 = {t}. T0 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 T1 and T2. T0 has two subsets, {} and {t}, and one element, {t}. t ε {t} (we can call this truth t1,1) and t ~ε {} (we can call this truth t1,2). Then, T1 = {t, t1,1, t1,2}. T1 has eight subsets: {}, {t}, {t1,1}, {t1,2}, {t, t1,1}, {t, t1,2}, {t1,1, t1,2}, and {t, t1,1, t1,2}. With three elements of T1 and eight subsets of T1, we can generate 24 true statements of the form t2,j, 1<= j <= 24, two of which were in T1 (left as an exercise for the interested reader). T2 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 T3.

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: