**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Transfinite induction

Summary

Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC.
Let be a property defined for all ordinals . Suppose that whenever is true for all , then is also true. Then transfinite induction tells us that is true for all ordinals.
Usually the proof is broken down into three cases:
Zero case: Prove that is true.
Successor case: Prove that for any successor ordinal , follows from (and, if necessary, for all ).
Limit case: Prove that for any limit ordinal , follows from for all .
All three cases are identical except for the type of ordinal considered. They do not formally need to be considered separately, but in practice the proofs are typically so different as to require separate presentations. Zero is sometimes considered a limit ordinal and then may sometimes be treated in proofs in the same case as limit ordinals.
Transfinite recursion is similar to transfinite induction; however, instead of proving that something holds for all ordinal numbers, we construct a sequence of objects, one for each ordinal.
As an example, a basis for a (possibly infinite-dimensional) vector space can be created by starting with the empty set and for each ordinal α > 0 choosing a vector that is not in the span of the vectors . This process stops when no vector can be chosen.
More formally, we can state the Transfinite Recursion Theorem as follows:
Transfinite Recursion Theorem (version 1). Given a class function G: V → V (where V is the class of all sets), there exists a unique transfinite sequence F: Ord → V (where Ord is the class of all ordinals) such that
for all ordinals α, where denotes the restriction of Fs domain to ordinals < α.
As in the case of induction, we may treat different types of ordinals separately: another formulation of transfinite recursion is the following:
Transfinite Recursion Theorem (version 2)'''. 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,
for all limit λ ≠ 0.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (7)

Related concepts (16)

Related courses (12)

Related lectures (74)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

MATH-351: Advanced numerical analysis

The student will learn state-of-the-art algorithms for solving differential equations. The analysis and implementation of these algorithms will be discussed in some detail.

MATH-318: Set theory

Set Theory as a foundational system for mathematics. ZF, ZFC and ZF with atoms. Relative consistency of the Axiom of Choice, the Continuum Hypothesis, the reals as a countable union of countable sets,

Ordinal number

In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, nth, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the least natural number that has not been previously used. To extend this process to various infinite sets, ordinal numbers are defined more generally as linearly ordered labels that include the natural numbers and have the property that every set of ordinals has a least element (this is needed for giving a meaning to "the least unused element").

Mathematical induction

Mathematical induction is a method for proving that a statement is true for every natural number , that is, that the infinitely many cases all hold. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder: Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step). A proof by induction consists of two cases.

Well-order

In mathematics, a well-order (or well-ordering or well-order relation) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. The set S together with the well-order relation is then called a well-ordered set. In some academic articles and textbooks these terms are instead written as wellorder, wellordered, and wellordering or well order, well ordered, and well ordering. Every non-empty well-ordered set has a least element.

Explains the Implicit Euler Scheme, a method for solving differential equations numerically, focusing on stability and convergence properties.

Covers Cauchy sequences, convergence, and induction in mathematical analysis.

Explores the convergence of geometric series and their applications in real-world problems.

The Center for Artificial Muscle (CAM) is in the process of designing a new type of Vascular Assist Device (VAD) that uses the mechanical and electrical properties of Dielectric Elastomer Actuators (DEAs). The main challenges with these actuators are that ...

2019Dielectric metasurfaces require the integration of large index contrast materials with accurate control over position and size for high optical efficiency. Their fabrication usually relies on well-established lithographic techniques. While lithography bear ...

Pierre Dillenbourg, Jennifer Kaitlyn Olsen, Louis Pierre Faucon

Inductive reasoning is an important educational practice but can be difficult for teachers to support in the classroom due to the high level of preparation and classroom time needed to choose the teaching materials that challenge students' current views. I ...