Anti-fondation et graphes extensionnels
Bonjour à tous,
Je travaille en ce moment sur la théorie des hyperensembles de Peter Aczel. Je joins le papier à toutes fins utiles. Je bute sur l'exercice 2.9 page 23 du document (page 43 du pdf). Jusqu'à maintenant les exercices proposés étaient assez faciles, mais celui-là me laisse pantois. Je vais essayer de résumer ce qu'il faut savoir.
Un graphe est simplement un ensemble $G$ de noeuds, couplé avec un ensemble d'arêtes $(a,b)$, qui sont des paires ordonnées de noeuds. Si $(a,b)$ est une arête on écrira $a \to b$, et on dira que $b$ est un enfant de $a$. On définit de même la notion de petit-enfant, d'arrière-petit-enfant etc, et de descendant. On note $a_G$ l'ensemble des enfants de $a$, et $Ga$ l'ensemble de tous les descendants de $a$ (y compris $a$ lui-même, mais c'est un détail).
Une décoration de $G$ est une application $d$ définie sur $G$, à valeurs dans $V$, telle que
$$\forall a \in G, d(a)=\{d(b) : a \to b\}.$$
L'axiome d'anti-fondation AFA dit simplement que tout graphe admet une unique décoration. Il est clairement équivalent à la conjonction de AFA$_1$ et AFA$_2$, où AFA$_1$ est "tout graphe admet au moins une décoration " et AFA$_2$ est "tout graphe admet au plus une décoration".
Un graphe $G$ est dit extensionnel si pour tous $a,b \in G$,
$$a_G=b_G \Rightarrow a=b,$$
i.e. : si deux noeuds ont les mêmes enfants, alors ils sont égaux.
L'exercice 2.9 demande de démontrer que AFA$_2 \Leftrightarrow$ AFA$_2^{ext}$, où AFA$_2^{ext}$ est l'énoncé "tout graphe extensionnel admet au plus une décoration". Clairement, seule l'implication de la droite vers la gauche demande justification. J'ouvre un autre post pour donner mon idée de départ, qui est peut-être complètement erronée.
Réponses
-
On se donne donc un graphe quelconque $G$. On commence par remarquer que si $a,b$ sont deux nœuds du graphe et si $a_G = b_G$, i.e. si $a$ et $b$ ont les mêmes enfants, alors ils ont les mêmes petits-enfants, les mêmes arrière-petits-enfants etc, et par récurrence $Ga=Gb$. On définit une relation $\sim$ sur $G$ par $$a \sim b \Leftrightarrow a_G=b_G \Leftrightarrow Ga=Gb.$$ Il est clair que $\sim$ est une relation d'équivalence sur $G$. On considère alors le graphe $\widetilde{G}$ dont les nœuds sont les classes d'équivalence pour $\sim$, i.e. les éléments de $G/\sim$, et dont les arêtes sont définies par $$Cl(a) \to Cl(b) \Leftrightarrow Cl(a) \neq Cl(b) \land (\exists x \in Ma,\ \exists y \in Mb,\ x \to y).$$La remarque ci-dessus montre que cette définition est correcte, au sens où elle ne dépend pas des représentants choisis dans $Cl(a)$ et $Cl(b)$. Mon idée est de démontrer que le graphe $\widetilde{G}$ est extensionnel et de lui appliquer AFA$_2^{ext}$, puis d'essayer de "remonter" à $G$, mais je coince à ces deux niveaux.Merci d'avance pour votre aide
Martial
-
Bonjour,
Les graphes considérés ont-ils un nombre fini de sommets ? Par ailleurs, je crois qu'il faut considérer plutôt la relation d'équivalence suivante: soit $g(a)$ les fils de $a$, pour tout sommet $a$, alors $a$ est en relation $R$ avec $b$ ssi il existe $n \in \N$ tel que $g^n(a)=g^n(b)$.
Sinon, on ne peut montrer l'extensionalité, comme le montre le graphe suivant $1 \to 2 \to 3$ et $4 \to 5 \to 3$. On a $2 \sim 5$ mais pas $1 \sim 4$, alors qu'on a bien $2 R 5$ et $1 R 4$. -
Avec la relation $R$, on montre la transitivité: si $xRy$ et $yRz$, alors il existe $n$ tel que $g^n(x)=g^n(y)$ et $k$ tel que $g^k(y)=g^k(z)$. Donc pour $m=\max(n,k)$, on a $g^m(x)=g^m(z)$, donc $xRz$.
On définit $\overline{x}\to \overline{y}$ par: il existe $n$ tel que $g^n(y) \subset g^{n+1}(x)$. Alors $x\to y \implies \overline{x} \to \overline{y}$.
Et si $xRa, yRb$, alors $\overline{x} \to \overline{y} \iff \overline{a} \to \overline{b}$.
Pour montrer que le graphe quotient est extensionnel: si le nombre de sommets est fini, alors tout sommet $x$ a un nombre fini de fils $z_1, \dots, z_k$. On prend le maximum. Je le rédigerai plus tard. -
[Edit:correction de l'erreur, merci @Martial]Pardon, je me suis trompé. Il faut considérer la relation $xRy$ ssi il existe $n$ tel que $g^n(x)=g^n(y)$ mais en posant $g^0(x)=x$ et si les fils de $x$ sont $\{z_1, \dots, z_k\}$, $g^{m+1}(x)=\{g^m(z_1), \dots, g^m(z_k)\}$.Et $\overline{x} \to \overline{y}$ ssi il existe $n$ tel que $g^n(y) \in g^{n+1}(x)$.Sinon, cela quotiente trop.
-
Merci @marco pour tes réponses. J'ai compris, sauf les deux dernières lignes. A priori les graphes sont quelconques, donc il n'y a aucune raison pour que le nombre de noeuds soit fini, ni même pour que chaque noeud n'ait qu'un nombre fini de fils. Cependant on a droit à l'axiome du choix, je ne sais pas si cela peut aider.
-
La transitivité de $R$ se montre de la même façon que dans le message avec l'erreur.Montrons que le graphe quotient est extensionnel si le nombre de sommets est fini. Je note $Cl(x)$ la classe de $x$ dans le graphe quotienté par la relation $R$.Soit $x$ et $y$ des sommets du graphe $G$, tels que pour tout $z$, $Cl(x) \to Cl(z) \implies Cl(y) \to Cl(z)$. On va montrer qu'il existe $n$ tel que $g^n(x) \subset g^n(y)$.Soit $Cl(z_1), \dots, Cl(z_k)$ les fils de $Cl(x)$. et $(n_i)$ tels que $g^{n_i}(z_i) \in g^{n_i+1}(x)$, et $(m_i)$ tels que $g^{m_i}(z_i) \in g^{m_i+1}(y)$.Soit $t$ le maximum des $(n_i)$ et des $(m_i)$.Alors on a de même $g^t(z_i) \in g^{t+1}(x)$, et $g^t(z_i) \in g^{t+1}(y)$Et donc $g^{t+1}(x)=\{g^t(z_1), \dots, g^t(z_k)\} \subset g^{t+1}(y)$.Donc si $Cl(x) \to Cl(z) \iff Cl(y) \to Cl(z)$ pour tout $z$, alors on a qu'il existe $t,u$ tels que $g^{t+1}(x) \subset g^{t+1}(y)$ et $g^{u+1}(y) \subset g^{u+1}(x)$, donc il existe $v=\max(t+1,u+1)$ tel que $g^v(x)=g^v(y)$, donc $Cl(x)=Cl(y)$.
-
Je viens de voir tes deux derniers messages. Mais il y a quelque chose qui ne va pas dans ta deuxième définition de $g^m$. Tu dis : "si $x = \{z_1,...,z_k\}$, alors $g^{m+1}(x)= \{g^m(z_1),...,g^m(z_k)\}$". Mais si on fait $m=0$ on obtient $g(x)=\{z_1,...,z_k\}$, donc $g(x)=x$ et on n'avance pas.
Je pense qu'il faut plutôt dire : "$g^0(x)=x$, $g(x)$ est l'ensemble des fils de $x$, et, si les fils de $x$ sont $z_1,...,z_k$, alors $g^{m+1}(x)=g^m(z_1) \cup ... \cup g^m(z_k)$". (Par exemple les arrière-petits-fils de $x$ sont les petits fils des fils de $x$).
-
[Edit: correction erreur de démonstration]Si le nombre de sommets est fini, on a donc que le graphe quotient est extensionnel.Soit $d$ une décoration de $G$ le graphe d'origine. Alors on va montrer que $Cl(x)=Cl(y)$ implique que $d(x)=d(y)$.On le fait par récurrence, $(*)$ soit $x$ et $y$ tels que $g^{n+1}(x)=g^{n+1}(y)$. On suppose que, pour tout $a,b$ sommets de $G$, $g^n(a)=g^n(b) \implies d(a)=d(b)$. Alors $g^{n+1}(x)=\{g^n(x_1), \dots, g^n (x_k)\}$ (ensemble de cardinal $k$) où $\{x_1, \dots, x_k\}$ sont des fils de $x$, et tel que si $z$ est fils de $x$, alors il existe $i$ tel que $g^n(z)=g^n(x_i)$.De même, $g^{n+1}(y)=\{g^n(y_1), \dots, g^n(y_{k'})\}$ avec $k=k'$ par hypothèse $(*)$.Donc il existe $f$ une permutation de $\{1, \dots, k\}$ telle que $g^n(x_i)=g^n(y_{f(i)})$, donc $d(x_i)=d(y_{f(i)})$ par hypothèse de récurrence.Donc d'après la définition d'une décoration $d(x)=d(y)=\{d(x_1), \dots, d(x_k)\}=\{d(y_1), \dots, d(y_k)\}$.Donc si $d$ et $e$ sont deux décorations distinctes sur $G$, alors il existe $x$ tel que $d(x) \neq e(x)$.Soit $d'$ et $e'$ les décorations associées sur le graphe quotient définies par $d'(Cl(z))=d(z)$ et $e'(Cl(z))=e(z)$.Il faudrait montrer que $d'$ et $e'$ sont des décorations.On a donc $d'(Cl(x))=e'(Cl(x))$ car il y a au plus une décoration sur un graphe extensionnel, donc $d(x)=e(x)$ contradiction.
-
Merci @marco pour cette belle démonstration. J'avoue que j'ai parfois un peu de mal à te suivre, mais avec un effort je devrais y arriver. Il reste donc deux problèmes :$1)$ Montrer que $d'$ et $e'$ sont des décorations du graphe quotient.$2)$ Que faire si par malheur $G$ n'est pas localement fini ?
-
Montrons que $d'$ est une décoration du graphe quotient.Soit $d$ une décoration, on note $d_S^{n+1}(\{a_1, \dots, a_k\})=\{d_S^n(a_1), \dots, d_S^n(a_k)\}$ où $a_1, \dots, a_k$ sont des ensembles. Et $d_S^0(x)=d(x)$ si $x$ est un sommet du graphe, $\emptyset$ sinon.Alors si les fils de $x$ sont $\{a_1,\dots, a_k\}$, $d(x)=\{d(a_1),\dots, d(a_k)\}$ par définition d'une décoration.Donc $d(x)=d_S^1(g(x))$.De même, supposons $d(x)=d_S^n(g^n(x))$ pour tout $x$ sommet. Alors $d(x)=\{d(a_1), \dots, d(a_k)\}$ si les fils de $x$ sont $\{a_1,\dots, a_k\}$.Donc $d(x)=\{d_S^n(g^n(a_1)), \dots, d_S^n(g^n(a_k))\}=d_S^{n+1}(\{g^n(a_1), \dots, g^n(a_k)\})=d_S^{n+1}(g^{n+1}(x))$.Donc, $d(x)=d_S^n(g^n(x))$ pour tout $x$ sommet est vrai pour tout $n$ par récurrence.Soit $Cl(x)$ un sommet du graphe quotient, soit $Cl(x_1),\dots, Cl(x_k)$ ses fils. Il existe $n$ tel que $g^{n+1}(x)=\{g^n(x_1), \dots, g^n(x_k)\}$.Soit $z_1, \dots, z_p$ les fils de $x$ dans le graphe $G$.$d'(Cl(x))=d(x)=\{d(z_1), \dots, d(z_p)\}=\{d_S^n(g^n(z_1)), \dots, d_S^n(g^n(z_p))\}=d_S^{n+1}(\{g^n(z_1),\dots, g^n(z_p)\})=d_S^{n+1}(g^{n+1}(x))=d_S^{n+1}(\{g^n(x_1), \dots, g^n(x_k)\})=\{d_S^n(g^n(x_1)), \dots, d_S^n(g^n(x_k))\}=\{d(x_1), \dots, d(x_k)\}=\{d'(Cl(x_1)), \dots, d'(Cl(x_k))\}$.Donc $d'$ est une décoration.
-
Soit $x$ un sommet d'un graphe orienté, on considère le sous-graphe constitué de $x$ et de des descendants (enfants, petits-enfants, etc...). On le note $Gx$.
Si on considère des graphes infinis, peut-être faut-il quotienter le graphe par la relation d'équivalence suivante: si $x$ et $y$ sont deux sommets du graphe, on dit que $x \sim y$ si il existe un isomorphisme de $Gx$ sur $Gy$ qui envoie $x$ sur $y$.
A vérifier.
-
Il me semble que c'est alors simple de montrer l'extensionnalité du graphe quotient.
Par contre, il faut montrer qu'une décoration $d$ du graphe d'origine passe au quotient.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 69 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 31
+25 Invités