Arithmétique vraie

La signature de l'arithmétique de Peano comprend les symboles de l'addition, de la multiplication et de la fonction successeur, les symboles de l'égalité et de la relation inférieure, et un symbole constant pour 0. Les formules bien-formées de la signature de l'arithmétique de premier ordre sont construites à partir de ces symboles de manière habituelle de la logique du premier ordre.

La structure ${\displaystyle {\mathcal {N}}}$ est défini comme un modèle d'arithmétique Peano comme suit.

• L'univers du discours ${\displaystyle \mathbb {N} }$ est l'ensemble des entiers naturels.
• Le symbole 0 est interprété comme l'entier 0.
• Les symboles de fonction sont interprétés comme les opérations arithmétiques habituelles sur ${\displaystyle \mathbb {N} }$
• L'égalité et les symboles de relation inférieurs aux interprétations sont interprétés comme la relation habituelle d'égalité et d'ordre sur ${\displaystyle \mathbb {N} }$. Cette structure est connue comme le modèle standard ou l'interprétation prévue de l'arithmétique de premier ordre.

Une proposition dans le langage arithmétique de premier ordre est vraie dans ${\displaystyle {\mathcal {N}}}$ si elle vrai dans la structure juste définie. La notation ${\displaystyle {\mathcal {N}}\models \varphi }$ signifie que la proposition φ est vraie dans ${\displaystyle {\mathcal {N}}.}$

L'arithmétique vraie est définie comme étant l'ensemble de toutes les propositions dans le langage de l'arithmétique de premier ordre qui sont vraies dans ${\displaystyle {\mathcal {N}}}$, noté Th(${\displaystyle {\mathcal {N}}}$).

Cet ensemble est, de manière équivalente, la théorie de la structure ${\displaystyle {\mathcal {N}}}$.

Le résultat central sur l'arithmétique vraie est le théorème de non définissabilité d'Alfred Tarski (1936). Celui déclare que l'ensemble Th(${\displaystyle {\mathcal {N}}}$) n'est pas arithmétiquement définissable. Cela signifie qu'il n'existe pas de formule ${\displaystyle \varphi (x)}$ en arithmétique de premier ordre de sorte que, pour chaque proposition θ dans ce langage,

${\displaystyle {\mathcal {N}}\models \theta \qquad }$ si et seulement si ${\displaystyle {\mathcal {N}}\models \varphi ({\underline {\#(\theta )}})}$

où ${\displaystyle {\underline {\#(\theta )}}}$ est le nombre de Gödel de la proposition θ.

Le théorème de Post est une version plus nette du théorème d'indétermination qui montre une relation entre la définition de Th(${\displaystyle {\mathcal {N}}}$) et le degré de Turing, en utilisant la hiérarchie arithmétique. Pour chaque entier naturel n, on pose Th_n(${\displaystyle {\mathcal {N}}}$) le sous-ensemble de Th(${\displaystyle {\mathcal {N}}}$) composé uniquement de propositions qui sont ${\displaystyle \Sigma _{n}^{0}}$ ou plus bas dans la hiérarchie arithmétique. Le théorème de Post montre que, pour chaque n, Th_n(${\displaystyle {\mathcal {N}}}$) est arithmétiquement définissable, mais seulement par une formule de complexité supérieure à ${\displaystyle \Sigma _{n}^{0}}$. Ainsi, aucune formule unique ne peut définir Th(${\displaystyle {\mathcal {N}}}$), car

${\displaystyle {\mbox{Th}}({\mathcal {N}})=\bigcup _{n\in \mathbb {N} }{\mbox{Th}}_{n}({\mathcal {N}})}$

Mais aucune formule unique ne peut définir Th_n(${\displaystyle {\mathcal {N}}}$) pour n arbitrairement grand.

La théorie vraie de l'arithmétique de second ordre se compose de toutes les propositions dans le langage de l'arithmétique du second ordre qui sont satisfaites par le modèle standard de l'arithmétique du second ordre, celle dont la partie de premier ordre est la structure ${\displaystyle {\mathcal {N}}}$ et dont la partie de second ordre comprend tous les sous-ensembles de ${\displaystyle \mathbb {N} }$.

La théorie vraie de l'arithmétique du premier ordre, Th(${\displaystyle {\mathcal {N}}}$), est un sous-ensemble de la théorie vraie de l'arithmétique du second ordre, et Th(${\displaystyle {\mathcal {N}}}$) est définissable dans l'arithmétique du second ordre. Cependant, la généralisation du théorème de Post à la hiérarchie analytique montre que la théorie vraie de l'arithmétique du second ordre n'est pas définissable par une seule formule de l'arithmétique du second ordre.

Simpson (1977) a montré que la théorie vraie de l'arithmétique du second ordre est interprétée de façon comparable à la théorie de l'ordre partiel de tous les degrés de Turing, dans la signature d'ordres partiels, et vice versa.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « True arithmetic » (voir la liste des auteurs).
• George Boolos, John P. Burgess et Richard C. Jeffrey, Computability and logic, Cambridge University Press, 2002, 4th éd., 356 p. (ISBN 978-0-521-00758-0).
• Andrey Bovykin et Richard Kaye, Logic and algebra, vol. 302, American Mathematical Society, coll. « Contemporary Mathematics », 2001, 275–285 p., « On order-types of models of arithmetic ».
• Richard Shore, Handbook of Computability Theory, vol. 140, North-Holland, coll. « Studies in Logic and the Foundations of Mathematics », 1999, 169–197 p., « The recursively enumerable degrees ».
• Stephen G. Simpson, First-order theory of the degrees of recursive unsolvability, vol. 105, Annals of Mathematics, 1977, 121–139 p. (ISSN 0003-486X, DOI 10.2307/1971028, JSTOR 1971028, MR 0432435)
• Tarski, Alfred (1936), "Der Wahrheitsbegriff in den formalisierten Sprachen". An English translation "The Concept of Truth in Formalized Languages" appears in Corcoran, J., (ed.), Logic, Semantics and Metamathematics, 1983.