Cours de Mathématiques

Ce cours couvre les notions fondamentales des entiers naturels et des techniques de dénombrement. Il s'adresse principalement aux étudiants en classes préparatoires scientifiques ou à toute personne souhaitant consolider ses bases en théorie des ensembles finis, raisonnement par récurrence, et combinatoire.

Entiers naturels

L’ensemble N

L’ensemble des entiers naturels, noté IN, est muni d’une application s appelée succession, qui associe à chaque entier naturel n son successeur s(n). L’entier 0 est défini comme l’unique élément sans antécédent par s. On note 1 = s(0), 2 = s(1), etc. L’ensemble IN* = IN \ {0} regroupe les entiers naturels non nuls.

La fonction s est une bijection de IN sur IN*, ce qui permet de définir le prédécesseur de n ∈ IN* comme l’unique entier m tel que s(m) = n, noté n − 1.

L’axiome de récurrence stipule que toute partie A de IN contenant 0 et stable par succession (c’est-à-dire si n ∈ A alors s(n) ∈ A) est égale à IN.

Définition de l’addition

L’addition est définie par récurrence sur le second argument :

∀ (m, n) ∈ IN², m + 0 = m,
m + s(n) = s(m + n)

On vérifie que s(m) = m + 1.

Raisonnement par récurrence

Pour démontrer qu’une propriété P(n) est vraie pour tout n ∈ IN, on procède ainsi :

• Vérifier le cas initial : P(0) est vraie.
• Supposer que P(n) est vraie (hypothèse de récurrence).
• Montrer que cette hypothèse entraîne P(n + 1) (passage du rang n au rang n + 1).

On conclut que ∀ n ∈ IN, P(n) est vraie.

Somme et produit

L’addition sur IN est associative, commutative, possède 0 comme élément neutre, et est régulière (m + p = n + p ⇒ m = n).

La multiplication est définie par récurrence :

∀ (m, n) ∈ IN², m × 0 = 0,
m × (n + 1) = m × n + m

Elle est associative, commutative, distributive par rapport à l’addition, possède 1 comme élément neutre, et est régulière sur IN*.

Factorielle

La factorielle est définie par :

0! = 1,
∀ n ∈ IN*, n! = n × (n − 1)!

Autrement dit :

n! = ∏_{k=1}^n k

Exponentiation

Pour m, n ∈ IN :

m^0 = 1,
m^{n+1} = m^n × m

Les propriétés suivantes sont valides :

• m^n × m^p = m^{n+p}
• (m^n)^p = m^{np}
• m^{p} × n^{p} = (mn)^p
• n^1 = n, 1^n = 1
• 0^n = 0 pour n ∈ IN*, et par convention 0^0 = 1

Relation d’ordre et différence

On définit l’ordre sur IN par :

m ≤ n ⇔ ∃ p ∈ IN, m + p = n

Cette relation est un ordre total, avec 0 comme minimum. Elle est compatible avec l’addition et la multiplication :

m ≤ n ⇒ m + p ≤ n + p et m × p ≤ n × p

La différence n − m est définie uniquement si m ≤ n, comme l’unique entier p tel que m + p = n.

Division euclidienne

Pour m ∈ IN et n ∈ IN*, il existe un unique couple (q, r) ∈ IN² tel que :

m = n × q + r, avec 0 ≤ r ≤ n − 1

q est le quotient, r le reste. On note n | m si n divise m, c’est-à-dire si r = 0.

Variantes du raisonnement par récurrence

• Récurrence à partir de n0 : On suppose P(n0) vraie et que ∀ n ≥ n0, P(n) ⇒ P(n + 1), alors ∀ n ≥ n0, P(n).
• Récurrence double : On suppose P(n0) et P(n0 + 1) vraies, et que ∀ n ≥ n0, (P(n) et P(n + 1)) ⇒ P(n + 2), alors ∀ n ≥ n0, P(n).
• Récurrence forte : On suppose P(n0) vraie et que ∀ n ≥ n0, (P(n0), ..., P(n)) ⇒ P(n + 1), alors ∀ n ≥ n0, P(n).

Conseils pour réussir un raisonnement par récurrence :

• Ne pas oublier le pas initial.
• Formuler correctement l’hypothèse de récurrence pour un entier fixé n.
• Bien distinguer le passage du rang n au rang n + 1 et la conclusion finale.

Ensembles finis

Cardinal d’un ensemble fini

Pour n ∈ IN, on note En = {m ∈ IN, 1 ≤ m ≤ n}.

Propriétés :

• Il existe une injection de En dans Ep ⇔ n ≤ p.
• Il existe une surjection de En sur Ep ⇔ n ≥ p.
• Il existe une bijection de En sur Ep ⇔ n = p.
• Une application f : En → En est bijective ⇔ elle est injective ⇔ elle est surjective.

Un ensemble non vide E est fini s’il existe une bijection de En sur E. Le cardinal de E, noté card(E), est l’unique entier n tel que cette bijection existe. Par convention, ∅ est fini de cardinal 0.

Une partie non vide A de IN est finie ⇔ elle est majorée. En particulier, IN est infini.

Si E est fini et A ⊆ E, alors A est fini et card(A) ≤ card(E), avec égalité si et seulement si A = E.

Applications entre ensembles finis

• Si E est fini et f : E → F, alors f(E) est fini et card(f(E)) ≤ card(E), avec égalité ⇔ f est injective.
• Si f : E → F est surjective et E fini, alors F est fini et card(F) ≤ card(E), avec égalité ⇔ f est bijective.
• Si f : E → F est injective et f(E) fini, alors E est fini et card(E) = card(f(E)).
• Il existe une injection de E dans F avec F fini ⇔ E fini et card(E) ≤ card(F).
• Il existe une surjection de E sur F avec E fini ⇔ F fini et card(F) ≤ card(E).
• Il existe une bijection de E sur F avec E et F finis ⇔ card(E) = card(F).

Propriétés des cardinaux

Soient E et F des ensembles finis :

• Si E et F sont disjoints, alors card(E ∪ F) = card(E) + card(F).
• En général, card(E ∪ F) = card(E) + card(F) − card(E ∩ F).
• Pour n ensembles finis E1, ..., En :

card(⋃_{i=1}^n E_i) ≤ ∑_{i=1}^n card(E_i),
avec égalité si et seulement si les E_i sont deux à deux disjoints.

Formule du crible (inclusion-exclusion) :

card(⋃_{i=1}^n E_i) = ∑_{∅ ≠ J ⊆ {1,...,n}} (−1)^{|J|+1} card(⋂_{j∈J} E_j)

Exemple pour trois ensembles E, F, G :

card(E ∪ F ∪ G) = card(E) + card(F) + card(G)
− card(E ∩ F) − card(E ∩ G) − card(F ∩ G)
+ card(E ∩ F ∩ G)

Principe des bergers :

Soit f : E → F une application entre ensembles finis. Alors :

card(E) = ∑_{y ∈ F} card(f^{-1}({y}))

Si tous les éléments de F ont le même nombre q d’antécédents, alors :

card(E) = q × card(F)

Produit cartésien :

Si E et F sont finis, alors E × F est fini et :

card(E × F) = card(E) × card(F)

De même, pour E1, ..., En finis :

card(∏_{i=1}^n E_i) = ∏_{i=1}^n card(E_i)

En particulier :

card(E^n) = (card(E))^n

Dénombrements

Applications entre ensembles finis

Soient E et F finis non vides. L’ensemble des applications de E vers F, noté F(E, F), est fini et :

card(F(E, F)) = (card(F))^{card(E)}

Ensemble des parties

Pour un ensemble fini E de cardinal n, l’ensemble des parties P(E) est fini et :

card(P(E)) = 2^n

Nombre d’injections et de bijections

Soient E et F finis non vides, avec card(E) = p ≤ n = card(F).

Le nombre d’injections de E dans F est :

A_p^n = n! / (n − p)!

Si p = n, le nombre de bijections est :

n!

Les bijections de E sur E sont appelées permutations.

Arrangements et combinaisons

Soient p, n entiers avec 0 ≤ p ≤ n.

• Arrangement : Un arrangement de p éléments parmi n est un p-uplet de p éléments distincts choisis dans un ensemble de cardinal n. Leur nombre est A_p^n = n! / (n − p)!.
• Combinaison : Une combinaison de p éléments parmi n est une partie de cardinal p d’un ensemble de cardinal n. Leur nombre est noté C_p^n.

Relations fondamentales :

C_p^n = C_p^{n−1} + C_{p−1}^{n−1}, pour 1 ≤ p ≤ n − 1,
avec C_0^n = 1 et C_n^n = 1.

Triangle de Pascal

Les coefficients C_p^n sont organisés dans un tableau triangulaire appelé triangle de Pascal, où chaque coefficient s’obtient comme la somme des deux coefficients au-dessus :

C_p^n = C_p^{n−1} + C_{p−1}^{n−1}

Autres propriétés

Pour les coefficients binomiaux :

C_{p+1}^n = (n − p) / (p + 1) × C_p^n,
C_p^n = n / p × C_{p−1}^{n−1},
C_p^n = (n − p) / n × C_p^{n−1}.

Binôme de Newton

Pour (x, y) ∈ ℂ² et n ∈ IN :

(x + y)^n = ∑_{k=0}^n C_k^n x^k y^{n−k}

En particulier :

(1 + x)^n = ∑_{k=0}^n C_k^n x^k

Ensembles dénombrables

Définition

Un ensemble E est dit dénombrable s’il existe une bijection de IN sur E. Il est au plus dénombrable s’il est fini ou dénombrable.

Remarques

• IN, IN* (entiers naturels non nuls), l’ensemble des entiers pairs ou impairs sont dénombrables.
• Tout ensemble dénombrable est infini.
• Si E est dénombrable et n ↦ a_n une bijection de IN sur E, alors E = {a_n, n ∈ IN} avec les a_n distincts.
• Si E est dénombrable (resp. au plus dénombrable) et qu’il existe une bijection de E sur F, alors F est dénombrable (resp. au plus dénombrable).

Propriétés

• Toute partie F d’un ensemble dénombrable E est au plus dénombrable.
• L’ensemble IN × IN est dénombrable.
• Le produit cartésien d’un nombre fini d’ensembles dénombrables est dénombrable.
• Un ensemble F non vide est au plus dénombrable si et seulement s’il existe une surjection de E (dénombrable) sur F.

Exemples

• L’ensemble ZZ des entiers relatifs est dénombrable car il existe une surjection de IN² sur ZZ définie par f(m, n) = m − n.
• L’ensemble ℚ des rationnels est dénombrable car il existe une surjection de ZZ × IN* sur ℚ définie par f(m, n) = m / n.

Réunions d’ensembles au plus dénombrables

La réunion dénombrable d’ensembles au plus dénombrables est au plus dénombrable. Si au moins un des ensembles est dénombrable, la réunion est dénombrable.

Non dénombrabilité

• L’ensemble des parties de IN, P(IN), est infini et non dénombrable.
• L’ensemble ℝ des nombres réels est infini et non dénombrable.

Glossaire des termes clés

• IN : Ensemble des entiers naturels.
• Successeur : Application s : IN → IN, avec s(n) = n + 1.
• Prédécesseur : Pour n ∈ IN*, l’unique m tel que s(m) = n, noté n − 1.
• Récurrence : Méthode de démonstration basée sur un pas initial et un passage du rang n au rang n + 1.
• Cardinal : Nombre d’éléments d’un ensemble fini.
• Injection : Application qui associe des éléments distincts à des images distinctes.
• Surjection : Application dont l’image est tout l’ensemble d’arrivée.
• Bijection : Application à la fois injective et surjective.
• Arrangement : p-uplet d’éléments distincts choisis parmi n.
• Combinaison : Partie de cardinal p d’un ensemble de cardinal n.
• Coefficient binomial C_p^n : Nombre de combinaisons de p éléments parmi n.
• Triangle de Pascal : Tableau triangulaire des coefficients binomiaux.
• Binôme de Newton : Formule développant (x + y)^n en somme de termes avec coefficients binomiaux.
• Ensemble dénombrable : Ensemble en bijection avec IN.
• Ensemble au plus dénombrable : Ensemble fini ou dénombrable.

Points clés à retenir

• L’ensemble IN est construit à partir de 0 et de la fonction successeur, avec un axiome de récurrence fondamental.
• Les opérations d’addition, multiplication, factorielle et exponentiation sont définies par récurrence.
• La relation d’ordre sur IN est totale, compatible avec les opérations, et permet de définir la différence et la division euclidienne.
• Les ensembles finis sont caractérisés par l’existence d’une bijection avec En, leur cardinal est bien défini et unique.
• Les propriétés des cardinaux permettent de calculer la taille d’ensembles construits par union, intersection, produit cartésien.
• Les coefficients binomiaux et le triangle de Pascal sont essentiels en combinatoire, notamment pour le binôme de Newton.
• Les ensembles dénombrables sont ceux en bijection avec IN, et incluent de nombreux ensembles infinis usuels comme ZZ et ℚ.
• Les ensembles P(IN) et ℝ sont infinis non dénombrables, ce qui marque une différence fondamentale entre types d’infini.