Arithmétique

[Médiat]

Bonjour,

quel est niveau requis pour pouvoir comprendre ce document ?

Le but (sournois ) que je poursuis en publiant ce petit document est de faire connaître les questions qui se posent en logique mathématique et démythifier le théorème d'incomplétude de Gödel (sans lui retirer son importance), et tenter d'éviter que ne se répandent ses interprétations folkloriques (voire complètement débiles pour certaines). J'ai donc essayé de faire simple (ce n'est pas toujours facile) et l'ensemble du document ne demande que très peu de connaissances purement mathématiques (à part le théorème des reste chinois et le théorème de Dirichlet, mais qui sont rappelés) ; par contre il faut s'habituer un peu à la méthode des logiciens.
Les sections 0 et 1 ne demandent vraiment pas de connaissance préalables. La section 2 est un peu plus compliquée à cause de l'introduction de la notion de complexité d'une formule. La section 3 est encore un peu plus compliquée (à cause du théorème d'incomplétude de Gödel). La section 4 est simple (pas plus compliquée que la 2). La section 5 est très hétérogène du point de vue du niveau, chacun peut y faire son marché ...

Et les exercices sont tous faciles (mais éventuellement avec des petits pièges).

j'ai du mal à voir ce qu'est la connexité c'est un peu flou pour moi

Je ne sais pas si tu a lu le premier document (.doc) ou le deuxième (.pdf) dans ce dernier, à la suggestion de Gwyddon j'ai ajouté :
Définition : Une composante connexe pour la fonction successeur est un sous ensemble d’un modèle qui est clos pour la fonction successeur et telle que pour tout couple d’éléments de la même composante connexe x et y, il existe un entier (naïf) tel que x = s[exp]n[\exp](y) ou y = s[exp]n[\exp](x) (s[exp]n[\exp](x) est une abréviation pour s(s(s...(x)...) avec s appliqué n fois).

Tu peux comprendre une composante connexe comme un sous-ensemble où deux éléments sont toujours liés par le fait que l'un d'entre eux peut s'obtenir à partir de l'autre avec la seule opération "successeur".

Par exemple dans l'ensemble , si je définis la fonction successeur par (je viens de définir un modèle), les composantes connexes sont bien et , puisque la fonction successeur n'a aucun impact sur la première coordonnée (ce qui est dans y reste) et puis si , et alors, en supposant y > x (sinon c'est pareil), il existe bien un entier tel que , c'est à dire que ou encore .

la notion de modèle est abordé sans dire ce que c'est.

Tu peux regarder là : http://forums.futura-sciences.com/post1395351.html.

Pour faire simple, un modèle d'une théorie est un monde où les axiomes (donc les théorèmes) de la théorie sont vrais, un modèle est constitué d'un ensemble, et des interprétations des éléments du langage, par exemple si le langage est L = (#, 0) pour une théorie avec une opération binaire et un élément neutre pour cette opération, par exemple l'ensemble IN muni de l'addition est un modèle de cette théorie et 0 (dans IN) joue le rôle de 0 (dans le langage), et IN muni de la multiplication est aussi un modèle de cette théorie, mais cette fois c'est 1 (dans IN) qui joue le rôle de 0 (dans le langage).

J'espère avoir été plus clair ; en tout état de cause, n'hésite pas à poser toutes les question que tu veux (et essaye les exercices, c'est très formateur).

Merci de ton intérêt pour ce document.

Cordialement

Médiat
-----

[invité576543]

Et les exercices sont tous faciles (mais éventuellement avec des petits pièges).

Je suis un peu surpris par le contenu de l'affirmation. Pour beaucoup de ces exercices, je suis bloqué par le simple fait que je n'ai aucune idée de ce qui est "permis" ou "pas permis" dans une démonstration. Je veux dire par là que ce n'est pas trouver une réponse (ou même plusieurs) qui est difficile, mais trier entre celles qui utilisent des inférences permises ou non.

Par exemple la définition de la connexité, juste avant l'exo 1, utilise explicitement des entiers, du coup je ne sais pas trop si dans les exo qui suivent la définition ce qu'on a le droit de faire avec les entiers qui apparaissent dans la définition de la connexité. Utiliser l'arithmétique ne semble pas adapté dans le contexte!

Déjà voir sⁿ(x) comme une abréviation me met mal à l'aise. C'est une infinité d'abréviations, il me semble, infinité qu'il est impossible d'écrire. J'aurais pensé qu'il est difficile de manipuler cette infinité d'abréviations implicites sans une forme ou une autre d'arithmétique.

Prenons l'exercice 1. La démonstration naïve: si c'est fini alors il y a un n max, et comme s(sⁿ(0))=sⁿ⁺¹(0) est dans la composante de par la définition, il y a contradiction puisque n+1>n. J'imagine la démonstration comme totalement inacceptable, parce qu'utilisant des propriétés "non disponibles". Genre la notion de max, fini implique existence d'un n max, etc. Mais quelles sont les propriétés disponibles? Mystère. Si on essaye de partir de bases plus profondes (i.e., moins de risque d'utiliser des propriétés "non disponibles", mais sans garanties!), faut trouver ce que veut dire "fini". Une possibilité est "ne possède pas de sous-ensemble strict avec lequel il peut être mis en bijection", mais ça ne ressemble pas à de la logique du premier ordre. Aïe. Est-ce autorisé? Ou sinon, où trouver une définition autorisée de "fini"? J'abrège, tout est à l'avenant.

Peut-être que ces réflexions montrent juste ma bêtise. Peut-être montrent-elles que des explications préalables sur "la règle du jeu" pourraient être utiles pour les esprits limités comme le mien.

Cordialement,

[invitefe0032b8]

Merci pour ces éclaircissements
Je n' ais pas vraiment fait de logique cette année, je crois qu'il y a une UE Logique mathématiques en L2 maths mais comme je ne suis pas en maths . Je vais déjà essayer de bien comprendre la section 0 et 1, lire le document sur les modèles et faire les exos.

Merci encore !

[invitec1242683]

Je trouve votre travail fort interessant .
Cependant comme certains membres avant moi vous l'ont fait remarquer , ce livre ne s'adresse pas a des etudiants de cinquième ! La dialectique pere-fils est intéressante ,et consitue un excellent moyen , ludique de surcroît , de faire enseigner les sciences , et parfois les concepts difficiles .
N'y aurait-il pas justement intérêt à tirer profit de cet atout pédagogique et d'introduire l'arithmétique à de jeunes écoliers .
Après tout , c'est un peu ce qu'on faisait à l'époque , avec les " maths modernes" , cependant , bien que demeurant être un sujet passionnant , elles irritaient les esprits vétérants de cette période à cause de leur manque d'interactivité .
Pourquoi pas réinventer ce système ?
Visiblement , vous avez un réel talent pédagogique , bien que mon avis n'ait que peu d'importance , alors pourquoi ne pas l'exploiter davantage ?
Cordialement ,
Weensie

[Médiat]

Je suis un peu surpris par le contenu de l'affirmation. Pour beaucoup de ces exercices, je suis bloqué par le simple fait que je n'ai aucune idée de ce qui est "permis" ou "pas permis" dans une démonstration. Je veux dire par là que ce n'est pas trouver une réponse (ou même plusieurs) qui est difficile, mais trier entre celles qui utilisent des inférences permises ou non

C'est bien là que se trouve, à la fois, le piège de certains exercices et leur aspect pédagogique, d'où mon insistance, manquant parfois de subtilité, pour que le lecteur s'essaye à ces exercices.

Par exemple la définition de la connexité, juste avant l'exo 1, utilise explicitement des entiers, du coup je ne sais pas trop si dans les exo qui suivent la définition ce qu'on a le droit de faire avec les entiers qui apparaissent dans la définition de la connexité. Utiliser l'arithmétique ne semble pas adapté dans le contexte!

Oui, mais des entiers naïfs, ceux que l'on apprend à manipuler en 6^ième, que tu peux considérer comme les chaînes de caractères que tu peux écrire avec 10 signes et certaines conventions d'écriture.

Déjà voir sⁿ(x) comme une abréviation me met mal à l'aise. C'est une infinité d'abréviations, il me semble, infinité qu'il est impossible d'écrire. J'aurais pensé qu'il est difficile de manipuler cette infinité d'abréviations implicites sans une forme ou une autre d'arithmétique.

Et pourtant c'est bien une abréviation, puisque je n'ai écrit qu'une seule chose ; bien sur la question et la réponse sont purement rhétoriques, si tu préfères voir cela comme un schéma d'abréviations, je n'y vois aucune objection. Tu es sans doute familier du schéma de récurrence, s'il ne te gêne pas, le schéma d'abréviations ne devrait pas te gêner non plus, s'il te gêne, je développerais ce point.

Prenons l'exercice 1. La démonstration naïve: si c'est fini alors il y a un n max, et comme s(sⁿ(0))=sⁿ⁺¹(0) est dans la composante de par la définition, il y a contradiction puisque n+1>n.

Tu peux prendre la définition de fini comme " quand je compte ça s'arrête " (et d'un seul coup c'est Turing et toutes la théorie de la récursivité que je viens de convoquer).
Effectivement ta démonstration n'est pas acceptable mais pas pour les raisons que tu invoques (je n'ai pas envie d'en dire trop pour ne pas trop en dévoiler sur l'ensemble des exercices, mais si tu veux une réponse plus précise, envoie-moi un MP)

Peut-être montrent-elles que des explications préalables sur "la règle du jeu" pourraient être utiles.

Cette absence est tout l'intérêt des exercices (c'est donc un choix (par définition critiquable) pédagogique que j'ai fait).

Cordialement

[Médiat]

La dialectique pere-fils est intéressante ,et consitue un excellent moyen , ludique de surcroît , de faire enseigner les sciences , et parfois les concepts difficiles .
N'y aurait-il pas justement intérêt à tirer profit de cet atout pédagogique et d'introduire l'arithmétique à de jeunes écoliers .

Le point de départ de ce petit travail est effectivement une question de mon fils (11 ans), mais malgré ses bons résultats en maths, je ne crois pas qu'il est encore le pouvoir d'abstraction suffisant pour la méthode axiomatique (je sonde parfois ).

Visiblement , vous avez un réel talent pédagogique , [...] , alors pourquoi ne pas l'exploiter davantage ?

C'est très gentil, mais ma cible pour l'instant est le lectorat du forum "Mathématiques du supérieur", j'ai peur que ce talent que vous m'accordez bien généreusement (et bien hâtivement) ne soit pas suffisant pour développer ces idées pour une classe d'âge nettement antérieure (je verrai en fonction de la réponse de mon fils à ces stimulus ).

Cordialement ,

[invité576543]

(...)

C'est bien ce que je pensais. Je n'ai fait preuve que de ma bêtise, comme tu le montres. Je ne suis pas fichu de faire un seul exercice correctement. Ce texte est bien trop compliqué pour moi, bien au-dessus de mon niveau.

Cordialement,

[invitec1242683]

En effet , ce sont la de bons stimuli!
L'idéal serait de partir du calcul au sens propre ( compter avec les cailloux) et puis d'arriver à cela , cette arithmétique !
Mais c'est pas gagné

[Médiat]

L'idéal serait de partir du calcul au sens propre ( compter avec les cailloux) et puis d'arriver à cela , cette arithmétique !

C'est ce que j'ai essayé de faire, mais il est clair que pour bien suivre il faut être un peu accoutumé à la méthode axiomatique, et à la notion de modèle ... (ou faire la démarche de s'accoutumer)

[Médiat]

Il m'apparaît que j'ai, peut-être, sous-estimé la difficulté des pièges de certains exercices, je vais donc essayer d'être un peu plus explicatifs sur ces points.
Néanmoins je conseille fortement de ne pas lire ce qui suit si vous pensez, comme moi, que mettre les mains dedans et même se planter est plus formateur que lire une réponse.

Toi qui entre ici abandonne toute espérance

(Le smiley n'est pas de Dante )

1.  Cliquez pour afficher

   1. Je peux définir 1 = s(0), puis 2 = s(s(0)) ... pour 12 c'est un peu plus long : 12 = s(s(s(s(s(s(s(s(s(s(s(s(0))))) ))))))), etc. On comprend bien que pour tout nombre entier (naïf) je vais pouvoir faire ce petit travail d'écriture. Il va de soi que je ne peux pas écrire toutes ces relations qui me permettraient d'écrire tous les entiers (naïfs) comme des successeurs plus ou moins lointain de 0, mais, chaque fois que j'aurais à manipuler l'un d'entre eux, je sais que je pourrais le faire (ce qui m'évite de le faire).
      On pourrait m'objecter que dans les exemples précédents on voit mal ce qui appartient à un modèle d'une théorie de l'arithmétique et ce qui n'y appartient pas, et qu'on ne sait pas d'où viennent ces nombres qui n'appartiennent pas à l'arithmétique, alors je creuse encore un peu :
      Je note DOUZE un nouveau symbole de constante, et je pose DOUZE = s(s(s(s(s(s(s(s(s(s(s(s(0))))) ))))))). Bien sur la notation habituelle celle apprise en CP est plus pratique puisqu'elle met en jeu un algorithme qui permet de noter le suivant d'un nombre, et même de le lire.
   2. Soit T une théorie de l'arithmétique (avec au moins 0 et s)
      a) , cette expression n'a pas de sens parce que je ne sais pas itérer s x-fois avec x un élément quelconque d'un modèle d'une arithmétique (je sais le faire 2 fois, 154897521548542 fois, mais pas x fois.
      b) , cette expression n'a pas de sens parce que n'existe pas dans notre langage
      c) Pour tout n dans , non seulement cette expression a du sens, mais en plus elle est vraie (au regard des axiomes de s), mais dans cette expression (j'ai changé le nom pour que l'on ne mélange pas les variables du langage et les notations externes au langage) doit bien être comprise comme une abréviation pratique (ou un schéma d'abréviations) et non comme une formule du langage.
      Plus compliqué est le cas , évidemment les deux premières objections sont à nouveau opposable à cette écriture, mais que faire pour le cas c) ?
      c) "Il existe n dans " cette formulation ne convient pas puisque dans l'expression originale y dépend de x, ce qui n'est plus les cas ici (n ayant remplacé y).
      Il n'est pas très compliqué de comprendre ce que veux dire la formule : tout entier x est le successeur plus ou moins lointain de 0, l'évidence que nous sommes ici dans une impasse, c'est que cette formule est fausse (seuls les entiers standard) vérifient cela), mais en plus je ne peux pas la compléter (suffisamment) en restreignant x (dans le langage de la théorie T) à l'ensemble des entiers standard (cf. théorème 19, dont la démonstration n'utilise que le schéma d'induction, en plus de 0 et + dont ce schéma a besoin).
   3. Je vais finir par une analogie avec la théorie des ensembles (ZF), cette partie est donc parfaitement inutile à ceux qui ne connaisse pas cette théorie.
      Parmi les axiomes de ZF, il y a le schéma d'axiomes de compréhension, comme son nom l'indique, il s'agit bien d'un schéma et non d'un axiome, ce schéma nous donne un moyen (une méthode, un algorithme) qui permet d'écrire tous les axiomes nécessaires et surtout ceux dont nous allons avoir besoin (cette périphrase m'évite de dire une infinité d'axiomes).
      D'un point de vue strictement théorique, on peut imaginer que l'algorithme est capable de générer tous les axiomes de la théorie, mais, plus simplement, d'un point de vue pratique, sans rien écrire (de plus que le schéma), nous savons que chaque fois que nous aurons à manipuler une formule, l'axiome de compréhension correspondant à cette formule, fait partie de l'axiomatisation de ZF.
      Il y a évidemment les mêmes remarques à faire pour le schéma d'induction, mais je voulais donner un exemple hors de l'arithmétique.

[invité576543]

Bonjour,

C'est ce que j'ai essayé de faire

Je pense que ce n'est qu'un aspect du texte, et pas le plus important. Les développements exposés sont usuellement présentés (dans d'autres textes d'autres auteurs) dans le cadre des théories de la démonstration. Et le texte occulte cette idée, tout en ne parlant pratiquement que de cela.

Définir les entiers ou l'arithmétique ne demande pas un développement si long et si compliqué. Par contre, définir l'arithmétique d'une manière, et dans un cadre, permettant de formaliser et théoriser sur les démonstrations que l'on peut y faire ou non, oui.

Ce qui est une autre manière de parler de ce qui me met mal à l'aise, qui est l'existence de deux "niveaux" de démonstration. La démonstration comme objet, et les démonstrations portant sur les démonstrations comme objets d'étude.

L'absence de distinction claire entre les deux niveaux me rend la lecture difficile, et les exercices impossibles.

Il y a en fait deux "règles du jeu", l'une est qu'est-ce qu'on a le droit de faire quand on fait des "démonstations sur les démonstrations", et l'autre, l'ensemble des "règles" qui est construit peu à peu au cours du texte pour obtenir l'arithmétique et le cadre dans lequel y faire des démonstrations.

Cordialement,

[invité576543]

Effectivement ta démonstration n'est pas acceptable

Au passage, peux-tu m'ôter un doute (non levé par ton message récent): la démo naïve proposée est-elle correcte pour montrer, avec les outils et dnas le cadre de l'arithmétique usuelle, qu'un sous-ensemble de N non vide et clos pour l'incrémentation est nécessairement infini?

Cordialement,

[Médiat]

Au passage, peux-tu m'ôter un doute (non levé par ton message récent): la démo naïve proposée est-elle correcte pour montrer, avec les outils et dnas le cadre de l'arithmétique usuelle, qu'un sous-ensemble de N non vide et clos pour l'incrémentation est nécessairement infini?

Comme tu de dis pas quelle définition de "infini" tu utilises, je ne sais pas répondre telle quelle est, à cette question.
Je vais traduire ta question dans le cadre de l'arithmétique du premier ordre, donc pas question de quantifier sur des ensembles, pour me ramener au premier ordre je vais supposer qu'il existe une formule (du premier ordre) telle que soit equivalent à (sinon A n'est pas définissable au premier ordre).
Si A est un sous-ensemble non vide de , je peux trouver un et construire la formule :

Dans la notation précédente j'ai terminé les formules atomiques par , ce qui peut paraître inutile puisque va de toute façon vérifier , mais cela évite un problème de notation si ; en tout état de cause je préfère écrire :

Remarques : nous travaillons dans et non dans la théorie, je peux donc utiliser la notation habituelle pour les entiers 1, 2, ...n sans me poser de questions.
La formule vérifie les conditions d'applications du schéma de récurrence donc est une formule vraie dans , et donc A est égal à moins au plus éléments (c'est peut-être une définition acceptable de l'infini dans ce cadre).
En logique du second ordre nous ne serions pas obligé de passer par une formule définissant l'ensemble A.
Pour revenir sur ta "démonstration naïve", tu écris

il y a un n max

Ce n'est pas exact, il n'y a pas de n max : on peut toujours appliquer s à un élément de la théorie.

[invité576543]

Comme tu de dis pas quelle définition de "infini" tu utilises

J'avais précisé

"avec les outils et dans le cadre de l'arithmétique usuelle"

Disons, si c'était une question pour un examen en bac+2 genre concours grandes écoles, si c'est plus précis.

Cordialement,

[invité576543]

Ce n'est pas exact, il n'y a pas de n max : on peut toujours appliquer s à un élément de la théorie.

Ce n'est pas exact que tout sous-ensemble fini de N a un maximum pour l'ordre usuel des entiers?

Cordialement,

[Médiat]

Ce n'est pas exact que tout sous-ensemble fini de N a un maximum pour l'ordre usuel des entiers?

Si, bien sur, mais c'est sⁿ(0) qui est le max dans ce cas, pas n, la preuve tu la donnes toi-même en remarquant que si sⁿ(0) existe, alors sⁿ⁺¹(0) existe aussi, cela montre bien que n n'est pas le max, mais le n appartient ici aux entiers naïfs, pas au modèle qui nous (m')intéresse.

Pour une démonstration strictement dans IN et relativement naïve, tu peux, effectivement, invoquer la contraposée de ce que tu dis ci-dessus : si un sous-enesmble est infini, il n'a pas de max, ce qui est trivialement le cas d'un ensemble non vide clos par l'opération "+ 1" (il n'y a pas de raison de s'encombrer avec la fonction successeur dans IN, où l'on connaît bien l'addition).

[Médiat]

Pour montrer que les exercices ne sont pas vraiment difficiles, voici une démonstration par l'absurde (ce n'est pas la seule possible) pour l'exercice 1 :

 Cliquez pour afficher

Supposons qu'il existe un modèle de PréA qui contiennent une composante connexe de 0 qui soit finie ; construisons cette composante connexe :
Elle contient 0, bien sur, et par définition d'une composante connexe, elle contient les successeurs de tous ses éléments, c'est à dire :
, ou encore en utilisant la notation abrégée : , on s'arrête dès que l'itération de s n'ajoute pas un nouvel élément.
Comme par hypothèse cette composante connexe est finie, je suis bien obligé de terminer cette énumération à un moment ou à un autre, ayant épuisé tous les éléments de cette composante.
Comme cette composante connexe doit contenir les successeurs de chacun de ses éléments, elle doit contenir le successeur de , c'est à dire (mais ce n'est pas encore une contradiction, qui terminerait cette démonstration par l'absurde).
Par conséquent doit être égal à un des éléments de la composante connexe, c'est à dire :

1. soit
2. soit pour un p inférieur ou égal à n (c'est à dire pour un élément trouvé avant (au sens large) )

Le cas 1 est impossible à cause de l'axiome
Le cas 2 est impossible car étant apparu dans l'énumération de la composante connexe, il est successeur d'un élément, que nous appellerons x, apparu strictement avant lui-même donc strictement avant (qui est le dernier), c'est à dire que , ce qui est incompatible avec à cause de l'axiome

[Médiat]

Comme je n'aime pas laisser trop de points imprécis, voici quelques corrigés.
Exercice 4 (PréA). Pourquoi n’est-ce pas gênant d’utiliser ici (ainsi que et alors que le but est justement de trouver une axiomatisation de ?

 Cliquez pour afficher

Parce que, à cette étape, nous décrivons des modèles de la théorie PréA, pas la théorie elle-même, il serait effectivement impossible d’utiliser dans l’axiomatisation de ; mais il serait plus qu' étrange qu’en cherchant à axiomatiser on ne soit pas capable de trouver des modèles construit avec .

Exercice 11 ( Presburger). Pourquoi n’ai-je pas simplement écrit "Les axiomes sont ceux de PréA’ plus deux axiomes pour + " ?

 Cliquez pour afficher

Parce que le schéma d’induction de PréA’ ne génère que les axiomes construits sur les formules utilisant le langage de PréA’, alors que ce même schéma génère les axiomes construits sur les formules utilisant le langage de Preburger, c'est-à-dire avec + en plus, certes les schémas sont les mêmes, mais les axiomes générés ne sont pas les mêmes (ceux de PréA’ appartiennent aussi à Presburger, mais le contraire n’est pas vrai).

Exercice 12 : Ici la démonstration doit se faire intégralement dans le cadre de la théorie Presburger, on pourrait dire que ce que nous devons faire n’est pas de démontrer , mais de démontrer que Presburger démontre c’est d’ailleurs bien le sens de .

 Cliquez pour afficher

Soit P(x) la formule , nous devons donc démontrer que .
En appliquant la définition de :
(Axiome )
(Théorème )
(Axiome )
(Définition de l’égalité)
(Théorème )
(définition de P)
(schéma d’induction appliqué à la formule P)

Exercice 13 ( Presburger). Il est clair que la notation nx utilisée ci-dessus permet de définir la multiplication par n, pour tout n, mais pourquoi n’est-ce pas la définition de la multiplication ?

 Cliquez pour afficher

Parce que nx n’est qu’une notation, et même si on créait un symbole du langage pour chacune de ces « multiplications », on ne pourrait pas quantifier dessus (logique du premier ordre). Une autre objection est que, au mieux, cela permet de définir la multiplication par un élément de la composante connexe de 0 (les éléments « standard »), mais pas par les autres

Exercice 18 (Peano). Pourquoi un argument de compacité ne fonctionne-t-il pas ici ?

 Cliquez pour afficher

Précisons d’abord quel argument de compacité pourrait être utilisé :
Soit une formule vraie pour tous les entiers standards d’un modèle.
Soit la formule , pour n standard l’ensemble des est consistant par compacité (trivial), or cet ensemble affirme que est vérifiée par un élément plus grand que tous les standards ; malheureusement dire que cet ensemble est consistant permet d’affirmer qu’il admet au moins un modèle, pas qu’il est vérifié par tous les modèles.

Exercice 37.
Démontrer que
Une première remarque : dans le document pdf il y a une erreur, la variable t est inutile (reliquat d’une autre version de la formule), heureusement cela donne une formule équivalente à la bonne.

 Cliquez pour afficher

est l’ensemble des formules ne contenant que des quantificateurs bornés, il suffit de montrer que les deux quantificateurs de G(x) sont bornables (désolé pour le néologisme).
La définition de est , par conséquent, , G(x) peut donc être réécrite :
.
Ce qui montre que

[invite787dfb08]

Plop

Me semble pas avoir posté encore pour te féliciter sur ce document, vraiment très complet...

On ne se rend jamais vraiment compte de l'importance de ces "fondements", et on les néglige souvent, si bien que beaucoup de personnes font des mathématiques sans vraiment savoir ce qu'ils font... C'est un peu comme d'apprendre à jouer de la guitare en apprenant par coeur où il faut mettre les doigts, sans même s'intéresser à la théorie. . Il y en a qui gère beaucoup d'ailleurs ce genre de choses...

Donc tout ça pour dire qu'il est indispensable de prendre son temps sur les bases, puisque tout le reste en découle...

Merci alors pour ce doc que je lirai plus en profondeur et que je n'hésiterai pas à conseiller...

+++

[invite9c9b9968]

Hello,

Je reviens sur ce fil car j'ai commencé une étude complète et critique du document. Bien sûr, elle n'en est qu'à ses débuts

L'une des critiques de mmy me paraît fondée, à savoir le fait qu'on ne sait pas a priori quel(s) outil(s) on a le droit d'utiliser. Du coup, il y a dès le début de la section 0) l'utilisation du mot "entier" ou la notation utilisés sans définition préalable, au sein même de définitions, ce qui est gênant ! De même l'utilisation du symbole + me paraît inappropriée sans définition du cadre d'utilisation (sinon on a l'impression de se mordre la queue).. On pourrait à ce stade préciser que "+1" est une notation pour s : s(x) = x+1 de façon formelle.

Après coup j'ai saisi qu'en fait Médiat faisait référence à la définition naïve donnée en français des entiers ; ce qui me paraît confirmé par la présente discussion, mais je pense que ceci vaut d'être explicitement écrit juste après la description naïve, du style "dorénavant dans les définitions primaires nous utiliserons par commodité de langage 'entier' pour ce que nous venons de décrire naïvement".

Le point 1 du message #40 de cette discussion me paraît ainsi indispensable

Autre détail, que j'aurais dû aborder plus haut : annoncer dès le début les prérequis indispensable me paraît aussi essentiel.


Voilà pour l'instant (je n'ai pas beaucoup avancé) pour les points critiques. Les points (très) positifs : les exercices sont pédagogiques (une fois la difficulté énoncée ci-dessus résolue ), le texte est agréable à lire, et c'est passionnant

Maintenant j'ai une question plus "technique" : je n'ai pas réellement compris comment était formé, notamment en quoi les unions sont-elles réellement disjointes ?

[Médiat]

Salut Gwyddon,

D'abord, merci pour le temps passé :

Du coup, il y a dès le début de la section 0) l'utilisation du mot "entier" ou la notation utilisés sans définition préalable, au sein même de définitions, ce qui est gênant !

Je suppose que tu fais allusion à la première définition "en langage naturel", où j'ai pris soin de parler de Marcel et non de 0, et de AuSuivant au lieu de +1 (ou de successeur), mais où j'ai gardé le nom "entier" pour les éléments que je suis en train de définir, j'ai eu peur qu'en les appelant des Zblurps (c'est ainsi que je les appelle quand je me parle à moi-même), la phrase perde son aspect provocant (à la réflexion) au profit de l'inintelligible ; de plus, je ne trouve pas choquant d'appeler entier les éléments d'une théorie quand on a la volonté d'axiomatiser les entiers, ce qui est important, c'est que dans la définition formelle, aucun présupposé sur les éléments du langage (0 et s) ne soit nécessaire à la définition (mais peut être nécessaire à la compréhension).

De même l'utilisation du symbole + me paraît inappropriée sans définition du cadre d'utilisation (sinon on a l'impression de se mordre la queue).. On pourrait à ce stade préciser que "+1" est une notation pour s : s(x) = x+1 de façon formelle.

J'ai un petit doute sur le paragraphe auquel tu fais allusion, si c'est celui sur la construction du modèle , alors l'utilisation du +1 est légitime et même obligatoire, car nous sommes dans le modèle naïf des entiers (quelque soit la façon de le définir, en tout cas, le modèle où les enfants apprennent à compter, et où +1 est parfaitement défini), par contre il faut absolument que j'interprète les éléments du langage dans ce modèle).

je pense que ceci vaut d'être explicitement écrit juste après la description naïve, du style "dorénavant dans les définitions primaires nous utiliserons par commodité de langage 'entier' pour ce que nous venons de décrire naïvement".

Le point 1 du message #40 de cette discussion me paraît ainsi indispensable

Ok

Autre détail, que j'aurais dû aborder plus haut : annoncer dès le début les prérequis indispensable me paraît aussi essentiel.

Le but, non avoué, de ce travail est de montrer le petit "twist" que le logicien doit faire en permanence, la difficulté que tu décris est justement le point que je voulais exemplifié, d'où la pléthore d'exercices n'ayant pour but que de mettre ce point en scène (en fait c'est le récit d'un rite de passage, où celui qui passe est le lecteur (cf. ma référence à Dante) ). Pour pouvoir lire ce texte, il me semble qu'un peu de connaissance de logique n'est pas inutile, mais pas non plus crucial, il suffit, en fait, de savoir ce qu'est un langage, un axiome, un connecteur et un quantificateur ; je suis, évidemment, près à répondre à toutes les questions permettant d'éclairer un point particulier (comme celui ci-dessous) ; pour quelqu'un ayant de bonnes (sans plus) connaissances de la logique du premier ordre, le texte tout entier n'aurait que l'intérêt de la compilation (et de la mise en scène), mais il ne contient rien d'original.

Maintenant j'ai une question plus "technique" : je n'ai pas réellement compris comment était formé, notamment en quoi les unions sont-elles réellement disjointes ?

Si ce n'était pas des unions disjointes les différentes composantes auraient des éléments en communs, et il serait difficile de parler de composantes connexes. Tu peux imaginer une fibration (à ne pas prendre au sens strict) où l'ensemble de base serait un ordinal suffisament grand est où les fibres seraient une copie de , des copies de et des copies de (sans oublier que "des" copies peut vouloir dire un cardinal monumental), la seule chose à faire dans ce modèle est d'interprèter les éléments du langage et de contrôler que cette interprétation vérifie bien les axiomes.

[invite9c9b9968]

Si ce n'était pas des unions disjointes les différentes composantes auraient des éléments en communs, et il serait difficile de parler de composantes connexes. Tu peux imaginer une fibration (à ne pas prendre au sens strict) où l'ensemble de base serait un ordinal suffisament grand est où les fibres seraient une copie de , des copies de et des copies de (sans oublier que "des" copies peut vouloir dire un cardinal monumental), la seule chose à faire dans ce modèle est d'interprèter les éléments du langage et de contrôler que cette interprétation vérifie bien les axiomes.

Hello,

En fait j'ai saisi mon erreur, au début j'étais en train de me dire "mais bon sang, on a bien mais en fait non en terme de composante connexe puisque l'une contient un zéro, pas l'autre

Je continue mon petit bonhomme de chemin

Note : tu dis qu'un peu de logique suffit, mais bon si les gens ne savent pas ce que signifie par exemple , c'est dur

[Médiat]

"mais bon sang, on a bien mais en fait non en terme de composante connexe puisque l'une contient un zéro, pas l'autre

Pour être sur que le lecteur comprenne bien :
Il va de soi que et contienne chacun un 0, mais ils sont différents, puisque l'union est disjointe, et en fait le seul 0 qui ait un intérêt ici est celui qui interprète le 0 du langage.

Note : tu dis qu'un peu de logique suffit, mais bon si les gens ne savent pas ce que signifie par exemple , c'est dur

L'arithmétique modulaire basique ne se voit plus en bac + 1 ? Effectivement, si c'est le cas il faudrait que j'explique un peu...

En tout état de cause, merci de ton intérêt.

[invite9c9b9968]

Me revoici

Si si l'arithmétique modulaire se voit en bac+1, mais au départ je pensais que tu destinais ça à des bac+0 qui rentrent dans l'enseignement supérieur

Et oui merci de la précision aux lecteurs, j'admets que ma formulation était hum... douteuse


Le théorème 4 me paraît douteux, présenté tel quel. En fait le souci vient des quantificateurs ; dans la formule apparaît un quantificateur, ce qui somme toute vu l'objectif est normal et logique :

Le souci vient alors de l'axiome supplémentaire : il suppose l'utilisation d'une formule dépendante de x, or la formule est indépendante de x

Du coup j'ai un peu du mal

[Médiat]

Le théorème 4 me paraît douteux, présenté tel quel. En fait le souci vient des quantificateurs ; dans la formule apparaît un quantificateur, ce qui somme toute vu l'objectif est normal et logique :

Le souci vient alors de l'axiome supplémentaire : il suppose l'utilisation d'une formule dépendante de x, or la formule est indépendante de x

Tu as parfaitement raison, il y a là (au mieux) un abus de langage, j'aurais dû écrire :

Soit la formule (pour p > 0)
et dans l'exercice suivant
Montrer que n’est pas valide dans un modèle de PréA contenant
et le théorème 4 devient .

[invite9c9b9968]

Ah là ça me va

Je continue mon exploration détaillée !

[invite9c9b9968]

J'ai une petite question : c'est quoi pour cardinal transfini ?

Sinon je suggère l'ajout de la définition d'une théorie catégorique juste avant le théorème 5 : "une théorie est catégorique en le cardinal A s'il existe un unique modèle en ce cardinal A, à isomorphisme près"

Remarque stylistique : dans l'exercice 10 je dirais plus des théorèmes, que les théorèmes.

[Médiat]

J'ai une petite question : c'est quoi pour cardinal transfini ?

C'est l'union disjointe de copies de , le produit cartésien si tu préfères.

Sinon je suggère l'ajout de la définition d'une théorie catégorique juste avant le théorème 5 : "une théorie est catégorique en le cardinal A s'il existe un unique modèle en ce cardinal A, à isomorphisme près"

Oui, tu as raison là aussi

Remarque stylistique : dans l'exercice 10 je dirais plus des théorèmes, que les théorèmes.

Euh, il y a bien écrit "des théorèmes " dans l'exercice 10 .

Merci de faire vivre un peu ce document.

[invite9c9b9968]

C'est l'union disjointe de copies de , le produit cartésien si tu préfères.

ok je vois maintenant comment lui donner un sens, quoique l'imaginer pour ça me fait mal à la tête

Euh, il y a bien écrit "des théorèmes " dans l'exercice 10 .

Non non c'est moi, il faut que j'aille chez l'ophtalmo

[Médiat]

l'imaginer pour ça me fait mal à la tête

C'est pour cela que j'aime particulièrement la logique : il y a un moment où les neurones s'affolent et puis d'un seul coup, à la grâce d'un théorème comme celui de Löwenheim-Skolem ou celui de Los-Vaught :

Là tout n'est qu'ordre et beauté,
Luxe, calme et volupté.

Je crois que toi tu peux me comprendre : j'ai un rapport sensuel aux maths.