Namespaces
Variants
Actions

Difference between revisions of "Induction axiom"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
The assertion of the validity for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i0507401.png" /> of some predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i0507402.png" /> defined on the set of all non-negative integers, if the following two conditions hold: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i0507403.png" /> is valid; and 2) for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i0507404.png" />, the truth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i0507405.png" /> implies that of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i0507406.png" />. The induction axiom is written in the form
+
{{TEX|done}}
 +
The assertion of the validity for all $x$ of some predicate $P(x)$ defined on the set of all non-negative integers, if the following two conditions hold: 1) $P(0)$ is valid; and 2) for any $x$, the truth of $P(x)$ implies that of $P(x+1)$. The induction axiom is written in the form
  
<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/i/i050/i050740/i0507407.png" /></td> </tr></table>
+
$$P(0)\&\forall x(P(x)\supset P(x+1))\supset\forall xP(x).$$
  
In applications of the induction axiom, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i0507408.png" /> is called the induction predicate, or the induction proposition, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i0507409.png" /> is called the induction variable, induction parameter or the variable with respect to which the induction is carried out (in those cases when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074010.png" /> contains other parameters apart from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074011.png" />). Here the verification of condition 1) is called the basis of the induction, while the verification of condition 2) is called the induction step. The assumption in 2) of the validity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074012.png" />, from which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074013.png" /> is then deduced, is called the induction hypothesis. The principle of (mathematical) induction in mathematics is the scheme of all induction axioms for all possible predicates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074014.png" />. In the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074015.png" /> of formal arithmetic (cf. [[Arithmetic, formal|Arithmetic, formal]]), the induction scheme consists merely of those induction axioms that correspond to predicates expressible in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074016.png" /> (these predicates form a countable set). It is this circumstance, namely the impossibility of expressing in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074017.png" /> induction in its full extent, that is responsible for the incompleteness of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074018.png" /> (see [[Gödel incompleteness theorem|Gödel incompleteness theorem]]).
+
In applications of the induction axiom, $P(x)$ is called the induction predicate, or the induction proposition, and $x$ is called the induction variable, induction parameter or the variable with respect to which the induction is carried out (in those cases when $P(x)$ contains other parameters apart from $x$). Here the verification of condition 1) is called the basis of the induction, while the verification of condition 2) is called the induction step. The assumption in 2) of the validity of $P(x)$, from which $P(x+1)$ is then deduced, is called the induction hypothesis. The principle of (mathematical) induction in mathematics is the scheme of all induction axioms for all possible predicates $P(x)$. In the system $\text{FA}$ of formal arithmetic (cf. [[Arithmetic, formal|Arithmetic, formal]]), the induction scheme consists merely of those induction axioms that correspond to predicates expressible in $\text{FA}$ (these predicates form a countable set). It is this circumstance, namely the impossibility of expressing in $\text{FA}$ induction in its full extent, that is responsible for the incompleteness of $\text{FA}$ (see [[Gödel incompleteness theorem|Gödel incompleteness theorem]]).
  
Sometimes one considers the following axiom instead of the induction axiom: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074019.png" /> be some property of non-negative integers; if for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074020.png" /> it follows from the assumption that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074021.png" /> is true for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074022.png" /> smaller than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074023.png" /> that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074024.png" /> is true, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074025.png" /> is true for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050740/i05074026.png" />. In other words,
+
Sometimes one considers the following axiom instead of the induction axiom: Let $P(x)$ be some property of non-negative integers; if for any $x$ it follows from the assumption that $P(y)$ is true for all $y$ smaller than $x$ that $P(x)$ is true, then $P(x)$ is true for all $x$. In other words,
  
<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/i/i050/i050740/i05074027.png" /></td> </tr></table>
+
$$\forall x((\forall y<x)P(y)\supset P(x))\supset\forall xP(x).$$
  
 
This axiom is called the complete or recursive induction axiom. The principle of complete induction is equivalent to the principle of ordinary induction. See also [[Transfinite induction|Transfinite induction]].
 
This axiom is called the complete or recursive induction axiom. The principle of complete induction is equivalent to the principle of ordinary induction. See also [[Transfinite induction|Transfinite induction]].

Revision as of 19:21, 16 April 2014

The assertion of the validity for all $x$ of some predicate $P(x)$ defined on the set of all non-negative integers, if the following two conditions hold: 1) $P(0)$ is valid; and 2) for any $x$, the truth of $P(x)$ implies that of $P(x+1)$. The induction axiom is written in the form

$$P(0)\&\forall x(P(x)\supset P(x+1))\supset\forall xP(x).$$

In applications of the induction axiom, $P(x)$ is called the induction predicate, or the induction proposition, and $x$ is called the induction variable, induction parameter or the variable with respect to which the induction is carried out (in those cases when $P(x)$ contains other parameters apart from $x$). Here the verification of condition 1) is called the basis of the induction, while the verification of condition 2) is called the induction step. The assumption in 2) of the validity of $P(x)$, from which $P(x+1)$ is then deduced, is called the induction hypothesis. The principle of (mathematical) induction in mathematics is the scheme of all induction axioms for all possible predicates $P(x)$. In the system $\text{FA}$ of formal arithmetic (cf. Arithmetic, formal), the induction scheme consists merely of those induction axioms that correspond to predicates expressible in $\text{FA}$ (these predicates form a countable set). It is this circumstance, namely the impossibility of expressing in $\text{FA}$ induction in its full extent, that is responsible for the incompleteness of $\text{FA}$ (see Gödel incompleteness theorem).

Sometimes one considers the following axiom instead of the induction axiom: Let $P(x)$ be some property of non-negative integers; if for any $x$ it follows from the assumption that $P(y)$ is true for all $y$ smaller than $x$ that $P(x)$ is true, then $P(x)$ is true for all $x$. In other words,

$$\forall x((\forall y<x)P(y)\supset P(x))\supset\forall xP(x).$$

This axiom is called the complete or recursive induction axiom. The principle of complete induction is equivalent to the principle of ordinary induction. See also Transfinite induction.

References

[1] S.C. Kleene, "Mathematical logic" , Wiley (1967)
How to Cite This Entry:
Induction axiom. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Induction_axiom&oldid=18450
This article was adapted from an original article by S.K. Sobolev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article