Ensemble non dénombrable

[y6227]

Bonjour,

Pouvez-vous m'indiquer pourquoi l'ensemble suivant n'est pas dénombrable ?

{ tel que n appartient à N}

J'ai énormément de mal avec cette notion.

En vous remerciant par avance.

[nodjim]

Aucune indication sur a et b ?

[y6227]

Aucune indication sur a et b ?

Si tu veux pour n = 2 on a le mot aabb, pour n = 3 aaabbb, peu importe la valeur de a et de b

On peut faire la meme chose pour 1 et 0 : 10 1100 111000 ....

ps: a et b ne peuvent représenter que des chiffres, c'était peut etre ce que tu te demandais

[LaCoc6nl]

Aucune indication sur a et b ?

Si , la propriété est vraie par récurrence sur et d'après le théorème de Cantor à non dénombrable car il n'y a pas de surjection entre et : .

[y6227]

Si , la propriété est vraie par le théorème de Cantor à car:

As-tu une explication de pourquoi { tel que n et p appartient à N} est dénombrable alors que { tel que n appartient à N} ne l'est pas ?

[nodjim]

Je demandais juste si a et b étaient eux mêmes entiers. Apparemment, la réponse donnée suffit.

[nodjim]

La démo de la coccinelle est un peu juste je trouve....

[Robic]

Pour moi cet ensemble est trivialement démontrable. En effet, tout élément de cet ensemble est de la forme (ab)^n, où ab est donné, donc peut être indexé par n.

Si c'est , c'est encore démontrable car chaque élément peut être indexé par un couple d'entiers, et on sait que NxN est démontrable.

Et de même avec , c'est toujours démontrable puisque chaque élément peut être indexé par un k-uplet d'entiers, et on sait que N^k est démontrable.

Ou alors a et b ne sont pas des constantes données ? Il faudrait peut-être préciser ce qui varie (j'ai supposé que c'était n d'après le premier message.)

[Matt_01]

Tu confondrais pas avec la notion de langage reconnaissable/rationnel ? Dans ce cas le lemme de l'étoile est simple à appliquer.

[y6227]

Pour moi cet ensemble est trivialement démontrable. En effet, tout élément de cet ensemble est de la forme (ab)^n, où ab est donné, donc peut être indexé par n.

Si c'est , c'est encore démontrable car chaque élément peut être indexé par un couple d'entiers, et on sait que NxN est démontrable.

Et de même avec , c'est toujours démontrable puisque chaque élément peut être indexé par un k-uplet d'entiers, et on sait que N^k est démontrable.

Ou alors a et b ne sont pas des constantes données ? Il faudrait peut-être préciser ce qui varie (j'ai supposé que c'était n d'après le premier message.)

Oui seul a et b ne varie pas

[y6227]

Tu confondrais pas avec la notion de langage reconnaissable/rationnel ? Dans ce cas le lemme de l'étoile est simple à appliquer.

Je connais le lemme de l'étoile, mais je ne vois pas comment l'appliquer pour démontrer qu'un langage n'est pas reconnaissable

[y6227]

Problème résolu merci