 \documentclass{beamer}

%\input{beamer_settings}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[frenchb]{babel}

\usepackage{amsfonts,latexsym,amsfonts,amsmath,amssymb,amsthm,amscd,stmaryrd,amstext,amscd}
\usepackage{array}
\usepackage{stmaryrd,mathrsfs}

\usepackage{bbm}
\usepackage{yhmath}

\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{arrows,automata,petri,positioning}

\usetikzlibrary{decorations.pathreplacing}
\usetikzlibrary{decorations.pathmorphing}
\usetikzlibrary{chains,fit,shapes}
\usetikzlibrary{patterns}

%\usetheme{metropolis}           % Use metropolis theme
\usetheme{Boadilla}
\usecolortheme{seahorse}
%\mode<presentation>
%{
 % \usetheme{Darmstadt}
  %\useoutertheme{infolines}
%}

%\usecolortheme{whale}
%\usecolortheme{orchid}
%\useinnertheme[shadow]{rounded}
%\useoutertheme{infolines}

\makeatother
\setbeamertemplate{footline}
{
  \leavevmode%
  \hbox{%
  \begin{beamercolorbox}[wd=.45\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
    \usebeamerfont{author in head/foot}\insertsection
      \end{beamercolorbox}%
  \begin{beamercolorbox}[wd=.45\paperwidth,ht=2.25ex,dp=1ex,center]{title in head/foot}%
    \usebeamerfont{title in head/foot}\insertsubsection
      \end{beamercolorbox}
      \begin{beamercolorbox}[wd=.1\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
    \usebeamerfont{author in head/foot}
    \insertframenumber{} / \inserttotalframenumber\hspace*{1ex}
  \end{beamercolorbox}}%
  \vskip0pt%
}
\makeatletter


%\input{defs}
\definecolor{darkgreen}{rgb}{0,0.7,0}
\newcommand{\green}[1]{{\color{darkgreen}#1}}
\newcommand{\red}[1]{{\color{red}#1}}

\newcommand{\define}[1]{\textbf{#1}}%\index{#1}}
\newcommand{\card}[1]{\textrm{Card}\left(#1\right)}%\index{#1}}

\newcommand{\Cl}[1]{\mathbf{Cl}(#1)}
\newcommand{\Lang}{\mathcal{L}}
\newcommand{\M}{\mathbbm{M}}
\newcommand{\N}{\mathbbm{N}}
\newcommand{\Z}{\mathbbm{Z}}
\newcommand{\Q}{\mathbbm{Q}}
\newcommand{\R}{\mathbbm{R}}
\newcommand{\C}{\mathbbm{C}}
\newcommand{\G}{\mathbbm{G}}
\newcommand{\K}{\mathbbm{K}}

\renewcommand{\P}{\mathcal{P}}

\newcommand{\Rel}{\mathcal{R}}
\newcommand{\A}{\mathcal{A}}

\newcommand{\U}{\mathbbm{U}}
\newcommand{\V}{\mathbbm{V}}


%%%TIKZ
\newcommand{\Eset}{(-4,-1) rectangle (4,4)}
\newcommand{\Aset}{(0,0) ++(135:2) circle (2)}
\newcommand{\Bset}{(0,0) ++(45:2) circle (2)}
\newcommand{\Cset}{(0,0) ++(270:1) circle (2)}



\title{Cardinalité}

%\author{Bérénice Delcroix-Oger \and Ralph Matthes \and Martin Strecker}
\institute{Université de Toulouse}
\date{Année 2020/2021} 


\begin{document}

%======================================================================

\begin{frame}
  \titlepage
\end{frame}


%======================================================================

%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%



\section{Cardinalité des ensembles finis}


\begin{frame}
\begin{center}
\textcolor{magenta}{{\huge \sc Cardinalité des ensembles finis}}
\end{center}
\end{frame}


\subsection{Ensembles équipotents}

%-------------------------------------------------------------
\begin{frame}
\frametitle{Ensembles équipotents}


Soient $E=\{a,b,c,d\}$ et $F=\{1,2,3\}$. 
\begin{itemize}
\item Il existe une application surjective de $E$ sur $F$, mais pas d'application injective. 

\item Il existe application injective de $F$ sur $E$, mais pas d'application surjective. 
\end{itemize}

En fait, il n'y a pas assez d'éléments dans $F$ (ou trop peu dans $E$). Le cardinal d’un ensemble précise la notion de nombre d’éléments

\begin{block}{Ensemble de même cardinal}
Deux ensembles (fini ou non) sont \define{équipotents} ou de \define{même cardinal} s'il existe une bijection entre eux.
\end{block}
\end{frame}

%%%

\subsection{Cardinal d'un ensemble fini}

\begin{frame}
\frametitle{Cardinal d'un ensemble fini}

\begin{block}{Définition}
  Un ensemble $E$ est \define{fini} si $E=\emptyset$ ou si $\exists n\in\N^{\ast}$ tel que $E$ est en bijection avec $\{1,\dots,n\}$. Cet entier est unique, il est appelé le \define{cardinal} de $E$ noté $\card{E}$. Si $E=\emptyset$, on pose $\card{E}=0$.
\end{block}

\only<1>{Pour montrer que cet entier est définit de manière unique, on prouve la proposition suivante:

\begin{exampleblock}{Proposition}
\begin{itemize}
 \item S'il existe une application injective de $\{1,\dots,n\}$ dans $\{1,\dots,k\}$ alors $n\leq k$.
 \item S'il existe une application surjective de $\{1,\dots,n\}$ dans $\{1,\dots,k\}$ alors $n\geq k$.
 \item S'il existe une application bijection de $\{1,\dots,n\}$ dans $\{1,\dots,k\}$ alors $n= k$.
\end{itemize}
\end{exampleblock}}

\only<2>{Qui se traduit de la manière suivante avec les cardinaux.

\begin{exampleblock}{Proposition}
Soient $E$ et $F$ deux ensembles finis. On a:
\begin{itemize}
 \item Il existe une application injective de $E$ dans $F$ si et seulement si $\card{E}\leq\card{F}$. 
 \item Il existe une application surjective de $E$ dans $F$ si et seulement si $\card{E}\geq\card{F}$. 
 \item Il existe une application bijective de $E$ dans $F$ si et seulement si $\card{E}=\card{F}$. 
 \end{itemize}
\end{exampleblock}}
\end{frame}

%%%

\subsection{Principe des tiroirs}
\begin{frame}
\frametitle{Principe des tiroirs}
\begin{exampleblock}{Principe des tiroirs}
 Soient $E$ et $F$ deux ensembles finis non vides et $f:E\to F$ une application. Si $\card{E}>\card{F}$ alors il existe $x_1,x_2\in E$ tels que $f(x_1)=f(x_2)$.
\end{exampleblock}

Nombre moyen de cheveux: 150000

Nombre d'habitant à Paris: 2,2 million

Il y a au moins deux personnes à Paris qui ont exactement le même nombre de cheveux. 


\begin{exampleblock}<2>{Principe des tiroirs généralisé}
  Soient $E$ et $F$ deux ensembles finis non vides et $f:E\to F$ une application. Si $\card{E}>k\,\card{F}$ avec $k\in\N^{\ast}$ alors il existe une valeur de $f$ qui est répétée au moins $k+1$ fois.

\end{exampleblock}
\end{frame}

%%%

\section{Dénombrement}

\begin{frame}
\begin{center}
\textcolor{magenta}{{\huge \sc Dénombrement}}
\end{center}
\end{frame}

%%%
\subsection{Motivations}


\begin{frame}
\frametitle{Pourquoi dénombrer un ensemble fini?}
En informatique vous utiliserez la notion de dénombrement au moins dans les deux cas de figures suivants:
\begin{itemize}
 \item dénombrer le nombre de cas à analyser par un algorithme en vu d'étudier sa complexité;
 \item lorsqu'on tire au hasard un élément dans un univers finis $\Omega$ de manière équiprobable (c'est à dire que chaque élément à la même probabilité d'être tiré), la probabilité que cet élément soit dans l'ensemble $A\subseteq\Omega$ est $$\mathbf{P}(A)=\frac{\card{A}}{\card{\Omega}}.$$
\end{itemize}


\end{frame}

%%%

\subsection{Opération sur les ensembles}

\begin{frame}
\frametitle{Dénombrement et opérations sur les ensembles}

\begin{exampleblock}{Union}
\begin{small}
$$\card{A\cup B}=\card{A}+\card{B}-\card{A\cap B}$$
\only<2>{$$\card{A\cup B\cup C}=\card{A}+\card{B}+\card{C}-\card{A\cap B}$$
$$-\card{A\cap C}-\card{B\cap C}+\card{A\cap B\cap C}$$}
\end{small}
\vspace{-0.4cm}
\end{exampleblock}
\vspace{-0.7cm}
\begin{center}
\only<1>{
  \begin{tikzpicture}[scale=0.8]
 \draw[color=white] (-4,-3.5) rectangle (4,4);
\fill[opacity=0.5,red]  \Aset;
\fill[opacity=0.5,blue] \Bset;
\draw (-1.5,1.5) node{$A$};
\draw (1.5,1.5) node{$B$};
\node (a) at (1.9, 0.1) {$\times$};
\node (b) at (-1.9, 0.7) {$\times$};
\node (c) at (-2.1, 2.3) {$\times$};
\node (d) at (2, 2.5) {$\times$};
\node (e) at (0,0.8) {$\times$};
\node (f) at (-0.1, 1.8) {$\times$};
\node (g) at (2.3, 1.4) {$\times$};
\node (h) at (-1, 2.9) {$\times$};

\draw (a) node[right]{$a$};
\draw (b) node[right]{$b$};
\draw (c) node[right]{$c$};
\draw (d) node[right]{$d$};
\draw (e) node[right]{$e$};
\draw (f) node[right]{$f$};
\draw (g) node[right]{$g$};
\draw (h) node[right]{$h$};

\end{tikzpicture}
}

\only<2>{
 \begin{tikzpicture}[scale=0.8]
 \draw[color=white] (-4,-3.5) rectangle (4,4);
\fill[opacity=0.5,red]  \Aset;
\fill[opacity=0.5,blue] \Bset;
\fill[opacity=0.5,green] \Cset;
\draw (-1.5,1.5) node{$A$};
\draw (1.5,1.5) node{$B$};
\draw (270:1) node{$C$};
\node (a) at (1.2, 0.1) {$\times$};
\node (b) at (-1.9, 0.7) {$\times$};
\node (c) at (-2.1, 2.3) {$\times$};
\node (d) at (2, 2.5) {$\times$};
\node (e) at (0,0.6) {$\times$};
\node (f) at (-0.1, 1.8) {$\times$};
\node (g) at (2.3, 1.4) {$\times$};
\node (h) at (-1, 2.9) {$\times$};
\node (i) at (-1.3,0.2) {$\times$};
\node (j) at (-1.1, -0.9) {$\times$};
\node (k) at (1.4, -1.2) {$\times$};
\node (l) at (-0.6,0) {$\times$};
\node (m) at (0.2, -1.9) {$\times$};

\draw (a) node[right]{$a$};
\draw (b) node[right]{$b$};
\draw (c) node[right]{$c$};
\draw (d) node[right]{$d$};
\draw (e) node[right]{$e$};
\draw (f) node[right]{$f$};
\draw (g) node[right]{$g$};
\draw (h) node[right]{$h$};
\draw (i) node[right]{$i$};
\draw (j) node[right]{$j$};
\draw (k) node[right]{$k$};
\draw (l) node[right]{$l$};
\draw (m) node[right]{$m$};

\end{tikzpicture}
}
\end{center}
\end{frame}

%%%


\begin{frame}
\frametitle{Dénombrement et opérations sur les ensembles}

\begin{exampleblock}{Produit cartésien}
\begin{eqnarray*}
\card{A\times B}&=&\card{A}\times\card{B}\\
\card{A_1\times\dots\times A_n}&=&\card{A_1}\times\dots\times\card{A_n}
\end{eqnarray*}
\end{exampleblock}
\begin{center}
\begin{tiny}
\begin{tikzpicture}[scale=1.05]
   \tikzstyle{noeud}=[draw,fill=gray!40]

  \node[noeud] (a) at (0.5,4) {};
\node[noeud] (b) at (-4,2) {$a_1$};
\node[noeud] (c) at (-1,2) {$a_2$};
\node[noeud] (d) at (2,2) {$a_3$};
\node[noeud] (e) at (5,2) {$a_4$};
\node[noeud] (f) at (-5,0) {$(a_1,b_1)$};
\node[noeud] (g) at (-4,0) {$(a_1,b_2)$};
\node[noeud] (h) at (-3,0) {$(a_1,b_3)$};
\node[noeud] (f2) at (-2,0) {$(a_2,b_1)$};
\node[noeud] (g2) at (-1,0) {$(a_2,b_2)$};
\node[noeud] (h2) at (0,0) {$(a_2,b_3)$};
\node[noeud] (f3) at (1,0) {$(a_3,b_1)$};
\node[noeud] (g3) at (2,0) {$(a_3,b_2)$};
\node[noeud] (h3) at (3,0) {$(a_3,b_3)$};
\node[noeud] (f4) at (4,0) {$(a_4,b_1)$};
\node[noeud] (g4) at (5,0) {$(a_4,b_2)$};
\node[noeud] (h4) at (6,0) {$(a_4,b_3)$};

\path 
(a) edge (b)
	edge (c)
	edge (d)
	edge (e)
(b) edge (f)
	edge (g)
	edge (h)	
(c) edge (f2)
	edge (g2)
	edge (h2)
(d) edge (f3)
	edge (g3)
	edge (h3)
(e) edge (f4)
	edge (g4)
	edge (h4);
\end{tikzpicture}
\end{tiny}

$A=\{a_1,a_2,a_3,a_4\}$, $B=\{b_1,b_2,b_3\}$, $\card{A\times B}=4\times3=12$
\end{center}

\end{frame}

%%%


%%%


%%%
\begin{frame}
\frametitle{Dénombrement et opérations sur les ensembles}

\begin{exampleblock}{Passage au complémentaire}
 \[\card{\overline{A}}=\card{\Omega}-\card{A}\]
 \end{exampleblock}
% \begin{overlayarea}{12cm}{7cm}

%{\bf \underline{Examples:}}


%\end{overlayarea}
\end{frame}

%%%
\subsection{Arrangement}

\begin{frame}
\frametitle{Arrangement}
\begin{exampleblock}{Permutation de $n$ éléments} Nombre de fa\c con de ranger $n$ objets dans l'ordre. 
$$n!=n\times (n-1)\times (n-2) \times \cdots \times 2 \times 1$$
\end{exampleblock}
\begin{overlayarea}{12cm}{7cm}

{\bf \underline{Examples:}}

\only<2->{$\bullet$ Voici les $4!=24$ permutations de quatre éléments distinct $a$, $b$, $c$ et $d$:
 $$
\begin{array}{cccccc}
 abcd&abdc&acbd&acdb&adbc&adcb\\
 bacd&badc&bcad&bcda&bdac&bdca\\
 cabd&cadb&cbad&cdba&cdab&cdba\\
 dabc&dacb&dbac&dbca&dcab&dcba
\end{array}
 $$}
 
\only<3->{$\bullet$ De combien de façons pouvez-vous ranger 10 livres sur une étagère ? }
\only<4->{ $$10! = 3628800$$}
\end{overlayarea}
\end{frame}

%%%

\begin{frame}
\frametitle{Arrangement}
\begin{exampleblock}{Arrangements de $p$ éléments parmi $n$ sans répétition} Nombre de listes ordonnées de $p$ éléments parmi $n$
$$A^p_n=n\times (n-1)\times (n-2) \times \cdots \times (n-p+1)=\frac{n!}{(n-p)!}$$ 
\end{exampleblock}
\vspace{0.3cm}
\begin{overlayarea}{12cm}{7cm}

{\bf \underline{Examples:}}
{\small

\only<2>{$\bullet$  Les $A^3_4=4\times3\times32 = 24$ arrangements de 3 éléments choisis parmi $a$, $b$, $c$, $d$ :
  $$
\begin{array}{cccccc}
 abc&abd&acb&acd&adb&adc\\
 bac&bad&bca&bcd&bda&bdc\\
 cab&cad&cba&cdb&cda&cdb\\
 dab&dac&dba&dbc&dca&dcb
\end{array}
 $$}

\only<3->{$\bullet$ Quinze chevaux participes à une course, le nombre de tiercé est: }
$$\only<4->{A^3_{15}=15\times14\times13}$$

\only<5->{$\bullet$ Nombre d'injection de $E=\{1,2,3\}$ dans $F=\{1,2,\dots,15\}$:}
$$\only<6>{A^3_{15}=15\times14\times13}$$


}


\end{overlayarea}
\end{frame}
%%%


\subsection{Arrangement}

\begin{frame}
\frametitle{Arrangement}
\begin{exampleblock}{Arrangement de $p$ éléments parmi $n$ avec répétition:} 
Nombre de listes ordonnées de $p$ éléments parmi $n$, mais on s'autorise des répétitions éventuelles des éléments
$$n^p$$
\end{exampleblock}
\begin{overlayarea}{12cm}{7cm}
\only<1>{
{\bf \underline{Example:}}

 Les $3^2 = 9$ arrangements avec répétitions de $2$ éléments parmi $a$, $b$, $c$:
$$aa \quad ab \quad ac \quad ba \quad bb \quad bc \quad ca \quad cb \quad cc$$}

\only<2>{
{\bf \underline{Example:}}
\begin{tabular}{p{6.5cm}p{6cm}}
 {\small Raymond Queneau a écrit un ouvrage intitulé {\em Cent mille milliards de poèmes}.
Il est composé de 10 pages contenant chacune 14 vers.
Le lecteur peut composer son propre poème de 14 vers en prenant le premier vers de l’une des 10 pages puis le deuxième vers de l’une des 10 pages et ainsi de suite jusqu’au quatorzième vers. }&
 \vspace{-0.2cm}
 \includegraphics[width=6cm]{Figure/Poeme.png}
\end{tabular}
}

\begin{exampleblock}<3->{Proposition}
Le cardinal de l'ensemble des applications de $E$ dans $F$, noté $F^E$, est: \[\card{F^E}=\card{F}^{\card{E}}\]
\end{exampleblock}

\begin{exampleblock}<4>{Proposition}
Le cardinal de l'ensemble des parties d'un ensemble $E$ fini est: \[\card{\mathcal{P}(E)}=2^{\card{E}}\]
\end{exampleblock}
\end{overlayarea}
\end{frame}
%%%

%%%
\subsection{Combinaison}

\begin{frame}
\frametitle{Combinaison}

\begin{exampleblock}{Combinaisons de $p$ éléments parmi $n$ sans répétition:} nombre de sous-ensembles de $p$ éléments dans un ensemble contenant $n$ éléments
$$C^p_n=\frac{A^p_n}{p!}=\frac{n!}{p!(n-p)!}$$ 
\end{exampleblock}
\begin{overlayarea}{12cm}{7cm}
{\bf \underline{Example:}}

 Les $C_3^2=\frac{3!}{2!1!}=3$ combinaisons de $2$ éléments choisis parmi $a$, $b$, $c$: 
 $$ab\qquad ac\qquad bc$$
 
 

\end{overlayarea}
\end{frame}


\begin{frame}
\frametitle{Combinaison}
\begin{exampleblock}{Proposition}
$$C^{n-p}_n=C^p_n\qquad \quad C^{p+1}_{n+1}=C^p_n+C^{p+1}_n$$

$$(a+b)^n=\sum_{i=0}^nC^k_n a^kb^{n-k} \textrm{ (formule du binôme)}$$
\end{exampleblock}


\end{frame}

%%%
\begin{frame}
\frametitle{Combinaison}
\begin{exampleblock}{Combinaisons de $p$ éléments parmi $n$ avec répétition:} 
Nombre de listes non ordonnées, avec répétition éventuelle, de $p$ éléments dans un ensemble contenant $n$ éléments
$$K^p_n=C^p_{n+p-1}=\frac{(n+p-1)!}{p!(n-1)!}$$ 
\end{exampleblock}
{\bf \underline{Examples:}}
\begin{overlayarea}{12cm}{7cm}
\only<2->{$\bullet$ Les $K_4^2=C_{4+2-1}^2=\frac{(4+2-1)!}{(4-1)!2!} =\frac{5\times4}{2}=10$ combinaisons avec répétitions de $2$ lettres choisies parmi $a$, $b$, $c$, $d$
sont :
$$aa \qquad ab\qquad ac\qquad ad\qquad bb\qquad bc\qquad bd\qquad cc\qquad cd\qquad dd$$}

\only<3->{
$\bullet$ Combien y a-t-il de dominos avec 10 symboles différents ?}
 \only<4->{$$K_{10}^2=C_{10+2-1}^2=\frac{11!}{9!.2!}=\frac{11\times10}{2}=55$$}
 
 
 
 \end{overlayarea}
\end{frame}
%%%%%%


\begin{frame}
 \frametitle{Résumé}
 
 Tirages de $p$ éléments parmi $n$:
\begin{center}
\begin{tabular}{|p{3cm}||p{3cm}|p{3cm}|}
\hline
\begin{center}Tirages\end{center} & \begin{center}Ordonn\'es\end{center} & \begin{center}Non ordonn\'es\end{center} \\
\hline
\hline
\begin{center}Sans remise\end{center} & $$A^p_n=\frac{n!}{(n-p)!}$$ & $$C^p_n=\frac{n!}{p!(n-p)!}$$ \\
\hline
\begin{center}Avec remise\end{center} & $$n^p$$ & $$K^p_n=C^p_{n+p-1}$$ \\ 
\hline
\end{tabular}
\end{center}
\end{frame}
%%%%%%


\begin{frame}
 \frametitle{Résumé}
 Rangement de $p$ objets dans $n$ cases:
\begin{center}
\begin{tabular}{|p{3cm}||p{3cm}|p{3cm}|}
\hline
\begin{center}Objets\end{center} & \begin{center}Discernables\end{center} & \begin{center}Indiscernables \end{center} \\
\hline
\hline
\begin{center}Un seul dans chaque case\end{center} & $$A^p_n=\frac{n!}{(n-p)!}$$ & $$C^p_n=\frac{n!}{p!(n-p)!}$$ \\
\hline
\begin{center}\'Eventuellement plusieurs dans chaque case\end{center} & $$n^p$$ & $$K^p_n=C^p_{n+p-1}$$ \\ 
\hline
\end{tabular}
\end{center}


\end{frame}


%%%%

\section{Cardinalité des ensembles infinis}


\begin{frame}
\begin{center}
\textcolor{magenta}{{\huge \sc Cardinalité des ensembles infinis}}
\vspace{0.7cm}

\textcolor{magenta}{{\huge \sc Ensembles dénombrables}}
\end{center}
\end{frame}


\begin{frame}
\frametitle{Ensembles dénombrables}
\begin{block}{Définition: Ensemble dénombrable}
Un ensemble est \define{dénombrable} s'il est fini ou s'il est en bijection $\N$.
\end{block}

Montrer que les ensembles suivants sont dénombrables:
\begin{itemize}
 \item $\N\smallsetminus\{0\}$ est dénombrable par la bijection 
 \item l'ensemble des nombres pairs, noté $2\N$, est dénombrable par la bijection 

  \item l'ensemble des nombres impairs, noté $2\N+1$, est dénombrable par la bijection 
\item l'ensemble des entiers relatifs $\Z$ est dénombrable par la bijection
\item l'ensemble $\N^2$ est dénombrable par la bijection

\end{itemize}

\begin{exampleblock}{Proposition}
Tout sous-ensemble $X\subseteq\N$ est dénombrable.
\end{exampleblock}
\end{frame}
%%%%%%

\begin{frame}
\frametitle{Critère de dénombrabilité}
\begin{exampleblock}{Proposition}
Il existe une application $f:X\to\N$ qui est injective si et seulement si $X$ est dénombrable.
\end{exampleblock}
\textbf{\underline{Exemples d'applications:}}
\begin{itemize}
 \item Un sous-ensemble d'un ensemble dénombrable est dénombrable.
 
 \item $\N^2$ est dénombrable.
\item $\N^k$ est dénombrable.

\item Un produit fini d’ensembles dénombrables est dénombrable.
\end{itemize}


\begin{exampleblock}{Proposition}
Il existe une application $f:\N\to X$ qui est surjective si et seulement si $X$ est dénombrable.
\end{exampleblock}
\textbf{\underline{Exemples d'applications:}}
\begin{itemize}
 \item $\Q$  est dénombrable.

\item Une union dénombrable d’ensembles dénombrables est dénombrable.
\end{itemize}

\end{frame}
%%%%%%

\begin{frame}
\frametitle{Ensembles non dénombrables}

\begin{exampleblock}{Théorème (Cantor 1981)}
 Soient $E$ un ensemble. Il n'existe pas d'application bijective de $E$ dans $\P(E)$.
\end{exampleblock}

On en déduit que $\mathcal{P}(\N)$ n'est pas dénombrable.

\begin{exampleblock}{Théorème}
 L'ensemble $[0,1[$ n'est pas dénombrable. 
\end{exampleblock}
\end{frame}
%%%%%%

\begin{frame}
\frametitle{Théorème de Cantor-Schr\"oder-Bernstein}

\begin{exampleblock}{Théorème de Cantor-Schr\"oder-Bernstein}
S’il existe une application injective de $A$ vers $B$ et une application injective de $B$ vers $A$, alors il existe une application bijection de $A$ vers $B$.
\end{exampleblock}
\textbf{\underline{Exemple d'application:}}

$\P(\N)$ et $[0,1]$ sont en bijection car les deux fonctions suivantes sont des injections:

\vspace{0.3cm}

$
\begin{array}{rccl}
 f: & \P(\N) &\longrightarrow& [0,1] \\
 &	A&\longmapsto&\sum_{n\in A}3^{-n}
\end{array}
$

\vspace{0.3cm}

$
\begin{array}{rccl}
g:&[0,1]&\longrightarrow& \P(\N)\\
&x=0,x_0x_1x_2x_3x_4\dots&\longmapsto&\{i\in\N\textrm{ si }x_i=1\}
\end{array}
$

\end{frame}
%%%%%%

%%%
%%%


\end{document}

