Cours 1 : Cardinalité, Lemme d’Erdös, Formule du crible

Prof : Claudine Picaronny picaro@lsv.ens-cachan.fr

TD : Anthony Lick / Jeremy Dubut

“Maths discrètes” :

  • bcp de combinatoire
  • structures discrète
  • probas

Chapitre 1 : Cardinalité

I. Ensembles finis

Généralités

Ensemble fini :

un ensemble de card $n$ est fini ssi il est en bijection avec $⟦1,n⟧$

NB:

  1. Définition “qui se mord la queue” :

    • les entiers naturels sont en fait construits comme des cardinaux de classe d’éq d’ensembles (pour la relation d’équivalence : “être en bijection avec”).

      ∅ ≡ entier 0

  2. Notation : \(Card(E) ≝ \vert E\vert ≝ \#E\)
  3. Si il existe une surjection de $⟦1,n⟧$ sur $E$, alors $E$ est fini de card $\leq n$
  4. Si il existe une injection de $⟦1,n⟧$ sur $E$, alors $E$ est de card $≥ n$

Soient $E,F$ sont des ensembles fini de card respectifs $n, m$.

  • $E \times F$ est un ensemble fini de card $mn$.

  • $E ∪ F$ est fini et $\vert E ∪ F\vert \leq \vert E\vert + \vert F\vert$.

    Plus précisément :

    \[\vert E ∪ F\vert = \vert E\vert + \vert F\vert - \vert E ∩ F\vert\]

  • $𝒫(E)$, l’ensemble des parties de $E$, est fini de card $2^n$.

    Dém:

    \[\begin{cases} 𝒫(E) &⟶ \{0,1\}^n \\ F &\mapsto (1_F(i))_{i ∈ E} \end{cases}\]

    est une bijection

  • Le nombre de bijections d’un ensemble de card $n$ est $n!$.

Coefficients binomiaux

Soit $k ∈ ⟦0,n⟧$.

Coefficient binomial $\binom{n}{k}$ :

Cardinal de l’ensemble des parties de $E$ de card $k$ (qui est fini).

Identités :

  • \[2^n = \sum\limits_{k=0}^n \binom{n}{k}\]

    car

\(𝒫(E) = \bigsqcup\limits_{k=0}^n \{\text{parties de $E$ de card $k$}\}\)

  • \[\binom{n}{k} = \binom{n}{n-k}\]

    car le passage au complémentaire est une bijection (c’est même une involution) qui échange les parties de card $k$ avec celles de card $n-k$.

  • Le triangle de Pascal : si $n ∈ ℕ^*$ :

    \[\binom{n-1}{k} + \binom{n-1}{k-1} = \binom{n}{k}\]

    Dém:

    Il y a deux types de parties de cardinal $k$ : celles qui contiennent $n$ (et qui sont au nombre de $\binom{n-1}{k-1}$) et celles qui ne le contiennent pas (il y en a $\binom{n-1}{k}$).

  • \[\binom{n}{k} = \sum\limits_{j=k}^n \binom{j-1}{k-1}\]

    Dém :

    on partitionne l’ensemble des parties de card $k$ selon leur plus grand élément $∈ ⟦k, n⟧$

  • Identité de Vandermonde : \(\binom{m+n}{k} = \sum\limits_{0\leq i \leq m, k-n \leq i \leq k} \binom{m}{i}\binom{n}{k-i}\)

Dém:

  1. Méthode 1 : On regarde le $k$-ième coeff de $(X+1)^{n+m} = (X+1)^n (X+1)^m$
  2. Méthode 2 : On partitionne l’ensemble des parties de card $k$ de $E∪F = ⟦1,m+n⟧$ selon les cardinaux des traces sur $E$ et sur $F$.
  • \[k \binom{n}{k} = n \binom{n-1}{k-1}\]

    Dém:

    1. Soit

      \[X = \{ (i,𝕱), 1\leq i \leq k, 𝕱 ⊆ F, \vert 𝕱\vert =k \}\]

      Calculer $\vert X\vert $ de deux façons.

    2. Nombre de façons de choisir un comité de $k$ personnes dont un président parmi $n$ personnes : soit on choisit déjà le président, puis $k-1$ autres personnes du comité, soit on choisit déjà les $k$ personnes du comité puis le président parmi elles.

    Corollaire :

    \[\binom{n}{k} = \frac{n!}{k!(n-k)!}\]

Principe des tiroirs

Principe des tiroirs / Pigeon Hole :

Soit $f : E ⟶ F$ une application d’un ensemble fini $E$ dans un autre $F$.

Si $\vert E\vert > \vert F\vert $, au moins deux éléments ont la même image.

Applications :

Pumping Lemma :

Soit $L$ un langage rationnel :

$∃ N ∈ ℕ; ∀ 𝜔 ∈ L,$

\[\vert w\vert \geq N ⟹ ∃ x,y,z; \begin{cases} 𝜔 ≝ xyz ∈ L \\ \vert y\vert \leq N \end{cases} ∧ ∀n∈ℕ, xy^nz ∈ L\]

Exs:

  • ${a^n b^n, n ∈ ℕ }$ non rationnel

    Dém : Si il y a $N$ états, attention à $a^{N+1}b^{N+1}$

Lemme d’Erdös

Erdös : croyait que Dieu lui dévoilait le livre des mathématiques déjà préécrit petit à petit.

Lemme d’Erdös :

Soit $(x_i)_{i ∈ ⟦1, n^2+1⟧}$ une famille d’entiers naturels.

Alors il y a au moins une sous-famille croissante de card $n+1$ ou un sous-famille décroissante de card $n+1$.

Dém :

On note $c_i$ le card de la plus grande sous-famille croissante qui débute en $x_i$.

On note $d_i$ le card de la plus grande sous-famille décroissante qui termine en $x_i$.

ABS : $∀ i ∈ ⟦1,n^2+1⟧$ : \(\begin{cases} 1 \leq c_i \leq n \\ 1 \leq d_i \leq n \end{cases}\)

Donc par le lemme des tiroirs, il existe $i \neq j$ tq $(c_i, d_i) = (c_j, d_j)$

  • Si $x_i \leq x_j$ : on contredit la définition de $c_i$ puisque \(x_i \leq x_j \leq x_{j_2} \leq x_{j_{c_j}}\)

  • Idem si $x_i > x_j$ : on contredit la définition de $d_j$

Formule du crible / de Poincaré / Principe d’inclusion-exclusion

Dans un ensemble $X$, soient $E_1, …, E_n$ des parties de $X$.

\[\left\vert \bigcup_{1}^n E_i \right\vert = \sum\limits_{\substack{k ∈ ⟦1,n⟧ \\ 1 \leq i_1 < ⋯ < i_k \leq n}} (-1)^{k-1} \bigcap_j E_{i_j}\]

NB :

  • $\vert F\vert = \sum\limits_{x ∈ X} 1_F(x)$
  • $1_{F^c} = 1_X - 1_F$
  • $1_{F∩E} = 1_F \times 1_E$

⟹

\[\begin{align} 1_X - 1_{\bigcup E_i} &= \prod\limits_{1}^n (1_X - 1_{E_i}) \\ &= 1_X + \sum\limits_{k = 1}^n \sum\limits_{1 \leq i_1 < ⋯ < i_k \leq n} (-1)^{k} \prod_j 1_{E_{i_j}} \\ &= 1_X - \sum\limits_{\substack{k ∈ ⟦1,n⟧ \\ 1 \leq i_1 < ⋯ < i_k \leq n}} (-1)^{k-1} 1_{\bigcap E_{i_j}} \end{align}\]

II. Ensembles Dénombrables

Ensemble dénombrable (au sens strict):

ssi il est en bijection avec $ℕ$

NB :

  • Si $f: ℕ ⟶ E$ est une bijection, $f$ permet d’énumérer les éléments de $E$ : \(E ≝ \{f(n) \vert n ∈ ℕ\}\)
  • Un ensemble dénombrable au sens large est un ensemble qui est :
    • soit fini
    • soit dénombrable au sens strict
  • Si $E$ et $F$ sont deux ensembles tels qu’∃ une bij de $E$ sur $F$, alors $E$ est dénombrable ssi $F$ l’est.

NB : Un cardinal = une classe d’éq d’ensembles en bijection.

Proposition : Soit $E$ un ss-ensemble infini de $ℕ$. Alors $E$ est dénombrable.

Dém : On sait que $ℕ$ est

bien ordonné (cf. chap. 2) :

i.e dont toute partie non vide admet un plus petit élément.

On définit $f : ℕ ⟶ E$ par récurrence :

  • $f(0) = \min(E)$
  • Étant donné $n ∈ ℕ^*$, si on a construit $f(0), ⋯, f(n-1)$, on pose : \(f(n) ≝ \min(E\backslash\{f(0), ⋯, f(n-1)\})\)

Par construction, $f$ est injective (car $f(n) \neq f(0), ⋯, f(n-1)$), et même strictement (par injectivité) croissante.

Mq $f$ est surjective : soit $x ∈ E$.

  • Cas 1 : $x = \min(E)$ : fini, car $x = f(0)$
  • Cas 2 : L’ensemble $∅ \neq {m \vert f(m) < x} ∋ 0$ est fini (il s’injecte, par $f$, dans $⟦0,x⟦$).

Notons $n$ le maximum de cet ensemble fini non vide (il existe car l’ordre est total), et montrons que $x = f(n+1)$.

Comme $f$ est croissante et $f(n)<x$, $x > f(i)$ pour tout $i ∈ ⟦0, n⟧$. Par définition de $f(n+1)$, $x \geq f(n+1)$.

De plus, par définition de $n$, $\lnot (f(n+1) < x)$.

Donc $x=f(n+1)$. $\square$

Corollaire : Soit $E$ un ensemble tel qu’∃ une injection de $E$ dans $ℕ$. Alors $E$ est dénombrable au sens large.

Ex:

i) $ℕ$. ii) Pour $ℤ$ : \(\begin{cases} ℤ ⟶ ℕ \\ n \mapsto \begin{cases} 2n \text{ si } n\geq 0 \\ -2n-1 \text{ sinon.} \\ \end{cases}\end{cases}\)

iii) \(\begin{cases} ℕ\times ℕ ⟶ ℕ \\ (a,b) \mapsto 2^a 3^b \end{cases}\)

iv) \(\begin{cases} ℕ^n ⟶ ℕ \\ (a_1, ⋯, a_n) \mapsto 2^{a_1} 3^{a_2} ⋯ \underbrace{p_n^{a_n}}_{p_n : n\text{-ième nombre premier}} \end{cases}\)

NB: $ℙ$ n’est pas fini : cf. preuve d’Euclide : sinon, $\prod_i p_i + 1$ en est un nouveau (puisque tout nombre premier qui le divise divise 1).

Lemme : Un produit cartésien fini d’ensembles dénombrables est dénombrable.

v) $ℚ$ dénombrable : \(\begin{cases} ℚ ⟶ ℕ \\ x = 𝜀\frac p q \mapsto \begin{cases} 2^p 3^q \text{ si } 𝜀=1 \\ 2^p 5^q \text{ si } 𝜀=-1 \text{ et } p\neq 0 \\ \end{cases}\end{cases}\)

($𝜀 ∈ {-1, 1}, p∧q=1$)

Proposition: Soit $E$ un ensemble. Soit ${E_n}_{n∈ℕ}$ une famille de parties de $E$ toutes dénombrables. Alors $\bigcup_n E_n$ est dénombrable.

Dém : Pour $n$ entier, soit $f$ une injection de $E_n$ sur $ℕ$.

\(F : \begin{cases} \bigcup E_i ⟶ ℕ\times ℕ \\ x \mapsto (i, f_i(x)) \end{cases}\) où $i = \min{j \vert x∈E_j}$

Mq $F$ est injective : si $x, j ∈ \bigcup_n E_n$. Posons $F(x) = (i, f_i(x))$, $F(y) = (j, f_j(y))$

\[F(x) = F(y) ⟹ i=j ∧ f_i(x) = f_j(y)\]

et donc $x=y$ par injectivité de $f_i$.

Exs: Ensembles non dénombrables :

  • $ℝ$ :

Argument diagonal (Cantor)

Par l’absurde : Supposons $ℝ = {x_n}_{n∈ℕ}$

On considère le dvpt décimal de $x_n$ non cofinal à 9.

\[x_n = 𝜀_n E_n, u_1^n u_2^n u_3^n ⋯\]

Posons $y = 0, v_0 v_1 ⋯$, où \(v_n ≝ \begin{cases} 0 \text{ si } u_n^n=1 \\ 1 \text{ sinon } \\ \end{cases}\)

Alors pour tout $n$, $y$ et $x_n$ diffèrent tous sur la $n$_ième décimale, donc $y \neq x_n$. $\square$

  • ${0,1}^ℕ$ (et a fortiori $ℕ^ℕ$) est non dénombrable : idem.

III. Equipotence

Équipotence

Deux ensembles en bijection sont dits équipotents.

Théorème de Cantor-Bernstein : Si il existe une injection de $E$ dans $F$ et une injection de $F$ dans $E$, alors $E$ et $F$ sont équipotents.

Dém : Dans le Chap.2

Ex:

  • $ℝ$ et $ℕ^ℕ$ sont équipotents (cf. TD2)

Théorème de Cantor : Soit $E$ un ensemble. $E$ et $𝒫(E)$ ne sont pas équipotents.

Dém : Soit $f : E ⟶ 𝒫(E)$ une application surjective.

Soit \(X ≝ \{x ∈ E \vert x \not\in f(x)\}\) Montrons que $X$ n’est pas atteinte par $f$ :

Supposons qu’il existe $y ∈ E$ tel que $X = f(y)$.

  • Si $y ∈ X = f(y)$, $y \not∈ X$
  • Si $y \not∈ X = f(y)$, $y ∈ X$

Contradiction.

Hypothèse du continu : Toute partie non dénombrable de $ℝ$ est équipotente à $ℝ$.

NB: C’est indécidable dans ZFC.

Leave a comment