L’axiome d’anti-fondation (en anglais, anti-foundation axiom ou AFA) est un axiome alternatif à l'axiome de fondation de la théorie des ensembles qui permet des chaînes infinies descendantes pour la relation d'appartenance sur les ensembles. Il permet par exemple à un ensemble d'appartenir à lui-même ou à deux ensembles distincts d'appartenir l'un à l'autre.
Proposé par Marco Forti et Furio Honsell en 1983, il a été popularisé par l'ouvrage Non-Well-Founded Sets de Peter Aczel, publié en 1988.
C'est un axiome qui propose une extension de l'ontologie ensembliste. En effet dans un univers de la théorie ZF (sans axiome de fondation) il est toujours possible de définir une partie de celui-ci, l'univers de von Neumann, qui satisfait tous les axiomes de ZF et l'axiome de fondation, ce sont les ensembles bien fondés. L'axiome d'anti-fondation a pour conséquence que l'univers de von Neumann n'est pas l'univers tout entier : il existe des ensembles non-bien fondés (appelés parfois hyper-ensembles). Cette vision avait été anticipée par le mathématicien Dmitry Mirimanoff.
Axiome de fondation
Les axiomes de ZFC — excepté l'extensionnalité et la fondation — énoncent l'existence de nouveaux ensembles, à partir d'ensembles existants ; on peut considérer qu'ils donnent des procédés de « construction » de ces ensembles (excepté l'axiome du choix qui est un simple énoncé d'existence).
L'axiome de fondation limite l'ontologie ensembliste aux ensembles bien fondés, il équivaut à ce que tout ensemble appartienne à la hiérarchie cumulative de von Neumann, construite sur l'ensemble vide par itération de l'ensemble des parties, et par réunion[1]. Les ensembles des mathématiques usuelles, et plus généralement tous ceux construits à partir de l'ensemble vide en itérant les règles d'engendrement d'ensembles décrites par les autres axiomes, appartiennent à la hiérarchie de von Neumann. Tout univers qui satisfait les axiomes de la théorie ZFC sans axiome de fondation contient donc un univers, l'univers de von Neumann qui, muni de la relation d'appartenance restreinte à celui-ci, satisfait les axiomes de ZFC et l'axiome de fondation, et les ensembles usuels vivent dans cet univers. Une conséquence est d'ailleurs que si la théorie ZFC sans axiome de fondation est cohérente[2] la théorie ZFC avec axiome de fondation est cohérente.
Mais on montre également que si la théorie ZFC est cohérente, alors la théorie ZFC sans axiome de fondation, mais avec la négation de cet axiome est cohérente[3] (ces deux derniers résultats établissent l'indépendance de l'axiome de fondation vis-à-vis des autres axiomes de ZFC).
Ainsi la limitation de l'ontologie ensembliste que propose l'axiome de fondation peut être modifiée ; ce que fait l'axiome d'anti-fondation, qui sans être une simple négation de l'axiome de fondation, propose une autre borne à ce qui est considéré comme un ensemble.
par définition par récurrence sur la relation bien fondée R. Soit F l'ensemble image de E par π, alors π définit un morphisme de (E, R) sur (F, ∈) (x R y si et seulement si π(x) ∈ π(y) ), F est le collapse de Mostowski de (E, R).
Énoncé de l'axiome
L'énoncé de l'axiome d'anti-fondation est une généralisation directe de celui du lemme de Mostowski à une relation, ou graphe, quelconque, non nécessairement bien fondée.
Un grapheG peut être vu comme le graphe d'une relationR (définie par l'ensemble des couples constituant les arêtes du graphe) sur un ensemble E (l'ensemble des nœuds du graphe).
Une décoration sur un graphe G est une fonction π définie sur E telle que, pour chaque nœud a de E[4] :
π(a) = { π(x) | x R a }.
Une décoration est généralement non injective, puisque, par exemple, elle associe à tout nœud sans antécédent l'ensemble vide.
Axiome d'anti-fondation. — Tout graphe a une et une seule décoration.
En choisissant une relation R qui n'est pas bien fondée, on peut obtenir par la décoration un ensemble qui n'est pas bien fondé, comme le montrent les exemples de la section suivante, c'est-à-dire qu'AFA contredit l'axiome de fondation.
AFA affirme que chaque nœud du graphe représente ainsi un et un seul ensemble.
Réciproquement, mais c'est un théorème, tout ensemble (classique ou non bien-fondé) est représentable par un tel graphe, en général non unique (il peut y en avoir une infinité).
La décoration π définit un morphisme de (E, R) sur l'ensemble image de π muni de la relation d'appartenance, mais, comme déjà dit ci-dessus, ce morphisme peut ne pas être injectif. Deux nœuds qui ont les mêmes antécédents par R sont identifiés par π, et du fait de ces identifications, il peut y avoir d'autres cas.
Exemples
En appliquant l'axiome AFA au graphe n'ayant qu'un point et où la flèche qui part de lui pointe vers lui, on forme l'ensemble Ω qui vérifie
.
De surcroît, AFA affirme qu'un seul ensemble vérifie cette équation.
Deux ensembles a et b s'appartenant mutuellement correspondent simplement à 2 points pointant l'un vers l'autre.
Notes et références
↑Il est possible d'adapter l'axiome de fondation en permettant d'autres objets primitifs — voir l'article ur-element.
↑La cohérence de ZFC qu'elle possède un modèle, qu'il existe un univers ensembliste ; cette hypothèse est nécessaire, car elle ne peut être démontrée dans la théorie d'après le théorème d'incomplétude de Gödel.
(en) Marco Forti et Furio Honsell, « Set theory with free construction principles », Annali della Scuola Normale Superiore di Pisa, Classe di Scienze 4e série, tome 10, no 3, 1983, p. 493-522
(en) Jon Barwise et John Etchemendy, The Liar, Oxford University Press, Londres, 1987 — Ouvrage présentant cet axiome et l'utilisant pour analyser le paradoxe du menteur.
