\documentclass[titlepage]{article}%
\usepackage{mdwlist}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amssymb}
\usepackage{color}
\usepackage{tikz} 
\usepackage[mathscr]{euscript}
\usepackage{pstricks,pstricks-add,pst-node,pst-tree,pst-eucl}
\usepackage{multicol}
\usepackage{enumitem} 

\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{CSTFile=LaTeX article (bright).cst}
%TCIDATA{Created=Saturday, October 04, 2008 11:24:41}
%TCIDATA{LastRevised=Friday, September 22, 2017 16:57:15}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="General\Document Rombaldi">}
%TCIDATA{Language=French}
\def\red{\textcolor{red}}
\def\blue{\textcolor{blue}}
\voffset=-3cm \hoffset=-2.5cm \textheight=26cm \textwidth=18cm
\parindent=5mm
\newtheorem{theorem}{Th\'{e}or\`{e}me}
\newtheorem{corollary}[theorem]{Corollaire}
\newtheorem{definition}[theorem]{D\'{e}finition}
\newtheorem{example}[theorem]{Exemple}
\newtheorem{exercise}[theorem]{Exercice}
%\newtheorem{lemme}[theorem]{Lemme}
%\renewcommand{\thelemme}{\empty{}}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Probl\`{e}me}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remarque}
\newtheorem{solution}[theorem]{Solution}
%\newenvironment{proof}[1][D\'{e}monstration]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}

\newtheorem*{lemme*}{Lemme}
\newtheorem{lemme}{Lemme}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

\def\red{\textcolor{red}}
\def\blue{\textcolor{blue}}

\begin{document}


\centerline{\Large \bf Ensembles \'equipotents (cardinaux ?)}

\bigskip 
\noindent
Emmanuel et \'Eric se retrouvent au bistrot. 
Emmanuel demande : \\ 
\guillemotleft Sais-tu comparer les tailles de diff\'erents ensemble ? \\ 
- Bien s\^ur : \`a la table de vieux, l\`a-bas, il y a trois personnes ; 
\`a l'autre table, plus loin, il y a six jeunes ; ça fait plus. \\ 
- Effectivement. Et \`a cette table-ci, on peut comparer le nombre de 
verres et le nombre de personnes attabl\'ees ? \\
- Of course : il y en a autant, car chaque personne a exactement un 
verre devant elle. \\ 
- Et si je compare les nombres entiers avec les nombres entiers pairs ? \\
- Facile : les nombres entiers pairs sont en particulier entiers, 
donc il y au moins autant d'entiers que d'entiers pairs ; mais je n'ai 
pas tous les entiers en ne prenant que les entiers pairs ; donc il y a 
un plus grand nombre d'entiers que d'entiers pairs. \\ 
- Certes. Et ce nombre est infini. Mais, comme pour les verres et 
les convives, \`a chaque entier, je peux faire correspondre un entier 
pair, qui ne correspond qu'\`a lui : regarde ce dessin\dots\guillemotright


\begin{center}
\begin{pspicture}(1,1)(7,5)
		\psellipse(3,3)(1,2)
		\psellipse(6,3)(1,2)
		
		\rput(3,4.5){$0$}
		\rput(3,3.5){$1$}
		\rput(3,2.5){$2$}
		\rput(3,2){\vdots}
		
		\rput(6,4.5){$0$}
		\rput(6,3.5){$2$}
		\rput(6,2.5){$4$}
		\rput(6,2){\vdots}
		
		\psline[linearc=3]{<->}(3.2,4.5)(4.5,5)(5.8,4.5)
		\psline[linearc=3]{<->}(3.2,3.5)(4.5,4)(5.8,3.5)
		\psline[linearc=3]{<->}(3.2,2.5)(4.5,3)(5.8,2.5)
		
		
	\end{pspicture}
\end{center}
\noindent	
\'Eric : \guillemotleft Mais alors, il y a autant d'entiers que d'entiers pairs !
\guillemotright

Ce proc\'ed\'e a \'et\'e introduit par Georg Cantor\footnote{Note historique} 
pour \guillemotleft mesurer la taille\guillemotright des ensembles infinis. 
On dit (en suivant la terminologie de Cantor) que deux ensembles $E$ et $F$  
ont \emph{m\^eme cardinal} s'il existe une \emph{bijection} de $E$ sur $F$, 
c'est-\`a-dire une application $f : E \rightarrow F$ telle que : 
$$
\forall y \in F, \, \exists\, ! \, x \in E, f(x) = y .
$$

\subsection*{Partie A. G\'en\'eralit\'es sur les bijections}
\noindent
Soit $E$, $F$, $G$ des ensembles. 

\begin{enumerate}
\item Soit $f$ une application de $E$ dans $F$. 
Montrer que $f$ est une bijection (de $E$ sur $F$) si et seulement si \\
(i) $\forall x,x' \in E$, $f(x)=f(x') \Rightarrow x=x'$, \\
et \\
(ii) $\forall y \in F, \exists x \in E, y=f(x)$.  
\end{enumerate}
Lorsque l'application $f$ v\'erifie (i), on dit qu'elle est \emph{injective} (de $E$ dans $F$) ; 
v\'erifie (ii), on dit qu'elle est \emph{surjective} (de $E$ sur $F$). 
\begin{enumerate}[resume]
\item Soit $f$ une bijection de $E$ sur $F$.
\begin{enumerate}
\item Montrer qu'il existe une application $g$ de $F$ dans $E$ telle que $f \circ g = \mbox{id}_F$ et $g \circ f = \mbox{id}_E$. 
\item Montrer qu'il n'existe qu'une seule telle application $g$. 
On l'appelle \emph{application r\'eciproque de $f$} 
(ou simplement \emph{r\'eciproque de $f$}, et on la note $f^{-1}$ (attention ! ne pas confondre 
avec une possible application $1/f$). 
\end{enumerate}
\item R\'eciproquement, montrer que si $f : E \rightarrow F$ et 
$g : F \rightarrow E$ sont telles que $f \circ g = \mbox{id}_F$ 
et $g \circ f = \mbox{id}_E$, alors $f$ et $g$ sont des bijections. 
\end{enumerate}
Noter que les r\'esultats des questions 2 et 3  justifient qu'on utilise l'expression \guillemotleft $E$ et $F$ ont 
m\^eme cardinal\guillemotright, o\`u $E$ et $F$ jouent des r\^oles sym\'etriques.  

\begin{enumerate}[resume]
\item Montrer que si $E$ et $F$ ont m\^eme cardinal, et si $F$ et $G$ ont m\^eme cardinal, 
alors $E$ et $G$ ont m\^eme cardinal.
\end{enumerate}

\subsection*{Partie B. Premiers exemples}

\begin{enumerate}
\item Montrer qu'il existe une bijection entre $[0;1]$ et $[0;2]$, 
c'est-\`a-dire que $[0;1]$ et $[0;2]$ ont m\^eme cardinal. \\
Montrer \'egalement que pour tous $a,b,c,d\in\R$ tels que 
$a<b$ et $c<d$, $[a;b]$ et $[c;d]$ ont m\^eme cardinal 
(on pourra le montrer directement, ou bien utiliser la question pr\'ec\'edente).  
\item Montrer que $]0;1[$ et $\mathbb{R}$ ont m\^eme cardinal. 
\item Montrer que l'application $f$ suivante est une bijection 
de $[0;1]$ sur $[0;1[$ (on commencera par donner l'allure 
de son graphe) : 
$$
f : 
\begin{array}[t]{ccl}
[0;1] & \rightarrow & [0;1[ \\
x & \mapsto & 
\left\{
\begin{array}{cl}
\frac{x}{2} & \mbox{ s'il existe } n\in\N 
\mbox{ tel que } x = \frac{1}{2^n}, \\
x & \mbox{ sinon.} 
\end{array}
\right.
\end{array}
$$
Indication : 
d\'efinir, de la m\^eme fa{\c c}on que $f$ est d\'efinie, 
son application r\'eciproque. 
\end{enumerate}

\subsection*{Partie C. Cardinaux des ensembles finis}
\noindent
Lorsque $E$ est un ensemble, on dit que \emph{$E$ est fini} 
si : $E$ est l'ensemble vide, ou il existe $n\in\N^*$ et une bijection 
de $E$ sur $\{1,\dots,n\}$. 

\begin{enumerate}
\item Soit $n,n'\in\N^*$. Montrer que, s'il existe 
une bijection de $\{1,\dots,n\}$ sur $\{1,\dots,n'\}$, alors $n=n'$. 
\suspend{enumerate}
Ainsi, lorsque $E$ est un ensemble fini non vide, il existe un unique entier 
$n\in\N^*$ tel que $E$ soit en bijection avec  $\{1,\dots,n\}$. 
Cet entier (le \og nombre d'\'el\'ements\fg{} de $E$) est 
appel\'e le \emph{cardinal de $E$}, et on le note Card$(E)$. On dit aussi que 
l'ensemble vide a pour cardinal 0 : Card$(\emptyset)=0$.
\resume{enumerate}
\item Soit $E$ un ensemble fini et $F$ un sous-ensemble de $E$. Montrer que :
\begin{enumerate}
\item $F$ est fini, et Card$(F) \leq$ Card$(E)$ ;
\item Card$(F) =$ Card$(E)$ si et seulement si $E=F$. 
\end{enumerate}
\suspend{enumerate}
Un ensemble $E$ sera dit \emph{infini} s'il n'est pas fini.  
\resume{enumerate}
\item Montrer que $\N$ est infini. 
\item \blue{Montrer que tout ensemble en bijection avec un ensemble infini 
est lui-m\^eme infini.} 
\item \blue{Montrer que tout ensemble contenant un ensemble infini 
est lui-m\^eme infini.} 
\end{enumerate}

\subsection*{Partie D. Ensembles d\'enombrables}
\noindent
Un ensemble $E$ est dit \emph{d\'enombrable} s'il a m\^eme cardinal que $\N$. \\
Intuitivement, le fait que $E$ soit d\'enombrable signifie qu'on peut num\'eroter ses \'el\'ements. 

\begin{enumerate}
\item En s'appuyant sur le dessin ci-dessous, construire (par des formules 
explicites, semblables \`a celles de B-3) une bijection de $\mathbb{Z}$ sur $\N$. 


	\begin{center}
	\psset{xunit=1cm,yunit=1cm,algebraic=true,dotstyle=*,dotsize=5pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
	\begin{pspicture}(-1,-4)(7,4)
		
		%\psline{->}(0,-3.5)(0,3.5)
		%\psline{->}(1,0)(7.5,0)
		\psellipse(0,0)(1,4)
		\rput(0,-3){-3}
		\rput(0,-2){-2}
		\rput(0,-1){-1}
		\rput(0,0){0}
		\rput(0,1){1}
		\rput(0,2){2}
		\rput(0,3){3}
		\rput(0,3.5){\vdots}
		\rput(0,-3.5){\vdots}
				
		%\psdots(0,0)(0,1)(0,2)(0,3)(0,-1)(0,-2)(0,-3)
		%\psdots(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)(7,0)
		
		\psline[linearc=2]{<->}(0.2,0.1)(1.5,1)(2.9,0.1)
		\psline[linearc=4.6]{<->}(0.2,1)(2.5,1.5)(4.9,0.1)
		\psline[linearc=6.6]{<->}(0.2,2)(3.5,2.5)(6.9,0.1)
		\psline[linearc=8.6]{<->}(0.2,3)(4.5,3.5)(8.9,0.1)
		
		\psline[linearc=3.6]{<->}(0.2,-1)(2,-1.5)(3.9,-0.1)
		\psline[linearc=5.6]{<->}(0.2,-2)(3,-2.5)(5.9,-0.1)
		\psline[linearc=7.6]{<->}(0.2,-3)(4,-3.5)(7.9,-0.1)
		
		\rput(-1,3){\Large{$\mathbb{Z}$}}
		\rput(9,1){\Large{$\mathbb{N}$}}
		
		
		
		\psellipse(6,0)(4,1)
		\rput(3,0){$0$}
		\rput(4,0){$1$}
		\rput(5,0){$2$}
		\rput(6,0){$3$}
		\rput(7,0){$4$}
		\rput(8,0){$5$}
		\rput(9,0){$6$}
		\rput(9.5,0){\dots}
				
		
	\end{pspicture}
	\end{center}







\item On va montrer que l'application 
$$
f : 
\begin{array}[t]{ccl}
\N^2 & \rightarrow & \N \\
(m,n) & \mapsto & \frac12(m+n)(m+n+1)+n 
\end{array}
$$
est une bijection. Remarquons que cela correspond au fait que le dessin suivant donne 
une num\'erotation des \'el\'ements de $\N^2$ : 

	\begin{center}
		\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=*,dotsize=5pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
	\begin{pspicture}
	
	\begin{psclip}{\psframe[linestyle=none](-0.5,-0.7)(6.5,6.5)}	\psgrid[griddots=10,gridcolor=black,gridwidth=1pt,gridlabels=0,subgriddiv=1](0,0)(6.5,6.5)
		\psaxes{->}(0,0)(6.5,6.5)
		\psline[linecolor=red]{->}(1,0)(0,1)
		\psline[linecolor=red]{->}(2,0)(0,2)
		\psline[linecolor=red]{->}(3,0)(0,3)
		\psline[linecolor=red]{->}(4,0)(0,4)
		\psline[linecolor=red]{->}(5,0)(0,5)
		\psline[linecolor=red]{->}(6,0)(3,3)
		\psline[linestyle=dashed,linecolor=red]{->}(3,3)(1.5,4.5)
		
	
	\psdots[linecolor=blue](0,0)(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)	
	\psdots[linecolor=blue](0,1)(1,1)(2,1)(3,1)(4,1)(5,1)
	\psdots[linecolor=blue](0,2)(1,2)(2,2)(3,2)(4,2)
	\psdots[linecolor=blue](0,3)(1,3)(2,3)(3,3)
	\psdots[linecolor=blue](0,4)(1,4)(2,4)
	\psdots[linecolor=blue](0,5)(1,5)
	\psdot[linecolor=blue](0,6)
	\end{psclip}
		\rput(6.7,0){$m$}
		\rput(0,6.7){$n$}
	\end{pspicture}
	\end{center}
	
\medskip
	
\begin{enumerate}
\item Pour prouver l'injectivit\'e de $f$, donnons-nous $(m,n)\in\N^2$ 
et $(m',n')\in\N^2$ tels que $f(m,n)=f(m',n')$. Posons $S=m+n$, $S'=m'+n'$. 
\begin{enumerate}
\item Montrer que $\frac12 S(S+1) \leq f(m,n) \leq \frac12 S'(S'+1)+S'$. 
\item Montrer par l'absurde que $S' \geq S$ : supposant $S'<S$, noter qu'alors 
$S'+1 \leq S$, et obtenir une contradiction avec i. 
\item En d\'eduire que $S=S'$. 
\item En utilisant que $f(m,n)=f(m',n')$, conclure. 
\end{enumerate}
\item Pour prouver la surjectivit\'e de $f$, c'est-\`a-dire : 
$$
\forall k\in\N, \, \exists (m,n)\in\N^2, \ k=f(m,n),
$$
proc\'edons par r\'ecurrence sur $k$ :   
\begin{enumerate}
\item initialiser la r\'ecurrence ; 
\item transmission de la propri\'et\'e : on s'appuie sur le dessin 
(voyez-vous comment ?) ; si $k\in\N$ s'\'ecrit $k=f(m,n)$ pour un 
certain couple $(m,n)\in\N^2$, calculer $f(m-1,n+1)$ si $m>0$, 
et calculer $f(n+1,0)$ si $m=0$.
\end{enumerate} 
\end{enumerate}
\item On montre ici que $\mathbb{Q}$ est d\'{e}nombrable. 
\begin{enumerate}
\item \blue{Montrer que $\mathbb{Q}$ est infini. } 
\item On montre ici que $\Q$ est en bijection avec une partie de $\N$. 
\begin{enumerate}
\item Soient $E$, $F$, $G$ des ensembles, et $f : E \rightarrow F$, 
$g : F \rightarrow G$. Montrer que si $f$ et $g$ sont injectives, alors 
$g \circ f$ l'est. 
\item Montrer que, si à tout nombre rationnel sous forme irréductible $\dfrac{p}{q}$, on associe $(p,q)$, on obtient une application injective de $\mathbb{Q}$ dans $\mathbb{Z}\times \mathbb{N}$.
\item En utilisant $i.$ et les résultats des questions $D.1$ et $D.2$, en déduire qu'il existe une application injective de $\mathbb{Q}$ dans $\mathbb{N}$.
\item En déduire que $\mathbb{Q}$ est en bijection avec une partie de $\mathbb{N}$.

\end{enumerate}
\item On considère $A$, une partie infinie de $\mathbb{N}$, et on va montrer qu'elle est en bijection avec $\mathbb{N}$. On rappelle que toute partie non vide $A$ de $\mathbb{N}$ admet un petit élément, noté $\min(A)$.

On définit une suite $(a_k)_{k\in \mathbb{N}}$ d'éléments de $A$ par $\left\lbrace
	\begin{array}{l}
		a_0=\min(A)\\
		a_{k+1}=\min(A\backslash\{a_0,\dots,a_k\})\\
	\end{array}
	\right.$


\begin{enumerate} 	
	\item Pourquoi la suite $(a_k)_{k\in \mathbb{N}}$ est-elle bien définie ?
	\item Montrer que pour tout $k\in\N$, $a_{k+1}>a_k$. 
	\item On d\'efinit l'application 
		$f:\begin{array}[t]{ccc}
			\mathbb{N}&\rightarrow & A \\
			k&\mapsto	& a_k\\
			\end{array}$ 
	(c'est la suite $(a_k)_{k\in \mathbb{N}}$ !). Montrer que : 
		\begin{itemize}
			\item l'application $f$ est injective ; 
			\item pour tout $k\in\N$, $f(k) \geqslant k$ ;
			\item la fonction $f$ a pour limite $+\infty$ en $+\infty$.
		\end{itemize}
	\item Soit $a\in A$ avec $a\geqslant a_0$. Montrer qu'il existe un unique 
	$k\in \mathbb{N}$ tel que $a_k \leqslant a <a_{k+1}$.\\
	\emph{Indication} : consid\'erer l'ensemble $\{\ell\in \mathbb{N}\ |\ a_{\ell+1}>a\}$, 
	montrer qu'il est non vide\dots
\item On montre que $f$ est surjective en montrant, si $a \in A$, que $a=a_k$ 
pour un certain $k\in\N$ : $a \geq a_0$, et 
\begin{enumerate} 
\item si $a=a_0$, OK ; 
\item sinon, $\exists k\in\N^*$, $a_{k-1} \leq a < 1$ (par ``$a_k \geq k$''), 
et alors $a=a_{k-1}$. 
\end{enumerate}
\end{enumerate}
\item Conclure : montrer que $\Q$ est d\'enombrable. 
\end{enumerate}
\item Un ensemble d\'enombrable priv\'e d'un sous-ensemble 
fini est encore d\'{e}nombrable. 
L'union d'un ensemble d\'enombrable et d'un ensemble fini 
est encore d\'{e}nombrable. 
Toute union finie d'ensembles d\'enombrables est d\'enombrable. 
Toute union d\'enombrable d'ensembles finis est d\'enombrable. 
Toute union d\'enombrable d'ensembles d\'enombrables est d\'enombrable ?
\end{enumerate}

En fait, infini ssi en bijection avec lui-m\^eme union un singleton\dots

\subsection*{Partie E. L'ensemble des r\'eels est-il d\'enombrable ?}
\noindent
Historique : hypoth\`ese du continu

Avec $[0,1[ = \{ a_n, n\in\N\}$ ; d\'eveloppements propres en base 10\dots 

{\bf dessin} du proc\'ed\'e diagonal ; $b_n = 0$ si $a_{n,n}\neq0$, 1 sinon

\bigskip 

{\bf \large Partie F. Le plan et la droite ont-elles m\^eme cardinal ?}

Bijection de $\left[  0,1\right]  ^{2}$ sur $\left[  0,1\right]
.$\newline Sol. On utilise le d\'{e}veloppement d\'{e}cimal illimit\'{e} avec
$0,123=0,1299999...$ qui est unique. \`{A} $\left(  x,y\right)  =\left(
0,x_{1}x_{2}...;0.y_{1}y_{2}...\right)  \in\left[  0,1\right]  ^{2},$ on
associe $z=0,z_{1}z_{2}...$ o\`{u} $z_{2n}=x_{n}$ et $z_{2n-1}=y_{n}.$

\bigskip
\bigskip3
\bigskip
\bigskip

\begin{enumerate}
\item On d\'{e}signe par $f$ l'application d\'{e}finie sur $\mathbb{N}%
^{2}=\mathbb{N}\times\mathbb{N}$ par :%
\[
\forall\left(  n,m\right)  \in\mathbb{N}^{2},\;f\left(  n,m\right)
=2^{n}3^{m}%
\]
Montrer que $f$ est injective. Il r\'{e}sulte que $\mathbb{N}^{2}$ est en
bijection avec le sous ensemble $f\left(  \mathbb{N}^{2}\right)  $ de
$\mathbb{N}.$ Ce r\'{e}sultat se traduit en disant que $\mathbb{N}^{2}$ est
d\'{e}nombrable.\newline Sol. L'\'{e}galit\'{e} $f\left(  n,m\right)
=f\left(  n^{\prime},m^{\prime}\right)  $ avec $\left(  n,m\right)  $ et
$\left(  n^{\prime},m^{\prime}\right)  $ dans $\mathbb{N}^{2}$ \'{e}quivaut
\`{a} $2^{n}3^{m}=2^{n^{\prime}}3^{m^{\prime}}$ et l'unicit\'{e} de la
d\'{e}composition en facteurs premiers d'un entier naturel non nul nous dit
que $\left(  n,m\right)  =\left(  n^{\prime},m^{\prime}\right)  .$
L'application $f$ est donc injective de $\mathbb{N}^{2}$ dans $\mathbb{N}$ et
bijective de $\mathbb{N}^{2}$ dans $f\left(  \mathbb{N}^{2}\right)
\subset\mathbb{N}.$

\item Montrer que l'application $f:\left(  n,m\right)  \mapsto2^{n+m+1}+2^{m}$
est injective de $\mathbb{N}^{2}$ dans $\mathbb{N}.$\newline Sol.
L'\'{e}galit\'{e} $f\left(  n,m\right)  =f\left(  n^{\prime},m^{\prime
}\right)  $ avec $\left(  n,m\right)  $ et $\left(  n^{\prime},m^{\prime
}\right)  $ dans $\mathbb{N}^{2}$ \'{e}quivaut \`{a} $2^{m}\left(
2^{n+1}+1\right)  =2^{m^{\prime}}\left(  2^{n^{\prime}+1}+1\right)  .$ Si
$m>m^{\prime},$ on a alors $2^{m-m^{\prime}}\left(  2^{n+1}+1\right)
=2^{n^{\prime}+1}+1$ qui est \`{a} la fois pair et impair, ce qui est
impossible. De mani\`{e}re analogue, on voit que $m^{\prime}>m$ est
impossible. On a donc $m=m^{\prime}$ et $2^{n+1}+1=2^{n^{\prime}+1}+1,$ ce qui
\'{e}quivaut \`{a} $n=n^{\prime}.$ L'application $f$ est donc injective.

\item Montrer que l'application $\varphi:\left(  n,m\right)  \mapsto
2^{n}\left(  2m+1\right)  -1$ est bijective de $\mathbb{N}^{2}$ sur
$\mathbb{N}.$\newline Sol. L'\'{e}galit\'{e} $\varphi\left(  n,m\right)
=\varphi\left(  n^{\prime},m^{\prime}\right)  $ avec $\left(  n,m\right)  $ et
$\left(  n^{\prime},m^{\prime}\right)  $ dans $\mathbb{N}^{2}$ \'{e}quivaut
\`{a} $2^{n}\left(  2m+1\right)  =2^{n^{\prime}}\left(  2m^{\prime}+1\right)
.$ Si $n>n^{\prime},$ on a alors $2^{n-n^{\prime}}\left(  2m+1\right)
=2m^{\prime}+1$ qui est \`{a} la fois pair et impair, ce qui est impossible.
De mani\`{e}re analogue, on voit que $n^{\prime}>n$ est impossible. On a donc
$n=n^{\prime}$ et $2m+1=2m^{\prime}+1,$ ce qui \'{e}quivaut \`{a}
$m=m^{\prime}.$ L'application $\varphi$ est donc injective.\newline Soit
$r\in\mathbb{N}.$ Si $r=0,$ on a alors $r=\varphi\left(  0,0\right)  .$ Si
$n\in\mathbb{N}^{\ast},$ alors $n+1\geq2$ et cet entier se d\'{e}compose en
facteurs premiers, ce qui s'\'{e}crit $r+1=2^{n}\left(  2m+1\right)  $ avec
$\left(  n,m\right)  $ dans $\mathbb{N}^{2}.$ L'application $\varphi$ est donc
surjective et en d\'{e}finitive bijective.

\item Montrer que l'application $\varphi:\left(  n,m\right)  \mapsto\dfrac
{1}{2}\left(  n+m\right)  \left(  n+m+1\right)  +m$ est bijective de
$\mathbb{N}^{2}$ sur $\mathbb{N}.$\newline Sol. On remarque d'abord que pour
tout $\left(  n,m\right)  \in\mathbb{N}^{2},$ les entiers $n+m$ et $n+m+1$
sont de parit\'{e}s diff\'{e}rentes, donc $\dfrac{1}{2}\left(  n+m\right)
\left(  n+m+1\right)  $ est entier et $\varphi$ est bien \`{a} valeurs dans
$\mathbb{N}.$\newline Supposons que $\varphi\left(  n,m\right)  =\varphi
\left(  n^{\prime},m^{\prime}\right)  $ avec $\left(  n,m\right)  $ et
$\left(  n^{\prime},m^{\prime}\right)  $ dans $\mathbb{N}^{2}.$ En notant
$N=n+m$ et $M=n^{\prime}+m^{\prime},$ on a $M\geq m^{\prime}$ et :%
\[
\dfrac{N\left(  N+1\right)  }{2}\leq\varphi\left(  n,m\right)  =\varphi\left(
n^{\prime},m^{\prime}\right)  \leq\dfrac{M\left(  M+1\right)  }{2}+M
\]
ce qui entra\^{\i}ne
\[
M^{2}+3M=\left(  M+\dfrac{3}{2}\right)  ^{2}-\dfrac{9}{4}\geq N^{2}+N=\left(
N+\dfrac{1}{2}\right)  ^{2}-\dfrac{1}{4}%
\]
soit :%
\[
\left(  2M+3\right)  ^{2}-9\geq\left(  2N+1\right)  ^{2}-1
\]
ou encore :%
\[
\left(  2M+3\right)  ^{2}-\left(  2N+1\right)  ^{2}=\left(  2\left(
M+N\right)  +4\right)  \left(  2\left(  M-N\right)  +2\right)  \geq8
\]
c'est-\`{a}-dire :%
\[
\left(  M+N+2\right)  \left(  M-N+1\right)  \geq2
\]
et n\'{e}cessairement $M\geq N.$ Comme $M$ et $N$ jouent des r\^{o}les
sym\'{e}triques, on a aussi $M\leq N$ et $M=N.$ De $\varphi\left(  n,m\right)
=\varphi\left(  n^{\prime},m^{\prime}\right)  ,$ on d\'{e}duit alors que
$m=m^{\prime}$ puis $n=n^{\prime}.$ L'application $\varphi$ est donc injective.

\item Bijection de $\left]  0,1\right]  $ sur $\left]  0,1\right[  .$\newline
Sol. Pour $x\in\left]  0,1\right]  ,$ $f\left(  x\right)  =\left\{
\begin{array}
[c]{l}%
\dfrac{x}{2}\text{ si }x=2^{-n}\text{ avec }n\in\mathbb{N}\\
x\text{ sinon}%
\end{array}
\right.  .$

\item Bijection de $\left[  0,1\right]  ^{2}$ sur $\left[  0,1\right]
.$\newline Sol. On utilise le d\'{e}veloppement d\'{e}cimal illimit\'{e} avec
$0,123=0,1299999...$ qui est unique. \`{A} $\left(  x,y\right)  =\left(
0,x_{1}x_{2}...;0.y_{1}y_{2}...\right)  \in\left[  0,1\right]  ^{2},$ on
associe $z=0,z_{1}z_{2}...$ o\`{u} $z_{2n}=x_{n}$ et $z_{2n-1}=y_{n}.$

\item $\mathbb{R}$ n'est pas d\'{e}nombrable.\newline Sol. Il suffit de
montrer que $\left[  0,1\right]  $ n'est pas d\'{e}nombrable. Supposons qu'il
existe une application bijective $\varphi:\mathbb{N}\rightarrow\left[
0,1\right]  .$ En coupant $I=\left[  0,1\right]  $ en trois segments de
m\^{e}me longueur, il en existe un que l'on note $I_{0}$ qui ne contient pas
$\varphi\left(  0\right)  .$ On coupe ensuite $I_{0}$ en trois segments de
m\^{e}me longueur en notant $I_{1}$ l'un de ces segments qui ne contient par
$\varphi\left(  1\right)  .$ Par r\'{e}currence, on construit ainsi une suite
de segments embo\^{\i}t\'{e}s $\left(  I_{n}\right)  _{n\in\mathbb{N}}$ telle
que, pour tout $n\in\mathbb{N},$ $I_{n}$ ne contient pas $\varphi\left(
n\right)  $ et $I_{n}$ est de longueur $\dfrac{1}{3^{n}},$ on d\'{e}duit alors
du th\'{e}or\`{e}me des segments embo\^{\i}t\'{e}s que $%
%TCIMACRO{\dbigcap \limits_{n\in\mathbb{N}}}%
%BeginExpansion
{\displaystyle\bigcap\limits_{n\in\mathbb{N}}}
%EndExpansion
I_{n}=\left\{  x\right\}  $ avec $x\in\left[  0,1\right]  $ et $x\neq
\varphi\left(  n\right)  $ pour tout $n\in\mathbb{N},$ ce qui contredit la
d\'{e}finition de $\varphi.$\newline Si $\mathbb{R}$ est d\'{e}nombrable il en
est alors de m\^{e}me de l'ensemble :
\[
A=\left\{  x=0,a_{1}a_{2}\cdots a_{n}\cdots\mid\forall k\geq1,\;0\leq
a_{k}\leq8\right\}
\]
On peut donc \'{e}crire que :
\[
A=\left\{  x_{p}=0,a_{p,1}a_{p,2}\cdots a_{p,n}\cdots\mid p\in\mathbb{N}%
^{\ast},\;\forall k\geq1,\;0\leq a_{p,k}\leq8\right\}
\]
Le r\'{e}el $b=0,b_{1}b_{2}\cdots b_{n}\cdots$ d\'{e}fini par $0\leq b_{i}%
\leq8$ et $b_{i}\neq a_{ii}$ pour tout $i\in\mathbb{N}^{\ast}$ est dans $A$ et
distinct de tous les $x_{p}$ ($b=x_{p}$ entra\^{\i}ne $b_{p}=x_{p,p}$) ce qui
est contradictoire. En d\'{e}finitive $\mathbb{R}$ est non d\'{e}nombrable.
\end{enumerate}







\end{document}