Modèles de PA, Extensions de N

Arthas

Bonjour
Généralement, quand on parle de $\N$, on parle du $\N$ défini dans $ZF$ avec les cardinaux. Je me poses plusieurs questions :
1) Tous les $\N$ définis dans $ZF$ sont ils isomorphes (donc standards) ?
2) Si $\N'$ est un modèle non standard de l'arithmétique ( $PA$ ), peut il être non dénombrable ?
3) Comment montre t'on que $\N$ s'injecte dans tout modèle de $PA$ ?
4) On construit $\Z$, puis $\R$ dans $ZF$ en quotientant $\N$ puis $\Q$, le quotientage est une opération bien définie dans $ZF$. Je me demandais si on pouvait construire de manière similaire ces objets à partir d'un modèle quelconque $M$ de $PA$, donc en sortant du cadre de $ZF$.
Merci, Arthas

GG

1) oui ... c'est la moindre des choses

jean-c_rien

"1) Tous les $ \mathbb{N}$ définis dans $ ZF$ sont-ils isomorphes (donc standards) ? "
Pour un modèle de ZF donné oui, sinon pas forcément.
"2) Si $ \mathbb{N}'$ est un modèle non standard de l'arithmétique ( $ PA$ ), peut-il être non dénombrable ?"
Super bonne question. Par définition, dénombrable veut dire en bijection avec N, donc... Mais si tu considère le mot dénombrable dans le sens de "en bijection avec notre N", ce qui à un sens si on sort du cadre de ZF (par exemple dans la théorie des modèles en étudiant des modèles de PA, mais le problème c'est qu'un modèle non-standard intéréssant se devrait de ne pas être un ensemble mais une classe propre), alors "notre" N est bien le plus petit.
"3) Comment montre t'on que $ \mathbb{N}$ s'injecte dans tout modèle de $ PA$ ?"
Par récurrence! Mais attention, le problème c'est que la représentation que nous avons de N est beaucoup plus précise que la description qu'on en donne formellement, donc si tu espère trouver une démonstration formelle, ça va se gâter.
"4) On construit $ \mathbb{Z}$, puis $ \mathbb{R}$ dans $ ZF$ en quotientant $ \mathbb{N}$ puis $ \mathbb{Q}$, le quotientage est une opération bien définie dans $ ZF$. Je me demandais si on pouvait construire de manière similaire ces objets à partir d'un modèle quelconque $ M$ de $ PA$, donc en sortant du cadre de $ ZF$. "
On peut. La théorie des catègorie fait ça très proprement. Sauf que si on y regarde de près ça revient à étudier des modèles de ZF, alors je te laisse choisir ta réponse.

Arthas

Bonjour
$\N$ dépend donc du modèle de $ZF$ utilisé ?
Si deux modèles de $PA$ définis dans deux modèles de $ZF$ différents ne sont pas isomorphes, alors comment définir la standardité ?
Surtout qu'on ne peut pas connaitre de modèle de $ZF$, donc on ne peut pas prendre un modèle de $ZF$ "de référence" pour la standardité.
Donc un modèle de $PA$ générer dans un modèle de $ZF$ ne devrait pas dépendre de ce modèle (à un isomorphisme près), non ?
Arthas

Arthas

Pour le point 4), est ce que ces objets ont encore les propriétés caractéristiques qu'ils ont dans $ZF$, par exemple pour $\R$ : le seul corps archimédien abélien complet. Est ce que $\Q$ est toujours défini comme le corps des fractions de $\Z$. Ou avez vous un lien ?
Je me pose une question : 5) peut il exister une bijection (intuitive, qui sont celles utilisés dans la théorie des modèles par les isomorphismes) entre un ensemble (dans le sens élément d'un modèle de $ZF$) et une classe propre ?
Est ce non parce que sinon il existe un modèle de $ZF$ isomorphe au premier contenant cette classe propre ? Mais cela reste à démontrer.
Merci, Arthas
note : les éléments entre paranthèses sont des interpétations de ma part, peut être erronées.

@l

Salut,

1) soit $\mathcal{M}$ un modèle de $ZF$; dans $\mathcal{M}$ on définit un unique ensemble-objet qu'on appellera les entiers naturels de $\mathcal{M}$ et qu'on notera $\N_{\mathcal{M}}$: c'est le plus petit ordinal infini de $\mathcal{M}$.
Maintenant soit $\mathcal{N}$ un autre modèle de $ZF$ et $\N_{\mathcal{N}}$ son ensemble-objet des entiers naturels.

Il n'y a aucune raison pour que $\N_{\mathcal{M}}$ et $\N_{\mathcal{N}}$ soient isomorphes. Même pire, ces $2$ ensembles-objets, qui sont aussi des ensembles 'intuitifs' peuvent de cardinal (à notre niveau) différent...

Début de démo: Soit $L$ la réunion du langage de la théorie des ensembles, $\{\epsilon\}$ et d'un ensemble $E$ de constantes ($E$ est quelconque); soit $T$ la théorie dans $L$ égale à la réunion de $ZF$ et du schéma d'axiomes suivant:

(on note $F[X]$ la formule dans $ZF$ qui définit le plus ordinal infini, donc l'ensemble-objet des entiers naturels)

$$F[a]$$
et
$$b\neq c$$

avec $(a,b,c)\in E^3$ et $b\neq c$

La théorie $T$ est finiment consistante donc consistante. On construit ainsi des modèles de $ZF$ avec des {\bf ensemble-objets $\N$} de cardinal {\bf intuitif} quelconque.

2) Pour les mêmes raisons, il existe des modèles de $PA$ non dénombrables. En fait le théorème de Löwenheim-Skolem affirme que si $L$ est un langage de cardinal $C$ et si $T$ est une théorie dans $L$, alors pour tout cardinal $\Gamma$ plus grand ou égal à $C$, $T$ possède un modèle de cardinal $\Gamma$.

3) Soit $\mathcal{N}$ un modèle de $PA$, si $x\in \mathcal{N}$, $x+1$ (le successeur de $x$) est dans $\mathcal{N}$. Ainsi on pose $\phi$ l'application qui va de $\N$ dans $\mathcal{N}$ telle que:

$\phi(n)$ désigne le $n$-ième successeur de $0$

$\phi$ est un plongement de $\N$ dans $\mathcal{N}$.

4) Tout d'abord, on ne sort pas du cadre de $ZF$. Effectivement, on peut faire de telles opérations. Soit $\mathcal{N}$ un modèle de $PA$,

- il n'y a pas de problème jusqu'à l'équivalent de $\Q$, qu'on noetra $\mathcal{Q}$: toutes les opérations sont algébriques.

- ensuite pour passer à l'équivalent de $\R$, on utilise le fait que $\mathcal{Q}$ est un espace uniforme pour la topologie de l'ordre; il existe ainsi un complété de Cauchy, noté $\mathcal{R}$ qui sera l'analogie de $\R$.
$\mathcal{R}$ est un corps réel-clos. On peut ensuite conitnuer avec l'analogie de $\C$.
Ces ensembles sont très étudiés en théorie de l'aritmétique non-standard.

@l

Arthas

Merci @l pour des réponses toujours intéressantes.
Il y a pas mal de notions que je ne connais pas ou qui demandent réflexion, donc je vais y travailler pendant quelques jours.
Arthas

Arthas

Je vais essayer de faire le point.
Un modèle non standard de $PA$ est donc un modèle qui n'est pas une structure de Dedekind Peano, donc par exemple, dès que le modèle est une classe propre.
Le théorème de Löwenheim-Skolem est impressionnant, je comprends l'importance de l'axiome du choix dans la théorie des modèles à présent.
(je suppose qu'on peut montrer que tout ensemble intuitif admet un cardinal intuitif d'une manière analogue à celle de $ZFC$)
On a besoin du symbole d'appartenance pour la formule $F[x]$.
Le reste est encore assez obscur.
Pour montrer que $T$ est finement consistante, il faut montrer qu'aucun des schémas d'axiomes n'est en contradiction avec les axiomes de $ZF$ et entre eux ?
Donc $T$ admet un modèle, qui est également un modèle de $ZF$.
Mais je ne comprends pas comment on en déduit que le cardinal de l'ensemble objet peut être quelconque (même fini ?).
Merci, Arthas

@l

Salut,

tout d'abord, je ne sais pas ce qu'est une structure de Dedekind Peano; pourrais-tu m'en donner la définition?
Ensuite, un modèle ne peut pas être une classe propre (par définition, c'est un ensemble)

"(je suppose qu'on peut montrer que tout ensemble intuitif admet un cardinal intuitif d'une manière analogue à celle de $ ZFC$)"

Je ne comprends pas cette remarque. Que voulais-tu dire par là?

"On a besoin du symbole d'appartenance pour la formule $ F[x]$."

Oui, et c'est l'unique symbole dont on a besoin.

"Pour montrer que $ T$ est finement consistante, il faut montrer qu'aucun des schémas d'axiomes n'est en contradiction avec les axiomes de $ ZF$ et entre eux ?"

Une théorie est finiment consistante si toutes ses parties finies sont consistantes. Dans le cas présent, la théorie $T$ est finiment consistante, car dans une morceau fini de $T$, on utilise uniquement un nombre fini de constantes. Or les 2 seules choses qu'on demande à ces constantes, c'est de satisfaire $F[X]$, donc d'avoir une interprétation dans l'ensemble-objet $\N$ et ensuite d'avoir une interprétation différente à partir du moment où elles sont différentes (les constantes).
Je dis que c'est facile à réaliser. Par exemple, le bout fini de $T$ donnée par $\{F[a], F,F[c], a\neq b, a\neq c, b\neq c\}$ est consistant, en prenant un modèle de $ZF$, dans lequel, par exemple, $a$ est interprété par $0$, $b$ par $1$, $c$ par $2$.
Ou alors, autre exemple, $a$ est interprété par $22203$, $b$ par $524$ et $c$ par $1289$....

Ensuite, comme $T$ est consistante, il existe un modèle $\mathcal{M}$ de $T$. Or par construction, $\N_{\mathcal{M}}$ contient au moins autant d'éléments que de constantes. Donc le cardinal intuitif de $\N_{\mathcal{M}}$ est supérieur ou égal à celui de $E$...

@l

Arthas

Bonjour
C'est le terme modèle "standard" (et non standard) de l'arithmétique qui m'intrigue.
Je n'ai toujours pas trouvé de définition.

Une structure de Dedekind-Peano est un triplet $(E,0,s)$ où $E$ est un ensemble, $0$ une constante et $s$ une fonction, vérifiant :
1) $E$ est un ensemble, $0\in E$, $s$ application de $E$ dans $E$
2) $0\notin s(E)$
3) $s$ injective
4) Tout sous-ensemble $F$ de $E$ contenant $0$ et stable par $s$ est égal à $E$.
Par exemple, dans un modèle $M$ de $ZF$, $(\N,\emptyset,s)$ où $\N$ désigne le plus petit ordinal infini de $M$, est une structure de Dedekind Peano.

"Ensuite, un modèle ne peut pas être une classe propre (par définition, c'est un ensemble)"
mais quel est la définition d'un ensemble (intuitif) alors ?

Dans $ZFC$, on montre que tout ensemble admet un cardinal car tout ensemble peut être muni d'un bon ordre.
Si on suppose que l'axiome du choix intuitif est vrai, je pense qu'on peut également démontré que tout ensemble admet un cardinal (intuitif) car le lemme de Zermelo (intuitif) est également valide. (je vais refaire la démo dans ce cas)
Enfait, je repensais à ce qu'avait écrit Bruno dans le post "questions sur $ZF$" : "on ne fait pas de théorie des modèles sans axiome de choix par exemple. "
On parle souvent de cardinaux dans la théorie des modèles ; est ce qu'une des raisons est justement : "tout ensemble intuitif admet un cardinal intuitif" ?
Cordialement, Arthas

jean-c_rien

Bonjour Arthas,
"C'est le terme modèle "standard" (et non standard) de l'arithmétique qui m'intrigue.
Je n'ai toujours pas trouvé de définition. "
Disons que c'est un synonyme de "intuitif", mais comme beaucoup de gens considère que c'est mal poli de parler d'intuition en math, on à opté pour le terme standard. Nous ne voyons pas d'autres explications.

Si j'ai bien suivi, une structure de Dedekind-Peano n'est rien moins qu'un modèle de PA, décrit explicitement en terme d'ensemble. Donc justement, les modèles non-standard dont les éléments forment un ensemble sont précisément les structures de Dedekind-Peano qui ne sont pas le modèle standard, ie notre N intuitif.

"Si on suppose que l'axiome du choix intuitif est vrai, je pense qu'on peut également démontré que tout ensemble admet un cardinal (intuitif) car le lemme de Zermelo (intuitif) est également valide. (je vais refaire la démo dans ce cas) "
Je suis d'accord, mais comme c'est purement intuitif, libre à quiconque de penser le contraire, ça n'aura aucune incidence sur la cohésion des mathématiques (et même que c'est ça qu'est beau à mon avis).

Cordiallement, jean-c_rien

@l

Salut,

je profite de l'occasion pour remettre ce lien sur le lien entre $ZF$ et les ensembles 'intuitifs':

http://www.les-mathematiques.net/phorum/read.php?f=2&i=288247&t=287172#reply_288247

Cela répondra je pense à ta question sur les ensembles et les classes propres.

Sinon, de manière générale, en théorie des modèles, le terme standard ne veut rien dire. Pour $PA$, un modèle standard signifie juste qu'il est isomorphe à $\N$; sinon il est non-standard. Dans $ZF$, il n'y a pas directement de standard et non-standard: il faut préciser un peu plus les choses.

Il faut vraiment distinguer 2 choses: $PA$ et le $\N$ de $ZF$.
Je m'explique. C'est encore une histoire de niveau auquel on se place.
Par exemple, on dit que notre monde de référence, c'est le monde 'réel' (ou 'intuitif'). Dans ce cas, on développe la théorie des modèles habituelles et on obtient entre autres, deux théories, $PA$ et $ZF$.

$PA$ est une tentative de description {\bf au premier ordre} des {\bf 'bonnes'} propriétés de $\N$. Ainsi, $PA$ est une théorie récursive.
Cependant, $PA$, comme toute théorie du premier ordre, possède une infinité d'autres modèles que $\N$ (c'est le théorème de Löwenheim-Skolem).
Toujours à notre niveau, on peut définir des structures de Dedekind-Peano.
Il n'y a à priori pas de lien entre ces structures et les modèles de $PA$.
En effet, déjà, pour qu'il apparaisse un lien, il faudrait par exemple, que l'ensemble $E$ soit un monoïde pour l'addition et la multiplication.
De plus, et finalement, c'est là le plus gros problème, dans une théorie du premier ordre (par exemple $PA$), on ne peut pas quantifier sur des ensembles.
Ainsi la condition $4$ pose un gros problème. Je rappelle que dans $PA$, la récurrence ne porte que sur des {\bf ensembles définissables et non sur tous les ensembles.}


Maintenant passons dans un modèle, $\mathcal{M}$ de $ZF$: on change de niveau. Dans ce modèle, on construit un ensemble-objet $\N_{\mathcal{M}}$.
Il faut bien voir que $\N_{\mathcal{M}}$ est en fait un point de $\mathcal{M}$.
Cependant, soit $x\in \mathcal{M}$ (donc $x$ est un ensemble-objet), on assimile $x$ et l'ensemble intuitif

$\{u\in \mathcal{M}; u\epsilon x\}$

où $\epsilon$ est le symbole du langage de la théorie des ensembles (c'est une appartenance-objet, donc au niveau de $\mathcal{M}$).

De ce fait, $\N_{\mathcal{M}}$ peut être aussi considérer comme un ensemble intuitif.
Il faut bien voir que les fomules de la théorie des ensembles sont de longueur entière {\bf intuive}. De ce fait, si $F[X]$ désigne toujours la formule définissant $\N_{\mathcal{M}}$ dans $\mathcal{M}$, on a:

$\mathcal{M}\models F[\emptyset]$

$\mathcal{M}\models F[\{\emptyset\}]$

$\mathcal{M}\models F[\{\emptyset, \{\emptyset\}\}]$

etc....

On obtient ainsi que $\N_{\mathcal{M}}$ 'débute' par une copie des entiers intuitifs.
Cependant, rien ne dit qu'après ces entiers, on a parcouru tout $\N_{\mathcal{M}}$.
Là, on tombe dans les entiers dits 'non-standards'.

Il existe des modèles de $ZF$, $\mathcal{U}$ où $\N_{\mathcal{U}}$ n'a que des éléments standards (intuitifs) et des modèles $\mathcal{V}$, où $\N_{\mathcal{V}}$ a d'autres éléments.

Or quand on vit dans un modèle donné de $ZF$, on ne peut pas savoir si notres $\N$ contient ou ne contient pas d'entiers non-standards. Mais j'insiste là-dessus, il s'agit de $\N$. Ceci est complètement détaché de $PA$. Ainsi, par exemple, nous ne pouvons pas savoir si il existe dans notres bon vieux $\N$ des entiers non-standards (au sens de la théorie des ensembles)....

En résumé, il y a des entiers standards et non-standards dans $PA$ et $ZF$ et il n'y a pas de rapports entre ces deux notions (en réalité, si mais c'est compliqué à expliquer).

@l

jean-c_rien

"Ainsi la condition $ 4$ pose un gros problème. Je rappelle que dans $ PA$, la récurrence ne porte que sur des ensembles définissables et non sur tous les ensembles. "
Très juste, j'avais omis ce détail. En fait quand j'ai dit :
"Si j'ai bien suivi, une structure de Dedekind-Peano n'est rien moins qu'un modèle de PA"
je n'avais pas compris que les stuctures de Dedekind-Peano se devait de vivre dans un modèle de ZF, j'avais compris ensemble comme ensemble intuitif, du coup j'ai totallement squizé la partie "logique du premier ordre", je crois donc que les structures de Dedekind-Peano sont plus restrictives que les simples modèles de PA (puisque ZF est là pour nous donner accès à la logique des ordres, plus générale), mais c'est en fait une considération sémantique et non formelle.

"Ainsi, par exemple, nous ne pouvons pas savoir si il existe dans notres bon vieux $ \mathbb{N}$ des entiers non-standards (au sens de la théorie des ensembles)...."
Est-ce que tu sous-entends que l'intuition que nous avons des ensembles est peut-être incompatible avec l'intuition de l'ensemble N. Si c'est le cas alors je croît que je viens de rencontrer un être qui possède une image intuitive des ensembles vraiment différente de la mienne, puisque chez moi l'idée que je me fait d'un ensemble est très justement ad hoc.

@l

"Est-ce que tu sous-entends que l'intuition que nous avons des ensembles est peut-être incompatible avec l'intuition de l'ensemble N. Si c'est le cas alors je croît que je viens de rencontrer un être qui possède une image intuitive des ensembles vraiment différente de la mienne, puisque chez moi l'idée que je me fait d'un ensemble est très justement ad hoc."


Je ne comprends pas complètement ce que tu écris. Il faut bien voir que la notion d'ensemble est surement une des notions les plus ardues en maths. En fait, on n'a pas de définitions de ce qu'est un ensemble.... C'est à mon sens là qu'on quitte les maths pour des considérations plus philosophiques.

Maintenant, dans notre $\N$ (et en fait dans énormément d'ensembles), il y a des éléments dont on n'a pas idée mais qui sont tout à fait clairs pour quelqu'un 'vivant' dans un univers supérieur au notre.

@l

@l

"Maintenant, dans notre $ \mathbb{N}$ (et en fait dans énormément d'ensembles), il y a des éléments dont on n'a pas idée mais qui sont tout à fait clairs pour quelqu'un 'vivant' dans un univers supérieur au notre."

Je voulais dire: il y a {\bf potentiellement} des éléments dont on n'a pas idée mais qui sont tout à fait clairs pour quelqu'un 'vivant' dans un univers supérieur au notre.
On n'a aucun moyen à notre niveau pour le savoir.

@l

jean-c_rien

"Je ne comprends pas complètement ce que tu écris."
C'est normale c'était ridicullement confus. Je me suit rendu compte qu'on ne disait peut-être pas la même chose quand nous parlions de "nos ensembles", pour moi le "nos" se réfère à la conception personelle des ensembles de chacun, et non à une conception partagée par tous. Donc "nos enembles" = "mes ensembles", mais le sens varie suivant la personne qui lit. En particulier, "mes ensembles" sont absolument indépendant de toute conception d'univers krivinesque (il y a cependant un lien avec les univers grothendieckien), et mon N n'a pas d'entiers non-standard. En fait mes ensembles ne vivent pas dans un univers à mon sens, car, toujours à mon sens, les univers sont des ensembles (que ce soient les univers de Krivine ou de Grothendieck).