On dit que deux ensembles {A} et {B} sont équipotents s’il existe une bijection de {A} dans {B} (ou de {B} dans {A} ce qui est évidemment équivalent).
Partie II
Soit {A} une partie infinie de {\mathbb{N}}.
On va montrer que {A} et {\mathbb{N}} sont équipotents.
Question I.1
Montrer que l’on définit bien une suite { (a_n)_{n \in \mathbb{N}}} d’éléments de {A} de la manière suivante :
Montrer que l’on définit bien une suite { (a_n)_{n \in \mathbb{N}}} d’éléments de {A} de la manière suivante :
- {a_{0}=\min(A_0)}, où {A_0=A}.
- Pour tout {n\in\mathbb{N}^*}, {a_{n}=\min A_n}, où {A_n=\Bigl(A\setminus\{a_{0},a_{1},\ldots,a_{n-1}\}\Bigr)}.
Question I.2
Montrer que la suite {n\mapsto a_{n}} est strictement croissante de {\mathbb{N}} dans {A}.
Montrer que la suite {n\mapsto a_{n}} est strictement croissante de {\mathbb{N}} dans {A}.
Question I.3
Pour tout {n} de {\mathbb{N}}, montrer que {a_{n}\ge n}.
En déduire que : {\forall\,m\in A,\;\exists\,k\in\mathbb{N}^*,\;a_{k}>m}.
Pour tout {n} de {\mathbb{N}}, montrer que {a_{n}\ge n}.
En déduire que : {\forall\,m\in A,\;\exists\,k\in\mathbb{N}^*,\;a_{k}>m}.
Question I.4
Pour tout {m\in A}, montrer : {\exists\,n\in\mathbb{N},\;a_{n}=m}.
En déduire que {A} et {\mathbb{N}} sont équipotents.
Pour tout {m\in A}, montrer : {\exists\,n\in\mathbb{N},\;a_{n}=m}.
En déduire que {A} et {\mathbb{N}} sont équipotents.
Partie II
Soit {X} un ensemble infini.
Question II.1.(a)
On suppose qu’il existe {f :X\to\mathbb{N}} injective.
Montrer que {X} et {\mathbb{N}} sont équipotents.
On suppose qu’il existe {f :X\to\mathbb{N}} injective.
Montrer que {X} et {\mathbb{N}} sont équipotents.
Question II.1.(b)
Soit {Y} un ensemble équipotent à {\mathbb{N}}.
On suppose qu’il existe {f :X\to Y} injective.
Montrer que {X} et {\mathbb{N}} sont équipotents.
Soit {Y} un ensemble équipotent à {\mathbb{N}}.
On suppose qu’il existe {f :X\to Y} injective.
Montrer que {X} et {\mathbb{N}} sont équipotents.
Question II.2
On pose : {\forall\,n\in\mathbb{Z},\;f(n)=(3n+1)^2}.
Montrer que {\mathbb{Z}} et {\mathbb{N}} sont équipotents.
On pose : {\forall\,n\in\mathbb{Z},\;f(n)=(3n+1)^2}.
Montrer que {\mathbb{Z}} et {\mathbb{N}} sont équipotents.
Question II.3.(a)
Soit {f :\mathbb{N}^2\to\mathbb{N}} définie par {f(m,n)=(m+n)^2+n}On se donne {(m,n)} et {(m',n')} dans {\mathbb{N}^2}.
Montrer que {m'\!+\!n'\!>\!m\!+\!n\!\Rightarrow\! f(m',n')\!>\!f(m,n)}
Soit {f :\mathbb{N}^2\to\mathbb{N}} définie par {f(m,n)=(m+n)^2+n}On se donne {(m,n)} et {(m',n')} dans {\mathbb{N}^2}.
Montrer que {m'\!+\!n'\!>\!m\!+\!n\!\Rightarrow\! f(m',n')\!>\!f(m,n)}
Question II.3.(b)
En déduire que {\mathbb{N}^2} et {\mathbb{N}} sont équipotents.
En déduire que {\mathbb{N}^2} et {\mathbb{N}} sont équipotents.
Question II.4.(a)
Soient {A} et {B} équipotents à {\mathbb{N}}.
Montrer que {A\times B} et {\mathbb{N}} sont équipotents.
Soient {A} et {B} équipotents à {\mathbb{N}}.
Montrer que {A\times B} et {\mathbb{N}} sont équipotents.
Question II.4.(b)
Plus généralement, soit {A_{1},\ldots,A_{n}} équipotents à {\mathbb{N}}.
Montrer {A_{1}\times A_{2}\times\cdots\times A_{n}} est équipotent à {\mathbb{N}}.
Plus généralement, soit {A_{1},\ldots,A_{n}} équipotents à {\mathbb{N}}.
Montrer {A_{1}\times A_{2}\times\cdots\times A_{n}} est équipotent à {\mathbb{N}}.
Question II.5
On sait que tout nombre rationnel {x} peut s’écrire de manière unique sous la forme {x=p/q} avec {p} dans {\mathbb{Z}} et {q} dans {\mathbb{N}^*}, la fraction étant non simplifiable).
Utiliser cette propriété pour montrer que {\mathbb{Q}} et {\mathbb{N}} sont équipotents.
On sait que tout nombre rationnel {x} peut s’écrire de manière unique sous la forme {x=p/q} avec {p} dans {\mathbb{Z}} et {q} dans {\mathbb{N}^*}, la fraction étant non simplifiable).
Utiliser cette propriété pour montrer que {\mathbb{Q}} et {\mathbb{N}} sont équipotents.
Question II.6
Montrer que {\mathscr{P}(\mathbb{N})} et {\mathbb{N}} ne sont pas équipotents.
Montrer que {\mathscr{P}(\mathbb{N})} et {\mathbb{N}} ne sont pas équipotents.