Arithmétique vraie

En logique mathématique, l'arithmétique vraie est l'ensemble de toutes les propositions vraies sur l'arithmétique des entiers naturels (Boolos, Burgess et Jeffrey 2002: 295). C'est la théorie associée au modèle standard des axiomes de Peano dans la signature des axiomes de Peano du premier ordre. L'arithmétique vraie est parfois appeléeModèle:Par qui arithmétique de SkolemModèle:Référence nécessaire, bien que ce terme se réfère habituellement à une théorie différente, la théorie des entiers naturels avec multiplication.

Définition

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 $𝒩$ est défini comme un modèle d'arithmétique Peano comme suit.

• L'univers du discours $\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 $\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 $\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 $𝒩$ si elle vrai dans la structure juste définie. La notation $𝒩\models \phi$ signifie que la proposition φ est vraie dans $𝒩.$

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 $𝒩$, noté Modèle:Nowrap.

Cet ensemble est, de manière équivalente, la théorie de la structure $𝒩$.

Non-déterminabilité de l'arithmétique

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 Modèle:Nowrap n'est pas arithmétiquement définissable. Cela signifie qu'il n'existe pas de formule $\phi (x)$ en arithmétique de premier ordre de sorte que, pour chaque proposition θ dans ce langage,

$𝒩\models \theta$ si et seulement si $𝒩\models \phi (\underset{\_}{\mathrm{\#}(\theta )})$

où $\underset{\_}{\mathrm{\#}(\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 Modèle:Nowrap et le degré de Turing, en utilisant la hiérarchie arithmétique. Pour chaque entier naturel n, on pose Modèle:Nowrap le sous-ensemble de Modèle:Nowrap composé uniquement de propositions qui sont ${\mathrm{\Sigma }}_n^0$ ou plus bas dans la hiérarchie arithmétique. Le théorème de Post montre que, pour chaque n, Modèle:Nowrap est arithmétiquement définissable, mais seulement par une formule de complexité supérieure à ${\mathrm{\Sigma }}_n^0$. Ainsi, aucune formule unique ne peut définir Modèle:Nowrap, car

$\text{Th}(𝒩)=\bigcup _{n\in \mathbb{N}}{\text{Th}}_n(𝒩)$

Mais aucune formule unique ne peut définir Modèle:Nowrap pour n arbitrairement grand.

Théorie vraie de l'arithmétique du second ordre

Modèle:Section à recycler 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 $𝒩$ et dont la partie de second ordre comprend tous les sous-ensembles de $\mathbb{N}$.

La théorie vraie de l'arithmétique du premier ordre, Modèle:Nowrap, est un sous-ensemble de la théorie vraie de l'arithmétique du second ordre, et Modèle:Nowrap 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.

Références

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Article
• 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.