Logique et fondements
L’algèbre de Boole
L’algèbre de Boole est à la base de la théorie des ensembles (le ET logique $\land$ correspond à l’intersection $\cap$ et le OU $\lor$ à l’union $\cup$) et joue ainsi le rôle de “brique élémentaire” de la pensée mathématique.
Monsieur Boole
L’algèbre de Boole est le langage naturelle de la logique et des circuits électroniques à la base de l’informatique.
Infinis dénombrables et indénombrables
Des entiers aux transcendants en passant par l’hypothèse du continu ($\aleph_0 = 2^{\aleph_1}$) :
Cette démonstration de Cantor de l’indénombrabilité des réels révolutionna les mathématiques. On retrouve un “argument diagonal” du même type chez Gödel dans son premier théorème d’incomplétude ou dans le théorème de l’arrêt de Türing.
Mais revenons aux nombres : pourquoi l’argument de la diagonal ne marcherait-il pas avec les entiers ?
Après tout, on pourrait bien lister tous les entiers (en binaire) et on retourne le premier chiffre à la première ligne, le deuxième à la deuxième, etc. Et hop, on a construit un chiffre qui n’est pas dans la liste. Et patatras, on a démontré que l’ensemble dénombrable des entiers est en fait indénombrable…
Bien sûr, on a fait une erreur quelque part. Et en effet, dès le départ, la construction est impossible puisqu’elle suppose que l’écriture d’un entier est faite d’un nombre infini de 1 et de 0. Or par définition, un entier est fini !
Par contre, on montre ainsi que l’ensemble des suites infinis de 1 et de 0 est bien, elle, indénombrable. On n’a pas tout perdu.
On pourrait résister encore en revenant à la démonstration de la vidéo sur l’intervalle $[0\,;\,1]$. Plutôt que de lister les réels, listons les rationnels de l’intervalle. Eux aussi ont des développement décimaux potentiellement infinis après tout. L’argument diagonal semble donc pouvoir marcher…
Et en effet, il marche ! Le nombre fourni par la diagonale n’appartient effectivement pas à $\mathbb{Q}$. Mais si on ne suppose pas que $\mathbb{Q}$ recouvre parfaitement l’intervalle, sans aucun trou, il n’y a pas de contradiction. Le nombre diagonal a justement permis de construire un de ces trous : un nombre irrationnel.
C’est parce qu’on part de l’idée que les réels recouvrent parfaitement (sans trou) l’intervalle que l’argument de Cantor permet de déduire l’indénombrabilité des réels. le nombre diagonal a bien un développement décimal le plaçant dans l’intervalle $[0\,;\,1]$. Il s’agit donc d’un réel puisque, par définition, tout point de cet intervalle est un réel. Or il n’est pas listé. On en conclut que les réels ne sont pas listables (dénombrables).