Ensembles dénombrables MPSI

[Henry]

Bonjour,
Pouvez vous m'aider à faire cet exercice s'il vous plaît. J'ai un peu de mal avec les raisonnements (même ci cela fait parti des difficultés de la prépas).
Merci d'avance

app=appartient à
c=inclus
On dit qu'un ensemble est dénombrable s'il est en bijection avec IN.

Soit P c IN, infini. On veut montrer que P est dénombrable?
1. Justifier l'existence d'un application phi:IN-->P telle que pour tout n app IN, phi(n)=Min(P\{phi(0),phi(1),...,phi(n-1)}(en particulier, phi(0)=MinP). Indication: utiliser une récurrence pour montrer que si, pour n app IN, phi(0),phi(1),...,phi(n) sont connus de manière unique dans P, alors phi(n+1) est déterminé de manière unique dans P.

2. Montrer que phi est bijective. Indication:pour la surjectivité, raisonnez par l'absurde, introduisez b app P\Im phi et utilisez, le plus petit élément de {n app IN|phi(n)>b}. Que pouvez vous en déduire pour P?

3. Justifier qu'un ensemble infini E est dénombrable ssi il existe une injection de E dans IN.

[Anonyme]

Bonjour,

Soit P c IN, infini. On veut montrer que P est dénombrable?
1. Justifier l'existence d'un application phi:IN-->P telle que pour tout n app IN, phi(n)=Min(P\{phi(0),phi(1),...,phi(n-1)}(en particulier, phi(0)=MinP). Indication: utiliser une récurrence pour montrer que si, pour n app IN, phi(0),phi(1),...,phi(n) sont connus de manière unique dans P, alors phi(n+1) est déterminé de manière unique dans P.

récurrence généralisée

on vérifie pour

Soit n un entier supérieur à 1. On suppose que pour tout et
b n'appartient pas à car b n'est pas dans Im phi et b appartient à P donc

d'où contradictoire

on en déduit que P n'a pas d'élément qui ne sont pas dans Im phi
d'où P=Im phi

[yos]

Il ne faut pas se laisser impressionner par les notations qui masquent toutes les idées.

Tu as un ensemble infini P d'entiers naturels. Tu les ranges dans l'ordre croissant. Le plus petit est noté phi(0), le deuxième phi(1), etc.
phi est une bijection de N sur P PAR CONSTRUCTION.

Un tel énoncé devrait être interdit!!

[Henry]

Oui, c'est vrai que je me suis un peu laissé impressioner. Je vous remercie encore pour votre aide. Pouvez-vous m'aider pour la question 3 s'il vous plaît?

[Anonyme]

Bonjour,
3. Justifier qu'un ensemble infini E est dénombrable ssi il existe une injection de E dans IN.

Bonjour,

S'il est dénombrable et infini alors il y a une bijection de E sur N donc une injection de E dans N

S'il existe une injection f de E dans N, alors comme E est infini il en est de même de P=f(E) qui est une partie de N. D'après la question précédente il existe une biection de P sur N.
la restriction g de f à l'ensemble d'arrivée P est bijective
Donc est biective de E sur N.

[Henry]

Merci beaucoup pour votre aide Looping.
Pouvez vous m'aider à faire un autre exercice s'il vous plaît?

Voilà:
a. Soit f:INXIN-->IN*,(a,b)-->(2^a)(2b+1). Montrer que f est bijective.
b.Montrer que l'ensemble Z est dénombrable et déduiser en que l'ensemble Q est dénombrable.

Je pense qu'il faut utiliser la question a. pour la b.
Merci encore pour votre aide

[Anonyme]

Voilà:
a. Soit f:INXIN-->IN*,(a,b)-->(2^a)(2b+1). Montrer que f est bijective.


Soit n un entier naturel non nul.
On considère le plus grand entier a tel que 2^a | n
il existe m tel que n=2^a . m

Mais 2^{a+1} qui ne divise pas n donc 2 ne divise pas m
D'où m impair et il existe b tel que m=2b+1

f est donc surjective

Pour l'injectivité on considère (a,b) et (a',b') tels que f(a,b)=f('a',b')
c'est-à-dire (2^a)(2b+1)=(2^a')(2b'+1)

par l'absurde si a différent de a' alors par ex a(2b+1)=(2^{a'-a})(2b'+1)
montre que 2 divise 2b+1 absurde
donc a=a' puis b=b'


b.Montrer que l'ensemble Z est dénombrable et déduiser en que l'ensemble Q est dénombrable.

g:Z---> N, n-->2n si n>=0 et -(2n+1) si n<0 bijective

donc Z dénombrable

f:INXIN-->IN*,(a,b)-->(2^a)(2b+1) bijective

h:Q->ZxN qui à r associe (p,q) où p/q est la fraction irréductible associée à r
h est injective (pas surjective)

en prenant par exemple l'application qui à r=p/q (p/q irréductible) associe f(g(p), q) est injective de Q dans N

et on utilise le résultat précédent sur E infini ...

[Henry]

Merci encore pour votre aide Looping .Est ce possible d'avoir votre mail ou votre msn?