Transfinite induction

related topics
{math, number, function}

Transfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinals or cardinals.

Contents

Transfinite induction

Let P(α) be a property defined for all ordinals α. Suppose that whenever P(β) is true for all β < α, then P(α) is also true. Then transfinite induction tells us that P is true for all ordinals.

That is, if P(α) is true whenever P(β) is true for all β < α, then P(α) is true for all α. Or, more practically: in order to prove a property P for all ordinals α, one can assume that it is already known for all smaller β < α.

Usually the proof is broken down into three cases:

  • Zero case: Prove that P(0) is true.
  • Successor case: Prove that for any successor ordinal α+1, P(α+1) follows from P(α) (and, if necessary, P(β) for all β < α).
  • Limit case: Prove that for any limit ordinal λ, P(λ) follows from [P(β) for all β < λ].

Notice that the second and third case are identical except for the type of ordinal considered. They do not formally need to be proved separately, but in practice the proofs are typically so different as to require separate presentations.

Transfinite recursion

Transfinite recursion is a method of constructing or defining something and is closely related to the concept of transfinite induction. As an example, a sequence of sets Aα is defined for every ordinal α, by specifying how to determine Aα from the sequence of Aβ for β < α.

More formally, we can state the Transfinite Recursion Theorem as follows. Given a class function G: VV, there exists a unique transfinite sequence F: Ord → V (where Ord is the class of all ordinals) such that

As in the case of induction, we may treat different types of ordinals separately: another formulation of transfinite recursion is that given a set g1, and class functions G2, G3, there exists a unique function F: Ord → V such that

  • F(0) = g1,
  • F(α + 1) = G2(F(α)), for all α ∈ Ord,
  • F(λ) = G3(F \upharpoonright λ), for all limit λ ≠ 0.

Note that we require the domains of G2, G3 to be broad enough to make the above properties meaningful. The uniqueness of the sequence satisfying these properties can be proven using transfinite induction.

More generally, one can define objects by transfinite recursion on any well-founded relation R. (R need not even be a set; it can be a proper class, provided it is a set-like relation; that is, for any x, the collection of all y such that y R x must be a set.)

Full article ▸

related documents
Tuple
Linear classifier
Fermat's little theorem
Floor and ceiling functions
Bounded set
Pre-Abelian category
Twin prime
Burali-Forti paradox
PSPACE
ElGamal encryption
Fuzzy set
Principal ideal
Discrete space
Entailment
Initial and terminal objects
Torsion subgroup
Monomorphism
Loss of significance
Triangle inequality
Caesar cipher
Binary space partitioning
Harmonic series (mathematics)
Multiplication table
Esoteric programming language
Simple group
Coset
Infimum
Inverse element
Bézout's theorem
Interior (topology)