diff options
| -rw-r--r-- | notes-mitro206.tex | 143 |
1 files changed, 131 insertions, 12 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index b013023..627b0dc 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -3356,7 +3356,7 @@ $G/\equiv$, on a bien $f(x) = f(x')$ ssi $x\equiv x'$). \section{Introduction aux ordinaux}\label{section-ordinals} -\subsection{Présentation informelle} +\subsection{Présentation informelle}\label{subsection-informal-description-of-ordinals} \thingy Les \index{ordinal}ordinaux sont une sorte de nombres, totalement ordonnés et même « bien-ordonnés », qui généralisent les entiers naturels en @@ -3743,8 +3743,10 @@ ordinal $\alpha$ : utilisable par tout le monde) reliant $\beta$ à $\beta'$ lorsque $\beta'<\beta$. Il s'agit du jeu de nim (cf. \ref{introduction-nim-game}) avec une seule ligne d'allumettes - ayant initialement $\alpha$ allumettes. Ce jeu s'appelle parfois le - \index{nimbre}« nimbre » associé à l'ordinal $\alpha$. + ayant initialement $\alpha$ allumettes (les allumettes sont bien + ordonnées et doivent être retirées \emph{par la droite} dans un + dessin comme au début de cette section). Ce jeu s'appelle parfois + le \index{nimbre}« nimbre » associé à l'ordinal $\alpha$. \item Deux jeux \emph{partisans} (=partiaux), où un joueur n'a aucun coup possible (il a donc immédiatement perdu si c'est à son tour de jouer, ce qui rend le jeu, pris isolément, encore plus inintéressant @@ -5627,15 +5629,16 @@ jeux combinatoires partisans (bien-fondés) généraux. Les nombres surréels sont par ailleurs remarquables en ce qu'ils généralisent \emph{à la fois} les ordinaux et les nombres réels (et contiennent des éléments surprenants comme $\omega-42$ ou -$\omega+\sqrt{2}$ ou $2\pi\omega$ ou $1/\omega$ ou $\sqrt{\omega}$). +$\omega+\sqrt{2}$ ou $2\pi\omega$ ou $1/\omega$ ou $\sqrt{\omega}$ +ou $\omega^{\sqrt{5}}$). -\begin{defin} +\begin{defn} Soit $\alpha$ un ordinal et $\sigma\colon\{\beta : \beta<\alpha\} \to -\{+1,-1\}$ une fonction quelconque définie sur les ordinaux $<\alpha$ -et à valeurs dans $\{+1,-1\}$ (on dira que $\sigma$ est une -\defin{suite de signes}). Le \index{surréel (nombre)}\defin{nombre - surréel} associé à ces données est le jeu combinatoire partisan -bien-fondé dont +\{+,-\}$ une fonction quelconque définie sur les ordinaux $<\alpha$ et +à valeurs dans $\{+,-\}$ (on dira que $\sigma$ est une \defin{suite de + signes} et que $\alpha$ est sa \textbf{longueur}). Le +\index{surréel (nombre)}\defin{nombre surréel} associé à ces données +est le jeu combinatoire partisan bien-fondé dont \begin{itemize} \item l'ensemble des positions est l'ensemble des ordinaux $\beta \leq \alpha$, @@ -5643,10 +5646,126 @@ bien-fondé dont c'est-à-dire que les voisins sortants de $\beta\leq\alpha$ sont les ordinaux $\beta'<\alpha$, \item l'arête $(\beta,\beta')$ est colorée en bleu si $\sigma(\beta') - = +1$ et el rouge si $\sigma(\beta') = -1$, et + = +$ et en rouge si $\sigma(\beta') = -$, et \item la position initiale est $\alpha$. \end{itemize} -\end{defin} +Lorsque la suite de signes $\sigma$ est constamment égale à $+$, le +nombre surréel défini est appelé nombre surréel associé à +l'ordinal $\alpha$. +\end{defn} + +\thingy Autrement dit, on peut considérer qu'on a affaire à une rangée +de $\alpha$ allumettes, mais cette fois-ci elles sont coloriées en +bleu ou rouge : les allumettes doivent être retirées par la droite, et +le joueur qui joue doit avoir la même couleur que l'allumette retirée +la plus à gauche (par exemple, si $\sigma(0)=+$, l'allumette la plus à +gauche est bleue et seul Blaise a le droit de retirer toutes les +allumettes d'un coup ; si $\sigma(1)=-$, l'allumette suivante est +rouge et Roxane a le droit de retirer toutes les allumettes à droite +de celle-là incluse, etc.). Au moins pour un ordinal $\alpha$ fini, +ce jeu peut être vu comme un cas particulier du jeu de Hackenbush +introduit en \ref{introduction-hackenbush}, pour un graphe formé d'une +seule tour verticale, en disposant les allumettes les unes sur les +autres plutôt qu'en ligne (dans ce cas, $\sigma(0)$ donne la couleur +de celle qui est le plus en bas et qui supporte toutes les autres, +$\sigma(1)$ donne la couleur de la suivante, etc.). + +Le cas particulier introduit en \ref{introduction-nimbers-and-numbers} +sous le nom de nombre surréel associé à l'ordinal $\alpha$ est bien le +cas où $\sigma$ est constamment $+$ (seul le joueur bleu peut jouer à +décroître l'ordinal, l'autre joueur ne peut jamais rien faire). + +L'opposé d'un nombre surréel défini par sa suite de signes s'obtient +en changeant tous les signes de la suite. + +\thingy Il est évident qu'un nombre surréel défini par une suite de +signes $\sigma$ est strictement positif lorsque $\sigma(0)=+$ (Blaise +peut gagner en un seul coup en retirant immédiatement toutes les +allumettes, c'est-à-dire en jouant vers la position $0$), et +strictement négatif lorsque $\sigma(0)=-$. Le seul nombre surréel qui +n'est ni strictement positif ni strictement négatif est $0$, défini +par l'ordinal $\alpha=0$ et la suite de signes vide. Autrement dit, +le signe d'un nombre surréel est donné par le premier signe de la +suite de signes. Un nombre surréel n'est jamais flou. + +En fait, on peut se convaincre que les nombres surréels sont +totalement ordonnés par l'ordre lexicographique sur leurs suites de +signes : si $x$ est défini par $\sigma$ de longueur $\alpha$ et $x'$ +par $\sigma'$ de longueur $\alpha'$, et si on appelle $\gamma$ la +longueur commune entre $\sigma$ et $\sigma'$ (c'est-à-dire le plus +grand ordinal $\leq\max(\alpha,\alpha')$ tel que $\sigma(\beta) = +\sigma'(\beta)$ si $\beta<\gamma$), alors on a $x<x'$ si et seulement +si $\sigma(\gamma) < \sigma(\gamma')$ où on convient que $- < +\mathrm{nd} < +$ avec $\mathrm{nd}$ signifiant « non défini » +(c'est-à-dire le cas où $\sigma$ ou $\sigma'$ a justement comme +longueur $\gamma$, de sorte que la valeur en $\gamma$ n'est pas +définie). Par exemple, l'ordre sur tous les nombres surréels de +longueur $\leq 2$ représentés par leurs suites de signes est donné par +$(--) < (-) < (-+) < () < (+-) < (+) < (++)$ (en fait, il s'agit des +nombres $-2 < -1 < -\frac{1}{2} < 0 < \frac{1}{2} < 1 < 2$). +L'égalité au sens de Conway entre deux nombres surréels ne peut se +produire que s'ils ont la même longueur et la même suite de signes. + +\thingy On peut montrer que la somme (i.e., la somme disjonctive, en +tant que jeux) de deux nombres surréels est égale au sens de Conway +(i.e., a la même valeur) qu'un (unique) nombre surréel : autrement +dit, les nombres surréels forment pour l'addition un sous-groupe des +jeux partisans. + +À titre d'exemple, le jeu $x$ défini par la suite de signes $(+-)$ +(c'est-à-dire de longueur $2$ avec $\sigma(0)=+$ et $\sigma(1)=-$ : +autrement dit, Blaise peut jouer vers le jeu nul $0 = ()$ et Roxane +peut jouer vers le jeu $1 = (+)$) vérifie $x+x \doteq 1$ : en effet, +on peut se convaincre que le second joueur quel qu'il soit a une +stratégie gagnante dans le jeu formé de la somme disjonctive de deux +copies de $(+-)$ et d'une copie de $-1 = (-)$ (l'opposé de +l'ordinal $1$) : par exemple, si Blaise commence à jouer dans $(+-) + +(+-) + (-)$, il joue efface forcément un des signes $+$ et le $-$ qui +suit, ce qui laisse $(+-) + (-)$ et Roxane gagne en jouant vers $(+) + +(-)$ ; tandis que si Roxane commence dans $(+-) + (+-) + (-)$, elle va +jouer soit vers $(+) + (+-) + (-)$ soit vers $(+-) + (+-)$, dans le +premier cas Blaise gagne en jouant $(+) + (-)$, dans le second c'est +encore plus facile. On dira donc que $x$ correspond au nombre réel +$\frac{1}{2}$. + +\thingy Il n'est cependant pas évident de calculer la suite de signes +de $x+x'$ à partir de celles de $x$ et de celle de $x'$. (Pour donner +un exemple, ajouter $1$ à un nombre surréel directement à partir de sa +suite de signes se fait de la façon — bien compliquée — suivante : on +commence par sauter tous les blocs de signes identiques dont la +longueur est multiple de $\omega$ ; si on arrive ainsi au bout de la +suite ou bien que le signe suivant est un $+$, on insère un $+$ à cet +endroit-là ; s'il y a au moins deux signes $-$, on en retire un ; s'il +y a un unique signe $-$, soit c'est le dernier de la suite auquel cas +on le retire, soit il est lui-même suivi d'un signe $+$, auquel cas on +remplace cette combinaison $-+$ par $+-$.) + +Les ordinaux se voient, comme on l'a déjà dit, comme les nombres +surréels dont la suite de signe n'a que des signes $+$ (l'addition sur +les nombres surréels ne redonne pas exactement l'addition usuelle sur +les ordinaux, puisque cette dernière n'est pas commutative, mais elle +n'est pas très éloignée : en fait, l'addition qu'on obtient est +l'addition terme à terme des formes normales de Cantor, c'est-à-dire +l'addition des mêmes puissances de $\omega$, opération également +appelée « somme naturelle » des ordinaux). + +Les nombres dyadiques (ceux de la forme $\frac{p}{2^k}$) se voient +comme les nombres surréels dont la suite de signes est de longueur +\emph{finie} (par exemple $\frac{1}{2} = (+-)$). Les nombres réels se +voient comme les nombres surréels dont la suite de signes et de +longueur $\leq\omega$ et qui ne se terminent pas par une infinité de +signes tous égaux (pour obtenir la suite de signes d'un nombre réel +strictement positif et qui n'est pas dyadique, on commence par mettre +un nombre de $+$ égal à sa partie entière, puis la séquence $+-$, puis +l'écriture binaire de la partie fractionnaire du nombre en remplaçant +$1$ par $+$ et $0$ par $-$). + +\thingy On peut même définir une multiplication sur les nombres +surréels qui font d'eux un corps totalement ordonné et « réel-clos » +(c'est-à-dire que, comme sur les réels, tout polynôme de degré impair +a une racine et que tout élément positif a une racine carrée). Cette +multiplication peut même être définie entre un nombre réel et [la + valeur d']un jeu partisan. |