Les algorithmes permettent-ils de fabriquer automatiquement des théorèmes ?

[Médiat]

ne pas préciser que le 0 de N n'est pas celui du langage est une façon d'introduire de la confusion.

Cette confusion était volontaire à but didactique, dans la pratique, il n'y a jamais de confusion.


On peut très bien définir la théorie des groupes sur le langage et dire que est un groupe où
-----

[Liet Kynes]

Vous parlez du modèle IN ou de la théorie ? Je comprends que vous parlez de IN, mais c'est le 0 du langage qui n'est jamais successeur (donc son interprétation), si on interprète le 0 du langage par le 2 (qui n'est pas un élément du langage) de IN, le 0 de IN sera forcément successeur de quelque chose

Oui je pensai au 0 de IN et effectivement ensuite j'ai pensé à des suites pour lesquelles le 0 n'apparait jamais, par exemple x^x , je reste fragile en terme de compréhension, j'espère que j'entrevoie la manière subtile de placer son esprit.

[Médiat]

Pourquoi voulez-vous que la suite s'exprime par une formule simple ? La suite (5, 0, 1, 2, 3, 4, 6, 7, 8, ...) permet de construire facilement un modèle de la théorie H2G2 (j'ai décidé de l'appeler ainsi, puisqu'elle est apparue au message 42)

[Médiat]

On peut très bien définir la théorie des groupes sur le langage et dire que est un groupe où

J'ai écrit trop vite, j'aurais dû écrire

On peut très bien définir la théorie des groupes sur le langage et dire que est un groupe où ou encore où est la fonction d'interprétation du langage dans

[stefjm]

Pourquoi voulez-vous que la suite s'exprime par une formule simple ? La suite (5, 0, 1, 2, 3, 4, 6, 7, 8, ...) permet de construire facilement un modèle de la théorie H2G2 (j'ai décidé de l'appeler ainsi, puisqu'elle est apparue au message 42)

Faut l'envoyer à Sloane
https://oeis.org/search?q=5%2C+0%2C+1%2C+2%2C+3 %2C+4%2C+6%2C+7%2C+8&language= french&go=Chercher

Nous le regrettons mais votre suite n'est pas dans la table.

Si votre suite est d'intérêt général, envoyez-la moi, s'il vous plaît et je l'ajouterai (probablement) ! Merci !

[Médiat]

Faut l'envoyer à Sloane

J'en ai envoyé de plus intéressantes qui ont été acceptées

[Liet Kynes]

Je manque de "bonnes" définitions à mon avis = toujours le même problème.

[Amanuensis]

Prenons un exemple simple Le langage est (0, s) où 0 est un symbole de constantes, et s une fonction appelé successeur, et 3 axiomes (ceux de Peano)

Une variante de l'exemple "didactique", qui résout la question de la notation du zéro

Prenons comme ensemble de base IN = {premier, deuxième, troisième, quatrième, cinquième, ...}, combien de façon de définir la fonction successeur ?

Ou encore, IN = {rez-de-chaussée, premier, deuxième, troisième, quatrième, cinquième, ...}

Ou encore (en relation avec une remarque faite plus tôt dans le fil), IN = {rien, unique, deux, trois, quatre, cinq, ...}

[Amanuensis]

Si je note s' la fonction incrémentation de N, est-ce que ce qui suit (description informelle mais j'espère suffisante) est une implémentation du modèle ?

Le 0 du modèle est représenté par le nombre 0

s(0) = 3

s représenté par s' pour les nombres à partir de 3

s(1) = 2, s(2)=1

Il me semble que oui. Cela augmente (sans la changer) la "quantité" de possibilités.

Si oui, quel axiome rajouter pour restreindre à ce que j'appellerais le "graphe des entiers naturels" ?

[Amanuensis]

PS: Je vois bien une possibilité avec une famille infinie d'axiomes, mais je n'en vois pas avec un seul axiome ???

[Médiat]

Bonjour,

Je reviens sur ce point que j'avais laissé passer :

Et Gödel a montré que dès que la théorie est assez complexe (si elle inclut l'arithmétique par exemple) alors il y a des propositions qui ne peuvent être démontrées.

Ou pour le dire autrement : la machine va égrainer indéfiniment des théorèmes mais il en manquera toujours certains.

Inutile d'en appeler à Gödel pour en arriver à la même conclusion : Si on prend comme théorie, l'arithmétique de Presburger (Comme Peano sans la multiplication), non seulement cette théorie n'est pas soumise aux théorèmes d'incomplétude, mais en plus elle est complète (il n'y a pas de formule indécidable), et pourtant "la machine va égrainer indéfiniment des théorèmes mais il en manquera toujours certains.", par exemple, elle ne finira jamais la liste de théorèmes :
0+1=1
1+1=2
2+1=3
...

ni la liste de théorèmes
(0+1=0)
(0+1=2)
(0+1=3)
...

etc.

[Amanuensis]

PPS : Avec la famille infinie d'axiomes à laquelle je pense on se trouve face à un cas assez absurde (mon opinion) d'un modèle se présentant comme un ensemble d'axiomes qui est une implémentation de lui-même !

[Médiat]

Une variante de l'exemple "didactique", qui résout la question de la notation du zéro

Pourquoi pas, mais je rappelle que dans la pratique le problème ne se pose jamais.

De plus votre solution risque de devenir très très lourde (si elle est possible) avec le modèle ayant comme ensemble de base (union disjointe)

Il y a quand même différents

[Médiat]

PPS : Avec la famille infinie d'axiomes à laquelle je pense on se trouve face à un cas assez absurde (mon opinion) d'un modèle se présentant comme un ensemble d'axiomes qui est une implémentation de lui-même !

Je suis obligé de quitter mon ordinateur, je vous répondrai plus tard, mais je peux dire rapidement dire que votre proposition ressemble à celle que j'ai proposée au message #63, et que j'ai bien pris en compte cette possibilité dans mon calcul du nombre de possibilités

[Amanuensis]

que votre proposition ressemble à celle que j'ai proposée au message #63

Il me semble que ce n'est pas le cas. Mais je n'y connais pas grand chose, vous avez raison, nécessairement. Désolée de ce plagiat, je pensais sincèrement, en toute bonne volonté, amener du nouveau (dans cette discussion).

Peut-être aussi la numérotation des messages est-elle ambigüe ? Selon mon affichage, le message #63 dit

Pourquoi voulez-vous que la suite s'exprime par une formule simple ? La suite (5, 0, 1, 2, 3, 4, 6, 7, 8, ...) permet de construire facilement un modèle de la théorie H2G2 (j'ai décidé de l'appeler ainsi, puisqu'elle est apparue au message 42)

[andretou]

0 est il un axiome, pour toi ?

"0" n'est pas un axiome, c'est un nombre. En revanche, la proposition "0 est un entier naturel" est un axiome.

[andretou]

Pour lever les malentendus éventuels, j'aimerais avoir votre avis sur la question suivante :
- l'ensemble des entiers naturels se déduit-il directement des axiomes de Peano ?
- ou bien l'ensemble des entiers naturels fait-il implicitement partie, comme l'addition, de la logique sous-jacente aux axiomes de Peano ?

[Deedee81]

Salut,

Toute petite retouche (sinon c'est correct) :

"0" n'est pas un axiome, c'est un nombre

non, à ce stade ce n'est pas un nombre, c'est juste un symbole.

[gg0]

On est revenu loin dans la discussion !!

Je disais :

Ta phrase "L'addition n'est donc pas un axiome" est assez bizarre, cette erreur de catégorie amène à se demander si tu comprends bien ce qu'est un axiome. 0 est il un axiome, pour toi ?

Et la réponse est venue deux jours après. Et montre que Andretou ne pose pas vraiment la question de l'axiomatisation des entiers, mais qu'il suppose l'existence des entiers, avec une opération l'addition, et la possibilité de les obtenir tous à partir des entiers 0 et 1 et de l'addition.
Dans le modèle des entiers intuitifs (*), ceux qui servent à compter, il me semble que la réponse est oui (les entiers sont justement ceux qu'on obtient par un nombre fini d'addition de 1 à partir de 0). Mais Médiat pourra confirmer que ce n'est pas le cas dans des modèles non standards, comme celui qu'il propose au message #73.

Cordialement.

(*) est-ce aussi le modèle "ensemble des ordinaux finis". J'aurais tendance à dire oui, mais je ne connais pas assez la logique pour en être vraiment sûr.

[Deedee81]

Andretou ne pose pas vraiment la question de l'axiomatisation des entiers, mais qu'il suppose l'existence des entiers, avec une opération l'addition, et la possibilité de les obtenir tous à partir des entiers 0 et 1 et de l'addition.

Ah bien vu. C'est une confusion que j'avais déjà vu d'ailleurs (je ne sais plus avec qui mais ce n'était pas Andretou). C'est probablement là que ça coinçait.

[Amanuensis]

- l'ensemble des entiers naturels se déduit-il directement des axiomes de Peano ?

C'était le but de Peano, non ? La question pourrait être comprise comme demandant si Peano a réussi ! Il me semble que l'histoire répond oui.

- ou bien l'ensemble des entiers naturels fait-il implicitement partie, comme l'addition, de la logique sous-jacente aux axiomes de Peano ?

Là encore, le but était bien d'éviter cela.

---

Maintenant, comme mentionné plus tôt, il y a la question de la nature humaine. Peano et tous ses lecteurs sont des humains, ce qui permet de poser la question d'un biais commun, et donc quelque chose qui échappe à tout le monde.

Du haut de mon incompétence, je ne pense pas qu'il y ait un tel problème avec les axiomes de Peano, mais il me semble que certains axiomes de la théorie des ensembles ont été longs à "dépasser" le "bon sens", ce qui vient de la nature humaine. Il a fallu des esprits très pointu pour aller chercher et trouver les "loups" (ainsi que des conséquences "heurtant le bon sens", comme Löwenstein-Skolem, déjà cité).

[Maintenant, ma question sur les familles infinies d'axiomes, définis récursivement, soulève un point qui m'intrique, peut-être pertinent pour la question en citation.]

[Médiat]

Si je note s' la fonction incrémentation de N

Si vous vous placez dans le modèle, vous pouvez aussi utiliser "+1"

Le 0 du modèle est représenté par le nombre 0

Vous voulez dire que le 0 de la théorie est interprété comme le 0 de IN ?

s(0) = 3

s représenté par s' pour les nombres à partir de 3

s(1) = 2, s(2)=1

Effectivement ce n'est pas ce que je proposais au message 63.

Au message 73, j'ai proposé un modèle "non-standard", je ne l'ai pas mis "complet" pour ne pas alourdir, je vous la mets ici : où et les sont des cardinaux (dénombrables si on veut utiliser IN comme ensemble sous-jacent.

Votre exemple est isomorphe à

Si oui, quel axiome rajouter pour restreindre à ce que j'appellerais le "graphe des entiers naturels" ?

Pour éviter les boucles, il faudrait ajouter le schéma d'axiomes

[Médiat]

Peut-être aussi la numérotation des messages est-elle ambigüe ? Selon mon affichage, le message #63 dit

C'est bien le bon message, voulant dire s(5) =0, s(0)=1, s(1) = 2 etc.

[Médiat]

- l'ensemble des entiers naturels se déduit-il directement des axiomes de Peano ?

Non, au mieux on peut dire les entiers naturels sont un modèle de Peano

- ou bien l'ensemble des entiers naturels fait-il implicitement partie, comme l'addition, de la logique sous-jacente aux axiomes de Peano ?

Non, l'ensemble des entiers ni l'addition ne font partie de la logique

[Médiat]

Dans le modèle des entiers intuitifs (*), ceux qui servent à compter, il me semble que la réponse est oui (les entiers sont justement ceux qu'on obtient par un nombre fini d'addition de 1 à partir de 0).

Surtout, les entiers intuitifs ne sont pas des objets mathématiques au sens où je ne peux pas les manipuler avec les outils mathématiques (on arriverait à écrire de grosses c... sinon), même chose avec les ensembles intuitifs

Mais Médiat pourra confirmer que ce n'est pas le cas dans des modèles non standards, comme celui qu'il propose au message #73.

Effectivement dans les modèles non standard, tous les éléments ne sont pas de la forme (voilà un exemple ou l'entier intuitif n'est pas un objet mathématique)

(*) est-ce aussi le modèle "ensemble des ordinaux finis". J'aurais tendance à dire oui, mais je ne connais pas assez la logique pour en être vraiment sûr.

Non, l'ensemble des cardinaux fini, généralement noté ou est bien un objet mathématique à part entière

[Médiat]

C'était le but de Peano, non ? La question pourrait être comprise comme demandant si Peano a réussi ! Il me semble que l'histoire répond oui.

Sujet à débat : tous les modèles dénombrables de Peano ne sont pas isomorphe à IN. Ce résultat peut se démontrer avec une notion "minimale" de l'arithmétique

il me semble que certains axiomes de la théorie des ensembles ont été longs à "dépasser" le "bon sens", ce qui vient de la nature humaine.

Oui, l'axiome du choix, ou ce que j'ai appelé "les errements créatifs" de Woodin (à propos de HC)

[Maintenant, ma question sur les familles infinies d'axiomes, définis récursivement, soulève un point qui m'intrique, peut-être pertinent pour la question en citation.]

Je n'ai pas compris qu'il y avait une question générale sur ce sujet, vous pourriez préciser ...

[andretou]

Non, au mieux on peut dire les entiers naturels sont un modèle de Peano

Pourriez-vous SVP préciser ? Quelle est l'origine et la nature de ce modèle ?

[Médiat]

Vous avez le choix :

1. L'ensemble des entiers naturels est l'objet initial (unique à isomorphisme près) de la catégorie des diagrammes de Lawvere().
2. Le monoïde libre à un générateur (ensemble des "mots" de longueur finie constitués à partir d’un alphabet ne contenant qu’une seule lettre auxquels on adjoint le mot vide) l’addition est simplement la concaténation des mots, pour la multiplication, on remplace chaque lettre du premier mot par le deuxième mot.
3. L’ensemble des mots de longueur finie sur l’alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ne commençant pas par 0, plus le mot 0, pour définir l’addition et la multiplication ... il suffit de retourner en cours préparatoire.
4. Dans le cadre de la théorie des ensembles (ZF supposé Consistante) (le plus petit ordinal limite), avec les opérations habituelles.
5. Le segment initial infini commun (à isomorphisme près) à tous les modèles de l’arithmétique de Peano supposé Consistante.

[andretou]

Chacune de ces 5 options implique-t-elle l'existence de la relation d'ordre qui caractérise l'ensemble des entiers naturels ?

[Médiat]

La relation d'ordre est définissable à l'aide de l'addition