Axiome d'extensionnalité

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

L’axiome d’extensionnalité, ou axiome d’extension, est l’un des axiomes-clés de la plupart des théories des ensembles, en particulier, des théories des ensembles de Zermelo, et de Zermelo-Fraenkel (ZF). Il énonce essentiellement qu'il est suffisant de vérifier que deux ensembles ont les mêmes éléments pour montrer que ces deux ensembles sont égaux, au sens où ils ont les mêmes propriétés, aucune propriété ne permettra de distinguer un ensemble de l'autre. Dit d'une façon plus approximative, il affirme que quelle que soit la façon dont l'on définit un ensemble, celui-ci ne dépend que de son extension, les éléments qui lui appartiennent, et pas de la façon dont il a été défini.

Cet axiome peut paraître évident pour la notion intuitive d'ensemble, mais a des conséquences importantes sur la complexité de l'égalité dans la théorie. Pour vérifier l'égalité de deux ensembles, on est amené, à cause par exemple du schéma d'axiomes de compréhension, à vérifier des équivalences entre énoncés de complexité arbitraire, ces énoncés eux-mêmes pouvant utiliser l'égalité entre ensembles (rappelons qu'il n'y a que des ensembles dans les théories des ensembles usuelles).

L’axiome est donc intimement lié à la notion d’égalité de deux ensembles. Il permet de montrer l’unicité d’ensembles caractérisés par la donnée de leurs éléments, tels l’ensemble vide, les singletons, les paires, l'ensemble des parties d'un ensemble…

Sommaire

1 L’axiome
2 Conséquences de cet axiome
3 Variantes de l’axiome d’extensionnalité
- 3.1 Dans une théorie des ensembles avec des ur-elements
4 Voir aussi

[modifier] L’axiome

L’égalité peut être introduite en théorie des ensembles, de diverses façons. Actuellement, elle est le plus souvent considérée comme une relation primitive, axiomatisée au niveau logique. La théorie des ensembles est alors une théorie énoncée dans le langage du calcul des prédicats égalitaire du premier ordre, construit sur la seule relation d'appartenance.

[modifier] Énoncé en calcul des prédicats égalitaire

Dans ce cas, l'axiome d'extensionnalité s'énonce ainsi :

∀A ∀B [ ∀x (x ∈ A ⇔ x ∈ B) ⇒ A = B ].

On sait que l'inclusion entre deux ensembles se définit par :

A ⊂ B signifie ∀ x (x ∈ A ⇒ x ∈ B).

On en déduit donc une autre formulation de l'axiome d'extensionnalité, qui est d'ailleurs celle originale de Ernst Zermelo.

(A ⊂ B et B ⊂ A) ⇒ A = B.

[modifier] Axiomes de l'égalité

Rappelons qu'en calcul des prédicats égalitaire, l'égalité satisfait l'axiome de réflexivité, un objet (un ensemble dans le cas de la théorie des ensembles) égale lui-même, en langage formel,

∀x x = x.

et le schéma d'axiomes suivant, qui affirme que si deux objets sont égaux, toute propriété vérifiée par l'un est vérifiée par l'autre, en langage formel, en tenant compte d'éventuels paramètres a₁ … a_p,

∀a₁ … ∀a_p ∀x ∀y [x = y ⇒ (P x a₁ … a_p ⇒ P y a₁ … a_p)] pour toute formule P ne contenant pas d'autre variable libre que x a₁ … a_p.

(on en déduit en particulier la symétrie et la transitivité de l'égalité).

On voit ainsi que la réciproque de l'axiome d'extensionnalité -- si deux ensembles sont égaux, alors ils ont les mêmes éléments -- est une propriété usuelle de l'égalité, un cas particulier du schéma que l'on vient d'énoncer :

∀A ∀B [ A = B ⇒ ∀x (x ∈ A ⇔ x ∈ B)].

On peut voir cette axiomatisation comme une formalisation de la définition de l'égalité par Leibniz : deux objets sont égaux quand ils ont exactement les mêmes propriétés, dit par contraposée, deux objets sont différents si une propriété permet de les distinguer. Pour formaliser directement cette définition, il faut pouvoir quantifier sur les propriétés, c'est à dire, formellement, les prédicats du langage (bien-sûr le choix du langage a des conséquences sur l'égalité, le nom, ou la définition d'un ensemble dans un langage formel, ne peut en constituer une propriété qui se définit dans ce langage). Ceci n'est pas possible en logique du premier ordre, donc en théorie des ensembles usuelle. Si l'on énonce la théorie des ensembles, par exemple ZFC, en logique du second ordre, en étendant les schémas d'axiomes aux nouvelles formules du langage, on obtient une théorie strictement plus forte, qui est équivalente à la théorie des classes de Morse-Kelley.

[modifier] Définition de l'égalité

Une alternative est de considérer la théorie des ensembles en calcul des prédicats du premier ordre sans égalité, et de définir cette dernière à partir de l'appartenance, par exemple par l'égalité extensionnelle :

x=y signifie ∀z (z ∈ x ⇔ z ∈ y)

On doit alors donner un axiome qui permet de retrouver les propriétés usuelles de l'égalité :

∀x ∀y [∀z (z ∈ x ⇔ z ∈ y) ⇒ ∀u(x ∈ u ⇒ y ∈ u)]

même s'il s'agit juste d'un cas particulier du schéma de l'égalité, on en déduit celui-ci par induction sur la structure des formules

[modifier] Conséquences de cet axiome

L'axiome d'extensionnalité permet d'assurer l'unicité d'ensembles fondamentaux, tels l'ensemble vide ou la paire de deux ensembles donnés, dont l'existence est directement affirmée par certains autres axiomes.

A cet effet, considérons un prédicat quelconque P, un de ses arguments que l'on notera x étant distingué, les autres, si l'en existe, sont notés a₁ …a_p et servent de paramètres. Il n'existe pas toujours (voir schéma d'axiomes de compréhension) un ensemble A défini comme l'ensemble des objets x qui vérifient P, c'est-à-dire tel que pour tous a₁ …a_p et pour tout x,

x ∈ A ⇔ P x a₁ …a_p.

Supposons que l'on ait démontré l'existence d'un tel ensemble A. Certains axiomes de la théorie des ensembles sont d'ailleurs directement de cette forme. Dans ce cas, cet ensemble A est l'unique ensemble des x vérifiant P : l'unicité est une conséquence immédiate de l'axiome d'extensionnalité.

Nous pouvons alors introduire un symbole particulier pour désigner cet ensemble, par exemple ∅ pour l'ensemble vide, { a } pour le singleton construit à partir de a, ou { a, b } pour la paire formée par a et b,... l'utilisation de ces nouveaux symboles ne modifie pas véritablement la théorie : les théorèmes (exprimés sans ces symboles) restent les mêmes. En fait tout énoncé contenant ces nouveaux symboles peut être remplacée par un énoncé équivalent ne les contenant pas, et ceci se montre en utilisant la propriété d'existence et d'unicité qui a permis de les introduire.

[modifier] Variantes de l’axiome d’extensionnalité

L’axiome d’extensionnalité apparaît, sous une forme ou sous une autre, dans les axiomatiques de la théorie des ensembles, tant l'égalité extensionnelle semble être constitutive de la notion d'ensemble. Il est cependant possible de s'intéresser, au moins en préalable, aux théories non extensionnelles, qui ont de meilleures propriété en théorie de la démonstration, à cause du « quotient » complexe qu'induit l'égalité extensionnelle. Par ailleurs, l'axiome peut subir des modifications pour satisfaire certaines exigences, comme dans l’exemple suivant.

[modifier] Dans une théorie des ensembles avec des ur-elements

La notion d’ur-élément, ou atome ou encore élément primitif, résulte de la formalisation de la notion d’élément de la théorie cantorienne. Cantor se souciait peu de la nature précise de ses éléments; tout ce qui lui importait, c’était qu’on puisse les mettre ensemble. Mais, avec les premiers efforts de formalisation (Zermelo), il est apparu nécessaire de distinguer les éléments qui étaient eux-mêmes des ensembles de ceux qui n’en étaient pas : un élément était donc soit un ensemble, soit un élément primitif. Un élément primitif, ou ur-element est donc un élément, c’est-à-dire un objet susceptible d’appartenir à un ensemble, mais qui n’est pas lui-même un ensemble, et qui ne comporte donc aucun élément.

Dans la théorie de Zermelo-Fraenkel actuelle, « tout est ensemble », et il n’y a plus d’ur-élément, mais les premières versions de Zermelo, inspirées par la théorie naïve, en comportaient; certaines axiomatiques alternatives de la théorie des ensembles en ont encore. Les ur-éléments peuvent être considérés comme logiquement différents des ensembles; dans le cas où A est un ur-élément, « x ∈ A » n’a aucun sens; ainsi, l’axiome d’extensionnalité ne s’applique qu’aux ensembles (sinon, comme un ur-élément n’a pas d’élément, il se confondrait avec l’ensemble vide).

Alternativement, dans une logique non typée, nous pouvons avoir besoin de donner un sens à « x ∈ A » ; cette expression est alors considérée comme fausse toutes les fois où A est un ur-élément. Dans ce cas, l’application de l’axiome habituel d’extensionnalité impliquerait, comme nous venons de le voir, que tout ur-élément se confond avec l’ensemble vide. Pour éviter cela, nous devons modifier l’axiome d’extensionnalité afin qu’il ne puisse s’appliquer qu’aux ensembles non-vides. Il s’énonce alors par exemple:

axiome d’extensionnalité restreint :

$\forall A , \forall B , [ ( \exists C /\, C \in A ) \wedge ( \forall x , ( x \in A ) \Leftrightarrow ( x \in B ) ) ] \Rightarrow [ A = B ] \,$

C'est-à-dire :

étant donnés des ensembles A et B quelconques, si A est un ensemble non vide (c'est-à-dire s'il existe au moins un élément C dans A ), et si A et B ont exactement les mêmes éléments, alors ils sont égaux.