Namespaces
Variants
Actions

Difference between revisions of "Infinite induction"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
''Carnap's rule, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050870/i0508702.png" />-rule''
+
{{TEX|done}}
 +
''Carnap's rule, $\omega$-rule''
  
A non-elementary [[Derivation rule|derivation rule]] with an infinite number of premises. More exactly, let the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050870/i0508703.png" /> in some logico-mathematical language be regarded as ranging over the natural numbers, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050870/i0508704.png" /> be a formula of this language. If each formula in the infinite list
+
A non-elementary [[Derivation rule|derivation rule]] with an infinite number of premises. More exactly, let the variable $x$ in some logico-mathematical language be regarded as ranging over the natural numbers, and let $\phi(x)$ be a formula of this language. If each formula in the infinite list
  
<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/i050870/i0508705.png" /></td> </tr></table>
+
$$\phi(0),\phi(1),\ldots,\phi(n),\ldots,$$
  
can be derived, the rule of infinite induction permits to conclude that the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050870/i0508706.png" /> is derivable as well.
+
can be derived, the rule of infinite induction permits to conclude that the formula $\forall x\phi(x)$ is derivable as well.
  
The use of the rule of infinite induction in deriving formulas usually renders the problem of existence of a derivation undecidable. An axiomatic system containing an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050870/i0508707.png" />-rule is called a semi-formal theory (semi-formal axiomatic system). They play an important role in [[Proof theory|proof theory]]. In order to render the concept of a derivation in the theory effective, additional restrictions must be imposed to ensure that the premises can be effectively derived. It may be required, for example, that derivations of the premises are enumerated by some general recursive function (the so-called constructive rule of infinite induction). It is known that formal arithmetic (cf. [[Arithmetic, formal|Arithmetic, formal]]), completed by the constructive rule of infinite induction, is complete with respect to classical truth. The rule of infinite induction has also found use in constructing semantics of constructive mathematics by the method of stepwise semantic systems.
+
The use of the rule of infinite induction in deriving formulas usually renders the problem of existence of a derivation undecidable. An axiomatic system containing an $\omega$-rule is called a semi-formal theory (semi-formal axiomatic system). They play an important role in [[Proof theory|proof theory]]. In order to render the concept of a derivation in the theory effective, additional restrictions must be imposed to ensure that the premises can be effectively derived. It may be required, for example, that derivations of the premises are enumerated by some general recursive function (the so-called constructive rule of infinite induction). It is known that formal arithmetic (cf. [[Arithmetic, formal|Arithmetic, formal]]), completed by the constructive rule of infinite induction, is complete with respect to classical truth. The rule of infinite induction has also found use in constructing semantics of constructive mathematics by the method of stepwise semantic systems.
  
  
  
 
====Comments====
 
====Comments====
Still another term for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050870/i0508708.png" />-rule is rule of complete induction.
+
Still another term for the $\omega$-rule is rule of complete induction.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Barwise,  "Infinitary logics"  E. Agazzi (ed.) , ''Modern logic—a survey'' , Reidel  (1981)  pp. 93–112</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Barwise,  "Infinitary logics"  E. Agazzi (ed.) , ''Modern logic—a survey'' , Reidel  (1981)  pp. 93–112</TD></TR></table>

Revision as of 12:46, 16 July 2014

Carnap's rule, $\omega$-rule

A non-elementary derivation rule with an infinite number of premises. More exactly, let the variable $x$ in some logico-mathematical language be regarded as ranging over the natural numbers, and let $\phi(x)$ be a formula of this language. If each formula in the infinite list

$$\phi(0),\phi(1),\ldots,\phi(n),\ldots,$$

can be derived, the rule of infinite induction permits to conclude that the formula $\forall x\phi(x)$ is derivable as well.

The use of the rule of infinite induction in deriving formulas usually renders the problem of existence of a derivation undecidable. An axiomatic system containing an $\omega$-rule is called a semi-formal theory (semi-formal axiomatic system). They play an important role in proof theory. In order to render the concept of a derivation in the theory effective, additional restrictions must be imposed to ensure that the premises can be effectively derived. It may be required, for example, that derivations of the premises are enumerated by some general recursive function (the so-called constructive rule of infinite induction). It is known that formal arithmetic (cf. Arithmetic, formal), completed by the constructive rule of infinite induction, is complete with respect to classical truth. The rule of infinite induction has also found use in constructing semantics of constructive mathematics by the method of stepwise semantic systems.


Comments

Still another term for the $\omega$-rule is rule of complete induction.

References

[a1] J. Barwise, "Infinitary logics" E. Agazzi (ed.) , Modern logic—a survey , Reidel (1981) pp. 93–112
How to Cite This Entry:
Infinite induction. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Infinite_induction&oldid=32451
This article was adapted from an original article by A.G. Dragalin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article