diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 238 |
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 |