Arithmétique

[Turgon]

Au modérateurs: ce doublon a pour but de condenser mes interrogations précédentes, ce qui permettrait à l'auteur du post de répondre plus facilement et ainsi d'éviter à chacun de long écueils. Si malgré tout, règle faisant loi, il faille supprimer ce message, je m'excuse d'avance.


Après une journée bien remplie et avec plus de nourriture (de boisson surtout) dans l'estomac, je crois que je peux compresser toutes mes questions en une:

Lorsque, considérant un langage, on en fait une interprétation dans une situation concrète (comme vous l'avez fait en me donnant votre exemple), quel statut ont les objets du modèle qu'on ne peut obtenir avec les règles du langage, mais qui existent tout de même dans le modèle? Si ces objets "s'insèrent" automatiquement dans le langage malgré tout, alors tout s'explique (sinon, on en revient au roman d'en haut).

J'espère avoir été plus clair que ci-dessus (difficile de l'être moins).

Cordialement.
-----

[Médiat]

Lorsque, considérant un langage, on en fait une interprétation dans une situation concrète (comme vous l'avez fait en me donnant votre exemple), quel statut ont les objets du modèle qu'on ne peut obtenir avec les règles du langage, mais qui existent tout de même dans le modèle? Si ces objets "s'insèrent" automatiquement dans le langage malgré tout, alors tout s'explique (sinon, on en revient au roman d'en haut).

Je ne suis pas certain de comprendre complètement cette question, mais je vais essayer.

Les objets du modèles ont tous un statut commun : appartenir au modèle, certains d'entre eux sont en plus définissables, soit parce qu'ils interprètent une constante (le 0 de IN qui interprète le 0 du langage), soit parce qu'il existe une formule du langage qui fait qu'il existe un et un seul élément dans chaque modèle qui la vérifie (Par exemple on peut démontrer (c'est un axiome ), qu'il existe un et un seul élément x, tel que x = s(0)).
Et d'autres éléments du modèle sont juste là . Par exemple dans la théorie des corps de caractéristique 0, on peut définir tous les éléments de , mais pas tous les éléments de ).

Un autre point, si on a un modèle d'une théorie, on peut enrichir le langage avec un symbole de constante pour chacun des éléments du modèle (mêmes et surtout les non définissables dans le langage initial), ce qui permet de manipuler ces éléments (par exemple dans .


Un superbe exemple du problème que vous soulevez est le paradoxe de Löwenheim-Skolem : Si ZFC est consistante alors elle admet un modèle dénombrable, dans le quel on trouve des ensembles de cardinal strictement plus grand que le dénombrable.

J'en parle un peu plus là : http://forums.futura-sciences.com/ma...ombrables.html.

La première difficulté de ZF est de comprendre l'axiome des parties .

[Médiat]

Ayant été sollicité par mp sur 2 questions qui peuvent intéresser plusieurs lecteurs, je poste ici les réponses :

1) Un document permettant de prendre contact avec la logique du premier ordre.
J'ai trouvé cela sur le net : http://deptinfo.cnam.fr/master/fichiers/courslog02.pdf
En particulier les §1.1 à 1.3 et 2.1 à 2.2. Les autres § des chapitres 1 et 2 sont intéressants aussi, mais pas nécessaire à la lecture du document sur l'arithmétique.

2) Expliciter un peu le modèle de la page 4 :
Ce modèle est constitué de IN, auquel on adjoint des copies (éventuellement aucune) de Z auquel on adjoint des copies de Z/pZ (éventuellement aucune) pour chaque p dans IN.

Par exemple pour , on a IN "plus" 3 copies de Z "plus" 2 copies de Z/5Z "plus" 1 copie de Z/13Z.
On peut, par exemple, l'écrire comme l'ensemble des couples (a, b) où a appartient à {0, 1, ... 6} et
i) b appartient à IN si a = 0
ii) b appartient à Z si a = 1, 2 ou 3
iii) b appartient à Z/5Z si a = 4 ou 5
iv) b appartient à Z/13Z si a = 6

Ce qui se généralise très bien avec des et des infinis.

[karlp]

Bonjour Médiat

Accepteriez vous de nous donner votre démonstration pour l'exercice 2 (page 4)?: "Démontrer qu'un modèle ne contient qu'une seule composante connexe de type CC1 ?"

(je vous ai dit que j'étais très lent; je cherche par ailleurs les outils qui me permettront de comprendre le modèle que vous présentez ensuite:j'ai du "pain sur la planche" )

[Médiat]

Bonjour karlp,

Un modèle doit contenir 0, donc forcément au moins une composante de type CC1 (puisque le type CC2 est impossible).

Une composante connexe de type CC1 contient 0, s'il y avait deux composantes de type CC1, elles contiendraient toutes les deux 0, qui aurait donc un successeur dans chacune des composantes connexes, or 0 ne peut avoir qu'un seul successeur.

N'hésitez pas à me solliciter, c'est un plaisir.

Cordialement,

[karlp]

Bonjour karlp,

Un modèle doit contenir 0, donc forcément au moins une composante de type CC1 (puisque le type CC2 est impossible).

Une composante connexe de type CC1 contient 0, s'il y avait deux composantes de type CC1, elles contiendraient toutes les deux 0, qui aurait donc un successeur dans chacune des composantes connexes, or 0 ne peut avoir qu'un seul successeur.

N'hésitez pas à me solliciter, c'est un plaisir.

Cordialement,

Quelle élégance !!

Il va me falloir du temps pour assimiler cette façon de démontrer.
Je n'hésiterai pas à faire appel à vos talents.
(J'ai devant moi quelques heures de travail pour découvrir les notions nécessaires à la poursuite de ma lecture)
Merci !

[karlp]

2) Expliciter un peu le modèle de la page 4 :
Ce modèle est constitué de IN, auquel on adjoint des copies (éventuellement aucune) de Z auquel on adjoint des copies de Z/pZ (éventuellement aucune) pour chaque p dans IN.

Par exemple pour , on a IN "plus" 3 copies de Z "plus" 2 copies de Z/5Z "plus" 1 copie de Z/13Z.
On peut, par exemple, l'écrire comme l'ensemble des couples (a, b) où a appartient à {0, 1, ... 6} et
i) b appartient à IN si a = 0
ii) b appartient à Z si a = 1, 2 ou 3
iii) b appartient à Z/5Z si a = 4 ou 5
iv) b appartient à Z/13Z si a = 6

Ce qui se généralise très bien avec des et des infinis.

Bonjour Médiat

Je sais maintenant ce qu'est une "classe résiduelle modulo n" et comprends donc un peu mieux l'écriture du modèle ci dessus.
Je crois comprendre que nous recherchons des couples en raison de la définition de " composante connexe" (expression que je découvre également).

En revanche, je ne comprends pas pourquoi le fait que (a = 0) implique que b appartienne à IN par exemple.
Je me pose la même question pour les conditions i à iv.

Avec tous mes remerciements anticipés.

[Médiat]

Bonjour karlp,
Avant de répondre à cette dernière question, je poste un petit dessin, que j'avais préparé pour illustrer géométriquement les différents types de composantes connexes.
Il faut bien comprendre que toutes les lignes noires devraient, en fait, être des lignes pointillées, afin de bien définir le successeur.
Le petit trait noir représente le 0.
Les flèches indiquent que les droites se prolongent indéfiniment dans le sens de la flèche.
La composante CC2a est impossible puisque le dernier point à droite n'a pas de successeur.
La composante CC2b est impossible puisque le point commun au segment de droite et au cercle serait successeur de deux éléments différents.
La composante CC2c est impossible puisque 0 serait successeur d'un élément.
Amicalement,

[Médiat]

En revanche, je ne comprends pas pourquoi le fait que (a = 0) implique que b appartienne à IN par exemple.
Je me pose la même question pour les conditions i à iv.

C'est un peu normal, car il ne s'agit pas ici d'une implication au sens de démonstration, mais d'un choix que je fais pour représenter le modèle.

Par exemple si vous figez la valeur de a, par exemple a = 0, alors b parcours IN, et si a = 1, il est clair que les couples obtenus sont tous différents des précédents, etc.

Pour continuer l'analogie géométrique, vous pouvez imaginer les 7 points {0, 1, 2, 3, 4, 5, 6} disposés sur un segment de droite, et sur le point 0, on place une demi-droite (perpendiculairement) pour représenter IN, sur chacun des points 1, 2 et 3 on place une droite (pour représenter Z), sur les point 4 et 5 vous placez un pentagone (pour Z/5Z), et sur le point 6 vous placez un 13-agone (pour Z/13Z).

[karlp]

Bonjour karlp,
Avant de répondre à cette dernière question, je poste un petit dessin, que j'avais préparé pour illustrer géométriquement les différents types de composantes connexes.
Il faut bien comprendre que toutes les lignes noires devraient, en fait, être des lignes pointillées, afin de bien définir le successeur.
Le petit trait noir représente le 0.
Les flèches indiquent que les droites se prolongent indéfiniment dans le sens de la flèche.
La composante CC2a est impossible puisque le dernier point à droite n'a pas de successeur.
La composante CC2b est impossible puisque le point commun au segment de droite et au cercle serait successeur de deux éléments différents.
La composante CC2c est impossible puisque 0 serait successeur d'un élément.
Amicalement,

C'est très rassurant pour moi ! Les schémas CC1, CC2c et CC4 correspondent à ce que je m'étais spontanément représenté.
Les autres schémas me permettent de "nettoyer" les a priori qui affectent ma compréhension.

Je poursuis le travail .
Amicalement

[karlp]

C'est un peu normal, car il ne s'agit pas ici d'une implication au sens de démonstration, mais d'un choix que je fais pour représenter le modèle.

Par exemple si vous figez la valeur de a, par exemple a = 0, alors b parcours IN, et si a = 1, il est clair que les couples obtenus sont tous différents des précédents, etc.

Pour continuer l'analogie géométrique, vous pouvez imaginer les 7 points {0, 1, 2, 3, 4, 5, 6} disposés sur un segment de droite, et sur le point 0, on place une demi-droite (perpendiculairement) pour représenter IN, sur chacun des points 1, 2 et 3 on place une droite (pour représenter Z), sur les point 4 et 5 vous placez un pentagone (pour Z/5Z), et sur le point 6 vous placez un 13-agone (pour Z/13Z).

J'ai une question qui, je le crains, illustrera ma profonde ignorance: nous cherchons un modèle pour la théorie préA; il s'agit de vérifier que tout élément du modèle respecte les axiomes.
Pourquoi est-ce que IN , tout seul, ne serait pas approprié ?
Posée autrement: est-ce que cette structure IM, assez complexe pour un profane comme moi, est nécessaire ou bien est-ce un exemple parmi d'autres ?

[Médiat]

Dans cette structure IM, seule la composante CC1 est obligatoire, les ensembles et peuvent être vides.

Donc effectivement IN est bien un modèle de PréA (mais on n'en cherche pas un , mais tous), le théorème important, c'est celui qui commence par l'Exercice 3, et la phrase qui suit l'Exercice 7 : c'est à dire que l'on connait tous les modèles de PréA.
Et comme certains de ces modèles sont très différents de IN, il paraît naturel de chercher à faire mieux, d'où la théorie PréA'.

[karlp]

Dans cette structure IM, seule la composante CC1 est obligatoire, les ensembles et peuvent être vides.

(1) Donc effectivement IN est bien un modèle de PréA (mais (2) on n'en cherche pas un , mais tous), le théorème important, c'est celui qui commence par l'Exercice 3, et la phrase qui suit l'Exercice 7 : c'est à dire que l'on connait tous les modèles de PréA.
Et comme certains de ces modèles sont très différents de IN, il paraît naturel de chercher à faire mieux, d'où la théorie PréA'.

(1) OUf !!!!

(2) C'est effectivement ce que j'avais "oublié".

Je vais poursuivre ma lecture ( en cherchant pourquoi la classe résiduelle modulo p joue un rôle important ici; la difficulté est grande , en raison de la nouveauté de cette notion pour moi. Je n'avais encore jamais entendu parler de la congruence modulo n il y a deux jours à peine)

Merci !

[karlp]

Bonjour Médiat

J'avance à pas de fourmis et "coince" sur la définition du successeur de x dans la classe résiduelle modulo p: pourquoi le successeur de x est-il nécessairement strictement inférieur à p ? (j'ai honte de poser cette question, mais la honte ne tue pas: serait-ce la conséquence du fait que "x congruent à y modulo n "implique qu'"il existe k tel que (x-y) = kn" ? - N'ayant jamais "joué" avec cette notion de congruence modulo n, je soupçonne qu'elle possède des propriétés évidentes pour chacun mais qui ne me sautent pas aux yeux)

Je ne sais pas non plus lire x+1[p]

Je vais essayer de poursuivre pour voir si je peux me faire ne serait-ce qu'un vague idée de la réponse à l'exercice 3.
En revanche je n'ai pas la moindre idée de la solution à l'exercice 4.

Amicalement.

[Médiat]

Por les classes résiduelles modulo p, c'est à dire les restes possibles dans la division d'un entier par p, ces restes sont 0, 1, ... (p-1), donc bien inférieur à p.


se lit s(x) est congru à (x+1) modulo p.

Pour vous donner un exemple simple Z/5Z = {0, 1, 2, 3, 4} et les opérations sont par exemple 3 + 1 = 4, 3+2 = 0 etc.

Pour l'exercice 4, il s'agit simplement de remarquer que dans cette partie on fabrique des modèles d'une théorie, on a donc le droit de manipuler toutes les structures connues (ou non), il ne faudrait pas utiliser IN dans l'axiomatisation de IN, mais pour fabriquer des modèles, il n'y a pas de problème.

[karlp]

(1) Por les classes résiduelles modulo p, c'est à dire les restes possibles dans la division d'un entier par p, ces restes sont 0, 1, ... (p-1), donc bien inférieur à p.

(2)
se lit s(x) est congru à (x+1) modulo p.

Pour vous donner un exemple simple Z/5Z = {0, 1, 2, 3, 4} et les opérations sont par exemple 3 + 1 = 4, 3+2 = 0 etc.

(3) Pour l'exercice 4, il s'agit simplement de remarquer que dans cette partie on fabrique des modèles d'une théorie, on a donc le droit de manipuler toutes les structures connues (ou non), il ne faudrait pas utiliser IN dans l'axiomatisation de IN, mais pour fabriquer des modèles, il n'y a pas de problème.

(1) Je comprends !!!
(3) C'est parfait pour moi !!!

(2) Un peu plus difficile mais je vais y arriver; ce n'est qu'un problème de familiarité avec les objets. L'exemple est très clair.


Je vais avoir besoin de temps pour assimiler (comme je vous l'ai dit je suis extrêmement lent)

Bonne journée à vous .

[karlp]

Excusez moi d'être si "lourd" (comme disent les jeunes)

Quand vous écrivez:

Pour vous donner un exemple simple Z/5Z = {0, 1, 2, 3, 4} et les opérations sont par exemple 3 + 1 = 4, 3+2 = 0 etc.

Puis-je traduire, en langage naturel, que l'ensemble Z/pZ contient les p-1 éléments qui sont les "restes" des "x congruents à y modulo p" ?

[Médiat]

Puis-je traduire, en langage naturel, que l'ensemble Z/pZ contient les p-1 éléments qui sont les "restes" des "x congruents à y modulo p" ?

Absolument, vous voyez, vous vous diffamez .

[karlp]

Absolument, vous voyez, vous vous diffamez .

Attendez la suite

(juste après l'exercice 4 et avant le 5): f est la fonction qui associe à tout élément de IN un élément de cc1
Très naïvement je suis tenté de "ranger" les x, y , etc.. dans IN et les f(x), f(y),... dans cc1.

Vous écrivez "Soit x élément de cc1": cela signifie t'il qu'a priori cc1 est un sous ensemble de IN ? (je le crois mais me méfie tellement de ce que l'on croit "évident").

Je crois comprendre la démonstration du caractère injectif de f (mais pas encore au point de pouvoir la reproduire de moi-même).

[Médiat]

Puis-je traduire, en langage naturel, que l'ensemble Z/pZ contient les p-1 éléments qui sont les "restes" des "x congruents à y modulo p" ?

J'ai répondu trop vite, sans voir une petite faute de frappe : l'ensemble Z/pZ contient les p éléments qui sont les restes possibles dans la division par p (ne pas oublier le 0).

[Médiat]

Vous écrivez "Soit x élément de cc1": cela signifie t'il qu'a priori cc1 est un sous ensemble de IN ?

Non, pas du tout, x est ici une variable, elle n'est pas, a priori censé être dans un ensemble particulier avant qu'on le dise. Je reconnais que c'est assez maladroit de ma part, j'aurais pu utiliser, par exemple les premières lettres de l'alphabet pour cc1, et les dernières pour IN, ce qui aurait donné, pour la première phrase :

Soit , c'est-à-dire que est dans la composante connexe contenant 0, c'est-à-dire qu'il existe n tel que (rappelons que est une abréviation pour s(s(s...(0)...)) avec s appliqué n fois).

La phrase suivante serait inchangée.

Car il s'agit bien de deux phrases différentes, les variables peuvent donc y jouer des rôles différents (ce n'est pas une excuse pour ma maladresse, mais une justification mathématique ).

[karlp]

Non, pas du tout, x est ici une variable, elle n'est pas, a priori censé être dans un ensemble particulier avant qu'on le dise. Je reconnais que c'est assez maladroit de ma part, j'aurais pu utiliser, par exemple les premières lettres de l'alphabet pour cc1, et les dernières pour IN, ce qui aurait donné, pour la première phrase :

La phrase suivante serait inchangée.

Car il s'agit bien de deux phrases différentes, les variables peuvent donc y jouer des rôles différents (ce n'est pas une excuse pour ma maladresse, mais une justification mathématique ).

C'est parfait pour moi: j'ai pu corriger mes erreurs de lecture.

Je vais reprendre le paragraphe et réfléchir à l'exercice 5 (je doute fort être en mesure de le résoudre, mais je vais essayer de me faire une idée, au moins intuitive)

Passez une excellent soirée

[Médiat]

Bonjour,

Je reviendrai sur l'exercice 5 si des questions se font jour, mais je voudrais dès maintenant faire quelques remarques.

L'exercice 5 termine donc la démonstration que tout modèle de PréA contient une et une seule composante connexe infinie et contenant 0 et que cette composante est isomorphe à IN ; une question légitime pourrait donc être : pourquoi ne pas ajouter aux axiomes de PréA que tous les éléments sont dans la même composante connexe (celle de 0) ? C'est à dire d'imposer que pour tout élément d'un modèle il existe n tel que ? La réponse est dans la question, le "n" qui apparaît dans la phrase précédente est un entier, et comme je l'ai dit précédemment, on ne peut pas axiomatiser l'ensemble des entiers en disant "je prend mes variables dans l'ensemble des entiers, c'est à dire dans l'ensemble que je n'ai pas encore défini".

Il y a une solution qui ressemble à celle-ci (deux mêmes au sens strict, mais c'est en fait deux fois la même avec deux habits différents) : se placer dans le cadre d'une théorie des ensembles, par exemple ZF (l'autre solution similaire consiste à se placer dans le cadre de la logique du 2^nd ordre), voir par exemple ici : http://www.math.ens.fr/culturemath/m...ue/entiers.pdf.

Dans ce nouveau cadre, le principe de récurrence peut s'écrire (je ne reprends pas les notations du pdf précédent), :



Et on retrouve dans cette écriture la différence entre dire "Tout" en français, ou le dire en langage formel.

Concours ouvert à tous :

Soit la proposition suivante dépendant d'une variable x, dans laquelle intervient une proposition quelconque de deux variables :


Question : quelle est la meilleure façon d'écrire cette proposition en français ?

Comme une certains M. S. dont certains doivent se souvenir, je suis le seul juge de ce que veut dire "meilleure" dans la phrase précédente .

[karlp]

Bonjour Médiat

Je me sens bien incapable de participer au concours, sauf pour laisser à chacun la chance (de probabilité 1) de n'être pas dernier !

J'ai passé une bonne partie de ma soirée à "étudier" la démonstration établissant que f est injective.
Sauf erreur, vous proposez d'ailleurs deux démonstrations.
La deuxième (celle qui part sur l'hypothèse que m est strictement supérieur à n) est pour moi "lumineuse" (et d'une élégance à laquelle je suis très sensible).
J'ai beaucoup de mal à comprendre en quoi la première est une démonstration: j'ai l'impression qu'il s'agit simplement d'une "écriture" exhibant ce qui est implicite dans les définitions de f.
(je ne désespère pas : j'ai passé des jours et des jours à essayer de comprendre l'argument diagonal de Cantor montrant que le cardinal de IR est strictement plus grand que celui de IN; jusqu'au jour où je ne parvenais plus à comprendre ce qui avait pu me bloquer dans ma compréhension. Peut-être que je cherche des difficultés où il n'y en a pas ?).
J'ai passé l'autre partie de la soirée à essayer de démontrer, en vain, que f est surjective.
J'ai pensé qu'il fallait en passer par le constat que tout élément de cc1 est de la forme Sn(0) et donc de la forme f(x); et que si ce n'était pas le cas, alors O (de MI) ne serait pas égal à f(O) (de IN), en contradiction avec la définition de f.

[invite7863222222222]

je tente, en français, la 2nde formule par : soit x et y des ensembles alors si pour tout t, t appartient à x alors t appartient y alors on a la propriété P(x, y) entre x et y . C'est pas trop incorrect ?

[Médiat]

@karlp : je ne suis pas très satisfait de ma prose dans la démonstration de l'injectivité, je réfléchis à une meilleure rédaction.
Pour la surjection, c'est très simple pour résoudre , il "suffit" de se demander à quoi est égal f(n) (car pour la fonction f, l'ensemble de départ, c'est bien IN, on a donc le droit d'utiliser des entiers, alors que dans l'écriture le "n" n'est qu'une abréviation pratique.

[Médiat]

je tente, en français, la 2nde formule par : soit x et y des ensembles alors si pour tout t, t appartient à x alors t appartient y alors on a la propriété P(x, y) entre x et y . C'est pas trop incorrect ?

Votre réponse est mathématiquement correcte, mais ce n'est que la lecture de la proposition formelle, imaginez que vous deviez expliquer cela à quelqu'un ignorant les mathématiques, votre formulation ne l'aiderait pas du tout.

[invite7863222222222]

Votre réponse est mathématiquement correcte, mais ce n'est que la lecture de la proposition formelle, imaginez que vous deviez expliquer cela à quelqu'un ignorant les mathématiques, votre formulation ne l'aiderait pas du tout.

Oui c'est pas fait expres j'ai mal lu, je vais retenter. Désolé.

[invite7863222222222]

A nouveau :

soit x un ensemble, si quelque soit y, pour tout t, t appartient à x alors t appartient y alors on a la propriété P(x, y) entre x et y.

[Médiat]

Ne soyez pas désolé, de toute façon cela fait avancer le schmilblick.

Pour ne pas vous envoyer sur une fausse piste, disons que p(x, y) se lit "p est vérifié entre x et y", ce n'est pas très joli, mais ce n'est pas le point important.

Pour votre réponse : il y a encore trop de choses qui cachent le sens profond (ce qui ne veut pas dire que c'est incorrect).

Je n'ai pas donné cet "exercice" au hasard, la solution de ce petit concours est une clé importante pour la compréhension de ce qu'est une théorie du premier ordre, de ce qu'est ZF, bien sur, et surtout d'une différence fondamentale entre langage naturel et langage formel, pour exprimer "tout".