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

The first step of the transfinite recursion is simple: T₀ = {t}. T₀ 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₁ and T₂. T₀ 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₁ = {t, t_1,1, t_1,2}. T₁ 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₁ and eight subsets of T₁, we can generate 24 true statements of the form t_2,j, 1<= j <= 24, two of which were in T₁ (left as an exercise for the interested reader). T₂ 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₃.

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.