Nombresentiersnaturels –Combinatoire
COURS
9
IMPORTANT
Cette démonstratione st hors programme. Le résultat pourra être admis.
Théorème 2
Soit (p, n) ∈ N
2
.
1) Il existe une injection de [[ 1 , p ]] dans[ [1, n]]
⇐⇒
p n .
2) Il existe une surjection de [[ 1 , p ]] dans[ [1, n]]
⇐⇒
p n .
3) Il existe une bijection de [[ 1 , p ]] dans[ [1, n]]
⇐⇒
p = n .
4) Si n > 0, touteinjection de [[ 1 , n ]] dans lui-même estbijective.
5) Toute surjection de [[ 1 , n ]] dans lui-même estbijective.
Démonstration
1) Si p n, [[ 1 , p ]] ⊂ [[ 1 , n ]] et l’injection canonique de [[ 1 , p ]] dans[ [1, n]]
convient.
Réciproquement, démontrons que, s’il existe une injection de [[ 1 , p ]] dans
[[ 1 , n ]] , alors p n. Procédons par récurrencesur p :
a) Si p = 0, touteapplication de ∅ dans [[ 1 , n ]] est évidemment injective.
b) Soit p ∈ N tel que la proposition soitv raie (pour tout n ∈ N
∗
)e ts oit f
uneinjection de [[ 1 , p +1]] dans[ [1, n]] .
f ( p +1)n ’ayant pas d’autre antécédent que p +1, la restriction de f à[ [1, p]]
est une injection de [[ 1 , p ]] dans[ [1, n]] \{f (p +1)}.
En composant par la bijection donnée par le lemme 2.1,onobtient une injection
de [[ 1 , p ]] dans[ [1, n − 1]] . D’aprèsl ’hypothèse de récurrence, on en déduit
p n − 1, ce qui équivaut à p +1 n. La proposition estvérifiée au rang p +1.
c) Cette propositionest donc vraie quel que soit p ∈ N
∗
.
2) Rappelons que l’existence d’une surjection de [[ 1 , p ]] dans[ [1, n]] équivaut
àc elle d’une injection de [[ 1 , n ]] dans[ [1, p]] ( chap. 8, Application 2), d’oùl e
résultat.
3) Conséquence immédiate des points 1) et 2).
4) Soit f uneinjection de [[ 1 , n ]] dans lui-même. Supposons que f ne soit pas
surjective. Il existerait un élément y ∈ [[ 1 , n ]] qui n’aurait pas d’antécédent par
f . L’application:
[[ 1 , n ]] → [[ 1 , n ]] \{y}
x
→
f (x)
serait encore injective. En composant avec la bijection donnée parlelemme 2.1,
on obtiendraitu ne injection de [[ 1 , n ]] dans[ [1, n − 1]], ce quie st impossible
d’après 1).Par conséquent, f est surjective, donc bijective.
5) Soit f unes urjection de [[ 1 , n ]] dans lui-même. Supposons que f ne soit
pas injective. Il existerait deux éléments distincts x et x
qui auraient la même
image (ce qui suppose que n 2). La restriction de f à[ [1, n]] \{x
} serait
encore surjective. En composant avec la réciproque de la bijectiondonnée par le
lemme 2.1,onobtiendrait une surjection de [[ 1 , n − 1]]d ans [[ 1 , n ]] , ce qui est
impossible d’après 2).Par conséquent, f est injective, donc bijective.
2.2 • Cardinal d’unensemble fini
Un ensemble E estd it fini,s ’il existe un entier naturel n et une bijection de
[[ 1 , n ]] dans E.
On peut déduire du théorème 2 que cet entier n est unique :onl’appelle cardinal
de E et on le note Card E. En particulier,C ard ∅ = 0.
Hachette Livre–HPrépa /Math –Laphotocopie non autorisée est un délit
169
COURS
9
IMPORTANT
Cette démonstratione st hors programme. Le résultat pourra être admis.
Théorème 2
Soit (p, n) ∈ N
2
.
1) Il existe une injection de [[ 1 , p ]] dans[ [1, n]]
⇐⇒
p n .
2) Il existe une surjection de [[ 1 , p ]] dans[ [1, n]]
⇐⇒
p n .
3) Il existe une bijection de [[ 1 , p ]] dans[ [1, n]]
⇐⇒
p = n .
4) Si n > 0, touteinjection de [[ 1 , n ]] dans lui-même estbijective.
5) Toute surjection de [[ 1 , n ]] dans lui-même estbijective.
Démonstration
1) Si p n, [[ 1 , p ]] ⊂ [[ 1 , n ]] et l’injection canonique de [[ 1 , p ]] dans[ [1, n]]
convient.
Réciproquement, démontrons que, s’il existe une injection de [[ 1 , p ]] dans
[[ 1 , n ]] , alors p n. Procédons par récurrencesur p :
a) Si p = 0, touteapplication de ∅ dans [[ 1 , n ]] est évidemment injective.
b) Soit p ∈ N tel que la proposition soitv raie (pour tout n ∈ N
∗
)e ts oit f
uneinjection de [[ 1 , p +1]] dans[ [1, n]] .
f ( p +1)n ’ayant pas d’autre antécédent que p +1, la restriction de f à[ [1, p]]
est une injection de [[ 1 , p ]] dans[ [1, n]] \{f (p +1)}.
En composant par la bijection donnée par le lemme 2.1,onobtient une injection
de [[ 1 , p ]] dans[ [1, n − 1]] . D’aprèsl ’hypothèse de récurrence, on en déduit
p n − 1, ce qui équivaut à p +1 n. La proposition estvérifiée au rang p +1.
c) Cette propositionest donc vraie quel que soit p ∈ N
∗
.
2) Rappelons que l’existence d’une surjection de [[ 1 , p ]] dans[ [1, n]] équivaut
àc elle d’une injection de [[ 1 , n ]] dans[ [1, p]] ( chap. 8, Application 2), d’oùl e
résultat.
3) Conséquence immédiate des points 1) et 2).
4) Soit f uneinjection de [[ 1 , n ]] dans lui-même. Supposons que f ne soit pas
surjective. Il existerait un élément y ∈ [[ 1 , n ]] qui n’aurait pas d’antécédent par
f . L’application:
[[ 1 , n ]] → [[ 1 , n ]] \{y}
x
→
f (x)
serait encore injective. En composant avec la bijection donnée parlelemme 2.1,
on obtiendraitu ne injection de [[ 1 , n ]] dans[ [1, n − 1]], ce quie st impossible
d’après 1).Par conséquent, f est surjective, donc bijective.
5) Soit f unes urjection de [[ 1 , n ]] dans lui-même. Supposons que f ne soit
pas injective. Il existerait deux éléments distincts x et x
qui auraient la même
image (ce qui suppose que n 2). La restriction de f à[ [1, n]] \{x
} serait
encore surjective. En composant avec la réciproque de la bijectiondonnée par le
lemme 2.1,onobtiendrait une surjection de [[ 1 , n − 1]]d ans [[ 1 , n ]] , ce qui est
impossible d’après 2).Par conséquent, f est injective, donc bijective.
2.2 • Cardinal d’unensemble fini
Un ensemble E estd it fini,s ’il existe un entier naturel n et une bijection de
[[ 1 , n ]] dans E.
On peut déduire du théorème 2 que cet entier n est unique :onl’appelle cardinal
de E et on le note Card E. En particulier,C ard ∅ = 0.
Hachette Livre–HPrépa /Math –Laphotocopie non autorisée est un délit
169