Prédicats récursifs primitifs pour l'exponentiation et la multiplication

Aug 19 2020

J'ai les croyances suivantes, exprimées de manière informelle et faiblement ancrées, dont certaines me semblent incohérentes après réflexion. Je me demande où la source de l'erreur (s) dans ma pensée pourrait être; des erreurs dans les définitions de base sont une possibilité certaine.

  1. Il est impossible de faire l'élimination des quantificateurs dans la théorie du premier ordre des entiers avec addition et multiplication. (Ceci est, pour autant que je sache, une version légèrement plus forte du premier théorème d'incomplétude.)

  2. Dans la théorie du premier ordre des entiers avec addition et multiplication, il est possible de définir un prédicat récursif primitif pour l'exponentiation. (Par un prédicat d'exponentiation, je veux juste dire quelque chose qui se comporte comme "$Fabc\text{ just when }a^b = c.$")

  3. Il est possible de faire l'élimination des quantificateurs dans la théorie du premier ordre des entiers avec deux opérations$a \oplus b = \min(a, b)$et$a \otimes b = a + b$(c'est-à-dire l'addition ordinaire d'entiers). Je suis conscient que nous avons également besoin de prédicats de divisibilité et d'opérateurs de multiplication pour que les nombres premiers effectuent réellement l'élimination des quantificateurs.

  4. Dans la théorie du premier ordre des entiers avec les opérations$\oplus$et$\otimes$, il est possible de définir un prédicat récursif primitif pour la multiplication (presque exactement de la même manière que le prédicat pour l'exponentiation ci-dessus).


En gros, il semble qu'il y ait une rupture dans l'analogie entre la "tour d'opérations ordinaire"$(+, \times, \hat{\phantom{n}}, \cdots)$et la "tour tropicale des opérations"$(\min, +, \times, \cdots)$.

Plus précisément, si (4) et (3) sont vrais, je ne comprends pas pourquoi on ne peut pas simplement utiliser librement le prédicat de multiplication et ensuite avoir une situation où nous pouvons tous les deux faire l'élimination du quantificateur (via (3)) et ne pas faire élimination du quantificateur (via (1)). Cela m'étonnerait beaucoup si (2) était vrai mais (4) ne l'était pas, et cela m'étonnerait encore plus si (2) était faux.

Je soupçonne que je ne comprends pas très bien ce que l'on entend par un prédicat d'exponentiation (c'est-à-dire ma définition informelle de$Fabc$est incorrect, ou bien il y a plus de détails concernant "l'utilisation libre du prédicat de multiplication" dont je ne suis pas au courant.

Réponses

4 NoahSchweber Aug 19 2020 at 05:54

Vos réclamations$(1), (2)$, et$(3)$sont chacun corrects. Prétendre$(4)$, cependant, est incorrect ; en effet, si la multiplication était définissable sur$(\mathbb{N};\max,+)$puis la théorie$Th(\mathbb{N};\max,+)$serait aussi compliqué que$Th(\mathbb{N};+,\times)$. Mais le premier est récursif tandis que le second n'est même pas définissable arithmétiquement.

Le problème est que la définition "évidente" de la multiplication en termes d'addition n'est pas réellement du premier ordre : les définitions récursives ne sont pas a priori quelque chose que la logique du premier ordre peut faire. Dans des structures suffisamment riches, nous pouvons trouver des moyens d'effectuer des définitions récursives d'une manière de premier ordre, et en effet c'est la richesse de$Th(\mathbb{N};+,\times)$en ce sens, ce qui rend possible l'éorème de Godel, mais l'addition seule n'est pas assez puissante pour que cela fonctionne. La clé est que si nous avons à la fois l'addition et la multiplication, nous pouvons "coder" des séquences finies de naturels par des naturels individuels (par exemple via le$\beta$fonction ) et donc parler de constructions récursives en parlant des séquences codant leurs "comportements pas à pas", mais avec l'addition seule, nous ne pouvons même pas coder des paires de nombres par des nombres individuels .

Élaborer sur cette dernière phrase et revenir à votre demande$(2)$, voici un aperçu de la façon de définir l'exponentiation en utilisant l'addition et la multiplication au premier ordre :

Nous avons$a^b=c$ssi il y a un certain nombre qui, lorsqu'il est interprété comme une séquence, a une longueur est$b$, premier mandat$a$, dernier terme$c$, et$i+1$ème terme égal à$a$fois le$i$ème terme.

Notez qu'il s'agit d'une définition "tout à la fois" plutôt que d'une définition par un "processus récursif :" modulo les détails du codage de séquences finies par des nombres, cela implique simplement de quantifier sur des nombres individuels et de vérifier les propriétés de base, ce qui est exactement ce qui premier- la logique de commande peut faire. Sans la possibilité de coder des séquences finies sous forme de nombres individuels au premier ordre - ce qui$(\mathbb{N};\max,+)$manque - nous serions coincés avec la définition habituelle de non-premier ordre.

  • Soit dit en passant, il est important qu'il s'agisse d'une "définition vérifiable :" dans la théorie$\mathsf{Q}$, qui est un petit fragment de la théorie complète$Th(\mathbb{N};+,\times)$, on a ça pour chaque$a,b,c$la phrase abrégée par$$\underline{a}^{\underline{b}}=\underline{c}$$(où$\underline{k}$est le chiffre représentant l'entier naturel$k$) est démontrable dans$\mathsf{Q}$si$a^b=c$et est réfutable dans$\mathsf{Q}$si$a^b\not=c$. C'est ce qu'on appelle la représentabilité , et c'est l'une des idées clés de la preuve de Godel ; en fait, toute fonction récursive est représentable .