Axiome D'anti-fondation

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 exemples à un ensemble d'appartenir à lui même ou à deux ensembles distincts d'appartenir l'un à l'autre.

Il fut présenté par Peter Aczel dans un article nommé Non-Well-Founded Sets 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.

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 a 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.

Enoncé de l'axiome

L'énoncé de l'axiome, contrairement à tous les autres de ZF qui s'expriment par des formules ou schéma de formules, passe par les définitions liminaires de directed graphs, pointed graphs, tagging of graph, et decoration of graph. [A FAIRE]

L'axiome devient alors :

• Axiome d'anti-fondation (AFA) : Every tagged graph has a unique decoration.

Informellement, il consiste grosso-modo à dire :

1. Considérons le graphe d'une relation binaire

2. Ayant une racine de laquelle tout autre point descend par transitivité (donc graphe connexe)

3. Et tel que tout point sans descendant soit nommé (tagged) par l'ensemble vide ou un ur-element (= une constante d'individu adjointe au langage de la théorie des ensembles usuelle)

Alors (AFA) : si on voit cette relation binaire comme la relation d'appartenance ("A descendant direct de B" interprété comme "A appartient à B"), c'est la représentation d'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

1. ↑ Ce qui ne signifie pas que l'axiome de fondation interdit l'existence de tels objets - voir l'article ur-element.
2. ↑ La cohérence de ZF ne peut être prouvée à l'intérieur de ZF, voir l'article théorème d'incomplétude de Gödel.

Bibliographie

• Peter Aczel, Non-Well-Founded Sets, 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 2^e é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

• nonwellfounded-set-theory article de la Standford Encyclopedia of Philosophy

Ce document provient de « Axiome d%27anti-fondation ».