Paradoxe de Skolem

PelucheCanard · June 2020

Bonjour
Un peu de contexte : je n'ai pas vraiment fait de formation poussée en logique ni en fondement des mathématiques. À l'origine j'utilise Coq et je découvre petit à petit les concepts qui y sont liés. Je connais très vite fait la théorie des ensembles ZFC mais mon "intuition" provient plutôt de la logique constructive comme support de la logique des prédicats.

Mon problème est le suivant : je pensais que la non dénombrabilité de l'ensemble des réels entraînait le fait qu'il était impossible de construire cet ensemble des réels, or on m'a souligné l'existence du paradoxe de Skolem dont j'ai du mal à comprendre la résolution.

Plus précisément d'après la page Wikipedia sur le paradoxe de Skolem (https://en.wikipedia.org/wiki/Skolem%27s_paradox), le théorème de Löwenheim-Skolem dit que s'il existe un modèle de cardinal quelconque à un jeu d'axiome dénombrable, alors il existe un modèle dénombrable pour ce même jeu d'axiome. Or les axiomes définissant R sont au nombre de 4 (corps, ordonnée, archimédien, à borne supérieur), et l'existence de R indique que ce jeu d'axiome n'est pas contradictoire. Du coup j'ai l'impression que la déduction est qu'il existe un ensemble dénombrable qui satisfait aux mêmes axiomes que R... J'ai l'impression d'avoir mal compris l'énoncé du théorème de Löwenheim-Skolem.

Plus je lis des explications de ce paradoxe moins je comprends ce qui se passe : une explication indique qu'il y a en fait 2 notions de dénombrabilités en jeu, celle qui est "naturelle" et celle qui fait partie du modèle... La dénombrabilité se définit comme l'absence de bijection entre un certain ensemble assimilé à des entiers, et un deuxième ensemble. Mais si je me place dans le cadre de Coq, les entiers sont définis comme des entiers de Peano qui me semblent être en bijection avec les entiers "hors du modèle", cet argument en tout cas ne m'aide pas à mieux percevoir ce qui se passe.
J'ai la sensation qu'une des définitions des concepts employés me manque mais je ne parviens pas à trouver laquelle.

Vincent

christophe c · June 2020

Ni archimédien, ni borne supérieure ne sont des énoncés du premier ordre.

Les énoncés du premier ordre s'obtiennent avec des $\forall\in LeMachin, \Rightarrow, non$ et rien de plus en dehors des opératoins/relatins officielles du machin.

Essaie d'obtenir un Prix Nobel en prouvant que tu peux exprimer la prop de borne supérieure de cette manière, tu vas ressentir la chose.

Tu peux d'ailleurs t'en apercevoir avec un exemple plus simple:

CanardPelucheFiction a écrit:

le théorème de Löwenheim-Skolem dit que s'il existe un modèle de cardinal quelconque à un jeu d'axiome dénombrable, alors il existe un modèle dénombrable pour ce même jeu d'axiome. Or il y a qu'un seul axiome dans le fait de demander "être non dénombrable". Donc, je ne comprends pas, les ensembles non dénombrables pourraient être dénombrables?"

Nîmes-man · June 2020

Comme tu mélanges beaucoup de choses c'est difficile de te répondre. Je veux juste revenir sur

PelucheCanard a écrit:

Le théorème de Löwenheim-Skolem dit que s'il existe un modèle de cardinal quelconque à un jeu d'axiome dénombrable, alors il existe un modèle dénombrable pour ce même jeu d'axiome. Or les axiomes définissants R sont au nombre de 4 (corps, ordonnée, archimédien, à borne supérieur).

Le théorème de Löwenheim-Skolem est un théorème qui porte sur la logique du premier ordre. Tu veux l'appliquer à une axiomatique de R qui ne me semble pas du premier ordre (l'axiome de la borne supérieure quantifie sur les parties de R).

Mais peut-être n'est-pas ce que tu voulais dire ?

Martial · June 2020

@PelucheCanard,
Il faut faire un peu de ménage dans tout cela.
Comme dit Christophe, les énoncés du type "toute partie non vide et majorée admet une borne sup" sont des énoncés du second ordre.

MAIS, dans ZFC tu as un axiome qui te dit que pour tout ensemble $x$ il existe un ensemble $\mathcal{P}(x)$.
ZFC te permet également de construire l'ordinal $\omega$, qui est le "pendant ZFC" de l'ensemble des entiers naturels.
Une fois que tu as $\omega$ tu peux construire $\mathbb{Q}$. Donc tu disposes maintenant de $\mathcal{P}(\mathbb{Q})$ et il est alors facile d'en déduire une construction de $\mathbb{R}$.
Tu montres (dans ZFC) que $\mathbb{R}$ est un corps totalement ordonné blablabla, et qu'il n'est pas dénombrable.

Soit.

Maintenant, supposons que ZFC n'est pas contradictoire. Par le théorème de complétude elle admet un modèle, soit $M$. Ce modèle est forcément infini, à cause justement de l'axiome de l'infini.
Par Löwenheim-Skolem il existe une structure $N$ qui est dénombrable et qui a exactement les mêmes propriétés que $M$, donc en particulier $N$ est modèle de ZFC.
Le soi-disant paradoxe de Skolem dit : "puisque $N$ est modèle de ZFC il doit contenir les réels. Et comme il est dénombrable comment fait-il pour contenir les réels ?"
L'explication est très simple : le modèle $N$ a "sa" version des réels. Vu de chez nous il n'y a qu'une quantité dénombrable de réels dans $N$. Notons $\mathbb{R}^N$ cet ensemble.
Nous, qui dominons les choses de haut, voyons bien que $\mathbb{R}^N$ est dénombrable. Mais l'habitant du modèle, qui dispose de beaucoup moins de bijections que nous, ne voit pas la bij qui témoigne de la dénombrabilité de cet ensemble, donc pour lui c'est un ensemble non dénombrable.
Et il n'y a plus de paradoxe.

PelucheCanard · June 2020

Merci pour vos réponses !

Effectivement je suis parti un peu vite avec l'hypothèse que tous les axiomes étaient représentables en logique du premier ordre et du coup effectivement ça lève une partie du paradoxe pour moi.

Martial écrivait dans le message précédant :

> MAIS, dans ZFC tu as un axiome qui te dit que pour tout ensemble $x$ il existe un ensemble $\mathcal{P}(x)$.
> ...
> Par Löwenheim-Skolem il existe une structure $N$ qui est dénombrable et qui a exactement les
> mêmes propriétés que $M$, donc en particulier $N$ est modèle de ZFC.

Merci pour cette explication. Mais du coup j'ai du mal à imaginer ce que les différents ensembles "sont" dans $N$. J'imagine que pour que l'équivalent dans $N$ de $\mathcal{P}(\mathbb{Q})$ soit dénombrable "pour nous" il faut que $\mathbb{Q}$ soit fini dans $N$, et donc $\mathbb{N}$ (qui du coup ne serait plus $\omega$ mais autre chose). Est-ce que c'est juste ?

Poirot · June 2020

Non, le $\mathbb N$ de $N$ est infini (sinon $N$ ne vérifierait pas l'axiome de l'infini). C'est juste que $N$ ne voit pas de bijection entre son $\mathbb R$ et son $\mathbb N$. Cette bijection n'est pas un élément de $N$.

PelucheCanard · June 2020

Mais si le $\mathbb{N}$ de N est infini, comment le $\mathcal{P}(\mathbb{Q})$ peut être dénombrable pour nous ? Je comprends l'absence de bijection dans le modèle, mais est-ce que l'équivalent de l'ensemble des parties est défini différemment dans $N$ par rapport à la façon de le définir "en dehors" du modèle ?

En gros ce que je comprends pas c'est ce que le $\mathbb{R}$ de $N$ représente pris en dehors du modèle.

Poirot · June 2020

Eh bien $\left(\mathcal P(\mathbb Q)\right)^N \neq \mathcal P\left(\mathbb Q^N\right)$ c'est pour ça ! Celui de gauche est "ce que $N$ croit être l'ensemble des parties de $\mathbb Q$" et en particulier $N$ ne contient aucune bijection entre cette chose et $\mathbb N^N$ par exemple, mais comme cet ensemble est dénombrable (de notre point de vue extérieur) on sait qu'il ne contient certainement pas toutes les parties de $\mathbb Q^N$, car on sait que cet ensemble n'est pas dénombrable.

Et $\mathbb R^N$ est un ensemble dénombrable de notre point de vue, on ne peut en dire grand-chose d'autre, si ce n'est que c'est l'ensemble obtenu à partir de $\mathbb Q^N$ en prenant les coupures de Dedekind (en ne travaillant qu'avec des paramètres variant dans $N$).

Martial · June 2020

Poirot a très bien résumé la situation.

A la question de PelucheCanard : qu'est-ce que le $\mathbb{R}$ de $N$ représente pris en dehors du modèle ?, il est difficile d'apporter une réponse autre que "philosophique".
En effet, d'après le second théorème d'incomplétude de Gödel, on est incapables de démontrer (dans ZFC) la consistance de ZFC. Donc on est aussi incapables de démontrer l'existence d'un modèle de ZFC, et encore moins d'un modèle dénombrable. On ne peut donc absolument pas savoir à quoi ressemble $N$, et encore moins son $\mathbb{R}$.

La seule chose qu'on puisse dire est la suivante : SI ZFC est CONSISTANTE, il existe (chez nous) une partie $E \subseteq \omega^2$ telle que, si on interprète le symbole $\in$ par la relation $E$, alors la structure $(\omega , E)$ satisfait tous les axiomes de ZFC. Et il existe aussi un ensemble $J \subseteq \omega$ qui est le $\mathbb{R}$ du modèle $(\omega, E)$.
En conclusion, les ensembles $E$ et $J$ sont peut-être "sous nos yeux", mais on ne les verra jamais. A noter toutefois que, s'ils existent, ils sont "fortement non récursifs".

P.S. : Si un extra-terrestre lit mon post il va se dire : "ce mec est complètement barjo, il a réussi à injecter $\mathbb{R}$ dans $\omega$, il faut le faire enfermer de toute urgence !"

Martial · June 2020

mode HS on :

Sorry mais ça m'énerve, je n'arrive pas à retrouver un fil de discussion.
Max avait ouvert un fil dans "Vie du forum et de ses membres", intitulé "Le forum et la fin de mon éducation formelle".
Quand il a compris que Christophe ne pouvait pas répondre il a continué la discussion quelque part dans "Fondements et logique", mais où ?

Pour info c'est le fil où Georges Abitbol avait fait une intervention remarquable au sujet de mon profil de poste : "le candidat devra avoir les cheveux gris, une barbe blanche mal taillée et de préférence regarder l'orateur d'un oeil torve. Des connaissances en théorie des ensembles seraient vivement appréciées". Un truc comme ça, qui m'avait littéralement fait mourir de rire.

Je voulais juste envoyer le lien à mes potes pour les faire marrer un peu.

Merci d'avance.

mode HS off

Poirot · June 2020

@Martial : le fil est là http://www.les-mathematiques.net/phorum/read.php?32,2014500 mais ce n'est pas là qu'il y avait eu cet échange. Le message dont tu parles est là : http://www.les-mathematiques.net/phorum/read.php?16,2014622,2015270#msg-2015270

PelucheCanard · June 2020

@Martial merci pour cette explication !

Mais du coup ce que j'ai du mal à interpréter, c'est qu'on parle d'entiers et de réels dans le modèle, mais au fond ces entiers et ces réels ne sont pas forcément en bijection "implicite" avec ceux qu'on utilise en dehors du modèle ?

En fait ce qui me perturbe c'est qu'en Coq on "construit" les entiers en suivant les axiomes de Peano et que donc j'ai l'impression que les entiers sont uniques "à isomorphisme près", or il semble que ça ne soit pas le cas.

Poirot · June 2020

Et moi j'ai pas le droit à un merci ? :-D

Pour ton questionnement sur les entiers, on a tous le même ! On a une idée intuitive de ce qu'est l'ensemble des entiers naturels, mais on ne sait pas le définir convenablement (au premier ordre). En fait l'arithmétique de Peano ne capture pas son essence : il existe des modèles "non standards" de l'arithmétique de Peano. Donc quand on fait de la théorie des ensembles, on travaille dans un modèle de ZFC (en supposant qu'une telle chose existe, ce que l'on ne peut démontrer uniquement avec ZFC d'après le second théorème d'incomplétude de Gödel comme l'a expliqué Martial), et on considère que le $\mathbb N$ de ce modèle est "le vrai $\mathbb N$". Maintenant notre modèle peut admettre des sous-modèles dont l'ensemble des entiers n'est pas standard, c'est la vie.

En fait il n'y a qu'un modèle de l'arithmétique de Peano au second ordre, mais au premier ordre il y a $2^{\aleph_0}$ modèles distincts.

Martial · June 2020

Bien joué, Poirot.
Et merci pour le lien.

Patrick Dehornoy m'a dit un jour : "Le forcing c'est de l'algèbre. Les grands cardinaux c'est de la combinatoire. Mais ce genre de subtilités (comme ci-dessus) est beaucoup plus subtil, et c'est très bien de se poser ce genre de questions".

Martial · June 2020

Décidément je suis trop fort : tout-à-l'heure je démontrais que $\mathbb{R} \subseteq \omega$, et maintenant je dis qu'une subtilité est subtile...

christophe c · June 2020

Ah bin pour le deuxième, tu fais des maths, bravo!!! ;-)

Martial · June 2020

@Christophe : oui, je démontre que $A \Rightarrow A$.
Félicitations du Jury !

PelucheCanard · June 2020

Désolé, merci à tous !

umrk · June 2020

@tous les intervenants : franchement, je suis éperdu d'admiration , vous me trouez le fondement !

Heureusement que mes enseignants (paix à leur âme) m'ont dissimulé les problèmes se cachant derrière l'ensemble sans nul doute le plus intuitif de toutes les mathématiques : N.

Mais en même temps, (bien que j'aie renoncé depuis longtemps à essayer d'approfondir tout ceci) , vous mettez en évidence le caractère diabolique de la logique, où rien ne semble jamais acquis, contrairement aux mathématiques ..... Discipline vraiment ingrate .....

Martial · June 2020

@umrk : tes enseignants avaient probablement de très bonnes raisons de te cacher ces subtilités. Soit eux-mêmes n'étaient que "fort peu logiciens" (il n'y a pas de honte à ça), soit ils ne voulaient pas t'encombrer le cerveau inutilement.

$\mathbb{N}$ est effectivement l'ensemble le plus intuitif des maths, mais il cache beaucoup de subtilités, le principal problème étant que quand tu travailles dans un modèle de ZF(C), tu ne peux jamais être que sûr que ce modèle est standard, c'est-à-dire que tu ne sais pas si la suite définie sur $\N$ par $u_0 = \emptyset$ et $u_{n+1} = u_n \cup \{u_n\}$ "remplit" ou pas le $\omega$ du modèle. C'est la vie, comme dit Poirot.

Mais là où je ne suis pas d'accord avec toi c'est quand tu dis que la logique est une science à part des maths.
Prends un étudiant de L1 pas trop mauvais en math. Tu supposes $\mathbb{N}$ connu et tu lui expliques les structures quotients. Une fois ce point acquis tu n'auras aucun mal à lui construire $\mathbb{Z}$, $\mathbb{Q}$ et $\mathbb{R}$. Mais si l'étudiant est intelligent il va te demander : "oui, d'accord, m'sieur, j'ai compris. Mais comment vous faîtes pour construire $\mathbb{N}$ ?"
Et là, si tu refuses de parler de logique tu vas avoir des problèmes pour lui répondre...

Paradoxe de Skolem

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 11