Dénombrabilité de A^n

[Seirios]

Bonjour à tous,

J'ai lu une démonstration d'un théorème indiquant que si A était un ensemble dénombrable, alors l'était également.

Pour cela, l'auteur indique que est donc dénombrable. Puis il pose l'ensemble dénombrable pour . Un élément de A^n a alors la forme :

avec et

On peut alors identifier comme . Comme une réunion d'ensemble dénombrable est dénombrable, on peut conclure que l'est également.

Mais ce que je n'arrive pas à comprendre, c'est l'équivalence entre et ...

Quelqu'un pourrait-il m'aider ?

Merci d'avance
Phys2
-----

[invité576543]

Mais ce que je n'arrive pas à comprendre, c'est l'équivalence entre et ...

En l'écrivant:



c'est plus clair?

Cordialement,

[Seirios]

c'est plus clair?

Oui c'est effectivement plus clair, je vois bien le lien entre les deux expressions, mais je ne vois pas sur quoi agit la réunion...

[Médiat]

Comme une réunion d'ensemble dénombrable est dénombrable, on peut conclure que l'est également.

Tu voulais sans doute dire réunion dénombrable d'ensembles dénombrables .
(Et selon moi, c'est là le théorème intéressant)

je ne vois pas sur quoi agit la réunion

C'est la réunion disjointe de |||| copies de , distinguées par leur indice pris dans .

[A voir en vidéo sur Futura]

[Seirios]

Tu voulais sans doute dire réunion dénombrable d'ensembles dénombrables .

Oui c'est exactement ce qui est écrit dans mon cours, mais quel est la différence avec ce que j'ai écrit

(Et selon moi, c'est là le théorème intéressant)

C'est un théorème qui avait été démontré précédemment, et qui est utilisé dans ce cas.

[Médiat]

Oui c'est exactement ce qui est écrit dans mon cours, mais quel est la différence avec ce que j'ai écrit

Une réunion non dénombrable d'ensembles dénombrables peut très bien ne pas être dénombrable (l'union de tous les singletons de , est une réunion non dénombrable d'ensembles fini qui n'est pas dénombrable)

[invite986312212]

comme le dit Médiat, le théorème important est celui sur la réunion dénombrable d'ensembles dénombrables. Le théorème sur le produit fini n'en est qu'un corollaire. Mais il a une démonstration plus directe. Dans ta récurrence, tu es amené à montrer qu'un produit BxA d'ensembles dénombrables B et A est dénombrable (B=A^(n-1)). Ca revient sans perte de généralité à trouver une bijection entre N et NxN, et il y a la très classique construction qui consiste à dessiner un parcours en zigzag parmi les points de NxN vus comme un réseau du plan (ou un parcours en spirale parmi les points de ZxZ, autre possibilité)

[Médiat]

Ca revient sans perte de généralité à trouver une bijection entre N et NxN

l'application de NxN das N définie par :
est une telle bijection, si je ne me suis pas pris les pieds dans le tapis

[invite66b0c17a]

@Mediat : Ah oui c'est vrai ! D'où t'es venue cette superbe idée ?

[Médiat]

@Mediat : Ah oui c'est vrai ! D'où t'es venue cette [...] idée ?

Je ne sais pas si tu vas me croire, mais en comptant sur mes doigts .

Il "suffit" (c'est toujours facile après) de remarquer qu'il y a (k+1) façons de faire une somme de 2 entiers dont le total = k, donc pour une somme donnée, il faut compter le nombre de sommes pour tous les totaux plus petits, c'est à dire la somme des entiers plus petit que k, pour savoir combien de couples ont déjà été comptés, après ça va tout seul.

[invite66b0c17a]

Voui j'ai bien vu ça comme ça mais j'y avais jamais pensé. Bravo.

[invité576543]

Ca consiste à numéroter par diagonales, non?

Visuellement, on part de (0,0), puis on redescend à (1, 0), on suit vers "le haut et la gauche" jusqu'à (0,1), on redescend à (2, 0), on suit la diagonale jusqu'à (0,2), on redescend à (3, 0), etc.

C'est pas ça?

Cordialement,

[invité576543]

On peut faire différentes bijection comme ça, en dessinant le graphe, puis en dérivant la formule. J'en avais vu une autre qui remplit les carrés, la succession au début est 0,0 0,1 1,1 0,1 0,2 1,2 2,2 2,1 2,0 3,0 3,1 3,2 3,3 2,3

Traduit en formule ça doit faire un truc compliqué à souhait...

Cordialement,

[Médiat]

Visuellement, on part de (0,0), puis on redescend à (1, 0), on suit vers "le haut et la gauche" jusqu'à (0,1), on redescend à (2, 0), on suit la diagonale jusqu'à (0,2), on redescend à (3, 0), etc.

Presque : on part de
(0,0) puis
(0,1) ; (1, 0) puis
(0,2) ; (1, 1) ; (2, 0) etc.

Pour une somme donnée c'est le plus petit x qui vient en premier (c'est l'ordre lexicographique sur ((x+y), x)).

Bien sur on peut faire le contraire et prendre l'ordre lexicographique sur ((x+y), y)).

[Médiat]

Traduit en formule ça doit faire un truc compliqué à souhait...

Sauf erreur ou omission :

si x >= y (x, y) --> x²+y
si x < y (x, y) --> y²+2y-x

[ericcc]

Moi j'aime bien (x,y)-->2^x(2y+1) comme bijection de NxN dans N

[invite986312212]

il manque le zéro mais autrement c'est pas mal. Moi j'aime bien les "parcours dans un verger" mais c'est vrai qu'une expression analytique d'une bijection de N vers NxN doit faire intervenir la division euclidienne et est moins jolie que celles proposées pour des bijections de NxN vers N.

[taladris]

J'aime bien l'injection de NxN dans N (x,y) -> 2^x3^y