Salut,

J'aimerais savoir quand un ensemble est dénombrable ?

D'après ce que je sais c'est quand il existe une bijection entre cet ensemble et N. Mais du coup je vois pas pourquoi Q est dénombrable

De même, pourquoi l'ensemble des fonctions de N dans {0;1} n'est pas dénombrable ?

Pour montrer que Q est dénombrable tu as plein de façon différente. Tu peux montrer qu'un produit d'ensemble dénombrable est dénombrable s et comme Z et N le sont tu peux (modulo l'unicité de l'écriture d'un rationnel) montrer que Q l'est
Tu peux aussi exhiber directement une bijection en utilisant un argument diagonal (ou alors c'est pour NxN mais ça revient à peu près à Q).

Pour la non dénombrabilité des suites de 0 et de 1, tu peux utiliser le fait que l'ensemble des parties de N et l'ensemble des suites de 0 et de 1 sont en bijection et que l'ensemble des parties d'un ensemble dénombrable n'est pas dénombrable. Ou aussi tu peux arriver à montrer que ça revient à montre la dénombrabilité de R, or R n'est pas dénombrable.

Je rajouterais que la dénombrabilité, c'est quelque chose de difficile à percevoir

Comme tu l'as dis, un ensemble E est dénombrable si et seulement si il existe une bijection entre E et N. Mais cette bijection peut parfois être très difficile à trouver. Pire, notre intuition nous hurle que ce n'est pas possible pour certains ensembles. Si on veut bien croire que Z est dénombrable, le fait que Q soit dénombrable n'est, tout de suite, pas très trivial, car c'est un ensemble vraiment très gros, comparé à N. Et comme l'a dit Belzeborg, on peut voir effectivement Q comme une partie de N x Z*, qui, effectivement, est un ensemble vachement gros quand on y pense.

Mais étrangement on arrive à trouver une bijection, et il y a même un dessin qui permet de la justifier (par l'argument diagonal chelou énoncé par Belzeborg, je l'ai vu en partiel l'année dernière et ... faut y penser quoi ).

En tout cas, le plus important, c'est de trouver une façon de "numéroter" les nombres. Genre les rationnels je peux les écrire r_1, r_2, r_3 ... Et ça se voit par le dessin que j'ai cité juste au-dessus. Pour certains ensembles cependant, ce n'est pas possible (genre R ... C'est un ensemble beaucoup, beaucoup trop gros pour qu'on puisse ne serais-ce que numéroter les réels).

Ce qu'il faut se dire c'est que le caractère équipotent c'est vraiment la forme la plus grossière de comparaison de structures. Évidemment qu'on comprend très facilement que Q est bien plus gros que IN, mais c'est parce qu'on pense pas juste à Q en tant que partie (à bijection près) de Z x IN* mais bien parce qu'on lui infère toutes ses caractéristiques algébriques (de corps) et toute sa topologie et son ordre.

Le fait est qu'il n'y a évidemment aucun isomorphisme que ça soit topologique ou algébrique entre IN et Q, par contre, en oubliant toutes ces propriétés (ce qui n'est pas si évident que ça), on peut effectivement trouver des moyens biscornus de compter les rationnels avec les entiers naturels. L'idée va souvent être de faire apparaître des constructions géométriques.