summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex238
1 files changed, 125 insertions, 113 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index e19150f..6e7d13f 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -15,6 +15,10 @@
\usepackage{wasysym}
\usepackage{url}
%
+\usepackage{makeidx}
+%% Self-note: compile index with:
+%% xindy -M texindy -C utf8 -L french notes-mitro206.idx
+%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
@@ -54,8 +58,11 @@
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
\hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
+\newcommand{\defin}[2][]{\def\latexsucks{#1}\ifx\latexsucks\empty\index{#2}\else\index{\latexsucks}\fi\textbf{#2}}
+%
%
%
+\makeindex
\begin{document}
\title{Théorie(s) des jeux\\(notes provisoires)}
\author{David A. Madore}
@@ -122,17 +129,17 @@ quelques unes de ces théories des jeux.
\thingy Une tentative pour approcher la notion de jeu mathématique :
-le jeu possède un \textbf{état}, qui évolue dans un ensemble (fini ou
-infini) d'états ou \textbf{positions} possibles ; un certain nombre de
-\textbf{joueurs} choisissent, simultanément ou consécutivement, un
-\textbf{coup} à jouer parmi différentes \textbf{options}, en fonction
+le jeu possède un \defin{état}, qui évolue dans un ensemble (fini ou
+infini) d'états ou \defin{positions} possibles ; un certain nombre de
+\defin{joueurs} choisissent, simultanément ou consécutivement, un
+\defin{coup} à jouer parmi différentes \defin{options}, en fonction
de l'état courant, ou peut-être seulement d'une fonction de l'état
courant ; ce coup peut éventuellement faire intervenir un aléa (hasard
voulu par le joueur) ; l'état du jeu évolue en fonction des coups des
joueurs et éventuellement d'un autre aléa (hasard intrinsèque au
jeu) ; au bout d'un certain nombre de coups (fini ou infini), la règle
du jeu attribue, en fonction de l'état final, ou de son évolution
-complète, un \textbf{gain} à chaque joueur, ce gain pouvant être un
+complète, un \defin{gain} à chaque joueur, ce gain pouvant être un
réel (gain numérique), l'étiquette « gagné » / « perdu », ou encore
autre chose, et chaque joueur cherche en priorité à maximiser son gain
(i.e., à gagner le plus possible, ou à gagner tout court), ou dans le
@@ -142,14 +149,14 @@ Mais même cette définition très vague est incomplète !, par exemple
dans le cas des jeux différentiels, les coups n'ont pas lieu tour à
tour mais continûment.
-Une \textbf{stratégie} d'un joueur est la fonction par laquelle il
+Une \defin{stratégie} d'un joueur est la fonction par laquelle il
choisit son coup à jouer en fonction de l'état du jeu (ou de la
fonction de l'état qui lui est présentée), et d'aléa éventuel. On
peut ainsi résumer le jeu en : chaque joueur choisit une stratégie, et
la règle du jeu définit alors un gain pour chaque joueur. Les
stratégies peuvent être contraintes de différentes manières (par
exemple : être calculables par une machine de Turing). Une stratégie
-est dite \textbf{gagnante} si le joueur qui l'utilise gagne le jeu
+est dite \defin{gagnante} si le joueur qui l'utilise gagne le jeu
(supposé avoir une notion de « joueur gagnant ») quels que soient les
coups choisis par l'autre joueur.
@@ -163,7 +170,7 @@ ne connaissent pas toute la règle du jeu (voir « information
\subsection{Quelques types de jeux}
-\thingy Le \textbf{nombre de joueurs} est généralement $2$. On peut
+\thingy Le \defin{nombre de joueurs} est généralement $2$. On peut
néanmoins étudier des jeux multi-joueurs, ce qui pose des questions
d'alliances et compliquer la question des buts (un joueur peut être
incapable de gagner lui-même mais être en situation de décider quel
@@ -183,7 +190,7 @@ ici surtout aux situations où la communication est imparfaite.
Le cas de deux joueurs d'intérêts opposés est le plus courant : dans
le cas de gains numériques, on le modélise en faisant des gains d'un
-joueur l'opposé des gains de l'autre — on parle alors de \textbf{jeu à
+joueur l'opposé des gains de l'autre — on parle alors de \defin[somme nulle (jeu à)]{jeu à
somme nulle} ; ou bien la règle fera qu'un et un seul joueur aura
gagné et l'autre perdu (mais parfois, elle peut aussi admettre le
match nul).
@@ -192,7 +199,7 @@ Toute autre situation intermédiaire est possible. Mais on conviendra
bien que le but de chaque joueur est de maximiser son propre gain,
sans considération des gains des autres joueurs.
-\thingy Le jeu peut être \textbf{partial/partisan ou impartial}. Un
+\thingy Le jeu peut être \index{partial (jeu)}\index{partisan (jeu)}\defin[impartial (jeu)]{partial/partisan ou impartial}. Un
jeu impartial est un jeu où tous les joueurs sont traités de façon
équivalente par la règle (le sens de « équivalent » étant à définir
plus précisément selon le type de jeu).
@@ -208,14 +215,14 @@ coups séquentiels en cachant à chaque joueur l'information de ce que
l'autre a joué. La question \ref{question-preposing-moves} est
cependant plus intéressante.
-\thingy Le jeu peut être à \textbf{information parfaite} ou non. Un
+\thingy Le jeu peut être à \defin[information parfaite (jeu à)]{information parfaite} ou non. Un
jeu à information parfaite est un jeu dont la règle ne fait pas
intervenir le hasard et où chaque joueur joue séquentiellement en
ayant la connaissance complète de l'état du jeu et de tous les coups
effectués antérieurement par tous les autres joueurs.
(Cette notion est parfois distinguée de la notion plus faible
-d'\textbf{information complète}, qui souligne que les joueurs ont
+d'\defin[information complète (jeu à)]{information complète}, qui souligne que les joueurs ont
connaissance complète de la \emph{règle} du jeu, i.e., des gains
finaux et des options disponibles à chaque joueur. Néanmoins, on peut
formellement ramener un jeu à information incomplète en jeu à
@@ -244,7 +251,7 @@ jeux différentiels).
\subsection{Quelques exemples en vrac}
-\thingy Le jeu de \textbf{pile ou face} entre Pauline et Florian. On
+\thingy Le jeu de \defin{pile ou face} entre Pauline et Florian. On
tire une pièce non-truquée : si elle tombe sur pile, Pauline gagne, si
c'est face, c'est Florian. Aucun des joueurs n'a de choix à faire.
Chacun a une probabilité $\frac{1}{2}$ de gagner, ou une espérance de
@@ -304,7 +311,7 @@ enfants. Voir aussi la « battle of wits » du film \textit{Princess
Bride} à ce sujet.)
\thingy\label{rock-paper-scissors} Le jeu de
-\textbf{pierre-papier-ciseaux} : Alice et Bob choisissent
+\defin{pierre-papier-ciseaux} : Alice et Bob choisissent
simultanément un élément de l'ensemble $\{\textrm{pierre},\penalty0
\textrm{papier},\penalty0 \textrm{ciseaux}\}$. S'ils ont choisi le
même élément, le jeu est nul ; sinon, papier gagne sur pierre, ciseaux
@@ -352,7 +359,7 @@ Puits&$+1,-1$&$-1,+1$&$+1,-1$&$0,0$\\
\end{tabular}
\end{center}
-\thingy\label{prisonners-dilemma} Le \textbf{dilemme du prisonnier} :
+\thingy\label{prisonners-dilemma} Le \defin{dilemme du prisonnier} :
Alice et Bob choisissent simultanément une option parmi « coopérer »
ou « faire défaut ». Les gains sont déterminés par la matrice
suivante :
@@ -382,8 +389,8 @@ d'étude justifiant que la coopération est rationnelle, pour expliquer
en quoi le jeu itéré (=répété) diffère du jeu simple, ou pour montrer
que la notion d'équilibre de Nash est perfectible.
-\thingy\label{dove-or-hawk} Le jeu du \textbf{trouillard}, ou de la
-\textbf{colombe et du faucon}, obtenu en modifiant les gains du
+\thingy\label{dove-or-hawk} Le jeu du \defin{trouillard}, ou de la
+\defin[colombe et faucon]{colombe et du faucon}, obtenu en modifiant les gains du
dilemme du prisonnier pour pénaliser le double défaut (maintenant
appelé rencontre faucon-faucon) plus lourdement que la coopération
(colombe) face au défaut. Autrement dit :
@@ -426,7 +433,7 @@ probabilités respectives $\frac{L-X}{W-T + L-X}$ et $\frac{W-T}{W-T +
$\frac{1}{3}$), pour un gain espéré de $\frac{LW - TX}{W-T + L-X}$
(avec les valeurs ci-dessus : $\frac{4}{3}$).
-\thingy\label{battle-of-sexes} La \textbf{guerre des sexes}. Alice et
+\thingy\label{battle-of-sexes} La \defin{guerre des sexes}. Alice et
Bob veulent faire du sport ensemble : Alice préfère l'alpinisme, Bob
préfère la boxe, mais tous les deux préfèrent faire quelque chose avec
l'autre que séparément. D'où les gains suivants :
@@ -456,7 +463,7 @@ $\frac{1}{3}$), pour un gain espéré de $\frac{PQ-N^2}{P+Q-2N}$ (avec
les valeurs ci-dessus : $\frac{2}{3}$). Remarquablement, ce gain
espéré est inférieur à $Q$.
-\thingy Le \textbf{jeu du partage} ou \textbf{de l'ultimatum} : Alice
+\thingy Le \defin[partage (jeu du)]{jeu du partage} ou \defin[ultimatum (jeu de l')]{de l'ultimatum} : Alice
et Bob ont $10$ points à se partager : Alice choisit un $k$ entre $0$
et $10$ entier (disons), la part qu'elle se propose de garder pour
elle, \emph{puis} Bob choisit, en fonction du $k$ proposé par Alice,
@@ -544,7 +551,7 @@ est rendu impossible, quatre cas sont possibles (Alice a une stratégie
gagnante qui que soit le joueur qui commence, ou Bob en a une, ou le
premier joueur a une stratégie gagnante, ou le second en a une).
-\thingy\label{introduction-nim-game} Le \textbf{jeu de nim} : un
+\thingy\label{introduction-nim-game} Le \defin[nim (jeu de)]{jeu de nim} : un
certain nombre d'allumettes sont
arrangées en plusieurs lignes ; chacun leur tour, Alice et Bob
retirent des allumettes, au moins une à chaque fois, et autant qu'ils
@@ -591,7 +598,7 @@ $n_1,\ldots,n_r$ correspond à celle du jeu de nim où il y a
$n_1,\ldots,n_r$ allumettes sur les différentes lignes. C'est ce
point de vue qui suggère le type de jeux suivant :
-\thingy Jeux de \textbf{retournement de pièces}. Ici une position est
+\thingy Jeux de \defin{retournement de pièces}. Ici une position est
une rangée de pièces (qui pourront être numérotées, de la gauche vers
la droite, de $0$ à $N-1$ ou de $1$ à $N$, selon la commodité du jeu),
chacune en position « pile vers le haut » (qu'on notera $\mathtt{0}$)
@@ -661,7 +668,7 @@ lignes et de deux colonnes), avec la contrainte supplémentaire que
dans chaque cas la pièce la plus en bas à droite de celles retournées
doit passer de face à pile.
-\thingy Le jeu de \textbf{chomp} ou de la tablette de chocolat (ou
+\thingy Le jeu de \defin{chomp} ou de la tablette de chocolat (ou
gaufre) empoisonnée.
On part d'une « tablette de chocolat » de taille $m\times n$,
@@ -696,7 +703,7 @@ directement en mordant en $(i,j)$, il se ramènerait à cet état, les
rôles des joueurs étant inversés, donc il aurait une stratégie
gagnante, et cela signifie qu'il en a une dès le premier tour.
-\thingy\label{introduction-hackenbush} Le jeu de \textbf{Hackenbush}
+\thingy\label{introduction-hackenbush} Le jeu de \defin{Hackenbush}
impartial, bicolore, ou tricolore.
Dans ce jeu, l'état est défini par un dessin, plus précisément un
@@ -771,7 +778,7 @@ stratégie gagnante soit pour Alice, soit pour Bob, soit pour le
premier joueur, soit pour le second (l'ensemble du dessin ci-dessus,
par exemple, est gagnable par Alice).
-\thingy Le \textbf{jeu de l'hydre} : Hercule essaie de terrasser
+\thingy Le \defin[hydre (jeu de l')]{jeu de l'hydre} : Hercule essaie de terrasser
l'hydre. Le joueur qui joue l'hydre commence par dessiner (i.e.,
choisir) un arbre (fini, enraciné), la forme initiale de l'hydre.
Puis Hercule choisit une \emph{tête} de l'hydre, c'est-à-dire une
@@ -853,7 +860,7 @@ Hercule possède une stratégie gagnante, mais en fait Hercule gagne
Pourtant, en pratique, l'hydre peut facilement s'arranger pour
survivre un temps inimaginablement long.
-\thingy Le \textbf{jeu topologique de Choquet} : soit $X$ un espace
+\thingy Le \defin[Choquet (jeu topologique de)]{jeu topologique de Choquet} : soit $X$ un espace
métrique (ou topologique) fixé à l'avance. Uriel et Vania choisissent
tour à tour un ouvert non vide de ($X$ contenu dans) l'ouvert
précédemment choisi : i.e., Uriel choisit $\varnothing \neq U_0
@@ -867,7 +874,7 @@ peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une
stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vania qui en
a une.
-\thingy\label{introduction-gale-stewart-games} Les \textbf{jeux de
+\thingy\label{introduction-gale-stewart-games} Les \defin[Gale-Stewart (jeu de)]{jeux de
Gale-Stewart} (cf. section \ref{gale-stewart-games}) : soit $A$ un sous-ensemble de
$\mathbb{N}^{\mathbb{N}}$ ou de $\{0,1\}^{\mathbb{N}}$ ou de $[0,1]$.
Alice et Bob choisissent tour à tour un élément de $\mathbb{N}$ (dans
@@ -1000,16 +1007,16 @@ Enfin, on évoquera quelques jeux en vrac et des liens avec la logique.
\subsection{Généralités}
\begin{defn}\label{definition-game-in-normal-form}
-Un \textbf{jeu en forme normale} à $N$ joueurs est la donnée de $N$
+Un \index{forme normale (jeu en)}\defin[normale (jeu en forme)]{jeu en forme normale} à $N$ joueurs est la donnée de $N$
ensembles finis $A_1,\ldots,A_N$ et de $N$ fonctions
$u_1,\ldots,u_N\colon A \to \mathbb{R}$ où $A := A_1 \times \cdots
\times A_N$.
-Un élément de $A_i$ s'appelle une \textbf{option} ou \textbf{stratégie
+Un élément de $A_i$ s'appelle une \defin{option} ou \index{pure (stratégie)}\defin{stratégie
pure} pour le joueur $i$. Un élément de $A := A_1 \times \cdots
-\times A_N$ s'appelle un \textbf{profil de stratégies pures}. La
+\times A_N$ s'appelle un \defin{profil de stratégies pures}. La
valeur $u_i(a)$ de la fonction $u_i$ sur un $a\in A$ s'appelle le
-\textbf{gain} du joueur $i$ selon le profil $a$.
+\defin{gain} du joueur $i$ selon le profil $a$.
\end{defn}
Le jeu doit se comprendre de la manière suivante : chaque joueur
@@ -1025,12 +1032,12 @@ fait que les joueurs peuvent également jouer de façon probabiliste, ce
qui amène à introduire la notion de stratégie mixte :
\begin{defn}\label{definition-mixed-strategy-abst}
-Donné un ensemble $B$ fini d'« options », on appelle \textbf{stratégie
+Donné un ensemble $B$ fini d'« options », on appelle \index{mixte (stratégie)}\defin{stratégie
mixte} sur $B$ une fonction $s\colon B\to\mathbb{R}$ telle que
$s(b)\geq 0$ pour tout $b\in B$ et $\sum_{b\in B} s(b) = 1$ :
autrement dit, il s'agit d'une distribution de probabilités sur $B$.
-Le \textbf{support} de $s$ est l'ensemble des options $b\in B$ pour
+Le \defin[support (d'une stratégie mixte)]{support} de $s$ est l'ensemble des options $b\in B$ pour
lesquelles $s(b) > 0$.
Parfois, on préférera considérer la stratégie comme la combinaison
@@ -1055,7 +1062,7 @@ coordonnées égale à $1$.
Pour un jeu comme défini en \ref{definition-game-in-normal-form}, une
stratégie mixte pour le joueur $i$ est donc une fonction $s\colon A_i
\to\mathbb{R}$ comme on vient de le dire. On notera parfois $S_i$
-l'ensemble des stratégies mixtes du joueur $i$. Un \textbf{profil de
+l'ensemble des stratégies mixtes du joueur $i$. Un \defin{profil de
stratégies mixtes} est un élément du produit cartésien $S := S_1
\times \cdots \times S_N$.
@@ -1092,7 +1099,7 @@ Ceci conduit à faire la définition suivante :
Donné un jeu en forme normale comme
en \ref{definition-game-in-normal-form}, si $s := (s_1,\ldots,s_N) \in
S_1 \times \cdots \times S_N$ est un profil de stratégies mixtes, on
-appelle \textbf{gain [espéré]} du joueur $i$ selon ce profil la
+appelle \defin{gain [espéré]} du joueur $i$ selon ce profil la
quantité
\[
u_i(s) := \sum_{a\in A} s_1(a_1)\cdots s_N(a_N)\,u_i(a)
@@ -1117,7 +1124,7 @@ en \ref{definition-game-in-normal-form}, si $1 \leq i \leq N$ et si
$s_? := (s_1,\ldots,s_{i-1},s_{i+1},\ldots,s_N) \in S_1 \times \cdots
\times S_{i-1} \times S_{i+1} \times \cdots \times S_N$ est un profil
de stratégies mixtes pour tous les joueurs autres que le joueur $i$,
-on dit que la stratégie mixte $s_! \in S_i$ est une \textbf{meilleure
+on dit que la stratégie mixte $s_! \in S_i$ est une \defin{meilleure
réponse} (resp. la meilleure réponse stricte) contre $s_?$ lorsque
pour tout $t \in S_i$ on a $u_i(s_?,s_!) \geq u_i(s_?,t)$
(resp. lorsque pour tout $t \in S_i$ différent de $s_!$ on a
@@ -1126,8 +1133,8 @@ $S_1\times \cdots \times S_N$ obtenu en insérant $t \in S_i$ comme
$i$-ième composante entre $s_{i-1}$ et $s_{i+1}$.
Un profil de stratégies mixtes $s = (s_1,\ldots,s_N)$ (pour l'ensemble
-des joueurs) est dit être un \textbf{équilibre de Nash} (resp., un
-équilibre de Nash \emph{strict}) lorsque pour tout $1\leq i \leq N$,
+des joueurs) est dit être un \index{Nash (équilibre de)}\defin{équilibre de Nash} (resp., un
+équilibre de Nash \defin[strict (équilibre de Nash)]{strict}) lorsque pour tout $1\leq i \leq N$,
la stratégie $s_i$ pour le joueur $i$ est une meilleure réponse
(resp. la meilleure réponse stricte) contre le profil $s_{?i}$ pour
les autres joueurs obtenu en supprimant la composante $s_i$ de $s$.
@@ -1366,8 +1373,8 @@ minimiser $u$). Comme on l'a expliqué dans la preuve, on a
donc en fait il y a égalité partout : tout équilibre de Nash réalise
la même valeur $u(x_0,y_0) = \max_{x\in S_1} \min_{y\in S_2} u(x,y) =
\min_{y\in S_2} \max_{x\in S_1} u(x,y)$, qu'on appelle la
-\textbf{valeur} du jeu à somme nulle. On peut donc parler de
-\textbf{stratégie optimale} pour le joueur $1$, resp. $2$ pour
+\defin[valeur (d'un jeu à somme nulle)]{valeur} du jeu à somme nulle. On peut donc parler de
+\index{optimale (stratégie)}\defin{stratégie optimale} pour le joueur $1$, resp. $2$ pour
désigner une composante $x_0$, resp. $y_0$, d'un équilibre de Nash,
i.e., vérifiant $\min_{y\in S_2} u(x_0,y) = \max_{x\in S_1} \min_{y\in
S_2} u(x,y)$, resp. $\max_{x\in S_1} u(x,y_0) = \min_{y\in S_2}
@@ -1464,23 +1471,23 @@ joueurs.
Soit $X$ un ensemble non vide quelconque (à titre indicatif, les cas
$X = \{0,1\}$ et $X = \mathbb{N}$ seront particulièrement
intéressants). Soit $A$ un sous-ensemble de $X^{\mathbb{N}}$. Le
-\textbf{jeu de Gale-Stewart} $G_X(A)$ (ou $G_X^{\mathrm{a}}(A)$,
+\defin[Gale-Stewart (jeu de)]{jeu de Gale-Stewart} $G_X(A)$ (ou $G_X^{\mathrm{a}}(A)$,
cf. \ref{remark-player-names}) est défini de la manière suivante :
Alice et Bob choisissent tour à tour un élément de $X$ (autrement dit,
Alice choisit $x_0 \in X$ puis Bob choisit $x_1 \in X$ puis Alice
choisit $x_2 \in X$ et ainsi de suite). Ils jouent un nombre infini
de tours, « à la fin » desquels la suite $(x_0,x_1,x_2,\ldots)$ de
leurs coups définit un élément de $X^{\mathbb{N}}$ : si cet élément
-appartient à $A$, Alice \textbf{gagne}, sinon c'est Bob (la partie
+appartient à $A$, Alice \defin[gain]{gagne}, sinon c'est Bob (la partie
n'est jamais nulle).
Dans ce contexte, les suites finies $(x_0,\ldots,x_{\ell-1})$
-d'éléments de $X$ s'appellent les \textbf{positions} (y compris la
+d'éléments de $X$ s'appellent les \defin[position]{positions} (y compris la
suite vide $()$, qui peut s'appeler position initiale) de $G_X(A)$, ou
de $G_X$ vu que $A$ n'intervient pas ici ; leur ensemble
-$\bigcup_{\ell=0}^{+\infty} X^\ell$ s'appelle parfois l'\textbf{arbre}
-du jeu $G_X$. Une \textbf{partie} ou
-\textbf{confrontation}\footnote{Le mot « partie » peut malheureusement
+$\bigcup_{\ell=0}^{+\infty} X^\ell$ s'appelle parfois l'\defin{arbre}
+du jeu $G_X$. Une \defin{partie} ou
+\defin{confrontation}\footnote{Le mot « partie » peut malheureusement
désigner soit un sous-ensemble soit une partie d'un jeu au sens
défini ici : le mot « confrontation » permet d'éviter l'ambiguïté.}
de $G_X$ est une suite $(x_0,x_1,x_2,\ldots) \in X^{\mathbb{N}}$.
@@ -1506,7 +1513,7 @@ des joueurs sont échangés.
\begin{defn}\label{definition-strategies-for-gale-stewart-games}
Pour un jeu $G_X$ comme en \ref{definition-gale-stewart-game}, une
-\textbf{stratégie} pour le premier joueur (resp. le second joueur) est
+\defin{stratégie} pour le premier joueur (resp. le second joueur) est
une fonction $\varsigma$ qui à une suite finie (=position) de longueur
paire (resp. impaire) d'éléments de $X$ associe un élément de $X$,
autrement dit une fonction $\big(\bigcup_{\ell=0}^{+\infty}
@@ -1530,12 +1537,12 @@ $\tau((x_0,\ldots,x_{i-1}))$ si $i$ est impair.
Si on se donne une partie $A$ de $X^{\mathbb{N}}$ et qu'on convient
qu'Alice joue en premier : la stratégie $\varsigma$ pour Alice est
-dite \textbf{gagnante} (dans $G_X^{\mathrm{a}}(A)$) lorsque Alice
+dite \index{stratégie gagnante}\defin[gagnante (stratégie)]{gagnante} (dans $G_X^{\mathrm{a}}(A)$) lorsque Alice
gagne toute partie où elle joue selon $\varsigma$ comme premier
joueur, et la stratégie $\tau$ pour Bob est dite gagnante lorsque Bob
gagne toute partie où il joue selon $\tau$. Lorsque l'un ou l'autre
joueur a une stratégie gagnante, le jeu $G_X^{\mathrm{a}}(A)$ est dit
-\textbf{déterminé}.
+\defin[déterminé (jeu)]{déterminé}.
\end{defn}
\thingy Il est clair que les deux joueurs ne peuvent pas avoir
@@ -1566,7 +1573,7 @@ x_{\ell-1}^{\$} \cdots x_1^{\$} x_0^{\$} A$.)
\thingy\label{gale-stewart-positions-as-games} Toute position
$(x_0,\ldots,x_{\ell-1})$ d'un jeu de Gale-Stewart peut être considérée
comme définissant un nouveau jeu de Gale-Stewart consistant à jouer
-\textbf{à partir de là}, c'est-à-dire, comme si les $\ell$ premiers
+\defin{à partir de là}, c'est-à-dire, comme si les $\ell$ premiers
coups étaient imposés.
La notation \ref{unshifting-notation} permet d'en donner une
@@ -1589,7 +1596,7 @@ $G_X^{\mathrm{a}}(\underline{x}^\$ A)$ lorsque $\ell$ est impair.)
\thingy\label{gale-stewart-winning-positions} On dira qu'une position
$(x_0,\ldots,x_{\ell-1})$ d'un jeu de Gale-Stewart $G_X(A)$ est
-\textbf{gagnante} pour Alice lorsque Alice a une stratégie gagnante
+\defin[gagnante (position)]{gagnante} pour Alice lorsque Alice a une stratégie gagnante
dans le jeu qui consiste à jouer à partir de cette position
(cf. \ref{gale-stewart-positions-as-games}). On définit de même une
position gagnante pour Bob.
@@ -1703,7 +1710,7 @@ comme menant à la position $\underline{z}x :=
\begin{defn}\label{definition-product-topology}
Soit $X$ un ensemble non vide. Si $\underline{x} :=
(x_0,x_1,x_2,\ldots)$ est une suite d'éléments de $X$ et
-$\ell\in\mathbb{N}$, on appelle $\ell$-ième \textbf{voisinage
+$\ell\in\mathbb{N}$, on appelle $\ell$-ième \defin{voisinage
fondamental} de $\underline{x}$, et on note $V_\ell(\underline{x})$
l'ensemble de tous les éléments $(z_0,z_1,z_2,\ldots)$ de
$X^{\mathbb{N}}$ dont les $\ell$ premiers termes coïncident avec
@@ -1714,7 +1721,7 @@ finie $(x_0,\ldots,x_{\ell-1})$ (il ne dépend manifestement que de ces
termes), et on peut le noter $V_\ell(x_0,\ldots,x_{\ell-1})$ ou
$V(x_0,\ldots,x_{\ell-1})$.
-Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dit \textbf{ouvert}
+Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dit \defin{ouvert}
[pour la topologie produit] lorsque pour tout $\underline{x} \in A$ il
existe un $\ell$ tel que le $\ell$-ième voisinage fondamental
$V_\ell(\underline{x})$ de $\underline{x}$ soit inclus dans $A$.
@@ -1723,7 +1730,7 @@ contient une suite $\underline{x} := (x_0,x_1,x_2,\ldots)$, il existe
un rang $\ell$ tel que $A$ contienne n'importe quelle suite obtenue en
modifiant la suite $\underline{x}$ à partir du rang $\ell$.
-Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dit \textbf{fermé}
+Un sous-ensemble $A \subseteq X^{\mathbb{N}}$ est dit \defin{fermé}
lorsque son complémentaire $B := X^{\mathbb{N}} \setminus A$ est
ouvert.
\end{defn}
@@ -1986,9 +1993,9 @@ jeux ouverts peut s'appliquer dans ce contexte :
Soit $G$ un graphe orienté (c'est-à-dire un ensemble $G$ muni d'une
relation $E$ irréflexive dont les éléments sont appelés arêtes du
graphe, cf. \ref{definitions-graphs} ci-dessous pour les définitions
-générales) dont les sommets seront appelés \textbf{positions} de $G$,
-et soit $x_0$ un sommet de $G$ qu'on appellera \textbf{position
- initiale}. Le \textbf{jeu combinatoire impartial à information
+générales) dont les sommets seront appelés \defin[position]{positions} de $G$,
+et soit $x_0$ un sommet de $G$ qu'on appellera \index{initiale (position)}\defin{position
+ initiale}. Le \index{impartial (jeu)}\index{information parfaite (jeu à)}\defin[combinatoire (jeu)]{jeu combinatoire impartial à information
parfaite} associé à ces données est défini de la manière suivante :
partant de $x = x_0$, Alice et Bob choisissent tour à tour un voisin
sortant de $x$, autrement dit, Alice choisit une arête $(x_0,x_1)$
@@ -1998,16 +2005,16 @@ peut plus jouer, il a perdu ; si la confrontation dure un temps
infini, elle est considérée comme nulle (ni gagnée ni perdue par les
joueurs).
-Une \textbf{partie} ou \textbf{confrontation} de ce jeu est une suite
+Une \defin{partie} ou \defin{confrontation} de ce jeu est une suite
finie ou infinie $(x_i)$ de sommets de $G$ telle que $x_0$ soit la
position initiale et que pour chaque $i$ pour lequel $x_{i+1}$ soit
défini, ce dernier soit un voisin sortant de $x_i$. Lorsque le
dernier $x_i$ défini l'est pour un $i$ pair, on dit que le premier
-joueur \textbf{perd} et que le second \textbf{gagne}, tandis que
+joueur \textbf{perd} et que le second \defin[gain]{gagne}, tandis que
lorsque le dernier $x_i$ défini l'est pour un $i$ impair, on dit que
le premier joueur gagne et que le second perd ; enfin, lorsque $x_i$
est défini pour tout entier naturel $i$, on dit que la confrontation
-est nulle ou que les deux joueurs \textbf{survivent} sans gagner.
+est nulle ou que les deux joueurs \defin[survie]{survivent} sans gagner.
\end{defn}
\thingy\label{combinatorial-to-gale-stewart} Pour un jeu comme
@@ -2143,11 +2150,11 @@ se contenter de lire celle-ci.
\begin{defn}
Soit $G$ un graphe orienté
(cf. \ref{first-definition-impartial-combinatorial-game} et \ref{definitions-graphs}).
-Une \textbf{stratégie positionnelle} sur $G$ est une fonction
+Une \index{positionnelle (stratégie)}\defin{stratégie positionnelle} sur $G$ est une fonction
partielle $\varsigma\colon G \dasharrow G$ (i.e., une fonction définie
sur un sous-ensemble de $G$) telle que $\varsigma(x)$ soit, s'il est
défini, un voisin sortant de $x$ (s'il n'est pas défini, il faut
-comprendre que le joueur abandonne la partie). Une \textbf{stratégie
+comprendre que le joueur abandonne la partie). Une \index{historique (stratégie)}\defin{stratégie
historique} sur $G$ une fonction partielle $\varsigma
\big(\bigcup_{\ell=1}^{+\infty} G^\ell\big) \dasharrow G$, où
$\big(\bigcup_{\ell=1}^{+\infty} G^\ell\big)$ désigne l'ensemble des
@@ -2178,11 +2185,11 @@ $\tau(x_1,\ldots,x_i)$ si $i$ est impair (si $x_{i+1}$ n'est pas
défini, la suite s'arrête là).
La stratégie (positionnelle ou historique) $\varsigma$ est dite
-\textbf{gagnante pour le premier joueur} à partir de la position
+\index{stratégie gagnante}\defin[gagnante (stratégie)]{gagnante pour le premier joueur} à partir de la position
initiale $x_0$ lorsque le premier joueur gagne toute confrontation où
il joue selon $\varsigma$, c'est-à-dire que la confrontation est finie
et que le dernier $x_i$ défini l'est pour un $i$ impair. On définit
-de même une stratégie $\varsigma$ \textbf{survivante} (c'est-à-dire,
+de même une stratégie $\varsigma$ \index{stratégie survivante}\defin[survivante (stratégie)]{survivante} (c'est-à-dire,
permettant d'assurer au moins le nul) pour le premier joueur à partir
d'une position initiale $x_0$, c'est-à-dire que dans toute
confrontation où il joue selon $\varsigma$, soit la confrontation est
@@ -2222,7 +2229,7 @@ et où il joue selon $\varsigma$).
L'ensemble $\mathcal{S}$ est partiellement ordonné par l'inclusion (si
$\varsigma,\tau \in \mathcal{S}$, on dit que $\varsigma$
-\textbf{prolonge} $\tau$ et on note $\varsigma \supseteq \tau$ ou
+\defin{prolonge} $\tau$ et on note $\varsigma \supseteq \tau$ ou
$\tau \subseteq \varsigma$, lorsque l'ensemble de définition de
$\varsigma$ contient celui de $\tau$ et que $\varsigma$ et $\tau$
coïncident là où $\tau$ est définie : ceci signifie bien que
@@ -2528,27 +2535,27 @@ et \ref{scholion-well-founded-definition}).
\subsection{Graphes orientés bien-fondés}\label{subsection-well-founded-graphs}
\begin{defn}\label{definitions-graphs}
-Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et
+Un \defin{graphe orienté [simple]} est la donnée d'un ensemble $G$ et
d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un
ensemble de couples $(x,y)$ avec $x\neq y$) : si on préfère, il s'agit
d'un ensemble $G$ muni d'une relation $E$ irréflexive. Les éléments
-de $G$ s'appellent \textbf{sommets} et les éléments de $E$
-\textbf{arêtes} de $G$, et si $(x,y) \in E$, on dit qu'il y a une
+de $G$ s'appellent \defin[sommet]{sommets} et les éléments de $E$
+\defin[arête]{arêtes} de $G$, et si $(x,y) \in E$, on dit qu'il y a une
arête allant du sommet $x$ au sommet $y$, ou arête de source $x$ et de
-cible $y$, ou encore que $y$ est \textbf{atteint} par une arête de
-source $x$, ou encore que $y$ est un \textbf{voisin sortant} de $x$,
+cible $y$, ou encore que $y$ est \defin[atteindre]{atteint} par une arête de
+source $x$, ou encore que $y$ est un \index{sortant (voisin)}\defin{voisin sortant} de $x$,
et on notera $\outnb(x) = \{y : (x,y) \in E\}$ l'ensemble des voisins
sortants de $x$. Un sommet qui n'a pas de voisin sortant est
-appelé \textbf{puits} dans $G$.
+appelé \defin{puits} dans $G$.
-Un tel graphe est dit \textbf{fini} lorsque $G$ est fini (il est clair
-que $E$ l'est alors aussi). Il est dit \textbf{acyclique} lorsqu'il
+Un tel graphe est dit \defin[fini (graphe)]{fini} lorsque $G$ est fini (il est clair
+que $E$ l'est alors aussi). Il est dit \defin[acyclique (graphe)]{acyclique} lorsqu'il
n'existe pas de suite finie (« cycle ») $x_0,\ldots,x_{n-1}$ de
sommets telle que $(x_i,x_{i+1})$ soit une arête pour chaque $0\leq
i\leq n-1$, où on convient que $x_n = x_0$.
-Un graphe orienté (possiblement infini) est dit \textbf{bien-fondé} ou
-\textbf{progressivement fini} lorsqu'il n'existe pas de suite
+Un graphe orienté (possiblement infini) est dit \defin[bien-fondé (graphe)]{bien-fondé} ou
+\defin{progressivement fini} lorsqu'il n'existe pas de suite
$x_0,x_1,x_2,\ldots$ de sommets telle que $(x_i,x_{i+1})$ soit une
arête pour tout $i\in\mathbb{N}$ (i.e., aucun cycle ni chemin infini,
cf. ci-dessous).
@@ -2567,7 +2574,7 @@ celui de $\mathbb{N}$ dans lequel on fait pointer une arête de $i$
à $i+1$ pour chaque $i$.
\begin{defn}\label{definition-accessibility-downstream}
-Si $G$ est un graphe orienté on appelle \textbf{relation
+Si $G$ est un graphe orienté on appelle \defin[accessibilité]{relation
d'accessibilité} la clôture réflexive-transitive de la relation
donnée par les arêtes de $G$ : autrement dit, on dit que $y$ est
accessible à partir de $x$ lorsqu'il existe $x {=}
@@ -2576,13 +2583,13 @@ $x_{i+1}$ soit voisin sortant de $x_i$ (on autorise $n=0$,
c'est-à-dire que chaque sommet est toujours accessible à partir de
lui-même).
-On pourra aussi introduire la relation d'\textbf{accessibilité
+On pourra aussi introduire la relation d'\defin{accessibilité
stricte} qui est la clôture transitive : autrement dit, la
différence avec l'accessibilité définie ci-dessus est qu'on
impose $n>0$, i.e., on ne relie pas un sommet à lui-même.
L'ensemble des sommets accessibles à partir d'un sommet $x$
-s'appellera aussi l'\textbf{aval} de $x$ et pourra se noter
+s'appellera aussi l'\defin{aval} de $x$ et pourra se noter
$\downstr(x)$ (c'est donc la plus petite partie $P$ de $G$ telle que
$x\in P$ et $y\in P \limp \outnb(y)\subseteq P$,
cf. \ref{definition-downstream-closed-inductive}). On peut considérer
@@ -2604,19 +2611,19 @@ strictement décroissante.
Une relation d'ordre \emph{total} (strict) $>$ qui soit bien-fondée,
i.e., telle qu'il n'existe pas de suite infinie strictement
-décroissante, est appelée un \textbf{bon ordre}, ou définir un
-ensemble \textbf{bien-ordonné}.
+décroissante, est appelée un \defin{bon ordre}, ou définir un
+ensemble \defin[bien-ordonné (ensemble)]{bien-ordonné}.
\begin{defn}\label{definition-downstream-closed-inductive}
Si $G$ est un graphe orienté, on dira qu'un ensemble $P$ de sommets de
-$G$ est \textbf{aval-clos} lorsqu'il vérifie la propriété suivante :
+$G$ est \defin{aval-clos} lorsqu'il vérifie la propriété suivante :
« si $x$ est dans $P$ alors tout voisin sortant de $x$ est dans $P$ »
(soit $x\in P \limp \outnb(x)\subseteq P$ ; ou de façon équivalente,
« tout sommet accessible à partir d'un sommet de $P$ est encore
dans $P$ »,).
Réciproquement, on dira qu'un ensemble $P$ de sommets de $G$ est
-\textbf{aval-inductif} lorsqu'il vérifie la propriété suivante : « si
+\defin{aval-inductif} lorsqu'il vérifie la propriété suivante : « si
$x \in G$ est tel que tout voisin sortant de $x$ appartient à $P$,
alors $x$ lui-même appartient à $P$ » (i.e. « $P$ contient tout
sommet dont tous les voisins sortants sont dans $P$ »,
@@ -2767,7 +2774,7 @@ $\Phi(x, r) = \max\{r(y) : y\in\outnb(x)\} + 1$ avec $\Phi(x, r) = 0$
si $x$ est un puits, et qu'on appelle $\rho$ la fonction telle que
$\rho(x) = \Phi(x, \rho|_{\outnb(x)})$ dont l'existence et l'unicité
sont garanties par le théorème. Cette fonction $\rho$ s'appelle la
-\textbf{fonction rang} sur $G$, on dit que $\rho(x)$ est le rang (ou
+\defin[rang]{fonction rang} sur $G$, on dit que $\rho(x)$ est le rang (ou
rang bien-fondé) d'un sommet $x$. (Voir
aussi \ref{ordinal-valued-rank-and-grundy-function} pour une
généralisation.)
@@ -2800,7 +2807,7 @@ $\Phi(x, g) = \mex\{g(y) : y\in\outnb(x)\}$ et qu'on appelle
$\gamma$ la fonction telle que $\gamma(x) = \Phi(x,
\gamma|_{\outnb(x)})$ dont l'existence et l'unicité sont
garanties par le théorème. Cette fonction $\gamma$ s'appelle la
-\textbf{fonction de Grundy} sur $G$, on dit que $\gamma(x)$ est la
+\defin[Grundy (fonction de)]{fonction de Grundy} sur $G$, on dit que $\gamma(x)$ est la
valeur de Grundy d'un sommet $x$. (Voir
aussi \ref{ordinal-valued-rank-and-grundy-function} pour une
généralisation.)
@@ -2834,9 +2841,9 @@ f|_{\outnb(x)})$ dont l'existence et l'unicité sont garanties par le
théorème, et enfin on pose $P = \{x \in G : f(x) = \mathtt{P}\}$.
Les éléments de $P$ (i.e., les $x$ tels que $f(x) = \mathtt{P}$)
-seront appelés les \textbf{P-sommets} (ou P-positions) de $G$, tandis
+seront appelés les \defin[P-sommet]{P-sommets} (ou P-positions) de $G$, tandis
que les éléments du complémentaire $G\setminus P$ (i.e., les $x$ tels
-que $f(x) = \mathtt{N}$) seront appelés \textbf{N-sommets} (ou
+que $f(x) = \mathtt{N}$) seront appelés \defin[N-sommet]{N-sommets} (ou
N-positions) de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous
les voisins sortants sont des N-sommets, et un N-sommet est un
sommet qui a au moins un P-sommet pour voisin sortant}.
@@ -2919,7 +2926,7 @@ définie par le théorème \ref{well-founded-definition} peut se calculer
algorithmiquement de la façon suivante (si tant est que $\Phi$
elle-même est calculable) :
\begin{itemize}
-\item utiliser un algorithme de \textbf{tri topologique} (en ayant
+\item utiliser un algorithme de \defin{tri topologique} (en ayant
inversé le sens des arêtes pour se ramener à la convention usuelle)
pour trouver une numérotation des sommets de $G$ telle que pour
toute arête $(x,y)$ de $G$ le sommet $y$ précède $x$ dans la
@@ -2951,7 +2958,7 @@ L'ensemble des sommets d'un graphe orienté dont l'aval est bien-fondé,
autrement dit, l'ensemble des sommets $x$ tels qu'il n'existe pas de
suite $x_0,x_1,x_2,\ldots$ de sommets où $x_0 = x$ et où pour
chaque $i$ le sommet $x_{i+1}$ est atteint par une arête de
-source $x_i$, est appelé la \textbf{partie bien-fondée} du graphe.
+source $x_i$, est appelé la \defin{partie bien-fondée} du graphe.
\end{defn}
\thingy\label{trivial-remark-wfpart} Il sera utile pour la suite de
@@ -2994,11 +3001,11 @@ bien-fondée de $G$.
\thingy Pour pouvoir énoncer le théorème suivant, on aura besoin de
faire les rappels, définitions et remarques suivants. Une
-\textbf{fonction partielle} $A \dasharrow Z$, où $A$ est un ensemble
+\defin[partielle (fonction)]{fonction partielle} $A \dasharrow Z$, où $A$ est un ensemble
quelconque, n'est rien d'autre qu'une fonction définie $D \to Z$ sur
-une partie $D\subseteq A$ de $Z$ (appelée \textbf{ensemble de
+une partie $D\subseteq A$ de $Z$ (appelée \defin[définition (ensemble de)]{ensemble de
définition} de la partie). Si $f,g\colon A \dasharrow Z$ sont deux
-fonctions partielles, on dit que $f$ \textbf{prolonge} $g$ et on note
+fonctions partielles, on dit que $f$ \defin{prolonge} $g$ et on note
$f \supseteq g$ ou $g\subseteq f$, lorsque l'ensemble de définition
$D_f$ de $f$ contient celui $D_g$ de $g$ et que $f$ et $g$ coïncident
sur $D_f$ (ceci signifie bien que $f \supseteq g$ en tant qu'ensembles
@@ -3009,7 +3016,7 @@ d'un ordre partiel (sur l'ensemble des fonctions partielles $A
Enfin, si $\Phi$ est une fonction partielle elle-même définie sur
l'ensemble des fonctions partielles $A \dasharrow Z$ (cet ensemble est
$\bigcup_{D\subseteq A} Z^D$, si on veut), on dit que $\Phi$ est
-\textbf{cohérente} lorsque $\Phi(f) = \Phi(g)$ à chaque fois que $f$
+\defin[cohérente (fonction)]{cohérente} lorsque $\Phi(f) = \Phi(g)$ à chaque fois que $f$
prolonge $g$ et que $\Phi(g)$ est définie (autrement dit, une fois que
$\Phi$ est définie sur une fonction partielle $g$, elle est définie
sur tout prolongement de $g$ et y prend la même valeur que sur $g$ ;
@@ -3217,8 +3224,8 @@ Soit $G$ un graphe orienté bien-fondé. En utilisant le
théorème \ref{well-founded-definition} (modulo la remarque qui suit),
on définit alors une fonction $f$ sur $G$ par $f(x) = \{f(y) :
y\in\outnb(x)\}$. L'image $f(G)$ de $G$ par la fonction $f$ (c'est-à-dire
-l'ensemble des $f(x)$ pour $x\in G$) s'appelle l'\textbf{écrasement
- transitif} ou \textbf{écrasement de Mostowski} de $G$, tandis que
+l'ensemble des $f(x)$ pour $x\in G$) s'appelle l'\defin{écrasement
+ transitif} ou \defin{écrasement de Mostowski} de $G$, tandis que
$f$ s'appelle la fonction d'écrasement, et la valeur $f(x)$ (qui n'est
autre que l'écrasement transitif de l'aval de $x$ vu comme un graphe
orienté) s'appelle l'écrasement transitif du sommet $x$.
@@ -3250,14 +3257,14 @@ admettrons qu'il existe bien une unique fonction $f$ sur $G$ qui
vérifie $f(x) = \{f(y) : y\in\outnb(x)\}$ pour chaque $x\in G$.
\begin{defn}
-Un graphe orienté $G$ est dit \textbf{extensionnel} lorsque deux
+Un graphe orienté $G$ est dit \defin[extensionnel (graphe)]{extensionnel} lorsque deux
sommets $x$ et $x'$ ayant le même ensemble de voisins sortants ($\outnb(x)
= \outnb(x')$) sont égaux.
\end{defn}
Pour bien comprendre et utiliser la définition ci-dessus, il est
pertinent de rappeler que \emph{deux ensembles sont égaux si et
- seulement si ils ont les mêmes éléments} (\textbf{axiome
+ seulement si ils ont les mêmes éléments} (\defin[extensionalité (axiome)]{axiome
d'extensionalité}).
\begin{prop}\label{extensional-iff-collapse-injective}
@@ -3659,7 +3666,7 @@ sous la forme $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$
où $\gamma_s > \cdots > \gamma_1$ sont des ordinaux et
$n_s,\ldots,n_1$ sont des entiers naturels non nuls (si un $n_i$ est
nul il convient de l'omettre) : il s'agit d'une sorte d'écriture en
-« base $\omega$ » de l'ordinal, appelée \textbf{forme normale de
+« base $\omega$ » de l'ordinal, appelée \defin[Cantor (forme normale de)]{forme normale de
Cantor}. On compare deux formes normales de Cantor en comparant le
terme dominant (le plus à gauche, i.e., $\omega^{\gamma_s} n_s$ dans
les notations qui viennent d'être données, ce qui se fait lui-même en
@@ -3741,7 +3748,7 @@ ordinal $\alpha$ :
\subsection{Ensembles bien-ordonnés et induction transfinie}
\thingy\label{definition-well-ordered-set}
-Un ensemble \textbf{[partiellement] ordonné} est un ensemble
+Un ensemble \defin[ordonné]{[partiellement] ordonné} est un ensemble
muni d'une relation $>$ (d'ordre \emph{strict}) qui soit à la fois
\begin{itemize}
\item irréflexive ($x>x$ n'est jamais vrai quel que soit $x$), et
@@ -3755,11 +3762,11 @@ $x=y$, ou symétriquement $x>y$ étant défini par $x\geq y$ et $x\neq
y$), réflexive, antisymétrique et transitive. On note bien sûr $x\leq
y$ pour $y\geq x$ et $x<y$ pour $y>x$.
-Un ensemble partiellement ordonné est dit \textbf{totalement ordonné}
+Un ensemble partiellement ordonné est dit \defin[totalement ordonné]{totalement ordonné}
lorsque pour tous $x\neq y$ on a soit $x>y$ soit $y>x$.
Un ensemble totalement ordonné bien-fondé $W$ est dit
-\textbf{bien-ordonné}. D'après \ref{well-founded-induction}, ceci
+\defin{bien-ordonné}. D'après \ref{well-founded-induction}, ceci
peut se reformuler de différentes façons :
\begin{itemize}
\item[(*)]$W$ est un ensemble totalement ordonné dans lequel il
@@ -3834,8 +3841,8 @@ pour $y<x$, dans la définition de $f(x)$.
bien-ordonné et $E \subseteq W$ est un sous-ensemble de $W$, alors $E$
est lui-même bien ordonné (pour l'ordre induit) ; ceci s'applique en
particulier à $\precs(x) = \{y : y<x\}$. La définition est qu'une
-fonction $f$ entre ensembles ordonnés est dite \textbf{croissante}
-lorsque $x \leq y$ implique $f(x) \leq f(y)$, et \textbf{strictement
+fonction $f$ entre ensembles ordonnés est dite \defin[croissante (fonction)]{croissante}
+lorsque $x \leq y$ implique $f(x) \leq f(y)$, et \defin[strictement croissante (fonction)]{strictement
croissante} lorsque $x < y$ implique $f(x) < f(y)$, ce qui entre des
ensembles totalement ordonnés signifie exactement la même chose que
« injective et croissante ».
@@ -3967,12 +3974,12 @@ d'équivalence qu'on vient de définir.
La classe d'équivalence\footnote{Pour être parfaitement rigoureux, on
ne peut pas vraiment définir des classes d'équivalence de façon
usuelle dans ce contexte, d'où l'intérêt de la définition suivante
- (ordinaux de von Neumann).} $\#W$ s'appelle l'\textbf{ordinal}
+ (ordinaux de von Neumann).} $\#W$ s'appelle l'\defin{ordinal}
de $W$.
Si on préfère éviter la définition par classe d'équivalence, on peut
aussi définir $\#W$ comme l'écrasement transitif
-(cf. \ref{definition-transitive-collapse}) de $W$ (\textbf{ordinal de
+(cf. \ref{definition-transitive-collapse}) de $W$ (\defin[von Neumann (ordinal de)]{ordinal de
von Neumann}), à savoir $\#W = \{\#\precs(x) : x\in W\}$ où
$\#\precs(x) = \{\#\precs(y) : y<x\}$, cette définition ayant bien un
sens par induction transfinie (\ref{transfinite-definition}
@@ -4064,7 +4071,7 @@ voulu.
\thingy Une conséquence de cette proposition est qu'il n'y a pas
d'ensemble de tous les ordinaux (car si $S$ était un tel ensemble, il
aurait un majorant strict, qui par définition ne peut pas appartenir
-à $S$) : c'est le \textbf{« paradoxe » de Burali-Forti} ; le mot
+à $S$) : c'est le \defin[Burali-Forti (paradoxe de)]{« paradoxe » de Burali-Forti} ; le mot
« paradoxe » fait référence à une conception ancienne de la théorie
des ensembles, mais selon les fondements modernes des mathématiques,
ce phénomène n'a rien de paradoxal (intuitivement, il y a trop
@@ -4077,7 +4084,7 @@ reconnaître leur existence.
\subsection{Ordinaux successeurs et limites}
-\thingy On appelle \textbf{successeur} d'un ordinal $\alpha$ le plus
+\thingy On appelle \defin[successeur (ordinal)]{successeur} d'un ordinal $\alpha$ le plus
petit ordinal strictement supérieur à $\alpha$ (qui existe d'après la
proposition \ref{sup-and-strict-sup-of-sets-of-ordinals} : si on veut,
c'est $\sup^+\{\alpha\}$) : il est facile de voir que cet ordinal est
@@ -4091,11 +4098,11 @@ $\#W$ est le successeur de $\#\precs(x)$.
\thingy On distingue maintenant trois sortes d'ordinaux :
\begin{itemize}
-\item l'ordinal \textbf{nul} $0 = \#\varnothing$, mis à part de tous
+\item l'ordinal \defin[nul (ordinal)]{nul} $0 = \#\varnothing$, mis à part de tous
les autres,
-\item les ordinaux \textbf{successeurs}, c'est-à-dire ceux qui ont un plus
+\item les ordinaux \defin[successeur (ordinal)]{successeurs}, c'est-à-dire ceux qui ont un plus
grand élément (au sens expliqué ci-dessus),
-\item les autres, qu'on appelle ordinaux \textbf{limites}.
+\item les autres, qu'on appelle ordinaux \defin[limite (ordinal)]{limites}.
\end{itemize}
La terminologie d'ordinaux « limites » s'explique ainsi : si $\delta$
@@ -4109,7 +4116,7 @@ limite ainsi :
\thingy Si $\delta$ est un ordinal limite et $f$ est une fonction
\emph{croissante} de $\delta$ (i.e., des ordinaux strictement plus
-petits que $\delta$) vers les ordinaux, on appelle \textbf{limite} de
+petits que $\delta$) vers les ordinaux, on appelle \defin{limite} de
$f$ en $\delta$ la valeur $\sup\{f(\xi) : \xi<\delta\}$. On pourra la
noter $\lim_{\xi\to\delta} f(\xi)$ ou simplement $\lim_\delta f$. (Il
s'agit bien d'une limite pour une certaine topologie : la topologie de
@@ -4275,7 +4282,7 @@ suivantes :
nulle (si $\alpha\leq\alpha'$ alors $\alpha\cdot\beta \leq
\alpha'\cdot\beta$, et si $\beta<\beta'$ et $\alpha>0$ alors
$\alpha\cdot\beta < \alpha\cdot\beta'$) ;
-\item \textbf{division euclidienne} : pour tout $\alpha$ (ici appelé
+\item \defin{division euclidienne} : pour tout $\alpha$ (ici appelé
dividende) et tout $\beta>0$ (ici appelé diviseur) il existe
$\gamma$ (ici appelé quotient) et $\rho<\beta$ (ici appelé reste)
uniques tels que $\alpha = \beta\gamma + \rho$ (on prendra garde au
@@ -4372,16 +4379,16 @@ finie la somme ci-dessus) et tous $<\tau$.
Deux telles expressions se comparent par l'ordre lexicographique
donnant le plus de poids aux puissances élevées de $\tau$. On parle
-d'écriture de $\alpha$ \textbf{en base $\tau$} : on dit que les
+d'écriture de $\alpha$ \defin[écriture en base $\tau$]{en base $\tau$} : on dit que les
$\xi_{(\iota)}$ sont les \emph{chiffres} de cette écriture. On
souligne que les chiffres sont \emph{tous nuls sauf un nombre fini}
(ce qui permet de les comparer lexicographiquement).
Les deux cas les plus importants sont $\tau=2$ et $\tau=\omega$ : le
-cas $\tau=2$ correspond à l'\textbf{écriture binaire} d'un ordinal,
+cas $\tau=2$ correspond à l'\defin{écriture binaire} d'un ordinal,
c'est-à-dire son écriture comme somme décroissante finie de puissances
de $2$ distinctes, et le cas $\tau=\omega$ s'appelle écriture en
-\textbf{forme normale de Cantor}, c'est-à-dire comme somme
+\defin[Cantor (forme normale de)]{forme normale de Cantor}, c'est-à-dire comme somme
décroissante finie de puissances de $\omega$.
\thingy La forme normale de Cantor permet de comprendre, et de
@@ -4473,6 +4480,11 @@ de $2^c$ pour des entiers naturels $c$ distincts). À titre d'exemple,
\end{array}
\]
+%
+%
+%
+
+\printindex