Formulation d'un des axiomes de Peano

[Seirios]

Bonjour à tous,

Sur la page de wikipédia à propos des axiomes de Peano, on peut trouver l'un des axiomes de l'arithmétique de Peano ainsi formulé :

.

Je me demdant s'il ne faudrait pas plutôt le formuler :



Qu'en pensez-vous ?

Phys2
-----

[Médiat]

Bonjour à tous,

Sur la page de wikipédia à propos des axiomes de Peano, on peut trouver l'un des axiomes de l'arithmétique de Peano ainsi formulé :

.

Je me demdant s'il ne faudrait pas plutôt le formuler :



Qu'en pensez-vous ?

Les deux écritures sont correctes (presque :
, serait mieux). Il est d'usage de ramener tous les quantificateurs en début de proposition (il faut être soigneux, car il y a des pièges, mais c'est toujours possible).

C'est ce que l'on appelle la forme prénexe d'une proposition, et c'est ce qui permet de classer les propositions en ou (j'ai parlé de cela dans mon pdf sur l'arithmétique (je viens de vérifier, j'effleure à peine le sujet)).

[POPOUCOSAM]

Bonjour Médiat,

Où pouvons nous consulter ton .pdf sur l' arithmétique, s' il te plaît, merci

[Médiat]

Bonjour,

Où pouvons nous consulter ton .pdf sur l' arithmétique

Là : http://forums.futura-sciences.com/ma...ml#post1980944

Bonne lecture.

[A voir en vidéo sur Futura]

[Seirios]

Je vais également faire un tour du côté de ce pdf. En attendant, j'aurais une question à propos de cette même page de wikipédiat : il est écrit que l'arithmétique de Peano se formule avec le langage , mais pourquoi pas avec le langage , puisque la définition de l'addition et de la multiplication sur les entiers naturels se fait à partir de s ? Dans ce cas, si l'on veut introduire l'ordre usuel sur , faut-il se placer dans le langage ? (je trouverais ça plutôt insatisfaisant)

[Médiat]

il est écrit que l'arithmétique de Peano se formule avec le langage , mais pourquoi pas avec le langage , puisque la définition de l'addition et de la multiplication sur les entiers naturels se fait à partir de s ? Dans ce cas, si l'on veut introduire l'ordre usuel sur , faut-il se placer dans le langage ? (je trouverais ça plutôt insatisfaisant)

Une précision, le langage de l'arithmétique de Peano inclus l'égalité (=), il est vrai que l'on peut se dispenser de la citer si l'on a pas oublier de dire "théorie égalitaire", ou "dans le langage égalitaire ...).

Je suis ravi que vous posiez cette question car la compréhension de la réponse est centrale dans la compréhension de la logique en général et de mon petit pdf en particulier :
L'addition (pour la multiplication je pourrais dire des choses similaires), ses propriétés sont données par des axiomes, qui font intervenir la fonction successeur, mais vous ne pourrez pas trouver une formule à 3 variables libres du langage telle que : .

Vous pouvez définir x + 1, x + 132135432163543165465465465321 35432123 (c'est plus long), mais vous ne pouvez pas définir x + y (il y a quelques mots sur un sujet similaire page 11 du pdf (arithmétique de Robinson)). Il y a même un théorème très fort sur ce sujet : le théorème de Tennenbaum (en bas de la page 17)

A l'opposé, il est facile de définir :
, il n'est donc pas obligatoire (mais cela peut être utile) d'enrichir le langage, puisque nous avons une formule (à mettre sous forme prénexe) qui définit ce dont nous avons besoin.

[Seirios]

Je n'ai pas encore regardé de près les exemples du pdf, parce qu'il y a encore du vocabulaire que je ne connais pas. Mais si j'ai bien compris, on est obligé d'introduire des fonctions supplémentaires dans le langage puisqu'on ne peut pas vraiment définir l'addition et la multiplication à partir de 0 et s. Mais qu'appelle-t-on définir ? Est-ce par une formule à variables libres utilisant uniquement les éléments du langage ? Parce que l'addition se définit très bien récursivement, non ?

[Médiat]

Je n'ai pas encore regardé de près les exemples du pdf, parce qu'il y a encore du vocabulaire que je ne connais pas.

N'hésitez pas à demander, je complèterai le pdf.

Mais si j'ai bien compris, on est obligé d'introduire des fonctions supplémentaires dans le langage puisqu'on ne peut pas vraiment définir l'addition et la multiplication à partir de 0 et s. Mais qu'appelle-t-on définir ? Est-ce par une formule à variables libres utilisant uniquement les éléments du langage ?

Oui, c'est bien cela.

Parce que l'addition se définit très bien récursivement, non ?

Sur quel ensemble ? Parce que, à part sur IN (où la réponse est oui), le théorème de Tennebaum dit exactement le contraire. Et quand on en est au niveau de la théorie, on ne dispose d'aucun ensemble a priori, d'ailleurs cela serait étrange de définir l'addition sur IN, à partir ... de IN (définition d'une fonction récursive)

[Seirios]

Tiens, un nouveau modérateur

Mais si j'ai bien compris, on est obligé d'introduire des fonctions supplémentaires dans le langage puisqu'on ne peut pas vraiment définir l'addition et la multiplication à partir de 0 et s. Mais qu'appelle-t-on définir ? Est-ce par une formule à variables libres utilisant uniquement les éléments du langage ?

Oui, c'est bien cela.

J'ai viens de lire qu'on définissait un langage propositionnel par un ensemble (non-vide) de symboles propositionnels, par les symboles logiques de négation, d'implication, d'équivalence, de disjonction et de conjonction, et par les parenthèses. Donc si j'ai bien compris, on peut supprimer le symbole d'équivalence du langage, puisqu'on peut le définir ainsi : pour tous énoncés A et B, ssi . C'est correct ?

EDIT : Ce n'est pas gênant d'écrire "ssi" sans avoir définie l'équivalence ? (ce que j'ai aussi trouvé dans un document de logique)

[Médiat]

J'ai viens de lire qu'on définissait un langage propositionnel par un ensemble (non-vide) de symboles propositionnels, par les symboles logiques de négation, d'implication, d'équivalence, de disjonction et de conjonction, et par les parenthèses. Donc si j'ai bien compris, on peut supprimer le symbole d'équivalence du langage, puisqu'on peut le définir ainsi : pour tous énoncés A et B, ssi . C'est correct ?

C'est correct ; on se limite généralement à qui permet de générer tous les autres connecteurs, mais on peut en choisir d'autres, il semble que la mode soit ; c'est intéressant de minimiser les éléments du langage, cela simplifie les récurrences sur la complexité d'une formule. Néanmoins, tous les connecteurs peut être générés par la seule barre de Sheffer, alors que je ne l'ai jamais vu utilisée dans les récurrences.

EDIT : Ce n'est pas gênant d'écrire "ssi" sans avoir définie l'équivalence ? (ce que j'ai aussi trouvé dans un document de logique)

Là il s'agit sans doute de langage courant et non de langage formel.

[Seirios]

Je ne comprends pas cette remarque :

c'est intéressant de minimiser les éléments du langage, cela simplifie les récurrences sur la complexité d'une formule.

[Médiat]

Je ne comprends pas cette remarque :

Certaines démonstrations (en général techniques, comme le théorème de Los, le théorème de complétude (1er ordre), et surtout la satisfaisabilité d'une formule dans un modèle) se font (peuvent se faire) par récurrence sur la complexité de la formule, avec comme connecteur (), il faut montrer que si le théorème est "vrai" pour les formules et alors il est "vrai" pour , et pour , s'il y avait 12 connecteurs, il faudrait le faire 12 fois.

L'initialisation de la récurrence se fait sur les formules atomiques.

[Seirios]

D'accord, merci.