- Axiome d'anti-fondation
-
L'axiome d'anti-fondation 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.
Découvert par Marco Forti et Furio Honsell en 1983, il est devenu célèbre grâce à l'ouvrage Non-Well-Founded Sets de Peter Aczel (de), publié en 1988.
C'est un axiome qui propose une extension de l'ontologie ensembliste.
Ainsi dans la théorie constituée de ZF - l'axiome de fondation + l'axiome d'antifondation, tous les ensembles de ZF sont préservés et les ensembles « ajoutés » sont appelés ensembles non-bien fondés ou hyper-ensembles.
Sommaire
Contexte, retour sur l'axiome de fondation
Les axiomes de ZF - excepté l'extensionnalité et la fondation - donnent des procédés de construction des ensembles.
Le rôle de l'axiome de fondation est de limiter l'ontologie ensembliste en disant en gros que tout ce qui n'est pas obtenu à partir de l'ensemble vide et par itération des règles d'engendrement d'ensembles que précisent les autres axiomes n'est pas un ensemble[1]. Une formulation plus explicite de cela peut être donnée par l'introduction de l'axiome de constructibilité.
Or il est démontré que l'axiome de fondation est indépendant des autres axiomes de ZF. La suppression de cet axiome avec adjonction de sa négation donne une théorie cohérente si ZF l'est[2].
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.
Énoncé de l'axiome
L'axiome d'anti-fondation (AFA)[3] s'énonce :
- Tout graphe a une et une seule décoration.
Un graphe est un ensemble de couples (paires ordonnées). Une décoration d du graphe G est une fonction telle que d(a)= {d(b) | bR a}.
Intuitivement, AFA affirme qu'une relation binaire (ensemble de couples) peut être vue comme une relation d'appartenance ("b descendant direct de a" est interprété comme "b appartient à a"). 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é).
Exemples
L'ensemble, que l'on peut prouver unique, égal au singleton de lui même et noté Ω, correspond au graphe n'ayant qu'un point et où la flèche qui part de lui pointe vers lui. Cela correspond à la simple représentation d'une relation réflexive sur un domaine à un élément.
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.
Aspect historique
Il est courant de penser en mathématiques qu'un ensemble ne peut appartenir à lui même sous peine de tomber sur le paradoxe de Russell; cela est dû à une mécompréhension de ce paradoxe. L'axiome AFA montre seulement sur ce sujet que ce n'est pas en contradiction avec les autres axiomes qui régissent l'utilisation de la relation d'appartenance dans ZF- axiome de fondation
Notes et références
- ur-element. Ce qui ne signifie pas que l'axiome de fondation interdit l'existence de tels objets - voir l'article
- théorème d'incomplétude de Gödel. La cohérence de ZF ne peut être prouvée à l'intérieur de ZF, voir l'article
- Nommé X1 par Forti-Honsell.
Bibliographie
- 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
- Peter Aczel, Non-Well-Founded Sets (pdf), CSLI Lecture Notes, Vol.14, CSLI Publications, Stanford, California, 1988.
- Keith Devlin, The Joy of Sets, Fundamentals of Contemporary Set Theory, Second Edition, Chapitre 7 (de la 2e édition), Springer-Verlag, Juin 1992.
- 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.
Lien externe
Catégories :- Axiome de la théorie des ensembles
- Concept en théorie des graphes
Wikimedia Foundation. 2010.