Se connecter

Savoir & Culture

Cours et Devoirs

Sujet : Construction des entiers naturels
1
PalaceCesar
Niveau 24
07 novembre 2022 à 18:10:12

Bonjour à tous !

J'essaye de comprendre comment on peut représenter l'ensemble des entiers naturels dans la théorie des ensembles Z (ou ZF mais je ne pense pas qu'il soit nécessaire d'avoir le schéma de remplacement pour ce qui va suivre). De ce que j'ai compris, on commence par coder les entiers de la façon suivante:

0 := {}, 1 := { {} } = {0}, 2 := { {}, { {} } } = {0,1} 3 := {0,1,2}, etc.

Dit autrement, on considère la fonction successeur s donnée par s(x) = x U {x} (qui est bien définie via les axiomes de la paire et de la réunion) et on code les entiers de la façon suivante:

0 := {}, 1 := s(0), 2 := s(1) = s(s(0)) 3 := s(2) = s(s(s(0))), etc.

Je cherche à montrer qu'il existe un ensemble dont les éléments sont EXACTEMENT les ensembles définis de cette façon, càd obtenus en appliquant un nombre fini de fois la fonction s à partir de l'ensemble vide. Pour cela, j'ai vu qu'on commençait d'abord par admettre l'existence d'un ensemble contenant l'ensemble vide et clos par application du successeur (c'est l'axiome de l'infini) et qu'ensuite on définissait l'ensemble des entiers naturels comme étant l'intersection de tous les ensembles contenant l'ensemble vide et clos par successeur.

On arrive enfin à ma question :p) . Bien qu'il soit clair que l'intersection de tous ces ensembles est un ensemble qui contient tous les entiers définis ci-dessus, je n'arrive pas à me convaincre qu'il ne puisse pas y avoir autre chose dedans, càd un élément qui n'est pas de la forme s...s(0) avec un nombre fini de s. Autrement dit , je cherche à montrer que tout élément de mon intersection puisse s'écrire comme s...s(0).

Merci d'avance pour votre aide !

DonDoritos25
Niveau 9
07 novembre 2022 à 20:50:21

En fait, c'est le principe de récurrence (qui vient par définition de N comme le plus petit ensemble inductif). L'ensemble des éléments de la forme s^n(0) est un sous-ensemble inductif de N, donc c'est N lui-même. Tous les éléments de N sont donc de la forme s^n(0).

PalaceCesar
Niveau 24
07 novembre 2022 à 20:58:41

Le 07 novembre 2022 à 20:50:21 :
En fait, c'est le principe de récurrence (qui vient par définition de N comme le plus petit ensemble inductif). L'ensemble des éléments de la forme s^n(0) est un sous-ensemble inductif de N, donc c'est N lui-même. Tous les éléments de N sont donc de la forme s^n(0).

Oui c'est justement sur ça que je bloque, comment montrer que la collection des éléments de la forme s^n(0) forme bien un ensemble (je me prends la tête pour rien je sais...) :non2: Intuitivement, je me dis que l'intersection de tous les ensembles inductifs, ça ne peut être que ça mais il me manque un truc pour que ce soit clair dans ma tête...

DonDoritos25
Niveau 9
07 novembre 2022 à 21:00:32

Avant bien sûr, tu dois définir les suites récurrentes (en montrant par récurrence que tu peux définir la suite sur les segments initiaux de N).

Comme ça tu donnes un sens aux applications s^n : N ---> N, puis tu définis par compréhension {s^n(0) avec n dans N} = {k dans N t.q. il existe n dans N tel que k = s^n(0)}

PalaceCesar
Niveau 24
07 novembre 2022 à 21:10:38

Le 07 novembre 2022 à 21:00:32 :
Avant bien sûr, tu dois définir les suites récurrentes (en montrant par récurrence que tu peux définir la suite sur les segments initiaux de N).

Comme ça tu donnes un sens aux applications s^n : N ---> N, puis tu définis par compréhension {s^n(0) avec n dans N} = {k dans N t.q. il existe n dans N tel que k = s^n(0)}

Ok faut que je réfléchisse un peu à cette partie là :hap: Juste pour être sûr, le symbole N de ton message fait référence à l'intersection des ensembles inductifs c'est bien ça ?

Peut être que ma difficulté vient du fait que j'ai du mal à distinguer les entiers naturels intuitifs de ceux que j'essaye de définir :(

PalaceCesar
Niveau 24
07 novembre 2022 à 21:31:45

D'ailleurs je viens de penser à un truc: si on prend pas l'axiome de fondation dans notre système, ça serait pas possible que dans le N qu'on a construit, on ait un ensemble dégueulasse de la forme { { { .. .} } } (des accolades infinies imbriquées ) ?

DonDoritos25
Niveau 9
07 novembre 2022 à 21:39:19

N = ensemble des entiers naturels = plus petit ensemble inductif (contient vide et stable par successeur) :hap:

Quand on définit les entiers naturels, on procède par étapes à chaque fois :

1) Il existe un ensemble inductif S_0 [c'est l'axiome de l'infini].
2) Si S est inductif, on définit N_S comme l'intersection des sous-ensembles inductifs de S. Alors, N_S est inductif.
3) Si S et T sont inductifs, alors S inter T est encore inductif.
4) Si S et T sont inductifs, alors N_S = N_T.

Théorème-Définition. Il existe un plus petit ensemble inductif, noté N.

Une fois qu'on a notre définition, on doit définir les suites récurrentes. Peut-être avant, il faut définir la relation d'ordre sur N (qui est l'inclusion) et vérifier qu'elle se comporte comme il faut avec la fonction successeur (et que N est totalement ordonné avec).

Théorème. Soit X un ensemble. Soit x un élément de X. Soit f : X ---> X une application. Alors, il existe une unique suite (x_n) telle que x_0 = x et pour tout entier naturel n, x_s(n) = f(x_n).

Les suites itératives permettent ensuite de définir toutes les suites récurrentes que l'on veut grâce à la technique du stacking.

Si on a une application f : (X) x N ---> X avec (X) l'ensemble des suites finies d'éléments de X (c'est un ensemble si on regarde ces suites comme des graphes fonctionnels, car ce sont des sous-ensembles de N x X) on peut définir une unique suite (x_n) telle que x_0 = x et x_s(n) = f(x_0,...,x_n; n) à partir de l'immonde fonction (f) : (X) x N ---> (X) x N définie par (f)(x_0,...,x_n;n) = ((x_0,...,x_n,f(x_0,...,x_n;n)), s(n)) puis en prenant la première section de la suite itérative obtenue en partant de la donnée (x; 0). :hap:

Avec ça on peut définir l'addition, la multiplication, et tout le bordel chiant qui vient avec les entiers naturels (les ensembles finis, les composés dans un monoïde, les formules d'associativité, etc).

Bref, on peut définir les applications s^n : N ----> N par la relation de récurrence s^0 = id_N et s^s(n) = s o s^n. Puis l'ensemble des s^n(0) existe (on le définit en compréhension), il contient 0 car 0 = s^0(0) et est inductif car s(s^n(0)) = s^s(n)(0) par construction. Donc N = {s^n(0) | n dans N}, il manque personne. :hap:

DonDoritos25
Niveau 9
07 novembre 2022 à 21:50:18

Je me suis planté dans la définition de (f) mais on peut définir astucieusement une fonction pour construire les suites par itération. :hap:

On définit à la place (X) comme l'ensemble des paires (S, n) avec S une suite finie définie sur [[0,n]] à valeurs dans X, puis avec f : (X) ----> X donnée on construit nos suites par itération avec (f) : (X) ----> (X).

PalaceCesar
Niveau 24
07 novembre 2022 à 21:57:46

Super ça répond parfaitement à ma question ! :gni: Merci beaucoup d'avoir pris le temps de me répondre !

DonDoritos25
Niveau 9
07 novembre 2022 à 22:07:05

La construction des entiers naturels n'est pas très fun, mais faut la faire au moins une fois dans sa vie. Perso, j'ai appris avec le livre Naive Set Theory de Paul Halmos, mais le bouquin est assez expéditif ! Là c'est les grandes lignes de la construction de N, écrire les détails peut bien t'occuper quelques semaines :rire:

Jacana
Niveau 10
07 novembre 2022 à 22:25:57

Il existe des modèles non-standards de ZFC où l'ensemble N peut contenir d'autres éléments que le N du niveau méta.

Cf par exemple cette discussion.
https://mathoverflow.net/questions/40821/existence-of-an-omega-nonstandard-model-of-zfc-from-compactness

Le dernier commentaire est intéressant car il explique en quoi ça ne contredit pas tout ce qu'a raconté DonDoritos. En particulier quand on définit l'ensemble {s^n(0) | n dans N}, le "n dans N" peut être non standard contrairement à ce qu'on s'imagine.

DonDoritos25
Niveau 9
07 novembre 2022 à 22:48:29

Les modèles non-standards des entiers naturels existent parce que les axiomes de Peano ne suffisent pas à « borner » les entiers naturels. Ici, avec l'axiome de l'infini on construit le plus petit modèle des entiers naturels : les entiers naturels standards dans ZF.

Jacana
Niveau 10
08 novembre 2022 à 01:38:16

Je parle bien de modèle non standard de ZF, pas de Peano. L'idée pour en construire est la même (cf le lien).

Le fait qu'on ait un N non-standard, ça n'empêche pas que ce soit "le plus petit" interne à ce modèle. (Du coup, un tel modèle ne doit pas contenir le "vrai" N, qui serait plus petit).

On peut pas garantir que le N méta et le N du modèle soient les mêmes. Je sais pas si c'est ça que demandait l'OP, mais c'est comme ça que j'interprète cette phrase :

Je cherche à montrer qu'il existe un ensemble dont les éléments sont EXACTEMENT les ensembles définis de cette façon, càd obtenus en appliquant un nombre fini de fois la fonction s à partir de l'ensemble vide.

Si "fini" est celui du niveau méta, alors on ne peut pas montrer ça. On peut montrer qu'il existe un ensemble qui contient exactement les s^n(0) pour tout n dans N, mais c'est déjà le N interne au modèle, qui est potentiellement non standard

PalaceCesar
Niveau 24
08 novembre 2022 à 14:31:00

Oui j'entendais le mot fini dans son sens intuitif en écrivant cela :p)

Du coup je me pose la question, comment on construit le (car unique à isomorphisme prés ?) modèle standard de Peano si le N défini comme l'intersection des inductifs ne l'est pas forcément ? Ca dépend du modèle de ZF dans lequel je travaille, càd que cette construction sera bien le modèle standard attendu si je travaille dans le modèle standard de ZF ?

J'ai également pensé à une autre façon de procéder: définir l'ensemble des entiers naturels comme le plus petit ordinal infini ou (je pense que c'est équivalent et à mon sens plus simple à concevoir ?) la borne supérieur de l'ensemble des ordinaux finis. Ici, le terme fini pourrait être formalisé en disant qu'un ordinal est fini si et seulement si chacun de ses sous-ensembles non vides possède un maximum (je me base sur l'une des définitions d'ordinal fini de https://en.wikipedia.org/wiki/Ordinal_number ). Est-ce que cette définition est équivalente à celle de mon premier poste ?

Jacana
Niveau 10
08 novembre 2022 à 15:10:45

Du coup je me pose la question, comment on construit le (car unique à isomorphisme prés ?) modèle standard de Peano si le N défini comme l'intersection des inductifs ne l'est pas forcément ?

Le fait qu'il existe des modèles non-standards (de Peano ou de ZF) est inevitable, et ce n'est pas un problème. À l'intérieur de la théorie le N construit comme l'intersection des inductifs se comporte tout comme le N standard, et c'est tout ce qui importe. En fait, on ne peut même pas formuler l'assertion "le N interne n'est pas le même que le N méta". Ce n'est visible que de l'extérieur.

Tu peux t'amuser à imaginer d'autres constructions de N, mais ça ne changera rien il y aura toujours des modèles non standards. C'est pas grave.

Ca dépend du modèle de ZF dans lequel je travaille, càd que cette construction sera bien le modèle standard attendu si je travaille dans le modèle standard de ZF ?

On ne "travaille" pas vraiment "dans" un modèle : on travaille dans la théorie. Si on démontre une formule dans ZF, elle sera vraie dans tout modèle. Elle sera vraie dans le modèle standard, et aussi dans les modèles non standards. Ce qui nous intéresse c'est surtout le modèle standard, le reste c'est de la bizarrerie amusante mais ça n'empêche pas de faire quoi que ce soit.

PalaceCesar
Niveau 24
08 novembre 2022 à 19:42:16

D'accord, merci pour ta réponse :p)

Jacana
Niveau 10
08 novembre 2022 à 22:52:05

Une autre bizarrerie similaire c'est le théorème de lowenheim skolem, qui implique qu'il y a un modèle dénombrable de ZF. En particulier dans un tel modèle, l'ensemble R contient un nombre dénombrable d'éléments. Pourtant dans ZF on arrive bien à prouver que R est indenombrable, et donc ça doit être vrai dans tout modèle...

L'astuce c'est que ce R a beau être "dénombrable" au sens méta, il est "indenombrable" au sens interne au modèle : il n'y a pas de bijection entre le N du modèle et le R du modèle. De l'extérieur on sait que cette bijection existe, mais elle ne se trouve pas dans le modèle donc tout va bien...

https://fr.wikipedia.org/wiki/Paradoxe_de_Skolem

1
Sujet : Construction des entiers naturels
   Retour haut de page
Consulter la version web de cette page