\documentclass[a4paper, titlepage]{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{textcomp} \usepackage[french]{babel} \usepackage{amsmath, amssymb} \usepackage{amsthm} \usepackage[svgnames]{xcolor} \usepackage{thmtools} \usepackage{lipsum} \usepackage{framed} \usepackage{parskip} \usepackage{titlesec} \usepackage{tikz} \renewcommand{\familydefault}{\sfdefault} % figure support \usepackage{import} \usepackage{xifthen} \pdfminorversion=7 \usepackage{pdfpages} \usepackage{transparent} \newcommand{\incfig}[1]{% \def\svgwidth{\columnwidth} \import{./figures/}{#1.pdf_tex} } \pdfsuppresswarningpagegroup=1 \colorlet{defn-color}{DarkBlue} \colorlet{props-color}{Blue} \colorlet{warn-color}{Red} \colorlet{exemple-color}{Green} \colorlet{corol-color}{Orange} \newenvironment{defn-leftbar}{% \def\FrameCommand{{\color{defn-color}\vrule width 3pt} \hspace{10pt}}% \MakeFramed {\advance\hsize-\width \FrameRestore}}% {\endMakeFramed} \newenvironment{warn-leftbar}{% \def\FrameCommand{{\color{warn-color}\vrule width 3pt} \hspace{10pt}}% \MakeFramed {\advance\hsize-\width \FrameRestore}}% {\endMakeFramed} \newenvironment{exemple-leftbar}{% \def\FrameCommand{{\color{exemple-color}\vrule width 3pt} \hspace{10pt}}% \MakeFramed {\advance\hsize-\width \FrameRestore}}% {\endMakeFramed} \newenvironment{props-leftbar}{% \def\FrameCommand{{\color{props-color}\vrule width 3pt} \hspace{10pt}}% \MakeFramed {\advance\hsize-\width \FrameRestore}}% {\endMakeFramed} \newenvironment{corol-leftbar}{% \def\FrameCommand{{\color{corol-color}\vrule width 3pt} \hspace{10pt}}% \MakeFramed {\advance\hsize-\width \FrameRestore}}% {\endMakeFramed} \def \freespace {1em} \declaretheoremstyle[headfont=\sffamily\bfseries,% notefont=\sffamily\bfseries,% notebraces={}{},% headpunct=,% bodyfont=\sffamily,% headformat=\color{defn-color}Définition~\NUMBER\hfill\NOTE\smallskip\linebreak,% preheadhook=\vspace{\freespace}\begin{defn-leftbar},% postfoothook=\end{defn-leftbar},% ]{better-defn} \declaretheoremstyle[headfont=\sffamily\bfseries,% notefont=\sffamily\bfseries,% notebraces={}{},% headpunct=,% bodyfont=\sffamily,% headformat=\color{warn-color}Attention~\NUMBER\hfill\NOTE\smallskip\linebreak,% preheadhook=\vspace{\freespace}\begin{warn-leftbar},% postfoothook=\end{warn-leftbar},% ]{better-warn} \declaretheoremstyle[headfont=\sffamily\bfseries,% notefont=\sffamily\bfseries,% notebraces={}{},% headpunct=,% bodyfont=\sffamily,% headformat=\color{exemple-color}Exemple~\NUMBER\hfill\NOTE\smallskip\linebreak,% preheadhook=\vspace{\freespace}\begin{exemple-leftbar},% postfoothook=\end{exemple-leftbar},% ]{better-exemple} \declaretheoremstyle[headfont=\sffamily\bfseries,% notefont=\sffamily\bfseries,% notebraces={}{},% headpunct=,% bodyfont=\sffamily,% headformat=\color{props-color}Proposition~\NUMBER\hfill\NOTE\smallskip\linebreak,% preheadhook=\vspace{\freespace}\begin{props-leftbar},% postfoothook=\end{props-leftbar},% ]{better-props} \declaretheoremstyle[headfont=\sffamily\bfseries,% notefont=\sffamily\bfseries,% notebraces={}{},% headpunct=,% bodyfont=\sffamily,% headformat=\color{props-color}Théorème~\NUMBER\hfill\NOTE\smallskip\linebreak,% preheadhook=\vspace{\freespace}\begin{props-leftbar},% postfoothook=\end{props-leftbar},% ]{better-thm} \declaretheoremstyle[headfont=\sffamily\bfseries,% notefont=\sffamily\bfseries,% notebraces={}{},% headpunct=,% bodyfont=\sffamily,% headformat=\color{corol-color}Corollaire~\NUMBER\hfill\NOTE\smallskip\linebreak,% preheadhook=\vspace{\freespace}\begin{corol-leftbar},% postfoothook=\end{corol-leftbar},% ]{better-corol} \declaretheorem[style=better-defn]{defn} \declaretheorem[style=better-warn]{warn} \declaretheorem[style=better-exemple]{exemple} \declaretheorem[style=better-corol]{corol} \declaretheorem[style=better-props, numberwithin=defn]{props} \declaretheorem[style=better-thm, sibling=props]{thm} \newtheorem*{lemme}{Lemme}%[subsection] %\newtheorem{props}{Propriétés}[defn] \newenvironment{system}% {\left\lbrace\begin{align}}% {\end{align}\right.} \newenvironment{AQT}{{\fontfamily{qbk}\selectfont AQT}} \usepackage{LobsterTwo} \titleformat{\section}{\newpage\LobsterTwo \huge\bfseries}{\thesection.}{1em}{} \titleformat{\subsection}{\vspace{2em}\LobsterTwo \Large\bfseries}{\thesubsection.}{1em}{} \titleformat{\subsubsection}{\vspace{1em}\LobsterTwo \large\bfseries}{\thesubsubsection.}{1em}{} \newenvironment{lititle}% {\vspace{7mm}\LobsterTwo \large}% {\\} \renewenvironment{proof}{\par$\square$ \footnotesize\textit{Démonstration.}}{\begin{flushright}$\blacksquare$\end{flushright}\par} \title{Relations d'ordre, ensembles ordonnés} \author{William Hergès\thanks{Sorbonne Université}} \begin{document} \maketitle \tableofcontents \newpage \section{Ensemble ordonné} \subsection{Définition} \begin{defn} Une relation d'ordre $\preceq$ est une relation binaire sur $E$ si et seulement si~: \begin{itemize} \item réflexive \item anti-symétrique \item transitive \end{itemize} L'ordre strict $\prec$ est associé à $\preceq$~: c'est la même, sauf qu'elle n'est pas réflexive~: $$ \prec = \preceq\backslash\mathrm{Id}_E $$ \end{defn} \begin{defn} Une relation d'ordre $\preceq$ est~: \begin{itemize} \item totale si et seulement si $\preceq$ permet toujours de comparer deux éléments quelconques de $E$ \item partielle s'il existe au moins deux éléments de $E$ incomparables avec $\preceq$ \end{itemize} \end{defn} \begin{defn} $(E,\preceq)$ est un ensemble~: \begin{itemize} \item totalement ordonné si $\preceq$ est un ordre total. \item partiellement ordonné si $\preceq$ est un ordre partiel. \end{itemize} \end{defn} \begin{exemple} $(\mathbb{N},\leqslant )$ est un ensemble totalement ordonné. $(\mathcal{P}(F),\subseteq)$ est un ensemble partiellement ordoné (pour $F$ un ensemble quelconque). $(\mathbb{N}^*, |)$ est aussi partiellement ordoné, où $$ | = \{(a,b)|\exists k\in\mathbb{N}^*, b = na\} $$ (c'est la relation divise.) \end{exemple} \begin{proof} Preuve du deuxième exemple. Soit $F$ un ensemble. Montrons que $\subseteq$ est un ordre pour $\mathcal{P}(F)$. \begin{itemize} \item Soit $A\in\mathcal{P}(F)$. Triviallement, $A\subseteq A$. Alors, $\subseteq$ est réflexive. \item Soit $(A,B)\in\mathcal{P}(F)^2$. Supposons que $A\subseteq B$ et que $B\subseteq A$. Alors, $A=B$ par définition. \item Soit $(A,B,C)\in\mathcal{P}(F)^3$ avec $A\subseteq B$ et $B\subseteq C$. Si $A$ est l'ensemble vide, il est inclu dans tous les ensembles. Donc $A\subseteq C$. Si $A$ n'est pas l'ensemble vide, tous ses éléments sont dans $B$. Or, tous les éléments de $B$ sont dans $C$. Donc, tous les éléments de $A$ sont dans $C$. Alors, $A\subseteq C$. \end{itemize} Ainsi, $\subseteq$ est bien un ordre pour $\mathcal{P}(F)$. Montrons que $\subseteq$ est un ordre partiel. Supposons que $F$ contient au moins deux éléments. Soit $(x,y)\in F^2$, deux éléments différents. Soient $A=\{x\}$ et $B=\{y\}$. On a que $A\not\subseteq B$ et que $B\subseteq A$. Donc, $\subseteq$ est partiel dans ce cas. Si $F$ est vide, alors $\mathcal{P}(F)$ contient un unique élément. Cet ensemble est totalement ordonné. Si $F$ est un singleton, alors $\mathcal{P}(F)$ contient $F$ et l'ensemble vide. Cet ensemble est totalement ordonné. La slide est ainsi fausse, mais les ensembles à moins de deux éléments sont peux intéressants. \end{proof} \subsection{Représentation d'une relation d'ordre} \begin{defn} La représentation d'une relation d'ordre $R$ sur un ensemble $E$ est le graphe \textit{minimal} représentant une relation $\to$, telle que~: \begin{itemize} \item la fermeture réflexive et transitive $\to^*$ de $\to$ correspond exactement à la relation $R$ \item $\to$ est la plus petite relation dont la fermeture réflexo-transitive est égale à la relation $R$ \item $\to$ contient tous les couples $(a,b)\in R$ tels que $a\neq b$ et que~: $$ \forall c\in E, c\neq a, c\neq b,\quad (a,c)\not\in R\lor (c,b)\not\in R $$ \end{itemize} On a donc que $\to$ s'obtient en supprimant de $R$~: \begin{itemize} \item les couples $(x,x)\in R$ (réflexivité) \item les couples pouvant se déduire par transitivité \end{itemize} On dit que ce graphe est couvrant. \end{defn} \begin{props} Le coupe $(a,b)$ appartient à $R$ si, et seulement si, il existe un chemin dans le graphe couvrant. \end{props} \begin{exemple} Graphe couvrant de $\leqslant$ sur $\mathbb{N}$~: \begin{tikzpicture} \node (start) {0}; \node (1) [right of=start] {$1$}; \draw [->] (start) -- (1); \node (2) [right of=1] {$2$}; \draw [->] (1) -- (2); \node (3) [right of=2] {$3$}; \draw [->] (2) -- (3); \node (4) [right of=3] {$\ldots$}; \draw [->] (3) -- (4); \end{tikzpicture} \end{exemple} \subsection{Monotonie} \begin{defn} Soient $(E_1,\preceq_1)$ et $(E_2,\preceq_2)$ deux ensemble ordonnés. L'application $f:E_1\to E_2$ est dite monotone si~: $$ \forall (x,y)\in E_1^2,\quad x\preceq_1 y \implies f(x)\preceq_2 f(y) $$ \end{defn} Une application monotone préserve les relations d'ordre. \begin{exemple} On se place dans $(\mathbb{N},\leqslant)$ et dans $(\mathcal{P}(\mathbb{N}))$ $f:\mathbb{N}\to \mathcal{P}(\mathbb{N})$ tel que $f(n) = \{k\in\mathbb{N}|k\leqslant n\}$ est monotone. $g:\mathbb{N}\to \mathcal{P}(\mathbb{N})$ tel que $g(n)=\{n\}$ ne l'est pas par contre~! \end{exemple} \begin{props} Deux ensembles ordonnés $(E_1,\preceq_1)$ et $(E_2,\preceq_2)$ sont isomorphes s'il existe une bijection $f:E_1\to E_2$ telle que $f$ et $f^{-1}$ sont monotones. \end{props} \begin{exemple} Soient $(\mathbb{N},\leqslant)$ et $(\mathcal{P}(\mathbb{N}),\subseteq)$ deux ensembles ordonnés. $f:\mathbb{N}\to\mathcal{P}(\mathbb{N})$ telle que $f(n) = \{k|k\leqslant n\}$ est monotone. $g:\mathbb{N}\to\mathcal{P}(\mathbb{N})$ telle que $g(n) = \{ n\}$ n'est pas monotone. \end{exemple} \begin{warn} Une bijection $f$ peut être monotone sans que $f^{-1}$ ne le soit~! \end{warn} \subsection{Minimum, maximum, bornes} \begin{defn} Soit $(E,\preceq)$ un ensemble ordonné et $X$ une partie de $E$. Un élément minimal $x$ de $X$ est un élément tel que~: $$ \forall y\in X,\quad y\preceq x\implies y=x $$ Un élément maximale $x$ de $X$ est un tel que~: $$ \forall y\in X,\quad x \preceq y \implies x=y $$ \end{defn} \begin{defn} On dit que $e\in E$ est un minorant de $X$ si~: $$ \forall x\in X,\quad e\preceq x $$ On dit que $e\in E$ est un majorant de $X$ si~: $$ \forall x\in X,\quad x\preceq e $$ \end{defn} La différence avec l'élément minimal, c'est que $e$ n'est pas forcément dans $X$~! La différence avec l'élément maximal, c'est que $e$ n'est pas forcément dans $X$~! \begin{defn} Le plus petit élément (aussi appelé minimum) de $X$, s'il existe, est l'unique élément de l'intersection de $X$ et de ses minorants. Le plus grand élément (aussi appelé maximum) de $X$, s'il existe, est l'unique élément de l'intersection de $X$ et de ses majorants. \end{defn} Le minimum est le minorant dans $X$~! Le maximum est le majorant dans $X$~! \begin{proof} Soient $x_1$ et $x_2$ deux minorants (resp. deux majorants) de $X$. Par défintion, on a~: $$ x_1\preceq x_2\quad\land\quad x_2\preceq x_1$$ Par anti-symétrie, on obtient $x_1=x_2$. Ainsi, le minorant (resp. majorant) est unique. \end{proof} \begin{defn} La borne inférieure de $X$ est le plus grand élément des minorants de $X$ (s'il existe). On la note $\inf$. La borne supérieure de $X$ est le plus petit élément des majorants de $X$ (s'il existe). On la note $\sup$. \end{defn} \section{Ordre bien fondé} \subsection{Relation d'ordre bien fondée et induction} \begin{defn} Une relation d'ordre $\preceq$ sur un ensemble $E$ est dite bien fondée s'il n'existe pas de suite infinie strictement décroissante d'éléments de $E$. \end{defn} \begin{exemple} $\leqslant$ sur $\mathbb{N}$ est une relation bien fondée. $\leqslant$ sur $\mathbb{Z}$ n'est pas une relation bien fondée. \end{exemple} \begin{thm} La relation d'ordre sur $E$ est bien fondée si, et seulement si, toute partie non vide de $E$ admet un élément minimal (pour cet ordre). \end{thm} \begin{proof} Soit $E$ un ensemble ordonné par $\prec$, une relation d'ordre bien fondée. Soit $X$ une partie non vide de $E$. \fbox{$\implies$} Par l'absurde, supposons que $X$ n'admet pas d'élément minimal. Comme $X$ n'est pas vide, il existe $x_0$ dans $X$. Comme $x_0$ n'est pas minimal, il existe $x_1$ dans $X$. On peut ainsi construire \textit{de proche en proche} une suite infinie strictement décroissante, ce qui contredit la définition de $\preceq$. \fbox{$\impliedby$} Si toute partie non vide de $E$ admet un élément minimal, c'est en particulier le cas pour une suite strictement décroissante. Soit $(u_n)$ une suite strictement décroissante à valeur dans $X$. Soit $p\in\mathbb{N}$ l'indice de l'élément minimal de $(u_n)$. Tous les éléments d'indice supérieur à $p$ doivent être strictement plus petit que $u_p$, ce qui est impossible. $(u_n)$ est donc finie. Ainsi, le théorème est vrai. \end{proof} \begin{thm}[Induction] Soit $E$ un ensemble muni d'une relation d'ordre bien fondée $\preceq$ et $P$ une propriété de $E$. Si pour tout $x\in E$ et pour tout $y \prec x$ telle que $P(y)$ soit vraie, on a alors que $P$ est vraie pour tous les éléments de $E$. \end{thm} Ceci est une version généralisée de la récurrence. \begin{proof} Soit $X$ l'ensemble des $x$ tels que $P(x)$ soit faux. Si $X$ est non vide, $X$ admet un élément minimal (car $\preceq$ est bien fondée). Donc, tous les $y$ strictement plus petits que $x$ sont vrais. En utilisant l'hypothèse, $P(x)$ est aussi vraie. $X$ est donc vide. Ainsi, pour tout $e\in E$, $P(e)$ est vraie. \end{proof} \begin{lititle} Démonstration utilisant l'induction \end{lititle} Elle fonctionne de la même manière qu'une récurrence~: \begin{itemize} \item Si $x$ est un élément minimal, on démontre $P(x)$ sans aucune hypothèse. \item On suppose $P(y)$ pour tous les éléments plus petit que $x$ et on démontre $P(x)$. \end{itemize} \begin{exemple} Toutes les démonstrations par récurrence sur $(\mathbb{N},\leqslant)$ sont des inductions~! \end{exemple} \subsection{Ordre lexicographique} \begin{defn} Soient $(E_1,\preceq_1)\ldots(E_n,\preceq_n)$ des ensembles ordonnés. La relation d'ordre lexicographique $\preceq$ sur $E_1\times\ldots\times E_n$ est définie par~: $$ \exists i