TD2 : Équipotence, Dénombrabilité

TD 2

EX1

  1. Soit $n \geq 1$.

Mq \(\binom{3n}{3} = 3 \binom{n}{3} + 6n \binom{n}{2} + n^3\)

$⟦1,3n⟧ = \underbrace{⟦1,n⟧}{≝ A} \sqcup \underbrace{⟦n+1,2n⟧}{≝ B} \sqcup \underbrace{⟦2n+1,3n⟧}_{≝ C}$

Une partie de $⟦1,3n⟧$ est constituée :

  • Soit d’un élément de $A$, d’un élément de $B$ et d’un élément de $C$ (il y en a $n^3$)
  • Soit de deux éléments d’un des trois ensembles, et d’un élément d’un autre : il y a $n \binom{n}{2}$ quand ces ensembles sont fixés, $6$ fois plus quand ces ensembles peuvent valoir $A$, $B$, ou $C$.
  • Soit de 3 éléments d’un des trois ensembles : il y a $\binom{n}{3}$ quand cet ensemble sont fixé, $3$ fois plus quand il peut valoir $A$, $B$ ou $C$.

EX2

Le cercle a un périmètre de 1. Disons que c’est $𝕌$, sans perte de généralité. On se donne une partie $A$ de $𝕌$ vérifiant la propriété de l’énoncé : $mes(A) < 1/2$. On pose $𝕌^+ ≝ {z ∈ 𝕌 \vert Im(z) \geq 0}$

ABS : Si ce n’était pas le cas, alors :

\(f≝\begin{cases} A ⟶ 𝕌^+ \\ z \mapsto \begin{cases} z \text{ si $z ∈ 𝕌^+$} \\ -z \text{ sinon}\end{cases} \end{cases}\) vérifierait $f(A) \supset 𝕌^+$, ce qui est absurde, par définition de $A$ (puisque $1/2 \leq mes(f(A)) < mes(A)$ ).

EX 3

Supposons que $m_1 < ⋯ < m_{n+1}$.

(Considérons \(f_{m_i} ≝\begin{cases} \{m_1, ⋯, m_{n+1}\}\backslash\{m_i\} ⟶ ⟦0, m_i-1⟧ \\ m \mapsto m \mod m_i \end{cases}\))

$m_i = 2^{k_i} q_i$ avec $q_i$ impair.

\[f ≝\begin{cases} \{m_1, ⋯, m_{n+1}\} ⟶ \{1, 3, 5, ⋯, 2n-1 \} \\ m_i \mapsto q_i \end{cases}\]

Par le principe des tiroirs, il y a deux $q_i, q_j$ égaux, donc $m_i$ divise $m_j$ ou $m_j$ divise $m_i$ (celui qui a la plus petite valuation 2-adique divise l’autre).

EX 4

M1. Toute partie finie $F$ de $ℕ$ peut être associée de manière bi-univoque à l’entier :

\(\prod\limits_{i ∈ F} p_i\) où $p_j$ est le $j$-ème nombre premier.

M2. \(𝒫_f(ℕ) = \bigcup\limits_{k ∈ ℕ} 𝒫(⟦0,k⟧)\)

EX 5

Tout nombre décimal $d = \sum\limits_{F ⊆ 𝒫_f(ℤ)}a_i 10^i$ :

M1. peut-être associé de manière injective à une suite finie $(a_i)_{F ⊆ 𝒫_f(ℤ)} ∈ ⟦0,9⟧^{(ℕ)}$ (en ignorant les développement cofinaux à 9).

M2. peut être associée de manière injective à l’entier :

\(\prod\limits_{i ∈ F} p_i^{a_i}\) où $p_j$ est le $j$-ème nombre premier.

M3. On peut aussi qu’on nombre décimal $d$ est la donnée d’un entier $k$ et d’un entier naturel $n$, puisque $d$ est de la forme $\frac{k}{10^n}$.

EX 6

En posant $n ≝ \vert 𝛴\vert $, $𝛴^*$ est équipotent à $⟦1,n⟧^{(ℕ)}$

Argument diagonal de Cantor pour $𝛴^∞$.

EX 7

M1. Argument diagonal de Cantor.

M2. Bijection avec $𝒫(ℕ)$ en associant à $a ∈ {0,1}^ℕ$ de manière bi-univoque l’ensemble des indices tels que $a_i = 1$

EX 8

À tout réel $r$, on associe une suite de rationnels $(r_i)_i ∈ ℚ^ℕ ≃ (ℕ^2)^ℕ ≃ ℕ^ℕ$ tendant vers $r$ (car $ℚ$ est dense dans $ℝ$).

Or, $ℕ^ℕ$ s’injecte dans l’ensemble des parties de la forme ${p_i^j}$, où $p_i$ est le $i$-ème nombre premier (à toute $f∈ℕ^ℕ$, on associe la partie $𝛷(f) ≝ {p_i^{f(i)}}_{i ∈ ℕ}$ , et réciproquement).

Alors $𝛷(ℕ^ℕ) ⊆ ℕ$ convient, puisque deux parties égales correspondent à des réels égaux, et $𝛷(ℕ^ℕ) ≃ ℕ^ℕ$ dans lequel s’injecte $ℝ$ (et qui est donc non dénombrable).

$u ∈ {1,2}^ℕ$

\[I_u = \{ \text{mots }u_n ⋯ u_0 \}\]

$(I_u)_{u ∈ {1,2}^ℕ}$

Si $u \neq u’$ : Soit $n_0$ tq $u_{n_0} \neq u’_{n_0}$ :

\[\vert I_u ∩ I_{u'}\vert \leq n_0\]

EX 9

  • À toute fonction $f ∈ ℕ^ℕ$, on associe de manière injective le réel \(\sum\limits_{i ∈ ℕ} f(i) 10^{-i}\)

  • À tout réel $r = \sum\limits_{i ∈ ℕ} a_i 10^{-i}$, on associe de manière injective la fonction $f ∈ ℕ^ℕ$ définie par : \(∀i∈ℕ, f(i) = a_i\)

EX 10

1) On a : $mn’ < nm’$, donc $mn’ + mn < nm’ + mn$ (inégalité de gauche) et $mn’ + m’n’ < nm’ + m’n’$ (inégalité de droite).

2) Par récurrence (trivialement fondée) : si c’est le cas à l’étape $k$, montrons que ça le reste à l’étape $k+1$.

Si $nm’ - mn’ = 1$, alors on a bien $(m+m’)n - m(n+n’) = 1$, et $(n+n’)m’ - n’(m+m’) = 1$.

3) Il y a une relation de Bézout entre numérateur et dénominateur.

4)

$1 = nm’ - mn’ = n(m’ - m) - m(n’-n) = m’(n - n’) - n’(m-m’)$

$m’q-n’p \geq 1 = nm’ - mn’$

$np-mq \geq 1 = nm’ - mn’$

\[n+n'+m+m' \leq (n+m)\times 1 + (n'+m')\times 1 \\ \leq (n+m)(m'q-n'p) + (n'+m')(np-mq) \\ = nm'q + mm'q - nn'p - mn'p + n'np + m'np -n'mq - m'mq \\ = (nm' - n'm)(p+q) \\ = p+q\]

5) $0/1 < p/q < 1/0$

Si $m/n < p/q < m’/n’$

  • Cas 1 : Si $p/q = (m+m’)/(n+n’)$ : OK
  • Cas 2 : Si $m/n < p/q < (m+m’)/(n+n’)$ : avec la Q4 :
    • D’une part : $n+n’+m+m’ \leq p + q$
    • D’autre part : $n+n’+m+m’ + m + n \leq p + q$

Donc : $\underbrace{n+n’+m+m}{u_k} \leq \underbrace{n+n’+m+m’ + m + n}{u_{k+1}} \leq p + q$

$u$ croît et est majorée ⟶ stationne (suite d’entiers), et forcément en $p/q$ (sinon on réitère le processus).

  • Cas 3 : idem.

5)

\[E_n = \{p/q \text{ obtenue à l'étape $n$}\}\]

donc

\(ℚ^*_+ = \bigcup\limits_{n ∈ ℕ} E_n\) est dénombrable.

Leave a comment