Infinité de nombres premiers dans Peano

@Calli : Poirot m'a coupé l'herbe sous les pieds, alors je vais juste me contenter d'en rajouter une couche.
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$

Histoire de détendre l'atmosphère, ça me rappelle une vanne de Gabriel Sabbagh (que je salue au passage, c'est lui qui m'a fait aimer la logique) lors de son deuxième cours de théorie des modèles. Juste après nous avoir démontré un théorème "scotchant" il avait dit : "Oui, je sais, la première fois ça surprend. C'est comme la première fois qu'on voit un film X. Mais je vous rassure, avec le temps vous allez vous habituer".

@Calli : pour montrer qu'il n'existe pas de formule voulant dire "je suis un modèle infini de tel truc" tu devrais te renseigner sur le théorème de compacité.

$\newcommand{\u}{\mathcal U}$ Ce qui va suivre s'appelle "théorème de Los" sauf erreur.
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.

Je réponds à deux-trois bricoles :

- 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.

De mon téléphone et très fatigué je n'ai lu que 1er msg.

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.

@Calli : pour ta 1.a. imagine deux modèles $\mathsf{M} \subset \mathsf{N}$ de $\mathsf{ZF}$ avec $\in^{\mathsf M} = \in^{\mathsf N}_{\mid \mathsf M}$. On considère deux ensembles $A, B \in \mathsf{M}$, vu comme éléments de $\mathsf N$ et on suppose qu'il existe, dans $\mathsf N$, une bijection $f$ de $A$ sur $B$. Eh bien rien ne te garantit que $f \in \mathsf M$, et il se pourrait très bien que $A$ et $B$ ne soient pas équipotents dans $\mathsf M$ ! C'est exactement ce qu'il se passe quand on fait du forcing pour changer les valeurs des cardinaux. Par exemple partant d'un modèle de $\mathsf{ZFC}$ où $card(\mathbb R) = \aleph_1$, on peut construire un modèle plus grand où $card(\mathbb R) = \aleph_2$, et bien sûr aucune bijection entre $\mathbb R$ et $\aleph_2$ dans le grand modèle n'appartient au petit modèle.

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

Je tente une dernière explication du "paradoxe" de Skolem : prenons un modèle transitif dénombrable $\mathsf{M}$ de $\mathsf{ZFC}$ (si tant est que ça existe ;-) ). Dans ce modèle, il y a un élément $R$ qui est "le $\mathbb R$ du modèle", au sens où c'est l'élément de $\mathsf{M}$ défini comme l'ensemble des classes d'équivalence de suites de Cauchy de $\mathbb Q$, lui-même définit comme... Du point de vue "extérieur" où l'on se trouve, c'est-à-dire vu depuis un modèle $\mathsf{N}$ de $\mathsf{ZFC}$ tel que $\mathsf{M} \in \mathsf{N}$ et qui décrète "$\mathsf{M}$ est dénombrable", l'ensemble $R \in \mathsf{N}$ est dénombrable puisqu'il est infini (ça c'est absolu) et inclus dans $\mathsf{M}$ (à cause de la transitivité).

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.

@Patrick123: 30031 est divisible par un nombre premier (on peut montrer par récurrence dans PA que tout nombre est divisible par un nombre premier) et ce nombre ne peut pas être parmi 2,3,5,7,11,13.

Pour info à l'époque je l'expliquais comme ça à mes élèves de seconde : on suppose l'existence d'un queum qui est très fort en raisonnement mais nul en calcul : il ne sait compter que jusqu'à 10, et croit que les seuls premiers sont 2, 3, 5, 7.
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.

Bon je n'ai pas encore lu le fil, ni regardé ce que t'a dit foys, mais je complète en réponse à :

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 ]$$

Bonjour Calli

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

Propos du paysan de Paris. Exhiber une suite infinie d'entiers naturels premiers entre eux deux à deux, ça ne répond pas à la question ? Or de ces suites, on en a, par exemple les $\mathcal F_n=2^{2^n}+1$.