Namespaces
Variants
Actions

Difference between revisions of "Carnap rule"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
''rule of infinite induction, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020480/c0204802.png" />-rule''
+
{{TEX|done}}
 +
''rule of infinite induction, $\omega$-rule''
  
A [[Derivation rule|derivation rule]] stating that if for an arithmetic formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020480/c0204803.png" /> the propositions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020480/c0204804.png" /> have been proved, then the proposition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020480/c0204805.png" /> can be regarded as being proved. This rule was first brought into consideration by R. Carnap [[#References|[1]]]. Carnap's rule uses an infinite set of premises and is therefore inadmissible within the structure of the formal theories of D. Hilbert. The concept of a derivation in a system with the Carnap rule is undecidable. In mathematical logic one uses, for the study of formal arithmetic, the constructive Carnap rule: If there is an algorithm which for a natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020480/c0204806.png" /> provides a derivation of the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020480/c0204807.png" />, then the proposition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020480/c0204808.png" /> can be regarded as being proved (the restricted <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020480/c02048010.png" />-rule, the rule of constructive infinite induction). Classical arithmetic calculus, which by Gödel's theorem is incomplete, becomes complete on adding the constructive Carnap rule (see [[#References|[2]]], [[#References|[3]]]).
+
A [[Derivation rule|derivation rule]] stating that if for an arithmetic formula $\phi(x)$ the propositions $\phi(0),\phi(1),\ldots,$ have been proved, then the proposition $\forall x\phi(x)$ can be regarded as being proved. This rule was first brought into consideration by R. Carnap [[#References|[1]]]. Carnap's rule uses an infinite set of premises and is therefore inadmissible within the structure of the formal theories of D. Hilbert. The concept of a derivation in a system with the Carnap rule is undecidable. In mathematical logic one uses, for the study of formal arithmetic, the constructive Carnap rule: If there is an algorithm which for a natural number $n$ provides a derivation of the formula $\phi(n)$, then the proposition $\forall x\phi(x)$ can be regarded as being proved (the restricted $\omega$-rule, the rule of constructive infinite induction). Classical arithmetic calculus, which by Gödel's theorem is incomplete, becomes complete on adding the constructive Carnap rule (see [[#References|[2]]], [[#References|[3]]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Carnap,  "The logical syntax of language" , Kegan Paul, Trench &amp; Truber  (1937)  (Translated from German)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.V. Kuznetsov,  ''Uspekhi Mat. Nauk'' , '''12''' :  4  (1957)  pp. 218–219</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  J.R. Shoenfield,  "On a restricted <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020480/c02048011.png" />-rule"  ''Bull. Acad. Polon. Sci. Cl. III'' , '''7'''  (1959)  pp. 405–407</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Carnap,  "The logical syntax of language" , Kegan Paul, Trench &amp; Truber  (1937)  (Translated from German)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.V. Kuznetsov,  ''Uspekhi Mat. Nauk'' , '''12''' :  4  (1957)  pp. 218–219</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  J.R. Shoenfield,  "On a restricted <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020480/c02048011.png" />-rule"  ''Bull. Acad. Polon. Sci. Cl. III'' , '''7'''  (1959)  pp. 405–407</TD></TR></table>

Revision as of 14:45, 1 May 2014

rule of infinite induction, $\omega$-rule

A derivation rule stating that if for an arithmetic formula $\phi(x)$ the propositions $\phi(0),\phi(1),\ldots,$ have been proved, then the proposition $\forall x\phi(x)$ can be regarded as being proved. This rule was first brought into consideration by R. Carnap [1]. Carnap's rule uses an infinite set of premises and is therefore inadmissible within the structure of the formal theories of D. Hilbert. The concept of a derivation in a system with the Carnap rule is undecidable. In mathematical logic one uses, for the study of formal arithmetic, the constructive Carnap rule: If there is an algorithm which for a natural number $n$ provides a derivation of the formula $\phi(n)$, then the proposition $\forall x\phi(x)$ can be regarded as being proved (the restricted $\omega$-rule, the rule of constructive infinite induction). Classical arithmetic calculus, which by Gödel's theorem is incomplete, becomes complete on adding the constructive Carnap rule (see [2], [3]).

References

[1] R. Carnap, "The logical syntax of language" , Kegan Paul, Trench & Truber (1937) (Translated from German)
[2] A.V. Kuznetsov, Uspekhi Mat. Nauk , 12 : 4 (1957) pp. 218–219
[3] J.R. Shoenfield, "On a restricted -rule" Bull. Acad. Polon. Sci. Cl. III , 7 (1959) pp. 405–407
How to Cite This Entry:
Carnap rule. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Carnap_rule&oldid=12356
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article