Transfinite inductionとは 意味・読み方・使い方

使用する際の注意点

• Suppose ${\displaystyle P(\alpha )}$ is a property defined for any ordinal number ${\displaystyle \alpha }$, and that whenever ${\displaystyle P(\beta )}$ is true for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta <\alpha }"> β < α {\displaystyle \beta <\alpha } <img loading="lazy" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/75a2847a928d4dc604cb25f967a3911fa4cc3f22" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.918ex; height:2.509ex;" alt="{\displaystyle \beta <\alpha }">, then ${\displaystyle P(\alpha )}$ is also true. Then transfinite induction tells us that ${\displaystyle P}$ is true for all ordinals.
• A transfinite induction proof is typically broken down into three cases:
  • Zero case: ${\displaystyle P(0)}$.
  • Successor case: For any ordinal number ${\displaystyle \alpha +1}$ that is the successor of some ordinal ${\displaystyle \alpha }$, ${\displaystyle P(\alpha )\implies P(\alpha +1)}$. (Alternatively, if necessary, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [\forall \beta <\alpha ,P(\beta )]\implies P(\alpha )}"> [ ∀ β < α , P ( β ) ] ⟹ P ( α ) {\displaystyle [\forall \beta <\alpha ,P(\beta )]\implies P(\alpha )} <img loading="lazy" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/41425004b196fd19a4301681d76ea78accff9adb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.854ex; height:2.843ex;" alt="{\displaystyle [\forall \beta <\alpha ,P(\beta )]\implies P(\alpha )}">.)
  • Limit case: For any limit ordinal (non-successor ordinal) ${\displaystyle \lambda }$, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [\forall \beta <\lambda ,P(\beta )]\implies P(\lambda )}"> [ ∀ β < λ , P ( β ) ] ⟹ P ( λ ) {\displaystyle [\forall \beta <\lambda ,P(\beta )]\implies P(\lambda )} <img loading="lazy" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c0a987eae8330203e11e15c69b5d86b3856beaa1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.589ex; height:2.843ex;" alt="{\displaystyle [\forall \beta <\lambda ,P(\beta )]\implies P(\lambda )}">.
• Some proofs involve first using the (historically controversial) axiom of choice to construct a well-ordered relation (enabling transfinite induction over its equivalence classes). If a well-ordered relation already exists, this step is unnecessary.
• For many purposes, transfinite induction is used only up to the smallest epsilon number, ${\displaystyle \varepsilon _{0}}$.

同意語

• (extension of mathematical induction to well-ordered sets of transfinite cardinality): Noetherian induction, structural induction, well-founded induction

下位語

• (extension of mathematical induction to well-ordered sets of transfinite cardinality): ε-induction, epsilon-induction

関連する語

• transfinite number
• transfinite recursion

参考

• well-founded relation

Further reading

• Epsilon-induction on Wikipedia.Wikipedia
• Mathematical induction on Wikipedia.Wikipedia
• Transfinite number on Wikipedia.Wikipedia
• Well-founded relation on Wikipedia.Wikipedia