Le premier écueil rencontré est celui du paradoxe de Russel : Le barbier du village rase tous les hommes qui ne se rasent pas eux-mêmes. Question : le barbier se rase-t-il lui-même? Réponse : s'il se rase lui-même, il rase quelqu'un qui se rasait déjà lui-même, donc contradiction. S'il ne se rase pas il omet de raser quelqu'un qui ne se rase pas lui-même, contradiction également.

Ce paradoxe, cité par Russel, mais déjà connu de Zermelo en 1900, est d'une portée générale et s'applique à de nombreuses situations. La variante pour la théorie des ensembles revient à considérer l'ensemble de tous les ensembles qui n'appartiennent pas à eux-mêmes. (Question : cet ensemble appartient-il à lui-même?).

L'existence d'un tel ensemble est paradoxale, donc aussi l'existence de l'ensemble de TOUS les ensembles, dont on ne peut dire si l'objet ci-dessus est élément ou non.

Le paradoxe de Berry (ou de Richard) en est un autre:

Les entiers naturels peuvent être décrits par des énoncés (en français) tels que : « dix puissance cent » ou « le plus grand nombre premier connu au vingtième siècle ». Comme le vocabulaire disponible est fini (mettons qu'il y ait 200 000 mots en français), les énoncés de N mots ne peuvent décrire plus de 200000 N entiers (et en fait beaucoup moins ; la plupart des « phrases » ne voulant en fait rien dire, ou ne parlant pas d'entiers).

L'ensemble des « nombres entiers naturels descriptibles par une expression de quinze mots ou moins » est donc fini; aussi existe-t-il forcément de nombreux entiers hors de cet ensemble. Le plus petit d'entre eux est donc « le plus petit entier naturel non descriptible par une expression de quinze mots ou moins ». Mais justement, cet énoncé qui le décrit parfaitement, ne comporte que quinze mots.

Tous ces paradoxes posent des problèmes de logique relativement complexes, mais fort heureusement aujourd'hui tous résolus. La théorie "naïve" des ensembles, doit être remplacée par une théorie "axiomatique" . Dans une telle théorie, ne mérite le nom d'ensemble que les objets construits à partir d'ensembles existants et d'un certain nombre de 'règles' (axiomes) permettant de construire de nouveaux ensembles. Il existe plusieurs systèmes de formalisation de la théorie des ensembles, le système ZF (Zermelo Frankel) étant le plus connu. Tous ces systèmes évitent en outre les pièges de l'autoréférence (type 'barbier'), en utilisant la notion de métalangage.

Il existe des paradoxes plus 'techniques' relevant de la théorie des ordinaux et des cardinaux, que nous ne mentionnerons pas ici.

Fort heureusement,  pour ce qui concerne les ensembles usuels (ensembles de nombres, de points, de vecteurs, de fonctions), les objets considérés par la théorie naïve, sont constructibles par la théorie axiomatique. On peut donc, dans un premier temps, faire des mathématiques en utilisant le formalisme de la théorie naïve, sans trop s'occuper de ces questions en ayant à l'esprit qu'il s'agit d'une affaire de 'spécialistes' (de logiciens) et que ceux ci contrôlent (à peu près) la situation.