Modèles de PA

damien09
Modifié (November 2023) dans Fondements et Logique
Une question sans doute classique mais qui continue à me donner des insomnies. Quand on utilise le mot "ensemble" pour parler du "domaine" d'un modèle, de quoi s'agit-il vraiment ?
Exemple pris chez Patrick Dehornoy, s'agissant des modèles de PA.

Qu'entend-il par "sous-ensemble" ? (T'es à l'écoute, Patrick ?...). À ma connaissance, la "suite" 0, S0, SS0, SSS0... n'est pas un ensemble au sens de la théorie du même nom. Le modèle "standard" est-il alors vraiment une sous-structure de tout modèle de PA au sens de la définition correcte d'une sous-structure ? Ou faut-il se résoudre à entendre tout ça dans le cadre d'une théorie "naïve" des ensembles, une "théorie" des paquets de trucs  :) ?...
Merci par avance à tous.

Réponses

  • Alesha
    Modifié (November 2023)
    Bonjour
    Pour tout entier $p$, le singleton $\{ (S^p O)^{\mathfrak{M}} \}$ est un ensemble, non? Alors $\bigcup_{p \in \mathbb{N}} \{ (S^p O)^{\mathfrak{M}} \}$ est un ensemble.  
  • Foys
    Modifié (November 2023)
    Patrick Dehornoy est à fond platonicien et invoque toute la force de la théorie des ensembles pour faire de la théorie des modèles. Donc dans son exposé le mot ensemble désigne ... un ensemble et les résultats en question  sont des théorèmes de ZF ou ZFC.
    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$.
  • damien09
    Modifié (November 2023)
    Merci @Alesha, mais c'est quoi N dans p∈N ? Les successeurs de 0 ? Donc pas un ensemble. Il est impossible dans ZF de formaliser un prédicat Nat(x) dont l'extension serait les entiers "naturels". Omega, plus petit ordinal infini est bien un ensemble, mais il existe des éléments de cet ensemble qui ne sont pas de la forme SSS...S0. Ce ne sont pas des successeurs de 0. Les entiers "naturels" ne forment pas un sous-ensemble de omega.
    Merci @Foys, mais je persiste à ne pas comprendre comment on peut parler d'un sous-ensemble (au sens de ZF) s'agissant des successeurs de 0 (voir le texte et le schéma de Dehornoy).
  • Alesha
    Modifié (November 2023)
    @damien09: Si ça t'aide, tu peux supposer $\mathbb{N} = \omega$ (et supposer que tu fais des mathématiques dans un modèle de ZFC, même si rien ne t'y oblige).
    Qu'il y ait ou non des éléments de $\mathbb{N}$ qui ne s'écrivent pas $S...S 0$ ne change rien à l'affaire : un "entier standard" d'un modèle $\mathfrak{M}$ de PA sera un élément de $\mathfrak{M}$ qui s'écrit $(S^pO)^\mathfrak{M}$ avec $p \in \mathbb{N}$. 
  • Martial
    Modifié (November 2023)
    @damien09 : je crois comprendre qu'est-ce qui te chiffonne. (Attention, ce qui suit est aussi très platonicien). Il faut se placer à plusieurs "niveaux de conscience". Mettons que nous vivons dans un modèle de ZFC, donc en particulier nous avons à notre disposition un ensemble de tous les entiers naturels qu'on note $\omega$ et que j'appellerai $\mathbb{N}$ pour garder les mêmes notations que Patrick. Par ailleurs, nous avons sous les yeux un modèle non standard de Peano, disons $\mathbb{M}$. Pour nous, $\mathbb{N}$ est un ensemble. A chaque entier $n$ on peut associer un unique élément du modèle, soit $S^n(0)$ (avec des notations évidentes). Par remplacement on peut donc parler de l'ensemble $\mathbb{N}_\bullet = \{x: \exists n \in \N \mid x=S^n(0)\}$. (On peut aussi raisonner comme @Alesha).
    Là où ça coince c'est quand on se place du point de vue de l'habitant du modèle. Lui est incapable d'identifier la partie standard de son modèle, donc à son sens $\mathbb{N}_\bullet$ n'existe tout simplement pas, et a fortiori n'est pas un ensemble.
  • J'explique maintenant pourquoi l'habitant du modèle ne peut pas identifier sa partie standard. Pour simplifier, supposons maintenant que $\mathbb{M}$ est un modèle, non pas de Peano, mais de ZF(C). Donc l'habitant dispose de son $\omega$ à lui, qui est bien ordonné comme tout ordinal qui se respecte. S'il "voyait" $\mathbb{N}_\bullet$ comme un ensemble, il "verrait" aussi $X=\omega \setminus \mathbb{N}_\bullet$, qui est non vide puisque le modèle est non standard.  Soit $x$ le plus petit élément de $X$. $x$ n'est pas nul car $0$ est standard. Donc $x=y+1$ avec $y$ standard par minimalité de $x$. Mais alors $y+1$ est aussi standard, donc $x$ est standard, contradiction.
  • Médiat_Suprème
    Modifié (November 2023)
    Une autre façon de dire ce que Martial dit très bien dans son deuxième message : 
    S'il existait une formule $\varphi(x)$ du premier ordre identifiant les éléments standards de $\mathbb M$, cette formule serait vraie pour tous les éléments standards et fausse pour tous les éléments non standards, il est facile de démontrer par récurrence (axiome de PA) que $\forall x \in \mathbb M (\varphi(x))$ ce qui est contradictoire.
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Je me permets de développer l'argument de @Médiat_Suprème car j'ai rencontré ce résultat il y a quelques jours, en lisant un papier de Samuel Reid : "On Non-Standard Models of Peano Arithmetic and Tennenbaum's Theorem", 25 novembre 2013.
    Le théorème est le suivant : soit $\mathbb{M}$ un modèle non standard de Peano, et soit $\varphi$ une formule de PA. Si $\varphi(x)$ est vraie pour tout standard $x$, alors il existe au moins un non standard $y$ tel que $\varphi(y)$.
    Démonstration : supposons le contraire, i.e. $\varphi(x)$ est vraie pour tout standard $x$, et fausse pour tout non standard $x$.
    $\varphi(0)$ est vraie car $0$ est standard.
    Montrons maintenant que $\varphi(x) \Rightarrow \varphi(x+1)$ est vraie pour tout $x$. Pour cela on distingue 2 cas.
    Cas 1 : $x$ est standard. Par hypothèse $\varphi(x)$ et $\varphi(x+1)$ sont vraies, donc l'implication $\varphi(x) \Rightarrow \varphi(x+1)$ est vraie.
    Cas 2 : $x$ est non standard. Toujours par hypothèse, $\varphi(x)$ et $\varphi(x+1)$ sont fausses, donc l'implication $\varphi(x) \Rightarrow \varphi(x+1)$ est vraie.
    Le schéma d'induction de PA permet de conclure que $\forall x \varphi(x)$, ce qui contredit l'hypothèse.
  • Médiat_Suprème
    Modifié (November 2023)
    J'avoue que j'ai cité cet exemple surtout parce que c'est ma récurrence favorite (utiliser que $\varphi(x)$ est fausse pour démontrer qu'elle est vraie (pour tout $x$) me ravit).
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Au cas où tu aies le papier sous les yeux, voici l'histoire.
    Un pote m'écrit dimanche pour me parler du théorème 6 page 9. Il a deux questions :
    1) Comment traduire "overspill" ?
    2) La preuve est-elle juste ? Il a l'impression que l'auteur suppose un truc pour démontrer le même truc.
    Dans un premier temps, j'ai la même impression que lui, celle que Reid essaye de nous enfumer. Puis je pige le truc : la preuve est selon moi mal rédigée, mais il suffit de penser que "Faux $\Rightarrow$ Faux" est vraie. Du coup on rejoint ce que tu dis ci-dessus.
    Pour la traduction j'ai proposé "lemme de débordement" : tout ce qui est vrai des standards "déborde" sur au moins un non-standard. Tu en penses quoi ?
  • Débordement semble adéquat. Il y a longtemps j'avais utilisé : slides1may2004.pdf (uchicago.edu)
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Foys
    Modifié (November 2023)
     Soit $M$ un modèle de PA et $S$ une partie de $M$ telle que $0\in S$ et pour tout $x$ dans $M$, $x\in S$ si et seulement si $x+1\in S$. Soit $\Phi$ une formule de $PA$ dont $x$ est la seule variable libre et telle que pour tout $t\in S$, $M,e_t \vDash \Phi$ (où $e_t$ est l'environnement envoyant $x$ sur $t$; en théorie des modèles les formules sont évaluées d'après un environnement, i.e. une application des variables libres de la formule dans le domaine du modèle). Alors $M,\emptyset \vDash \left (\Phi(0) \wedge \forall x (\Phi \Rightarrow \Phi[x:= x+1])\right ) \Rightarrow \forall x \Phi $ puisque par hypothèse $M$ satisfait tout PA. Supposons qu'il n'existe aucun $u \in S$ tel que $M, e_u \vDash \Phi$. Alors pour tout $t\in S$, $\left ( M,e_t \vDash \Phi \right ) \Rightarrow \left ( M,e_{t+1} \vDash \Phi\right )$ (car faux implique faux comme dit ci-dessus) autrement dit $M,e_t \vDash \left (\Phi \Rightarrow \Phi[x:= x+1] \right )$. En outre, pour tout $u\in S$, $M,e_u \vDash \Phi$ et donc aussi, $M,e_u \vDash \Phi \Rightarrow \Phi[u:= u+1]$. Finalement pour tout $t\in M$, $M,e_t \vDash \Phi \Rightarrow \Phi[x:= x+1]$ et donc $M,\emptyset \vDash \forall x \Phi \Rightarrow \Phi[x:= x+1]$. On a $M,\emptyset \vDash \Phi[x:= 0]$ parce que $0$ (du modèle) est dans $S$. La conclusion suit (à savoir que $S$ est vide ce qui entraîne une contradiction si on a supposé que $S$ était un ensemble d'éléments non standards non vide de $M$).
    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$.
  • damien09
    Modifié (November 2023)
    Merci à tous. Je vais poursuivre mes méditations, non sans perdre de vue cette forte pensée de @Martial :
    Une des grosses lacunes de ZF : si elle est capable de nous parler d'entiers naturels, cette théorie est incapable de nous dire exactement ce que sont les entiers intuitifs. (Théorie des ensembles, ch.5).
    Dont acte !
  • Foys
    Modifié (November 2023)
    Personne n'est capable de dire ce que sont les entiers intuitifs et pire, plus la théorie est puissante et plus elle est capable de construire des modèles exotiques, notamment de Peano.
    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$.
  • Foys
    Modifié (November 2023)
    Pour prendre un exemple: ZFC démontre (à l'aide du théorème de Los) que pour tout ensemble ordonné $(X,\leq)$ il existe un modèle $(M,+,\times)$ de l'arithmétique de Peano et une fonction strictement croissante de $X$ dans $M$. $X$ peut très bien être $\R$ par exemple.
    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$.
  • Médiat_Suprème
    Modifié (November 2023)
    Rappelons "qu'il existe" $2^{\aleph_0}$ modèles dénombrables (non isomorphes, et si AP est consistante) de AP (démonstration facile), cela laisse la place pour l'exotisme  :)
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
Connectez-vous ou Inscrivez-vous pour répondre.