Namespaces
Variants
Actions

Difference between revisions of "Transfinite induction"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (Completed rendering of article in TeX.)
 
Line 1: Line 1:
A principle enabling one to infer that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t0936801.png" /> holds for every element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t0936802.png" /> of a well-ordered class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t0936803.png" /> if it is established that for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t0936804.png" /> the truth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t0936805.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t0936806.png" /> implies the truth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t0936807.png" />:
+
A principle enabling one to infer that a proposition $ A(x) $ holds for every element $ x $ of a well-ordered class $ (E,<) $ if it is established that for each $ z \in E $, the truth of $ A(y) $ for all $ y < z $ implies the truth of $ A(z) $:
 +
$$
 +
(\forall z)((\forall y)((y < z) \Longrightarrow A(y)) \Longrightarrow A(z)) \Longrightarrow (\forall x) A(x).
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t0936808.png" /></td> </tr></table>
+
When $ E $ is the segment of [[Ordinal number|ordinal number]]s less than $ \alpha $, we have the following equivalent formulation: If
  
When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t0936809.png" /> is the segment of ordinal numbers less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368010.png" /> (cf. [[Ordinal number|Ordinal number]]), the following is an equivalent formulation: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368011.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368012.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368013.png" /> is preserved under limits, i.e.
+
* $ A(0) $,
 +
* $ A(\beta) \Longrightarrow A(\beta + 1) $, and
 +
* $ A(\cdot) $ is preserved under limits, i.e., $ \displaystyle \left( \left( \beta = \sup_{i \in I} \beta_{i} \right) \land (\forall i \in I) A(\beta_{i}) \right) \Longrightarrow A(\beta) $,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368014.png" /></td> </tr></table>
+
then $ A(\beta) $ for any $ \beta < \alpha $. A special case of transfinite induction is [[Mathematical induction|mathematical induction]]. If the relation $ < $ defines on the class $ E $ a well-founded tree (i.e., a tree all branches of which terminate), then transfinite induction for such an $ E $ is equivalent to [[Bar induction|bar induction]]: If $ A $ is true for all end vertices and is inherited on moving from them towards the root, then $ A $ is true for the root. This form is important in intuitionistic mathematics. The deductive power of a formal system can often be measured in terms of the provability of transfinite induction up to various ordinals.
  
then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368015.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368016.png" />. A special case of transfinite induction is [[Mathematical induction|mathematical induction]]. If the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368017.png" /> defines on the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368018.png" /> a well-founded tree (i.e. a tree all branches of which terminate), then transfinite induction for such an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368019.png" /> is equivalent to [[Bar induction|bar induction]]: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368020.png" /> is true for all end vertices and is inherited on moving from them towards the root, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093680/t09368021.png" /> is true for the root. This form is important in intuitionistic mathematics. The deductive power of a formal system can often be measured in terms of provability of transfinite induction up to various ordinals.
+
====References====
 
 
 
 
 
 
====Comments====
 
  
 
+
<table>
====References====
+
<TR><TD valign="top">[a1]</TD><TD valign="top">
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> S. Feferman,   "Theories of finite type related to mathematical practice"  J. Barwise (ed.) , ''Handbook of mathematical logic'' , North-Holland (1977) pp. 913–972</TD></TR></table>
+
S. Feferman, “Theories of finite type related to mathematical practice”, J. Barwise (ed.), ''Handbook of mathematical logic'', North-Holland (1977), pp. 913–972.</TD></TR>
 +
</table>

Latest revision as of 18:35, 28 December 2016

A principle enabling one to infer that a proposition $ A(x) $ holds for every element $ x $ of a well-ordered class $ (E,<) $ if it is established that for each $ z \in E $, the truth of $ A(y) $ for all $ y < z $ implies the truth of $ A(z) $: $$ (\forall z)((\forall y)((y < z) \Longrightarrow A(y)) \Longrightarrow A(z)) \Longrightarrow (\forall x) A(x). $$

When $ E $ is the segment of ordinal numbers less than $ \alpha $, we have the following equivalent formulation: If

  • $ A(0) $,
  • $ A(\beta) \Longrightarrow A(\beta + 1) $, and
  • $ A(\cdot) $ is preserved under limits, i.e., $ \displaystyle \left( \left( \beta = \sup_{i \in I} \beta_{i} \right) \land (\forall i \in I) A(\beta_{i}) \right) \Longrightarrow A(\beta) $,

then $ A(\beta) $ for any $ \beta < \alpha $. A special case of transfinite induction is mathematical induction. If the relation $ < $ defines on the class $ E $ a well-founded tree (i.e., a tree all branches of which terminate), then transfinite induction for such an $ E $ is equivalent to bar induction: If $ A $ is true for all end vertices and is inherited on moving from them towards the root, then $ A $ is true for the root. This form is important in intuitionistic mathematics. The deductive power of a formal system can often be measured in terms of the provability of transfinite induction up to various ordinals.

References

[a1] S. Feferman, “Theories of finite type related to mathematical practice”, J. Barwise (ed.), Handbook of mathematical logic, North-Holland (1977), pp. 913–972.
How to Cite This Entry:
Transfinite induction. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Transfinite_induction&oldid=15594
This article was adapted from an original article by G.E. Mints (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article