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 est défini.

Cet axiome peut paraître évident pour la notion intuitive d'ensemble (intuition qui repose essentiellement sur celle d'ensemble fini), 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é à 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 Présentation de l’axiome 2 Les diverses notions d’égalité 2.1 Égalité par les éléments 2.2 Égalité par inclusion réciproque 2.3 Égalité par les propriétés 2.4 Égalité par les classes 2.5 Égalité par définition indirecte 3 Axiome d’extensionnalité et égalité 4 Conséquences de cet axiome 5 Variantes de l’axiome d’extensionnalité 5.1 Dans une théorie des ensembles avec des ur-éléments 6 Voir aussi

[modifier] Présentation de 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. Dans ce cas, l'axiome d'extensionnalité s'énonce ainsi :

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

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

Néanmoins, il est également possible d'introduire autrement l'égalité, par exemple de la définir à partir de l'appartenance. C’est pourquoi nous allons examiner de plus près les différentes notions d’égalité.

[modifier] Les diverses notions d’égalité

Les différentes théories des ensembles ne définissent pas toujours de la même manière la notion d’égalité de deux ensembles. Nous récapitulons ici les définitions rencontrées :

[modifier] Égalité par les éléments

C’est l’égalité telle qu’elle est définie dans la théorie naïve des ensembles par Cantor ; elle sera notée ici « =_e ». Elle se définit formellement par :

Deux ensembles sont égaux par les éléments si et seulement s’ils ont les mêmes éléments.

[modifier] Égalité par inclusion réciproque

C’est une variante de la définition précédente; elle sera notée ici «  ». Elle fait appel à la notion d’inclusion, dont la définition (il n’y en a qu’une, heureusement) est :

Un ensemble E est inclus dans un ensemble F si et seulement si tout élément de E appartient à F.

L’égalité par inclusion réciproque se définit alors formellement par :

Deux ensembles sont égaux par inclusion réciproque si et seulement s’ils ont inclus l’un dans l’autre.

Ces deux premières définitions de l’égalité sont évidemment équivalentes; il suffit de remplacer l’inclusion par sa définition et de se rappeler que :

[modifier] Égalité par les propriétés

C'est l'égalité définie par Leibniz sous le nom d’identité logique, et notée autrefois « ≡ » car considérée comme plus « forte » que l’égalité au sens de Cantor pour une raison que nous verrons un peu plus loin; elle sera notée ici « =_P ». Elle se définit formellement par :

Deux ensembles sont égaux par les propriétés si et seulement s’ils vérifient les mêmes propriétés.

En fait, on se retrouve dans ce cas avec le même objet sous deux noms différents ( le nom d'un objet n'est pas une propriété propre à cet objet; c'est une étiquette qui lui est apposée ).

Cette définition qui parait naturelle au premier abord cache en fait une difficulté : les propriétés y sont quantifiées ( « ∀ P » ). Or, les propriétés sont des prédicats, et seule la quantification des variables, pas celle des prédicats est autorisée dans la logique habituelle ( logique des prédicats du premier ordre ).

Trois solutions sont possibles :

• recourir à une logique autorisant la quantification des prédicats, par exemple la logique des prédicats du second ordre; ce n'est pas la solution habituellement retenue, car les logiques d'ordre supérieur au premier sont beaucoup plus complexes et recèlent des pièges autrement redoutables que ceux de la logique classique...
• trouver une définition équivalente, mais qui ne fasse pas appel à la quantification des prédicats; c'est la solution retenue par exemple dans la théorie NGB ( théorie des classes de von Neumann, Gödel et Bernays );
• renoncer à définir directement l’égalité, et l’introduire comme terme primitif de la logique sous-jacente ( logique dite avec égalité ); c’est le cas par exemple de la théorie ZF.

[modifier] Égalité par les classes

C’est l’égalité telle qu’elle est définie dans la théorie NGB ; elle sera notée ici « =_C ». Elle se définit formellement par :

Deux ensembles sont égaux par les classes si et seulement s’ils appartiennent aux mêmes classes.

La notion de classe généralise celle d’ensemble. Une classe est un ensemble si et seulement si elle est élément d’une autre classe; sinon, c’est un univers.

Cette définition est équivalente à celle par les propriétés :

- comme à toute propriété peut être associée une classe, celle des ensembles qui vérifient cette propriété, l’égalité par les classes implique celle par les propriétés;

- inversement, comme toute classe a une propriété caractéristique, l’égalité par les propriétés implique celle par les classes.

Mais elle ne comporte pas de quantification de prédicat. À la place, ce sont les variables de classe qui sont quantifiées, ce qui est licite dans le cadre d’une logique du premier ordre.

[modifier] Égalité par définition indirecte

Elle sera notée ici « =_D ». Dans la théorie ZF, l’égalité n’est pas directement définie, mais considérée comme terme primitif de la logique sous-jacente ( logique dite « avec égalité » ), qui comporte alors les axiomes nécessaires pour définir un comportement de ce terme équivalent à celui de l’égalité par les propriétés.

[modifier] Axiome d’extensionnalité et égalité

On constate que les définitions précédentes se répartissent en deux groupes à l’intérieur desquelles elles sont équivalentes entre elles :

- les deux premières définitions d’une part ( groupe I ),

- et les trois dernières d’autre part ( groupe II ).

En résumé, nous avons :

De plus, on peut montrer que l’égalité par les éléments est un cas particulier de l’égalité par les propriétés, en considérant la propriété P(E) définie comme x ∈ E. L’égalité par les propriétés implique donc l’égalité par les éléments. C’est en ce sens que, comme indiqué plus haut, l’égalité par les propriétés est plus forte que l’égalité par les éléments. Nous en déduisons le schéma suivant d’implication du groupe II vers le groupe I :

Pour obtenir l’équivalence de toutes ces définitions, il ne reste donc plus qu’à démontrer l’implication inverse, du groupe I vers le groupe II. Mais cette dernière implication n’est autre que l’axiome d’extensionnalité !

Au passage, nous pouvons enfin exprimer cet axiome de façon formelle; nous représenterons ses différents énoncés possibles de manière compacte sous la forme suivante :

Il est possible de rencontrer des formulations de l’axiome où l’implication est remplacée par une équivalence, mais, sauf cas particulier, cette équivalence est superflue.

Chaque théorie choisit l’une des définitions précédentes comme définition de l’égalité, représentée par le symbole « = », et les autres définitions, du moins celles compatibles avec cette théorie, en deviennent des théorèmes.

[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-éléments

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-élément 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 :

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.

[modifier] Voir aussi

• Théorie axiomatique des ensembles
• Ensemble
• Classes