Axiome d'anti-fondation

Un article de Wikipédia, l'encyclopédie libre.

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 non une alternative à la théorie des ensembles usuelle (ZF) mais une extention à l'ontologie ensembliste (la classe de tous les ensembles).

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.

Sommaire 1 Contexte, retour sur l'axiome de fondation 2 Enoncé de l'axiome 3 Exemples 4 Aspect historique 5 Bibliographie

[modifier] Contexte, retour sur l'axiome de fondation

Tous les axiomes de ZF ont pour fonction de dire (sauf l'axiome d'extentionalité qui donne un critère d'égalité entre ensembles) :

1. Ceci est un ensemble, ou

2. Si ceci est un ensemble et si telles choses, tel autre truc est un ensemble.

À ce stade on sait que tel objet est forcément un ensemble mais pas que tel autre objet ne l'est pas.

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 (une formulation plus explicite de cela peut être donnée par l'introduction de l'axiome de constructibilité).

Or l'axiome de fondation est indépendant des autres axiomes de ZF (comme tout axiome qui se respecte d'une théorie). Via la suppression de cet axiome et l'adjonction de sa négation donne une théorie équiconsistante à ZF; donc cohèrente si cette théorie l'est (ce qu'on ne peut prouver voir le second Théorème d'incomplétude).

Ainsi la limitation de l'ontologie ensembliste que propose l'axiome de fondation peut être modifiée. Ce que fait en élargissement l'axiome d'anti-fondation, qui sans être une simple négation de l'axiome de fondation, propose une autre borne, mais plus large à ce qui est considéré comme un ensemble.

[modifier] 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 dit, 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és (tagged) par l'ensemble vide ou un ur-element (= une constante d'individu adjointe au langage de la théorie des ensembles usuelles)

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, on a que 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é).

[modifier] Exemples

L'ensemble, que l'on peut prouver unique, égal à 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.

[modifier] 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. En quoi un point pointant vers lui-même peut-il être contradictoire? 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.

[modifier] 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 Etchemendy, The Liar, ed. Oxford.