 \documentclass{beamer}

%\input{beamer_settings}
\usepackage[algoruled,vlined,norelsize]{algorithm2e}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[frenchb]{babel}

\usepackage{amsfonts,latexsym,amsfonts,amsmath,amssymb,amsthm,amscd,stmaryrd,amstext,amscd}
\usepackage{array}
\usepackage{stmaryrd,mathrsfs}

\usepackage{bbm}
\usepackage{yhmath}

\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{arrows,automata,petri,positioning}

\usetikzlibrary{decorations.pathreplacing}
\usetikzlibrary{decorations.pathmorphing}
\usetikzlibrary{chains,fit,shapes}
\usetikzlibrary{patterns}

%\usetheme{metropolis}           % Use metropolis theme
\usetheme{Boadilla}
\usecolortheme{seahorse}
%\mode<presentation>
%{
 % \usetheme{Darmstadt}
  %\useoutertheme{infolines}
%}

%\usecolortheme{whale}
%\usecolortheme{orchid}
%\useinnertheme[shadow]{rounded}
%\useoutertheme{infolines}

\makeatother
\setbeamertemplate{footline}
{
  \leavevmode%
  \hbox{%
  \begin{beamercolorbox}[wd=.45\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
    \usebeamerfont{author in head/foot}\insertsection
      \end{beamercolorbox}%
  \begin{beamercolorbox}[wd=.45\paperwidth,ht=2.25ex,dp=1ex,center]{title in head/foot}%
    \usebeamerfont{title in head/foot}\insertsubsection
      \end{beamercolorbox}
      \begin{beamercolorbox}[wd=.1\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
    \usebeamerfont{author in head/foot}
    \insertframenumber{} / \inserttotalframenumber\hspace*{1ex}
  \end{beamercolorbox}}%
  \vskip0pt%
}
\makeatletter


%\input{defs}
\definecolor{darkgreen}{rgb}{0,0.7,0}
\newcommand{\green}[1]{{\color{darkgreen}#1}}
\newcommand{\red}[1]{{\color{red}#1}}

\newcommand{\define}[1]{\textbf{#1}}%\index{#1}}
\newcommand{\card}[1]{\textrm{Card}\left(#1\right)}%\index{#1}}

\newcommand{\Cl}[1]{\mathbf{Cl}(#1)}
\newcommand{\Lang}{\mathcal{L}}
\newcommand{\M}{\mathbbm{M}}
\newcommand{\N}{\mathbbm{N}}
\newcommand{\Z}{\mathbbm{Z}}
\newcommand{\Q}{\mathbbm{Q}}
\newcommand{\R}{\mathbbm{R}}
\newcommand{\C}{\mathbbm{C}}
\newcommand{\G}{\mathbbm{G}}
\newcommand{\K}{\mathbbm{K}}

\renewcommand{\P}{\mathcal{P}}

\newcommand{\Rel}{\mathcal{R}}
\newcommand{\A}{\mathcal{A}}

\newcommand{\U}{\mathbbm{U}}
\newcommand{\V}{\mathbbm{V}}


%%%TIKZ
\newcommand{\Eset}{(-4,-1) rectangle (4,4)}
\newcommand{\Aset}{(0,0) ++(135:2) circle (2)}
\newcommand{\Bset}{(0,0) ++(45:2) circle (2)}



\title{Relation}

%\author{Bérénice Delcroix-Oger \and Ralph Matthes \and Martin Strecker}
\institute{Université de Toulouse}
\date{Année 2020/2021} 


\begin{document}

%======================================================================

\begin{frame}
  \titlepage
\end{frame}


%======================================================================

%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%



\section{Relations}


\begin{frame}
\begin{center}
\textcolor{magenta}{{\huge \sc Relations}}
\end{center}
\end{frame}

\begin{frame}
\frametitle{Définition}

\begin{block}{Relation binaire}
Une \define{relation binaire} $\Rel$ d'un ensemble de départ $E$ vers un ensemble d'arrivée $F$ est définie par une partie $G_\Rel\subseteq E\times F$.

Si $(x, y)\in G_\Rel$, on dit que $x$ est \define{en relation avec} $y$ et l'on note $x\Rel y$.

Si $E=F$ on dit que $\Rel$ est une \define{relation interne} sur $E$.
\end{block}

\vspace{0.5cm}

\textbf{\underline{Exemples:}}
\begin{scriptsize}
Soient $A=\{a,b,c,d,e\}$ l'ensemble des élèves et $B=\{Math,Info,Ang, Phys\}$ l'ensemble des cours. On peut définir les relations suivantes:
\begin{itemize}
 \item $\Rel$ qui décrit si un étudiant suit un cours régulièrement: $$G_{\Rel}=\{(a,Math), (a,Phys), (b,Info), (c,Ang), (d,Ang), (e,Math),(e,Ang)\}$$
 \item la relation $\mathcal{S}$ décrit si un étudiant a acheté un cadeau à un autre étudiant définit par 
 $$G_{\mathcal{S}}=\{(b;a);(a;a);(c;a);(a;d);(d;c)\}$$ 
 \end{itemize} 
\end{scriptsize}

\end{frame}

%%%

\begin{frame}
\frametitle{Mode de représentation}

\textbf{\underline{Diagramme cartésien et matrice de relation}}
\begin{scriptsize}
$$\begin{array}{|c||c|c|c|c|}
\hline
\mathcal{R}&Math&Phys&Ang&Info\\
\hline
\hline
a&V&V&&\\
\hline
b&&&&V\\
\hline
c&&&V&\\
\hline
d&&&V&\\
\hline
e&V&&V&\\
\hline
\end{array}
\qquad
\qquad
\begin{array}{|c||c|c|c|c|c|}
\hline
\mathcal{S}&a&b&c&d&e\\
\hline
\hline
a&&&&V&\\
\hline
b&V&V&&&\\
\hline
c&V&V&&&\\
\hline
d&&&&V&\\
\hline
e&&&&&\\
\hline
\end{array}
$$
\end{scriptsize}

\textbf{\underline{Diagramme sagittal}}
\begin{scriptsize}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\tikzstyle{noeud}=[circle,draw,fill=gray!40]
\tikzstyle{noeudbis}=[draw,fill=gray!40]

 \node[noeud] (a) at (0,4) {$a$};
\node[noeud] (b) at (0,3) {$b$};
\node[noeud] (c) at (0,2) {$c$};
\node[noeud] (d) at (0,1) {$d$};
\node[noeud] (e) at (0,0) {$e$};
\node[noeudbis] (ma) at (3,0.5) {$Math$};
\node[noeudbis] (ph) at (3,1.5) {$Phys$};
\node[noeudbis] (an) at (3,2.5) {$Ang$};
\node[noeudbis] (in) at (3,3.5) {$Info$};
\path (a) edge (ma)
edge (ph);
\path (b) edge (in);
\path (c) edge (an);
\path (d) edge (an);
\path (e) edge (an);
\path (e) edge (ma);

\begin{scope}[xshift=7.8cm,yshift=3.3cm]
 \tikzstyle{noeud}=[circle,draw,fill=gray!40]
 \node[noeud] (a) at (0,0) {a};
\node[noeud] (c) at (0,-2) {b};
\node[noeud] (d) at (2,-2) {c};
\node[noeud] (e) at (4,-2) {d};
\node[noeud] (f) at (4,0) {e};
\path[->,>=latex] (a) edge[bend left=20] (e);
\path[->,>=latex] (c) edge (a)
					       edge[loop below] (c);;
\path[->,>=latex] (d) edge (a);
\path[->,>=latex] (e) edge (d);
\path[->,>=latex] (d) edge (c);
\end{scope}
\end{tikzpicture}
\end{center}

\end{scriptsize}

\end{frame}

%%%

\begin{frame}
\frametitle{Relation fonctionnelle} 

Une fonction $f:E\to F$ associe a chaque élément de $E$ au plus un élément de $F$. On peut alors définir la relation $\Rel_f$ définie par le graphe
\[G_{\Rel_f}=\left\{(x,f(x)):x\in E\right\}\subseteq E\times F.\]

\vspace{1cm}

Réciproquement, pour une relation $\Rel$ telle que pour tout $x\in E$ il y a au plus un $y\in F$ vérifiant $x\Rel y$ alors on peut lui associer une fonction $f$ telle que $f(x)=y$ si et seulement si $x\Rel y$. On dit que $\Rel$ est une \define{relation fonctionnelle}. 


\end{frame}

%%%

\begin{frame}
\frametitle{Relation réflexive}

\begin{block}{Réflexivité}
Une relation $\Rel$ est \define{réflexive} si pour tout $x\in E$ on a $x\Rel x.$ 
\end{block}

\begin{itemize}
\item Diagramme cartésien: la diagonale doit être notée.
\item Diagramme sagittal: chaque sommet admet une boucle.
\end{itemize}
\begin{center}
 \begin{scriptsize}

 \begin{tikzpicture}
\tikzstyle{noeud}=[circle,draw,fill=gray!40]
 \node[noeud] (a) at (-90:1) {1};
\node[noeud] (b) at (30:1) {2};
\node[noeud] (c) at (150:1) {3};
\path[->,>=latex] (a) edge (b)
							edge (c)
					       edge[loop below] (a);
\path[->,>=latex] (b) edge (c)
						edge[loop below] (c);
\path[->,>=latex] (c) edge[loop below] (c);


\begin{scope}[xshift=5cm,yshift=-0.4cm]
 \draw (0,0) node{
  $\begin{array}{|c||c|c|c|}
 \hline
 &1&2&3\\
 \hline
 \hline
1&V&V&V\\
\hline
2&&V&V\\
\hline
3&&&V\\
\hline
\end{array}$
};
\end{scope}
\end{tikzpicture}
\end{scriptsize}
\end{center}

\begin{scriptsize}
\textbf{\underline{Exemples:}}
Quel que soit l'ensemble, la relation d'égalité $=$ est réflexive. Sur $\N$, la relation $\leq$ est réflexive, mais $<$ n'est pas réflexive.

\textbf{\underline{Exemples:}}
Sur l'ensemble des mots $\A^\ast$, on considère la relation $\overset{l}{\equiv}$ définit par $u\overset{l}{\equiv} v$  si et seulement si $u$ et $v$ ont même longueur. Par exemple $\texttt{grand}\overset{l}{\equiv}\texttt{petit}$ et $\texttt{grand}\overset{l}{\equiv}\texttt{grand}$ mais $\texttt{grand}\not\overset{l}{\equiv}\texttt{grande}$. La relation $\overset{l}{\equiv}$ est réflexive.
\end{scriptsize}


\end{frame}


%%%

\begin{frame}
\frametitle{Relation symétrique}

\begin{block}{Symétrie}
Une relation $\Rel$ est \define{symétrique} si pour tout $x,y\in E$ on a 
$x\Rel y$ si et seulement si $y\Rel x.$ \end{block}

\begin{itemize}
\item Diagramme cartésien: symétrie par rapport à la diagonale.
\item Diagramme sagittal: quand une flèche va de $a$ vers $b$, il y a aussi une flèche de $b$ vers $a$.
\end{itemize}
\begin{center}
\begin{scriptsize}
 \begin{tikzpicture}
\tikzstyle{noeud}=[circle,draw,fill=gray!40]
 \node[noeud] (a) at (-90:1) {1};
\node[noeud] (b) at (30:1) {2};
\node[noeud] (c) at (150:1) {3};
\path[->,>=latex] (a) edge[bend left=20] (c)
					       edge[loop below] (a);
\path[->,>=latex] (c) edge[bend left=20] (a);
\path[->,>=latex] (b) edge[loop below] (b);


\begin{scope}[xshift=5cm,yshift=-0.4cm]
 \draw (0,0) node{
  $\begin{array}{|c||c|c|c|}
 \hline
 &1&2&3\\
 \hline
 \hline
1&V&&V\\
\hline
2&&V&\\
\hline
3&V&&\\
\hline
\end{array}$
};
\end{scope}
\end{tikzpicture}
\end{scriptsize}
\end{center}
\begin{scriptsize}
\textbf{\underline{Exemples:}}
Quel que soit l'ensemble, la relation d'égalité $=$ est symétrique. Sur $\N$, la relation $\leq$ est n'est pas symétrique. 

La relation $\overset{l}{\equiv}$ sur $\A^\ast$ est symétrique.
\end{scriptsize}


\end{frame}
%%%

\begin{frame}
\frametitle{Relation transitive}

\begin{block}{Transitivité}
 Une relation $\Rel$ est \define{transitive} si pour tout $x,y,z\in E$ tel que 
$x\Rel y$ et $y\Rel z$ alors nécessairement on a $x\Rel z$.
\end{block}
\begin{itemize}
\item Diagramme sagittal: tout chemin qui part d'un sommet $s$ et va à un sommet $s'$ en suivant la direction des flèches admet un raccourci, c'est à dire un chemin de  longueur un. 
\end{itemize}
\begin{center}
\begin{scriptsize}
 \begin{tikzpicture}
\tikzstyle{noeud}=[circle,draw,fill=gray!40]
 \node[noeud] (a) at (0,0) {1};
\node[noeud] (b) at (1.5,-1.5) {2};
\node[noeud] (c) at (1.5,0) {3};
\node[noeud] (d) at (3,0) {4};
\path[->,>=latex] (b) edge (a)
							edge (c)
							edge (d)
					       edge[loop below] (b);
\path[->,>=latex] (d) edge (c);
\path[->,>=latex] (a) edge (c);


\begin{scope}[xshift=7cm,yshift=-0.8cm]
 \draw (0,0) node{
  $\begin{array}{|c||c|c|c|c|}
 \hline
 &1&2&3&4\\
 \hline
 \hline
1&&&V&\\
\hline
2&V&V&V&V\\
\hline
3&&&&\\
\hline
4&&&V&\\
\hline
\end{array}$
};
\end{scope}
\end{tikzpicture}
\end{scriptsize}
\end{center}
\vspace{-0.5cm}
\begin{scriptsize}
\textbf{\underline{Exemples:}}
Quel que soit l'ensemble, la relation d'égalité $=$ est transitive. 
Sur $\N$, la relation $\leq$ est transitive. 
La relation "est le père de" n'est pas transitive. 
\end{scriptsize}\end{frame}

%%%

\begin{frame}
\frametitle{Relation antisymétrique}

\begin{block}{Antisymétie} 
Une relation $\Rel$ est \define{antisymétrique} si pour tout $x,y\in E$ vérifiant $x\Rel y$ et $y\Rel x$ alors on a $x=y.$ 
\end{block}


\begin{center}
\begin{scriptsize}
 \begin{tikzpicture}
\tikzstyle{noeud}=[circle,draw,fill=gray!40]
 \node[noeud] (a) at (0,0) {1};
\node[noeud] (b) at (1.5,-1.5) {2};
\node[noeud] (c) at (1.5,0) {3};
\node[noeud] (d) at (3,0) {4};
\path[->,>=latex] (d) edge[bend right=35] (a)
					       edge[loop below] (d);
\path[->,>=latex] (b) edge (a)
							edge (d);
\path[->,>=latex] (c) edge (b)
							edge (d);
\path[->,>=latex] (a) edge (c);


\begin{scope}[xshift=7cm,yshift=-0.8cm]
 \draw (0,0) node{
  $\begin{array}{|c||c|c|c|c|}
 \hline
 &1&2&3&4\\
 \hline
 \hline
1&&&V&\\
\hline
2&V&&&V\\
\hline
3&&V&&V\\
\hline
4&V&&&V\\
\hline
\end{array}$
};
\end{scope}
\end{tikzpicture}
\end{scriptsize}
\end{center}

\begin{scriptsize}
\textbf{\underline{Exemples:}}
 Sur $\N$, la relation $\leq$ est antisymétrique. 

La relation $\overset{l}{\equiv}$ sur $\A^\ast$ n'est pas antisymétrique.
\end{scriptsize}\end{frame}


%%%

\subsection{Relations d'équivalence}

\begin{frame}
\begin{center}
\textcolor{magenta}{{\huge \sc Relations d'équivalence}}
\end{center}
\end{frame}

%%%

%%%

\begin{frame}
\frametitle{Définition et exemples}

\begin{block}{Définition}
 Une relation binaire définie sur un unique ensemble $E$ est une \define{relation d'équivalence} si elle est réflexive, symétrique et transitive.
\end{block}
\begin{scriptsize}

\vspace{1cm}
\textbf{\underline{Exemples:}}
Par définition, pour $x,y\in\Z$, on note $x\equiv y [\textrm{mod }n]$, lire $x$ est congru à $y$ modulo $n$, si et seulement s'il existe $k\in\Z$ tel que $x-y=kn$. On a défini une relation d'équivalence sur $\Z$ car on peut vérifier:
\begin{itemize}
 \item \textbf{Réflexivité:} $x\equiv x [\textrm{mod }n]$ car $x-x=0.n$ et $0\in\Z$.
 \item \textbf{Symétrie:} si $x\equiv y [\textrm{mod }n]$ alors il existe $k\in\Z$ tel que $x-y=k.n$, on a donc $y-x=-k.n$ et $-k\in\Z$ d'où $y\equiv x [\textrm{mod }n]$.
 \item \textbf{Transitivité:} si $x\equiv y [\textrm{mod }n]$ et $y\equiv z [\textrm{mod }n]$ alors il existe $k,k'\in\Z$ tels que $x-y=k.n$ et $y-z=k'.n$. Ainsi $x-z=x-y+y-z=(k+k').n$. On en déduit que $x\equiv z [\textrm{mod }n]$
\end{itemize}
\end{scriptsize}
\end{frame}

%%%

\begin{frame}
\frametitle{Définition et exemples}

\begin{block}{Définition}
 Une relation binaire définie sur un unique ensemble $E$ est une \define{relation d'équivalence} si elle est réflexive, symétrique et transitive.
\end{block}
\begin{scriptsize}

\vspace{1cm}
\textbf{\underline{Exemples:}}
\begin{itemize}
\item Sur n'importe quel ensemble la relation $=$ est une relation d'équivalence..
\item Sur l'ensemble des mot $\A^{\ast}$, la relation $\overset{l}{\equiv}$ est une relation d'équivalence.
 \item Sur l'ensemble des personnes, la relation "a le même âge que" est une relation d'équivalence. Des personnes liées appartiennent à la même tranche d'âge. 
 \item Sur l'ensemble des triangles, la relation "a les mêmes angles que" est une relation d'équivalence. Des triangles liés par cette relation sont dits semblables. 
 \item La relation $\mathcal{R}$ définie sur $\R\smallsetminus\{0\}$ par $x\mathcal{R}y$ si et seulement si $xy>0$ est une relation d'équivalence. Deux réels liés par cette relation ont le même signe.  
\end{itemize}
\end{scriptsize}
\end{frame}

%%%

\begin{frame}
\frametitle{Classes d'équivalence et partition}

\begin{block}{Classes d'équivalence}
 Soit $\mathcal{R}$ une relation d'équivalence  sur un ensemble $E$. La \define{classe d'équivalence} d'un élément $x$, noté $\Cl{x}$, est l'ensemble des éléments de $E$ qui sont en relation avec $x$. Autrement dit
 \[\Cl{x}=\{y\in E: x\mathcal{R} y\}.\]
\end{block}

\begin{exampleblock}{Proposition}
 Une classe d’équivalence n’est jamais vide.
 
 \vspace{0.3cm}
  L’intersection de deux classes d’équivalence distinctes est vide.
\end{exampleblock}

\end{frame}
%%%
\begin{frame}
\frametitle{Classes d'équivalence et partition}

\begin{block}{Partition}
 Soit $E$ un ensemble, la famille d'ensembles $(A_i)_{i\in I}$ indexée par $I$ est une \define{partition} si:
\begin{itemize}
 \item l'union des $(A_i)_{i\in I}$ est égale à $E$, c'est à dire $E=\cup_{i\in I}A_i$,
 \item deux éléments de $(A_i)_{i\in I}$ distincts sont disjoints, c'est à dire que si $i\ne j$ alors  $A_i\cap A_j=\emptyset$.
\end{itemize}
\end{block}

\begin{exampleblock}{Théorème}
 Etant donné une relation d'équivalence sur un ensemble, les classes d'équivalences forment une partition.
\end{exampleblock}

\end{frame}

%%%

\begin{frame}
\frametitle{Ensemble quotient}

\begin{block}{Ensemble quotient}
 Soit $E$ un ensemble munit d'une relation d'équivalence $\mathcal{R}$. L'ensemble quotient est l'ensemble des classes d'équivalence de tous les éléments de $E$. On le note $E/\mathcal{R}$.
 \end{block}

\begin{exampleblock}{Théorème}
Etant donné une relation d'équivalence $\Rel$ sur $E$, la fonction suivante est surjective:
$$
\begin{array}{cccc}
 f:&E&\longrightarrow&E/\Rel\\
 &x&\longmapsto&\Cl{x}
\end{array}
$$
\end{exampleblock}

\end{frame}


%%%

\subsection{Relations d'ordre}

\begin{frame}
\begin{center}
\textcolor{magenta}{{\huge \sc Relations d'ordre}}
\end{center}
\end{frame}


%%%

%%%

\begin{frame}
\frametitle{Définition}

\begin{block}{Définition}
  Une relation binaire $\preceq$ sur un ensemble $E$ est une \define{relation d'ordre} si elle est réflexive, transitive et antisymétrique. Autrement dit:
 \begin{description}
\item[$\preceq$ réflexive:]  on a $x\preceq x$ pour tout $x\in E$.
\item[$\preceq$ transitive:] si $x\preceq y$ et $y\preceq z$ alors $x\preceq z$.
\item[$\preceq$ antisymétrique:] si $x\preceq y$ et $y\preceq x$ alors $x=y$.
\end{description}
\end{block}
 
 Un ordre est \define{total} si pour tous éléments $x,y\in E$ on a  $x\preceq y$ ou $y\preceq x$. Un ordre est dit \define{partiel} pour souligner qu'on n'a pas forcément cette propriété. 
\end{frame}

%%%

\begin{frame}
\frametitle{Exemples d'ordres sur les nombres}

\begin{itemize}
\item  $\leq$ et $\geq$ sont des relations d'ordre total sur $\N$ qui s'étendent à $\Z$, $\Q$ ou $\R$.
\item$<$ et $>$ ne sont pas des relations d'ordre sur $\N$ .
\item Sur $\N^{\ast}$ la relation $a$ divise $b$, notée $a|b$, est une relation d'ordre mais n'est pas total. On rappelle que $a$ divise $b$ s'il existe $k\in\N^{\ast}$ tel que $b=a\,k$.
 \begin{description}
\item[$\preceq$ réflexive:]  on a $x\preceq x$ pour tout $x\in \N^{\ast}$.
\item[$\preceq$ transitive:] si $x$ divise $y$ (c'est à dire il existe $k$ tel que $y=k\, x$) et $y$ divise $z$ (c'est à dire il existe $k$ tel que $z=k'\, y$) alors $z=k'\, y=(k\,\k')\,x$ donc $x$ divise $z$.
\item[$\preceq$ antisymétrique:] si $x\preceq y$ et $y\preceq x$ alors $x=y$.
\end{description}
\end{itemize}

\end{frame}

%%%

\begin{frame}
\frametitle{Exemples d'ordre ordres sur les parties d'un ensemble}
Soit $E$ un ensemble l'inclusion, notée $\subseteq$, est une relation d'ordre sur l'ensemble des parties $\P(E)$ qui n'est pas totale.

 \begin{description}
\item[$\preceq$ réflexive:]  on a $A\subseteq A$ pour tout $A\in \P(E)$.
\item[$\preceq$ transitive:] si $A\subseteq B$ et $B\subseteq C$ alors $A\subseteq C$.
\item[$\preceq$ antisymétrique:] si $A\subseteq B$ et $B\subseteq A$ alors $A=B$.
\end{description}

\end{frame}

%%%

\begin{frame}
\frametitle{Ordres sur les mots}
Il existe différentes notions pour ordonner l'ensemble des mots $\A^{\ast}$:
\begin{itemize}
\item La relation $u$ est préfixe de $v$, notée $u\sqsubseteq_{\textrm{perd}} v$ et définit par $\exists w\in\A^{\ast}$ tel que $v=u.w$, est une relation d'ordre qui n'est pas total 

\item Soit $\preceq$ un ordre total sur $\A$ on définit l’\define{ordre lexicographique} sur $\A^\ast$:
$$u\leq_{lex} v \Longleftrightarrow \begin{cases}u \textrm{ préfixe de }v\\
\textrm{ ou bien}\\
 \exists m\in\N\textrm{ tel que } u_1\dots u_m=v_1\dots v_m \textrm{ et } u_{m+1}\leq v_{m+1}\end{cases}$$
C'est une relation d'ordre total sur $\A^\ast$. Par exemple:

 $\texttt{a}\leq_{lex}\texttt{fa}$, $\texttt{poule}\leq_{lex}\texttt{poulet}$, $\texttt{avion}\leq_{lex}\texttt{train}$, $\texttt{livraison}\leq_{lex}\texttt{livre}$, $\texttt{foot}\leq_{lex}\texttt{fort}$.
\end{itemize}
 
 
\end{frame}

%%%

\begin{frame}
\frametitle{Mode de représentation}

\begin{center}
\begin{scriptsize}
 \begin{tikzpicture}
\tikzstyle{noeud}=[circle,draw,fill=gray!40]
 \node[noeud] (a) at (-90:1) {1};
\node[noeud] (b) at (30:1) {2};
\node[noeud] (c) at (150:1) {3};
\path[->,>=latex] (a) edge (b)
							edge (c)
					       edge[loop below] (a);
\path[->,>=latex] (b) edge (c)
						edge[loop below] (c);
\path[->,>=latex] (c) edge[loop below] (c);


\begin{scope}[xshift=5cm,yshift=-0.4cm]
 \draw (0,0) node{
 \begin{normalsize}
  $\begin{array}{|c||c|c|c|}
 \hline
 &1&2&3\\
 \hline
 \hline
1&V&V&V\\
\hline
2&&V&V\\
\hline
3&&&V\\
\hline
\end{array}$
\end{normalsize}
};
\end{scope}
\end{tikzpicture}
\end{scriptsize}
\end{center}

Pour simplifier la lecture du diagramme, on supprime les boucles dues à la réflexivité et les flèches déductibles par transitivité:

\begin{center}
\begin{scriptsize}
 \begin{tikzpicture}
\tikzstyle{noeud}=[circle,draw,fill=gray!40]
 \node[noeud] (a) at (0,0) {1};
\node[noeud] (b) at (1.5,0) {2};
\node[noeud] (c) at (3,0) {3};
\path[->,>=latex] (a) edge (b);
\path[->,>=latex] (b) edge (c);
\end{tikzpicture}
\end{scriptsize}
\end{center}

L'idée est de représenter les sommets du diagramme et tracer seulement les flèches correspondant aux successeurs immédiats. On dit que $y$ est un successeur immédiat de $x$ si $x\preceq y$, $x\ne y$ et il n'existe pas de $z$ tel que $x\preceq z \preceq y$.
 
 
\end{frame}

%%%

\begin{frame}
\frametitle{Fonctions croissantes et décroissantes}
\begin{block}{Definition}
 Soient $A$ et $B$ deux ensembles munis respectivement des relations d'ordre $\preceq_A$ et $\preceq_B$ et $f:A\longrightarrow B$ une application. On dit que
\begin{itemize}
 \item $f$ est \define{croissante} si $x\preceq_A y$ alors $f(x) \preceq_B f(y)$.
 \item $f$ est \define{décroissante} si $x\preceq_A y$ alors $f(y) \preceq_B f(x)$.
 \item $f$ est \define{strictement croissante} si $x\preceq_A y$ et $x\ne y$ alors $f(x) \preceq_B f(y)$ et $f(x)\ne f(y)$.
 \item $f$ est \define{strictement décroissante} si $x\preceq_A y$ et $x\ne y$ alors $f(y) \preceq_B f(x)$ et $f(x)\ne f(y)$.
\end{itemize}
\end{block}

\begin{exampleblock}{Proposition}
 Une application strictement croissante ou strictement décroissante dont l'espace de départ est muni d'un ordre total est injective.
\end{exampleblock}
 
\end{frame}

%%%

\begin{frame}
\frametitle{Elément minimal, borne inférieure}

Soit $(E,\preceq)$ un ensemble ordonné et $A\subseteq E$.

\begin{itemize}
\item $x\in A$ est \define{minimal} de $A$ s'il n'admet pas d'élément plus petit dans $A$.

\item $x\in E$ \define{minorant} de $A$ si $\forall y\in A$ on a $x\preceq y$

\item $A$ admet au plus un seul minorant dans $A$ (par antisymétrique), c'est \define{le plus petit élément} de $A$, s'il existe on le note $\textrm{min}(A)$.

\item Le plus grand des minorants est la \define{borne inférieure}, on la note $\inf(A)$. Autrement dit:

$$\forall y\in A\textrm{ on a }\inf(A)\preceq y\textrm{ et }\forall z\textrm{  minorant de $A$ on a }z\preceq \inf(A)$$
\end{itemize}

\end{frame}

%%%

\begin{frame}
\frametitle{Elément maximal, borne supérieure}

Soit $(E,\preceq)$ un ensemble ordonné et $A\subseteq E$.

\begin{itemize}
\item $x\in A$ est \define{maximal} de $A$ s'il n'admet pas d'élément plus grand dans $A$.

\item $x\in E$ \define{majorant} de $A$ si $\forall y\in A$ on a $y\preceq x$

\item $A$ admet au plus un seul majorant dans $A$ (par antisymétrique), c'est \define{le plus grand élément} de $A$, s'il existe on le note $\textrm{max}(A)$.

\item Le plus petit des majorants est la \define{borne supérieure}, on la note $\sup(A)$. Autrement dit:

$$\forall y\in A\textrm{ on a }y\preceq \sup(A) \textrm{ et }\forall z\textrm{  majorant de $A$ on a }\sup(A)\preceq z$$
\end{itemize}

\end{frame}

%%%

\subsection{Induction}

\begin{frame}
\begin{center}
\textcolor{magenta}{{\huge \sc Induction}}
\end{center}
\end{frame}


%%%

\begin{frame}
\frametitle{Ordre bien fondé}

\begin{block}{Définition}
 Un ensemble ordonné $(E,\preceq)$ est \define{bien fondé} s'il n'existe pas de suite infinie strictement décroissante d'éléments de $E$.\end{block}
 
 De manière équivalente, on a:
 
\begin{exampleblock}{Théorème}
 Un ensemble ordonné $(E,\preceq)$ est bien fondé si et seulement si toute partie non vide admet au moins un élément minimal.
\end{exampleblock}
\underline{\textbf{Examples}}
\begin{itemize}
\item L'ordre usuel $\leq$ sur $\N$ est bien fondé mais il ne l'est pas sur $\Z$, $\R$, $[0,1]$.

\item L'ordre $|$ sur $\N\setminus\{0,1\}$ défini par "$a|b\Longleftrightarrow$ $a$ divise $b$" est bien fondé. 

\item Soit $\A$ un alphabet contenant au moins deux lettres, $\sqsubseteq_{\textrm{perd}}$ est bien fondé mais pas $\leq_{lex}$.
\end{itemize}
 
\end{frame}
%%%

\begin{frame}
 \frametitle{Application à la terminaison d'algorithme}
 
\begin{block}{Variant de boucles}
  Etant donné $(E,\preceq)$ un ordre bien fondé, un \define{variant} de boucle est une fonction de l'ensemble des états du programme dans $E$ strictement décroissant à chaque passage dans la boucle. 
\end{block}
 
\begin{exampleblock}{Proposition}
 Si une boucle admet un variant alors elle termine. 
\end{exampleblock} 

\textbf{Algorithme d'Euclide:}

\begin{small}
 
Donnée: $(x,y)\in\N^2$

Résultat: le pgcd de $x$ et $y$

$a\gets x$\;

$b\gets y$\;

\While{$b\ne 0$}{

$tmp\gets a$\;

$a\gets b$\;

$b\gets tmp [\textrm{mod }b]$\;
}

\end{small}

\end{frame}

%%%

\begin{frame}
 \frametitle{Application à la terminaison des algorithmes récursifs}

\begin{exampleblock}{Proposition}
 Soit $f$ une fonction récursive définit sur un ensemble ordonné $(E,\preceq)$ bien fondé. Si $f$ est défini sur les éléments minimaux et si pour tout $x\in E$ non minimal, le définition de $f(x)$ ne fait appel à des valeurs $f(y)$ pour $y\preceq x$ avec $x\ne y$ alors $f$ est bien définit. 
 \end{exampleblock}

\textbf{Examples:}

\begin{small}

$\bullet$ On considère la fonction $\texttt{fact}$ définie par:
\begin{itemize}
 \item $\texttt{fact}(0)=1$;
 \item $\texttt{fact}(n+1)=(n+1)*\texttt{fact}(n)$.
\end{itemize}
Elle est bien définie car $(\N,\leq)$ est bien fondé.


$\bullet$  On considère la fonction $f$ définie sur $\N\setminus\{0,1\}$ par:
\begin{itemize}
 \item $f(p)=1$ si $p$ premier;
 \item $f(n)=f(a)+f(b)$ si $n=ab$ et $a\ne1$ et $b\ne 1$.
\end{itemize}
Elle est bien définie car $(\N\setminus\{0,1\},|)$ est bien fondé.
 \end{small}

\end{frame}


%%%

\begin{frame}
\frametitle{$\N$ et le principe de récurrence}
\begin{exampleblock}{Principe de récurrence}
 Soit $P$ une propriété dépendant d'un élément $n$ de $\N$. Si les deux hypothèses suivantes sont vérifiées
 \begin{description}
\item[Initialisation:] $P(0)$ est vraie,
\item[Héridité:]  $\forall n\in\N$ on a "$P(n)\textrm{ est vraie}\Longrightarrow P(n+1)\textrm{ est vraie}$"
\end{description}
 
 Alors pour tout $n\in\N$, la propriété $P(n)$ est vraie. 
\end{exampleblock}
 

 \begin{scriptsize}

\textbf{\underline{Preuve:}}
On raisonne par l'absurde: supposons que les hypothèses du théorème sont vraies mais que la conclusion est fausse. 
 
 Soit $X=\{n\in\N, P(n)\textrm{ est fausse}\}$. L'ensemble $X$ est une partie non vide de $\N$, comme $(\N,\leq)$ est bien fondé, $X$ admet un plus petit élément noté $n_0$.
 
 Comme $P(0)$ est vraie, on a $n_0>0$ donc $n_0-1$ est un entier positif ou nul, autrement dit $n_0-1\in\N$. $P(n_0-1)$ est vraie car $n_0-1\notin X$. Par hypothèse $P(n_0-1)\Longrightarrow P(n_0)$ donc $P(n_0)$ est vraie ce qui est contradictoire avec le fait que $n_0\in X$.
\end{scriptsize}
 
\end{frame}



%%%

\begin{frame}
\frametitle{$\N$ et le principe de récurrence généralisé}
\begin{exampleblock}{Principe de récurrence généralisé}
 Soit $P$ une propriété dépendant d'un élément $n$ de $\N$. Si les deux hypothèses suivantes sont vérifiées
 \begin{description}
\item[Initialisation:] $P(0)$ est vraie,
\item[Héridité:]  $\forall n\in\N$ on a "$P(k)\textrm{ est vraie pour }k<n \Longrightarrow P(n)\textrm{ est vraie}$"
\end{description}
 
 Alors pour tout $n\in\N$, la propriété $P(n)$ est vraie. 
\end{exampleblock}
 

 \begin{scriptsize}

\textbf{\underline{Preuve:}}

 On applique le principe de récurrence du théorème précédent à la propriété $Q$ tel que pour $n\in\N$, $Q(n)$ est vraie si $P(k)$ est vraie pour tout $k\leq n$. 


\end{scriptsize}
 
\end{frame}

%%%

\begin{frame}
\frametitle{Principe d'induction}

 \begin{exampleblock}{Principe d'induction}
  Soit $P$ une propriété dépendante d'un élément $x$ de $E$ muni d'un ordre bien fondé $\preceq$. Si les deux hypothèses suivantes sont vérifiées: \begin{description}
\item[Initialisation:] $P(x)$ est vraie pour tout éléments minimaux de $E$,
\item[Héridité:]  Si pour tout $x\in E$ qui n'est pas minimal on a :$$P(y)\textrm{ est vraie }\forall y\preceq x \textrm{ avec }y\ne x  \Longrightarrow P(x)\textrm{ est vraie}$$
\end{description}
 
 Alors pour tout $x\in E$, la propriété $P(x)$ est vraie. 
\end{exampleblock}
 

 \begin{scriptsize}

\textbf{\underline{Preuve:}}
On raisonne par l'absurde. 
 
 Soit $X=\{x\in E, P(x)\textrm{ est fausse}\}$. L'ensemble $X$ est une partie non vide de $E$, comme $(E,\preceq)$ est bien fondé, $X$ admet un plus petit élément noté $x_0$.
 
 Comme $P$ est vraie pour tout élément minimal de $E$, l'élément $x_0$ n'est pas minimal. Pour tout $y\in E$ tel que $y\preceq x_0$ et $y\ne x_0$, la propriété $P(y)$ est vraie car $x_0$ minimal dans $X$ et donc $y\notin X$ . Par hypothèse d'hérédité $P(x_0)$ est vraie ce qui est contradictoire avec le fait que $x_0\in X$.
 \end{scriptsize}
 
\end{frame}

%%%

\begin{frame}
\frametitle{Définition inductive}

 
\begin{block}{Définition inductive d'un ensemble}
  Soit $E$ un ensemble. Une définition inductive d'un sous-ensemble $X$ de $E$ consiste à la donnée:
 \begin{itemize}
\item d'un sous-ensemble $B$ de $E$ appelé \define{base},
\item d'un ensemble $K$ d'opérations $\varphi:E^{r_{\varphi}}\longrightarrow E$ où $r_{\varphi}$ est l'arité de $\varphi$.
\end{itemize}

L'ensemble $X$ est alors défini comme le plus petit (pour l'inclusion) ensemble vérifiant les assertions suivantes:
 \begin{description}
\item[Base:] $B\subseteq X$,
\item[Induction:] pour tout $\varphi\in K$ et pour tous $x_1,x_2,\dots,x_{r_{\varphi}}\in X$ on a $\varphi(x_1,x_2,\dots,x_{r_{\varphi}})\in X$.
\end{description}

On dit que $X$ est la \define{fermeture inductive de $B$ par $K$}.
\end{block}
 
 \end{frame}

%%%



\begin{frame}
\frametitle{ Quelques ensembles définis inductivement:}


\begin{small}
\begin{itemize}
\item L'ensemble des entiers naturels est défini par:
 \begin{itemize}
 \item[Base:] $B=\{0\}$,
 \item[Induction:] $\begin{array}{rccc}\textrm{succ}:&\N&\longrightarrow\N \\ 
 &n&\longmapsto& n+1\end{array}$.
\end{itemize}
\item L'ensemble des entiers pairs est défini par:
 \begin{itemize}
 \item[Base:] $B=\{0\}$,
 \item[Induction:] $\begin{array}{rccc}\varphi:&\N&\longrightarrow\N \\ 
 &n&\longmapsto& n+2\end{array}$.
\end{itemize}
\item L'ensemble des entiers impairs est défini par:
 \begin{itemize}
 \item[Base:] $B=\{1\}$,
 \item[Induction:] $\begin{array}{rccc}\varphi:&\N&\longrightarrow\N \\ 
 &n&\longmapsto& n+2\end{array}$.
\end{itemize}
\item L'ensemble des mots binaires est défini par:
 \begin{itemize}
 \item[Base:] $B=\{\varepsilon\}$,
 \item[Induction:] $\begin{array}{rccc}\varphi_0:&\A^{\ast}&\longrightarrow\A^{\ast} \\ 
 &u&\longmapsto& 0u\end{array}$ et $\begin{array}{rccc}\varphi_1:&\A^{\ast}&\longrightarrow\A^{\ast} \\ 
 &u&\longmapsto& 1u\end{array}$.
  \end{itemize}
  \end{itemize}
 
\end{small}

\end{frame}

%%%

\begin{frame}
 \frametitle{Preuve pour des ensembles définis par induction}
 
 \begin{exampleblock}{Preuve par induction}
 Soit $X\subseteq E$ la fermeture inductive de $B$ par $K$. Soit $P$ une propriété définie sur $X$. Pour montrer que pour tout $x\in X$ la propriété $P(x)$ est vraie, il suffit de montrer que:
 \begin{description}
\item[Base:] Pour tout $x\in B$, on a $P(x)$ vraie.
\item[Induction] Pour tout $\varphi\in K$ d'arité $r_{\varphi}$ et tous $x_1,x_2,\dots,x_{r_{\varphi}}$ alors on a
$$P(x_1),P(x_2),\dots,P(x_{r_{\varphi}})\textrm{ vraies }\Longrightarrow P(\varphi(x_1,x_2,\dots,x_{r_{\varphi}}))\textrm{ vraie}$$
\end{description}
\end{exampleblock}
\end{frame}

%%%

\begin{frame}
\frametitle{Exemple de preuve par induction}
\begin{scriptsize}
 On considère l'ensemble des mots de Dyck $\Delta\subseteq\{0,1\}^{\ast}$  défini par:
\begin{itemize}
 \item \textcolor{blue}{Base:} $B=\{\varepsilon\}$,
 \item \textcolor{blue}{Induction:} $\begin{array}{rccc}\psi:&\A^{\ast}\times\A^{\ast}&\longrightarrow\A^{\ast} \\ 
 &(u,v)&\longmapsto& 0u1v\end{array}$.
 \end{itemize} 
 
 On veut montrer par induction que tout mot $w\in\Delta$ vérifie la propriété $P(w)$: "$w$ a autant de $0$ que de $1$ et tout préfixe de $w$ a plus de $0$ que de $1$". 

\begin{itemize}
 \item \textcolor{blue}{Base:} $\varepsilon$ vérifie la propriété demandée,
 \item \textcolor{blue}{Induction:} Soient $u,v\in\Delta$ tels que $P(u)$ et $P(v)$ soient vérifiées. On note $w=\psi(u,v)=0u1v$. Comme $u$ et $v$ ont autant de $0$ et de $1$, il en est de même pour $w$. Soit $t$ un préfixe de $w$. Il y a deux cas:
 \begin{itemize}
 \begin{scriptsize}
\item Si $|t|\leq1+|u|$ alors $t$ est un préfixe de $0u$. Il s'écrit $t=0t'$ où $t'$ est un préfixe de $u$. Comme les préfixes de $u$ ont plus de $0$ que de $1$, on en déduit que  $t$ a plus de $0$ que de $1$.  
\item Si $|t|>1+|u|$ alors $t$ s'écrit $t=0u1t'$ où $t'$ est un préfixe de $v$. Comme les préfixes de $v$ ont plus de $0$ que de $1$, on en déduit que $t$ a plus de $0$ que de $1$.
\end{scriptsize}

\end{itemize}

 \end{itemize} 

\end{scriptsize}

\end{frame}

\end{document}

