On dit qu'un ensemble non vide E est fini s'il existe n∈N∗ et une bijection de [[1,n]] sur E. Dans ce cas, l'entier n est unique et est appelé cardinal de E : on le note card E, ∣E∣ ou encore #E. Par convention, ∅ est fini et card ∅=0.
Remarque
Plus prosaïquement, le cardinal est le nombre d'éléments d'un ensemble.
Proposition
Deux ensembles finis ont même cardinal si et seulement si il existe une bijection de l'un sur l'autre.
Démonstration
Montrons les deux implications.
(⇒) Supposons que cardE=cardF=n. Par la Définition 1.1, il existe une bijection φ:[[1,n]]→E et une bijection ψ:[[1,n]]→F. Alors ψ∘φ−1:E→F est une composée de bijections, donc une bijection de E sur F.
(⇐) Supposons qu'il existe une bijection f:E→F. Montrons que cardE=cardF. Par la Définition 1.1, il existe un entier n∈N∗ et une bijection φ:[[1,n]]→E. Alors f∘φ:[[1,n]]→F est une bijection, ce qui montre, par définition, que cardF=n=cardE.
Le cas E=∅ : si cardE=cardF=0, alors E=F=∅ et l'application vide est la seule bijection de E sur F.
Méthode—Déterminer le cardinal d'un ensemble
Pour déterminer le cardinal d'un ensemble, il suffit de le mettre en bijection avec un ensemble de cardinal connu.
Proposition
Soit E un ensemble fini et A une partie de E. Alors A est fini et card A≤card E. Il y a égalité si et seulement si A=E.
Démonstration
Soit E un ensemble fini de cardinal n=cardE et A⊆E.
A est fini. Par la Définition 1.1, il existe une bijection φ:[[1,n]]→E. Notons I=φ−1(A)⊆[[1,n]]. La restriction φ∣I:I→A est alors bijective. Or toute partie I de [[1,n]] est finie (elle est en bijection avec [[1,cardI]] en réordonnant ses éléments). Donc A est fini et cardA=cardI≤n=cardE.
Cas d'égalité. Si A=E, alors clairement cardA=cardE. Réciproquement, si cardA=cardE=n, alors A⊆E et ∣A∣=n impliquent A=E (on ne peut pas avoir une partie stricte de [[1,n]] de cardinal n).
1.2. Opération sur les ensembles finis
Proposition
Soient E et F deux ensembles finis. Alors E∪F et E∩F sont finis et card(E∪F)=card E+card F−card(E∩F)
1.3. Applications entre ensembles finis
Proposition
Soit f:E→F.
Si f est injective et F fini, alors E est fini et card E≤card F.
Si f est surjective et E fini, alors F est fini et card E≥card F.
Posons nE=cardE, nF=cardF, n∩=card(E∩F). On remarque que {E∖F,E∩F,F∖E} est une partition de E∪F (les trois ensembles sont disjoints deux à deux et leur réunion est E∪F).
Par la Proposition 1.4 appliquée à cette partition :card(E∪F)=card(E∖F)+card(E∩F)+card(F∖E).De même, {E∖F,E∩F} est une partition de E, donc par la Proposition 1.4 :cardE=card(E∖F)+card(E∩F),d'où card(E∖F)=cardE−card(E∩F).
De même, card(F∖E)=cardF−card(E∩F).
En substituant :card(E∪F)=(cardE−n∩)+n∩+(cardF−n∩)=cardE+cardF−card(E∩F).
On veut montrer par récurrence sur n≥2 que pour tout n-uplet (A1,…,An) d'ensembles finis :card(i=1⋃nAi)=k=1∑n(−1)k−11≤i1<⋯<ik≤n∑card(Ai1∩⋯∩Aik).Initialisation (n=2) : C'est la Proposition 1.3 : card(A1∪A2)=card(A1)+card(A2)−card(A1∩A2). ✓
Hérédité : Supposons la formule vraie au rang n−1 (pour n≥3). On pose B=A1∪⋯∪An−1. Par la Proposition 1.3 :card(i=1⋃nAi)=card(B∪An)=card(B)+card(An)−card(B∩An).Or B∩An=(A1∪⋯∪An−1)∩An=(A1∩An)∪⋯∪(An−1∩An).
Par hypothèse de récurrence appliquée aux n−1 ensembles A1,…,An−1 (pour card(B)) et aux n−1 ensembles A1∩An,…,An−1∩An (pour card(B∩An)), on obtient :card(B)=k=1∑n−1(−1)k−11≤i1<⋯<ik≤n−1∑card(Ai1∩⋯∩Aik),card(B∩An)=k=1∑n−1(−1)k−11≤i1<⋯<ik≤n−1∑card(Ai1∩⋯∩Aik∩An).En combinant, les termes faisant intervenir An dans −card(B∩An) contribuent avec des signes (−1)k, ce qui complète exactement la somme jusqu'au rang n avec les bons signes.
Ainsi la formule est vraie au rang n, ce qui achève la récurrence. □
Définition—Partition
Soit E un ensemble (pas nécessairement fini) et (Ai)i∈I une famille de parties de E. On dit que (Ai)i∈I est une partition de E si
les Ai sont non vides;
les Ai sont disjoints deux à deux;
E=⋃i∈IAi.
On note alors E=⨆i∈IAi.
Remarque
Il arrive de parler de partition même si certaines des parties en question sont vides.
Proposition
Soit E un ensemble fini et (Ai)1≤i≤n une partition de E. Alors card E=∑i=1ncard Ai.
Démonstration
On raisonne par récurrence sur n, le nombre de parties de la partition.
Initialisation (n=1). La partition est (A1) avec E=A1, donc cardE=cardA1. C'est immédiat.
Hérédité. Supposons le résultat vrai pour une partition en n parties. Soit (Ai)1≤i≤n+1 une partition de E. Posons E′=⨆i=1nAi. Alors (A1,…,An) est une partition de E′, donc par hypothèse de récurrence :cardE′=i=1∑ncardAi.De plus, {E′,An+1} est une partition de E en deux parties disjointes. Par la Proposition 1.3 appliquée à E′∪An+1=E avec E′∩An+1=∅ :cardE=cardE′+cardAn+1=i=1∑ncardAi+cardAn+1=i=1∑n+1cardAi.Le résultat est établi par récurrence.
Remarque
La relation est vraie certaines des parties sont vides.
Méthode—Déterminer le cardinal d'un ensemble
Pour déterminer le cardinal d'un ensemble, il suffit de le partitionner en parties de cardinaux connus.
Corollaire
Soit A une partie d'un ensemble fini E. On note Aˉ son complémentaire. Alors card(Aˉ)=card(E)−card(A)
Démonstration
On observe que {A,Aˉ} est une partition de E : en effet, A et Aˉ=E∖A sont disjoints par définition du complémentaire, non vides (si l'un était vide, l'égalité de cardinal serait triviale), et leur réunion est E.
Par la Proposition 1.4 appliquée à cette partition en deux parties :cardE=cardA+card(Aˉ).On en déduit immédiatement :card(Aˉ)=cardE−cardA.
Proposition
Soient E et F deux ensembles finis. Alors E×F est fini. De plus, card(E×F)=card E×card F.
Démonstration
Posons p=cardE et q=cardF. Par la Définition 1.1, il existe des bijections φ:[[1,p]]→E et ψ:[[1,q]]→F.
L'applicationΦ:[[1,p]]×[[1,q]]→E×F,(i,j)↦(φ(i),ψ(j))est bijective (elle est injective car φ et ψ le sont, et surjective car tout (x,y)∈E×F s'écrit (φ(i),ψ(j)) avec i=φ−1(x) et j=ψ−1(y)).
Or l'ensemble [[1,p]]×[[1,q]] a pq éléments (on peut le mettre en bijection avec [[1,pq]] par l'ordre lexicographique). Donc E×F est fini etcard(E×F)=pq=cardE×cardF.
Corollaire
Soient E1,…,Ep des ensembles finis. Alors card (∏i=1pEi)=∏i=1pcard(Ei)
Démonstration
On procède par récurrence sur p≥1.
Initialisation (p=1).∏i=11Ei=E1 est fini et cardE1=∏i=11cardEi. C'est immédiat.
Hérédité. Supposons le résultat vrai au rang p. On ai=1∏p+1Ei=(i=1∏pEi)×Ep+1.Par hypothèse de récurrence, ∏i=1pEi est fini et card(∏i=1pEi)=∏i=1pcardEi. Par la Proposition 1.5 :card(i=1∏p+1Ei)=card(i=1∏pEi)×cardEp+1=i=1∏pcardEi×cardEp+1=i=1∏p+1cardEi.Le résultat est établi par récurrence.
Proposition
Soient E et F deux ensembles finis. Alors FE est fini. De plus, card(FE)=(card F)card E.
Démonstration
Posons p=cardE et q=cardF. Par la Définition 1.1, il existe des bijections φ:[[1,p]]→E et ψ:[[1,q]]→F.
Tout élément de FE est une application de E dans F. Via φ, on peut identifier FE avec l'ensemble des applications de [[1,p]] dans F. Plus précisément, l'applicationΦ:FE→F[[1,p]],f↦f∘φest bijective (de bijection réciproque g↦g∘φ−1).
Or une application de [[1,p]] dans F est entièrement déterminée par les p valeurs (f(1),…,f(p))∈Fp. Par le Corollaire 1.2 (produit cartésien de p copies de F) :card(F[[1,p]])=card(Fp)=(cardF)p=qp.Donc FE est fini et card(FE)=(cardF)cardE.
Proposition
Soit E un ensemble fini. Alors l'ensemble des parties de E noté P(E) est également fini et card P(E)=2card E.
Démonstration
Soit E un ensemble fini de cardinal n. Pour toute partie A⊆E, notons 1A:E→{0,1} sa fonction indicatrice, définie par 1A(x)=1 si x∈A et 1A(x)=0 sinon.
L'applicationΦ:P(E)→{0,1}E,A↦1Aest bijective : elle est injective (si 1A=1B alors A=B) et surjective (pour f∈{0,1}E, la partie A=f−1({1}) vérifie 1A=f).
Par la Proposition 1.1, cardP(E)=card({0,1}E).
Or, par la Proposition 1.6 appliquée à F={0,1} (de cardinal 2) et E (de cardinal n) :card({0,1}E)=2n=2cardE.Donc P(E) est fini et cardP(E)=2cardE.
Démonstration
Montrons les deux points séparément.
(i) f injective, F fini ⇒E fini et cardE≤cardF.
Posons n=cardF. Comme f est injective, f induit une bijection de E sur Imf⊆F. Par la Proposition 1.2, Imf est fini et card(Imf)≤cardF=n. Comme E est en bijection avec Imf, par la Proposition 1.1, E est fini et cardE=card(Imf)≤n=cardF.
(ii) f surjective, E fini ⇒F fini et cardE≥cardF.
Posons p=cardE. Comme f est surjective, pour tout y∈F, la fibre f−1({y}) est non vide. Les fibres (f−1({y}))y∈F forment une partition de E (elles sont deux à deux disjointes, non vides, et leur réunion est E). Par la Proposition 1.4 :p=cardE=y∈F∑card(f−1({y}))≥y∈F∑1=cardF.Ceci implique en particulier que F est fini (car cardF≤p<+∞) et cardE≥cardF.
Corollaire
Soit f:E→F. Si E est fini, alors Im f est fini et card(Im f)≤card E.
Démonstration
L'application f:E→F induit, par restriction du codomaine, une application surjective f~:E→Imf (par définition de l'image). Comme E est fini et f~ est surjective, la Proposition 1.8 (ii) donne que Imf est fini et card(Imf)≤cardE.
Encadré—Principe des tiroirs de Dirichlet
Supposons que l'on veuille ranger n paires de chaussettes dans p tiroirs. Si n>p, il est évident qu'un des tiroirs comportera plus d'une paire de chaussettes. On peut formaliser cette remarque de la manière suivante. Si on note E l'ensemble des paires de chaussettes, F l'ensemble des tiroirs et f l'application qui à une paire de chaussettes associe le tiroir dans laquelle elle se trouve, alors la remarque précédente signifie que f n'est pas injective.
Application
Soit n∈N∗. On se donne n+1 réels de l'intervalle [0,1[. Montrer que deux d'entre eux sont à une distance strictement inférieure à n1 l'un de l'autre.
Correction
On dispose de n+1 réels x0,x1,…,xn∈[0,1[. On veut montrer que deux d'entre eux sont à distance strictement inférieure à n1.
Application du principe des tiroirs (encadré du cours) :
On partitionne [0,1[ en n intervalles de longueur n1 :Ik=[nk−1,nk[,k=1,2,…,n.Ces n intervalles forment une partition de [0,1[ (ils sont disjoints et leur réunion est [0,1[).
On répartit les n+1 réels x0,…,xn dans ces n intervalles (« tiroirs »). Par le principe des tiroirs (encadré du cours) : puisqu'on place n+1 objets dans n tiroirs, au moins un tiroir contient au moins deux objets.
Donc il existe i=j tels que xi et xj appartiennent au même intervalle Ik. Puisque Ik est de longueur n1, on a :∣xi−xj∣<n1.Conclusion : parmi tout n+1 réels de [0,1[, il en existe deux dont la distance est strictement inférieure à n1. □
Proposition
Soit f:E→F où E et F sont des ensembles finis de même cardinal. Les propositions suivantes sont équivalentes :
f est bijective;
f est surjective;
f est injective.
Démonstration
Posons n=cardE=cardF. Il suffit de montrer le cycle d'implications : (i) ⇒ (ii), (ii) ⇒ (iii), (iii) ⇒ (i).
(i) ⇒ (ii). Toute bijection est en particulier surjective. Immédiat.
(ii) ⇒ (iii). Supposons f surjective. Par la Proposition 1.8 (ii), cardE≥cardF, soit n≥n. Les fibres (f−1({y}))y∈F forment une partition de E (par définition de f surjective), donc par la Proposition 1.4 :n=y∈F∑card(f−1({y}))≥cardF=n.L'égalité impose que toutes les fibres sont de cardinal 1, c'est-à-dire f est injective.
(iii) ⇒ (i). Supposons f injective. Par la Proposition 1.8 (i), cardE≤cardF, soit n≤n. Comme f est injective, f induit une bijection de E sur Imf, donc card(Imf)=n=cardF. Par la Proposition 1.2, Imf⊆F et card(Imf)=cardF impliquent Imf=F. Donc f est surjective, et comme elle est aussi injective, elle est bijective.
Proposition—Lemme des bergers
Soit f:E→F où E et F sont des ensembles finis. On suppose qu'il existe r∈N tel que card (f−1({y}))=r pour tout y∈F. Alors card E=rcard F.
Démonstration
Les fibres (f−1({y}))y∈F forment une partition de E : elles sont deux à deux disjointes, leur réunion est E (car f est définie sur E tout entier), et chacune est non vide (car pour tout y∈F, card(f−1({y}))=r≥1 puisque r∈N et si r=0 alors F serait vide, ce qui est trivial).
Par la Proposition 1.4 appliquée à cette partition :cardE=y∈F∑card(f−1({y}))=y∈F∑r=r×cardF.
