Namespaces
Variants
Actions

Difference between revisions of "Omega-consistency"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
''<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o0681602.png" />-consistency''
+
{{TEX|done}}
 +
''$\omega$-consistency''
  
The property of formal systems of arithmetic signifying the impossibility of obtaining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o0681603.png" />-inconsistency. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o0681605.png" />-inconsistency is a situation in which, for some formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o0681606.png" />, each formula of the infinite sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o0681607.png" /> and the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o0681608.png" /> are provable, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o0681609.png" /> is a constant of the formal system signifying the number 0, while the constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o06816010.png" /> are defined recursively in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o06816011.png" />, signifying the number following directly after <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o06816012.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o06816013.png" />.
+
The property of formal systems of arithmetic signifying the impossibility of obtaining $\omega$-inconsistency. $\omega$-inconsistency is a situation in which, for some formula $A(x)$, each formula of the infinite sequence $A(\bar0),\ldots,A(\bar n),\ldots,$ and the formula $\neg\forall xA(x)$ are provable, where $\bar 0$ is a constant of the formal system signifying the number 0, while the constants $\bar n$ are defined recursively in terms of $(x)'$, signifying the number following directly after $x$: $\overline{n+1}=(\bar n)'$.
  
The concept of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o06816014.png" />-consistency appeared in conjunction with the [[Gödel incompleteness theorem|Gödel incompleteness theorem]] of arithmetic. Assuming the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o06816015.png" />-consistency of formal arithmetic, K. Gödel proved its incompleteness. The property of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o06816016.png" />-consistency is stronger than the property of simple [[Consistency|consistency]]. Simple consistency occurs if a formula not involving <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o06816017.png" /> is taken as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o06816018.png" />. It follows from Gödel's incompleteness theorem that there exist systems which are consistent but also <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068160/o06816019.png" />-inconsistent.
+
The concept of $\omega$-consistency appeared in conjunction with the [[Gödel incompleteness theorem|Gödel incompleteness theorem]] of arithmetic. Assuming the $\omega$-consistency of formal arithmetic, K. Gödel proved its incompleteness. The property of $\omega$-consistency is stronger than the property of simple [[Consistency|consistency]]. Simple consistency occurs if a formula not involving $x$ is taken as $A(x)$. It follows from Gödel's incompleteness theorem that there exist systems which are consistent but also $\omega$-inconsistent.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.C. Kleene,  "Introduction to metamathematics" , North-Holland  (1951)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.C. Kleene,  "Introduction to metamathematics" , North-Holland  (1951)</TD></TR></table>

Revision as of 12:19, 12 April 2014

$\omega$-consistency

The property of formal systems of arithmetic signifying the impossibility of obtaining $\omega$-inconsistency. $\omega$-inconsistency is a situation in which, for some formula $A(x)$, each formula of the infinite sequence $A(\bar0),\ldots,A(\bar n),\ldots,$ and the formula $\neg\forall xA(x)$ are provable, where $\bar 0$ is a constant of the formal system signifying the number 0, while the constants $\bar n$ are defined recursively in terms of $(x)'$, signifying the number following directly after $x$: $\overline{n+1}=(\bar n)'$.

The concept of $\omega$-consistency appeared in conjunction with the Gödel incompleteness theorem of arithmetic. Assuming the $\omega$-consistency of formal arithmetic, K. Gödel proved its incompleteness. The property of $\omega$-consistency is stronger than the property of simple consistency. Simple consistency occurs if a formula not involving $x$ is taken as $A(x)$. It follows from Gödel's incompleteness theorem that there exist systems which are consistent but also $\omega$-inconsistent.

References

[1] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
How to Cite This Entry:
Omega-consistency. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Omega-consistency&oldid=31621
This article was adapted from an original article by V.N. Grishin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article