Infinité de nombres premiers dans Peano
Bonjour,
Je précise tout d'abord que je m'y connais mal en logique. Je n'ai jamais suivi de cours de logique (je le ferai l'année prochaine), mais des amis qui l'ont fait m'ont expliqué vite fait (enfin pendant plusieurs heures quand même) la logique du premier ordre, les modèles, etc.
Ma question est :
Merci d'avance
Je précise tout d'abord que je m'y connais mal en logique. Je n'ai jamais suivi de cours de logique (je le ferai l'année prochaine), mais des amis qui l'ont fait m'ont expliqué vite fait (enfin pendant plusieurs heures quand même) la logique du premier ordre, les modèles, etc.
Ma question est :
Est-il possible d'écrire, dans l'arithmétique de Peano du premier ordre, une formule logique qui dit "il existe une infinité de nombres premiers" ?
J'ai réussi à écrire une formule pour "$p$ est premier" : $\forall d, (\exists k, dk=p) \Rightarrow (d=s(0) \vee d=p)$. Et, pour tout entier naturel intuitif non nul $n$ on peut écrire "il existe au moins $n$ nombres premiers" ainsi : $$\forall p_1,\dots,\forall p_{n-1}, (p_1\text{ est premier} \wedge \dots \wedge p_{n-1}\text{ est premier}) \Rightarrow (\exists p_n, p_n\text{ est premier} \wedge p_n\neq p_1 \wedge \dots \wedge p_n\neq p_{n-1})$$ ou ainsi : $$\exists p_1,\dots,\exists p_n, (p_1\text{ est premier} \wedge \dots \wedge p_n\text{ est premier}) \wedge \underbrace{(p_1\neq p_2 \wedge \dots \wedge p_i\neq p_j \wedge \dots)}_{\text{pour tous $i\,\neq\, j$ dans $1,n$}}$$ en remplaçant les "$\text{machin est premier}$" par la formule précédente. Mais je n'ai pas trouvé de formule qui réponde à ma question et je doute qu'il en existe une.Merci d'avance
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
En fait tu t'y es mal pris, car en logique du premier ordre on ne peut pas caractériser les structures infinies avec un nombre fini d'axiomes. En particulier il n'existe pas de formule pour dire : "tel truc est infini".
Mais, comme tu travailles dans un modèle de Peano, dire qu'un ensemble $A$ est infini revient à dire que pour tout élément $k$ de ta structure tu peux trouver un élément $p$ de $A$ qui est plus grand que $k$
Pour $\forall k, \exists p, (p \geqslant k) \wedge (p \text{ est premier})$, je suis bien d'accord que ça implique l'existence d'un nombre infini de nombres premiers (au sens intuitif), mais la réciproque est-elle vraie ? Il est a priori possible qu'il existe un modèle (non standard) de Peano dans lequel il y a une infinité de nombres premiers mais les nombres premiers ne sont pas cofinaux parmi tous les nombres entiers du modèle. Bon, si la proposition $\forall k, \exists p, (p \geqslant k) \wedge (p \text{ est premier})$ est vraie dans tout modèle de Peano, la question du présent paragraphe ne se pose plus vraiment car on a quelque chose du type $\text{vrai} \Rightarrow \text{vrai}$.
Eh, c'est bien ce que je me disais. Mais je ne suis pas à l'aise en logique, donc je me suis permis de solliciter votre aide et je voulais voir s'il n'y avait pas d'autre approche (et j'en ai eu une :-)).
PS: Ça ne se dit pas "PA1" ? (AD l'a remplacé par Peano)
[Pour moi PA1 n'est connu que des spécialistes ... :-S AD]
[D'accord, c'est un comble puisque je ne suis pas du tout spécialiste :-D. Donc "PA1" se dit, mais Peano est plus clair pour tout le monde, ça me va. Calli]
Je te rappelle que tu es dans la partie Logique du forum. Je te laisse...
christophe c n'a pas encore déboulé mais je sens que, quand il va le faire, je vais être perdu X:-(
PA1 désigne l'axiomatique de Peano du 1er ordre, qui a $2^{\aleph_{0}}$ modèles 2 à 2 non isomorphes, dont un seul est standard, par opposition à PA2, celle du 2ème ordre, qui n'a qu'un seul modèle à isomorphisme près.
GaBuZoMeu a raison quand il dit que tu ne raisonnes pas par l'absurde. La raison profonde en est assez subtile mais je vais te l'expliquer en termes plus simples : au lieu de dire : "je fais le produit de tous les premiers +1", il te suffit de dire : "je me donne les r premiers nombres premiers", et je fais le produit de tous ces machins +1. Puis j'en fabrique un (r+1)ième, ce qui prouve qu'au-dessus d'un premier il y en a toujours un plus grand.
Et là, c'est clair, pas de raisonnement par l'absurde.
Je ne savais pas qu'on pouvait calculer le nombre de modèles de PA1 ::o. Et peut-on décrire le nombre maximal d'éléments d'un modèle de PA1 (au sens des cardinaux de la théorie de ensembles) ?
Peut-on aussi estimer le nombre de modèles de ZF, ZFC ou bien une quelconque autre théorie contenant ZF ? (là, j'ai des doutes...)
http://www.les-mathematiques.net/phorum/read.php?16,1880930
Tu as raison, on ne peut effectivement pas compter le nombre de modèles de PA1. Je me suis mal exprimé : ce que je voulais dire c'est qu'il y a $2^{\aleph_{0}}$ modèles DENOMBRABLES de Peano 2 à 2 non isomorphes.
Il y a aussi des modèles de cardinal $\aleph_{1}$, etc, bref selon le théorème de Löwenheim-Skolem, si PA1 est consistante elle a un modèle en toute cardinalité infinie.
Il y a donc autant de modèles de PA1 qu'il y a d'éléments dans l'univers, c'est-à-dire une classe propre (ce que Cantor appelait "l'infini absolu").
Et on ne peut pas non plus compter le nombre de modèles de ZF ou ZFC, sauf si ZF est inconsistante, auquel cas il y en a 0.
Si elle est consistante elle admet un modèle en toute cardinalité infinie, donc là encore ça fait beaucoup.
Oui, je sais, la première fois ça donne le vertige...
Tu vas me dire que tout ça ça reste du dénombrable... Certes, mais maintenant il faut encore définir les opérations, et ça il y a $2^{\aleph_{0}}$ façons de le faire. La démonstration n'est pas très compliquée, je ne la connais plus par coeur mais je sais qu'elle utilise un argument "musclé" de compacité.
1°) Soit $N\in \N$. Alors les entiers $1+k(N!)$ pour $k=1,2,...,N$ sont premiers 2 à 2 (si $i<j \leq N$ et un nombre premier $p$ divise $1+i(N!)$ et $j(N)!$ alors il divise $(j-i)(N!)$ et donc est plus petit que $N$, or il est premier avec $N!$ car divise $1+!N$). On peut s'en inspirer pour montrer dans PA (en montrant d'abord par récurrence l'existence pour tout $N$ d'un entier $M$ tel que tous les facteurs premiers de $M$ sont inférieurs à $N$ et tel que tous les entiers inférieurs à $N$ divisent $m$) que pour tout $n$, il existe $m\in N$ tels que pour tous $i,j$, $1\leq i < j \leq n$, $1+in$ et $1+jn$ sont deux à deux sans facteurs communs.
A l'aide du lemme chinois (prouvable dans PA avec reformulation idoine), on peut conclure que pour toute formule $F$ à deux arguments, si pour tout $p\in \N$ il existe $q \in N$ tel que $F(p,q)$, alors il existe un entier $u$ tel que pour tout $k\leq n$, le reste $r_k$ de la division de $u$ par $(1+km)$ satisfait $F(k,r_k)$ (c'est l'idée de Gödel d'utiliser lemme chinois et division euclidienne pour montrer qu'on peut encoder toutes les suites finies d'entiers dans PA; après on peut formuler des énoncés dont la signification intuitive est "pour toute suite finie blabla").
2°) Pour tout ensemble ordonné $(I,\leq)$, Il existe dans ZFC un modèle de PA où $(I,\leq)$ se plonge (avec des ultrafiltres).
On fixe $I$ un ensemble et $\u$ un ultrafiltre sur $I$.
On abrège par $F_I(\bf p)$ l'énoncé "$\bf p$ est une fonction (un ensemble de couples tel que blabla) dont le domaine est $I$".
Dans ce qui suit les formules sont construites avec $\in,=$ et les connecteurs $\wedge, \neg,\exists$ ($A \Rightarrow B$ abrège $\neg( A \wedge \neg $ etc).
Si $\Box$ est l'un des deux symboles $\in, =$ on définit la formule à deux arguments $\xi (\bf x \Box y)$ comme étant l'abréviation de:
"$F_I(\mathbf x) \wedge F_I(\mathbf y) \wedge \exists T \in \u \left [\forall i,j,k, \left ( i \in T \Rightarrow (i,j)\in \mathbf x \Rightarrow (i,k)\in \mathbf y \Rightarrow j \Box k \right ) \right ]$"
(énoncé plus clairement: $\mathbf x$ et $\mathbf y$ sont des fonctions de domaine $I$ et l'ensemble des $i\in I$ tels que $\mathbf x(i) \Box \mathbf y(i)$ appartient à $\u$).
Ensuite on définit pour toute liste de variables $\Gamma := [\bf x_1,...,x_n]$ et toute formule $F$ dont les variables libres sont dans $\Gamma$, une formule $\Xi^{\Gamma}(F)$ de la façon suivante:
$\Xi^{\Gamma} (\bf x_i \Box x_j) := \xi( \bf x_i \Box x_j)$ ($\Box$ est "$\in$" ou "$=$")
$\Xi^{\Gamma}(A \wedge := \Xi^{\Gamma}(A) \wedge \Xi^{\Gamma} (B)$
$\Xi^{\Gamma} (\neg D) :=\neg \left ( \Xi^{\Gamma} D\right)$ (édité)
$\Xi^{\Gamma} \left ( \exists \mathbf y C\right ) := \exists \mathbf y \left ( F_I (\mathbf y) \wedge \Xi^{\Gamma \cup \{\mathbf y\}} C \right )$ (où $\mathbf y$ n'est pas une lettre de $\Gamma$ et $C$ est une formule dont les variables libres sont dans $\Gamma \cup (\mathbf y)$).
Les propriétés de base des ultrafiltres permettent, pour toute formule $F$ dont les variables libres sont parmi $[\mathbf y_1,...,\mathbf y_p]=: \Delta$, de montrer inductivement sur la taille de la formule l'équivalence suivante:
1°) Pour toutes fonctions $a_1,...,a_p$ de domaine $I$, on a $ \Xi^{\Delta} \left ( F \right ) [\mathbf y_1 := a_1,...,\mathbf y_n := a_n]$ (édité) si et seulement si l'ensemble des $x\in I$ tels que $F[\mathbf y_1 := a_1(x), ... \mathbf y_n := a_n(x)]$ est un élément de $\mathcal U$.
$\Delta$ peut être vide ce qui montre en particulier que en notant $\in^* := \xi ( ... \in ...)$ et $=^* := \xi ( ... = ...)$, les éléments de la classe des fonctions de domaine $I$ constituent un modèle (non ensembliste ...) de ZFC avec ces nouveaux symboles de relation $\in^*$ et $=^*$.
Pour tout ensemble $a$, notons $\chi (a)$ la fonction constante $i\in I \mapsto a$. Il est clair que pour tous $a,b$, on a $\chi (a) \in^*\chi(b)$ (resp $\chi(a) =^* \chi (b)$) si et seulement si $a\in b$ (resp $a=b$). On dira qu'une fonction $f$ de domaine $I$ est standarde (et on notera $St(f)$) s'il existe $A\in \u$ tel que la restriction de $f$ à $A$ est constante, autrement dit s'il existe $t$ tel que $f =^* \chi (t)$.
La propriété 1°) ci-dessus entraîne la 2°) suivante:
Pour toute formule $G$ à variables libres dans $[\mathbf x_1,...\mathbf x_p, \mathbf y_1,...,\mathbf y_q]:=\Sigma$, on peut prouver que:
Pour tous ensembles $u_1,...,u_p$ et toutes fonctions $b_1,...,b_q$ de domaine $I$,
$\Xi^{\Sigma} (G)[\mathbf x_1 := \chi(u_1), ... \mathbf x_p := \chi (u_p), \mathbf y_1 := b_1, ... \mathbf y_q := b_q]$ si et seulement si l'ensemble des $t\in I$ tels que $G[\mathbf x_1 := u_1, ... \mathbf x_p := u_p, \mathbf y_1 := b_1(t), ... \mathbf y_q := b_q (t)]$ appartient à $\u$.
Ce théorème dit que tous les objets usuels $\N, \R, \C, \sqrt 2$ etc de ZFC s'envoient sur les bons objets correspondants du nouveau modèle avec $\in^*, =^*$. Par exemple $\chi(\N)$ est l'ensemble des entiers standards ou non.
Les cas les plus intéressants sont bien sûr ceux où $\mathcal U$ est non principal et où tout un tas de phénomènes exotiques apparaissent.
Merci @Poirot. J'ai lu la page Wikipédia sur le théorème de compacité (mes amis mentionnés plus haut m'en ont parlé, mais je ne connaissais pas ses applications).
Prenons le langage de Peano $\{0,s,+,\times\}$ et notons $\mathcal{P}(p)$ la proposition qui s'interprète comme "$p$ est premier" en arithmétique : $\mathcal{P}(p) \equiv \forall d, (\exists k, d\times k=p) \Rightarrow (d=s(0) \vee d=p)$. Soit $\varphi$ une formule du premier ordre qui dit "il existe une infinité de $p$ tels que $\mathcal{P}(p)$". La théorie $$\{\neg\varphi, (\exists p, \mathcal{P}(p)), \text{ il existe deux $p$ distincts tels que $\mathcal{P}(p)$},\text{ il existe trois $p$ distincts tels que $\mathcal{P}(p)$},\dots\}$$ est finiment satisfaisable (considérer des modèles finis contenant un $0$ dans lequels $s$ et $+$ sont quelconques et : $\forall d, \forall k,d\times k=d$) mais non satisfaisable. Donc $\varphi$ ne peut pas exister.
Je n'ai pas mis les axiomes de Peano car sinon la théorie considérée n'aurait pas été finiment satisfaisable, puisqu'il y a effectivement un nombre infini de nombres premiers en arithmétique.
Est-ce correct ? Si oui, ça répond à ma question initiale :-).
Pour l'histoire du raisonnement par l'absurde, ça se complique effectivement. J'ai lu le post de christoche c mis en lien mais je ne l'ai pas très bien compris (comme c'est malheureusement souvent le cas lorsque je lis christoche c). Je vais me contenter d'admettre que le raisonnement par l'absurde marche, mais qu'il y a des raisons de préférer celui sans l'absurde.
Tu veux dire "pour tout cardinal $\kappa$, il existe un modèle de ZF qui contient $\kappa$ éléments" ? Mais c'est faux pour $\aleph_0, \aleph_1$... Ou peut-être que ton énoncé marche pour $\kappa$ un grand cardinal (qui ne peut pas être élément du modèle car sinon on aurait aussi $2^\kappa$ dans le modèle)... :-S Bref, peux-tu réexpliquer s'il te plait, j'ai dû mal comprendre.
Qu'il y ait $2^{\aleph_0}$ modèles dénombrables de PA1 ne me choque pas. Après tout, l'opérateur successeur $s$ est une "quasi-bijection" et $\mathbb{N}$ a $2^{\aleph_0}$ bijections. Évidemment il y a d'autres contraintes imposées par PA1, mais je me dis "pourquoi pas".
En revanche, je me demande pourquoi les copies de $\mathbb{Z}$ qui contiennent les entiers non standard doivent être ordonnées de façon dense. Est-ce que ce sont les opérations $+,\times$ qui l'imposent ou la récurrence ? (ça se trouve c'est les deux en même temps)
[AD, comme je suis sur un PC fixe cette fois, j'ai réessayé tes raccourcis et ça ne marche pas. Tu dois avoir un PC magique. (:P) Calli]
- Montrons par récurrence sur $n$ : $\forall n>0,\exists m, \forall d, 0<d\leqslant n \Rightarrow d\mid m$. Ecrire $m=1\times \dots \times n$ n'est pas licite dans PA1.
- Initialisation : Pour $n=1$, on prend $m=1$.
- Hérédité : Si $m$ convient pour $n$, alors on vérifie que $m\times s(n)$ convient pour $s(n)$.
- On montre par récurrence que les entiers sont réguliers pour $+$.
- Montrons par récurrence sur $a$ : $\forall a,\forall b,\forall p>0, ap\leqslant bp \Rightarrow a\leqslant b$.
- Initialisation : $a=0$, trivial.
- Hérédité : Si $a\neq0$, alors $bp>0$, donc $b\neq 0$. En écrivant $a=s(a')$ et $b=s(b')$, on a pour un certain $k$, $s(a')p+k=s(b')p$ donc $a'p+p+k+k=b'p+p$, puis $a'p+k=b'p$ et $a'p\leqslant b'p$. Donc $a'\leqslant b'$ et $a\leqslant b$.
- A présent, la conclusion. Soit $n>0$. Soit $m$ donné par $(1)$. Il existe un nombre premier $p$ qui divise $m+1$ (preuve par récurrence). S'il est inférieur à $n$, alors $p\mid m$ donc on peut écrire $m=ap$ et $m+1=bp$. $ap\leqslant bp$, donc d'après $(3)$ il existe $c$ tel que $b=a+c$. Donc $(a+c)p=ap+1$ puis $cp=1$ et $p\mid 1$. Contradiction
C'est un peu fastidieux. J'ai eu du mal à montrer dans PA1 (sans utiliser $\mathbb{Z}$) que $(p\mid m)\wedge (p\mid m+1)\Rightarrow p\mid 1$.Mon raisonnement est-il correct (dans PA1) ?
Q1 : Le $\Xi^{\Delta} [\mathbf y_1 := a_1,...,\mathbf y_n := a_n]$ dépend de $F$, non ? Ce serait plutôt un $\Xi^{\Delta}(F)[\mathbf y_1 := a_1,...,\mathbf y_n := a_n]$.
Si j'ai bien compris, $\Xi$ d'une formule signifie grossièrement que la formule est vérifiée sur un gros sous-ensemble de $I$ (en considérant qu'un filtre sur $I$ est un ensemble de "gros" sous-ensembles de $I$, dans un sens qui dépend du filtre).
Q2 : Pourquoi tu parles de $\wedge$ et $\exists$ et pas de $\neg$, $\vee$ et $\forall$ ? Ça impose que la formule $F$ dans la première citation ne contienne que des $\wedge$, $\exists$, $=$ et $\in$, non ?
Q3 : Qu'est-ce que le fait que $\mathcal{U}$ soit un ultrafiltre apporte par à rapport à un simple filtre ?
Q4 : Si $\mathcal{U}$ est un ultrafiltre principal, on obtient un modèle isomorphe à celui de départ, non ?
- Ton utilisation du théorème de compacité est correcte.
- Si $\mathsf{ZF}$ admet un modèle, alors elle admet un modèle en toute cardinalité infinie. C'est bien ce que voulait dire Martial. Tu devrais te renseigner sur les théorèmes de Löwenheim-Skolem. C'est une situation qui paraît paradoxale : comment un modèle de $\mathsf{ZF}$ pourrait ne posséder qu'un nombre dénombrable d'éléments et en même temps des ensembles non dénombrables ? La réponse est toute simple : la cardinalité n'a de sens que dans un modèle donné. Ainsi le "$\mathbb R$" d'un modèle dénombrable de $\mathsf{ZF}$ sera, d'un point de vue "extérieur" dénombrable, mais dans ce modèle, il n'existe pas de bijection entre ce $\mathbb R$ et $\omega$.
- Un ultrafiltre $\mathcal U$ sur $I$ a l'avantage de vérifier que pour toute partie $A$ de $I$, $A \in \mathcal U$ ou $I \setminus A \in \mathcal U$. Ça fait que l'on dispose du tiers exclu dans les structures ultraproduits : si $\varphi$ n'est pas satisfaite dans $\prod_i A_i/\mathcal U$, c'est que $\{i \in A_i \mid A_i \vDash \varphi\} \not \in \mathcal U$, et donc que $\{i \in A_i \mid A_i \not \vDash \varphi\} \in \mathcal U$, autrement dit $\neg \varphi$ est satisfaite dans $\prod_i A_i/\mathcal U$. Ça intervient aussi dans la démonstration du théorème de Los, pour traiter le cas des négations de formules (j'aurais peut-être du le présenter dans l'autre sens, mon raisonnement ci-dessus utilise le théorème de Los).
EDIT : visiblement les caractères du nom de Los ne passent pas, désolé à lui.
J'ai édité mon message.
Je prends $\exists, \wedge $ et $\neg$ comme connecteurs de base mais j'aurais tout aussi bien pu prendre d'autres tels $\forall, \vee, \neg$ ou $\forall, \Rightarrow, \neg$ etc.
Dans ce genre d'énoncé on ne prend pas tous les connecteurs mais un sous-système complet qui les engendre (NB: on est du début à la fin en logique classique et donc c'est possible de le faire) afin de raccourcir les preuves (distinction de cas interminables dans les récurrences sur la taille des formules).
Q4: oui.
Je vois mieux l'intérêt de l'ultrafiltre : si $\mathcal{U}$ n'en était pas un, la proposition 1°) de Foys ne marcherait pas pour les formules contenant $\neg$.
@Poirot, je n'ai pas compris qui sont $\prod_i A_i/\mathcal U$ et $\{i \in A_i \mid A_i \vDash \varphi\}$.
J'ai regardé les pages Wikipédia sur le théorème de Löwenheim-Skolem et le paradoxe de Skolem, mais je ne comprends pas comment un $\aleph_1$ peut rentrer dans un modèle dénombrable. Ce qui m'amène à me poser les questions suivantes :
https://sites.google.com/view/martial-leroy
Pour le reste, en vrac :
1)a) Tu vois bien que non : dans l'exemple de Poirot ton $\R$ intérieur au modèle est non dénombrable (comme tout $\R$ qui se respecte) tandis que vu de chez nous il est dénombrable, puisqu'inclus dans un ensemble dénombrable.
b) Ça dépend de ta façon de voir les choses. Selon moi, on vit dans un modèle de ZFC, et toute la logique peut être reformalisée là-dedans, mais tout le monde n'est pas d'accord. (Voir discussion dans mon chap 16).
2)a) Oui, tu le sais très bien.
b) Je dirais oui à vue de nez, mais la question ne veut pas dire grand-chose.
3)a) Oui. Tu peux même voir $M'$ comme un sous-ensemble de $\omega^2$, voire de $\omega$. (Là encore, voir chap 16).
b) Si le modèle est non standard il n'est jamais transitif, donc clairement non. (C'est une relation artificielle).
Il y avait une coquille dans ma question 2)b) que j'ai corrigée (ça ne voulait effectivement pas dire grand chose).
Donc il n'existe pas de formalisation du dénombrable intuitif ? Ce que j'appelle "dénombrable intuitif", c'est le "cardinal" des entiers naturels standard : 0,1,2,3...
Pour le prouver DANS PEANO tu peux écrire que pour tout a il existe b divisible par tous les entiers inférieur à a. Et c'est alors grâce au plus petit diviseur de b+1 que tu conclus. C'est purement peaniste.
Pour ta 1.b., quand on parle de langage dénombrable, c'est au sens métamathématique de la théorie des ensembles ambiante dans laquelle on se place pour voir $\mathcal L$ comme un ensemble de symboles de constantes, fonctions et relations.
Pour mes $A_i$ je m'explique. On considère un langage $\mathcal L$ et pour tout $i \in I$ une $\mathcal L$-structure $A_i$. Alors on peut munir l'ultraproduit $A = \prod_i A_i/\mathcal U$ (c'est juste $\prod_i A_i/=_{\mathcal U}^*$) d'une $\mathcal L$-structure de manière naturelle (par exemple, pour toute constante $c$ de $\mathcal L$, l'interprétation de $c$ dans $A$ est $c^A := \overline{(c^{A_i})_{i \in I}}$, où la barre désigne la classe dans le quotient par $=^*$). Alors le théorème de Los dit qu'une formule du premier ordre $\varphi$ sur $\mathcal L$ est satisfaite dans $A$ si et seulement si l'ensemble des $i \in I$ tels que $\varphi$ est satisfaite dans $A_i$ est dans $\mathcal U$. Le théorème n'est pas très dur à démontrer en fait, il faut raisonner sur le profondeur de la formule : on commence par les formules atomiques, puis supposant le théorème démontré pour $\varphi$ et $\psi$, on le montre pour $\neg \varphi, \varphi \wedge \psi, \exists x, \varphi(x)$.
Je détaille le cas de $\neg \varphi$ pour illustrer en quoi le fait que l'on utilise un ultrafiltre est important. On suppose donc que $\varphi \vDash A$ si et seulement si $\{i \in I \mid A_i \vDash \varphi\} \in \mathcal U$. Alors \begin{align*}A \vDash \neg \varphi &\Leftrightarrow A \not \vDash \varphi\\ &\Leftrightarrow \{i \in I \mid A_i \vDash \varphi\} \not \in \mathcal U\\ &\Leftrightarrow \{i \in I \mid A_i \not \vDash \varphi\} \in \mathcal U \quad \text{(c'est là que l'ultrafiltre est important)}\\ &\Leftrightarrow \{i \in I \mid A_i \vDash \neg \varphi\} \in \mathcal U\end{align*} CQFD
Le paradoxe de Skolem me pose un gros problème d'intuition (à côté de ça, l'Hôtel de Hilbert était facile à avaler). Je ne serai pleinement convaincu que lorsque j'aurai vu et compris une preuve. Et pour ça il faudra attendre d'avoir suivi un vrai cours de logique. Donc je ne vais pas trop passer de temps là-dessus pour l'instant.
Une petite question quand même :
Est-ce que les $\mathbb R$, $\aleph_1$ et $\aleph_2$ du gros modèle sont les même que ceux du petit ? Je suppose que non, puisque la bijection $f_1 : \mathbb R \rightarrow \aleph_1$ du petit modèle est aussi dans le grand, et dans le grand modèle on a $\aleph_1 \not\cong \aleph_2$. Dans ce cas, lesquels ont changé et lesquels sont les mêmes ?
Autrement dit, il existe, dans $\mathsf{N}$, une bijection entre l'ensemble $R$ et l'ensemble $\omega$, c'est-à-dire un sous-ensemble $f$ de $R \times \omega$ vérifiant "je suis une application, injective et surjective". Point de paradoxe, car il n'existe pas de bijection dans $\mathsf{M}$ entre $R$ et $\omega$ : $\mathsf{M}$ ne "voit pas" qu'il y a une bijection entre les deux, mais $\mathsf{N}$ si, car $f \in \mathsf N$ et bien sûr $f \not \in \mathsf M$. Enfin "le $\mathbb R$ de $\mathsf{N}$" n'est pas en bijection avec $\omega$ (en tout cas $\mathsf{N}$ le pense).
Pour ta dernière question, ça dépend du forcing employé. Ce qui est vrai c'est que les ordinaux du petit modèle sont toujours des ordinaux dans le grand, c'est juste qu'ils peuvent avoir perdu en cardinalité ou ne plus être des cardinaux car on a pu introduire plus de bijections. Classiquement (avec le forcing de Cohen) on ajoute des éléments à $\mathbb R$, de sorte que le $\mathbb R$ du grand modèle contient strictement celui du petit modèle.
- $\mathcal{D}_0(n) \equiv (n=0 \vee n=s(0))$
- pour tout entier intuitif non nul $k$ : $\mathcal{D}_k(n) \equiv$ "$n$ peut s'écrire comme un produit d'au plus $k$ nombres premiers".
- $\mathcal{D}(n) \equiv \mathcal{D}_0(n) \vee \mathcal{D}_1(n) \vee \mathcal{D}_2(n) \vee\dots \equiv$ "$n$ peut s'écrire comme un produit de nombres premiers (ou bien $n=0$ ou $1$)".
Par exemple $\mathcal{D}_2(4)$ est vrai, mais pas $\mathcal{D}_1(4)$. Le théorème fondamental de l'arithmétique énonce : $\forall n, \mathcal{D}(n)$.Les $\mathcal{D}_k$ peuvent s'écrire dans PA1 et on veut montrer que ce n'est pas le cas de $\mathcal{D}$. Considérons le langage $\{0,s,+,\times,c\}$ ($c$ est une constante) et la théorie $$\mathsf{PA1} \cup \{\mathcal{D}(c), \neg \mathcal{D}_0(c), \neg \mathcal{D}_1(c), \neg \mathcal{D}_2(c), \dots\}.$$
Elle est finiment satisfaisable (prendre un modèle de PA1 et poser $c=2^k$ pour $k$ assez grand) mais pas satisfaisable (car on peut montrer en théorie des ensembles que le théorème fondamental de l'arithmétique est vrai). Donc $\mathcal D$ ne peut pas être une formule du premier ordre d'après le théorème de compacité.
Est-ce correct ?
Cela impliquerait que le produit des r premiers nombres premiers, plus un, est un nombre premier. Ce n'est pas vrai.
2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031
Ce nombre est divisible par 59.
59 * 509 = 30031.
Donc il faut bien supposer qu'il n'y ait pas plus que r nombres premiers pour que cette démonstration marche.
Pour info, selon mes derniers souvenirs cette histoire était au programme de seconde il y a une dizaine d'années...
Son pote lui prouve, sans faire aucun calcul, que 2x3x5x7+1 admet forcément un diviseur premier, autre que 2,3,5,7.
Et tout le monde s'en tape de savoir si 211 est premier ou pas.
- tout nombre autre que 0 ou 1, est divisible par un nombre premier
- un nombre n'est pas un nombre premier, s'il est divisible par un nombre premier autre que lui-même, sinon c'en est un.
Comme il n'y a, par hypothèse, que r nombres premiers, et que ce nouveau nombre p1*...pr + 1, n'est pas divisible par aucun d'eux, nous avons donc une contradiction, ou bien avec la première proposition (nous avons un nombre qui ne serait divisible par aucun nombre premier), ou bien avec la deuxième.
Mais oui, c'est vrai que ce n'est qu'un pas de plus pour dire que p1 ... pr + 1 prouve l'existence d'un autre nombre premier que p1 ... pr.
Je ne l'avais jamais vu comme ça, effectivement. "s'il y a r nombres premiers, alors il y en a r+1".
http://www.les-mathematiques.net/phorum/read.php?16,1926158,1928132#msg-1928132
Même si pour les nombres premiers c'est personnalisément facile, le cas général, plus lourd en terme de cabalistique, consistant à parler dans Peano des choses finies sans en oublier provient du fait que par un théorème dit "chinois", remixé en mode artihmétique, tu as tous "les débuts de suites", dans le sens suivant:
Pour toute suite $u$ à valeurs dans $\N$ et entier $n$, il existe $a,b,c$ tels que pour tout $i<n:$ $$
u_i = a\mod (ib+c).
$$ Exercice: définir dans le langage de Peano la relation binaire $$
(x,y) \mapsto [ y = 5^x ]$$
J'ai finalement vu le paradoxe de Skolem en cours de logique vendredi (:D. Enfin, ça n'était pas exactement le théorème de Löwenheim-Skolem, mais plutôt la preuve de "$\Phi \vdash \chi$ ssi $\Phi \vDash \chi$" qui utilise les témoins de Henkin. À la fin on déduisait que si $\sf ZF$ est cohérente alors elle possède un modèle dénombrable, donc la barrière intuitive du paradoxe de Skolem était bien là.
Et c'est marrant mais ce théorème qui avant me troublait beaucoup, je le trouve plutôt "rassurant" maintenant :
La personne qui fait des maths dans $\sf ZF$ n'a accès qu'à une quantité dénombrable de connaissances : elle ne peut formuler qu'un nombre dénombrable de théorème et elle ne peut définir qu'un nombre dénombrable d'objets alors qu'il peut exister beaucoup beaucoup plus d'objets.
Ça donne un peu le vertige tous ces objets qui peuvent être présents dans le modèle mais qu'on ne peut pas définir. Mais là on a "construit" un modèle avec le minimum d'objets : $\varnothing$ + tous les ensembles qui doivent exister d'après les axiomes existentiels de $\sf ZF$, et pas plus.
:-)
Quel cursus suis-tu ? A quelle université ? Veux-tu me fournir un lien sur les UE, s'il te plait ? Tu peux me répondre par MP.
Bien cordialement,
Thierry
Tu te trompes : le modèle que tu as "construit" par Löwenheim-Skolem n'a aucune raison d'être minimal.
Je m'explique.
Tu verras dans la suite du cours qu'à partir d'un modèle $\mathbb{V}$ absolument quelconque de ZF, tu peux fabriquer l'univers des constructibles de Gödel, qu'on note $\mathbb{L}$. Très schématiquement, $\mathbb{L}$ est constitué de tous les ensembles que tu sais "fabriquer à la main". Et $\mathbb{L}$ est minimal au sens où tout modèle intérieur de $\mathbb{V}$, c'est-à-dire toute sous-classe transitive de $\mathbb{V}$ qui est modèle de ZF et qui contient les mêmes ordinaux que $\mathbb{V}$, contient $\mathbb{L}$.
Mais avec des techniques on peut montrer que $\mathbb{V}=\mathbb{L}$, qu'on appelle l'axiome de constructibilité, n'est pas conséquence de ZF. Autrement dit, si ZF est consistante elle admet un modèle, que j'appelle encore $\mathbb{V}$, qui satisfait $\mathbb{V} \neq \mathbb{L}$. Partant d'un tel modèle, en lui appliquant Löwenheim-Skolem tu vas exhiber un modèle dénombrable $M$ qui, par élémentarité, ne satisfait pas non plus l'axiome de constructibilité. En refaisant la construction de $\mathbb{L}$ à partir de $M$ tu vas obtenir un autre modèle dénombrable $\mathbb{L}^M \subsetneqq M$, donc $M$ n'est pas minimal.
Je me doutais que ce genre de message risquait d'arriver :-D. C'est aussi pour ça que c'est intéressant pour moi de poster dans "fondements & logique". ;-)
Déjà, on a rien "construit par Löwenheim-Skolem" puisque j'ai bien dit qu'on avait pas fait exactement le théorème de Löwenheim-Skolem (dont je n'ai pas compris l'énoncé en détails d'ailleurs). Du coup, je précise ce qu'on a fait pour être sûr qu'on soit d'accord là-dessus.
Soient $\def\L{{\cal L}} \L$ un langage et $\Phi$ une $\L$-théorie cohérente. On veut montrer que $\Phi$ possède un modèle. $\def\lene{\L{-}{\rm En}_\exists}$
Soit $\lene$ l'ensemble des $(x,\varphi)$ où $x$ est une variable et $\varphi$ est une $\cal L$-formule telle que ${\rm Varlibre}(\varphi)\subset\{x\}$. On note $\L'$ le langage $\L$ auquel on rajoute une constante $c_{(x,\varphi)}$ pour chaque $(x,\varphi)\in\lene$. Et on note $$\L^* = \bigcup_{n\in\Bbb N}\L^{\prime\cdots\prime}$$ (à chaque fois, on a $n$ apostrophes impriquées). Puis on pose $$H_{\L^*} = \{ ``(\exists x \; \varphi)\to \varphi[x:=c_{(x,\varphi)}]"\ \mid (x,\varphi)\in \L^*{-}{\rm En}_\exists \}$$ et on prend $\Phi^*$ une théorie complète qui contient $\Phi\cup H_{\L^*}$. Enfin, construit la $\L$-structure $\Bbb S$ dont les objets sont les $\L^*$-termes sans variable libre, quotientés par la relation d'équivalence "$t_1\sim t_2$ ssi $\Phi^* \vdash t_1=t_2$", et dont les constantes, les relations et les fonctions sont celles qu'on imagine raisonnablement.
Et on a : $\def\card{{\rm card}} \card(\Bbb S)\leqslant \max(\card(\L^*),\aleph_0)\leqslant \max(\card(\L),\aleph_0)$.
Bon, avant de commencer à chercher où ce que je disais peut capoter dans le raisonnement ci-dessus, j'ai besoin de clarifier trois trucs :
- C'est quoi un objet de ZF qui est constructible ? J'ai vu dans mon cours la définition de la définissabilité d'une partie d'une structure, mais je n'ai pas vu de notion similaire pour les objets de la structure. Est-ce que l'ensemble (au sens de ZF) $x$ est constructible lorsque la collection des objets $y$ de la structure vérifiant $y\in x$ est définissable ?
- Quand tu parles "d'axiome de constructibilité", c'est un vrai axiome en logique du premier ordre dans le langage de ZF ? On n'a pas besoin de faire appel à une quantification sur les formules ou quelque chose du genre ?
- Je n'ai pas compris le "par élémentarité". Ça veut dire quoi "élémentaire" dans ce contexte ?
Merci d'avance1- C'est une notion qui se définit dans le cadre de ZF. C'est pas trop compliqué: tu prends $\emptyset$, tu regardes l'ensemble de ses parties définissables, puis l'ensemble des parties définissables de ça, puis de ça, etc. Tu récurres ordinalement et tu obtiens $\mathbb L$, les constructibles. Bon, en principe faut un peu plus de détail parce qu'il faut préciser ce qu'on entend par définissable mais voilà, en idée c'est ça. Ensuite on montre que si $V$ est un modèle de ZF, le $\mathbb L$ construit à l'intérieur de $V$ est un modèle de ZFC (+GCH mais c'est pas important pour l'argument de Martial), et que lui vérifie "$V=\mathbb L$" (i.e. si tu reconstruis $\mathbb L$ à l'intérieur de $\mathbb L$, tu obtiens tout, ce qui n'est pas automatique a priori - mais pas compliqué à montrer)
2- Oui oui c'est un vrai axiome, pas besoin de quantification cheloue (en fait ça se cache dans les "détails" mentionnés juste au-dessus: tu ne prends que des formules internes à chaque étape, donc tout va bien)
3- Une extension $N\subset M$ de modèles est une extension élémentaire si pour toute formule $\varphi$ et tous $x_1,...,x_n \in N, N\models \varphi(x_1,...,x_n)$ si et seulement si $M\models \varphi(x_1,...,x_n)$. C'est un truc qui t'est assuré par Löwenheim-Skolem.
Je disais ça à cause du "tu te trompes" de Martial :-S. Mais je me rends compte que la définition de la constructibilité n'est pas du tout celle à la quelle je m'attendais. Par exemple, si j'ai bien compris, les grands cardinaux (s'il en existe dans le modèle considéré) sont constructibles puisque ce sont des ordinaux.
PS: J'ai en partie lu l'article Wikipédia sur les ensembles constructibles. J'ai arrêté ma lecture à cette phrase délirante de pédagogie : « On déduit que V = L est vrai dans L et dans tout L$\kappa$ qui est un modèle de ZF, des faits que le L de L et le V de L sont tous deux le vrai L et que le L de L$\kappa$ et le V de L$\kappa$ sont le vrai L$\kappa$ ». (:P)