Paradoxe de Richard: Si nous numérotons tous les nombres réels définissables en un nombre fini de mots, alors nous pouvons construire en utilisant l’argument de la diagonale de Cantor un nombre réel hors de cette liste. Pourtant ce nombre a été défini en un nombre fini de mots.

Paradoxe de Russell: L’ensemble des ensembles n’appartenant pas a eux-mêmes appartient-il a lui-même?

Paradoxe de Berry: Le plus petit entier naturel non descriptible pour une expression de quinze mots ou moins.

Paradoxe de Burali-Foti: Soit Ω l’ensemble de tous les ordinaux. Comme Ω détient toutes les propriétés d’un nombre ordinal, il est lui-même un nombre ordinal. Cependant, cet ordinal doit être un élément de Ω car Ω contient tous les nombres ordinaux. Aussi Ω doit être strictement inférieur à Ω.

Paradoxe de Cantor: Si le plus grand cardinal est un ensemble, il a donc un ensemble des parties, qui a alors un cardinal strictement supérieur à ce plus grand cardinal.

En interprétant ces paradoxes dans le cadre de la complexité de Kolmogorov, il est possible de les coder de manière plus formelle. Dans e cadre général de la théorie algorithmique de l’information, Chaitin a défini la constante Ω qui représente un nombre réel qui exprime la probabilité qu’un programme aléatoire s’arrête. Il met en exergue de manière innovante l’incomplétude des mathématiques qui sont suffisamment puissantes pour contenir de l’indécidable.