path: root/exercices-ordinaux.tex

%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\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}
\usetikzlibrary{matrix,calc}
\usepackage{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\outnb}{\operatorname{outnb}}
\newcommand{\downstr}{\operatorname{downstr}}
\newcommand{\precs}{\operatorname{precs}}
\newcommand{\mex}{\operatorname{mex}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\limp}{\Longrightarrow}
\newcommand{\gr}{\operatorname{gr}}
\newcommand{\rk}{\operatorname{rk}}
%
\DeclareUnicodeCharacter{00A0}{~}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
%
\begin{document}
\ifcorrige
\title{Exercices sur les ordinaux — Corrigé}
\else
\title{Exercices sur les ordinaux}
\fi
\author{David A. Madore}
\maketitle

\centerline{\textbf{MITRO206}}

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pretolerance=8000
\tolerance=50000



%
%
%

\exercice

Ranger les ordinaux suivants par ordre croissant :
\spaceout $\omega^{\omega+1} + \omega^\omega\cdot 33$ ;
\spaceout $\omega\cdot 3 + 42$ ;
\spaceout $\omega^{\omega+1} + \omega + 33$ ;
\spaceout $\omega^{\omega+2} + \omega^\omega$ ;
\spaceout $\omega^2\cdot 42 + 1000$ ;
\spaceout $\omega^2 + \omega$ ;
\spaceout $\omega^2\cdot 42 + \omega$ ;
\spaceout $\omega^{\omega^2 + 1}$ ;
\spaceout $\omega^{\omega^{(\omega\cdot 2)}}$ ;
\spaceout $\omega^{\omega^\omega} + 1$ ;
\spaceout $\omega^{\omega+1} + \omega\cdot 33$ ;
\spaceout $\omega^{\omega^2}$ ;
\spaceout $\omega^{\omega^2 + 1} + \omega^{\omega\cdot 2}\cdot 1000$ ;
\spaceout $\omega^{\omega^2 + \omega}$ ;
\spaceout $\omega\cdot 3$ ;
\spaceout $\omega^{(\omega^\omega\cdot 2)}$ ;
\spaceout $\omega^{\omega^3}$ ;
\spaceout $\omega^{\omega+1} + 1000$ ;
\spaceout $\omega^{\omega+2}$ ;
\spaceout $\omega^{\omega+1}\cdot 2$ ;
\spaceout $\omega\cdot 2 + 1729$ ;
\spaceout $\omega^2 + 1000$ ;
\spaceout $42$ ;
\spaceout $\omega^{\omega^2 + \omega} + \omega^{\omega^2 + 1}$ ;
\spaceout $\omega^{\omega\cdot 2}\cdot 1000$ ;
\spaceout $\omega^2\cdot 42$ ;
\spaceout $\omega^{\omega+1} + \omega^2\cdot 33$ ;
\spaceout $\omega^2$ ;
\spaceout $\omega$ ;
\spaceout $\omega^{\omega+1}$ ;
\spaceout $\omega^{\omega^2 + 1} + \omega^{\omega^2}\cdot 42$ ;
\spaceout $\omega^{\omega\cdot 2} + \omega^{\omega+2}$ ;
\spaceout $\omega^{\omega^2 + \omega} + \omega^{\omega^2} + \omega^{\omega+1}$ ;
\spaceout $\omega^{\omega^{(\omega^2)}}$ ;
\spaceout $\omega^{\omega^2 + 1}\cdot 2$ ;
\spaceout $\omega^2 + \omega\cdot 42$ ;
\spaceout $\omega + 42$ ;
\spaceout $\omega^{\omega^2\cdot 2}$ ;
\spaceout $\omega^{\omega\cdot 2 + 42}$ ;
\spaceout $\omega^{\omega\cdot 2}$ ;
\spaceout $\omega\cdot 2$ ;
\spaceout $\omega^{\omega+1} + \omega^2 + 33$ ;
\spaceout $\omega^{\omega^{(\omega+1)}}$ ;
\spaceout $\omega^\omega$ ;
\spaceout $\omega^{\omega^2 + \omega + 1}$ ;
\spaceout $\omega^{\omega^\omega}\cdot 2$ ;
\spaceout $\omega^{\omega^\omega}$ ;
\spaceout $0$ ;
\spaceout $\omega^{\omega^2} + \omega^{\omega+1}$ ;
\spaceout $\omega^{(\omega^\omega + 1)}$.

\begin{corrige}
On vérifie que tous ces ordinaux sont écrits en forme normale de
Cantor (et les exposants de $\omega$ aussi, etc.).  On les compare
donc en comparant à chaque fois la plus grande puissance de $\omega$.

Dans l'ordre croissant : \spaceout $0$ ;
\spaceout $42$ ;
\spaceout $\omega$ ;
\spaceout $\omega + 42$ ;
\spaceout $\omega\cdot 2$ ;
\spaceout $\omega\cdot 2 + 1729$ ;
\spaceout $\omega\cdot 3$ ;
\spaceout $\omega\cdot 3 + 42$ ;
\spaceout $\omega^2$ ;
\spaceout $\omega^2 + 1000$ ;
\spaceout $\omega^2 + \omega$ ;
\spaceout $\omega^2 + \omega\cdot 42$ ;
\spaceout $\omega^2\cdot 42$ ;
\spaceout $\omega^2\cdot 42 + 1000$ ;
\spaceout $\omega^2\cdot 42 + \omega$ ;
\spaceout $\omega^\omega$ ;
\spaceout $\omega^{\omega+1}$ ;
\spaceout $\omega^{\omega+1} + 1000$ ;
\spaceout $\omega^{\omega+1} + \omega + 33$ ;
\spaceout $\omega^{\omega+1} + \omega\cdot 33$ ;
\spaceout $\omega^{\omega+1} + \omega^2 + 33$ ;
\spaceout $\omega^{\omega+1} + \omega^2\cdot 33$ ;
\spaceout $\omega^{\omega+1} + \omega^\omega\cdot 33$ ;
\spaceout $\omega^{\omega+1}\cdot 2$ ;
\spaceout $\omega^{\omega+2}$ ;
\spaceout $\omega^{\omega+2} + \omega^\omega$ ;
\spaceout $\omega^{\omega\cdot 2}$ ;
\spaceout $\omega^{\omega\cdot 2} + \omega^{\omega+2}$ ;
\spaceout $\omega^{\omega\cdot 2}\cdot 1000$ ;
\spaceout $\omega^{\omega\cdot 2 + 42}$ ;
\spaceout $\omega^{\omega^2}$ ;
\spaceout $\omega^{\omega^2} + \omega^{\omega+1}$ ;
\spaceout $\omega^{\omega^2 + 1}$ ;
\spaceout $\omega^{\omega^2 + 1} + \omega^{\omega\cdot 2}\cdot 1000$ ;
\spaceout $\omega^{\omega^2 + 1} + \omega^{\omega^2}\cdot 42$ ;
\spaceout $\omega^{\omega^2 + 1}\cdot 2$ ;
\spaceout $\omega^{\omega^2 + \omega}$ ;
\spaceout $\omega^{\omega^2 + \omega} + \omega^{\omega^2} + \omega^{\omega+1}$ ;
\spaceout $\omega^{\omega^2 + \omega} + \omega^{\omega^2 + 1}$ ;
\spaceout $\omega^{\omega^2 + \omega + 1}$ ;
\spaceout $\omega^{\omega^2\cdot 2}$ ;
\spaceout $\omega^{\omega^3}$ ;
\spaceout $\omega^{\omega^\omega}$ ;
\spaceout $\omega^{\omega^\omega} + 1$ ;
\spaceout $\omega^{\omega^\omega}\cdot 2$ ;
\spaceout $\omega^{(\omega^\omega + 1)}$ ;
\spaceout $\omega^{(\omega^\omega\cdot 2)}$ ;
\spaceout $\omega^{\omega^{(\omega+1)}}$ ;
\spaceout $\omega^{\omega^{(\omega\cdot 2)}}$ ;
\spaceout et enfin\spaceout $\omega^{\omega^{(\omega^2)}}$.
\end{corrige}



%
%
%

\exercice

(a) Que vaut $(\omega+1) + (\omega+1)$ ?

(b) Plus généralement, que vaut $(\omega+1) + \cdots + (\omega+1)$
avec $n$ termes $\omega+1$ (où $n$ est un entier naturel $\geq 1$) ?

(c) En déduire ce que vaut $(\omega+1)\cdot n$.

(d) En déduire ce que vaut $(\omega+1)\cdot \omega$.

(e) En déduire ce que vaut $(\omega+1)\cdot(\omega+1)$.

(f) En déduire ce que vaut $(\omega+1)^2$.

\begin{corrige}
(a) On a $(\omega+1) + (\omega+1) = \omega + 1 + \omega + 1 = \omega +
  (1 + \omega) + 1 = \omega + \omega + 1 = \omega\cdot 2 + 1$.

(b) En procédant de même, on voit que dans la somme de $n$ termes
  $\omega + 1$, chaque $1$ est absorbé par le $\omega$ qui
  \emph{suit}, sauf le dernier $1$ qui demeure : la somme vaut
  donc $\omega\cdot n + 1$.

(c) Quel que soit l'ordinal $\alpha$, la somme $\alpha + \cdots +
  \alpha$ avec $n$ termes $\alpha$ vaut $\alpha\cdot n$ (ceci se voit
  soit par une récurrence immédiate sur $n$ avec la définition par
  induction de la multiplication, soit en utilisant la distributivité
  à droite, c'est-à-dire $\alpha\cdot n = \alpha\cdot(1 + \cdots + 1)
  = \alpha + \cdots + \alpha$).  On a donc $(\omega+1)\cdot n =
  \omega\cdot n + 1$.

(d) L'ordinal $(\omega+1)\cdot \omega$ est donc la limite
  (c'est-à-dire la borne supérieure) des $(\omega+1)\cdot n =
  \omega\cdot n + 1$ pour $n\to\omega$.  Cette borne supérieure
  vaut $\omega^2$ : en effet, $\omega^2 \geq \omega\cdot n + 1$ pour
  chaque $n<\omega$, mais inversement, si $\gamma < \omega^2$, on a
  $\gamma < \omega\cdot n$ pour un certain $n$ (par exemple en
  utilisant le fait que $\omega^2 = \omega\cdot\omega$ est elle-même
  la limite des $\omega\cdot n$, c'est-à-dire le plus petit ordinal
  supérieur ou égal à eux), et en particulier $\gamma < \omega\cdot n
  + 1$ ; ou, si on préfère, quel que soit $n$ on a $\omega\cdot n \leq
  \omega\cdot n + 1 \leq \omega\cdot (n + 1)$ où $\omega\cdot n$ et
  $\omega\cdot (n+1)$ ont la même limite $\omega^2$ quand
  $n\to\omega$, d'où il résulte que $\omega\cdot n + 1$ aussi.

(e) On a $(\omega+1)\cdot (\omega+1) = (\omega+1)\cdot \omega +
  (\omega + 1) = \omega^2 + \omega + 1$.

(f) On a toujours $\alpha^2 = \alpha\cdot\alpha$, donc $(\omega+1)^2 =
  \omega^2 + \omega + 1$ comme on vient de le montrer.
\end{corrige}



%
%
%

\exercice

(a) Que vaut $(\omega 2) \cdot (\omega 2)$ ?

(b) Plus généralement, que vaut $(\omega 2) \cdots (\omega 2)$ avec
$n$ facteurs $\omega 2$ (où $n$ est un entier naturel $\geq 1$) ?

(c) En déduire ce que vaut $(\omega 2)^n$.

(d) En déduire ce que vaut $(\omega 2)^\omega$.  Comparer avec
$\omega^\omega \cdot 2^\omega$.

(e) En déduire ce que vaut $(\omega 2)^{\omega+n}$ pour $n\geq 1$
entier naturel.

(f) En déduire ce que vaut $(\omega 2)^{\omega 2}$.

\begin{corrige}
(a) On a $(\omega 2) \cdot (\omega 2) = \omega \cdot 2 \cdot \omega
  \cdot 2 = \omega \cdot (2 \cdot \omega) \cdot 2 = \omega \cdot
  \omega \cdot 2 = \omega^2 \cdot 2$.

(b) En procédant de même, on voit que dans le produit de $n$ facteurs
  $\omega 2$, chaque $2$ est absorbé par le $\omega$ qui \emph{suit},
  sauf le dernier $2$ qui demeure : le produit vaut donc $\omega^n
  \cdot 2$.

(c) Quel que soit l'ordinal $\alpha$, le produit $\alpha \cdots
  \alpha$ avec $n$ facteurs $\alpha$ vaut $\alpha^n$ (ceci se voit
  soit par une récurrence immédiate sur $n$ avec la définition par
  induction de l'exponentiation, soit en écrivant $\alpha^n =
  \alpha^{1+\cdots+1} = \alpha \cdots \alpha$).  On a donc $(\omega
  2)^n = \omega^n \cdot 2$.

(d) L'ordinal $(\omega 2)^\omega$ est la limite (c'est-à-dire la borne
  supérieure) des $\omega^n \cdot 2$ pour $n\to\omega$.  Cette borne
  supérieure vaut $\omega^\omega$ : en effet, $\omega^\omega \geq
  \omega^n \cdot 2$ pour chaque $n<\omega$, mais inversement, si
  $\gamma < \omega^\omega$, on a $\gamma < \omega^n$ pour un
  certain $n$ (par exemple en utilisant le fait que $\omega^\omega$
  est lui-même la limite des $\omega^n$, c'est-à-dire le plus petit
  ordinal supérieur ou égal à eux), et en particulier $\gamma <
  \omega^n \cdot 2$ ; ou, si on préfère, quel que soit $n$ on a
  $\omega^n \leq \omega^n \cdot 2 \leq \omega^{n+1}$ où $\omega^n$ et
  $\omega^{n+1}$ ont la même limite $\omega^\omega$ quand
  $n\to\omega$, d'où il résulte que $\omega^n \cdot 2$ aussi.

  Bref, $(\omega 2)^\omega = \omega^\omega$.  En revanche,
  $\omega^\omega \cdot 2^\omega = \omega^\omega \cdot \omega =
  \omega^{\omega+1}$ est strictement plus grand.

(e) On a $(\omega 2)^{\omega + n} = (\omega 2)^\omega \cdot (\omega
  2)^n = \omega^\omega \cdot \omega^n \cdot 2$ d'après les questions
  précédentes, donc ceci vaut $\omega^{\omega+n} \cdot 2$.

(f) L'ordinal $(\omega 2)^{\omega 2}$ est la limite des
  $\omega^{\omega+n} \cdot 2$ pour $n\to\omega$, et le même
  raisonnement qu'en (d) montre que cette limite est
  $\omega^{\omega+\omega} = \omega^{\omega 2}$.  Bref, $(\omega
  2)^{\omega 2} = \omega^{\omega 2}$.
\end{corrige}



%
%
%

\exercice

On dit qu'un ordinal $\alpha$ est \textbf{infini} lorsque
$\alpha\geq\omega$.  Montrer qu'un ordinal est infini si et seulement
si $1+\alpha = \alpha$.

\begin{corrige}
Si $\alpha$ est infini, on a $\alpha \geq \omega$, donc il existe un
unique ordinal $\beta$ tel que $\alpha = \omega + \beta$.  On a alors
$1 + \alpha = 1 + (\omega + \beta) = (1 + \omega) + \beta = \omega +
\beta = \alpha$.

Si, en revanche, $\alpha$ est fini, c'est-à-dire $\alpha < \omega$,
alors $\alpha$ est un entier naturel, et comme l'addition ordinale sur
les entiers naturels coïncide avec l'addition usuelle sur ceux-ci, on
a $1 + \alpha > \alpha$.
\end{corrige}



%
%
%

\exercice

On rappelle que si $\alpha' \geq \alpha$ sont deux ordinaux, il existe
un unique $\beta$ tel que $\alpha' = \alpha + \beta$.\spaceout (a) En
déduire que si $\gamma < \gamma'$ alors $\omega^\gamma +
\omega^{\gamma'} = \omega^{\gamma'}$ (on pourra utiliser la conclusion
de l'exercice précédent).\spaceout (b) Expliquer pourquoi
$\omega^{\gamma'} + \omega^\gamma$, lui, est strictement plus grand
que $\omega^{\gamma'}$ et $\omega^\gamma$.

\begin{corrige}
(a) Si $\gamma < \gamma'$, il existe $\beta$ tel que $\gamma' = \gamma
  + \beta$, si bien qu'on a $\omega^\gamma + \omega^{\gamma'} =
  \omega^\gamma + \omega^{\gamma + \beta} = \omega^\gamma +
  \omega^\gamma \cdot \omega^\beta = \omega^\gamma (1 +
  \omega^\beta)$.  La conclusion voulue découle donc du fait que $1 +
  \omega^\beta = \omega^\beta$ : or ceci résulte de l'exercice
  précédent (on a $\beta \neq 0$ puisque $\gamma' \neq \gamma$, donc
  $\beta \geq 1$, donc $\omega^\beta \geq \omega$).

(b) On a $\omega^\gamma > 0$ donc $\omega^{\gamma'} + \omega^\gamma >
  \omega^{\gamma'}$ (par stricte croissance de la somme en la variable
  de droite), et comme $\omega^{\gamma'} > \omega^\gamma$, la somme
  est également $> \omega^\gamma$.  (On pouvait aussi invoquer la
  comparaison des formes normales de Cantor.)
\end{corrige}



%
%
%

\exercice

(A) (1) Que vaut $2^{\omega+1}$ ?\spaceout (2) Que vaut
$2^{\omega^2}$ ?\spaceout (3) Expliquer pourquoi $\omega^\omega =
\omega\cdot \omega^\omega$.  En déduire ce que vaut
$2^{\omega^\omega}$.\spaceout (À chaque fois, on écrira les ordinaux
demandés en forme normale de Cantor.)

(B) On suppose que $\varepsilon = \omega^\varepsilon$.\spaceout
(1) Que vaut $\varepsilon^\varepsilon$ ?\spaceout (2) Que vaut
$\varepsilon^{\varepsilon^\varepsilon}$ (on pourra utiliser un des
deux exercices précédents) ?\spaceout (À chaque fois, plusieurs
écritures sont possibles.)

\begin{corrige}
(A) (1) On a $2^{\omega+1} = 2^\omega\cdot 2^1 = \omega\cdot
  2$.\spaceout (2) On a $2^{\omega^2} = 2^{\omega\cdot\omega} =
  (2^\omega)^\omega = \omega^\omega$.\spaceout (3) On a $\omega\cdot
  \omega^\omega = \omega^1 \cdot \omega^\omega = \omega^{1+\omega} =
  \omega^\omega$.  On en déduit que $2^{\omega^\omega} =
  2^{\omega\cdot \omega^\omega} = (2^\omega)^{\omega^\omega} =
  \omega^{\omega^\omega}$.

(B) (1) On a $\varepsilon^\varepsilon =
  (\omega^\varepsilon)^\varepsilon = \omega^{\varepsilon^2}$ ou, si on
  préfère, $\omega^{\omega^{\varepsilon\cdot 2}}$.\spaceout  (2) On a
  $\varepsilon^{\varepsilon^\varepsilon} =
  (\omega^\varepsilon)^{\varepsilon^\varepsilon} = \omega^{\varepsilon
    \cdot \varepsilon^\varepsilon} = \omega^{\varepsilon^{1 +
      \varepsilon}}$.  Or $1 + \varepsilon = \varepsilon$ d'après un
  des exercices précédents (parce que $\varepsilon$ est infini ou
  parce que la somme est $\omega^0 + \omega^\varepsilon$), donc
  $\varepsilon^{\varepsilon^\varepsilon} =
  \omega^{\varepsilon^\varepsilon}$.  D'après la sous-question
  précédente, c'est aussi $\omega^{\omega^{\varepsilon^2}}$ ou encore
  $\omega^{\omega^{\omega^{\varepsilon\cdot 2}}}$.
\end{corrige}


%
%
%
\end{document}