Syntaxe et sémantique autour de Z

ignatus · October 2019

Bonjour,
j'ai parcouru le fil parallèle qui parle de la théorie des modèles, mais je préfère ouvrir un nouveau fil concernant un problème qui est lié, dans mon esprit, à la notion de modèle.
Voilà le problème.
Dans un fil portant sur "la règle des signes" http://www.les-mathematiques.net/phorum/read.php?18,1864264,1869008#msg-1869008 , j'ai affirmé que j'avais une démonstration, dans le contexte de la construction des entiers relatifs comme quotient de N x N, que la règle des signes était équivalente à la distributivité.
Foys a posté un contre-exemple qui montre une application qui vérifie la règle des signes, mais pas la distributivité.
J'ai répondu qu'il ne s'agissait pas d'un véritable contre-exemple, car tout dépendait du contexte dans lequel on avait construit Z. Pour appuyer cette affirmation, j'ai joint le cours d'un enseignant qui, en utilisant la définition du produit des relatifs, arrive à démontrer la distributivité à partir de la règle des signes.

Il s'est avéré qu'il fallait faire très attention à ce qu'on appelait règle des signes. Face à mes contradicteurs qui me reprochaient de nier l'évidence, j'ai été amené à distinguer le niveau syntaxique et le niveau sémantique. J'ai assimilé le contre-exemple de Foys a un usage syntaxique de la règle des signes, alors qu'un usage sémantique de cette règle la fait intervenir dans le cadre d'une construction de Z. J'ai eu tendance alors à assimiler construction de Z et modèles de Z, mais je ne suis pas sûr que cela soit exact.
Je pense maintenant différemment. Il me semble qu'il y a le modèle usuel, intuitif des entiers relatifs, avec toutes les propriétés que l'on y rencontre habituellement. Mais se pose le problème des relations logiques entre chacune de ces propriétés. Ces relations dépendent d'une architecture logique qui définit la manière dont on a construit Z. Autrement dit, dans la construction de Z, on reste au niveau syntaxique. L'interprétation de cette construction donne, en première approximation, les même énoncés usuels, mais avec des relations logiques différentes.
Le cours que j'ai utilisé comme argument d'autorité utilise deux axiomes, les valeurs absolues et la règle des signes, pour montrer la distributivité. Dois-je comprendre ça comme une syntaxe nouvelle qui permet de dériver la distributivité ?

Bon là je commence à fatiguer. Je voudrais simplement comprendre ce que l'on appelle le niveau syntaxique et le niveau sémantique avec l'exemple des entiers relatifs.
Merci.

ignatus.

Dom · October 2019

Je ne suis pas compétent, bien sûr.
Mais pour ajouter de l’eau au moulin de l’importance de savoir de quoi on parle, j’ajoute un exemple de source de quiproquo.
Quand on parle de $\mathbb Z$, on a déjà des confusions possibles.
Certains ne parlent que de l’ensemble (sans rien d’autre, tout nu !) et d’autres parlent de l’anneau (donc de $\mathbb Z$ muni des deux lois et des axiomes usuels).
Je crois que déjà là, ça peut engendrer un dialogue de sourd.
Mais mon intervention n’est qu’introductive.

Lisons les autres intervenants, après un peu de patience.

verdurin · October 2019

Il me semble possible, même si c'est très lourd, de construire $\mathbf{Z}$ comme on le faisait au collège au début des années soixante.
J'étais élève à l'époque et il n'y avait pas trace de démonstration en « algèbre », juste des règles à appliquer.

Disons que l'on prend $\mathbf{Z}=\{+,-\}\times\mathbf{N}$ dans lequel on identifie $(+0)$ et $(-0)$.

On défini l'addition, que le je note $\oplus$ par

$\quad-\ \forall (x,y)\in\mathbf{Z}^2\ x\oplus y=y\oplus x$
$\quad-\ \forall (a,b)\in\mathbf{N}^{*2}$
$\qquad\bullet\ (+a)\oplus(+b)=\bigl(+(a+b)\bigr)$
$\qquad\bullet\ (-a)\oplus(-b)=\bigl(-(a+b)\bigr)$
$\qquad\bullet\ (+a)\oplus(-b)=\begin{cases}\bigl(+(a-b)\bigr)&\text{si } a\ge b\\\bigl(-(b-a)\bigr)&\text{si } a\le b\end{cases}$

Il est long, mais vraisemblablement pas trop difficile, de démontrer que l'on a bien le résultat voulu à savoir que $\bigl(\mathbf{Z},\oplus, \pm0\bigr)$ est un groupe commutatif.

Ensuite on défini une multiplication $\otimes$ dans $\mathbf{Z}$ par

$\quad-\ \forall (x,y)\in\mathbf{Z}^2\ x\otimes y=y\otimes x$
$\quad-\ \forall (a,b)\in\mathbf{N}^2$
$\qquad\bullet\ (+a)\otimes(+b)=(+ab)$
$\qquad\bullet\ (+a)\otimes(-b)=(-ab)$
$\qquad\bullet\ (-a)\otimes(-b)=(+ab)$

Ce qui est sans doute ce qu'ignatus appelle « règle des signes ».

À partir de ces définitions on peut montrer que $\bigl(\mathbf{Z},\oplus,\otimes\bigr)$ est bien isomorphe à l'anneau $\mathbb Z$ usuel. Si on est patient et pas rebuté par l'étude de nombreux cas.
Et, en particulier, on peut montrer que la multiplication est distributive sur l'addition.

Après j'ai beaucoup de mal à voir ce que signifie « sémantique » et « syntaxique » pour toi.

Pour moi une démonstration est correcte quand elle est syntaxiquement correcte.

Un ps pour Dom :
si on considère $\Z$ uniquement comme un ensemble il me semble difficile de le distinguer de $\N$ ou $\Q$, par exemple.

Edit : modification de
$\quad-\ \forall x\in\mathbf{Z}\ x\oplus y=y\oplus x$
en
$\quad-\ \forall (x,y)\in\mathbf{Z}^2\ x\oplus y=y\oplus x$

ignatus · October 2019

Merci verdurin pour cet effort.

Je ne comprends ni ce qu'est une syntaxe, ni ce qu'est une sémantique. Par exemple, il se pourrait bien que le calcul des prédicats par exemple soit un modèle d'autre chose, les propositions formelles se révélant des interprétations. J'essaie en ce moment de comprendre le théorème de complétude, et ce qu'on appelle une déduction logique. J'aurais du le faire depuis longtemps, mais je n'en ai jamais eu la motivation.

ignatus.

verdurin · October 2019

Je dirais qu'avant d'étudier le « théorème de complétude » dont j'ignore tout, apprendre ce qu'est une déduction logique est indispensable pour quiconque enseigne les mathématiques.

Poirot · October 2019

@ignatus : tu devrais lire un cours de théorie des modèles avant de te lancer au hasard dans ces choses-là. Syntaxe = formules, sémantique = interprétation des formules. En logique du premier ordre, les deux se rejoignent au sens où une formule $\phi$ est démontrable à partir d'une théorie (famille de formules) $T$ si et seulement si dans tout modèle de $T$ (un "univers" qui interprète ton langage et dans lequel tous les éléments de $T$ sont vrais) $\phi$ est vraie, c'est le théorème de complétude.

Un exemple simple mais très parlant : on considère le langage $(e, *)$ de la théorie des groupes, où $e$ est un symbole de constante et $*$ un symbole d'opération binaire. La théorie des groupes est l'ensemble formé des trois formules suivantes : $$\forall x, \forall y, \forall z, (x*y)*z = x*(y*z)$$ $$\forall x, x*e=e*x=x$$ et $$\forall x, \exists y, x*y=y*x=e.$$
Un modèle de la théorie des groupes est... un groupe. C'est un ensemble $M$ possédant un élément $1$, noté $e^M$, l'interprétation du symbole $e$ dans $M$, et une fonction $\bullet : M \times M \rightarrow M$, notée $*^M$, l'interprétation de $*$ dans $M$, et tels que les trois formules ci-dessus, une fois interprétées dans $M$, sont vraies.

Puisqu'il existe des groupes qui ne sont pas abéliens, c'est-à-dire des modèles de la théorie des groupes tels que la formule $\forall x, \forall y, x*y=y*x$ n'est pas vraie, le sens facile du théorème de complétude nous dit que l'on ne peut pas démontrer cette formule à partir des trois formules de la théorie des groupes. Et comme il existe des groupes abéliens, on ne peut pas démontrer la négation de cette formule non plus. Dans l'autre sens, puisque dans tous les groupes, la formule $\forall x, (\forall y, y*x=x*y=y) \Rightarrow x=e$ est vraie, on en déduit que cette formule est démontrable à partir des axiomes de la théorie des groupes.

ignatus · October 2019

Merci Poirot pour cette explication.
Dans la théorie des anneaux, la distributivité de la loi "multiplication" sur la loi "addition" fait partie des axiomes de la théorie. Z est un modèle d'anneau dont la distributivité de la multiplication entraîne la règle des signes.
Il me semble que Foys avait montré qu'avec un peu moins que les axiomes de la théorie des anneaux, on pouvait démontrer la règle des signes.
Cela veut dire que c'est une loi logique dans le cadre de la théorie des anneaux que la distributivité entraîne la règle des signes. Foys a aussi exhibé un contre-exemple qui montre que la règle des signes peut être vraie, sans que la distributivité le soit.
Si l'on prend Z comme univers des noms de variables qui interviennent dans le contre-exemple, cela montre que dans un modèle de la théorie des anneaux, la règle des signes est vraie, mais pas la distributivité. Il est donc impossible, dans la théorie des anneaux, de démontrer que la règle des signes implique la distributivité.
Pourtant, il existe des constructions de Z pour lesquelles la règle des signes entraîne la distributivité. Cela veut donc dire que Z est un modèle pour plusieurs théories différentes, et que pour certaines de ces théories, il est possible que la distributivité soit démontrable à partir de la règle des signes.

ignatus.

ignatus · October 2019

Bonjour,

j'espère être arrivé à une bonne compréhension de ce problème autour de la règle des signes.
Il me semble à présent que ce que je disais à propos de l'architecture logique d'un modèle est complètement faux. Un modèle est un univers dans lequel un certain nombre de propositions sont vraies. On ne peut pas garder toutes ces propositions vraies et changer d'armature logique. La valeur de vérité des propositions dépend de l'architecture logique.
Ensuite, pendant longtemps je ne savais pas comment interpréter le fait qu'il y avait plusieurs constructions de Z. Est-ce-que ça voulait dire qu'il y avait plusieurs modèles de Z, ou que Z était un modèle de plusieurs théories ? En fait, c'est la deuxième option qui est juste. Z est un modèle de plusieurs théories, mais ces théories ne doivent pas être n'importe comment les unes par rapport aux autres, puisqu'elles ne doivent pas changer les valeurs de vérité des propositions dans Z.
C'est ainsi que je pense avoir finalement compris la signification du contre-exemple de Foys. Il insiste beaucoup sur sa preuve en COQ de la vérité du contre-exemple, et je ne comprenais pas pourquoi. COQ étant un logiciel de calcul formel, son utilisation démontrait que le contre-exemple de Foys est une vérité logique, c'est-à-dire que, quel que soit le modèle, il existe une application qui vérifie la règle des signes et pas la distributivité. Cela veut donc dire que dans une théorie du 1er ordre, il est impossible de démontrer la distributivité à partir de la règle des signes uniquement. Si donc il existe des constructions de Z qui donnent l'impression que la règle des signes implique la distributivité, elles ne peuvent être que de deux types : soit elles utilisent la règle des signes comme axiome, et il y a besoin d'un axiome indépendant pour pouvoir démontrer la distributivité, soit elles utilisent un système d'axiomes qui permet de dériver la règle des signes, et une propriété qui en est indépendante, et dont on se sert pour démontrer la distributivité. Lorsque dans une construction de Z, on pense avoir montré que la règle des signes implique la distributivité, si la preuve n'est pas fausse, c'est qu'on a utilisé un argument supplémentaire qui est indépendant de la règle des signes.
Conclusion: Foys avait raison, et j'avais tort. Qu'il y ait plusieurs constructions de Z ne change pas le fait qu'il est impossible de démontrer la distributivité à partir de la règle des signes toute seule.

ignatus.

Syntaxe et sémantique autour de Z

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 6