Dénombrabilité

Tankario
Tankario
dans Topologie
Bonjour,
Un ensemble $X$ est dénombrable si et seulement si il est en bijection avec $\mathbb{N}$.
Or, pourquoi pour montrer qu'un ensemble $X$ est dénombrable, il nous suffit de trouver une injection de $X$ vers $\mathbb{N}$ ?

Merci à vous

Réponses

  • Boole et Bill
    Boole et Bill
    On parle ici d'ensembles infinis. Donc s'il existe une injection de $X$ dans $\mathbb{N}$, il existe une bijection de $X$ sur une partie infinie $A$ de $\mathbb{N}$ (l'image de l'injection). Cette partie $A$ peut être vue comme le support d'une suite $(a_n)_{n \in \mathbb{N}}$, qui est clairement en bijection avec $\mathbb{N}$. Bon ce que je viens de dire c'est du fait maison, attendons de voir ce qu'en disent les autre intervenants.
  • Boole et Bill
    Boole et Bill
    J'affine un peu : strictement croissante la suite, de premier terme le minorant de $A$, de deuxième terme le minorant de $A$ privé de $a_0$ etc..
  • gerard0
    gerard0
    Attention : le mot dénombrable est utilisé pour deux choses : "en bijection avec $\mathbb N$", ou bien "fini ou en bijection avec $\mathbb N$".
    Premier cas : Suivant les axiomatiques utilisées, on prouve que $\mathbb N$ s'injecte dans tout ensemble infini, voire même c'est la définition de "ensemble infini". Si $E$ s'injecte dans $\mathbb N$ et est infini, alors $E$ et $\mathbb N$ s'injectent l'un dans l'autre donc sont en bijection (théorème de Cantor-Bernstein). La réciproque est évidente.
    Deuxième cas : Si $E$ est fini, on en utilise une énumération. S'il est infini, voir ci-dessus.
    Tu peux étudier ce cours : Viossat Dauphine.

    Cordialement.
  • gerard0
    gerard0
    Attention, Boole et Bill,

    la notion de croissant ou de plus petit élément n'a pas de sens sur un ensemble quelconque.

    Cordialement.
  • Boole et Bill
    Boole et Bill
    Oui gerard0, mais je travaille avec l'ensemble $A$ que j'ai défini comme étant l'image par l'injection considérée de $X$ dans $\N$.
  • gerard0
    gerard0
    Ok, j'avais lu trop vite.

    En fait, tu redémontres qu'une partie infinie de $\mathbb N$ est en bijection avec $\mathbb N$.

    Cordialement.
  • Algèbre
    Algèbre
    Je crois que dans la terminologie française(Bourbaki.)., fini n'est pas dénombrable. Ainsi $\{1\}$ s'injecte dans $\mathbb{N}$ mais n'est pas dénombrable. Mais ce n'est que du jeu de définition.
    Je le dis pour te sensibiliser sur contexte dans lequel s'inscrit ta question. Si seulement on pouvait se mettre d'accord sur un contexte...
  • Maxtimax
    Maxtimax
    @gerard0: même pas besoin d'utiliser Cantor-Bernstein et le fait que $\N$ s'injecte dans $X$ voyons ! Cela nécessiterait une forme de choix alors que ce résultat est bien plus basique que ça.

    Si $X$ s'injecte dans $\N$ alors son image est ou finie (auquel cas $X $ est fini), ou infinie. Une partie infinie de $\N$ est dénombrable (aucun axiome du choix, aucun Cantor-Bernstein ici: une partie infinie de $\N$ est un ensemble bien ordonné infini, il est donc isomorphe à un ordinal infini qui n'a pas d'élément limite: c'est donc $\omega= \N$ -on peut le faire plus "à la main" en construisant par récurrence une énumération $(a_n)$ comme le proposait Boole et Bill, dont la première réponse aurait dû clore la question) , donc $X$ est dénombrable.
  • gerard0
    gerard0
    Effectivement, j'ai utilisé trop gros B-)
  • Georges Abitbol
    Georges Abitbol
    @Max : Il y a besoin de l'axiome du choix pour Cantor-Bernstein ? Dans mon souvenir, on pouvait y arriver sans !
  • Maxtimax
    Maxtimax
    @GA : Tu as raison, on n'en a pas besoin; je faisais référence au passage où gerard0 utilise une injection de $\N$ dans $X$ (la partie qui suit le "et" de ma première phrase) - désolé si ce n'était pas clair
    (C'est d'ailleurs ce qui est remarquable avec CB : un résultat d'arithmétique des cardinaux sans AC !)
  • Tankario
    Tankario
    Bonjour,

    Merci à tous pour vos réponses.

    Pour revenir à ta définition @gerard0, dans mon cours il est écrit :

    $X$ est dénombrable si et seulement si $X$ est en bijection avec $\mathbb{N}$
    $X$ est au plus dénombrable si et seulement si $X$ est fini ou $X$ est dénombrable.

    Or, quelques lignes plus bas, il est écrit que pour montrer qu'un ensemble n'est pas dénombrable, il nous suffit de montrer qu'il est fini.
    Mais un ensemble fini n'est donc pas au plus dénombrable comme mentionné ci-dessus ?

    Je me perds...
  • gerard0
    gerard0
    Bizarre ce que tu écris : "Or, quelques lignes plus bas, il est écrit que pour montrer qu'un ensemble n'est pas dénombrable, il nous suffit de montrer qu'il est fini."
    $\mathbb R$ n'est pas dénombrable, et est loin d'être fini.
    Tu es sûr qu'il y a ça dans le cours du prof ? Hors de tout contexte particulier ?

    Sinon, pour la différence entre "dénombrable" et "au plus dénombrable", c'est du simple français quand on connaît les inégalités entre cardinaux; ou bien on apprend la définition que tu rappelles ci-dessus. "Au plus dénombrable" ne signifie pas "dénombrable", de même que "x vaut au plus 8" ne dit pas que x vaut 8.

    Cordialement.
  • Tankario
    Tankario
    Il y a la première méthode pour montrer qu'un ensemble $X$ est dénombrable, c'est justement ma question de départ.

    La seconde méthode c'est pour montrer que $X$ n'est pas dénombrable :
    - $X$ est fini
    - $\exists \phi : \mathbb{R} \rightarrow X$ injective
    - $\not\exists \phi : X \rightarrow \mathbb{N} $ injective
    - $\not\exists \phi : \mathbb{N} \rightarrow X $ surjective

    Peut-être que le fait que $X$ soit fini est une condition pour les applications qui suivent ?
  • Algèbre
    Algèbre
    Quelles applications?
  • Tankario
    Tankario
    Les applications citées ci-dessus (celles qui suivent "$X$ est fini")
  • gerard0
    gerard0
    A vue de nez, il s'agit de 4 méthodes différentes. Et j'avais mal compris ta phrase "Or, quelques lignes plus bas, il est écrit que pour montrer qu'un ensemble n'est pas dénombrable, il nous suffit de montrer qu'il est fini." Qui est tout à faut juste.

    Par exemple, la deuxième méthode s'appuie sur le fait connu que $\R$ n'est pas dénombrable.

    Cordialement.
  • Tankario
    Tankario
    @gerard0 : Tant mieux, nous nous étions mal compris! Merci pour ces précieux conseils, je re-posterai sur ce topic en cas de questions supplémentaires au sujet de la dénombrabilité.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 11

Domalexispbiguine_equation +8 Invités