TD 2

EX1

1. Soit $n\ge 1$.

Mq $(\genfrac{}{}{0ex}{}{3n}{3})=3(\genfrac{}{}{0ex}{}{n}{3})+6n(\genfrac{}{}{0ex}{}{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(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{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 ${𝕌}^{+}\stackrel{\scriptscriptstyle\mathrm{def}}{=}z\in 𝕌|Im(z)\ge 0$

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

$f\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{\begin{array}{l}A⟶{𝕌}^{+}\\ z\mapsto \{\begin{array}{l}z\text{ si }z\in {𝕌}^{+}\\ -z\text{ sinon}\end{array}\end{array}$ vérifierait $f(A)\supset {𝕌}^{+}$, ce qui est absurde, par définition de $A$ (puisque $1/2\le mes(f(A))<mes(A)$ ).

EX 3

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

(Considérons $f_{m_i}\stackrel{\scriptscriptstyle\mathrm{def}}{=}\{\begin{array}{l}\{m_1,\cdots ,m_{n+1}\}\mathrm{\setminus }\{m_i\}⟶⟦0,m_i-1⟧\\ m\mapsto m\mathrm{mod}{m}_i\end{array}$)

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

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 $\mathbb{N}$ peut être associée de manière bi-univoque à l’entier :

$\prod _{i\in F}{p}_i$ où $p_j$ est le $j$-ème nombre premier.

M2. ${𝒫}_f(\mathbb{N})=\bigcup _{k\in \mathbb{N}}𝒫(⟦0,k⟧)$

EX 5

Tout nombre décimal $d=\sum _{F\subseteq {𝒫}_f(\mathbb{Z})}{a}_i{10}^i$ :

M1. peut-être associé de manière injective à une suite finie $(a_i{)}_{F\subseteq {𝒫}_f(\mathbb{Z})}\in ⟦0,9{⟧}^{(\mathbb{N})}$ (en ignorant les développement cofinaux à 9).

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

$\prod _{i\in 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\stackrel{\scriptscriptstyle\mathrm{def}}{=}|𝛴|$, ${𝛴}^{\ast }$ est équipotent à $⟦1,n{⟧}^{(\mathbb{N})}$

Argument diagonal de Cantor pour ${𝛴}^{\infty }$.

EX 7

M1. Argument diagonal de Cantor.

M2. Bijection avec $𝒫(\mathbb{N})$ en associant à $a\in {0,1}^{\mathbb{N}}$ 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\in {\mathbb{Q}}^{\mathbb{N}}\simeq ({\mathbb{N}}^2{)}^{\mathbb{N}}\simeq {\mathbb{N}}^{\mathbb{N}}$ tendant vers $r$ (car $\mathbb{Q}$ est dense dans $ℝ$).

Or, ${\mathbb{N}}^{\mathbb{N}}$ s’injecte dans l’ensemble des parties de la forme $p_i^j$, où $p_i$ est le $i$-ème nombre premier (à toute $f\in {\mathbb{N}}^{\mathbb{N}}$, on associe la partie $𝛷(f)\stackrel{\scriptscriptstyle\mathrm{def}}{=}{p_i^{f(i)}}_{i\in \mathbb{N}}$ , et réciproquement).

Alors $𝛷({\mathbb{N}}^{\mathbb{N}})\subseteq \mathbb{N}$ convient, puisque deux parties égales correspondent à des réels égaux, et $𝛷({\mathbb{N}}^{\mathbb{N}})\simeq {\mathbb{N}}^{\mathbb{N}}$ dans lequel s’injecte $ℝ$ (et qui est donc non dénombrable).

$u\in {1,2}^{\mathbb{N}}$

$(I_u{)}_{u\in {1,2}^{\mathbb{N}}}$

Si $u\ne u^{\prime }$ : Soit $n_0$ tq $u_{n_0}\ne u_{n_0}^{\prime }$ :

EX 9

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

• À tout réel $r=\sum _{i\in \mathbb{N}}{a}_i{10}^{-i}$, on associe de manière injective la fonction $f\in {\mathbb{N}}^{\mathbb{N}}$ définie par : $\forall i\in \mathbb{N},f(i)=a_i$

EX 10

1) On a : $m{n}^{\prime }<n{m}^{\prime }$, donc $m{n}^{\prime }+mn<n{m}^{\prime }+mn$ (inégalité de gauche) et $m{n}^{\prime }+m^{\prime }{n}^{\prime }<n{m}^{\prime }+m^{\prime }{n}^{\prime }$ (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 $n{m}^{\prime }-m{n}^{\prime }=1$, alors on a bien $(m+m^{\prime })n-m(n+n^{\prime })=1$, et $(n+n^{\prime })m^{\prime }-n^{\prime }(m+m^{\prime })=1$.

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

4)

$1=n{m}^{\prime }-m{n}^{\prime }=n(m^{\prime }-m)-m(n^{\prime }-n)=m^{\prime }(n-n^{\prime })-n^{\prime }(m-m^{\prime })$

$m^{\prime }q-n^{\prime }p\ge 1=n{m}^{\prime }-m{n}^{\prime }$

$np-mq\ge 1=n{m}^{\prime }-m{n}^{\prime }$

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

Si $m/n<p/q<m^{\prime }/n^{\prime }$

• Cas 1 : Si $p/q=(m+m^{\prime })/(n+n^{\prime })$ : OK
• Cas 2 : Si $m/n<p/q<(m+m^{\prime })/(n+n^{\prime })$ : avec la Q4 :
  • D’une part : $n+n^{\prime }+m+m^{\prime }\le p+q$
  • D’autre part : $n+n^{\prime }+m+m^{\prime }+m+n\le 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)

donc

${\mathbb{Q}}_{+}^{\ast }=\bigcup _{n\in \mathbb{N}}{E}_n$ est dénombrable.