Fondements des mathématiques 2: premiers développements

Fondements des mathématiques



2. Premiers développements
Note de vocabulaire : les mots "proposition", "théorème", "lemme", "corollaire" sont synonymes, et désignent un énoncé qu'on prouve vrai, aux nuances près qu'un théorème est plus important qu'une proposition, qu'un lemme sert à démontrer un théorème, et un corollaire en résulte. On appelle "axiome" un énoncé qu'on choisit (ou qu'on envisage) de supposer toujours vrai.

2.1. Quelques propriétés des quantificateurs
Soit E un ensemble. Sous-entendant le domaine E pour tous les quantificateurs, les propriétés suivantes utilisant suivant les cas, des relations unaires A, B sur E, et une variable propositionnelle C sont toujours vraies. Nous ne les justifierons que brièvement, laissant le lecteur compléter les explications et méthodes pour les déduire les unes des autres. (Il n'y a ici aucune notation de couple, les ponctuations articulent les quantificateurs avec leurs énoncés...).
Quelques évidences:
∀x, (vrai)
∀x, (A(x)⇒∃y, A(y))
∀x, ((∀y, A(y))⇒A(x))
Que C soit vrai ou faux, on a toujours
(∃x, C)⇒C
C⇒∀x, C
(∃x, C) ⇔ (C et ∃x, vrai)
Exemple: s'il existe une chaise telle que la Terre est ronde, alors la Terre est ronde. Puis, si la Terre est ronde, alors, quelle que soit la chaise que l'on considèrerait, la Terre serait toujours ronde. Mais la réciproque est fausse: la phrase "si la Terre est ronde, alors il existe une chaise telle que la Terre est ronde", est équivalente à "il existe une chaise, ou la Terre n'est pas ronde".
Sur l'énoncé (A(x),B(x))(y), de variables x ∈ E, y ∈ V, on peut commuter les quantificateurs de même espèce (de ∀x ∀y à ∀y∀x, et de même pour les ∃):
((∃x, A(x)) ou (∃x,B(x)) ⇔ (∃x, A(x) ou B(x))
((∀x, A(x)) et (∀x,B(x)) ⇔ (∀x, A(x) et B(x))
Autres en vrac:
(∃x, C ou A(x))⇒(C ou ∃x, A(x))
(C et ∀x, A(x))⇒(∀x, C et A(x))
(∃x, C et A(x)) ⇔ (C  et ∃x, A(x))
(∀x, C ou A(x)) ⇔ (C  ou ∀x, A(x))
(∀x, C⇒A(x)) ⇔ (C ⇒∀x, A(x))
(∀x, A(x)⇒C) ⇔ ((∃x , A(x))⇒C)
((∀x, A(x)⇒B(x)) et (∀x, A(x)))⇒(∀x, B(x))
((∀x, A(x)⇒B(x)) et (∃x, A(x)))⇒(∃x, B(x))
(∀x, A(x) ou B(x))⇒((∃x, A(x)) ou (∀x, B(x)))
((∃x, A(x)) et (∀x, B(x)))⇒∃x, (A(x) et B(x))
(∀x, A(x))⇒(∀x, (A(x) ou B(x))
(∃x, A(x))⇒(∃x, (A(x) ou B(x))
(∀x, A(x) et B(x) )⇒(∀x, A(x))
(∃x, A(x) et B(x) )⇒(∃x, A(x))
Un cas particulier de deux de ces formules donne les propriétés de distributivité entre les connecteurs (et) et (ou): pour trois variables propositionnelles A, B, C on a
((A et B) ou C) ⇔ ((A ou C) et (B ou C))
((A ou B) et C) ⇔ ((A et C) ou (B et C)).
Soient maintenant deux ensembles E et F et une relation R entre E et F. On a alors
(∃x ∈ E, ∀y ∈ F, R(x,y))⇒(∀y ∈ F,∃x ∈ E, R(x,y)).

Changements de domaine
Soient deux ensembles E et F, une application f de domaine E, et une relation unaire ou autre énoncé A de domaine contenant F ainsi que Imf. On a alors
(∃y ∈ F, y ∈ Im
f et A(y))
 ⇔ ∃y ∈ F, ∃x ∈ E, f(x)=y et A(y)
 ⇔ ∃x ∈ E, ∃y ∈ F, f(x)=y et A(f(x))
 ⇔ ∃x ∈ E, f(x) ∈ F et A(f(x))
On en tire comme cas particuliers les conséquences suivantes.

Lemme. Pour tous ensembles E ⊂ F, et toute relation unaire A sur F,
(∃x ∈ E, A(x)) ⇔ (∃x ∈ F, (x ∈ E et A(x)))
(∀x ∈ E, A(x)) ⇔ (∀x ∈ F, (x ∈ E⇒A(x)))
La première s'obtient par f=IdE, et la deuxième s'en déduit en remplaçant A par sa négation. En procédant de même avec A=vrai, ou en passant par ∃x ∈ E∪F, x ∈ E et x ∈ F, on obtient (∃x ∈ E, x ∈ F) ⇔ (∃x ∈ F, x ∈ E), d'où par négation

Définition. On dit que deux ensembles E et F sont disjoints ssi (∀x ∈ E, x ∉ F), ce qui équivaut à (∀x ∈ F, x ∉ E).
Passons à une troisième conséquence, qui peut d'ailleurs être intuitivement tirée de la définition de l'image d'une application f comme ensemble des valeurs possibles de f(x).

Lemme. Soit une application f d'un ensemble E dans un ensemble F, et soit R une relation unaire sur F. Alors
(∃x ∈ E, R(f(x)))
 ⇔ (∃y ∈ Im
f, R(y))
(∀x ∈ E, R(f(x)))
 ⇔ (∀y ∈ Im
f, R(y))
La deuxième formule est, là encore, simple reformulation de la première.
Ainsi, tout énoncé comportant une variable x apparaissant uniquement sous forme de f(x) et liée par un quantificateur de même domaine que f, est équivalente à la formule modifiée en remplaçant le domaine du quantificateur par Imf et en remplaçant f(x) par x.
De là vient le fait que souvent on peut employer de manière semblable la notion d'ensemble et celle de famille: pour une famille u indexée par I, un énoncé avec quantificateur sur i ∈ I, où i n'apparaît que par son image ui, est équivalent à l'énoncé obtenu en portant ce quantificateur sur x ∈ Imu, où ui est remplacé par x. C'est ainsi par exemple que les notions d'unions et d'intersections s'appliqueront aussi bien aux familles d'ensembles qu'aux ensembles d'ensembles.

Quantificateur d'unicité
Pour tout objet x et tout ensemble F on a
{x} ⊂ F ⇔ x ∈ F
F ⊂ {x} ⇔ (∀y ∈ F, y=x)
F={x} ⇔ ({x} ⊂ F et F ⊂ {x}) ⇔ (x ∈ F et ∀y ∈ F, y=x)
L'énoncé F ≠ ∅ que F a un élément, s'écrit (∃x ∈ F, vrai).
On notera ∃!(F) l'énoncé qu'il n'en a pas d'autre, i.e. que F un singleton:
∃!(F) ⇔ ∃x ∈ F,∀y ∈ F, x=y.
Le fait que F comporte au moins deux éléments, peut s'écrire ∃x,y ∈ F, x ≠ y.
La négation de ce dernier énoncé, affirmation qu'il a au plus un élément (il est vide ou un singleton), sera notée !(F):
!(F) ⇔ ∀x,y ∈ F, x=y
Soient un objet x, un ensemble F, et B une relation unaire ayant un sens sur F et aussi sur l'élément x. Alors:
Si x ∈ F on a
(∀y ∈ F, B(y))⇒B(x)⇒(∃y ∈ F, B(y))
Ces deux implications sont symétriques à travers le remplacement de B par nonB. De là vient
F ≠ ∅⇒((∀y ∈ F, B(y))⇒(∃y ∈ F, B(y))).
De même, si ∀y ∈ F, y=x, on a
(∃y ∈ F, B(y))⇒B(x)⇒(∀y ∈ F, B(y)).
La deuxième implication dans le cas où B(x) est l'énoncé ∀y ∈ F, y=x, donne
(∀y ∈ F, y=x)⇒ !(F)
ce qui permet de redémontrer en formules que ∃!(F) ⇔ (F ≠ ∅ et  !(F)) ("F est un singleton" équivaut à "F a un et un seul élément").
On peut voir directement, ou comme résultant de la dernière double implication (avec x ∈ F si F ≠ ∅ ou x quelconque sinon), que
!(F)⇒((∃y ∈ F, B(y))⇒(∀y ∈ F, B(y)).
Rassemblant tout cela, on a
F={x}⇒((∃y ∈ F, B(y)) ⇔ B(x) ⇔ (∀y ∈ F, B(y)))
∃!(F)⇒((∃y ∈ F, B(y)) ⇔ (∀y ∈ F, B(y))).
Soit maintenant une relation unaire A sur un ensemble E, et soit F={x ∈ E|A(x)}.
On notera "!x ∈ E, A(x)" et on dira il y a unicité de x ∈ E tel que A(x), l'énoncé que F a au plus un élément, autrement dit
! x ∈ E, A(x) ⇔  !{x ∈ E|A(x)} ⇔ ∀x,y ∈ E, ((A(x)  et A(y))⇒ x=y).
De même on notera "∃!x ∈ E, A(x)" et on lira il existe un unique x ∈ E tel que A(x), l'énoncé que F est un singleton, ce qui s'écrit
∃! x ∈ E, A(x)
 ⇔ ∃!{x ∈ E| A(x)}
 ⇔ ∃x ∈ E, (A(x)  et ∀y ∈ E, (A(y)⇒y=x))
 ⇔ ((∃x ∈ E, A(x)) et (!x ∈ E, A(x)).
Puis, soient deux relations unaires A et B sur un ensemble E, et un élément x ∈ E tels que A(x) et ∀y ∈ E, (A(y)⇒y=x). Ainsi ∀y ∈ E, A(y) ⇔ y=x. Alors on a les équivalences
(∃y ∈ E, A(y) et B(y)) ⇔ B(x) ⇔ (∀y ∈ E, A(y)⇒B(y)).
De cette manière, si ∃! x ∈ E, A(x) alors les énoncés B qu'on peut formuler sur l'unique objet x tel que A(x) peuvent également s'exprimer sans le symbole de la variable libre "x", au moyen d'une variable liée par un quantificateur, et de la relation unaire A.
Par ailleurs, en remplaçant A(y) par son expression équivalente "y=x", on retrouve (dans le cas particulier x ∈ E) deux équivalences dont on avait déjà initialement vu la première
(∃y ∈ E, y=x et B(y)) ⇔ B(x) ⇔ (∀y ∈ E, y=x⇒B(y)).

2.2. Operations sur les ensembles; l'axiome des parties

Objets canoniques
On dira qu'un objet x est canonique par rapport à des objets désignés par des symboles, disons y,z, si x est le seul objet à satisfaire une certaine formule sans autre symbole de variable libre que y et z. Cette formule constitue donc une définition de x. En pratique, la mention des symboles y,z par rapport auxquels on considère la canonicité, est sous-entendue comme étant donnée par le contexte, à savoir que ce sont les symboles apparaissant dans les termes alors utilisés.
Ceci n'est pas une notion mathématique au sens où elle ne se situe pas au même niveau de théorie que les autres notions que nous exposons autour, mais une notion métamathématique (située au-dessus du langage de ces dernières). Précisément, c'est l'évocation d'une formule de définition implicitement utilisée, et qu'on ne prend pas nécessairement la peine de réexpliciter. Il faudrait réexpliciter cette formule pour traduire cette notion en un travail mathématique proprement dit au même niveau que le reste.
Par exemple, si on considère un singleton, son élément est canonique (par rapport à lui); mais si on considère un ensemble à plus d'un élément (autrement dit ni vide ni singleton), sans préciser d'autre contexte, et en particulier le considérant comme un ensemble d'éléments purs, alors aucun de ses éléments n'est canonique.

Union et intersection d'une famille d'ensembles
Soit une famille d'ensembles (Ei)i ∈ I. Notons son ensemble image E ={Ei|i ∈ I}. Pour tout objet x on a
(∃i ∈ I,x ∈ Ei) ⇔ (∃F ∈ E, x ∈ F) ⇔ x ∈ ∪
E.
On définit alors l'union de la famille (Ei)i ∈ I, notée ∪i ∈ I Ei (notation par laquelle on peut du même coup définir cette famille en remplaçant ici Ei par le terme qui le définit), comme étant ∪E, de sorte qu'on a
x ∈
∪
i ∈ I 
 Ei ⇔ (∃i ∈ I,x ∈ Ei).
Si I ≠ ∅, on définit de même l'intersection de la famille (Ei)i ∈ I comme étant l'ensemble défini comme classe par l'énoncé de variable x:
x ∈
∩
i ∈ I 
 Ei ⇔ ∀i ∈ I, x ∈ Ei.
Ceci définit bien un ensemble pour la raison suivante: I étant non vide, soit un certain j ∈ I. Alors cet énoncé de définition (partie de droite) implique x ∈ Ej, de sorte que cette intersection peut se voir comme définie par compréhension dans Ej. De même on définit l'intersection de E où E est un ensemble non vide d'ensembles, comme classe des x tels que ∀F ∈ E, x ∈ F, de sorte que si E est comme ci-dessus l'image de la famille (Ei)i ∈ I, son intersection est égale à celle de cette famille.
Par abus de langage, quand on étudie les intersections d'ensembles (ou de familles) de parties d'un ensemble E précis, on prolongera cette notion au cas de l'intersection de la famille vide (ou de l'ensemble vide) définie comme égale à E lui-même, entendant l'opération comme définie par compréhension dans E.

L'algèbre des parties d'un ensemble
Les parties d'un ensemble E se traduisant en relations unaires sur E, les opérations sur les relations unaires se traduisent en opérations entre parties. Appliquant des relations unaires sur E à une même variable libre x ∈ E, elles deviennent des variables propositionnelles libres entre lesquelles opèrent les connecteurs logiques. Soient A et B des parties de E, et soient A ⇔ x ∈ A, B ⇔ x ∈ B leurs traductions en variables propositionnelles. Voici des opérations entre parties traduisant des connecteurs, à commencer par ceux d'arité 0 ou 1.
faux
∅
non
A
∁E A=E\A
(complémentaire de A dans E)
Cette notion de complémentaire nécessite de préciser E afin de ramener la classe ainsi définie à un ensemble par compréhension. Pour éviter ce problème, seules seront nommées les opérations d'arité 2 entre parties issues des connecteurs qui donnent faux quand A et B sont faux. (En effet, la classe obtenue étant alors inclue dans A∪B, définit dedans par compréhension un ensemble qui ne dépend que de A et B, et non de E):
A ou B
A∪B
(union)
A et B
A∩B
(intersection)
A et ( non
B)
A\B
(différence)
A XOR B
A∆B
(différence symétrique)
Dire que A et B sont disjoints se traduit par A∩B=∅.
On remarque que, tout comme les connecteurs (et) et (ou) sont des cas particuliers d'usage des quantificateurs (∀) et (∃), l'union (respectivement l'intersection) de deux ensembles est un cas particulier de celle d'une famille d'ensembles :
E∪F
= ∪
(E,F)= ∪
{E,F}
E∩F
= ∩
(E,F)= ∩
{E,F}.
La relation d'inclusion entre deux parties F et G d'un ensemble E se traduit par
F ⊂ G ⇔ (∀x ∈ F, x ∈ G) ⇔ (∀x ∈ E, x ∈ F⇒x ∈ G)
Tout comme avec les implications, on notera des chaînes d'inclusions successives entre ensembles :
F ⊂ G ⊂ H ⇔ (F ⊂ G et G ⊂ H)⇒F ⊂ H.
De même, les opérations d'union et d'intersections sont associatives et distributives l'une sur l'autre:
(A∪B)∪C
=A∪(B∪C)= ∪
(A,B,C)
(A∩B)∩C
=A∩(B∩C)= ∩
(A,B,C)
(A∪B)∩C
=(A∩C)∪(B∩C)
(A∩B)∪C
=(A∪C)∩(B∪C)
ce qui tout comme pour les connecteurs est un cas particulier des formules plus générales
(
∪
i ∈ I 
 Ai)∩C=
∪
i ∈ I 
 (Ai∩C),    (
∩
i ∈ I 
 Ai)∪C=
∩
i ∈ I 
 (Ai∪C).

Axiomes des parties et de la puissance
Fixant deux ensembles E et F, considérons la classe des applications f de E vers F, i.e. telles que Domf = E et Imf ⊂ F. C'est un cas particulier de la notion de produit, évoquée précédemment. Or, pas plus que d'ensemble de tous les ensembles, il n'existe d'ensemble de toutes les applications dans lequel celui de toutes celles qui vont de E vers F se définirait par compréhension. Mais les conditions semblent restreindre la classe de manière appréciable, rendant envisageable qu'elle soit un ensemble, i.e. qu'on puisse abstraitement "trouver" tous ses éléments. Alors donc, est-ce un ensemble ? Dans toute la suite nous postulerons que oui, par les axiomes suivants:

Axiome des parties. Pour tout ensemble E, la classe de toutes les parties de E est un ensemble, noté ℘(E). Formellement, pour tout F, on a: F ∈ ℘(E) ⇔ (F ensemble et F ⊂ E).

Axiome de la puissance. Pour tous ensembles E et F, la classe des applications de E dans F est un ensemble noté FE. Formellement, pour tout f on a: f ∈ FE ⇔ (f application, Domf=E et Imf ⊂ F).
En fait, ce ne sont pas exactement des axiomes, mais chacun est constitué d'un enrichissement du langage de la théorie des ensembles par un symbole d'opérateur (respectivement ℘ et le symbole invisible de puissance), suivi d'un axiome portant sur ce symbole. (On appelle ici symbole d'opérateur un symbole de la théorie des ensembles au même titre que = ou ∈ , i.e. quelque chose qui ressemble à un symbole d'opération mais dont les variables n'ont pas pour domaines des ensembles, de sorte qu'il ne s'agit d'opérations objets du même univers).
Cet ajout au langage de la théorie des ensembles, d'un symbole d'opérateur désignant l'ensemble postulé égal à une classe donnée dépendant de paramètres, est ainsi a priori nécessaire pour rendre effectif le postulat suivant lequel cette classe serait un ensemble. Pour expliquer cela, appelons normal un énoncé dont tous les quantificateurs ont pour domaines des ensembles. La question est donc de formuler l'égalité entre une classe d'énoncé P(x) et un ensemble K. L'inclusion de K dans cette classe s'écrit ∀x ∈ K, P(x). Mais, l'autre inclusion aurait la forme anormale ∀x, P(x)⇒x ∈ K (avec un quantificateur universel sur l'univers).
Ce problème se résoud dans le cas des concepts d'union, de compréhension, d'image et de produit cartésien, car les quantificateurs de domaines les résultats de ces opérateurs sont remplaçables par des constructions n'utilisant que des quantificateurs rapportés aux ensembles initiaux. En effet: pour tout ensemble E d'ensembles, le quantificateur ∀x ∈ ∪E, est traduisible par (∀A ∈ E,∀x ∈ A); pour toute application f, le quantificateur ∀x ∈ Imf,…x se traduit par ∀x ∈ Domf, …f(x); et on peut en faire autant avec la compréhension et le produit cartésien.
Mais il y a d'autres classes comme celles des parties d'un ensemble ou des applications d'un ensemble dans un autre, telles que même en admettant qu'elles soient par ailleurs des ensembles (si une telle hypothèse pouvait trouver un sens), un quantificateur indéfini portant sur cette classe ne peut pas se traduire en une construction d'énoncé équivalent normal. Il a alors un grand risque qu'un tel ensemble ne soit identifiable par (i.e. ne soit l'unique objet qui satisfasse) aucun énoncé normal. Seul le fait d'ajouter de l'extérieur un symbole spécifique pour désigner les ensembles en question, et d'inclure l'énoncé anormal qui les identifie, comme axiome de la théorie des ensembles, permet de les reconnaître effectivement comme tels, ce que ne permettrait pas le seul axiome de leur existence.
En l'occurence, l'axiome des parties ne serait au fond que l'énoncé d'une relation entre ℘(E) et l'univers, telle que dans chaque univers donné il existe au plus un objet ℘(E) qui la satisfasse. Finalement, il définit ℘(E) comme dépendant de l'univers. Or, l'intention profonde serait de le concevoir comme objet absolument défini sans considération de l'univers, lequel serait pour cela supposé suffisamment grand pour contenir "vraiment" toutes les parties de E, et par là, le "vrai" ℘(E). Donc, lorsqu'on parlera de ℘(E), on oubliera qu'il s'agit en fait d'un aspect de l'univers.
Les "axiomes" composites des parties et de la puissance, bien que n'étant ainsi pas vraiment des énoncés, sont néanmoins "équivalents", autrement dit il suffit d'en postuler un des deux pour que l'autre en résulte. Voici ce que cela signifie: l'axiome de la puissance "implique" l'axiome des parties, en ce sens qu'il est possible de désigner l'ensemble ℘(E) en termes de l'opération de puissance (VE). Réciproquement, on peut désigner l'ensemble puissance FE en termes de ℘(E×F), au moyen de la représentation des applications par leur graphe (comme précisé plus loin).
Cet "axiome" des parties ou de la puissance, enrichissant le langage de la théorie des ensembles, est introduit parce qu'il est indispensable pour pouvoir s'exprimer raisonnablement en mathématiques, en énonçant les nombreuses définitions dont on a besoin. Sans lui, on ne pourrait plus dire grand-chose. On ne pourrait pas toujours distinguer si un ensemble est fini ou infini: un ensemble ne pourrait être déclaré fini que s'il est construit "à la main", élément par élément, ou du moins s'il satisfait une propriété qui limite formellement son nombre d'éléments. Il n'y aurait plus de ℕ, ni encore moins de définition de suites par récurrence. On pourrait seulement établir l'existence d'un ensemble puissance FE lorsqu'on saurait que E est fini.
Heureusement, accepter le langage et les axiomes des parties et de la puissance n'entraîne pas de contradiction (du moins on espère qu'on en trouvera pas, tout en sachant que la non-contradiction d'une théorie des ensembles comme celle-ci ou d'autres est de toute manière indémontrable).
Mais, lorsqu'on explore les fondements des mathématiques, on découvre que la question posée par ces axiomes, de la désignation ou de l'existence des ensembles des parties ou des ensembles puissances, est un problème central, sur lequel repose l'essentiel de l'incomplétude des mathématiques.
Précisément, contrairement au cas d'un ensemble démontrablement fini évoqué ci-dessus, si E est un ensemble infini et F a plus d'un élément, il s'avère impossible de formaliser totalement l'affirmation qu'un ensemble donné d'applications de E dans F, même noté FE, contient réellement toutes les applications de E dans F: bien qu'effectivement d'après l'axiome il contient toutes celles qui sont dans notre univers, on ne peut exclure qu'il puisse exister ailleurs, dans un autre univers plus grand, d'autres applications de E dans F qui n'appartiennent pas à notre FE. L'axiome de la puissance peut être aussi vrai dans cet autre univers, mais avec une autre interprétation des ensembles de parties et de puissance. C'est par ces jeux de Grandes Illusions se démontrent nombre de résultats d'indécidabilités des mathématiques (un énoncé est dit indécidable si ni lui ni sa négation n'est démontrable).
Alors donc, nous poserons les axiomes (équivalents) des parties et de la puissance parce que nous en aurons besoin au départ des mathématiques. En aurons-nous vraiment besoin ? Si on examine attentivement les mathématiques courantes, et même celles qui constituent tout l'essentiel du cycle fondateur des mathématiques, il s'avère que, en gros, on n'utilise guère que les ensembles finis, l'ensemble ℕ des entiers naturels et l'ensemble ℘(ℕ) de ses parties (qui permet de construire l'ensemble ℝ des nombres réels); qu'il est rare d'aller plus loin, et que même si on se permet parfois de parler de "parties quelconques de ℝ", ce n'est souvent en pratique que pour en dire des choses qu'on pourrait avec plus ou moins de difficultés réécrire en termes de ℝ seul, sans lui appliquer l'axiome des parties. Mais ici, comme d'ailleurs suivant la tradition ZF, nous accepterons l'axiome des parties, lequel permet à partir de ℕ d'invoquer non seulement ℘(ℕ) mais aussi ℘(℘(ℕ)), ℘(℘(℘(ℕ))) et ainsi de suite, donc bien plus que ce qui est nécessaire en pratique.
Pourrait-on alors se contenter d'un axiome plus faible ? Bien sûr, sauf que pour cela il faudrait écrire par exemple "on désigne par ℘(ℕ) l'ensemble de toutes les parties de ℕ" (ce qui est d'ailleurs un pléonasme puisqu'on utilise un énoncé avec quantificateur sur ℘(ℕ) pour formuler que ℕ désigne bien l'ensemble des entiers naturels), ou encore "il existe un ensemble infini dont on a l'ensemble des parties" (avec une remarque du même style). Mais de telles subtilités n'ont guère d'intérêt dans une première approche des mathématiques, et, étant donnée la relative complexité de l'introduction de ℕ ou de la notion d'ensemble infini, compliqueraient encore l'exposé, par les précautions prises à marcher sur des oeufs. Or nous voulions partir des fondements les plus simples possibles. Par mesure de simplicité donc, nous accepterons l'axiome des parties dans son intégralité.
Nous n'avons pas encore ici complété la formulation d'une théorie des ensembles suffisante pour fonder les mathématiques. Pour cela, il restera à poser l'axiome de l'infini: "Il existe un ensemble infini" (une fois définie la notion d'ensemble infini), permettant de construire ℕ et bien d'autres ensembles intéressants. Car bien sûr, sans ensemble infini, toute la force de l'axiome des parties que nous venons de commenter resterait quasiment sans objet.
On abbrègera l'expression ∀A ∈ ℘(E) en ∀A ⊂ E, et de même pour ∃.

Produit
Montrons que l'axiome de la puissance est aussi "équivalent" à la donnée des ensembles produit.
On définit le produit de toute famille d'ensembles (Ei)i ∈ I, grâce aux axiomes de la réunion et de la puissance, par

∏
i ∈ I 
 Ei = {f ∈ (
∪
i ∈ I 
 Ei)I|∀i ∈ I,f(i) ∈ Ei}
f ∈
∏
i ∈ I 
 Ei ⇔ (f application,  Dom
f=I et ∀i ∈ I, f(i) ∈ Ei)
Réciproquement, l'ensemble puissance FE est égal à au produit de la famille constante ∏i ∈ IF.
Pour tout i ∈ I on appelle i-ième projection canonique, l'application πi de ∏i ∈ I Ei dans Ei qui à toute famille x associe l'image de i par x: πi(x)=xi.
On peut voir cela comme une sorte de renversement des rôles entre l'application (famille) et sa variable (son indice), c'est-à-dire, si on voit l'expression xi comme une opération entre les deux objets x et i, le fait de fixer i et laisser x variable de domaine le produit, au lieu de fixer x et de laisser i variable comme on le conçoit à la base.

Somme ou union disjointe
Etant donnée une famille (Ei)i ∈ I d'ensembles, on définit leur somme ou union disjointe (même si les Ei ne sont pas disjoints) comme étant l'union de copies des Ei deux à deux disjointes. Comment construit-on de telles copies ? Un élément d'une telle copie comporte deux informations: l'indice i et l'élément x de Ei qu'il représente. C'est donc le couple (i,x):
∐i ∈ IEi={(i,x)|i ∈ I et x ∈ Ei} ⊂ I×
∪
i ∈ I 
 Ei
∐i ∈ IE=I×E.

Opérations et inclusions
F ⊂ F′⇒
    FE ⊂ F′E
E ⊂ E′,F ⊂ F′⇒
    E×F ⊂ E′×F′
(∀i ∈ I, Ei ⊂ E′i)⇒
   
∏
i ∈ I 
 Ei ⊂
∏
i ∈ I 
 E′i     et     ∐i ∈ IEi ⊂ ∐i ∈ IE′i.

2.3. Etude des applications

Graphe d'une application
Pour toute relation R entre E et F, on avait déjà défini son graphe comme étant
Gr
(R)={(x,y) ∈ E×F|R(x,y)}.
Soit f une application de E dans F. On appelle graphe de f l'ensemble (indépendant de f)
Gr
f= Im
(IdE×f) = {(x,f(x))|x ∈ E} ⊂ E×F

∀x ∈ E,∀y ∈ F,     (x,y) ∈ Gr
f
 ⇔ ∃x′ ∈ E, (x,y)=(x′,f(x′))
 ⇔ ∃x′ ∈ E, x=x′ et y=f(x′)
 ⇔ y=f(x)
.
Pour tous f,g ∈ FE et toutes relations R,S entre E et F on a
Gr
(R) ⊂ Gr
(S)
 ⇔ ∀x ∈ E, ∀y ∈ F, (R(x,y)⇒S(x,y))
Gr
(R)= Gr
(S)
 ⇔ ∀x ∈ E, ∀y ∈ F, (R(x,y) ⇔ S(x,y))
Gr
(f) ⊂ Gr
(R)
 ⇔ ∀x ∈ E, R(x,f(x))
Gr
(R) ⊂ Gr
(f)
 ⇔ ∀x ∈ E, ∀y ∈ F, (R(x,y)⇒y=f(x))
Gr
(f)= Gr
(R)
 ⇔ ∀x ∈ E, ∀y ∈ F, (R(x,y) ⇔ y=f(x))
Gr
(f) ⊂ Gr
(g)
 ⇔ f=g.
La dernière ligne se vérifie en écrivant
Gr
(f) ⊂ Gr
(g) ⇔ (∀x ∈ E, (x,f(x)) ∈ Gr
(g)) ⇔ (∀x ∈ E, f(x)=g(x)) ⇔ f=g.
De plus, deux applications ayant même graphe sont égales. En effet, elles ont même domaine Domf=π1[Grf], puis le reste vient d'être vu.
Comme toute partie P ⊂ E×F est le graphe d'une unique relation (x,y) ⟼ ((x,y) ∈ P) entre E et F, la donnée d'une application f de E dans F se traduit donc, à travers son graphe, sous forme de la relation (y=f(x)) entre E et F.
Soit R une relation entre deux ensembles E et F. Alors on a
(∀x ∈ E, ! y ∈ F, R(x,y))⇒ ! f ∈ FE, Gr
(f) ⊂ Gr
(R)
En effet, si la partie de gauche est vraie alors ∀f,g ∈ FE, Gr(f) ⊂ Gr(R) et Gr(g) ⊂ Gr(R)⇒(∀x ∈ E, R(x,f(x)) et R(x,g(x)))⇒∀x ∈ E, f(x)=g(x)⇒f=g.

Proposition. Soit R une relation entre deux ensembles E et F. Il y a équivalence entre
1. ∀x ∈ E, ∃!y ∈ F, R(x,y)
2. ∃f ∈ FE, Gr(f)=Gr(R)
3. ∃!f ∈ FE, Gr(f)=Gr(R)
4. ∃!f ∈ FE, Gr(f) ⊂ Gr(R).
Preuves:
1.⇒2. peut être vue comme un axiome: l'expression du fait que lorsqu'on trouve une relation qui a manifestement la propriété qui en fait un graphe d'application, alors, l'application qu'elle définit, sera effectivement reconnue comme application qui existe formellement dans FE.
2.⇒1. est immédiat: ∀x ∈ E, ∃! y ∈ F, y=f(x).
2. ⇔ 3. est évident.
(1. et 2.)⇒4. : 2. donne l'existence du f; 1. donne son unicité par le résultat plus haut.
4.⇒2. : soit f tel que Gr(f) ⊂ Gr(R). Alors ∀(x,y) ∈ Gr(R),Gr(x′ ⟼ (y,f(x′))(x=x′)) ⊂ Gr(R), donc f=(x′ ⟼ (y,f(x′))(x=x′)), donc y=f(x). Finalement Gr(f)=Gr(R).
Les cours traditionnels présentent la notion d'application comme n'étant pas première, mais comme ramenée à la notion d'ensemble au moyen du graphe. Or cela pose deux problèmes: d'une part, pour traiter de même la notion de relation, il faudrait ajouter à la donnée de son graphe celle des domaines de ses variables, ce qui en fait une notion composite; d'autre part cela utilise la notion de couple. Nous n'avons pas procédé ainsi à cause de l'intérêt de définir les couples comme cas particuliers d'applications, et des spécificités de la notion d'application avec ses usages et notations, auxquels le formalisme des relations n'est guère adapté.

Injections, surjections, bijections

Théorème et définition. Pour toute application f d'un ensemble E dans un ensemble F, les énoncés suivants sont équivalents, et seront désignés en disant que f est injective (ou : une injection ):
∀x, x′ ∈ E, f(x)=f(x′)⇒x=x′
∀y ∈ F, !x ∈ E, f(x)=y
Preuve: les équivalences s'enchaînent ainsi (utilisant que f(x) ∈ F):
∀y ∈ F, !x ∈ E, f(x)=y
 ⇔ ∀y ∈ F, ∀x,x′ ∈ E, (f(x)=y et f(x′)=y)⇒x=x′
 ⇔ ∀x,x′ ∈ E, ∀y ∈ F, f(x)=y⇒(f(x′)=y⇒x=x′)
 ⇔ ∀x,x′ ∈ E, f(x)=f(x′)⇒x=x′
Remarque: la première formule peut aussi s'écrire sous la forme plus intuitive mais moins utilisée en pratique dans les démonstrations:
∀x, x′ ∈ E, x ≠ x′⇒f(x) ≠ f(x′).

Définition. On dit qu'une application de E dans F est surjective (ou une surjection) lorsque Imf=F, autrement dit lorsque ∀y ∈ F,∃x ∈ E, f(x)=y.
C'est donc en quelque sorte non une propriété de f en elle-même mais une relation entre f et l'ensemble d'arrivée mentionné. On dit aussi, pour insister, une surjection de E sur F.
Une application bijective (ou bijection) f de E sur F est une application injective et surjective de E sur F, autrement dit telle que ∀y ∈ F, ∃! x ∈ E, f(x)=y.
Une bijection d'un ensemble sur lui-même s'appelle une permutation (on dit aussi une transformation pour un espace géométrique).

Identité, composition et restriction
Pour toutes applications f ∈ FE et g ∈ GF, on définit leur composée g∘f ∈ GE par :
g∘f=(E ∋ x ⟼ g(f(x))).
De même pour la composée de toute chaîne d'applications entre ensembles successifs :
h∘g∘f=(h∘g)∘f=h∘(g∘f)=( Dom
f ∋ x ⟼ h(g(f(x)))).
Pour tout ensemble E on appelle identité sur E l'application
IdE=(E ∋ x ⟼ x) ∈ EE.
qu'on appellera aussi l'injection canonique de E dans tout ensemble dans lequel E est inclus.
Pour toute application f ∈ FE et A ⊂ E, on appelle restriction de f à A l'application notée f|A ∈ FE′, définie par
f|A=(A ∋ x ⟼ f(x))=f∘IdA ∈ FA.
ce qui définit une surjection de FE sur FA si F ≠ ∅ (voir plus loin un résultat plus général).

Image directe, image reciproque
Soient f ∈ FE et B ⊂ F. On appelle image réciproque de B par f et on note f*(B) l'ensemble
f*(B)={x ∈ E|f(x) ∈ B}.
Cette notation f* ne peut être vue comme désignant une application qu'à condition de choisir un ensemble d'arrivée F de f, dont l'ensemble des parties servira de domaine.
Si A ⊂ B ⊂ F alors f*(A) ⊂ f*(B) et f*(∁F A)=∁Ff*(A).
Pour toute famille d'ensembles (Ai)i ∈ I,
f*(
∪
i ∈ I 
 Ai)=
∪
i ∈ I 
 f*(Ai)
f*(
∩
i ∈ I 
 Ai)=
∩
i ∈ I 
 f*(Ai).
Soit maintenant un ensemble A ⊂ E. On appelle image directe de A par f et on note f[A] l'ensemble
f[A]= Im
(f|A)={f(x)|x ∈ A}={y ∈ F| ∃x ∈ A, y=f(x)} ⊂ Im
f ⊂ F.
(Cette notation avec crochets, évitant les ambiguités de l'usage classique des parenthèses, est celle du Wikipedia anglophone.) C'est une surjection f[] de ℘(E) sur ℘(Imf) car ∀B ⊂ Imf, f[f*(B)]=B.
Pour tous A ⊂ B ⊂ E on a f[A] ⊂ f[B]. Pour toute famille (Ai)i ∈ I de parties de E,
f[
∪
i ∈ I 
 Ai]=
∪
i ∈ I 
 f[Ai]
f[
∩
i ∈ I 
 Ai] ⊂
∩
i ∈ I 
 f[Ai]
où l'inclusion devient une égalité notamment si (f est injective et I ≠ ∅).

Proposition. Soient deux applications f ∈ FE et g ∈ GF. On a:
1) Si f et g sont injectives alors g∘f est injective.
2) Im(g∘f)=g[Imf] ⊂ Img
3) Si f est surjective (i.e. Imf=F) alors Im(g∘f)=Img.
4) Si f et g sont surjectives alors g∘f est surjective (i.e. Im(g∘f)=G).
5) Si g∘f est surjective alors g est surjective.
6) Si g∘f est injective alors f est injective.
7) Si f et g sont bijectives alors g∘f est bijective.
Preuves:
1) Si f et g sont injectives, ∀, x,y ∈ E, g(f(x))=g(f(y))⇒f(x)=f(y)⇒x=y.
2) ∀z ∈ G, z ∈ Im(g∘f) ⇔ (∃x ∈ E, g(f(x))=z) ⇔ (∃y ∈ Imf, g(y)=z) ⇔ z ∈ g[Imf].
3) résulte de 2)
4) résulte de 3)
5) résulte de 2)
6) Si g∘f est injective alors ∀x,y ∈ E, f(x)=f(y)⇒(g∘f)(x)=(g∘f)(y)⇒x=y.
7) vient de 1) et 4).∎

Transposition
Une transposition est une permutation qui échange deux éléments et laisse fixe les autres.
En particulier, dans une paire on s'intéressera à l'unique transposition, qu'on notera σ. C'est l'unique cas d'une permutation d'un ensemble sans structure, qui soit canonique et différente de l'identité. Soit maintenant une opération f à deux variables de domaines E et F. Voyant f comme application de domaine E×F, on appellera transposée de f l'opération tf entre F et E obtenue par transposition des positions des variables dans l'écriture de f:
∀y ∈ F,∀x ∈ E, tf(y,x)=f(x,y)=f((y,x)∘σ).
Ceci s'applique en particulier au cas d'une relation entre deux ensembles, et, suivant la correspondance entre ces relations et les ensembles de couples, on parlera aussi de transpositions sur les ensembles C de couples:
tC={(y,x)|(x,y) ∈ C}.

Inversion d'applications et propriétés de la composition
Soient E et F deux ensembles, f ∈ FE et g ∈ EF. Alors on a équivalence entre
1) g∘f=IdE
2) ∀x ∈ E, ∀y ∈ F, f(x)=y⇒g(y)=x
3) Grf ⊂ tGrg.
4) ∀y ∈ F, f*({y}) ⊂ {g(y)}
5) ∀x ∈ E, f(x) ∈ g*({x})

Vérification facile, dans l'ordre suivant: 5 ⇔ 1 ⇔ 2 ⇔ 3 ⇔ 4 (et aussi 2 ⇔ 4).
On remarque que ces conditions impliquent que f est injective.
De même en combinant ces énoncés avec ceux où on échange f et g: on a équivalence entre
1) g∘f=IdE et f∘g = IdF.
2) ∀x ∈ E,∀y ∈ F, f(x)=y ⇔ g(y)=x
3) Grg=tGrf.
4) ∀y ∈ F, f*({y})={g(y)}
5) ∀x ∈ E, {f(x)} = g*({x})
D'après les propriétés des graphes d'applications,
∀f ∈ FE,    f bijective
 ⇔ ∃g ∈ EF, Gr
g=t Gr
f
 ⇔ ∃! g ∈ EF, Gr
g=t Gr
f
 ⇔ ∃! g ∈ EF, Gr
g ⊂ t Gr
f.
Par ailleurs, on remarque que quelles que soient les applications f et g sans hypothèse sur les domaines et images, l'égalité Grg=tGrf implique à elle seule que Domf=Img, Domg=Imf et que f et g sont injectives. Toute injection pouvant être regardée comme bijective sur son image, on peut poser:

Définition. Pour toute injection f, on appelle inverse de f et on note f−1 l'application définie par Gr(f−1)=tGrf; elle est bijective de Imf sur Domf.
Comme la condition Grg=tGrf équivaut à Grf=tGrg, on a (f−1)−1=f.

Proposition. Soient deux ensembles E et F et trois applications f,h ∈ FE, g ∈ EF telles que g∘f=IdE et h∘g=IdF. Alors f=h, de sorte que f et g sont l'inverse l'un de l'autre.
Preuve: ∀x ∈ E, f(x)=h(g(f(x)))=h(x).

Proposition. Soient deux applications f ∈ FE et g ∈ GF bijectives. Alors (g∘f)−1=f−1∘g−1.
On peut écrire la preuve
∀x ∈ E, ∀y ∈ G, g∘f(x)=y ⇔ f(x)=g−1(y) ⇔ x=f−1∘g−1(y)
ou encore (g∘f)∘(f−1∘g−1)=g∘IdF∘g−1 = IdG, et de même (f−1∘g−1)∘(g∘f)=IdE.

Théorème. Soient trois ensembles E, F, G, soit f ∈ FE, et soit φ = (GF ∋ g ⟼ g∘f) l'application de composition à droite par f, arrivant dans GE. On a alors:
1) Si f est surjective alors φest injective
2) Si f est injective et G ≠ ∅alors φest surjective
3) Si φest injective et ∃z,z′ ∈ G, z ≠ z′ alors f est surjective.
4) Si φest surjective et ∃z,z′ ∈ G, z ≠ z′ alors f est injective.
Preuves:
1) ∀g,h ∈ GF, φ(g)=φ(h) ⇔ (∀x ∈ E, g(f(x))=h(f(x)) ⇔ ∀y ∈ F, g(y)=h(y) ⇔ g=h.
2) Soient h ∈ GE et z ∈ G. Alors, f étant injective, φ(F ∋ y ⟼ (h∘f−1(y),z)(y ∈ Imf))=h.
3) φ(y ⟼ z)=φ(y ⟼ (z,z′)(y ∈ Imf))⇒(∀y ∈ F, (y ∈ Imf  ou z=z′))⇒Imf=F.
4) ∀x ∈ E,∃g ∈ GF, ∀y ∈ E, g(f(y))=(z,z′)(y=x) donc f(y)=f(x)⇒g(f(y))=g(f(x))=z⇒y=x.
Prenant dans 2) le cas G=E on a en particulier

Corrollaire 1. Soit une injection f ∈ FE où E ≠ ∅, alors ∃g ∈ EF, g∘f=IdE.
Par ailleurs le cas G=V se traduit par

Corrollaire 2. Soient deux ensembles E, F, soit f ∈ FE, et considérons f* comme application de ℘(F) dans ℘(E). Alors on a (f injective  ⇔ f* surjective), et (f surjective  ⇔ f* injective).

Théorème. Soient trois ensembles E, F, G, soit g ∈ GF, et soit ψ = (FE ∋ f ⟼ g∘f) l'application de composition à gauche par g, arrivant dans GE. On a alors:
1) Si g est injective alors ψest injective
2) (Si g est surjective alors ψest surjective) est une expression de l'axiome du choix.
3) Si ψest injective et E ≠ ∅alors g est injective.
4) Si ψest surjective et E ≠ ∅alors g est surjective.
Preuves:
1) ∀f,f′ ∈ FE, ψ(f)=ψ(f′) ⇔ ∀x ∈ E, g(f(x))=g(f′(x))⇒∀x ∈ E, f(x)=f′(x)⇒f=f′.
2) sera étudié avec l'axiome du choix.
3) ∀y,y′ ∈ F, g(y)=g(y′)⇒ψ(x ⟼ y)=ψ(x ⟼ y′)⇒(∀x ∈ E, y=y′)⇒y=y′ car E ≠ ∅.
4) ∀z ∈ G, ∃f ∈ FE, g∘f=(x ⟼ z) donc E ≠ ∅⇒z ∈ Img.

Proposition. Soient f ∈ FE, g ∈ EF tels que g∘f=IdE. Alors f est injective, g est surjective, et on a les équivalences : (f surjective ) ⇔ (g injective ) ⇔ f∘g=IdF.
Preuve:
Les premiers résultats découlent de l'injectivité et la surjectivité de IdE=g∘f.
De f∘g=IdF on tire les résultats analogues en échangeant f et g.
Si f est surjective alors f∘g∘f=f⇒f∘g=IdF
Si g est injective alors g∘f∘g=g⇒f∘g=IdF. ∎
En particulier, si f ou g est bijective et g∘f=IdE alors f et g sont l'inverse l'un de l'autre.

Points fixes; applications idempotentes

Définition. Etant donnée une application f d'un ensemble E dans lui-même, on dit qu'un élément x ∈ E est un point fixe de f ssi f(x)=x. L'ensemble des points fixes de f sera noté Fixf.

Définition. Une application f d'un ensemble dans lui-même est dite idempotente ssi f∘f=f.
Pour tous ensembles E et F, tous f ∈ FE et g ∈ FF,
Fix
g ⊂ Im
g
g∘f=f ⇔  Im
f ⊂ Fix
g
g∘g=g ⇔  Im
g= Fix
g

2.4. Bijections canoniques remarquables

Les identités remarquables usuelles reliant les opérations entre entiers se retrouveront ici en remplaçant l'égalité par l'existence de bijections canoniques. L'existence d'une bijection canonique entre deux ensembles E et F (donnés sous forme de termes dépendant d'autres noms d'ensembles), sera notée E ≅ F.
Tout comme pour la notion d'objet canonique dont ceci est un cas particulier, cette notation E ≅ F, est un énoncé métamathématique qui a pour objet de sous-entendre un autre énoncé, à savoir un énoncé de définition d'une bijection f entre E et F. En pratique, cela pourra être un énoncé P de variables x ∈ E, y ∈ F, de paramètres les noms des ensembles figurant dans les termes définissant E et F, tel que P(x,y) désigne f suivant P(x,y) ⇔ y=f(x).
Dans les situations auquelles nous nous intéresserons, lorsque E ≅ F et F ≅ G on aura E ≅ G. En effet, en assemblant les énoncés définissant les bijections entre E et F et entre F et G on obtient une définition d'une bijection entre E et G.
Mais dans des situations auxquelles nous ne nous intéresserons pas, cela pourrait être faux, comme par exemple si ce sont des paires d'éléments purs, que E∩G=∅ et que F est formé d'un élément de E et d'un élément de G: dans ce cas, la bijection définie entre E et G dépend de F et n'est donc pas canonique. Mais, dans les situations auxquelles nous nous intéresserons, donc, il sera possible d'éliminer le paramètre F, par exemple en le remplaçant par sa définition à partir de ce qui constitue E et/ou G, pour aboutir à une définition sans paramètre.
Des bijections canoniques entre des ensembles et d'autres ensembles permettent de définir des bijections canoniques entre ensembles construits à partir des premiers et ceux construits de même à partir des seconds, par exemple (E ≅ E′ et F ≅ F′)⇒(EF ≅ E′F′ et E×F ≅ E′×F′).
La transposition (composition des couples avec σ) donne une formule de commutativité du produit cartésien: E×F ≅ F×E.
Nous avons précédemment mentionné la bijection canonique
GE×F
≅ (GF)E
f
⟼ (x ⟼ (y ⟼ f(x,y)))
d'inverse g ⟼ ((x,y) ⟼ g(x)(y)). Il en résulte (GF)E ≅ GE×F ≅ GF×E ≅ (GE)F.
Dans le cas G=V, ces identités traduites par VE ≅ ℘(E) donnent
(℘(F))E ≅ VE×F ≅ ℘(E×F) ≅ (℘(E))F.
Pour toute relation R entre deux ensembles E et F, notons R→ ∈ ℘(F)E et R← ∈ ℘(E)F les images de R par ces bijections canoniques:
∀x ∈ E, →
R
 
 (x)
={y ∈ F|x R y}
∀y ∈ F, ←
R
 
 (y)
={x ∈ X|x R y}
∀x ∈ E,∀y ∈ F,x R y
 ⇔ x ∈ ←
R
 
 (y) ⇔ y ∈ →
R
 
 (x).
Etant donnée une famille d'ensembles ∏i ∈ I Fi, la formule (FI)E ≅ (FE)I appliquée à l'union F des Fi donne par restriction
(
∏
i ∈ I 
 Fi)E
≅
∏
i ∈ I 
 (FiE)
h
⟼ (fi)i ∈ I
définie par ∀i ∈ i, fi=πi∘h, ou inversement par ∀x ∈ E, h(x)=(fi(x))i ∈ I. On dit que h est le produit de la famille (fi), et on le note h=∏i ∈ i fi.
En particulier, étant données deux applications f et g de même domaine E, leur produit est
f×g=(E ∋ x ⟼ (f(x),g(x))).
De cette manière, (F×G)E ≅ FE×GE, qui se raffine en la formule du développement
(∐i ∈ I Fi)E ≅ ∐h ∈ IE
∏
x ∈ E 
 Fh(x).
La bijection GE×F ≅ (GF)E se raffine en
F∐i ∈ IEi ≅
∏
i ∈ I 
 FEi
où une application f de ∐i ∈ IEi dans F est liée à une famille d'applications fi ∈ FEi par ∀i ∈ i, fi=f∘ji où ji est l'injection canonique (x ⟼ (i,x)) de Ei dans ∐i ∈ IEi. On écrira alors
f=∐i ∈ Ifi
Cette opération de somme d'une famille d'applications, est ainsi nommée parce que son graphe est essentiellement la somme des graphes respectifs, (Gr(f)=∪i ∈ IIm(ji×fi) et elle s'applique à toute famille (fi)i ∈ I; elle ne dépend pas de l'ensemble d'arrivée F. On peut aussi l'écrire sous la forme f(x)=fπ(x)(jπ(x)−1(x)) où π est la première projection de ∐i ∈ IEi sur I (avec j(x)=i ⇔ x ∈ Imji).
Par restriction à des sous-ensembles, cette bijection canonique donne également

∏
i ∈ I 
∏
y ∈ Ei 
 F(i,y) ≅
∏
x ∈ ∐i ∈ IEi 
 Fx
dont un cas très particulier donne (E×F)×G ≅ E×F×G.
Nous ne détaillerons pas E{x} ≅ E, E×{x} ≅ E, E×∅ = ∅, {x}E ≅ {x}, E∅ ≅ {x}, et pour E ≠ ∅, ∅E=∅.

2.5. Notions sur les relations binaires.

On appelle relation binaire sur un ensemble E, une relation à deux variables de même domaine E. Par exemple sur tout ensemble la relation d'égalité est une relation binaire.
Dans ce qui suit nous noterons ces deux variables de part et d'autre du symbole de relation (comme x R y) au lieu de les noter à droite entre parenthèse (comme R(x,y)); bien sûr cela ne change rien au fond.
Une relation binaire  R  sur un ensemble E est dite:
- réflexive ssi ∀x ∈ E, x R x
- antiréflexive ssi ∀x ∈ E, non(x R x)
- symétrique ssi ∀x,y ∈ E, x R y⇒y R x
- antisymétrique ssi ∀x,y ∈ E, (x R y et y R x)⇒x=y.
- transitive ssi ∀x,y,z ∈ E, (x R y et y R z)⇒x R z
Toute relation binaire transitive et antiréflexive est antisymétrique.

Préordre. On appelle préordre toute relation binaire réflexive et transitive. Un ensemble muni d'une relation de préordre est dit un ensemble préordonné. Un préordre antisymétrique est appelé un ordre (ou: relation d'ordre). Un ensemble muni d'un ordre est appelé un ensemble ordonné.

Relation d'équivalence. On nomme ainsi une relation de préordre symétrique.
Sous-entendons les quantificateurs comme portant sur E dans la proposition suivante.

Proposition. 1) Si  R  est un préordre alors x R y ⇔ R←(x) ⊂ R←(y), i.e.
∀x,y, x R y ⇔ ∀z,(z R x⇒z R y)
2) Si de plus  R  est symétrique (donc, une relation d'équivalence) alors x R y ⇔ R←(x)=R←(y), i.e.
∀x,y, x R y ⇔ ∀z,(z R x ⇔ z R y)
3) Si R est réflexive et ∀x,y,z, (x R y et z R y)⇒z R x alors R est une relation d'équivalence.
Preuves:
1) La transitivité se réécrit ∀x,y, x R y⇒∀z,(z R x⇒z R y).
Puis,  R  étant réflexive, ∀x,y, (∀z, z R x⇒z R y)⇒(x R x⇒x R y)⇒x R y.
2) ∀x,y,x R y ⇔ (x R y et y R x) ⇔ (R←(x) ⊂ R←(y) et R←(y) ⊂ R←(x)) ⇔ (R←(x)=R←(y)).
3) on vérifie la symétrie: ∀x,y, (x R y et y R y)⇒y R x. La transitivité en découle.∎

On voit facilement que les réciproques de 1) et 2) sont vraies aussi. Ainsi, leurs formules étant respectivement équivalentes aux notions de préordre et de relation d'équivalence, peuvent donc leur servir de définitions.

2.6. Etude des relations d'équivalence

Partitions et familles-partitions
Soit E un ensemble.
On appellera famille-partition de E une famille (Ai)i ∈ I de parties de E non vides, deux à deux disjointes et dont l'union est E, autrement dit
∀i ∈ I, Ai ≠ ∅
∀i,j ∈ I, i ≠ j⇒Ai∩Aj=∅

∪
i ∈ I 
 Ai=E
Reformulons la deuxième condition:
(∀i,j ∈ I, i ≠ j⇒Ai∩Aj=∅)
 ⇔ ∀i,j ∈ I, i ≠ j⇒∀x ∈ E, non
(x ∈ Ai et x ∈ Aj)
 ⇔ ∀i,j ∈ I, ∀x ∈ E, i ≠ j⇒ non
(x ∈ Ai et x ∈ Aj)
 ⇔ ∀x ∈ E, ∀i,j ∈ I, (x ∈ Ai et x ∈ Aj) ⇒i=j
 ⇔ ∀x ∈ E, !i ∈ I, x ∈ Ai
Par conséquent, le système des 3 conditions pour qu'une famille (Ai)i ∈ I de parties de E soit une famille-partition de E se résume en un système de deux conditions
∀i ∈ I, ∃x ∈ E, x ∈ Ai
∀x ∈ E, ∃!i ∈ I, x ∈ Ai.
On appelle partition de E un ensemble P d'ensembles non vides, deux à deux disjoints et dont l'union est E. Ceci équivaut à dire que IdP est une famille-partition de E.
Nous allons examiner les correspondances entre les notions suivantes, concernant un même ensemble E:
- Surjection de domaine E;
- Famille-partition de E;
- Partition de E;
- Relation d'équivalence sur E.

Surjection et famille-partition
Soit une application quelconque f de domaine un ensemble E, et I=Imf. Alors, définissons l'application f• de I dans ℘(E) (autrement dit une famille de parties de E indexée par I), par
∀i ∈ I, f•(i)=f*({i})={x ∈ E|f(x)=i}.
Autrement dit, f• est définie comme étant l'unique application de I dans ℘(E) telle que
∀i ∈ I, ∀x ∈ E, x ∈ f•(i) ⇔ f(x)=i.
On remarque qu'à travers la bijection canonique ℘(E)I ≅ ℘(E×I), f• correspond au graphe de f. Or par cette même correspondance, le système de formules définissant la notion de famille-partition de E, se traduit en celui caractérisant les graphes de surjections de E sur I. Ceci définit une bijection canonique entre l'ensemble des surjections de E sur I, et celui des familles-partitions de E indexées par I.

De surjection à relation d'équivalence

Soit une application f de domaine E. On appelle relation d'équivalence sur E associée à f la relation binaire  ∼ f sur E définie par
∀x,y ∈ E, x 
 ∼ 
f 
   y  ⇔ f(x)=f(y).
En effet, les propriétés de réflexivité, symétrie et transitivité d'une relation ainsi définie se vérifient immédiatement.

Relation d'équivalence et partition, surjection canonique

Soit  R  une relation binaire sur E et P=ImR←.
Le fait que  R  soit une relation d'équivalence, se réexprime par les formules équivalentes
∀x,y ∈ E, x R y ⇔  ←
R
 
 (x)= ←
R
 
 (y)
∀x,y ∈ E, x ∈ ←
R
 
 (y) ⇔  ←
R
 
 (x)= ←
R
 
 (y)
∀x ∈ E, ∀A ∈ P, x ∈ A=IdP(A) ⇔  ←
R
 
 (x)=A
IdP= ←
R
 
 •.
L'ensemble des partitions de E, autrement dit des P ⊂ ℘(E) tels que IdP est une famille-partition de E, donc de la forme R←• pour une certaine relation binaire R sur E finalement unique, est ainsi en bijection canonique avec l'ensemble des relations d'équivalence.
Dans les constructions ci-dessus, lorsque  R  est une relation d'équivalence, et que donc P est une partition, l'ensemble P est appelé le quotient de E par  R  et noté E/R; et l'application R←:E→P est appelée surjection canonique de E sur E/R. Pour tout x ∈ E, l'élément R←(x), unique élément A de P tel que x ∈ A, est appelé la classe de x par  R .

De surjection à partition
A toute surjection f de E sur I nous avons associé une relation d'équivalence  R  sur E par ∀x,y ∈ E,x R y ⇔ f(x)=f(y), et montré que toute relation d'équivalence R est égale à celle associée à R←. Puis nous avons associé à une telle relation R une partition P=ImR← de E.
Nous allons maintenant voir que P=Im(f•), tout comme il était égal à Im(R←•) où R←•=IdP.
En effet, la définition de R se traduit par
∀x,y ∈ E, x ∈ ←
R
 
 (y) ⇔ f(x)=f(y) ⇔ x ∈ f•(f(y))
autrement dit R← =f•∘f, d'où P=ImR← =Imf• puisque f est surjective.
L'ensemble I muni de f, étant naturellement par f• en bijection avec E/R, pourra être utilisé comme jouant le rôle de E/R, autrement dit être vu comme un autre quotient (une copie du quotient) de E par  R ; le rôle de la surjection canonique est alors joué par f.

Remarque. f•est injective.
On peut le voir directement, ou en notant que  ∼ f=  ∼ f•∘f . Cette injectivité devient fausse lorsqu'on étend f• à plus d'un élément hors de Imf:

Extension de notation. Ultérieurement, pour toute application f et tout ensemble d'arrivé F de f donné, on notera encore (abusivement) f•l'application F ∋ y→ f*({y})={x ∈ E|f(x)=y}, qui prolonge le f•précédemment défini, par \0 hors de Imf.

Autre résultat

Lemme. Soient trois ensembles E, F, G, deux applications f ∈ FE, g ∈ GE, soit H=Im(f×g)={(f(x),g(x))|x ∈ E} ⊂ F×G, et soit  R  une relation entre F et G. Alors
(∀x ∈ E, R(f(x),g(x)) ⇔ (∀(y,z) ∈ H,y R z)
En effet, R(f(x),g(x)) peut également s'écrire R((f×g)(x)).

Théorème. Avec les notations ci-dessus, si Imf = F et ∀x,x′ ∈ E, f(x)=f(x′)⇒g(x)=g(x′) (ce qu'on peut abbréger en  ∼  f <  ∼ g) alors il existe un unique h ∈ GF tel que g=h∘f.
Preuve: Par le lemme, g=h∘f ⇔ (∀(y,z) ∈ H, z=h(y)) ⇔ H ⊂ Grh.
Il ne reste plus qu'à vérifier que H est le graphe d'une application de F dans G.
De la surjectivité de f il vient ∀y ∈ F, ∃z ∈ G, (y,z) ∈ H (par (y=f(x)⇒(y,g(x)) ∈ H)).
Enfin, par le lemme,

 ∼ 
f 
 <
 ∼ 
g 
 ⇔ ∀(y,z) ∈ H,∀(y′,z′) ∈ H, y=y′⇒z=z′
 ⇔ ∀y ∈ F, ! z ∈ G, (y,z) ∈ H.
∎

Remarque. Ce théorème a une sorte de réciproque: l'existence d'un h tel que g=h∘f, même sans hypothèse sur son domaine, implique que  ∼  f <  ∼ g. Finalement, pour une surjection f fixée, l'injection GF ∋ h ⟼ h∘f a pour image l'ensemble des g ∈ GE tels que  ∼  f <  ∼ g. Sa restriction à l'ensemble des injections de F dans G a pour image {g ∈ GE|  ∼  f= ∼ g}.

Notation. Soit g ∈ FE et R une relation d'équivalence sur E telle que R <  ∼ g. On note alors g/R l'application de domaine E/R définie par g=(g/R)∘R←. Si R= ∼ g on l'appellera l'injection canonique de E/ ∼ g dans F.

2.7. Axiome du choix

Théorème et définition. Pour tout ensemble X fixé, les énoncés suivants sont équivalents, et pareillement nommés axiome du choix de base X et notés ACX :
1) Tout produit indexé par X d'ensembles non vides est non vide
2) Pour tout ensemble E et toute relation R entre X et E,
(∀x ∈ X,∃y ∈ E, R(x,y))⇒(∃f ∈ EX, ∀x ∈ X, R(x,f(x)))
3) Pour toute application g d'image X, ∃f ∈ (Domg)X, g∘f=IdX.
1)⇒2) est immédiat; 2)⇒1) en définissant E comme union de la famille.
On a 2)⇒3) en définissant R(x,y) ⇔ (x=g(y)). Autrement dit on a 1)⇒3) en prenant la famille g• d'ensembles non vides. Réciproquement, on montre 3)⇒1) en prenant la somme de la famille, ou encore on montre 3)⇒2) à l'aide du graphe de R. ∎


Axiome du choix (AC). Pour tout ensemble X, ACX.
Déjà, ACX est vrai pour tout ensemble fini X, comme on peut facilement le voir à "la main" et on le démontrera dans le texte suivant.
Mais, les logiciens professionnels ont réussi à démontrer que l'axiome du choix est indécidable, c'est-à-dire ni démontrable ni réfutable. Précisément, que s'il existe un univers de la théorie des ensembles dans lequel il est vrai, alors il en existe aussi un dans lequel il est faux (ACX devient faux pour certains ensembles infinis X), et inversement. Comment est-ce possible ? Nous avons prévenu que les indécidabilités venaient du fait que pour deux ensembles X et Y où X est infini, rien ne peut garantir que ce qui sert d'ensemble puissance YX dans un univers donné, soit le vrai. Autrement dit, il pourrait toujours y avoir des applications de X dans Y qui n'appartiennent pas à cet univers, mais seulement à un autre univers plus grand. La véracité d'une formule énoncée en termes d'ensembles puissance pourrait n'être qu'une illusion due à sa restriction à l'univers donné. En fabriquant des petits univers ainsi illusoires, certains énoncés comme l'axiome du choix peuvent y apparaître de valeur vraie ou faux contraire à ce qu'ils seraient dans une supposée "réalité" extérieure.
Ainsi l'axiome du choix peut sembler faux dans un univers U, alors qu'il serait vrai dans un univers plus vaste U′, du fait que les éléments dans U′ d'un certain produit d'ensembles non vides, n'apparaissent pas dans U. Et au contraire il peut sembler vrai dans un univers U, alors qu'il est faux dans un univers plus vaste U′, parce qu'une certaine famille d'ensembles non vides dans U′, dont le produit est vide, n'existe simplement pas dans U. Mais les détails de ces constructions sont bien trop complexes pour être abordés ici.
En pratique, comme l'axiome du choix est conforme à l'intuition et plus facile à affirmer qu'à nier (comme il y a plusieurs manières de le nier), la majorité des travaux de mathématiques sur les questions qui en dépendent le supposent vrai. Cependant, bien des questions n'en dépendent pas, ou se satisfont d'une version plus faible (notamment ACℕ).
Pour terminer, citons d'autres équivalents simples de l'axiome du choix:

Théorème. Les énoncés suivants sont équivalents à l'axiome du choix:
4) Pour tous ensembles E, F, G et toute g ∈ GF surjective, {g∘f|f ∈ FE}=GE.
5) Pour tout ensemble E et toute relation d'équivalence R sur E, ∃A ⊂ E, ∀x ∈ E,∃!y ∈ A, xRy.
6) Pour tout ensemble E d'ensembles, ∅ ∉ E⇒(∏A ∈ EA) ≠ ∅.
Preuves:
ACE⇒4) par ∀h ∈ GE,(∀x ∈ E, ∃y ∈ F, g(y)=h(x))⇒(∃f ∈ FE, ∀x ∈ E, g(f(x))=h(x))
ACG⇒4) par ∃i ∈ FG,g∘i=IdG et ∀h ∈ GE, i∘h ∈ FE et g∘i∘h=h.
4)⇒3) : avec E=G, par IdE ∈ {g∘f|f ∈ FE}.
3)⇒5) : ∃g ∈ EE/R,R←∘g=IdE/R de sorte que A=Img convient.
5)⇒3) : soit E=Domg, et A ⊂ E tel que ∀x ∈ E,∃! y ∈ A, g(x)=g(y). Alors g|A est bijective de A sur X, et son inverse f ∈ AX ⊂ EX vérifie g∘f=g|A∘f=IdX.
1)⇒6) : il suffit de prendre la famille IdE.
6) ⇒1) : soit (Ai)i ∈ I une famille d'ensembles non vides, et soit E son image {Ai|i ∈ I}. On a alors ∅ ∉ E, donc il existe f ∈ ∏A ∈ EA. Alors (f(Ai))i ∈ I ∈ ∏i ∈ IAi. ∎

Les prochains textes sur la théorie des ensembles s'appuieront sur l'axiome des parties mais non pas l'axiome du choix (sauf cas particuliers explicites). Non que le premier soit plus vrai (on pourrait même estimer le contraire), seulement il sera le seul des deux à y être indispensable.

File translated from TEX by TTH, version 3.67.
On 11 Feb 2009, 23:38.
Retour au sommaire