Quelques bizarreries de $ \mathbb{N} $

Quelqu’un de plus expert que moi sur ce sujet pourra compléter (ou corriger) : L’ensemble des parties de $\N$ est en bijection avec l’ensemble $\R$. Ensuite, il me semble que l’on se ramène à la notion de réel calculable : Wikipedia.

Bonjour.

Je rajouterais juste que s'il existe des sous-ensembles de N facilement descriptibles, il y en a par contre qui ne peuvent être décrits qu'en énumérant la liste (finie ou infinie) de leurs éléments (c'est sans doute le sens derrière l'expression "indescriptible" de Pablo), ce qui n'est pas vraiment un problème d'existence, comme ce qui est sous-entendu.

À bientôt.

@Pablo : il n'y a rien de bien mystérieux là-dessous.
Modulo la thèse de Church (voir wikipédia), un ensemble $A \subseteq \mathbb{N}$ est récursif s'il existe un algorithme qui, pour tout $x \in \mathbb{N}$, te dit en un temps fini si $x \in A$ ou si $x \notin A$.

$A$ est récursivement énumérable (re) si l'algorithme te donne la réponse en un temps fini si $x \in A$ et diverge (c'est-à-dire boucle indéfiniment) si $x \notin A$. Donc un ensemble est récursif ssi il est re ainsi que son complémentaire. (Il suffit de faire tourner deux machines et d'attendre laquelle va cracher le morceau).

Si un ensemble est re, on peut considérer qu'il est définissable (par exemple par une formule qui code la machine ou l'algorithme).

Il est assez facile de démontrer qu'il n'y a qu'une famille dénombrable de parties de $\mathbb{N}$ qui sont re. Donc, par le principe des tiroirs, il y en a "beaucoup" (à vrai dire autant que de nombres réels) qui ne sont pas définissables. Et pourtant elles existent. C'est la vie...

Ok Gérard,
En effet mon prof de Licence disait cela aussi à l’oral : « quand je dis dénombrable c’est pour dire au plus dénombrable. ».