\documentclass{article}

\usepackage{a4}
\usepackage{francais,t1enc}

\renewcommand{\S}{\textbf{S}}
\newcommand{\N}{\texttt{\small |}\!\textsf{N}}
\newcommand{\R}{\texttt{\small |}\!\textsf{R}}
\newcommand{\vDash}{\mathop{|\!\!\!=}}
\newcommand{\pr}{\mathop{\underline{\textsf{prefix}}}}
\newcommand{\mlt}{\prec\!\!\prec}
\newcommand{\inferLabel}[3]{
    {#1} \quad 
    \begin{array}{c}
      #2\\
      \hline \noalign{\vskip 1pt}#3
    \end{array}
  }

\begin{document}
\title{Magist�re d'Informatique et Mod�lisation}
\author{Devoir de Logique~: \emph{induction et ordres}}
\date{� remettre le 12 octobre 2000}

\maketitle 

\subsection*{Exercice 1~: bornes sup�rieures}


Soit $(E, <)$ un ensemble ordonn�. Un \emph{majorant} d'un
sous-ensemble $A$ de $E$ est un el�ment $m\in E$ tel que $(\forall
a\in A)~ m >a$.  Un �l�ment $b$ est le \emph{minimum} de $A$ si $b\in
A$ et si $(\forall a\in A)~ b\le a$.  Un �l�ment est la \emph{borne
  sup�rieure} de $A$ si c'est le minimum de l'ensemble des majorants
de $A$.

\begin{enumerate}
\item Quelle est, si elle existe, la borne sup�rieure de $\emptyset$~?
  De $E$~?
\item Quelles sont les conditions d'existence de cette borne sup�rieure~?
\end{enumerate}


\subsection*{Exercice~2~: fermeture transitive}

Si $R$ et $T$ sont  deux relations binaires not�es de fa�on infix�e
(c-�-d, $x~R~y$). On d�finit  
\begin{itemize}
\item $x~R\,T~y$ si et seulement si il existe $z$ tel que
$x~R~z$ et $z~T~y$.  

\item $R^n$ par $R^1=R$ et $R^{n+1} = R\,R^n$.  

\item $R \subseteq T$ si et
  seulement $x~R~y$ implique $x~T~y$.

\item $x~(R\bigcup T)~y$ ssi $x~R~y$ ou $x~T~y$.
\end{itemize}
Une relation est transitive si $x~R~y$ et $y~R~z$ impliquent $x~R~z$.
La \emph{fermeture transitive} de $R$ est la plus petite relation transitive
qui contient $R$.
\begin{enumerate}
\item Montrez que $R$ est transitive si et seulement si $ R\,R
  \subseteq R$.

\item Montrez que la fermeture transitive est la relation
\[\bigcup^{\infty}_{n=1}R^n.\]
\end{enumerate}

On note $R^+$ la fermeture transtive de $R$.

\subsection*{Exercice 3~: ordre bien fond�}

Une relation transitive est aussi appel�e un \emph{pr�ordre}.

Une relation $>$ est \emph{noeth�rienne} (ou \emph{bien fond�e}), si
toute suite infinie 
$(x_i)_{i\in \N}$ \emph{d�croissante} (\mbox{c-�-d} telle
que\footnote{$a\ge b$ signifie <<$a>b$ ou $a=b$>>.}  $(\forall
i\in\N)(\forall\ j\in\N) i<j \Rightarrow x_i\ge x_j$) est 
\emph{stationnaire} (\mbox{c-�-d} telle qu'il existe un $k\in\N$ qui
satisfait $(\forall i\in\N)\ x_i=x_k$).  De fa�on �quivalente, cela
signifie qu'il n'existe pas de suite infinie \emph{strictement
  d�croissante} (\mbox{c-�-d} telle $(\forall i\in\N)\mbox{$(\forall
  j\in\N$})\ i>j \Rightarrow x_i> x_j$).

Le produit lexicographique de deux relations $R$ sur $E$ et $T$ sur
$F$ est une relation $R\times T$ sur $E\times F$ telle que
$(x_1,y_1)~R\times T~(x_2,y_2)$ si $x_1~R~x_2$ ou $x_1=x_2$ et
$y_1~T~y_2$.
\begin{enumerate}
\item Montrez qu'une relation $<$ est noeth�rienne si et seulement si
  toute partie non vide admet un minimal\footnote{Un �l�ment $m\in A$
    est un \emph{minimal} de $A$ si $x<m$ implique $x\not\in A$.} pour
  le pr�ordre $<^+$.

\item Construisez un ordre bien fond� dans lequel il y a un �l�ment
  ayant un ensemble infini de minorants.

\item Montrez que le produit lexicographique de deux pr�ordres et un
  pr�ordre.

\item Montrez que le produit lexicographique de deux relations
  noeth�riennes est une relation noeth�rienne.

\item Donnez des exemples de pr�ordres noeth�riens.
\end{enumerate}

\subsection*{Exercice 4: fonctions convexes}



La r�gle d'induction g�n�ralis�\footnote{Donn�e ici � titre culturel.}
$\mathit{Ind_G}$ est la suivante:
\[\mathit{Ind_G}: (\forall P)\ (\{(\forall n)[(\forall m) m < n
\Rightarrow P(m)] \Rightarrow P(n)\} \Rightarrow (\forall k) P(k))\]
Elle d�pend d'une relation d'ordre bien fond� et est quantifi�e
universellement sur les pr�dicats.  Elle permet de prouver qu'une
propri�t� $P$ est satisfaite sur un ensemble muni d'une relation
d'ordre bien fond� $>$.


\paragraph{}

Une fonction $f : \R \rightarrow  \R$ est convexe si 
\[(\forall x_1\in\R)(\forall x_2\in\R)\ \  f\left(\frac{x_1+x_2}{2}\right) \le
\frac{f(x_1)+f(x_2)}{2}.\] 
\begin{enumerate}
\item Montrez que pour tout $n\in\N^+$ et  $x_1\in\R,..., x_n\in\R$,
\[f\left(\frac{x_1+....+x_n}{n}\right) \le
\frac{f(x_1)+...+f(x_n)}{n}.\] \textsf{Indication:} L'induction qu'on
peut utiliser est une induction qui ne parcourt pas les entiers
lin�airement, mais comme � la procession
d'Echternach\footnote{http://www.cathol.lu/dansante.html}.

\item �noncez la r�gle d'induction utilis�e.

\item Prouvez la l'�quivalence de cette r�gle d'induction avec la
  r�gle
\[\mathit{Ind_C}: (\forall P)\ ([P(0) \vee (\forall n) P(n)
\Rightarrow P(n+1)] \Rightarrow (\forall k) P(k)).\]

\end{enumerate}

\end{document}
% LocalWords:  infix�e pr�ordre pr�ordres multi-ensemble multi-ensembles ssi
