Entiers naturels, denombrements

Table des mati`eres

I Entiers naturels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
I.1 Les proprietes admises de lensemble N . . . . . . . . . . . . . . . . . . . . . . 2
I.2 Le principe de recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
I.3 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I.4 Raisonnement par recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
I.5 Pratique du raisonnement par recurrence . . . . . . . . . . . . . . . . . . . . . 5
II Ensembles nis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
II.1 Cardinal dun ensemble ni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
II.2 Proprietes des cardinaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
III Denombrements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
III.1 Applications entre ensembles nis . . . . . . . . . . . . . . . . . . . . . . . . . 13
III.2 Arrangements et combinaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
III.3 Bin ome de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 1
Entiers naturels, denombrements Partie I : Entiers naturels
I Entiers naturels
I.1 Les proprietes admises de lensemble N
Conformement au programme, lensemble N = 0, 1, 2, . . . est suppose connu, ainsi que ses proprietes
(operations + et , relation dordre). Voici quelques-unes de ces proprietes.
Addition
Loperation + est associative : (m, n, p) N
3
, m + (n + p) = (m + n) + p.
Elle est + est commutative : (m, n) N
2
, m + n = n + m.
0 est element neutre : n N, n + 0 = n.
On note N

lensemble N prive de 0.
Tout element de N est simpliable pour laddition :
(m, n, p) N
3
, m + p = n + p m = n.
(m, n) N
2
, m + n = 0 m = n = 0.
Multiplication
Loperation est associative : (m, n, p) N
3
, m(np) = (mn)p.
Elle est commutative : (m, n) N
2
, mn = nm.
Elle est distributive par rapport ` a la loi + : (m, n, p) N
3
, m(n + p) = mp + mp.
1 est element neutre : n N, n1 = n.
Tout element non nul de N est simpliable pour le produit :
(m, n) N
2
, p N

, mp = np m = n.
Relation dordre
On pose : (m, n) N
2
, m n p N, m + p = n.
Cest une relation dordre total sur N (ca signie que deux elements m et n de N sont toujours
comparables : on a toujours m n ou n m)
Lentier 0 est le minimum de N pour cette relation dordre.
Demonstration:
Cela resulte evidemment de legalite 0 +n = n, valable pour tout n de N
Pour tous entiers m, n, p, si m n alors
_
m + p n + p
mp np
Remarques
Si m n, lentier p tel que m + p = n est note n m.
Loperation dierence nest pas partout denie sur N (lentier p nexiste que si m n) et nest
pas tr`es interessante (pas commutative, ni associative, pas delement neutre).
On note indieremment n m et m n (mais plus souvent m n).
On note m < n pour ecrire : (m n) et (m ,= n).
Soit (m, n) dans N
2
. On pose : [[m, n]] = p N, m p n (ensemble vide si n < m).
On mn = 1 m = n = 1, et on a mn = 0 (m = 0) ou (n = 0).
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 2
Entiers naturels, denombrements Partie I : Entiers naturels
Si a
m
, a
m+1
, . . . , a
n
sont dans N, on notera
n

j=m
a
j
, ou

mjn
a
j
, plut ot que a
m
+a
m+1
+. . . +a
n
.
De meme on notera
n

j=m
a
j
, ou

mjn
a
j
plut ot que a
m
a
m+1
. . . a
n
.
Par convention, dans le cas o` u n < m on pose
n

j=m
a
j
= 0 et
n

j=m
a
j
= 1.
Factorielle
Pour tout n de N, on note n! =
n

k=1
k (et en particulier 0! = 1)
Puissances dun entier
Pour tous m, n de N, on pose m
n
=
n

j=1
m (et en particulier m
0
= 1).
On a alors les proprietes suivantes : m
n
m
p
= m
n+p
, (m
n
)
p
= m
np
, (mn)
p
= m
p
n
p
.
I.2 Le principe de recurrence
Dans N, on admet en particulier la propriete fondamentale :
Toute partie non vide de N poss`ede un plus petit element
Remarques et exemples
Soit n dans N. Lensemble A = m N, m > n est non vide.
Le plus petit element de A est bien s ur n + 1 (cest le successeur de n).
Autrement dit, pour tout n de N, on a : m > n m n + 1.
Soit n dans N

. Lensemble A des m de N tel que m < n est non vide (il contient 0).
Le plus grand element de cet ensemble est bien s ur n 1 (cest le predecesseur de n).
Autrement dit, pour tout n de N, on a : m < n m n 1.
La propriete du plus petit element poss`ede deux corollaires tr`es importants :
Principe de recurrence
Soit A une partie de N, contenant 0.
On suppose que : n A, n + 1 A. Alors A = N.
Autrement dit, si une partie A de N contient 0 et si elle contient le successeur de chacun de ses
elements, alors cette partie A est egale ` a N tout entier.
Demonstration:
On raisonne par labsurde, donc on suppose que le complementaire B de A dans N nest pas vide.
Soit b le plus petit element de B (on utilise laxiome du plus petit element).
On trouve b 1 (car 0 est dans A, donc pas dans B, et b est dans B).
On peut donc parler de lentier a = b 1, et a est dans A.
Par hypoth`ese sur A, on en deduit que b = a + 1 est dans A, et cest absurde.
Plus grand element dune partie non vide majoree
Toute partie majoree non vide de N poss`ede un plus grand element
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 3
Entiers naturels, denombrements Partie I : Entiers naturels
Demonstration:
Soit A une partie majoree non vide de N. Soit B lensemble des majorants de A.
Lensemble B est une partie non vide de N donc poss`ede un plus petit element b.
Pour tout element a de A, on a linegalite a b.
Si b = 0, alors necessairement A = 0 et A poss`ede bien un plus grand element...
On suppose donc b > 0. Par denition de b, lentier b 1 nest pas dans B.
Il existe donc un element a de A tel que b 1 < a.
On a alors b 1 < a b, ce qui implique b = a : lentier b est donc dans A.
Ainsi b est un majorant de A qui appartient `a A : cest lelement maximum de A
I.3 Division euclidienne
Denition
On dit que n divise m (ou que m est un multiple de n) si : q N, m = nq.
On note alors n [ m. On denit ainsi une relation dordre partiel sur N.
Pour cette relation, 1 est le minimum de N.
Demonstration:
Pour tout entier n, on a n = n 1 donc
_
n [ n (la relation est reexive)
1 [ n (lentier 1 est minimum)
La relation est transitive car
_
n [ n

[ n

_
n

= nq
n

= n

= n(qq

)n [ n

.
_
n [ m
m [ n

_
m = nq
n = mp
n = n(qp)
_
n = 0 ou
pq = 1

_
m = n = 0 ou
p = q = 1
m = n
Cest un ordre partiel car par exemple 2 et 3 ne sont pas comparables
Denition
Soit (m, n) dans N N

.
Il existe un unique couple (q, r) de N
2
tel que : (m = nq + r) et (r n 1)
Le passage du couple (m, n) au couple (q, r) sappelle division euclidienne de m par n.
Dans cette division, m est le dividende, n le diviseur, q le quotient, et r le reste.
Demonstration:
Soit A le sous-ensemble de N

forme des entiers k tels que m < kn.

Notons que k = m+ 1 convient toujours car (m+ 1)n m = m(n 1) +n n 1.
Lensemble A etant non vide, il a un minimum q

1. Notons q

= q + 1 (q N).
Par denition
_
q / A
q + 1 A
cest-`a-dire
_
qn m
m < (q + 1)n
Ainsi r = mnq est un entier naturel strictement inferieur `a n.
On a donc trouve un couple (q, r) N
2
tel que m = nq +r, avec r n 1.
Supposons alors quon ait aussi m = nq

+r

, avec (q

, r

) N
2
et r

n 1.
On doit montrer que les couples (q, r) et (q

, r

) sont egaux.
Sans perdre de generalite, on peut supposer q

q.
Par dierence on trouve n(q

q) = r r

r < n. La seule possibilite est q

q = 0.
On trouve donc q

= q, puis r

= r. Le couple (q, r) obtenu plus haut est donc unique

Remarque
n [ m (m = n = 0) ou (n ,= 0 et le reste dans la division de m par n est nul).
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 4
Entiers naturels, denombrements Partie I : Entiers naturels
I.4 Raisonnement par recurrence
Soit T un predicat, de referentiel N.
Rappelons quon ecrit T(n) pour dire T(n) est vraie.
Recurrence simple (ou faible)
_
On suppose T(0) et, pour tout entier n, T(n) T(n + 1).
Alors, pour tout entier n, T(n).
Demonstration:
Notons A lensemble des entiers n de N pour lesquels T(n) est vraie.
Les deux hypoth`eses signient que 0 est dans A et que : n A, n + 1 A.
Laxiome de recurrence donne A = N : la propriete T est donc vraie pour tout n de N
Voici donc comment montrer quune propriete T(n) est vraie pour tous les entiers naturels :
On verie que lentier 0 satisfait ` a la propriete : cest le pas initial de la recurrence.
On se donne ensuite un entier n, pour lequel on suppose que T(n) est vraie.
Cest lhypoth`ese de recurrence.
On demontre alors que T(n + 1) est vraie (cest le passage du rang n au rang n + 1).
On exprime limplication T(n) T(n + 1) en disant que la propriete T est hereditaire.
On conclut en annoncant que, par recurrence, la propriete est vraie pour tout entier n.
I.5 Pratique du raisonnement par recurrence
Le raisonnement de recurrence admet plusieurs variantes, dont celle-ci, qui ne di`ere de loriginal
que par le pas initial qui peut se situer en n
0
(entier naturel) plutot quen 0 :
Soit n
0
un entier naturel.
_

_
On suppose T(n
0
).
On suppose egalement que : n n
0
, T(n) T(n + 1).
Alors, n n
0
, T(n).
Une autre variante reside dans la mani`ere davancer dans la recurrence.
Il arrive en eet que lhypoth`ese T(n) seule soit insusante pour demontrer T(n + 1).
Le cas le plus frequent est celui de la recurrence double, o` u le pas initial et lhypoth`ese de recurrence
portent sur deux entiers consecutifs.
Recurrence de pas double
Soit n
0
un entier naturel.
_

_
On suppose T(n
0
) et T(n
0
+ 1).
On suppose egalement que : n n
0
, (T(n) et T(n + 1)) T(n + 2).
Alors, n n
0
, T(n).
Il reste ` a voir une derni`ere version du raisonnement par recurrence. Pour demontrer T(n + 1), on
peut en eet utiliser tout ou partie des hypoth`eses T(n
0
), T(n
0
+ 1), . . ., et T(n).
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 5
Entiers naturels, denombrements Partie II : Ensembles nis
Recurrence forte
_

_
Soit n
0
un entier naturel. On suppose T(n
0
).
On suppose aussi que : n n
0
, (T(n
0
), T(n
0
+ 1), . . . , T(n)) T(n + 1).
Alors, n n
0
, T(n).
Voici enn quelques conseils pour reussir un raisonnement par recurrence :
Ne pas oublier le pas initial (la propriete est souvent triviale, mais on doit la prouver).
Ne pas ecrire : Supposons que pour tout n, T(n). Montrons T(n + 1) alors quil faut ecrire :
Soit n un entier naturel ; on suppose T(n). Montrons T(n + 1).
Bien articuler le pas initial et lhypoth`ese de recurrence.
Si le pas initial est par exemple n
0
, et si on veut demontrer T(n) T(n + 1), alors n doit etre
superieur ou egal `a n
0
. On peut tout ` a fait prouver T(n1) T(n), mais dans ce cas n doit etre
strictement superieur ` a n
0
.
Bien separer le passage du rang n au rang n + 1, o` u lentier n est xe, et la conclusion nale
(qui est obligatoire, et qui doit porter sur tous les entiers naturels n).
II Ensembles nis
II.1 Cardinal dun ensemble ni
Pour tout entier naturel, on note E
n
= m N, 1 m n. En particulier E
0
= .
Dans les trois enonces suivants, n et p sont des entiers naturels.
Proposition
Il existe une injection de E
n
dans E
p
si et seulement si n p.
Il existe une surjection de E
n
sur E
p
si et seulement si n p.
Il existe une bijection de E
n
sur E
p
si et seulement si n = p.
Demonstration:
Si n p, on denit une injection f de E
n
dans E
p
en posant : k E
n
, f(k) = k.
Reciproquement, prouvons que lexistence dune injection de E
n
dans E
p
implique n p.
On va le montrer par recurrence sur n. Si n = 1 cest evident puisque par hypoth`ese 1 p.
Soit n dans N

. Supposons la propriete demontree au rang n.

On suppose alors quil existe une injection f : E
n+1
E
p
: il faut prouver n + 1 p.
Tout dabord p > 1, sinon f ne serait pas injective (on aurait f(1) = f(2) = 1.)
Si f(n + 1) < p, soit g la bijection de E
p
sur lui-meme qui echange f(n + 1) et p en laissant xe tous
les autres. Si au contraire f(n + 1) = p, soit g lapplication identite de E
p
.
Par construction h = g f est une injection de E
n+1
dans E
p
telle que h(n + 1) = p.
Sa restriction `a E
n
est donc une injection de E
n
dans E
p1
.
Lhypoth`ese de recurrence nous donne alors n p 1 donc n + 1 p.
On a ainsi prouve la propriete au rang n + 1, ce qui ach`eve la recurrence
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 6
Entiers naturels, denombrements Partie II : Ensembles nis
Demonstration:
Si n p, lapplication f : E
n
E
p
denie par f(k) = min(k, p) est surjective.
Reciproquement supposons quil existe une surjection f de E
n
sur E
p
.
On denit alors une application g de E
p
dans E
n
en associant `a tout j de E
p
lun quelconque (il y en
a toujours au moins un) des elements k de E
n
tels que f(k) = j.
Par construction, lapplication f g est lidentite de E
p
.
Puisque f g est injective, il en est de meme de g.
Lexistence dune injection g de E
p
dans E
n
implique donc p n (proposition precedente.)
Demonstration:
Si n = p, lapplication identite est une bijection de E
n
sur E
p
.
Reciproquement cest une simple consequence des deux proprietes precedentes
Proposition
Soit n un entier naturel non nul, et f une application de E
n
dans lui-meme.
Alors : f est bijective f est injective f est surjective.
Demonstration:
Il sut de verier lequivalence entre f injective et f surjective.
Soit f une injection de E
n
dans lui-meme.
Supposons par labsurde que f ne soit pas surjective.
Alors il existe k de E
n
qui ne poss`ede pas dantecedent par f.
On remarque que cette situation implique necessairement n 2.
Si k < n, on note g la bijection de E
n
sur lui-meme qui echange k et n et laisse xe tous les autres. Si
k = n, on prend pour g lidentite de E
n
.
Par construction g f est une injection de E
n
dans E
n1
, ce qui est absurde.
Conclusion : si f est injective de E
n
dans lui-meme, alors elle est bijective.
Soit f une surjection de E
n
sur lui-meme.
On denit une application g de E
n
dans lui-meme en associant `a tout j de E
n
lun quelconque (il y en
a toujours au moins un) des elements k de E
n
tels que f(k) = j.
Par construction, lapplication f g est lidentite de E
n
.
Puisque f g est injective, il en est de meme de g.
La demonstration precedente nous apprend alors que g est bijective.
Puisque f g est lidentite de E
n
, il en decoule f = g
1
. Lapplication f est donc bijective.
Conclusion : si f est surjective de E
n
sur lui-meme, alors elle est bijective
On peut maintenant donner la denition dun ensemble ni.
Proposition
Un ensemble non vide E est dit ni sil existe une bijection de E
n
sur E, avec n 0.
Lentier n, sil existe, est unique et est appele le cardinal de E. On note n = card (E).
En particulier card () = 0. Un ensemble non ni est dit inni.
Demonstration:
Lunicite de lentier n resulte du fait que sil existe une bijection f de E
n
sur E et une bijection g de E
p
sur E alors g
1
f est une bijection de E
n
sur E
p
, ce qui implique n = p
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 7
Entiers naturels, denombrements Partie II : Ensembles nis
Remarques
card (E) represente bien s ur le nombre delements de E.
Dans la denition, on aurait pu aussi bien dire : sil existe une bijection de E sur E
n

Si m n, lintervalle [[m, n]] est ni de cardinal n m + 1. En eet lapplication f denie par

f(k) = k m + 1 est bijective de [[m, n]] sur E
nm+1
.
Sil existe une bijection f de E ni sur F, alors F est ni et card (E) = card (F).
Demonstration:
Si E = alors F = . Sinon, soit g une bijection de E
n
sur E, avec n = card (E) 1.
Alors f g est une bijection de E
n
sur F. Lensemble F est donc ni de cardinal n
On peut caracteriser les parties nies de N :
Proposition
Une partie A non vide de N est nie elle est majoree. En particulier N est inni.
Demonstration:
Montrons par recurrence que toute partie A de N, de cardinal n 1, est majoree.
Si n = 1 : A qui est en bijection avec E
1
= 1 et est donc un singleton est majore...
Supposons la propriete vraie pour un entier n 1 donne, et soit A N de cardinal n + 1.
Soit f une bijection de E
n+1
sur A, et soit a = f(n + 1).
La restriction de f `a E
n
est une bijection de E
n
sur B = A a.
Lensemble B est de cardinal n donc majore. Soit m un majorant de B.
Pour tout x de A, on a x max(a, m). Donc A est majore, ce qui ach`eve la recurrence.
Montrons par recurrence sur n que si A [[0, n]], alors A est ni et card (A) n + 1.
Si n = 0, alors A = 0. Donc A est ni et card (A) = 1.
Supposons la propriete vraie pour n 0 donne. Soit A une partie de [[0, n + 1]].
Il faut montrer que A est nie et que card (A) n + 2.
Si A [[0, n]], on applique lhypoth`ese de recurrence : card (A) n + 1 n + 2.
Sinon n + 1 est dans A. Si A = n + 1, il est ni de cardinal 1 n + 2...
Sinon lensemble B = A n + 1 est non vide et inclus dans [[0, n]].
Cet ensemble est donc ni et card (B) = p n + 1. Soit f une bijection E
p
sur B.
On prolonge f en une bijection g de E
p+1
sur A en posant f(p + 1) = n + 1.
Il en resulte que A est ni avec card (A) = p + 1 n + 2, ce qui ach`eve la recurrence.
N est inni car non majore (consequence de lexistence de lapplication succession)
On en deduit le resultat suivant :
Proposition
Soit E un ensemble ni. Soit A une partie de E.
Alors A est un ensemble ni et card (A) card (E).
Plus precisement, on a card (A) = card (E) si et seulement si A = E.
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 8
Entiers naturels, denombrements Partie II : Ensembles nis
Demonstration:
Soit A une partie de lensemble ni E. Si A = , il est ni et card (A) card (E) . . .
On suppose donc A non vide. Soit n = card (E) 1 et f une bijection de E sur E
n
.
Lapplication g : k g(k) = f(k) 1 est bijective de E dans [[0, n 1]].
Elle induit donc une bijection de A sur une partie non vide B = f(A) de [[0, n 1]].
La proposition precedente nous apprend que B est nie, et que card (B) n.
Or il y a une bijection de A sur B. Donc A est ni et card (A) = card (B) card (E).
Soit A E, avec E ni et card (A) = card (E). Il faut montrer que A = E.
Si A est vide, alors card (E) = card (A) = 0 : lensemble E est vide egalement.
Sinon soient n = card (A) = card (E) 1, f : E
n
A et g : E E
n
deux bijections.
Soit linjection canonique de A dans E, denie par (a) = a pour tout a de A.
Lapplication = g f est une injection de E
n
dans lui-meme.
On sait que cela implique que lapplication est bijective.
On en deduit que = g
1
f
1
est bijective et en particulier surjective.
Autrement dit tout element de E est un element de A. On a donc legalite A = E
Remarque
Si E est inni, il peut exister des bijections de E sur une partie stricte de E.
Par exemple, lapplication n 2n est une bijection de N sur lensemble des entiers pairs, et la
succession n n + 1 est une bijection de N sur N

.
Les deux propositions suivantes peuvent permettre de montrer quun ensemble est ni.
Proposition
Soit E un ensemble ni. Soit F un ensemble quelconque.
Soit f une application surjective de E sur F.
Alors F est ni, et card (F) card (E).
De plus on a card (F) = card (E) f est bijective.
Demonstration:
On denit une application g de F vers E en associant `a tout y de F lun quelconque (il en existe
toujours au moins un) des elements x de E tels que f(x) = y.
Par construction, lapplication f g est lidentite de F. En particulier g est injective.
Lapplication g realise donc une bijection de F sur son image A = g(F).
Puisque A est une partie de E, A est nie et card (A) card (E).
La bijection entre A et F montre que F est ni et card (F) = card (A) card (E).
Si f est injective, cest une bijection de E sur F. Donc card (F) = card (E).
Inversement : card (F) = card (E)card (A) = card (E) (notations precedentes.)
Or A E. Il en decoule A = E. Mais par construction deux elements distincts de A ont des images
distinctes par f. Il en decoule que f est injective
Proposition
Soient E et F deux ensembles.
Soit f une application injective de E dans F.
Si f(E) est ni, alors E est ni et card (E) = card (f(E)).
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 9
Entiers naturels, denombrements Partie II : Ensembles nis
Demonstration:
Cest evident puisque f realise une bijection de E sur f(E)
Voici des resultats tr`es proches des precedents. Il sagit plut ot ici de caracteriser lexistence dappli-
cations injectives, surjectives ou bijectives entre deux ensembles dont lun est ni.
Proposition
Soient E et F deux ensembles non vides, lensemble F etant ni.
Il existe une injection de E dans F (E est ni et card (E) card (F)).
Demonstration:
Soit f une injection de E dans F. Lensemble f(E) est une partie de lensemble ni F.
Ainsi f(E) est ni, puis E lui-meme car f est injective (proposition precedente.)
On a enn card (E) = card (f(E)) card (F).
Reciproquement, on suppose n m, avec n = card (E) et m = card (F).
Puisque n m, on sait quil existe une injection f de E
n
dans E
m
.
Soit g une bijection de E sur E
n
, et h une bijection de E
m
sur F.
Alors h f g est une injection de E dans F
Proposition
Soient E et F deux ensembles non vides, lensemble E etant ni.
Il existe une surjection de E sur F (F est ni et card (F) card (E)).
Il existe une bijection de E sur F (F est ni et card (E) = card (F)).
Demonstration:
Pour la premi`ere propriete, le sens direct a dej`a ete vu.
Reciproquement, on suppose m n, avec m = card (F) et n = card (E).
Puisque n m, on sait quil existe une surjection f de E
n
dans E
m
.
Soit g une bijection de E sur E
n
, et h une bijection de E
m
sur F.
Alors h f g est une surjection de E dans F.
On sait que si E est ni et si f : E F est bijective, alors F est ni et card (E) = card (F).
Reciproquement, si F est ni et si card (F) = card (E) = n 1, il existe une bijection f de E sur E
n
et une bijection g de E
n
sur F : g f est alors une bijection de E sur F
Proposition
Soient E et F deux ensembles nis non vides de meme cardinal.
Soit f une application de E vers F.
f est bijective f est injective f est surjective.
Demonstration:
On pose n = card (E). On utilise la proposition analogue avec E
n
`a la place de E et F.
On sait quil existe une bijection g de E
n
sur E et une bijection h de F sur E
n
.
Si f est injective alors = h f g est injective de E
n
dans lui-meme.
On en deduit que est bijective, ainsi donc que f = h
1
g
1
.
Cest la meme demonstration si on suppose au depart que f est surjective
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 10
Entiers naturels, denombrements Partie II : Ensembles nis
II.2 Proprietes des cardinaux
On voit ici comment calculer le cardinal densembles construits ` a partir densembles nis.
Proposition (Reunion densembles nis disjoints)
Si E et F sont nis disjoints, alors E F est ni et card (E F) = card (E) + card (F).
Si E
1
, . . . , E
n
sont nis disjoints deux ` a deux,
n

i=1
E
i
est ni et card (
n

i=1
E
i
) =
n

i=1
card (E
i
).
Demonstration:
Soient E et F deux ensembles nis disjoints.
Si lun deux est vide, alors E F est ni et card (E F) = card (E) + card (F).
On suppose donc card (E) = n 1 et card (F) = m 1.
Soit f une bijection de E sur E
n
et g une bijection de F sur E
m
.
On denit alors h : E F E
m+n
par
_
x E, h(x) = f(x)
x F, h(x) = n +g(x)
Il est clair que h est bijective, avec :
_
k 1, . . . , n, h
1
(k) = f
1
(k)
k n + 1, . . . , n +m, h
1
(k) = g
1
(k n)
Donc E F est ni et card (E F) = n +m = card (E) + card (F).
Par recurrence, on generalise `a n ensembles E
1
, E
2
, . . . , E
n
, nis et disjoints deux `a deux
Proposition (Reunion de deux ensembles nis)
Si E et F sont nis, alors E F est ni et card (E F) = card (E) + card (F) card (E F).
En particulier : card (E F) card (E) + card (F), avec egalite E F = .
Demonstration:
Lensemble E F est ni car inclus dans E. On a lunion disjointe E = (E F) (E F).
On en deduit card (E) = card (E F) + card (E F).
De meme, on a lunion disjointe E F = (E F) F.
Ainsi : card (E F) = card (E F) + card (F) = card (E) + card (F) card (E F).
Enn : card (E F) = card (E) + card (F) card (E F) = 0 E F =
Proposition (Generalisation ` a n ensembles nis)
Si E
1
, E
2
, . . . , E
n
sont nis, alors
n

i=1
E
i
est ni et card (
n

i=1
E
i
)
n

i=1
card (E
i
).
On a legalite card (
n

i=1
E
i
) =
n

i=1
card (E
i
) les E
i
sont disjoints deux ` a deux.
Demonstration:
On proc`ede par recurrence sur lentier n 2. Le resultat est connu si n = 2.
On suppose que ces proprietes sont vraies pour un entier n 2 donne.
On se donne n + 1 ensembles nis E
1
, E
2
, . . . , E
n
, E
n+1
. Soit F =
n

i=1
E
i
.
Par hypoth`ese de recurrence, F est ni et card (F)
n

i=1
card (E
i
).
Donc
n+1

i=1
E
i
= F E
n+1
est ni et card (
n+1

i=1
E
i
) card (F) + card (E
n+1
)
n+1

i=1
card (E
i
).
Legalite card (
n+1

i=1
E
i
) =
n+1

i=1
card (E
i
) equivaut `a
_
_
_
card (F E
n+1
) = card (F) + card (E
n+1
)
card (
n

i=1
E
i
) =
n

i=1
card (E
i
)
et signie que E
n+1
est disjoint de F =
n

i=1
E
i
, les ensembles E
1
, . . . , E
n
etant eux-memes disjoints deux
`a deux. Ceci prouve la propriete au rang n + 1 et ach`eve la recurrence
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 11
Entiers naturels, denombrements Partie II : Ensembles nis
Le resultat precedent peut etre generalise (mais la demonstration est admise) :
Proposition (Formule du crible)
Soient E
1
, . . ., E
n
des ensembles nis. Posons I = 1, 2, . . . , n.
On a card (
n

i=1
E
i
) =

J I
(1)
1+card (J)
card (

jJ
E
j
)
Par exemple, si E, F, G sont trois ensembles nis :
card (E F G) = card (E) + card (F) + card (G)
card (E F) card (E G) card (F G)
+card (E F G).
Demonstration:
Soit H = F G. On a card (E F G) = card (E H) = card (E) + card (H) card (E H).
Mais card (H) = card (F) + card (G) card (F G).
On a donc dej`a : card (E F G) = card (E) + card (F) + card (G) card (F G) card (E H).
Dautre part, E H = E (F G) = (E F) (E G). On en deduit :
card (E H) = card (E F) + card (E G) card ((E F) (E G))
= card (E F) + card (E G) card ((E F G))
Lexpression attendue de card (E F G) en decoule
Proposition (Principe des bergers)
Soit E, F deux ensembles nis, et f une application de E vers F.
Alors card (E) =

yF
card f
-1
(y).
Donc si tous les elements de F ont le meme nombre q dantecedents : card (E) = q card (F).
Demonstration:
En eet, les ensembles A
y
= f
-1
(y), quand y parcourt F, forment une partition de E.
Ils sont donc disjoints deux `a deux et leur reunion est egale `a E.
Il en decoule card (E) = card (

yF
A
y
) =

yF
card (A
y
).
Si tous les y de F ont q antecedents, chaque card (A
y
) vaut q, et il y a card (F) elements y dans F. On
en deduit card (E) = q card (F)
Proposition (Produit cartesien densembles nis)
Si E et F sont nis, alors E F est ni et card (E F) = card (E) card (F).
Plus generalement, si E
1
, E
2
, . . ., E
n
sont nis, alors card (
n

i=1
E
i
) =
n

i=1
card (E
i
).
En particulier, si E est ni, alors pour tout n 1 : card (E
n
) = card (E)
n
.
Demonstration:
Si E ou F est vide, alors E F est vide et on a card (E F) = card (E) card (F) = 0.
Sinon, soit f lapplication de E F vers F denie par : (x, y) E F, f(x, y) = y.
Lapplication f est surjective. Pour tout y de F, A
y
= f
1
(y) = (x, y), x E.
Lapplication g
y
: E A
y
denie par g
y
(x) = (x, y) est visiblement une bijection.
Il en decoule que pour tout y de F, on a card (A
y
) = q = card (E).
Le principe des bergers donne : card (E F) = q card (F) = card (E) card (F).
La suite de la proposition se demontre par une recurrence evidente sur n
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 12
Entiers naturels, denombrements Partie III : Denombrements
III Denombrements
III.1 Applications entre ensembles nis
On note T(E, F) lensemble des applications dun ensemble E vers un ensemble F.
Proposition (Nombre dapplications entre deux ensembles nis)
Si E et F sont nis non vides, T(E, F) est ni et card (T(E, F)) = card (F)
card (E)
.
Ce resultat justie que lon note souvent F
E
lensemble T(E, F).
Demonstration:
Posons n = card (E). Soit a une bijection de E
n
sur E. On note E = a
1
, a
2
, . . . , a
n
.
Toute application f : E F est caracterisee par le n-uplet (f(a
1
), f(a
2
), . . . , f(a
n
)).
Lapplication : T(E, F) F
n
denie par (f) = (f(a
1
), . . . , f(a
n
)) est donc bijective.
On en deduit card (T(E, F)) = card (F
n
) = card (F)
n
= card (F)
card (E)

Proposition (Ensemble des parties dun ensemble ni)

Soit E un ensemble ni, de cardinal n. Alors T(E) est ni et card (T(E)) = 2
n
.
Demonstration:
A toute partie A de E, on associe sa fonction caracteristique

A
: E 0, 1.
On sait que lapplication A

A
est une bijection de T(E) sur lensemble T(E, 0, 1).
On sait que lensemble T(E, 0, 1) est ni, de cardinal 2
n
.
On en deduit card (T(E)) = 2
n

Proposition (Nombre dinjections ou de bijections entre deux ensembles nis)

Soient E et F deux ensembles nis non vides.
Notons card (E) = p, et card (F) = n, avec 1 p n.
Le nombre dinjections de E dans F est
n!
(n p)!

En particulier, si card (E) = card (F) = n, le nombre de bijections de E dans F est n!

Cest le cas si E = F (les bijections de E sur E sont appelees permutations de E).
Demonstration:
Soit J(E, F) lensemble des applications injectives de E dans F.
Cest un ensemble non vide car p n, et il est ni car inclus dans T(E, F).
On raisonne par recurrence sur lentier p 1.
Si p = 1, cest evident : il y a n applications de E dans F, toutes injectives !
Supposons le resultat prouve `a lordre p 1.
On se donne donc E de cardinal p + 1, et F de cardinal n p + 1.
Soit a un element xe de E, et soit E

= E a.
A tout element f de J(E, F), on associe (f) = f(a), image de a par f.
On denit ainsi une application de J(E, F) dans F.
Soit b un element de F. Posons F

= F b.
Une injection g : E

F

a un seul prolongement injectif f : E F tel que f(a) = b.
On dispose ainsi dune bijection de
1
(b) sur J(E

, F

).
Lhypoth`ese de recurrence donne : card (J(E

, F

)) =
(n 1)!
((n 1) p))!
=
(n 1)!
(n (p + 1))!
On en deduit card
1
(b) =
(n 1)!
(n (p + 1))!
pour tout b de F.
Le lemme des bergers donne alors card (J(E, F)) = card (F)
(n 1)!
(n (p + 1))!
=
n!
(n (p + 1))!
.
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 13
Entiers naturels, denombrements Partie III : Denombrements
On a ainsi demontre la propriete au rang p + 1, ce qui ach`eve la recurrence.
Puisque E est ni, une application f : E E est bijective si et seulement si elle est injective.
Le nombre de bijections de E dans E est donc
n!
(n n)!
=
n!
0!
= n!
III.2 Arrangements et combinaisons
Denition
Soient p, n deux entiers tels que 0 p n.
On pose
A
p
n
=
n!
(n p)!
et
_
n
p
_
=
1
p !
A
p
n
=
n!
p !(n p)!
On constate que, si 1 p n :
_
_
_
A
p
n
= n(n 1) (n p + 1)
_
n
p
_
=
n(n 1) (n p + 1)
p(p 1) 2 1
Par exemple :
_

_
n N,
A
0
n
= 1,
A
n
n
= n!,
_
n
0
_
=
_
n
n
_
= 1.
n N

,
A
1
n
= n,
A
n1
n
= n!,
_
n
1
_
=
_
n
n 1
_
= n.
On sait que si 1 p n,
A
p
n
represente le nombre dapplications injectives dun ensemble ` a p
elements vers un ensemble ` a n elements.
Proposition (Arrangements)
Soit F un ensemble ni de cardinal n 1. Soit p un entier veriant 1 p n.
Un arrangement de p elements de F est un p-uplet (y
1
, y
2
, . . . , y
p
) forme de p elements de F,
distincts deux ` a deux.
Le nombre darrangements de p elements de F est
A
p
n
(on parle souvent darrangements de p
elements parmi n).
Demonstration:
Se donner un arrangement (y
1
, y
2
, , y
p
) de p elements de F, cest se donner une application injective
f de E
p
dans F, denie par : k E
p
, f(k) = y
k
. Il y a donc autant darrangements de p elements de F
que de telles applications injectives, cest-` a-dire
A
p
n

Proposition (Combinaisons)
Soit F un ensemble ni de cardinal n 1. Soit p un entier veriant 0 p n.
Une combinaison de p elements de F est une partie de F, de cardinal p.
Si p 1, elle peut donc secrire y
1
, y
2
, . . . , y
p
, o` u y
1
, y
2
, . . ., y
p
sont distincts deux `a deux dans
F (on parle souvent de combinaison sans repetitions).
Le nombre de combinaisons de p elements de F est egal ` a
_
n
p
_
(on parle souvent de combinaisons
de p elements parmi n).
Demonstration:
Il y a un seul arrangement de 0 elements de F : cest la partie vide, et on a bien
_
n
0
_
= 1.
On suppose donc p 1. Soit lapplication qui `a un arrangement (y
1
, y
2
, . . . , y
p
) de p elements de F
associe la combinaison y
1
, y
2
, . . . , y
p
. Lapplication est sujective et chaque combinaison de p elements
de F est limage de p ! arrangements dierents.
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 14
Entiers naturels, denombrements Partie III : Denombrements
En eet les arrangements fournissant la meme combinaison que (y
1
, y
2
, . . . , y
p
) sont ceux qui sen deduisent
par une des p ! permutations possibles sur les p elements y
1
, y
2
, . . . , y
p
.
Le principe des bergers permet alors decrire :
A
p
n
= p !
_
n
p
_
.
On en deduit
_
n
p
_
=
1
p !
A
p
n
=
n!
p !(n p)!

Proprietes fondamentales des coecients
_
n
p
_
_

_
Pour tous entiers n, p avec 0 p n :
_
n
p
_
=
_
n
n p
_
.
Si 1 p n 1, alors
_
n
p
_
=
_
n 1
p
_
+
_
n 1
p 1
_
.
Demonstration:
Soit E un ensemble ni de cardinal n.
Pour tout k de 0, . . . , n, soit T
k
(E) lensemble des parties de E ayant k elements.
Lapplication A A est une bijection de T(E) sur lui-meme.
Pour tout p de 0, . . . , n, elle induit une bijection de T
p
(E) sur T
np
(E).
Il en resulte legalite card (T
p
(E)) = card (T
np
(E)).
On a donc prouve legalite
_
n
p
_
=
_
n
n p
_
.
Remarque : on peut bien s ur ecrire
_
n
n p
_
=
n!
(n p)! (n (n p))!
=
n!
(n p)!p !
=
_
n
p
_
.
On pourrait mettre en place des bijections, mais un simple denombrement sut.
On suppose que les entiers n et p verient 1 p n 1.
On xe un element a dun ensemble E de cardinal n.
Il y a
_
n
p
_
mani`eres dierentes de choisir une partie A de E ayant p elements.
Deux cas sont possibles, qui sexcluent mutuellement :
- Ou bien a nappartient pas `a A :
Il y a alors
_
n 1
p
_
mani`eres de former A car il reste `a choisir p elements parmi les n 1 elements
de E a.
- Ou bien a appartient `a A :
Il y a alors
_
n 1
p 1
_
mani`eres de former A car il reste `a choisir p1 elements parmi les n1 elements
de E a.
Ce denombrement prouve que
_
n
p
_
=
_
n 1
p
_
+
_
n 1
p 1
_

Cette derni`ere formule, avec
_
n
0
_
=
_
n
n
_
= 1, permet de calculer les
_
n
p
_
de proche en proche. On
place souvent les
_
n
p
_
dans un tableau triangulaire, dont les lignes et les colonnes sont numerotees
` a partir de 0. Le coecient
_
n
p
_
vient alors se placer ` a lintersection de la ligne dindice n et de la
colonne dindice p.
Le tableau ci-dessous est connu sous le nom de triangle de Pascal :
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 15
Entiers naturels, denombrements Partie III : Denombrements
p = 0 p = 1 p = 2 p = 3 p = 4 p = 5 p = 6
n = 0 1
n = 1 1 1
n = 2 1 2 1
n = 3 1 3 3 1
n = 4 1 4 6 4 1
n = 5 1 5 10 10 5 1
n = 6 1 6 15 20 15 6 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
n
_
n
0
_ _
n
1
_ _
n
2
_ _
n
3
_ _
n
4
_ _
n
5
_ _
n
6
_
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Autres proprietes
Sous reserve que les coecients ci-dessous soient denis, on a les egalites :
_
n
p + 1
_
=
n p
p + 1
_
n
p
_
,
_
n
p
_
=
n
p
_
n 1
p 1
_
,
_
n
p
_
=
n
n p
_
n 1
p
_
Demonstration:
On suppose 0 p < n :
_
n
p + 1
_
=
n!
(p + 1)!(n p 1)!
=
n p
p + 1
n!
p !(n p)!
=
n p
p + 1
_
n
p
_
.
On suppose 1 p n :
_
n
p
_
=
n!
p !(n p)!
=
n
p
(n 1)!
(p 1) ! ((n 1) (p 1))!
=
n
p
_
n 1
p 1
_
.
On suppose 0 p < n :
_
n
p
_
=
n!
p !(n p)!
=
n
n p
(n 1)!
p !(n p 1)!
=
n
n p
_
n 1
p
_

III.3 Binome de Newton
Le resultat suivant est particuli`erement important.
Cest sans doute en utilisant la formule du binome quon a le plus de chances de rencontrer les
coecients
_
n
p
_
(qui pour cette raison sont appeles coecients du binome).
Proposition (Formule du bin ome de Newton)
(x, y) C
2
, n N, (x + y)
n
=
n

k=0
_
n
k
_
x
k
y
nk
. En particulier : (1 + x)
n
=
n

k=0
_
n
k
_
x
k
.
Demonstration:
On proc`ede par recurrence sur N. La propriete est evidente si n = 0.
En eet (xy)
0
= 1 et
n

k=0
_
n
k
_
x
k
y
nk
=
_
n
0
_
x
0
y
0
= 1.
Supposons la propriete demontree au rang n 0, et considerons (x +y)
n+1
. On a :
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 16
Entiers naturels, denombrements Partie III : Denombrements
(x +y)
n+1
= (x +y)(x +y)
n
= (x +y)
_
n

k=0
_
n
k
_
x
k
y
nk
_
=
n

k=0
_
n
k
_
x
k+1
y
nk
+
n

k=0
_
n
k
_
x
k
y
n+1k
=
_
n
n
_
x
n+1
y
0
+
n1

k=0
_
n
k
_
x
k+1
y
nk
+
n

k=1
_
n
k
_
x
k
y
n+1k
+
_
n
0
_
x
0
y
n+1
= x
n+1
+
n

k=1
_
n
k 1
_
x
k
y
n+1k
+
n

k=1
_
n
k
_
x
k
y
n+1k
+y
n+1
= x
n+1
+
n

k=1
(
_
n
k 1
_
+
_
n
k
_
) x
k
y
n+1k
+y
n+1
=
_
n + 1
n + 1
_
x
n+1
y
0
+
n

k=1
_
n + 1
k
_
x
k
y
n+1k
+
_
n + 1
0
_
x
0
y
n+1
=
n+1

k=0
_
n + 1
k
_
x
k
y
n+1k
Ce qui demontre la propriete au rang n + 1 et ach`eve la recurrence
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 17
Entiers naturels, denombrements Complements
Complements
Axiomes de Peano
On pourrait denir lensemble N ` a partir dun nombre reduit daxiomes.
Une telle denition est hors-programme en MPSI.
Lintroduction la plus connue de N est par les Axiomes de Peano.
Si on est interesse par le sujet, on pourra se referer `a
http://megamaths.perso.neuf.fr/cenn0001.pdf
http://fr.wikipedia.org/wiki/Axiomes_de_Peano
http://fr.wikipedia.org/wiki/Giuseppe_Peano
Ensembles denombrables
NB : la notion densemble denombrable est hors-programme des classes preparatoires.
Denition
Un ensemble E est dit denombrable sil existe une bijection de N sur E.
Un ensemble E est dit au plus denombrable sil est ni ou denombrable.
Remarques
N est evidemment lui-meme un ensemble denombrable.
N

est denombrable car la succession n n + 1 est une bijection de N sur N

.
De meme, lensemble des entiers pairs et celui des entiers impairs sont denombrables (considerer
les applications n 2n et n 2n + 1.)
Tout ensemble denombrable est inni (car N est lui-meme inni.)
Si E est denombrable, et si on note n a
n
une bijection de N sur E, on peut donc ecrire
E = a
n
, n N, les a
n
etant distincts deux ` a deux. Le caract`ere denombrable de E est donc une
mani`ere de numeroter distinctement les dierents elements de E.
Si E est denombrable (resp. au plus denombrable) et sil existe une bijection de E sur un ensemble
F, alors F est denombrable (resp. au plus denombrable).
Proposition (Parties dun ensemble denombrable)
Toute partie F dun ensemble denombrable E est au plus denombrable.
Demonstration:
Quitte `a utiliser une bijection de N sur E, on peut toujours supposer que E = N.
Soit F une partie de N. Montrons que si F est innie alors F est denombrable.
On forme une application f de N dans F, par recurrence, de la mani`ere suivante :
f(0) est le minimum de F (qui est une partie non vide de N.)
Pour tout n de N

, f(n) = min (F f(0), . . . , f(n1)) (non vide car F est inni.)

Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 18
Entiers naturels, denombrements Complements
f est injective. En eet, si m < n, alors f(n) / f(0), . . . , f(m) f(n) ,= f(m).
Lapplication f realise donc une bijection de N sur f(N). Il en decoule que f(N) est inni.
Supposons par labsurde que f ne soit pas bijective.
Il existe alors un element x de F qui na pas dantecedent par f.
Pour tout entier n 1, lelement x est donc dans F f(0), . . . , f(n 1).
Par denition de f(n), il en decoule f(n) a. Or on a egalement f(0) a.
Lensemble f(N) est donc inclus dans [[0, a]], ce qui implique quil est majore donc ni.
On arrive ainsi `a une absurdite.
Lapplication f est donc une bijection de N sur F : lensemble F est denombrable
Proposition (Produit cartesien densembles denombrables)
Lensemble N N est denombrable.
Si E
1
, . . . , E
n
sont denombrables, leur produit cartesien
n

k=1
E
k
est denombrable.
Demonstration:
Tout entier n non nul secrit dune mani`ere unique n = 2
p
(2q + 1), avec (p, q) N
2
.
En eet, p est lexposant maximum k tel que 2
k
[ n, et 2q + 1 est lentier (necessairement impair)
resultant du quotient exact de n par 2
p
.
Lapplication (p, q) 2
p
(2q + 1) est donc une bijection de N
2
sur N

.
Comme N

est denombrable, il en resulte que N

2
est denombrable.
On commence par traiter le cas de la reunion de deux ensembles denombrables.
Soient E
1
et E
2
deux ensembles denombrables.
Soient f : N E
1
et g : N E
2
deux bijections.
Alors lapplication h : N
2
E
1
E
2
denie par h(m, n) = (f(m), g(n)) est une bijection.
Il en decoule que lensemble E
1
E
2
est denombrable.
Le passage au cas de plus de deux ensembles seectue par une recurrence evidente
Proposition (Une caracterisation des ensembles au plus denombrables)
Soient E un ensemble denombrable. Un ensemble F non vide est au plus denombrable si et
seulement sil existe une surjection de E sur F.
Demonstration:
Quitte `a utiliser une bijection de N sur E, on peut toujours supposer que E = N.
Soit f une surjection de N vers F.
Pour tout y de F, on note g(y) le plus petit des antecedents de y par f.
On denit ainsi une application g : F N qui verie f g = Id
F
par construction.
Lapplication f g etant injective, il en est de meme de g.
Lapplication g realise donc une bijection de F sur une partie de N.
Cette derni`ere etant au plus denombrable, il en est de meme de F.
La reciproque est evidente.
Si F est denombrable il existe une bijection (donc une surjection) f de N sur F.
Supposons donc card (F) = n 1, et soit f une bijection de [[0, n1]] sur F.
Lapplication g denie par g(k) = min(k, n1) est alors une surjection de N sur F
Remarques et consequences
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 19
Entiers naturels, denombrements Complements
La proposition precedente signie quun ensemble non vide E est au plus denombrable si et seule-
ment sil peut secrire E = a
n
, n N, (les a
n
etant non necessairement distincts.)
Lensemble Z est denombrable car il est inni (il contient N) et lapplication denie sur N
2
par
f(m, n) = m n est une sujection de N
2
sur Z.
Lensemble Q est denombrable car il est inni (il contient N) et lapplication f denie sur Z N

par f(m, n) =
m
n
est une surjection de Z N

sur Q.
Proposition (Reunions densembles au plus denombrables)
Soit (E
n
)
nN
une suite densembles au plus denombrables.
Alors leur reunion F =

nN
E
n
est un ensemble au plus denombrable.
Demonstration:
Pour tout n de N, on sait quil existe une surjection, que nous noterons f
n
, de N sur E
n
.
On denit alors g : N
2
F en posant g(n, m) = f
n
(m). Montrons que g est surjective.
Soit x un element de F. Il existe au moins un entier n tel que x appartienne `a E
n
.
Mais lapplication f
n
: N E
n
etant surjective, il existe m dans N tel que f
n
(m) = x.
On a ainsi trouve (n, m) dans N
2
tel que g(n, m) = x. Lapplication g est donc surjective.
Il en decoule que F est au plus denombrable
Remarques
Si lun au moins des E
n
est denombrable, alors F =

nN
E
n
est denombrable.
Une union nie densembles au plus denombrables est au plus denombrable : il sut en eet de
completer une famille nie E
0
, E
1
, . . . , E
n
par des E
k
egaux par exemple `a E
n
.
Proposition
Lensemble T(N) est inni non denombrable.
Demonstration:
Supposons par labsurde quil existe une surjection f de N sur T(N).
Considerons la partie de A de N denie par A = n N, n / f(n).
Puisque f est surjective, il existe un element a de N tel que f(a) = A.
On se pose alors la question de savoir si a est ou nest pas element de A.
Si a A, cela signie, par denition de A, que a nest pas dans f(a) = A : cest absurde.
Si a / A, cela signie que a est dans f(a) = A : cest toujours aussi absurde.
Conclusion : lhypoth`ese de lexistence dune surjection de N dans T(N) est absurde.
Il en resulte que lensemble T(N) (qui est manifestement inni) est non denombrable
Proposition
Lensemble R est inni non denombrable.
Demonstration:
Tout x de [0, 1[ a un unique developpement decimal illimite x = 0, a
1
a
2
. . . a
n
. . .
Pour simplier les notations, on note a
k
= d
k
(x). Soit f une application de N

sur [0, 1[.

On denit x = 0, a
1
a
2
. . . a
n
. . . par son developpement decimal de la mani`ere suivante :
Si d
n
(f(n)) = 0 alors d
n
(x) = 1. Sinon d
n
(x) = 0.
Ainsi : n N

, x ,= f(n) car leurs decimales de rang n sont distinctes.

Le reel x na donc pas dantecedent par f. On peut donc conclure :
Il ny a pas de surjection de N

sur [0, 1[ donc `a fortiori sur R : R nest pas denombrable

Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 20
Entiers naturels, denombrements Complements
Si on est interesse par le sujet denombrabilite, on pourra se referer ` a
http://fr.wikipedia.org/wiki/Ensemble_denombrable
Plus precisement, pour la non-denombrabilite de R, on pourra consulter :
http://fr.wikipedia.org/wiki/Argument_de_la_diagonale_de_Cantor
Lycee Saint-Louis, MPSI3 annee 2011/2012 Page 21