axiomatique "ultra-finitaire"

maillotjaune

Bonjour,

Une question aux sages du forum bien calés en logique: existe-t-il une axiomatique complètement finie qui permette de parler de nombres entiers jusqu'à une borne arbitraire (disons les entiers jusqu'à $10^{100}$) ?

C'est à dire que je ne voudrais ni d'axiome de l'infini, ni de schémas d'axiomes, vraiment juste un nombre fini de règles et de symboles, quelque chose d'assez proche d'un vrai ordinateur de bureau en quelque sorte. En connaissez-vous ?

Merci !

mpif0

Bonjour,

Pour votre cas précis, on a qu'a prendre comme axiomatique les tables d'addition et de multiplication dans $\mathbb{Z}/10^{100}\mathbb{Z}$. Il n'y a qu'un nombre fini d'axiomes : $2\times 10^{200}$. C'est très proche de ce qu'il y a pour les ordinateurs...

christophe c

Ta question n'a pas beaucoup de "fondement" car même un nombre fini d'axiomes utilisent en filigrane un nombre infini de règles diverses (infinité de variables, infinité d'axiomes logiques (qui sont des schémas d'axiomes), etc)

Il y a une façon vicieuse de mettre de l'infini sans le dire.

On remplace $\forall x\exists y: y=successeur(x)$ par exemple par une petite conjonction d'axiome qui disent que le "dernier" entier s'écrit à la fois en base 2 de la manière "1111111...111" (1) et aussi en base 3 de la manière "22222222222.....222" (2)

C'est faisable.

On garde le schéma de récurrence, et (1) seul avec le reste est consistant**, de même pour (2) seul**, mais (1)+(2) + le reste est aussi fort que Peano tout entier.

** en fait c'est une théorie qui gère des ensembles bases $\{0;1;2;.........;n\}$ et qui a des modèles.

J'avais essayé ça pour "prouver" consPeano (et donc nonconsPeano lol) dans Peano, car intuitivement, l'idée "du manque de place" lié à "tout entier a un successeur" n'était à priori plus présente (en effet, dès qu'on a de la place pour écrire des digits, le fait de mettre que des "2", pour l'écriture en base 3, par exemple, ne nécessite pas de gratter dans l'espace intersidéral un peu plus de place). Je me disais donc qu'en mariant les 2...

Les "modulos" sont plus savonneux et contre-intuitif, car ça donne à 0 un prédecesseur (on revient à 0 après la fin) et la gestion logique est moins intuitive.

maillotjaune

cela semble naturel en effet (quitte peut-être à adopter une notation qui fasse bien comprendre que l'on ne parle pas d'ensembles), merci pour votre réponse.

maillotjaune

Merci à christophe dont je n'avais pas vu la réponse (justement mon but était de savoir si on pouvait avoir des axiomes sans aucune forme d'infini caché).

christophe c

(justement mon but était de savoir si on pouvait avoir des axiomes sans aucune forme d'infini caché).

Hélas, "non", l'absence d'infini ne sera que sémantique.

Un exemple: tu prends la logique affine par exemple (c'est une logique où quand on se sert 42 fois d'une même hypothèse, on la fait 42 fois). Je crois qu'elle est P, ou coNPcomplete.

Avec une astuce du genre B=A et A
C=B et B
D= C et C

etc, rajoutés en guise d'axiomes

on pourrait avoir l'illusion de récupérer à cout logarithmique la logique classique et donc de prouver NP=coNP voire même NP=P.

Mais en fait, on est tellement habitué à "recopier" les choses qu'on ne s'aperçoit pas qu'on le fait au nom d'un schéma infini, qu'on admet.

Quand on utilise F=E et E (par avec une copie de F avoir 2 copies de E), et économiser en apparence de l'encre, en fait on a besoin de faire DEUX fois l'hypothèse F=E et E et donc on ne gagne rien...

Concrêtement, chaque hypothèse que tu fais, TU LA FAIS, et les maths fonctionnent grace aux schémas d'axiomes qu'on évoque par un simple label (un seul symbole) pour affirmer moult choses différentes (leurs instances)

Sémantiquement, l'élimination des coupures*** entraine que ton espoir a peu de chances d'être satisfait, même si on extrapole ton désir

*** que ce que tu obtiendrais de toute façon, tu l'y aurais mis d'avance, au sens presque propre.