summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex143
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.