Comment le formalisme mathématique échappe-t-il au paradoxe du menteur ?

Homo Topi
Modifié (August 2023) dans Fondements et Logique
Le fameux "cette phrase est fausse". Si j'essaie de formaliser ça, j'ai l'impression que si $A$ est l'énoncé "cette phrase est fausse", alors en fait $A$ est l'énoncé "$A$ est faux" donc on aurait $A \Longleftrightarrow \neg A$. Ce qui est impossible en logique classique. Pourtant, quand on n'a pas des connaissances profondes en logique (ce qui est mon cas, j'ai les bases mais je ne suis pas logicien), on a quand même l'impression d'avoir fait les choses dans les règles et d'avoir abouti à une absurdité.
Je lisais sur Wikipédia que "cette phrase est fausse" n'est pas une "formule bien formée" et que c'est une "formule du métalangage". Pour moi, ça c'est du charabia pour l'instant. Cependant, quand j'essaie de formaliser "cette phrase est fausse", à part le $A \Longleftrightarrow \neg A$, je ne vois pas comment faire.
Donc voilà, j'aimerais comprendre un peu comment "formaliser proprement" (métalangage ou pas) le paradoxe du menteur en logique, et comprendre comment la logique mathématique fait pour y échapper (donc cette histoire de formule "bien formée").

Réponses

  • Le fond du problème est bien la notion de formule bien formée (on trouve souvent wff dans les textes anglais), c'est à dire une formule qui respecte les règles de construction des formules. Voir par exemple : Module IA - Logique, Session 1 (cnrs.fr), il y a des tonnes d'autres sites sur ce sujet
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Foys
    Modifié (August 2023)
    Les mathématiques -les formalismes dont on dispose aujourd'hui- n'offrent pas la garantie d'échapper au paradoxe du menteur. En effet si elles le pouvaient elles montreraient leur non contradiction et seraient contradictoires d'après le 2ième théorème d'incomplétude de Gödel.
    Ce qui se passe est la chose suivante.
    0°) Dans ces développements les nombres entiers sont utilisés pour encoder toutes sorte s d'informations, par exemple lorsqu'il est exprimé en base 4 (2,3 codant des espaces et des virgules), le nombre 310012112110131212100311 encode le fichier (1001 11 1101; 1 1 100; 11).
    Avec une règle d'encodage convenable un entier peut donc encoder une formule mathématique et/ou logique. On note $\lceil F \rceil$ le nombre qui encode la formule $F$.
    1°) Soit $(A_n)_{n\in \N}$ un ensemble dénombrables de propriétés mathématiques contenant toutes celles qui sont exprimables par une formule de logique du premier ordre. Par exemple $"p \in A_q"$ signifie "$p$ possède la propriété $A_q$".
    On suppose qu'il existe une fonction $n \mapsto n^*$ telle que pour tout entiers $\mathbf p, \mathbf n$ explicite (une chaîne de caractères en chiffres),  on peut démontrer que $\mathbf p \in A_{\mathbf n*}$ si et seulement si $\lceil \mathbf p \in A_{\mathbf p} \rceil \in A_{\mathbf n}$.  
    (Là je vends du rêve car la construction de $n\mapsto n^*$ s'appelle arithmétisation de la syntaxe et accapare des dizaines de pages des traités cependant on comprend que les règles de formation d'une expression mathématique et du remplacement d'une variable dans une propriété par un objet donné sont exprimables par des opérations élémentaires. La manipulation de binaires sur des parties de disque dur encodés comme au 0°) à travers des opérations arithmétiques ne pose pas de problème conceptuel mais de programmation.)
    2°) On suppose aussi qu'il existe une fonction $m \mapsto N m$ telle que pour tous nombres explicites $\mathbf n, \mathbf p$, on peut démontrer que $\mathbf p \in A_{N \mathbf n}$ si et seulement si $\mathbf p \notin A_{\mathbf n}$.
    On a les propriétés fondamentales suivantes.
    A ) LE THEOREME (FONDAMENTAL) DU POINT FIXE (conséquence de la seule propriété 1° ci-dessus. La preuve est entièrement constructive)
    Étant donné un nombre entier explicite $\mathbf n$, il existe un énoncé $E$ explicite tel qu'on peut prouver que $\lceil E \rceil \in A_{\mathbf n}$.
    En effet cet énoncé est $\mathbf n^* \in A_{\mathbf n^*}$. Il suffit d'appliquer ce qui a été dit : on a l'équivalence suivante qui est démontrable.
    $\mathbf n^* \in A_{\mathbf n^*}$ si et seulement si $\lceil \mathbf n^* \in A_{\mathbf n^*} \rceil \in A_{\mathbf n}$.
    Ça ne va pas plus loin que ça.
    B ) Corollaire. Aucune formule ne peut exprimer qu'une formule est fausse, sauf si les maths ambiantes sont contradictoires.
    Soit $\mathbf f$ un entier explicite tel qu'on puisse démontrer que  $\lceil \Phi \rceil \in A_{\mathbf f}$ si et seulement si $\neg \Phi$, pour tout énoncé $\Phi$. Alors en considérant un point fixe $F$ de $\mathbf f$ comme ci-dessus on a une preuve de $F \Leftrightarrow \neg F$ et les mathématiques sont contradictoires.
    Ca c'était pour le paradoxe du menteur !
    C ) On suppose 1°) et désormais 2°) du préambule. Aucune formule ne peut exprimer qu'une formule est vraie, sauf si les maths ambiantes sont contradictoires (Tarski).
    Soit $\mathbf v$ un entier explicite tel que pour tout énoncé $\Gamma$, on puisse démontrer que $\lceil \Gamma \rceil \in A_{\mathbf v} \Leftrightarrow \Gamma$. On applique B ) à $N\mathbf v$.
    D ) S'il existe un entier $\mathbf p$ explicite tel que pour tout énoncé $E$, $\lceil E \rceil \in A_{\mathbf p} $ si et seulement si $E$ est prouvable alors il  y a un énoncé équivalent à sa non prouvabilité.
    Cet énoncé est obtenu en appliquant le théorème du point fixe à $N\mathbf p$. Kurt Gödel avait démontré que $\mathbf p$ existe vraiment pour l'arithmétique. C'est le premier théorème d'incomplétude de Gödel.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Ben314159
    Modifié (August 2023)
    Salut,
    Si on ne veut pas rentrer dans du trop compliqué, le problème, c'est que la phrase parle d'elle même (auto référence) ce qui pose évidement des problème vu que pour connaitre le statut vrai/faux de la phrase, il faut précédemment connaitre . . . son statut.
    Pour faire une analogie, c'est plus ou moins la même chose que quand tu veut définir un réel X en posant X=... : si le X apparâit aussi après le symbole =, il ne s'agit plus d'une définition, mais d'une équation.
    Et si tu regarde la phrase "je suis fausse" comme une équation $P\Leftrightarrow\neg P$, c'est comme si tu avait l'équation X=X+1 : le bilan, ce n'est pas "une contradiction", mais simplement qu'il n'y a pas de solutions à l'équation.
  • Cyrano
    Modifié (August 2023)
    Je ne vois pas en quoi la formule $P \Leftrightarrow \neg P$ serait mal formée.
    Si on prend la logique propositionnelle classique, cette formule est bien formée et on peut calculer sa table de vérité.
  • @Cyrano la question est plutôt si cette formule est une bonne formalisation du paradoxe du menteur (et/ou s'il se laisse bien formaliser). J'ai envie de dire que non : ce qui indiquerait aussi que le paradoxe du menteur ne se laisse pas proprement exprimer comme une formule, cf le concept de formule bien formée.
    J'ai de la lecture en tout cas. Merci :)
  • Foys
    Modifié (August 2023)
    Cyrano a dit :
    Je ne vois pas en quoi la formule $P \Leftrightarrow \neg P$ serait mal formée.
    Si on prend la logique propositionnelle classique, cette formule est bien formée et on peut calculer sa table de vérité.
    La logique ou les maths n'ont jamais fait figurer une quelconque obligation de n'écrire que des énoncés vrais (peu importe ce que ça veut dire) ou même non immédiatement réfutables (sinon comment vous faites un raisonnement par l'absurde ou même par contraposition). Pour tout énoncé "bien formé" $X$, $X \Leftrightarrow \neg X$ est bien formé. En maths écrire est différent d'affirmer.
    Ensuite, les autoréférences sont possibles en maths puisqu'il est possible de parler de l'énoncé $x$ écrit par le programme informatique $y$.
    L'énoncé suivant parle de lui-même et se qualifie de mensonge:
    On écrit un mensonge lorsqu'on recopie l'énoncé entre guillemets suivant sans le mettre entre guillemets une première fois, puis qu'on met un deux-points, puis qu'on va à la ligne, puis qu'on écrit l'énoncé entre guillemets, puis qu'on met un point final:
    "On écrit un mensonge lorsqu'on recopie l'énoncé entre guillemets suivant sans le mettre entre guillemets une première fois, puis qu'on met un deux-points, puis qu'on va à la ligne, puis qu'on écrit l'énoncé entre guillemets, puis qu'on met un point final".
    Le mot mensonge peut-être facilement remplacé par n'importe quoi. La concrétisation de ce phénomène amusant existe en informatique, est à la base de la récursion, et possède des réalisations ludiques appelées "quines". Les théorèmes d'indécidabilité en sont la contrepartie en mathématiques.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • GG
    GG
    Modifié (August 2023)
    Excuse-moi Foys, mais je ne trouve pas ton argument très convaincant.

    La question n'est pas de savoir si l'énoncé $X \Leftrightarrow \neg X$ est bien formé ou non, bien sûr qu'il l'est !
    La question est de donner une valeur de vérité à $X$ qui rendrait l'énoncé vrai, ce qui n'est pas possible.

    Justifier l'autoréférence en maths par un appel à l'informatique ne fait que déplacer le problème.
    D'ailleurs, l'autoréférence est-elle vraiment possible ?
    Pour un esprit un peu faible comme le mien, définir quelque chose, quoi que ce soit, dans n'importe quel domaine, c'est fixer les limites, la nature, ou la signification de cette chose en fonction d'autres choses, elles-mêmes déjà définies.

    Dire que la définition de la  factorielle $n! = n(n-1)!$ est autoréférente est un trompe-l’œil. Elle n'est possible que parce que les applications de $\mathbf N $ dans $\mathbf N$ sont déjà définies et que l'on a démontré qu'il en existe exactement une qui vérifie une certaine relation, elle-même déjà définie.

    Appeler $P$ l'énoncé "$P$ est faux" n'a tout simplement pas de sens.
  • gerard0
    Modifié (August 2023)
    Bien vu, GG !
    Partout en maths, dire "j'appelle x le nombre x+1" est considéré comme une absurdité, la lettre x étant utilisée pour deux usages différents. Il n'y a pas de raison d'accepter de déroger à cette règle élémentaire de clarté.
    Cordialement.
  • Médiat_Suprème
    Modifié (August 2023)
    GG a dit :
    Dire que la définition de la  factorielle $n! = n(n-1)!$ est autoréférente est un trompe-l’œil. Elle n'est possible que parce que les applications de $\mathbf N $ dans $\mathbf N$ sont déjà définies et que l'on a démontré qu'il en existe exactement une qui vérifie une certaine relation, elle-même déjà définie.
    Appeler $P$ l'énoncé "$P$ est faux" n'a tout simplement pas de sens.
    Je ne comprends pas ce que vous voulez dire dans votre première phrase, pour m'éclairer, pourriez-vous me préciser le statut de la définition  de $+$ (comme vous l'avez fait pour la factorielle) :
     $ (\forall x ,\ (x + 0 = x)) \wedge (\forall x,\ \forall y, \ ((x + s(y) = s(x + y)))$

    Pour votre deuxième phrase, n'est-ce pas exactement dire que $P$ est mal formée ?
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • @Médiat_Suprème, à mon tour de ne pas comprendre vos questions !
    Je me plaçais dans un contexte de théorie des ensembles, pas d'axiomatique de Peano. Pour définir une nouvelle fonction sur $\mathbf N$ comme la factorielle (ou sur $\mathbf N ^2 $ comme l'addition), je ne peux pas me contenter simplement d'introduire un nouveau symbole et d'écrire une relation de récurrence qui comporte une autoréférence. Je dois d'abord démontrer l'existence et l'unicité d'une telle fonction, et ensuite seulement la désigner par ce symbole.

    Dans votre question, "n'est-ce pas exactement dire que $P$ est mal formée ?", qu'entendez-vous par  $P$ ?
  • N'y a-t-il pas un théorème qui dit grosso modo que toute définition "par récurrence" peut-être "dé-recursivée" ?
  • @Cyrano, oui bien sûr. Quand je disais "je dois d'abord démontrer l'existence  et l'unicité d'une telle fonction" , je faisais allusion à ce théorème !
  • @GG : Ce n'est pas le cas de l'addition, on ne démontre pas son existence avant de la définir.

    Quant à $P$, c'est celui de votre message.
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • "Ce n'est pas le cas de l'addition, on ne démontre pas son existence avant de la définir".

    Ça dépend. Si je définis les entiers naturels comme ordinaux finis, je peux définir leur somme comme union disjointe, ou alors par récurrence, auquel cas ...

    "Quant à $P$, c'est celui de votre message".

    Qui dit précisément qu'il n'a pas de définition ! :)


  • Je ne comprends toujours pas votre réticence vis-à-vis des définitions récurrentes.

    Pour $P$, nous sommes d'accord, il me semble, une formule qui n'a pas de sens est mal formée (et réciproquement)
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Homo Topi
    Modifié (August 2023)
    gerard0 a dit :
    Bien vu, GG !
    Partout en maths, dire "j'appelle x le nombre x+1" est considéré comme une absurdité, la lettre x étant utilisée pour deux usages différents. Il n'y a pas de raison d'accepter de déroger à cette règle élémentaire de clarté.
    Cordialement.
    C'est un peu comme ça que j'interprète les histoires de formules bien fondées. Pour dire "cette phrase est fausse" mathématiquement, il faut faire de "cette phrase" une variable $P$. Donc on a juste l'énoncé "non-$P$" (la phrase $P$ est fausse), mais on ne peut pas dire que "la phrase $P$ est fausse" "soit" $P$. L'autoréférencement "de non-$P$ par $P$" est impossible quand on quantifie les choses proprement... je le comprends bien, mais ce qui serait intéressant "à mon niveau" serait de comprendre comment ça a été axiomatisé de sorte à fonctionner comme ça. On m'a bien donné de la lecture, il faut que je me prenne le temps.
    Médiat_Suprème a dit :
    Pour votre deuxième phrase, n'est-ce pas exactement dire que $P$ est mal formée ?
    En tout cas j'ai l'impression qu'on est sur la bonne voie.
    On pourrait appeler $P(x)$ le prédicat $\neg x$ où $x$ est un autre prédicat, j'imagine que tout ce qu'on dit ici c'est que $P(P)$ n'a "pas de définition" ? Je suppose que c'est puisque "$P$" tout seul ici n'a pas été défini, c'est "$P(\cdot)$".
    Il serait fascinant de définir quelles "formules en français" ne sont pas bien formables mathématiquement.
  • Ben314159
    Modifié (August 2023)
    Homo Topi a dit :Il serait fascinant de définir quelles "formules en français" ne sont pas bien formables mathématiquement.
    Je ne sais pas s'il est bien facile de définir de définir quelles sont les phrases bien formée en Français (vu l’ambiguïté qu'il peut y avoir concernant de nombreux mots), mais parmi celle qui ne sont "pas bien formée", un grand classique (que j'aime bien), c'est celle là : 
    Quelle est le plus petit entier que l'on ne puisse pas définir sans ambiguïté par une phrase de moins de cinquante mots ?
  • GG
    GG
    Modifié (August 2023)
    "Je ne comprends toujours pas votre réticence vis-à-vis des définitions récurrentes".
    Vos interventions m'ont fait comprendre que la récurrence n'est pas un bon exemple d'autoréférence. Ce n'est pas un exemple du tout, dans la mesure où  la fonction n'est pas définie d'un bloc, mais par éléments, chacun étant bien défini en fonction d'un autre.  Mais je me rends compte maintenant qu'étant donné un ensemble $A$ quelconque bien défini et une application $g$ de $A$ dans $A$, un point fixe $x$ de $g$ est bien défini bien qu'il n'entre pas dans le cadre que je me faisais de la définition d'une définition.
    En conséquence de quoi, je bats ma coulpe et retire tout ce que j'ai dit jusqu'à présent ! :)
  • Ok, pas de problème :smiley:
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Foys
    Modifié (August 2023)
    @GG La fonction $p,q\in \N \mapsto 2^p (2q+1)$ est une injection (édité) de $\N^2$ dans $\N$, telle que pour tous entiers $p,q$, $p< \langle p,q\rangle$ et $q < \langle p, q\rangle$, la fonction $p,q \mapsto 1+p + \sum_{k=0}^{p+q} k = 1+p +\frac {(p+q) (p+q+1)}2$ aussi , quoique ça demande un peu plus de travail. Dans la suite on désignera par $p,q \mapsto \langle p,q\rangle$ une de ces deux bijections au choix et on conviendra que $\langle a,b,c\rangle$ abrège $\langle a, \langle  b,c \rangle\rangle$, et plus généralement que $\langle x_n, x_{n-1}, ... x_1\rangle$ abrège $\langle x_n, \langle x_{n-1}, ... , x_1\rangle\rangle$ pour tout entier $n$ et tous objets $x_1,...,x_n$.

    On convient que les symboles suivants désignent en fait des nombres entiers: on indique l'entier désigné par le symbole ci-dessous:
    $\boxed {terme}:=0$; $\boxed {formule} := 1$; $\boxed{variable}:=2$; $\boxed{classe}:= 3$, $\boxed{\in}:= 4$; $\boxed{=}:=5$; $\boxed{\neg}:= 6$; $\boxed{\wedge}:=7; \boxed{\vee}:= 8$; $\boxed{\Rightarrow}:= 9$; $\boxed{\Leftrightarrow}:= 10$; $\boxed{\forall}:= 11$; $\boxed{\exists}:=12$.

    On appelle "ensemble des expressions formelles" le plus petit sous-ensemble $\mathcal E$ de $\N$ qui a les propriétés suivantes (c'est-à-dire comme d'habitude que c'est l'intersection de toutes les parties qui ont ces propriétés):

    1°) Pour tout entier $n$, $\langle \boxed{terme},\boxed{variable}, n\rangle$ appartient à $\mathcal E$
    2°) Pour tous entiers $n,f$, si $\langle \boxed{formule}, f\rangle $ appartient à $ \mathcal E$ alors $\langle \boxed{terme}, \boxed{classe},n, \boxed{formule},f\rangle $ appartient à $ \mathcal E$
    3°) Pour tous entiers $s,t$, si $\langle \boxed{terme},s\rangle$ et $\langle \boxed{terme}, t \rangle$ appartiennent à $\mathcal E$, alors pour tout $r\in \{\boxed{\in}, \boxed =\}$, $\langle \boxed{formule}, r, \langle\boxed{terme}, s \rangle, \langle\boxed{terme},t \rangle \rangle \in \mathcal E$
    4°) Pour tout entier $f$, si $\langle \boxed{formule}, f\rangle$ est dans $\mathcal E$, alors $\langle \boxed{formule}, \boxed{\neg}, \boxed{formule}, f\rangle$ appartient à $\mathcal E$
    5°) Pour tous entiers $a,b$, si $\langle \boxed{formule}, a\rangle$ et $\langle \boxed{formule}, b\rangle$ appartiennent à $\mathcal E$ alors pour tout $c\in  \{\boxed{\wedge}, \boxed{\vee}, \boxed{\Rightarrow}, \boxed{\Leftrightarrow}\}$,
    $\langle \boxed{formule}, c , \langle \boxed{formule},a\rangle, \langle \boxed{formule}, b\rangle\rangle$
    6°) Pour tous entiers $n,f$ si $\langle \boxed{formule}, f\rangle$  appartient à $\mathcal E$ alors pour tout $q\in \{\boxed{\forall}, \boxed{\exists}\}$, $\langle \boxed{formule}, q, \boxed{formule}, f\rangle$ appartient à $\mathcal E$.

    Les éléments de $\mathcal E$ de la forme $\langle 1,n\rangle $ (c'est-à-dire $\langle \boxed{formule},  n \rangle$) s'appellent des "formules" et ceux de la forme $\langle 0,n \rangle$ (c'est-à-dire $\langle \boxed{terme}, n\rangle$) s'appellent de "termes"

    Tous les énoncés de théorie des ensembles peuvent s'écrire rapidement avec des variables, $\in, =$, des connecteurs logiques, des quantificateurs et des écritures du type "$\{x \mid P\}$"  (que nous appellerons plus bas des "écritures de classe") où $x$ est une variable et $P$ un énoncé.
    Par exemple, "$x \neq x$" est une abréviation de "$\neg (x = x)$", $\emptyset$ est une abréviation de $\{x \mid x \neq x\}$, $\mathcal P (E)$ est une abréviation de $\{x \mid \forall y, y \in x \Rightarrow y \in E\}$, $\bigcap F$ est une abréviation de $\{x \mid \forall y, y \in F \Rightarrow x \in y\}$, $\{p,q\}$ est une abréviation de $\{x \mid x = p \vee x = q\}$, $\{r\}$ est une abréviation de $\{r,r\}$, $a \cup b$ est une abréviation de $\{x  \mid x\in a \vee x \in b\}$, $\{x \in A \mid P\}$ est une abréviation de $\{x \mid x \in A \wedge P\}$ et enfin $\N$ est une abréviation de $\bigcap \{y \mid \emptyset \in y \wedge \forall n, n \in y \Rightarrow n \cup \{n\} \in y\}$.
    (cf Takeuti et Zaring: axiomatic set theory).

    On donne ci-dessous une méta-traduction (appelée numérotation de Gödel) des formules, variables et écritures de classes des mathématiques en nombres entiers.

    Les variables sont des symboles $\mathbf x_n$ avec $n$ entier; par exemple les lettres $a,b,c,d,e,f...,x,y,z$ sont des écritures plus agréables de $\mathbf x_0, \mathbf x_1, \mathbf x_2, ... \mathbf x_{24}, \mathbf x_{25}$.

    Etant donnée une variable $\bf x_n$, on pose $\lceil \mathbf x_{\mathbf n} \rceil := \langle \boxed{terme}, \boxed{variable}, \mathbf n \rangle$.
    Etant donné une formule $F$ telle que $\lceil F \rceil$ est défini, et $\bf x_n$ une variable, on pose $\lceil \{\mathbf x_{\mathbf n} \mid F\}\rceil:= \langle \boxed{terme}, \boxed{classe}, \mathbf n, \boxed{formule}, \lceil F \rceil \rangle$. Ensuite on complète la définition par induction de $\lceil \cdot \rceil$ en posant:
    (i) si $\mathbf u$, $\mathbf v$ sont des variables ou des écritures de classe alors $\lceil \mathbf u \in \mathbf v \rceil:= \langle \boxed{formule}, \boxed{\in}, \lceil \mathbf u\rceil, \lceil \mathbf v\rceil\rangle$ et $\lceil \mathbf u = \mathbf v \rceil:= \langle \boxed{formule}, \boxed{=}, \lceil \mathbf u\rceil, \lceil \mathbf v\rceil\rangle$;
    (ii) si $F$ est une formule, $\lceil \neg F \rceil := \langle \boxed{formule}, \boxed{\neg},\lceil F \rceil \rangle$
    (iii) si $A,B$ sont deux formules et $\mathbf s$ l'un des symboles $\wedge, \vee, \Rightarrow, \Leftrightarrow$ alors
    $\lceil A \mathbf s B \rceil:= \langle \boxed{formule}, \boxed{\mathbf s}, \lceil A \rceil, \lceil B \rceil\rangle$;
    (iv) si $\mathbf q$ est l'un des symboles $\forall, \exists$, $\bf x_n$ une variable et $G$ une formule,
    $\lceil   \exists \mathbf x_{\mathbf n} G \rceil := \langle \boxed{formule}, \boxed{\mathbf q}, \lceil G \rceil\rangle$.

    Ainsi on peut énoncer en théorie des ensembles, des propriétés de formules, par exemple si $P$ est une formule du premier ordre avec une variable libre $x$, pour tout autre formule $Q$ cela a un sens de parler de $P[x:= \lceil Q \rceil]$ ("le numéro de Gödel de $Q$ a la propriété $P(x)"$).

    Le (méta) théorème de point fixe affirme que pour toute formule $P$ ayant une variable libre $x$, il existe un énoncé $E$ (explicite même si gigantesque) tel que $E \Leftrightarrow P[x:= \lceil  E\rceil]$ est prouvable. $E$ parle alors de lui-même et dit qu'il a la propriété $P(x)$. C'est en ce sens que l'auto-référence est possible.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Merci Foys, je vais regarder ça ... à tête reposée !
  • GG
    GG
    Modifié (August 2023)
    @Foys, juste un détail  :  1ère ligne, ... bijection de $\mathbf N ^2$ dans $\mathbf N$, c'est sans doute ... injection .. , ou alors mieux, bijection de $\mathbf N^2$ sur $\mathbf N ^ *$ ?
    Par ailleurs, n'est-ce pas gênant qu'un même entier soit l'image de plusieurs suites, par ex. $<0, 2, 0> = <0, 4> = 9$, etc.  ?
  • Foys
    Modifié (August 2023)
    @GG oui bien sûr qu'il s'agit d'une injection je viens de corriger ça. L'usage abondant d'étiquettes ($\boxed{formule}$, $\boxed{classe}$ etc, bref les entiers de $0$ à $12$) est justement fait pour qu'il y ait un lemme de lecture unique (pour tous entiers $p \leq q$ et tous entiers $x_1,..,x_p,y_1,...,y_q$, l'égalté $\langle x_1,...,x_p\rangle = \langle y_1,...,y_q\rangle$ entraîne $x_k = y_k$ pour tout $k<p$).
    Le fait que $\max \{p, q\} < \langle p,q\rangle$ garantit quant à lui que toute expression est (en tant qu'entier) toujours strictement plus grande que toutes ses sous-expressions, ouvrant la possibilité de raisonnements par récurrence naturels.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • OK, merci.
  • Je pense que notre façon de faire des mathématiques est justement faite exprès pour interdire des phrases « problématiques » comme le paradoxe du menteur ; quand on dit que la phrase « cette phrase est fausse » est « mal formée », on peut entendre que c’est une phrase dégénérée à laquelle il ne faudrait pas s’intéresser, et je pense qu’au contraire, c’est une phrase beaucoup plus intéressante que nos trivialités telles que le théorème de Perelman.
  • Bonjour, selon moi-même  écrire "cette phrase est fausse" n'est pas une affirmation ou sa négation la phrase existe et est syntaxiquement bien formée (sujet verbe complément). Faites cette expérience, demandez à ChatGPT une recette avec une dameuse!
    Les mathématiques ne sont pas vraies, elles sont commodes.
    Henri Poincaré
  • Une grosse différence entre langage formel et langage naturel est qu'une "phrase" bien formée dans le premier cas a du sens (mathématiques) alors qu'en langage naturel, ce n'est pas le cas : le chat pleut des chiens (sujet, verbe, complément, et pourtant ...), certes pleuvoir est défectif, mais "les cheveux du révolver sont blancs" est grammaticalement correct (spécial dédicace à A. Breton) mais n'a toujours pas de sens
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Lirone93
    Modifié (October 2023)
    N'a pas toujours de sens univoque, oui. Dans le sens, où le langage naturel accorde toujours en partie un rôle à l'interprétatif.
    Sinon, par exemple, la poésie n'existerait pas.
    « je sais que la question de départ est bizarre de la part d'un professeur certifié ».
  • Médiat_Suprème
    Modifié (October 2023)
    Ce n'est pas pour rien que j'ai cité A. Breton  ;)

    Et il est possible d'en trouver plein, par exemple, j'aime bien la phrase de Raffarin : "La guerre en Iraq n'est plus inexorable", qui est bien formée, mais ne devrait pas être formée.
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Eh ben, ce fil !
    Je pense que la difficulté réside dans le fait de convaincre les gens (pourrai-je dire : démontrer) que telle ou telle formule en français n'est pas "matématiquement bien formée". Puisqu'une formule mal formée est justement mal formée, on ne peut pas l'écrire formellement... donc comment apprendre à différencier les formules bien et mal formées ?
Connectez-vous ou Inscrivez-vous pour répondre.