diff options
Diffstat (limited to 'controle-20250626.tex')
| -rw-r--r-- | controle-20250626.tex | 41 |
1 files changed, 38 insertions, 3 deletions
diff --git a/controle-20250626.tex b/controle-20250626.tex index 6e01fbe..d03816c 100644 --- a/controle-20250626.tex +++ b/controle-20250626.tex @@ -200,9 +200,9 @@ vides. Un coup d'un joueur consiste à retirer \emph{exactement un} jeton d'une certaine pile $i$, de son choix, et d'ajouter \emph{autant qu'il -le souhaite} (y compris $0$) jetons à chacune des piles $j<i$. Par -exemple, à partir de la position $(0,3,2)$ on peut notamment jouer -vers $(42,1000,1)$ ou bien vers $(0,2,2)$. +le souhaite} (y compris $0$) jetons à chacune des piles $j<i$, y +compris plusieurs. Par exemple, à partir de la position $(0,3,2)$ on +peut notamment jouer vers $(42,1000,1)$ ou bien vers $(0,2,2)$. Comme d'habitude, le joueur qui ne peut pas jouer a perdu, c'est-à-dire que celui qui prend le dernier jeton a gagné. @@ -252,6 +252,41 @@ d'une position $(n_0,n_1,\ldots,n_{k-1})$ quelconque. \exercise +Dans cet exercice, on fixe un ordinal $\varepsilon$ tel que +$\varepsilon = \omega^\varepsilon$. + +\textbf{(1)} Montrer que $\varepsilon^\varepsilon = +\omega^{\varepsilon^2}$ et que $\varepsilon \cdot +\varepsilon^\varepsilon$ vaut la même chose. + +\textbf{(2)} On suppose que $S$ et $T$ sont deux ensembles d'ordinaux +tels que $\forall \alpha\in S,\; \exists \beta\in +T,\;(\alpha\leq\beta)$ et que $\forall \beta\in T,\; \exists \alpha\in +S,\;(\beta\leq\alpha)$. Montrer que $\sup S = \sup T$. + +\textbf{(3)} On appelle $(\alpha_n)_{n\in\mathbb{N}}$ la suite +d'ordinaux définie par récurrence par $\alpha_0 = 1$ et $\alpha_{n+1} += \varepsilon^{\alpha_n}$, et $(\beta_n)_{n\in\mathbb{N}}$ la suite +d'ordinaux définie par récurrence par $\beta_0 = \varepsilon+1$ et +$\beta_{n+1} = \omega^{\beta_n}$. Autrement dit : $1, \varepsilon, +\varepsilon^{\varepsilon}, \varepsilon^{\varepsilon^\varepsilon}, +\varepsilon^{\varepsilon^{\varepsilon^\varepsilon}}, \ldots$ d'une +part, et $\varepsilon+1, \omega^{\varepsilon+1}, +\omega^{\omega^{\varepsilon+1}}, +\omega^{\omega^{\omega^{\varepsilon+1}}}, \ldots$ de l'autre. Montrer +que ces suites ont la même limite. + +\textbf{(4)} Montrer que la limite commune trouvée en (3) vérifie +$\eta = \omega^\eta$, et qu'elle est le plus petit ordinal +$\eta>\epsilon$ tel que $\eta = \omega^\eta$. + + +% +% +% + +\exercise + On se propose dans cet exercice de montrer qu'il existe une partie $A \subseteq \{0,1\}^{\mathbb{N}}$ tel que le jeu de Gale-Stewart $G(A) := G_{\{0,1\}}(A)$ ne soit pas déterminé (i.e., tel qu'aucun des deux |