CH2

LES ENTIERS NATURELS

LES ENSEMBLES AU PLUS DENOMBRABLES

LA DENOMBRABILITE

  1. Ensemble des entiers naturels |N
  2. Les ensembles au plus dénombrables
    1. Les ensembles finis
    2. Les ensembles infinis
  3. Dénombrement

I] Ensemble des entiers naturels |N

L'ensemble des entiers naturels est muni de 2 lois de composition interne, l'addition et la multiplication, qui sont associatives, commutative, qui admettent un élément neutre. La multiplication est distributive par rapport à l'addition.
|N est muni de la relation d'ordre £ , l'ensemble ( |N, £ ) est bien ordonné, c'est à dire toute partie non vide admet un plus petit élément.

Prop : Soit A une partie non vide de |N
Si A est majoré, A admet une borne supérieur, attention, |N n'admet pas de borne supérieur.

Dem :

Théo : Soit (a, b) Î |N *, $ ! (q, r) Î |N² tq a = b . q + r et 0 £ r £ b

Dem :

Def : Soit 2 entiers non nuls (a, b)

On dit que a est divisible par b ou que a est un multiple de b si le reste de la division euclidienne de a par b est égal à 0
$ q Î |N tq a = b . q
On dit que a est un nombre premier si a n'est divisible que par 1 et lui-même.
Le PGCD entre a et b est le plus grand commun diviseur d entre a et b, alors d / a (d divise a) et d / b. Si n / a et n / b, alors n £ d. On note d = a Ù b = pgcd(a, b).
Le PPCM entre a et b est le plus petit commun multiple m entre a et b. Alors a / m et b / m et si a / n et b / n alors m £ n. On note m = a Ú b = ppcm(a, b).
On dit que a et b sont premiers entre eux, si le PGCD de a et b est égal à 1 i.e. pgcd(a, b) = 1.
On dit que I une partie de |N est un intervalle de |N, si k£ n, " k, n Î I, " k < m £ n, alors m Î I.

Théo : Tout entier non nul est décomposable en produit de facteurs premiers. Si on note P, l'ensemble des nombres premiers,

" n Î |N *, n = Õ Pivi, avec Pi Î P et où les vi sont tous nuls sauf un nombre fini.
Et la décomposition est unique.

Théo : Identité de Bezout

Soit a et b Î |N *²
a et b sont premier entre eux Û $ (l , m ) Î Z² tq l .a + m .b = 1
Si a Ù b = d, alors (l , m ) Î Z² tq l .a + m .b = d

Théorème de GAUSS

Soit (a, b) Î |N *², soit c Î |N. Si a divise b . c et a et b premiers entre eux, alors a divise c.

Théo : Soit a et b Î |N *²

a = Õ pia i b = Õ pib i pi Î P
alors a Ù b = Õ pim i avec m i = min(a i, b i)
et a Ú b = Õ pim i avec m i = max(a i, b i)
(a Ù b)( a Ú b) = a . b

 II] Les ensembles au plus dénombrables

Def : On dit que E et F sont équipotents s'il existe une bijection entre E et F

1. Les ensembles finis

Def : Soit E un ensemble non vide, on dit que E est un ensemble fini s'il existe un entier p tq E et [| 1, p |] soit en bijection.
Par convention, Æ est un ensemble fini. Si E n'est pas fini, il est infini.

Théo : Soit (p, q) Î |N *².

Corollaire : Si E est un ensemble fini non vide, il existe un unique entier p tel que E et [| 1, p |] soit en bijection. Alors p s'appelle le cardinal de E, on note card(E), |E|, #E. Par convention card(Æ ) = 0.

Théo : On considère E et F des ensembles finis p = card(E) et q = card(F).

Théo : Si E et F sont deux ensembles finis de même cardinal n.
Soit f : E ® F une application.
f bijective Û f injective Û f surjective

 Théo : Soit A et B 2 ensembles finis,
Alors Card(AÈ B) = Card(A) + Card(B) - Card(AÇ B)

Théo : Soit A et B 2 ensembles finis,
A x B est fini et Card(A x B) = Card(A) * Card(B)

2. Ensembles infinis

Théo : Pour qu'un ensemble E soit infini, il faut et il suffit que |N s'injecte dans E.

Def : On dit que E est dénombrable, si E est en bijection avec |N.
On dit que E est au plus dénombrable si E est fini ou E est dénombrable.

Théo : Si E et F sont 2 ensembles dénombrables,
Alors E x F est dénombrable.

Théo : Soit I un ensemble dénombrable
Si " i Î I, Ai est un ensemble au plus dénombrable, alors È Ai (i Î I) est au plus dénombrable.

III] Dénombrement

Prop : Si E et F sont 2 ensembles finis de cardinaux respectifs n et p.
Alors F(E,F) est fini et Card(F(E,F)) = pn

Théo : Soit E et F 2 ensembles finis de cardinaux respectifs p et n où p £ n.
Alors le nombre d'injection de E dans F est Apn = n! / (n - p)! appelé le nombre d'arrangements et Apn est le nombre d'arrangements de p éléments choisi parmi n. C'est le nombre de p - upplets distincts dans un ensemble de n éléments.

Rem : Pour les bijections c'est n!

Théo : Soit E un ensemble fini de cardinal n. Le nombre de parties de E à k éléments est Ckn = n! / ((n - k)! * k!) =
Apn / k!

Prop : " (k, n) Î |N², 0 £ k £ n, alors
Ckn = C n - k n
Et k * Ckn = n * Ck-1n-1
Ckn = Ckn-1 + Ck-1n-1 Relation de Pascal
" (a, b) Î |R², (a + b)n = å Ckn * ak * bn - k pour k variant de 0 à n.

Prop : " n Î |N, å Ckn = 2n pour k variant de 0 à n.