\documentclass[a4]{seminar}

\usepackage{amsmath,amssymb}
\usepackage{amsthm,amsfonts}
\usepackage{enumerate}
\usepackage[french]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}

\usepackage[all]{xy}
\usepackage[purexy]{qsymbols}

\usepackage{psfig}

\newcommand{\ul}{\ar[ul]}
\newcommand{\ur}{\ar[ur]}
\newcommand{\ulr}{\ar[ul] \ar[ur]}

\newcommand{\hasse}[1]{\xymatrix@R-1em@C-2em{#1}}
\newcommand{\reduction}{$$x ``[= y   "<==>" `A y ``<= y', x \uparrow  y'$$}

\newtheorem*{faits}{Faits}
\newtheorem*{fait}{Fait}

\begin{document}
\begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Classifying holes of arbitrary dimensions in partially
ordered cubes}
\author{Stefan Soko{\l}owski}
\date{}
\maketitle

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\tiny \tableofcontents}

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Choix}

Insister sur deux points du papier:
\begin{itemize}
\item la notion de réduction ({\sl collapse}) d'un ordre, qui
      permet d'extraire de manière générique les informations
      de branchement (prise de décision); c'est quelque chose
      d'important pour comprendre les systèmes concurrents;
\item le problème de la fonctorialité: important pour obtenir
      une belle théorie.
\end{itemize}


\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Prolongement et bifurcations}

\subsection{Idées}

\begin{itemize}
\item Modéliser par un ordre la notion de prolongement des
  calculs d'un système.
\item Capturer algébriquement l'information sur les prises de décision
  du système, vu comme une bifurcation dans l'ordre.
\item Ignorer les détails de fonctionnement: ce qui compte, c'est
  uniquement les bifurcations.
\end{itemize}

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Compatibilité}

Soit $(X,``<= )$ un ensemble ordonné (ou préordonné).
On dit que deux éléments $x$ et $y$ sont {\bf compatibles}, et l'on note 
$x \uparrow^{``<=} y$, s'ils ont un majorant commun. 

Intuition: il est possible que les calculs $x$ et $y$ se rejoignent finalement.

\hasse{ 
  D & & E & & F \\
  & B \ulr & & C \ulr\\
  & &  A \ulr
}

Les issues possibles sont $D,E,F$. En $A$, on n'a encore fait aucun
choix; en $B$, on sait déjà que que l'on n'ira pas en $F$, \ldots

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\hasse{ 
  E & & F \\
  & D \ulr \\
  & B \ar[u] & & C \\
  & & A \ulr
}

On ne veut pas distinguer $B$ et $D$: ils ont fait exactement les mêmes
choix de bifurcations.

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Préordre de réduction}

On définit le {\bf préordre de réduction}: 

\reduction

Intuition: les comportements possibles de $y$ restent compatibles avec
$x$; autrement dit, $x$ a fait moins de choix que $y$.

\begin{faits}
Le préordre de réduction est un préordre qui vérifie:
$$``<= ``[= ``<= = ``[=$$

La notion de compatibilité $\uparrow$ est la même pour $``[=$ et pour $``<=$.

Toute équivalence $``<=$-compatible est $``[=$-compatible.
\end{faits}

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Représentons graphiquement le préordre de réducation par un
trait double.

Voici les preuves de la transitivité, de l'inclusion 
$``<= ``[= ``<= \subset ``[=$, de la préservation de la compatibilité:

\begin{tabular}{lll}
\hasse{
. \\
& . \ar@{.>}[ul]_{2} \\
& & . \ar@{.>}[ul]_{1} \\
& & . \ar[u] \\
& . \ar@{.>}[uuu]^{1} \ar@{=>}[ur] \\
. \ar@{.>}[uuuuu]^{2} \ar@{=>}[ur] \\
} 
&
\hasse{
. \\
& . \ar@{.>}[ul] \\
& . \ar[u] \\
& . \ar[u] \\
. \ar@{.>}[uuuu] \ar@{=>}[ur] \\
. \ar[u] \\
}
&
\hasse{
. \\
& . \ar@{.>}[ul]_{2} \\
& . \ar@{.>}[u]^{1} \\
. \ar@{.>}[uuu]^{2} \ar@{=>}[ur] & & . \ar@{.>}[uul]_{1} \ar@{=>}[ul] \\
}
\end{tabular}


\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

On peut donner aussi une définition coinductive de cette relation:
$``[=$ est la plus grande relation vérifiant:
\begin{enumerate}
\item[i)] Si $x ``[= y$, alors $x \uparrow y$
\item[ii)] $ ``[= ``<=  \subset ``<= ``[= $
\end{enumerate}
La deuxième condition est une propriété de simulation; elle affirme
l'existence de $x'$, étant donné $x,y,y'$ comme sur le diagramme:

\xymatrix{
   x \ar@{-}[r]^{``[=} \ar@{.}[d]_{``<=} & y \ar@{-}[d]^{``<=} \\
   x' \ar@{.}[r]_{``[=} & y' \\
}

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Un cas particulier intéressant, c'est lorsque tous les éléments
ont au moins un majorant maximal. 

\begin{fait} On note $\overline{x}$ l'ensemble des majorants maximaux
  de $x$. Alors:

$$x ``[= y  "<==>" \overline{x} \supset \overline{y}$$
\end{fait}

Intuition: les éléments maximaux représentent les calculs achevés,
donc les résultats finaux avec le souvenir de tous les choix
effectués. Dire que l'on a moins de tels majorants, c'est dire
que l'on a fait plus de choix.

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Réduction}

On note $Red(X,``<= )$ l'ensemble ordonné déduit (par quotient) du
préordre $``[=$.  On l'appelle {\bf réduit} de $X$.
On note $\pi:X \rightarrow Red(X)$ la projection, qui est croissante.

On dit que $(X,``<= )$ est réduit si $``[= = ``<=$. 

\begin{fait}
Le réduit d'un ensemble ordonné est réduit.
\end{fait}

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

La réduction consiste essentiellement à confondre les éléments
qui correspondent aux mêmes choix déjà effectués.

\begin{tabular}{ccc}

\hasse{
 & A \\
 A \ur & & A \ul & B \\
 & A \ul \ur & & B \ar[u]\\
 & & C \ul \ur
}
&  $\Longrightarrow$
&
\hasse{
 A & & B\\
 & C \ul \ur
}

\end{tabular}

Les éléments de même nom sont identifiés par la réduction.

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Mais, attention, la réduction peut ajouter des relations sans
diminuer le nombre d'éléments !

\begin{tabular}{ccc}
\hasse{
 C & & D & & E \\
 & B \ul \ur \\
 & A \ar[uul] \ar[uur] \ar[uurrr]
}
&  $\Longrightarrow$
\hasse{
 C & & D & & E \\
 & B \ul \ur \\
 & A \ar[uul] \ar[uur] \ar[uurrr] \ar@{=>}[u]
}
\end{tabular}

Le problème, c'est que l'on ne peut pas mettre le doigt sur l'instant
où chaque choix est effectué; autrement dit, on n'a pas la propriété:

$$ x ``[= a  "=>"  `Ex' ``>= x. a `= x'$$

(on note $`=$ l'équivalence induite par $``[=$)

On dit que l'ordre $``<=$ est {\bf fin} s'il vérifie cette propriété.

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Il serait plus agréable d'avoir une condition qui porte uniquement
sur l'ordre $``<=$. Le résultat suivant donne une condition
suffisante:

\begin{fait} Un sup-demi treillis sous condition (c'est-à-dire:
toute paire d'élements compatibles admet une borne supérieure) est
fin. 
\end{fait}

La réciproque est fausse, comme le montre cet exemple:

\hasse{
 & E \\
C \ur & & D \ul \\
A \ar[u] \ar[urr] & & B \ar[u] \ar[ull]
}

La condition passe bien à la réduction:

\begin{fait} Le réduit d'un sup-demi treillis sous condition est un 
sup-demi treillis sous condition.
\end{fait}

Malheureusement, on verra que ce critère est trop fort pour
les applications topologiques que l'on a en tête.

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Fonctorialité de la réduction}

La réduction associe à tout ensemble ordonné un autre ensemble
ordonné. Il est naturel d'étudier les propriétés universelles
et fonctorielles de cette construction.

Tout d'abord, on se demande si les morphismes passent au quotient par
la réduction. En fait, il est facile de voir avec l'exemple problématique vu
ci-dessus que ce n'est pas le cas en général. 
Néanmoins, une condition suffisante
pour assurer cette propriété est la {\bf condition de prolongation}:

$ f(x) ``<= a "=>" `E x' ``>= x. a = f(x')$ 

En particulier, un isomorphisme d'ensemble ordonné vérifie
cette propriété.

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Un morphisme qui vérifie cette condition passe donc au quotient. Il
est donc naturel de considerer une catégorie dont les morphismes
sont les applications croissantes avec la condition de prolongation
(on les appelle pour l'instant "bonnes applications")

\begin{faits} On a alors:
\begin{itemize}
\item La projection $\pi:X \rightarrow Red(X)$ est une bonne
  application si et seulement si $X$ est finement ordonné.
\item Si $X$ est finement ordonné, les bonnes applications,
  qui passent au quotient, donnent encore des bonnes applications.
\end{itemize}
\end{faits}

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Ces résultats nous invitent naturellement à considérer les deux
catégories suivantes:
\begin{itemize} 
\item {\bf FPoset} a pour objets les ensembles ordonnés fins
et pour morphismes les bonnes fonctions;
\item {\bf RedPoset} est la sous catégorie pleine des ordres réduits.
\end{itemize}

La réduction est alors un foncteur de la première vers la seconde;
adjoint à gauche de l'insertion. Autrement dit, on a la propriété
universelle, pour tout ordre X et tout ordre réduit Y:
$$\begin{array}{ccc}
Hom(Red(X),Y) & \cong & Hom(X,Y) \\
 f & \rightarrow & f \circ \pi \\
 Red(g) & \leftarrow & g \\
\end{array}$$

On aurait pu également considérer la catégorie des sup-demi treillis
sous condition.

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Chemins}

Soit $X$ un ensemble. On interprète les éléments de  $X$ comme des
chemins. On se donne:
\begin{itemize}
\item une notion d'homotopie $\approx$ (équivalence sur $X$)
\item une notion de concaténation (opération partielle  $X \times X
  \rightarrow X$), compatible avec l'homotopie, c'est-à-dire qui vérifie:
\item $`A a,b,c.~a(bc) \approx (ab)c$
\item $`A a, `E b.~ab \approx a$
\item $`A a,b,c.~a \approx b "=>" ac \approx bc$
\end{itemize}

Alors on définit un préordre $\approx$-compatible par:
$$a ``<= b "<=>" `E x. ax \approx b$$


\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Retour à la topologie}

\subsection{Idées}

\begin{itemize}
\item {\bf Très mauvaise} idée: travailler sur les états (points)
et dire que $x ``<= y$ si on peut arriver dans l'état $y$ à partir
de l'état $x$.
\item On va définir une notion de chemin dans un espace topologique
localement ordonné, et une homotopie sur ces chemins. L'espace
modélise les états d'un système complexe avec des sous-processus
concurrents.
\item L'ensemble des chemins d'origine fixée (ou qui ne peuvent
pas être prolongé à gauche) va être muni d'un préordre avec
ce qui précède.
\item Pour lire l'information sur les branchements du système,
on va considerer le réduit de ce préordre.
\end{itemize}

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Chemins, cylindres}

Pour capturer une information sur les trous (zones interdites)
de dimension quelconque dans l'espace, il faut définir une notion
de chemin plus riche que les traces d'execution.

Soit $X$ l'espace considéré. On appelle {\bf n-cylindre} l'espace
$C^n = S^{n-1} \times [0,1]$ avec la topologie classique et 
l'ordre : $(x,s) ``<= (y,t)  "<=>" x=y \wedge s ``<= t$. On appelle
{\bf n-cylindre tracé sur $X$ (ou chemin)}
une application $x:C^n \rightarrow X$ continue et localement
croissante. Le début et la fin de $x$ sont respectivement les
applications $x_0=x(\cdot,0)$ et $x_1=x(\cdot,1)$.

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Homotopie, concaténation}

Une {\bf homotopie} de chemins est une application continue
$h: [0,1] \times C^n \rightarrow X$ telle que pour tout $t \in [0,1]$,
$h(t,\cdot)$ est un n-cylindre de mêmes extremités
que $h(0,\cdot)$. On dit que $h$ relie les chemins
$h(0,\cdot)$ et $h(1,\cdot)$.

On définit sans problème une notion naturelle de {\bf concaténation}
compatible avec l'homotopie.

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Poset des n-cylindres}

On dit qu'un chemin $x$ est maximal à gauche si le seul chemin
$y$ que l'on peut lui concaténer à gauche ($yx$) est trivial.

L'ensemble de ces chemins est muni de l'ordre associé
à ces notions d'homotopie et de concaténation. On note
$Cyl^n(X)$ cet ensemble ordonné et $\Omega_n(X)=Red(Cyl^n(X))$.

C'est clairement un invariant d'isomorphisme d'espace
topologique localement ordonné.


\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Il est facile de voir que l'ordre obtenu n'est pas forcément
un sup-demi treillis sous condition. Prenons par exemple
un cube $[0,1]^3$ duquel on retire un petit cube 
s'appuyant sur une face initiale, 
par exemple $[1/3;2/3] \times [1/3;2/3] \times [0;1/3]$.
Les deux chemins-segments $(0,0,0) \rightarrow (1/2,0,0)$
et $(0,0,0) \rightarrow (0,1/2,0)$ sont compatibles
mais n'ont pas de plus petit majorant commun.

Il est naturel de se demander si l'ordre est néanmoins fin.
Je pense que ce résultat est vrai, au moins pour des
complexes cubiques.

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$\Omega_n(X)$ n'est pas fonctoriel avec toutes les applications
continues croissantes.

\psfig{file=recolle.eps}

$F$ est une application qui recolle les deux demi-carrés.
Au départ, les deux chemins sont équivalents; l'arrivée, ce n'est 
plus le cas.

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Pour faire passer une application continue croissante $F$ au quotient,
on demande que son
image par le foncteur qui associe à un espace localement ordonné
l'ensemble de ses $n$-cylindres soit une bonne application,
c'est-à-dire:

\frame{

\begin{minipage}{9cm}
\vspace{.3cm}
si l'image du chemin $f$ peut être prolongé en $g$,
alors $f$ peut-être prolongé en un chemin d'image $g$.
\vspace{.3cm}
\end{minipage}

}

(prolongé dans le sens: prolongé modulo homotopie, donc pour l'ordre
$``<=$; dans le cas où l'application n'est pas injective, il n'est pas
clair que cela implique la même propriété avec prolongé au sens
strict; l'autre implication est vraie).

Il faut aussi demander que l'application preserve les cylindres
maximaux à gauche.


\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Calculs de $\Omega_1(X)$}

\begin{itemize}

\item $X=I^2$ : un singleton
\item $X=I^2$ privé d'un petit carré central
$$ \hasse{ 
   B & & B \\
 & A \ulr } $$
 
\end{itemize}

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{itemize}

\item "Drapeau suisse"

\psfig{file=swiss.eps}

\hasse{ 
  E & & D & & F \\
  & B \ulr & & C \ulr & & G \\
  & &  A \ulr
}
 
\end{itemize}

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{itemize}

\item Double croix
\item Limite continue
\item Avec deux trous, on peut obtenir:

\begin{tabular}{lll}
\hasse{ 
  D & & D & & D \\
& B \ulr & & C \ulr \\
& & A \ulr }
&
\hasse{ 
  C & & C \\
& B \ulr & & C \\
& & A \ulr }
&
\hasse{ 
  C & & C & & C & & C \\
& B \ulr & & & & B \ulr \\
& & & A \ar[ull] \ar[urr] }
\end{tabular}

\end{itemize}

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Cylindres de dimension 2}

\begin{itemize}
\item Le carré avec un trou
\item Le cube avec un trou
\end{itemize}

\end{slide} \begin{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Conclusion}

Notion pas très maniable; il faudrait des théorèmes
généraux (de recollement à la Van Kampen par exemple;
d'approximation discrète; de compatibilité avec limites
inductives/projectives), ou des abstractions (homologie) 
plus facilement calculables.

Van-Kampen: ce n'est pas facile; les points de décision dans un espace
dépendent des trous dans l'autre (pas de localité).

De plus, l'ensemble ordonné obtenu peut-être très gros
(exemple du drapeau suisse continu). Se restreindre aux chemins
qui arrivent à un point donné ?

\end{slide}
\end{document}