Voir la source de Axiome d'anti-fondation

{{Voir homonymes|AFA}}

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 [[Théorie des ensembles de Zermelo-Fraenkel|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 [[Univers de von Neumann|hiérarchie cumulative de von Neumann]], construite sur l'ensemble vide par itération de l'ensemble des parties, et par réunion<ref>Il est possible d'adapter l'axiome de fondation en permettant d'autres objets primitifs — voir l'article [[ur-element]].</ref>.  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<ref>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]].</ref> 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<ref>Voir par exemple {{Krivine98}}, chap. 7.</ref> (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.

En [[ZFC|théorie des ensembles ZF]], d'après le [[lemme de contraction de Mostowski]], pour tout ensemble ''E'' muni d'une [[relation bien fondée]] ''R'' (''R'' est définie comme un ensemble de couples d'éléments de ''E''), il existe une unique fonction π définie sur ''E'' et vérifiant pour tout ''a'' de ''E''
: π(''a'') = { π(''x'') | ''x R a''}
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 [[graphe orienté|graphe]] ''G'' peut être vu comme le [[graphe d'une relation]] ''R'' (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''<ref>Peter Aczel prend la convention inverse : sa relation, qu'il note →, est la relation inverse de celle notée ici ''R''.</ref> :
: π(''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.

L'axiome d'anti-fondation (AFA)<ref>Nommé X1 par Forti-Honsell.</ref> est alors :

'''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
:<math>\Omega = \{\Omega\}</math>.
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. <!-- Pour ne pas avoir une autre représentation de Ω il suffit que l'un des 2 points pointe vers un autre point sur lequel ne pointe pas l'autre. -->

== Notes et références ==
<references/>

== Voir aussi ==
=== Articles connexes ===
* [[Axiome de fondation]]
* [[Algèbre de processus]]
*[[Théorie des ensembles non bien fondés]]

=== Bibliographie ===
*{{en}} Marco Forti et Furio Honsell, « [http://www.numdam.org/item?id=ASNSP_1983_4_10_3_493_0 Set theory with free construction principles] », ''Annali della Scuola Normale Superiore di Pisa'', Classe di Scienze {{4e|série}}, tome 10, {{n°|3}}, 1983, {{p.|493-522}}
*{{en}} Peter Aczel, [https://web.archive.org/web/20161017184455/http://standish.stanford.edu/pdf/00000056.pdf ''Non-Well-Founded Sets'' {{pdf}}], CSLI Lecture Notes, vol. 14, CSLI Publications, Stanford, California, 1988
*{{en}} Keith Devlin, ''{{Google Livres|hCv-vFu4jskC|{{Lang|en|The Joy of Sets, Fundamentals of Contemporary Set Theory}}}}'', {{2e}} éd., Springer, 1992, chap. 7
*{{en}} [[Jon Barwise]] et [[John Etchemendy]], ''The Liar'', [[Oxford University Press]], Londres, 1987{{Commentaire biblio SRL|Ouvrage présentant cet axiome et l'utilisant pour analyser le [[paradoxe du menteur]].}}

=== Lien externe ===
{{Lien web|langue=en|url=http://plato.stanford.edu/entries/nonwellfounded-set-theory/|auteur=Lawrence S. Moss|titre=Non-wellfounded set theory|site=[[Stanford Encyclopedia of Philosophy]]|année=2008}}

{{portail|mathématiques|logique|informatique théorique}}

[[Catégorie:Axiome de la théorie des ensembles]]
[[Catégorie:Concept en théorie des graphes|Anti]]
[[Catégorie:Graphe orienté]]