Ensemble dénombrable

[Bleyblue]

Bonjour,

Je dois démontrer que l'ensemble A des fonctions injectives de vers 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
Si je prends une fonction définie comme suit :

Si

g(z) = z

Si

g(z) est le plus petit naturel non nul différent de 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]

Salut,

c'est quoi ?

Cordialement.

[Gwyddon]

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]

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

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



cela marche comme ça ?

merci

[A voir en vidéo sur Futura]

[martini_bird]

Salut,

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.

[invite6b1e2c2e]

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]

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.

[invite6b1e2c2e]

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...

[GrisBleu]

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


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 un nombre de D.
-si il n y a pas de 0 dans les decimales, on prend


etc...
f est bien injective
- si il y a au moins un zero, disons , on prend

par definition, il existe q>p tq different de 0. si il n y a plus de 0 dans les decimales,
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 ?

[invite6b1e2c2e]

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

[GrisBleu]

argh rvz m a tue

[Bleyblue]

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]

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
alors g(x) = x et g(y) = y donc x = y

b) Si

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

g(y) est le plus petit naturel non nul, différent de , 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]

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

[Bleyblue]

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

merci

[Bleyblue]

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 et ici ça revient à montrer que l'ensemble des applications de N -> {0,1} n'est pas dénombrable

Supposons que 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

[invite8b04eba7]

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.

[invitea77054e9]

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 et je définis une fonction f:N->N comme suit:
, pour i>0
f est clairement injective, car les sont tous non nuls.
Je considère alors l'ensemble B des fonctions définies comme ci-dessus, avec variant dans .
Il s'ensuit que B est inclus dans A, de cardinal la puissance du continu.

[Bleyblue]

Plus généralement, essaie de montrer qu'il n'y a pas de surjection entre X et l'ensemble des parties de X.

J'ai déja vu cette démonstration dans le cas ou X = N, ça n'étais pas particulièrement simple comme démonstration, je ne sais pas si cela change quelque chose dans le cas d'un ensemble X quelconque (si je me souviens bien je pense que oui)

[Gwyddon]

Et pourtant...

Théorème : soit un ensemble quelconque. Il n'existe pas de surjection de sur

Démonstration

Supposons qu'il existe une telle surjection .

Soit . Par surjection, il existe un certain tel que .

Si l'on suppose que , par définition cela impose . Cela est absurde.

Par conséquent, ; mais alors cela signifie que

C'est encore absurde. Donc en définitive l'hypothèse de départ, à savoir l'existence de f, est absurde.

Ainsi, il n'existe pas de surjection de vers

[Bleyblue]

Ah tiens oui, c'est la même démo que celle que j'ai eu sauf que N est remplacé par un ensemble quelconque X

merci