| Transfinite Recursion |
Website Links For Induction |
Information AboutTransfinite Recursion |
| CATEGORIES ABOUT TRANSFINITE INDUCTION | |
| ordinal numbers | |
|
TRANSFINITE INDUCTION Suppose whenever for all α < β, P (α) is true, 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:
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 three things:
Note that there's not much formal difference between the second and third clauses, but in practice they are so often different that it is useful to present them separately. 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 ''yRx'' must be a set.) RELATIONSHIP TO AC There is a popular misconception that transfinite induction, or transfinite recursion, or both, require the Axiom Of Choice (AC). This is incorrect. However it is very often the case that proofs or constructions using the technique ''do'' use AC. |
|
|