Ensemble dénombrable.

mystic_snake [Théo] · 08/05/2007, 16h48

Il me faudrait une petite aide pour demain... Il faudrait que je (re)trouve 2 démos:
-Soit E un ensemble dénombrable et f:E->F (ensemble quelquonque) une Fonction surjective, alors F est dénombrrable.
-Soit F un ensemble dénombrable et g:E->F injective. Alors E est dénombrable.

a priori, je crois qu'il faut déjà supposer que les ensembles sont infinis.
merci bien ^^

PS: Je parle d'ensembles dénombrables dans le sens ensemble équipotent à IN.

martini_bird · 08/05/2007, 16h59

Salut,

pour une application sujective, c'est difficile pour l'image de contenir plus d'éléments que la source... Idem dans l'autre sens pour une fonction injective.

Cordialement.

mystic_snake [Théo] · 08/05/2007, 17h01

oui, dit comme ça, ça parait simple, mais en fait, comment monter une preuve en bonne et due forme? Il faut que je me donne des fonctions explicites non? parce que si je dit juste ça, ça risque de faire moyen non (c'est pour un TIPE en fait)

prgasp77 · 08/05/2007, 17h04

Bonjour, il suffit d'utiliser les définitions de tes termes. Je te montre pour la première :

$E$ est dénombrable, ainsi il existe une bijection $n_E$ de $\mathbb{N}$ dans $E$ . Ainsi,
$\forall x\,\in\,E,\, \exist! n\,\in\,\mathbb{N},\, n_E(n)=x$ (1)

Il existe une application f surjective de $E$ sur $F$ . Ainsi
$\forall y\,\in\,F,\, \exist x\,\in\,E,\, f(x)=y$ (2)

On injecte (1) dans (2) :
$\forall y\,\in\,F,\, \exist! n\,\in\,\mathbb{N}, f(n_E(n))=y$

Ainsi il existe une bijection $f\,\circ\,n_E$ de $\mathbb{N}$ dans $F$ , donc $F$ est dénombrable.

mystic_snake [Théo] · 08/05/2007, 17h07

merci bien,
PS: il y a un tutorial ou des infos pour écrire mathématiques (somme, etc...) sur le forum ou bien c'est du Copié/collé depuis autre chose??

Médiat · 08/05/2007, 17h15

Salut prgasp77, dans ta dernière formule le "Il existe un et un seul n" est abusif (il vient du "Il existe x" de ta formule 2).

Donc ce que tu as démontré c'est que $f \circ n_E$ est une surjection, ce qui est d'ailleurs suffisant pour démontrer que F est au plus dénombrable (cf. les contre-exemples de Martini_bird, plus rapide que moi, cela doit être l'âge).

prgasp77 · 08/05/2007, 17h18

Arf ! Mea culpa.
Il faut m'excuser il est encore bien tôt

Erratum :
$E$ est dénombrable, ainsi il existe une bijection $n_E$ de $\mathbb{N}$ dans $E$ . Ainsi,
$\forall x\,\in\,E,\, \exist! n\,\in\,\mathbb{N},\, n_E(n)=x$ (1)

Il existe une application f surjective de $E$ sur $F$ . Ainsi
$\forall y\,\in\,F,\, \exist x\,\in\,E,\, f(x)=y$ (2)

On injecte (1) dans (2) :
$\forall y\,\in\,F,\, \exist n\,\in\,\mathbb{N}, f(n_E(n))=y$

Ainsi il existe une surjection $f\,\circ\,n_E$ de $\mathbb{N}$ sur $F$ , donc $F$ est au plus dénombrable, donc $F$ est dénombrable.

martini_bird · 08/05/2007, 17h20

Citation:

Posté par Médiat

cf. les contre-exemples de Martini_bird

Oups, fausse manip, je remets les exemples :

$\begin{array}{lccc}f:& \mathbb{N}& \rightarrow & \{0\} \\ &n&\rightarrow &0\end{array}$

$\begin{array}{lccc}g: & \{0\}&\rightarrow & \mathbb{N} \\ &0&\rightarrow &0\end{array}$

Cordialement.

mystic_snake [Théo] · 08/05/2007, 17h20

ben a priori, j'utilise les argumesnts de martini bird, ça devrait suffire à défaut de trouver une preuve plus convaincante

mystic_snake [Théo] · 09/05/2007, 00h39

Citation:

Posté par prgasp77

Arf ! Mea culpa.

donc $F$ est au plus dénombrable, donc $F$ est dénombrable.

euh cette implication me parait louche non? (c'est justifié par le fait que les ensembles sont infinis alors n'est ce pas?)

prgasp77 · 09/05/2007, 03h38

Citation:

Posté par mystic_snake [Théo]

euh cette implication me parait louche non? (c'est justifié par le fait que les ensembles sont infinis alors n'est ce pas?)

En disant que $F$ est au plus dénombrable on dit que $F$ est fini (ex: {0,1,2,3}) ou infini dénombrable (ex : $\mathbb{N}$ ).

mystic_snake [Théo] · 09/05/2007, 17h46

ok, mais j'aimerais savoir vraiment si le fait qu'un ensemble infini soit au plus dénombrable en fait automatiquement dénombrable?

Médiat · 09/05/2007, 18h46

Si ta question est de savoir s'il existe des infinis strictement plus petits que le dénombrable, la réponse est non.

prgasp77 · 09/05/2007, 20h31

Quant à le démontrer ... c'est autre chose (petit clin d'oeil à ta signature Médiat

)

mystic_snake [Théo] · 09/05/2007, 22h44

parce que c'est comme dire qu'il n'existe rien entre les infinis de IN et de IR, on nous l'a dit, mais bon...

Médiat · 09/05/2007, 23h43

Citation:

Posté par mystic_snake [Théo]

parce que c'est comme dire qu'il n'existe rien entre les infinis de IN et de IR, on nous l'a dit, mais bon...

Ah non, cela c'est l'hypothèse du continu dont il est démontré qu'elle est indécidable dans la théorie ZFC.

Citation:

Posté par prgasp77

Quant à le démontrer ... c'est autre chose

Dans la mesure ou $\aleph_0$ (l'infini dénombrable) est par définition le plus petit cardinal infini... il n'y a pas grand-chose à démontrer, il me semble

.

prgasp77 · 10/05/2007, 00h15

Citation:

Posté par Médiat

Dans la mesure ou $\aleph_0$ (l'infini dénombrable) est par définition le plus petit cardinal infini... il n'y a pas grand-chose à démontrer, il me semble

.

SI, démontrer que le cardinal de $\mathbb{N}$ est $\aleph_0$

Médiat · 10/05/2007, 05h50

Citation:

Posté par prgasp77

SI, démontrer que le cardinal de $\mathbb{N}$ est $\aleph_0$

Je ne vois pas pourquoi j'aurais à faire cela (dans ce contexte) puisque je n'ai pas parlé de $\mathbb{N}$
Soit ; on fabrique une injection de vers , de la façon suivante :
1. Au plus petit élément $a_0$ de $\mathbb{E}$ ( $\mathbb{N}$ est un bon ordre) on fait correspondre 0, au plus petit élément de $\mathbb{E}$ - { $a_0$ }, on fait correspondre 1, etc.
2. Soit cette application est une surjection, donc une bijection, donc les cardinaux de $\mathbb{E}$ et de $\mathbb{N}$ sont égaux.
3. Soit cette application n'est pas une surjection et l'ensemble des éléments de $\mathbb{N}$ qui ne sont pas image dans cette application admet un plus petit élément n ( $\mathbb{N}$ est un bon ordre) et alors $\mathbb{E}$ est fini (sont cardinal est n puisque isomorphe au segment initial de $\mathbb{N}$ identifié à n.
Donc pas de cardinal entre celui de et les cardinaux finis, donc celui de est le plus petit non fini.