Accessibilité et induction

$\newcommand{\pred}[1]{\text{préd} \left ( #1\right )}$
Le but de ce post est de présenter un prédicat ("Acc") qui est utilisé dans les prouveurs comme COQ afin de pratiquer des formes de récurrence un peu générales, mais qui se formalise bien en théorie des ensembles.

On se place dans ZF.
Dans toute la suite, $E$ est un ensemble et $r$ une relation binaire (quelconque!) sur $E$ (i.e. une partie de $E^2$).


I) Définitions de base.

Si $x\in E$, on notera $\pred x$ l'ensemble des prédécesseurs de $x$ c'est-à-dire l'ensemble des éléments $y$ de $E$ tels que $(x,y) \in r$.

Définition 1: On dit qu'une partie $D$ de $E$ est stable par succession si pour tout $x\in E$, si $\pred x \subseteq D$ alors $x \in D$.

Par exemple $E$ est lui-même stable par succession.

On a le premier résultat évident suivant:
1°) l'intersection de toute famille de parties de $E$ stables par succession est stable par succession.

Définition 2: l'intersection de l'ensemble des parties de $E$ stables par succession se note $Acc(E,r)$ dans la suite. Ses éléments s'appellent les éléments accessibles de $(E,r)$.

Remarque 1°: $Acc(E,r)$ est donc la plus petite partie de $E$ stable par succession d'après 1°).

On a un "principe de récurrence" qui n'est rien d'autre qu'un remaniement trivial de la définition:
2°)"Soit $P$ une propriété sur $E$ telle que pour tout $y\in E$, si pour tout $z\in E$ tel que $(y,z)\in r$, on a $P(z)$ alors on a $P(y)$.
Alors tout élément accessible de $E$ satisfait $P$". C'est simplement parce que $F:=\{x\in E \mid P(x)\}$ est stable par succession.

Définition 3: On dit qu'un élément de $E$ est initial (pour $r$) si l'ensemble de ses prédécesseurs est vide.
Si $y$ est un élément initial et si $F$ est une partie de $E$ stable par succession, alors $\emptyset = \pred y \subseteq F$ et donc $y\in F$. Ainsi $y$ appartient à toutes les parties de $E$ stables par succession et par suite:
3°) Tout élément initial de $E$ est accessible.
On verra plus loin que réciproquement, si $Acc(E,r) \neq \emptyset$ alors il existe des éléments initiaux pour $r$ dans $E$.
_______________________


II) Interprétation intuitive de la notion d'élément accessible.
Cette partie est indépendante des autres; aucun de ses résultats ne sera utilisé dans la suite notamment parce qu'on définira plus tard la notion de "fonction définie par récurrence" de façon générale. Le but est de permettre au lecteur de mettre une image mentale sur l'ensemble $Acc (E,r)$ . On suppose l'axiome du choix dépendant.

4°) Un élément $a$ de $E$ est accessible si et seulement si il n'existe aucune suite infinie $(a_n)_{n\in \N}$ telle que $a_0=a$ et $(a_{n+1},a_n) \in r$.
Ainsi, $a$ est accessible précisément quand toutes les suites qui partent de $a$ et remontent $r$ finissent par s'arrêter.

Preuve: Soit $B$ l'ensemble de tous les $x$ tels qu'il n'existe aucune suite partant de $x$ et satisfaisant la condition de l'énoncé. Alors $B$ est stable par succession (évident) et donc $Acc(E,r) \subseteq B$. Réciproquement, soit $y$ non accessible. Posons $y_0:=y$. Alors il existe au moins un $y_1 \in \pred {y_0}$ non accessible (sinon, $\pred {y_0} \subseteq Acc(E,r)$ et donc $y_0 \in Acc(E,r)$), de même il existe $y_2\in \pred {y_1}$ non accessible, $y_3\in \pred {y_2}$ non accessible ... Via l'axiome du choix dépendant, on construit donc une suite $n\mapsto y_n$ telle que $y_0=y$ et $y_{n+1} \in \pred {y_n}$ i.e. $(y_{n+1},y_n) \in r$ pour tout $n\in \N$. On a donc $y\notin B$, et le résultat suit.

Par exemple les éléments de $\N$ sont tous accessibles pour la relation $R(x,y) := y = x+1$ (on y reviendra).
___________________________


III) Relations bien fondées.

5°) Les énoncés suivants sont équivalents:
(i) tous les éléments de $E$ sont accessibles
(ii) pour toute partie non vide $G$ de $E$, il existe $y\in G$ tel que $\pred {y}$ est disjoint de $G$.

Définition 4: on dira que $r$ est bien fondée si elle satisfait une des conditions équivalentes du théorème 5°)

Preuve: si (i) est satisfait alors $E=Acc(E,r)$ est la plus petite partie stable par succession de $E$ et donc la seule. Si $G$ est une partie non vide de $E$ alors $E\backslash G$ est différent de $E$ et donc non stable par succession. Il existe donc $y$ dans $E$ tel que $\pred y \subseteq E \backslash G$ et tel que $y \notin E \backslash G$, autrement dit $y \in G$ ce qui entraîne (ii).
Réciproquement si (ii) est vrai, alors aucune partie de $E$ à part $E$ ne peut être stable par succession, en effet si $H$ est une partie de $E$ différente de $E$, $E \backslash H$ est non vide donc contient $z$ tel que $\pred z \cap (E \backslash H) = \emptyset$, autrement dit $\pred z \subseteq H$. Par suite $Acc(E,r)= \bigcap_{X \in \{E\}} X = E$ ce qui conclut la preuve.

Les relations bien fondées sont le cadre où on applique fréquemment les résultats de ce fil. $\N$ et la succession usuelle, les ensembles ordonnés, les fermés dans un espace muni d'une topologie noethérienne (Topologie de Zariski), l'appartenance sous l'axiome de fondation, les idéaux d'un anneau noethérien pour la relation d'ordre opposée de l'inclusion ...
__________________________


IV) Parties stables par prédecesseurs.
Définition 5: On dira qu'une partie $X$ de $E$ est stable par prédécesseurs si pour tout $t\in X$, $\pred t$ est contenu dans $X$.
$E$ est évidemment stable par prédécesseurs.

6°) Toute réunion et toute intersection d'un ensemble de parties de $E$ stables par prédécesseurs est encore stable par prédécesseur.
A nouveau cette propriété est triviale (application directe de la définition) comme le théorème 1°.

NB: on prendra grade au fait que "stable par prédécesseurs" n'est pas équivalent à "stable par succession" pour la relation opposée.

7°) $Acc(E,r)$ est stable par prédecesseurs.
Autrement dit, pour tout $x$, $x$ est accessible si et seulement si tous les prédécesseurs de $x$ sont accessibles.
Preuve de 7°): soit $F$ l'ensemble des $x$ de $E$ tels que $\pred x \subseteq Acc(E,r)$. Soit $y\in E$ tel que $\pred y \subseteq F$. Alors pour tout $z\in \pred y$, on a $\pred z \subseteq Acc(E,r)$ et donc $z\in Acc(E,r)$ par la remarque 1° de la partie I. Par suite, $\pred y\subseteq Acc(E,r)$ et donc $y\in F$. Donc $F$ est stable par succession. Donc $Acc(E,r) \subseteq F$ ce qui entraîne le résultat.

8°) Si $Acc(E,r)$ est non vide, il existe dans $E$ des éléments initiaux pour $r$.
Ce résultat est une sorte de réciproque à 3°.
Preuve: si $y\in E$, on définit $G(y)$ comme l'intersection des parties stables par prédécesseurs et contenant $y$.
Soit $U$ l'ensemble de tous les $t\in E$ tel que $G(t)$ contient au moins un élément initial. Alors $U$ est stable par succession, en effet soit $x\in E$ est tel que $\pred x \subseteq U$. Si $\pred x=\emptyset$, alors $x$ est un élément initial de $G(x)$. Sinon, soit $y\in \pred x$. Alors comme $y\in U$, il existe $i\in G(y)$ initial. Or $G(y) \subseteq G(x)$ (si $V$ est une partie de $E$ stable par prédécesseurs et si $x\in V$ alors $y \in V$ donc $G(y) \subseteq V$ donc en prenant l'intersection de tels $V$, $G(y) \subseteq G(x)$). Donc $i\in G(x)$.
Bref $U$ étant stable par succession, il contient $Acc(E,r)$ et comme ce dernier ensemble est par hypothèse non vide, on en déduit qu'il existe $p,q\in E$ tels que $p\in G(q)$ et $p$ initial,et en particulier l'existence d'un élément initial dans $E$.
De façon imagée, si on appelle "arbre généalogique" d'un élément $x\in E$ l'ensemble $G(x)$ défini dans cette preuve, on a montré plus généralement que tout élément accessible de $E$ possède au moins un élément initial dans son arbre généalogique.

Exemples: Si $(M,\top)$ est un ensemble muni d'une loi de composition interne et $e\in M$ un élément, notons $r_{\top,e}$ la relation $\{x,y \mid x \top e = y\}$.
Lorsque $M=\N$ muni de l'addition usuelle, $0$ est initial pour $r_{+,1}$.
Lorsque $M=\Z$ ou $\Z / n \Z$, aucun élément de $M$ n'est accessible pour $r_{ +,1}$ puisqu'il n'y a aucun élément initial dans $M$.
_________________________


Dans le message qui va suivre, on va montrer comment définir des fonctions par "induction" (ou récurrence) sur l'ensemble des éléments accessibles de $E$, ce qui était en fait le but principal de ce fil.