Exercices de MPSI

[Kuystre]

Ah d'accord merci pour la réponse rapide, je pense que ça peut être utile de préciser que les ensembles ne sont pas finis pour les TS un peu paumés comme moi Du coup je m'y pencherai sûrement demain

[siro]

L'ensemble des entiers naturels n'est pas fini.

(Par contre il faut se méfier avec les "ensembles" qui "contiennent" trop d'"éléments". Mais bon les entiers naturels ça va.)

[BobbyJoe]

En guise de premier exercice en logique/théorie des ensembles, montrer le théorème de Cantor-Bernstein n'est pas l'"exercice" le plus simple qui soit ^^ C'est même difficile...

[Errys]

Mes solutions pour les questions de dénombrement :

SPOILER:

Je connaissais déjà les solutions pour Z, Q, N^p, R donc je vais les laisser aux autres.

Pour $ P(\mathbb{N}) $ :
Soit $ A\subset P(\mathbb{N}) $ tel que $ A $ dénombrable.
Soit $ g $ de $ \mathbb{N} $ vers $ \mathbb{A} $ bijective, montrons que $ A
\neq P(\mathbb{N}) $ :
On pose la suite de suite $ (u_{i, j}) $ de la manière suivante :
$ u_{i, j} = 1 \text{ si } j\in g(i) \text{, 0 sinon} $.
Construisons une suite $ (v_n)\in\{ 0,1\}^\mathbb{N} $ telle que pour tout $ i\in\mathbb{N} $, il existe $ j\in\mathbb{N} $ tel que $ u_{i, j}\neq v_j $ :
Pour cela, on pose pour tout $ n\in\mathbb{N} : $ $ v_n = 1 - u_{n, n} $
Ainsi, pour tout $ i\in\mathbb{N} $, $ u_{i,i}\neq v_i $.
En posant $ E = \{i\in\mathbb{N}, v_i=1\} $, il est clair que $ E\not\subset A $ mais $ E\in P(\mathbb{N}) $ soit $ A\neq P(\mathbb{N}) $.
Ainsi, $ P(\mathbb{N}) $ n'est pas dénombrable. Et $ \{0,1\}^\mathbb{N} $ non plus ducoup (ce résultat me servira après).

Maintenant, montrons que l'ensemble des parties finies de $ \mathbb{N} $ est dénombrable :

Soit $ I_n = \{ A\in P(\mathbb{N}), card(A) = n\} $. Ainsi, $ I_n $ est l'ensemble des n-uplets d'entiers naturels donc $ I_n = \mathbb{N}^n $ qui est dénombrable.
Si I est l'ensemble des parties finis de $ \mathbb{N} $ alors :
$ I = \displaystyle \bigcup\limits_{i=1}^{\infty} I_n $
Donc I est un union dénombrable d'ensembles dénombrables. Il est donc équipotent à $ \mathbb{N}\times\mathbb{N} $ donc dénombrable.

Pour les parties infinies, que l'on notera J, il est clair que $ J = P(\mathbb{N})\setminus I $ donc non dénombrable.

Pour $ \mathbb{N}^\mathbb{N} $ :
Soit $ A\subset\mathbb{N}^\mathbb{N} $ tel que $ A $ dénombrable. Soit g une bijection de $ \mathbb{N} $ vers $ A $. Montrons que $ A\neq\mathbb{N}^\mathbb{N} $On définit l'operateur = dans $ \mathbb{N}^\mathbb{N} $ :
$ \forall(p,q)\in\left(\mathbb{N}^\mathbb{N}\right)^2, p=q\iff \forall n\in\mathbb{N}, p_n = q_n $
Construisons une suite $ p\in\mathbb{N}^\mathbb{N} $ telle que $ p\notin A $.
Pour tout $ n\in\mathbb{N}, $, on pose $ p_n = g(n)_n + 1 $
Il est clair que $ p\notin A $ mais $ p\in\mathbb{N}^\mathbb{N} $ donc $ A\neq\mathbb{N}^\mathbb{N} $ et donc $ \mathbb{N} $ n'est pas dénombrable.

Pour l'ensemble des suites rationnelles qui convergent vers 0 :
Une petite astuce permet de montrer très rapidement que cet ensemble n'est pas dénombrable. En effet, pour tout $ p\in \{0,1\}^\mathbb{N} $ et pour $ q_n = n $, $ p_n/q_n\longrightarrow 0 $. Comme$ (p_n/q_n)\in\mathbb{Q}^\mathbb{N} $, l'ensemble des suites de rationnelles qui convergent vers 0 n'est pas dénombrable car $ \{0,1\}^\mathbb{N} $ ne l'est pas.

Pour la caractéristique des ensembles au plus dénombrable, je n'ai pas compris ce que tu voulais dire avec "si tu te sens l'ame d'un tricheur". Voici ma solution :
Montrons que c'est une condition nécessaire :
Soit $ A $ au plus dénombrable :
-Si A est fini et n son cardinal, et $ g $ une bijection de $ [0,n-1]\cap\mathbb{N} $ vers A, on définit la suite $ (v_n) $ de la manière suivante :
$ v_0 = g(0) $,
$ \forall i\in[1, n-1],v_i = g(i)\cup v_{i-1}, $,
$ \forall i\ge n, v_i = v_{i-1} $
Il est clair que $ (v_n) $ est croissante au sens de l'inclusion, que les ensembles sont finis et leurs réunion vaut A.
- SInon, A est dénombrable. Soit g une bijection de $ \mathbb{N} $ vers A. On définit la suite $ (v_n) $ de la manière suivante :
$ v_0 = g(0) $ et $ \forall n\in\mathbb{N}, v_n = g(n)\cup v_{n-1} $
Encore une fois, il est clair que $ (v_n) $ est croissante au sens de l'inclusion, que le cardinal de chacun de ses éléments est finis et que l'union de tout les v_n est A.

Montrons que c'est une condition suffisante :
Soit $ (v_n) $ une telle suite, alors :
$ A = \displaystyle\bigcup_{n=0}^{\infty} v_n $. Donc A est un union dénombrable d'ensemble finis donc $ A $ est au plus dénombrable. J'ai surement une erreur en fait, vu que je n'utilise pas la croissance....

Bonne journée.

[Zetary]

Tu as écrit :

SPOILER:

Soit $ I_n = \{ A\in P(\mathbb{N}), card(A) = n\} $. Ainsi, $ I_n $ est l'ensemble des n-uplets d'entiers naturels donc $ I_n = \mathbb{N}^n $ qui est dénombrable.
Si I est l'ensemble des parties finis de $ \mathbb{N} $ alors :
$ I = \displaystyle \bigcup\limits_{i=1}^{\infty} I_n $
Donc I est un union dénombrable d'ensembles dénombrables. Il est donc équipotent à $ \mathbb{N}\times\mathbb{N} $ donc dénombrable.

Je ne suis pas d'accord avec ce point, ton $ I $ n'est pas l'ensemble des parties finies de $ \mathbb{N} $ mais l'ensemble des suites finies à valeurs dans $ \mathbb{N} $ (il y a la même différence qu'entre une paire et un couple). En réalité ça ne change pas grand chose ici, mais ça reste très différent en général.

Sinon pour la dernière question, ton raisonnement me paraît correct. En effet :

Exercice' : montrer qu'un ensemble s'écrit comme réunion croissante d'une suite de ses parties finies si et seulement si il s'écrit comme réunion d'une suite de ses parties finies

Exercice'' : Soit $ A\subset \mathbb{R} $. Montrer que s'il existe une fonction $ f \colon \mathbb{R} \to \mathbb{R} $ croissante, continue en aucun point de $ A $ alors $ A $ est fini ou dénombrable

(Exercice''' (beaucoup trop difficile) : Montrer la réciproque de Exercice'')

[Errys]

Ah oui.... Je vois ce que tu veux dire, merci pour la précision ! Dans un n-uplet on peut avoir des répétitions. Mais ducoup I_n est inclus dans N^n non ?

Merci pour les exercices, je vais les commencer dimanche soir

[Zetary]

On ne peut pas vraiment donner cette inclusion non (une autre différence majeure est que dans un n-uplet l'ordre des éléments importe, pas dans un ensemble), mais tu peux essayer de trouver une injection...

[Errys]

Ok je comprend mieux maintenant. Merci pour l'explication.

[Errys]

J'ai enfin trouvé la preuve pour l'irrationalité de pi !

SPOILER:

On suppose par l'absurde que $ \pi=p/q $
En utilisant le binôme de Newton pour transformer l'expression de $ f_n $ il vient :
$ f_n(x) = \dfrac{1}{n!}\left(\displaystyle\sum_{k=0}^n \binom{n}{k}(-1)^k(px)^k(qx^2)^{n-k}\right) = \dfrac{1}{n!}\left(\displaystyle\sum_{k=0}^n \binom{n}{k}(-1)^kp^k x^{2n-k}q^{n-k}\right) $

Ainsi : $ I_n = \dfrac{1}{n!}\displaystyle\sum_{k=0}^n\int_{0}^\pi \sin(x)\binom{n}{k}(-1)^kp^kx^{2n-k}q^{n-k}dx $
$ = \dfrac{1}{n!}\displaystyle\sum_{k=0}^n\left(\binom{n}{k}(-1)^kp^kq^{n-k}\int_{0}^{\pi}\sin(x)x^{2n-k}dx\right) $

Je suis sur mon ordinateur portable donc je ne vais pas avoir le courage d'écrire bien toutes les IPP mais en gros, en faisant 2n-k IPP, on perd le x et il reste plus que $ \sin(x) $ ou $ cos(x) $ selon la parité de k/n. Ainsi, en utilisant les primitives on a un entier. Et en faisant les IPP, il reste aussi $ (2n-k)! $ ce qui nous assure que chaque terme de la somme est divisible par $ n! $ et donc que $ I_n $ est entier.

Ainsi :
$ \forall n\in\mathbb{N}, I_n \in\mathbb{N}^* $
On arrive à une contradiction en remarquant que $ I_n\longrightarrow 0 $. Donc $ \pi $ est irrationnel.

[Zetary]

Bravo, même si tu t'es compliqué la vie (fais attention, il y a une question que tu n'as pas utilisée), ta preuve est juste mais cette question intermédiaire servait à faire que la derniere question soit pratiquement sans calculs