une version de plus

[hdrcouchot.git] / annexesccg.tex

diff --git a/annexesccg.tex b/annexesccg.tex
index 3db4320a045f548e37f9320592b1c12b14e8b7b6..d6843dcd3f4429fbe33c07e59bd41bad2cd9d87e 100644 (file)
--- a/annexesccg.tex
+++ b/annexesccg.tex
@@ -1,13 +1,13 @@
 Soit $\alpha\in\Bool$. 
 Soit $\alpha\in\Bool$. 

-On nomme $f^{\alpha}$ la fonction de $\Bool^{n-1}$ 
+On nomme $f^{\alpha}$ la fonction de $\Bool^{{\mathsf{N}}-1}$ 

 dans lui-même définie pour 
 dans lui-même définie pour 

-chaque $x\in\Bool^{n-1}$ par 
+chaque $x\in\Bool^{{\mathsf{N}}-1}$ par 

 \[
 \[

-f^{\alpha}(x)=(f_1(x,\alpha),\dots,f_{n-1}(x,\alpha)).
+f^{\alpha}(x)=(f_1(x,\alpha),\dots,f_{{\mathsf{N}}-1}(x,\alpha)).

 \]
 \]

-On nomme $\Gamma(f)^\alpha$ le sous-graphe
-de $\Gamma(f)$ engendré par le sous-ensemble
-$\Bool^{n-1} \times \{\alpha\}$ de $\Bool^n$.
+On nomme $\textsc{giu}(f)^\alpha$ le sous-graphe
+de $\textsc{giu}(f)$ engendré par le sous-ensemble
+$\Bool^{{\mathsf{N}}-1} \times \{\alpha\}$ de $\Bool^{\mathsf{N}}$.

 
 
 
 
 
 


@@ -16,111 +16,113 @@ $\Bool^{n-1} \times \{\alpha\}$ de $\Bool^n$.
 
 \begin{lemma}\label{lemma:subgraph}
 $G(f^\alpha)$ est un sous-graphe de $G(f)$: chaque arc de $G(f^\alpha)$ est
 
 \begin{lemma}\label{lemma:subgraph}
 $G(f^\alpha)$ est un sous-graphe de $G(f)$: chaque arc de $G(f^\alpha)$ est

-un arc de $G(f)$. De plus si $G(f)$ n'a pas d'arc de $n$ vers un autre 
-sommet $i\neq n$, alors on déduit
-$G(f^\alpha)$ de $G(f)$ en supprimant le sommet $n$ ainsi que tous les 
-arcs dont $n$ est soit l'extrémité, soit l'origine (et dans ce dernier  
-cas, les arcs sont des boucles sur $n$).
+un arc de $G(f)$. De plus si $G(f)$ n'a pas d'arc de ${\mathsf{N}}$ vers un autre 
+sommet $i\neq {\mathsf{N}}$, alors on déduit
+$G(f^\alpha)$ de $G(f)$ en supprimant le sommet ${\mathsf{N}}$ ainsi que tous les 
+arcs dont ${\mathsf{N}}$ est soit l'extrémité, soit l'origine (et dans ce dernier  
+cas, les arcs sont des boucles sur ${\mathsf{N}}$).

 \end{lemma}
 
 \end{lemma}
 

-\begin{Proof}
+\begin{proof}

 Supposons que $G(f^{\alpha})$ possède un arc de  $j$ vers $i$ de signe 
 Supposons que $G(f^{\alpha})$ possède un arc de  $j$ vers $i$ de signe 

-$s$. Par définition, il existe un sommet $x\in\Bool^{n-1}$ tel que
+$s$. Par définition, il existe un sommet $x\in\Bool^{{\mathsf{N}}-1}$ tel que

 $f^{\alpha}_{ij}(x)=s$, et puisque 
 $f^{\alpha}_{ij}(x)=f_{ij}(x,\alpha)$, on en déduit que $G(f)$ possède un arc
 de $j$ à $i$ de signe $s$. Ceci prouve la première assertion. 
 Pour démontrer la seconde, il suffit de  prouver que si
 $f^{\alpha}_{ij}(x)=s$, et puisque 
 $f^{\alpha}_{ij}(x)=f_{ij}(x,\alpha)$, on en déduit que $G(f)$ possède un arc
 de $j$ à $i$ de signe $s$. Ceci prouve la première assertion. 
 Pour démontrer la seconde, il suffit de  prouver que si

-$G(f)$ a un arc de $j$ vers $i$ de signe $s$, avec $i,j\neq n$, alors
+$G(f)$ a un arc de $j$ vers $i$ de signe $s$, avec $i,j\neq {\mathsf{N}}$, alors

 $G(f^\alpha)$ contient aussi cet arc. Ainsi, supposons que $G(f)$ a un 
 $G(f^\alpha)$ contient aussi cet arc. Ainsi, supposons que $G(f)$ a un 

-arc de $j$ vers $i$ de signe $s$, avec $i,j\neq n$.
+arc de $j$ vers $i$ de signe $s$, avec $i,j\neq {\mathsf{N}}$.

 Alors, il existe
 Alors, il existe

-$x\in\Bool^{n-1}$ et $\beta\in\Bool$ tels que
+$x\in\Bool^{{\mathsf{N}}-1}$ et $\beta\in\Bool$ tels que

 $f_{ij}(x,\beta)=s$. Si $f_{ij}(x,\beta)\neq f_{ij}(x,\alpha)$, alors
 $f_{ij}(x,\beta)=s$. Si $f_{ij}(x,\beta)\neq f_{ij}(x,\alpha)$, alors

-$f_i$ dépend du  $n^{\textrm{ème}}$ composant, ce qui est en contradiction 
+$f_i$ dépend du  ${\mathsf{N}}^{\textrm{ème}}$ composant, ce qui est en contradiction 

 avec les hypothèses.
 Ainsi $f_{ij}(x,\alpha)$ est égal à $s$.
 On a donc aussi
 $f^{\alpha}_{ij}(x)=s$. Ainsi $G(f^\alpha)$ possède un arc 
 arc de $j$ vers $i$ de signe $s$.
 avec les hypothèses.
 Ainsi $f_{ij}(x,\alpha)$ est égal à $s$.
 On a donc aussi
 $f^{\alpha}_{ij}(x)=s$. Ainsi $G(f^\alpha)$ possède un arc 
 arc de $j$ vers $i$ de signe $s$.

-\end{Proof}
+\end{proof}

 
 \begin{lemma}\label{lemma:iso}
 
 \begin{lemma}\label{lemma:iso}

-Les graphes $\Gamma(f^\alpha)$ et $\Gamma(f)^\alpha$ sont isomorphes.
+Les graphes $\textsc{giu}(f^\alpha)$ et $\textsc{giu}(f)^\alpha$ sont isomorphes.

 \end{lemma}
 
 \end{lemma}
 

-\begin{Proof}
-Soit $h$ la bijection de $\Bool^{n-1}$ vers
-$\Bool^{n-1}\times \{\alpha\}$ définie par $h(x)=(x,\alpha)$ pour chaque
-$x\in\Bool^{n-1}$.
+\begin{proof}
+Soit $h$ la bijection de $\Bool^{{\mathsf{N}}-1}$ vers
+$\Bool^{{\mathsf{N}}-1}\times \{\alpha\}$ définie par $h(x)=(x,\alpha)$ pour chaque
+$x\in\Bool^{{\mathsf{N}}-1}$.

 On voit facilement que $h$ permet de définir un isomorphisme
 On voit facilement que $h$ permet de définir un isomorphisme

-entre $\Gamma(f^\alpha)$ et $\Gamma(f)^\alpha$: 
-$\Gamma(f^\alpha)$ possède un arc de $x$ vers $y$ si et seulement si 
-$\Gamma(f)^\alpha$ a un  arc de $h(x)$ vers $h(y)$.
-\end{Proof}
+entre $\textsc{giu}(f^\alpha)$ et $\textsc{giu}(f)^\alpha$: 
+$\textsc{giu}(f^\alpha)$ possède un arc de $x$ vers $y$ si et seulement si 
+$\textsc{giu}(f)^\alpha$ a un  arc de $h(x)$ vers $h(y)$.
+\end{proof}

 
 
 
 

-\begin{Proof}
-du Théorème~\ref{th:Adrien}.
-La preuve se fait par induction sur $n$. 
-Soit $f$ une fonction de $\Bool^n$ dans lui-même et qui vérifie les hypothèses 
+On peut alors prouver le théorème:
+\thAdrien*
+
+\begin{proof}
+La preuve se fait par induction sur ${\mathsf{N}}$. 
+Soit $f$ une fonction de $\Bool^{\mathsf{N}}$ dans lui-même et qui vérifie les hypothèses 

 du théorème.
 du théorème.

-Si $n=1$ la démonstration est élémentaire:
+Si ${\mathsf{N}}=1$ la démonstration est élémentaire:

 en raison du troisième point du théorème, $G(f)$ a une boucle négative;
 en raison du troisième point du théorème, $G(f)$ a une boucle négative;

-ainsi $f(x)=\overline{x}$ et $\Gamma(f)$ est un cycle de longueur 2.
-On suppose donc que $n>1$ et que le théorème est valide pour toutes les 
-fonctions de $\Bool^{n-1}$ dans lui-même. 
+ainsi $f(x)=\overline{x}$ et $\textsc{giu}(f)$ est un cycle de longueur 2.
+On suppose donc que ${\mathsf{N}}>1$ et que le théorème est valide pour toutes les 
+fonctions de $\Bool^{{\mathsf{N}}-1}$ dans lui-même. 

 En raison du premier point du théorème, $G(f)$
 contient au moins un sommet $i$ tel qu'il n'existe pas dans $G(f)$
 d'arc de $i$ vers un autre sommet $j\neq i$.
 Sans perte de généralité, on peut considérer que 
 En raison du premier point du théorème, $G(f)$
 contient au moins un sommet $i$ tel qu'il n'existe pas dans $G(f)$
 d'arc de $i$ vers un autre sommet $j\neq i$.
 Sans perte de généralité, on peut considérer que 

-ce sommet est  $n$.
+ce sommet est  ${\mathsf{N}}$.

 Alors, d'après le lemme~\ref{lemma:subgraph}, 
 $f^0$ et $f^1$ vérifient les conditions de l'hypothèse.
 Alors, d'après le lemme~\ref{lemma:subgraph}, 
 $f^0$ et $f^1$ vérifient les conditions de l'hypothèse.

-Alors, par hypothèse d'induction $\Gamma(f^0)$ et
-$\Gamma(f^1)$ sont fortement connexes. 
+Alors, par hypothèse d'induction $\textsc{giu}(f^0)$ et
+$\textsc{giu}(f^1)$ sont fortement connexes. 

 Ainsi, d'après le lemme~\ref{lemma:iso}, 
 Ainsi, d'après le lemme~\ref{lemma:iso}, 

-$\Gamma(f)^0$ et $\Gamma(f)^1$ sont fortement 
+$\textsc{giu}(f)^0$ et $\textsc{giu}(f)^1$ sont fortement 

 connexes. 
 connexes. 

-Pour prouver que $\Gamma(f)$ est fortement connexe, il suffit 
-de prouver que $\Gamma(f)$ contient un arc $x\to y$ avec 
-$x_n=0<y_n$ et un arc $x\to y$ avec $x_n=1>y_n$. 
+Pour prouver que $\textsc{giu}(f)$ est fortement connexe, il suffit 
+de prouver que $\textsc{giu}(f)$ contient un arc $x\to y$ avec 
+$x_{\mathsf{N}}=0<y_{\mathsf{N}}$ et un arc $x\to y$ avec $x_{\mathsf{N}}=1>y_{\mathsf{N}}$. 

 En d'autres mots, il suffit de prouver que:
 \begin{equation}\tag{$*$}
 En d'autres mots, il suffit de prouver que:
 \begin{equation}\tag{$*$}

-\forall \alpha\in\Bool,~\exists x\in\Bool^n,\qquad  x_n=\alpha\neq f_n(x).
+\forall \alpha\in\Bool,~\exists x\in\Bool^{\mathsf{N}},\qquad  x_{\mathsf{N}}=\alpha\neq f_{\mathsf{N}}(x).

 \end{equation}
 
 \end{equation}
 

-On suppose tout d'abord que $n$ a une boucle 
+On suppose tout d'abord que ${\mathsf{N}}$ a une boucle 

 négative.
 Alors, d'après la définition de 
 négative.
 Alors, d'après la définition de 

-$G(f)$, il existe $x\in\Bool^n$ tel que $f_{nn}(x)<0$. 
-Ainsi si $x_n=0$, on a  $f_n(x)>f_n(\overline{x}^n)$, et donc 
-$x_n=0\neq f_n(x)$ et
-$\overline{x}^n_n=1\neq f_n(\overline{x}^n)$; 
-et si  $x_n=1$, on a 
-$f_n(x)<f_n(\overline{x}^n)$, donc $x_n=1\neq f_n(x)$ et $\overline{x}^n_n=0\neq
-f_n(\overline{x}^n)$. 
+$G(f)$, il existe $x\in\Bool^{\mathsf{N}}$ tel que $f_{{\mathsf{N}}}(x)<0$. 
+Ainsi si $x_{\mathsf{N}}=0$, on a  $f_{\mathsf{N}}(x)>f_{\mathsf{N}}(\overline{x}^{\mathsf{N}})$, et donc 
+$x_{\mathsf{N}}=0\neq f_{\mathsf{N}}(x)$ et
+$\overline{x}^{\mathsf{N}}_{\mathsf{N}}=1\neq f_{\mathsf{N}}(\overline{x}^{\mathsf{N}})$; 
+et si  $x_{\mathsf{N}}=1$, on a 
+$f_{\mathsf{N}}(x)<f_{\mathsf{N}}(\overline{x}^{\mathsf{N}})$, donc $x_{\mathsf{N}}=1\neq f_{\mathsf{N}}(x)$ et $\overline{x}^{\mathsf{N}}_{\mathsf{N}}=0\neq
+f_{\mathsf{N}}(\overline{x}^{\mathsf{N}})$. 

 Dans les deux cas, la condition ($*$) est établie.
 
 Dans les deux cas, la condition ($*$) est établie.
 

-Supposons maintenant que  $n$ n'a pas de boucle négative.
+Supposons maintenant que  ${\mathsf{N}}$ n'a pas de boucle négative.

 D'après la seconde hypothèse, 
 D'après la seconde hypothèse, 

-$n$ n'a pas de boucle, \emph{i.e.}, la valeur de $f_n(x)$
-ne dépend pas de la valeur de $x_n$. 
+${\mathsf{N}}$ n'a pas de boucle, \emph{i.e.}, la valeur de $f_{\mathsf{N}}(x)$
+ne dépend pas de la valeur de $x_{\mathsf{N}}$. 

 D'après la troisième hypothèse, 
 D'après la troisième hypothèse, 

-il existe $i\in \llbracket 1;n \rrbracket$ tel que $G(f)$ a un arc de 
-$i$ vers $n$.
-Ainsi, il existe $x \in \Bool^n$ tel que $f_{ni}(x) \neq 0$ et donc 
+il existe $i\in [{\mathsf{N}}]$ tel que $G(f)$ a un arc de 
+$i$ vers ${\mathsf{N}}$.
+Ainsi, il existe $x \in \Bool^{\mathsf{N}}$ tel que $f_{{\mathsf{N}}i}(x) \neq 0$ et donc 

 %$n$ n'est donc pas de degré zéro dans $G(f)$, \emph{i.e.} 
 %$n$ n'est donc pas de degré zéro dans $G(f)$, \emph{i.e.} 

-$f_n$ n'est pas constante.
-Ainsi, il existe $x,y\in \Bool^n$ tel que
-$f_n(x)=1$ et $f_n(y)=0$. 
-Soit  $x'=(x_1,\dots,x_{n-1},0)$ et
-$y'=(y_1,\dots,y_{n-1},1)$. 
-Puisque la valeur de $f_n(x)$
-(resp. de $f_n(y)$) ne dépend pas de la  valeur de  $x_n$ (resp. de  $y_n$),
-on a $f_n(x')=f_n(x)=1\neq x'_n$ (resp. $f_n(y')=f_n(y)=0\neq
-y'_n$). 
+$f_{\mathsf{N}}$ n'est pas constante.
+Ainsi, il existe $x,y\in \Bool^{\mathsf{N}}$ tel que
+$f_{\mathsf{N}}(x)=1$ et $f_{\mathsf{N}}(y)=0$. 
+Soit  $x'=(x_1,\dots,x_{{\mathsf{N}}-1},0)$ et
+$y'=(y_1,\dots,y_{{\mathsf{N}}-1},1)$. 
+Puisque la valeur de $f_{\mathsf{N}}(x)$
+(resp. de $f_{\mathsf{N}}(y)$) ne dépend pas de la  valeur de  $x_{\mathsf{N}}$ (resp. de  $y_{\mathsf{N}}$),
+on a $f_{\mathsf{N}}(x')=f_{\mathsf{N}}(x)=1\neq x'_{\mathsf{N}}$ (resp. $f_{\mathsf{N}}(y')=f_{\mathsf{N}}(y)=0\neq
+y'_{\mathsf{N}}$). 

 Ainsi la  condition ($*$) est établie, et le théorème est prouvé.
 Ainsi la  condition ($*$) est établie, et le théorème est prouvé.

-\end{Proof}
+\end{proof}