Relation d'ordre sur $\N$

GG

Bonjour !
Petit challenge pascal : démontrer directement à l'aide des axiomes de Peano exclusivement qu'il existe au plus une relation d'ordre sur $\N$ vérifiant $n < n^+$ pour tout entier naturel $n$ ($n^+$ étant le successeur de $n$).
Cela m'a pris un temps fou pour trouver une preuve qui me satisfasse et je serais intéressé et curieux de connaître votre démarche, peut-être plus satisfaisante que la mienne.

Chaurien

https://www.academie-francaise.fr/challenge

GG

@Chaurien,    Figure-toi qu'avant de taper le mot "challenge" sur mon clavier, j'ai ouvert mon "Petit Robert" pour m'assurer que je ne commettais pas un monstrueux et impardonnable anglicisme. Cela ne m'a pas semblé être le cas, et j'ai écrit le mot.
Serais-je passé, à mon corps défendant, du côté obscur de la Force ?!

rémi

https://www.dictionnaire-academie.fr/article/A9C1505

gerard0

De l'art de faire dévier un fil de discussion.

Médiat_Suprème

On sait que les modèles non-standard de l'arithmétique de Peano sont de la forme $\mathbb{M} = \mathbb{N} \oplus \mathbb{Q} \times \mathbb{Z}$, pour la relation d'ordre, où $\mathbb{Q} \times \mathbb{Z}$ est muni de l'ordre lexicographique., si on inverse l'ordre sur $\mathbb Q$, il me semble qu'on obtient une deuxième relation d'ordre qui vérifie $n < s(n)$ (et on pourrait compliquer encore un peu).

AlainLyon

Les ordres signifiants sont ceux compatibles avec l'addition, hors or l'addition et les entiers naturels peuvent être définis par n+1=s(n), n+2=s(s(n)) puis par le principe d'induction appelé aussi récurrence, la relation d'ordre telle que n<s(n)<s(s(n))<s(s(s(n))) est alors la seule compatible avec l'addition se démontre alors par récurrence grâce à l'axiome : toute partie non vide des entiers a un plus petit élément pour la relation d'ordre précédente :  l'ajout de structure permet de montrer l'unicité de la relation d'ordre compatible avec l'addition!

Martial

@AlainLyon : justement @GG veut qu'on n'utilise que les axiomes de Peano (je pense qu'il fait référence à l'arithmétique de Peano du premier ordre PA1). Or, dans cette dernière l'axiome "toute partie non vide admet un plus petit élément" est faux en général, donc ton raisonnement ne tient pas. 

Pire, il est pour ainsi dire trivial que, à isomorphisme près, le seul modèle de PA1 qui vérifie cet axiome est le modèle standard.

AlainLyon

@Martial modèle standard appartient au domaine de la physique des particules. Par ailleurs il existe ce qu'on appelle l'analyse non-standard laquelle consiste à adjoindre aux nombres réels des infinitésimaux (par exemple des nombres non nuls plus petits que tous les réels positifs et non nuls) on utilise pour cela des axiomes supplémentaires à ceux de ZFC : donc si ZFC est inconsistant l'usage de l'analyse non-standard doit pouvoir démontrer P et non P

pour au moins un énoncé P!

Médiat_Suprème

Bonjour Martial
Quel effet cela fait-il d'être totalement incompris ?   
Moi, dans ce cas précis, j'en tirerais gloire 

Martial

@AlainLyon : tu dis n'importe quoi ! La physique des particules n'a rien à voir là-dedans. Ce que j'appelle le modèle standard c'est simplement l'objet $\mathbb{N}$ avec lequel on "deal with" depuis le CP. Et il n'y a pas besoin de ZFC pour répondre à la question posée initialement (voir de que dit @Médiat_Suprème plus haut).

Je te remercie pour ton cours mais je sais ce qu'est l'analyse non standard. L'ANS (ou IST Nelson) est une extension conservative de ZFC, donc on peut aussi écrire la réciproque de ce que tu écris : si IST est inconsistante, alors $ZFC \vdash 0=1$.

gerard0

Peut-on considérer Alain Lyon comme un énorme poisson d'avril qui se croit le premier avril tous les jours de l'année ? Ce serait rassurant sur son fonctionnement intellectuel. Car sinon ...

Martial

@gerard0 : Bien vu ! Mais peut-être que dans l'univers d'Alain Lyon il y a un nombre non standard de jours (et donc aussi de 1er avril) dans l'année !

GG

Au vu des commentaires, je me rends compte que je n'ai pas été suffisamment clair.

Je me place dans la théorie des ensembles usuelle. Je considère un ensemble $\N$ dont les éléments s'appellent entiers (naturels) et qui satisfait les cinq axiomes suivants :

1) $0$ est un entier.

2) à tout entier $n$ est associé un entier appelé successeur de $n$ et noté $n^+$.

3) $0$ n'est le successeur d'aucun entier.

4) deux entiers qui ont le même successeur sont égaux.

5) Toute partie de $\N$ qui contient $0$ et $n^+$ en même temps que $n$ coïncide avec $\N$.

Le défi (j'ai assimilé la leçon !) est d'établir que deux relations d'ordre strict sur $\N$ $R$ et $S$ qui vérifient $n R n^+$ et $n S n^+$ pour tout entier $n$ sont équivalentes, et ce, sans introduire d'addition ou d'autres opérations.

Médiat_Suprème

Il s'agit donc de Peano du second ordre, ce qui n'était pas clair dans le message #1

GG

oui, désolé.

Martial

@Médiat_Suprème : Effectivement.

@GG : donc ce que j'ai écrit plus haut est nul et non avenu... sauf, bien sûr, quand je dis à @AlainLyon qu'il raconte n'importe quoi, ce qui n'est pas vraiment un scoop à proprement parler, lol.

Dom

$R$ et $S$ sont égales plutôt, non ? Sinon que cache ce mot « relations d’ordre équivalentes ». 

GG

@Dom, oui, oui, Une relation binaire sur $\N$ est une partie $R$ de $\N$ x $\N$. Quand on note $x R y$, c'est pour dire que $(x, y) \in R$. C'est donc la même chose de dire que $R$ et $S$ sont égales ou que $R$ et $S$ sont équivalentes, c'est-à-dire $x R y \Leftrightarrow x S y$ pour tous $x, y \in \N$.

Dom

Ok. Je pensais qu’il pouvait être dangereux de parler de « relations équivalentes » par proximité sémantique de « relation d’équivalence » surtout quand on parle de relations binaires. Dont acte. 

GG

Mon petit défi n'a pas eu beaucoup de succès ! Ce que je comprends tout à fait parce que ce sujet est plus le reflet de mes marottes qu'un résultat mathématique intéressant. Même s'il y a une histoire personnelle derrière, considérez-le seulement comme un petit exercice amusant de récurrence, et je compte sur vous pour détecter mes éventuelles erreurs.

soit $x \leqslant y$ une relation d'ordre naturel sur $\N$, i.e. telle que $n < n^+$ pour tout entier $n$.

On montre immédiatement par récurrence que $0 \leqslant x$ pour tout entier $x$.

$n^+$ s'appelle le successeur de $n$. Dans le contexte d'une relation d'ordre, on appelle (aussi) successeur de $n$ (s'il existe) le plus petit entier (strictement) supérieur à $n$, et prédécesseur de $n$ (s'il existe) le plus grand entier (strictement) inférieur à $n$.

Il se trouve que pour tout entier $n$, $n^+$ est le successeur de $n$ (autrement dit $n < x \implies n^+ \leqslant x$ pour tout $x$), et que pour tout entier $n$, $n$ est le prédécesseur de $n^+$ (autrement dit $x < n^+ \implies x \leqslant n$ pour tout $x$), mais ce n'est pas facile à montrer. Ce qui n'est pas trop dur à prouver, c'est que l'un de ces énoncés se déduit de l'autre au moyen d'une récurrence. Malheureusement, les deux récurrences ne portent pas sur la même lettre et l'on ne peut espérer montrer simultanément les deux énoncés par une récurrence. Sauf que ... l'on peut quand même grâce à une seconde récurrence imbriquée, et c'est ça qui m'a longtemps bloqué !

Montrons par récurrence sur $n$ que pour tous entiers $n$ et $x$ on a ($n < x^+ \implies n \leqslant x$) et ($n < x \implies n^+ \leqslant x$).

$\square$ Pour $n = 0$, la première implication est vraie. Montrons par récurrence sur $x$ que l'on a $0 < x \implies 1 \leqslant x $. C'est vrai pour $x = 0$. Supposons-le vrai pour $x$. Ou bien $x = 0$ et $x^+ = 1$, ou bien $x > 0$ et $1 \leqslant x < x^+$. Dans les deux cas on a $1 \leqslant x^+$ et donc $0 < x^+ \implies 1 \leqslant x^+$.

Supposons la relation initiale vraie pour $n$ et supposons $n^+ < x^+$. On a $n < n^+ < x^+$ et donc $n \leqslant x$. Ou bien $n = x$, ce qui est exclus, ou bien $n < x$ et $n^+ \leqslant x$. Ainsi $n^+ < x^+ \implies n^+ \leqslant x$ pour tout $x$. Il reste à montrer par récurrence sur $x$ que $n^+ < x \implies n^{++} \leqslant x$.

C'est vrai pour $x = 0$. Supposons-le vrai pour $x$ et supposons $n^+ < x^+$. On a alors $n^+ \leqslant x$ et ou bien $n^+ = x$ d'où $n^{++} = x^+$, ou bien $n^+ < x$ et $n^{++} \leqslant x < x^+$. Dans les deux cas on a $n^{++} \leqslant x^+$ et donc $n^+ < x^+ \implies n^{++} \leqslant x^+$. Finalement, la relation initiale est vraie pour $n^+$. $\square$

Il reste à montrer que pour deux relations d'ordre naturel strict sur $\N$ $R$ et $S$, $x R y \Leftrightarrow x S y$ pour tous entiers $x$ et $y$.

Montrons par récurrence sur $n$ que pour tous $n$ et $x$, on a $x R n \implies x S n $.

C'est vrai pour $n = 0$. Supposons-le vrai pour $n$, et supposons $x R n^+$. On a $x R n$ ou $x = n$ (théorème précédent). Dans le premier cas, on a $x S n$ et donc $x S n^+$. Et dans le second cas, on a aussi $x S n^+$. La récurrence est démontrée. En changeant le rôle de $R$ et de $S$, on montre l'implication réciproque et l'équivalence de $R$ et de $S$ (ou l'égalité de $R$ et de $S$, pour Dom )