Ensemble dénombrable

Bleyblue · 13/07/2006, 22h18

Bonjour,

Je dois démontrer que l'ensemble A des fonctions injectives de $\mathbb{Z}$ vers $\mathbb{Z}$ n'est pas dénombrable.

En calquant sur une autre démonstration (je ne suis pas encore capable de démontrer des propositions pareilles tout seul) :

Si A était dénombrable il existerait une bijection $F:\mathbb{N} \to F_n$
Si je prends une fonction $g:\mathbb{Z} \to \mathbb{Z}$ définie comme suit :

Si $z \le 0$

g(z) = z

Si $z > 0$

g(z) est le plus petit naturel non nul différent de $F_n(n)$ et de g(l) avec 0 < l < z

Alors g est injective mais n'est pas dans l'image de F. Donc F n'est pas surjective, donc F n'est pas une bijection donc l'ensemble n'est pas dénombrable

ca va ça ?

merci

martini_bird · 13/07/2006, 22h55

Salut,

c'est quoi $F_n$ ?

Cordialement.

Gwyddon · 13/07/2006, 23h14

F_n m'a l'air d'être l'ensemble des fonctions injectives A.

Donc la définition de g est erronée, puisque F_n(n) est une fonction, pas un entier...

Bleyblue · 13/07/2006, 23h17

Excusez-moi j'ai fait une erreur dans mes notations.

A est l'ensemble des fonctions injectives et la fonction est :

$F : \mathbb{N} \to A : n \to F_n$

cela marche comme ça ?

merci

martini_bird · 14/07/2006, 00h49

Salut,

Citation:

Alors g est injective mais n'est pas dans l'image de F.

Il faudrait délayer un peu ça.

En fait c'est une sorte d'argument "diagonal" (d'aileurs on pourrait s'y ramener très facilement).

Cordialement.

rvz · 14/07/2006, 11h07

Salut,

Je dois être un peu fatigué (il est encore tôt

) mais il me semble que l'argument de Bleyblue est tout à fait juste et bien écrit, une fois qu'il a précisé ce qu'était F_n comme il l'a fait au post 4.
Je comprends pas trop quels commentaires vous attendez en plus ?
__
rvz, qui l'année prochaine, devra faire des TDs, alors j'en profite pour essayer d'apprendre à rédiger clairement...

martini_bird · 14/07/2006, 11h26

Salut,

tu te souviens quand tu étais en sup et qu'on te demandait pour démontrer qu'une fonction est injective de supposer qu'on a f(x)=f(y) et d'en déduire que x=y ?

Il y a différents niveaux de rédaction : je ne suis pas certain (mais je me trompe peut-être) qu'un prof de sup accepte l'ommission de « détails »... Et puis c'est pas un mauvais exercice pour Bleyblue s'il veut vraiment se convaincre de sa preuve.

Cordialement.

rvz · 14/07/2006, 11h35

Oui, tu dois avoir raison. Encore que pour les fonctions injectives, ou c'est trivial, ou il faut vraiment le poser calmement. Je n'ai jamais vu de cas intermédiaire ...

__
rvz, qui se prépare à des longs exercices de rédaction...

wlad_von_tokyo · 14/07/2006, 14h32

Salut

j essaie un truc, pas sur de la veracite

1) R est indenombrable, l ensemble des nombres a developement decimale fini est inclus dans Q qui est denombrable, l ensemble des nombres a developpement non finis est donc indenombrables.
c est la meme chose donc pour
$D=\{0.x_0x_1...x_n...,~x_n \in[0,1,2,3,4,5,6,7,8,9] et \forall p \in \N, \exists q>p x_q > 0\}$

2) soit l ensemble F des fonction de N dans N injectives. A chaque f de F, on associe le nombre 0.f(0)f(1)f(2)....f(n).... Par exemple f(0)=3, f(1)=33, f(2)=333,... donne 0.33333333..... a chaque f de F, on peut associer ainsi un nombre de D, le 0 ne se repetant pas car f injectif
montrons que c est injectif
soit $0.x_0x_1....x_n...$ un nombre de D.
-si il n y a pas de 0 dans les decimales, on prend
$f(0)=x_0$
$f(1)=x_1x_2$
etc...
f est bien injective
- si il y a au moins un zero, disons $x_p=0$ , on prend
$f(0)=x_0...x_{p-1}$
par definition, il existe q>p tq $x_q$ different de 0. si il n y a plus de 0 dans les decimales,
$f(1)=0000000000000...00000x_q. ..x_{p+q+1}$ different de f(0) puis chque f(n+1) est construit avec une decimale de plus que f(n)
si il y a encore un 0 on recommence

ainsi par recurence on construit un bon f

donc F et D sont en bijection, F est donc indenombrable

qu en pensez vous ?

rvz · 14/07/2006, 14h45

Salut

L'idée est pas mauvaise, mais je ne comprends pas comment tu fais pour prouver que f est une bijection.
x = 0,12345667....
et y = 0,102345667... la même chose que x vont avoir la même image, non ? Y a sans doute moyen de corriger ça, mais j'ai pas trop le temps d'y réfléchir.

__
rvz

wlad_von_tokyo · 14/07/2006, 14h58

argh rvz m a tue

Bleyblue · 14/07/2006, 21h22

Citation:

Posté par martini_bird

Il y a différents niveaux de rédaction : je ne suis pas certain (mais je me trompe peut-être)

Non c'est bien vrai, j'ai oublié cette partie de la démonstration.
J'essaie de démontrer proprement l'injectivité

merci

Bleyblue · 14/07/2006, 21h42

Comme ça :

Je dois montrer g injective.

Supposons g(x) = g(y). Il faut x > 0 et y > 0 ou x <=0 et y <=0 car si x et y étaient de signes contraires il faudrait g(x) et g(y) aussi de signes contraires donc g(x) serait différent de g(y).

a) Si $x \le 0 \ y \le 0$
alors g(x) = x et g(y) = y donc x = y

b) Si $x > 0 et y > 0$

g(x) est le plus petit naturel non nul, différent de $F_x(x)$ , et différent de g(l1) avec 0 < l1 < x

g(y) est le plus petit naturel non nul, différent de $F_y(y)$ , et différent de g(l2) avec 0 < l2 < y

Supposons x > y

Alors g(x) est différent de g(l1) pour tout 0 < l1 < x et comme 0 < y < x eh bien g(x) est différent de g(y) ce qui est faux par hypothèse

Supposons x < y
(par le même raisonnement je montre que ce n'est pas possible)

Donc x = y

Donc g est une fonction injective car g(x) = g(y) ==> x = y et elle est différent de Fn pour tout naturel n car Fn(n) est différent de g(n)

Maintenant, ça va ?

merci

Gwyddon · 14/07/2006, 23h02

Je n'y vois strictement aucune faute, c'est nickel

Bleyblue · 14/07/2006, 23h09

Bien bien, je vais mettre ça au net puis essayer une autre démonstration du même genre

merci

Bleyblue · 15/07/2006, 14h50

Je dois montrer que l'ensemble E de toutes les suites réelles dont les termes sont 0 ou 1 n'est pas dénombrable

En fait on se ramène à un ensemble de fonction parcequ'une suite réelle est une application $\mathbb{N} \to \mathbb{R}$ et ici ça revient à montrer que l'ensemble des applications de N -> {0,1} n'est pas dénombrable

Supposons que $U:\mathbb{N} \to \mathbb{E} : n \to U_n$ est une bijection et soit u une suite de E définie par :

u(n) = 0 si U_n(n) = 1
u(n) = 1 si U_n(n) = 0

Alors la fonction u n'est pas dans l'image de U car pour toute suite Un appartenant à l'image de U on a u(n) diffèrent de Un(n) donc ça contredit la surjectivité etc.

Ca passe ?

merci

doudache · 15/07/2006, 18h16

Salut !

Ca a l'air juste.

Je ne sais pas si tu as remarqué, mais ton ensemble de suites est en bijection avec les parties de N. Plus généralement, essaie de montrer qu'il n'y a pas de surjection entre X et l'ensemble des parties de X.

evariste_galois · 15/07/2006, 22h58

Salut,

J'y vais de ma petite idée, en espérant qu'elle soit juste:

Montrons que l'ensemble A des fonctions injectives de N dans N est non dénombrable (On raisonne de même pour les fonctions injectives de Z dans Z).
Je me donne une suite d'entiers naturels tous non nuls $(a_0,a_1,...,a_n,...)$ et je définis une fonction f:N->N comme suit:
$f_{(0)}=a_0$ , $f_{(i)}=f_{(i-1)}+a_i$ pour i>0
f est clairement injective, car les $a_i$ sont tous non nuls.
Je considère alors l'ensemble B des fonctions définies comme ci-dessus, avec $(a_0,a_1,...,a_n,...)$ variant dans $N*^N$ .
Il s'ensuit que B est inclus dans A, de cardinal la puissance du continu.