Cours 2
Théorie des ensembles naïve et Paradoxes
2.1 Paradoxes
2.1.1 Proposition logique
Définition 2.1 (Proposition logique). Une proposition est un énoncée déclaratif dont on peut dire
s’il est vrai ou s’il est faux , indépendamment de tout contexte de lieu, de temps, ou de personne qui
le prononce. De plus, un énoncé qui est à la fois vrai et faux n’est pas une proposition.
Par définition une proposition satisfait les 3 principes suivants :
Principe d’identité :
P est P. Autrement dit si P est vrai alors P est vrai et si P est faux alors P est faux.
Principe de non contradiction :
P ne peut pas à la fois être vrai et faux.
Principe du tiers exclus :
soit P est vrai, soit P est faux. Il n’existe pas d’autre valeur de vérité en logique mathématique.
Ces trois principes constituent le fondement de tout raisonnement mathématique (standard).
2.1.2 Paradoxe du menteur
Epiménides, le crétois, dit : tous les crétois sont des menteurs.
Est-ce que Epiménides est un menteur ?
Qu’en pensez vous ? C’est un paradoxe ? L’assertion "Epiménides est un menteur" est-elle une
proposition ? Quelle est la solution de ce paradoxe ?
Une autre formulation du paradoxe : Un homme disait qu’il était en train de mentir.
Ce que l’homme disait est-il vrai ou faux ? Quelle est maintenant la solution de ce paradoxe ?
2.1.3 Paradoxe du barbier
Un barbier affirme ceci :
"Je rase tous les hommes qui ne se rasent pas eux-mêmes et seulement ceux-là".
Question : qui rase le barbier ? S’il se rase lui-même, alors il rasera quelqu’un qui se rase déjà.
Mais s’il ne se rase pas, il ne rasera pas tous les hommes du village qui ne le font pas eux-mêmes.
Donc, aucune des deux réponses ne semble acceptable.
2.1.4 Paradoxe de Berry
"Le plus petit entier naturel non descriptible par une expression de quinze mots ou moins." Ce
nombre appartient-il à l’ensemble des entiers naturels descriptibles par une expression de quinze mots
ou moins ?
1
2.1.5 Théorie naïve des ensembles
Intuitivement, un ensemble est une collection d’objets qui satisfont une certaine propriété. On est
donc tenté de donner la règle suivante pour la définition d’ensembles : Pour une propriété donnée PX
il existe un ensemble
X = {x |PX (x)}
Ce schéma est dit Schéma de compréhension non restreint.
On peut alors définir toutes les opérations habituelles sur les ensembles.
Si X = {x| PX (x)} et Y = {x| PY (x)} sont des ensembles alors :
— Inclusion : On définit X ⊂ Y ssi PX (x) ⇒ PY (x).
— Union : On définit X ∪ Y = {x| PX (x) ∨ PY (x)}
— Intersection : On définit X ∩ Y = {x| PX (x) ∧ PY (x)}
— Complémentaire : On définit CX Y = {x| PX (x) ∧ ¬PY (x)}
— Ensemble des parties : On définit P(X) = {Y |Y ⊂ X}
2.1.6 Paradoxe de Russel
Cependant, ce principe est faux. En effet, considérons l’ensemble S défini par
( )
S = X|X ∈
/X .
Est-ce que S ∈ S ?
— Si S ∈ S, alors S ∈ / S par définition de S.
— Si S ∈ / S, alors S est tel que S ∈ S.
Dans les deux cas, on arrive à une contraction. C’est le fameux paradoxe de Russel.
On est obligé de conclure que S n’est pas un ensemble. On doit donc redéfinir la notion d’ensemble
afin d’exclure la construction de S, ou d’un autre ensemble posant des problèmes similaires.
La manière la plus sûre d’éliminer les paradoxes de ce type est d’abandonner le schéma de
compréhension, et d’en garder une version affaiblie : le schéma de séparation.
2.1.7 Schéma de Séparation :
Si P est une propriété (avec des paramètres) et x est un ensemble, alors il existe un ensemble
( ) ( )
y = z|z ∈ x ∧ P (z) = z ∈ x|P (z)
Une fois le schéma de compréhension éliminé, le paradoxe de Russell n’est plus aussi inquiétant On
doit donc ajouter des axiomes supplémentaires afin d’obtenir une théorie des ensembles satisfaisante.
On a développé par exemple la théorie ZF(C) qui est basée sur la logique formelle du premier ordre.
Voir par exemple le cours : Théorie des ensembles 1 .
Remarque 1. Les mathématiciens ont raisonné correctement durant des siècles sans connaître la
logique formelle. La logique moderne est née de l’ambition de formaliser (mécaniser) le raisonne-
ment mathématique : ce projet a reçu une impulsion décisive quand il est apparu que l’absence de
formalisation pouvait conduire à des contradictions. Le développement actuel de la logique continue
avec
— le besoin de prouver la correction des programmes (particulièrement quand ces programmes
sont utilisés dans des domaines où la sécurité est en jeu)
— l’ambition de représenter en machine l’ensemble des connaissances mathématiques
1. Théorie des ensembles : Thomas Seiller
2
2.2 Dénombrabilité
2.2.1 Introduction
Question 1. Y a-t-il moins de nombres pairs que d’entiers dans N?
Question 2. Y a-t-il plus de réels dans ]0; 1[ ou ]1; +∞[?
Intuitivement, il y a autant de droites qui passent au dessus de la première bissectrice que de
droites qui passent en dessous. Pourtant ces droites sont paramétrées pas y = ax avec a ∈]0; 1[ en
dessous et y ∈]1; +∞[ au dessus... Comment comparer le nombre d’éléments d’ensembles infinis ?
Cette question a été étudiée par le mathématicien allemand Georg Cantor (1845-1918).
2.2.2 Rappels
Définition 2.2.
** Une fonction f : A → B est injective si ∀(x, y) ∈ A2 , f (x) = f (y) ⇒ x = y.
** Une fonction f : A → B est surjective si ∀y ∈ B, ∃x ∈ A, f (x) = y.
** Une fonction f : A → B est bijective si ∀y ∈ B, ∃!x ∈ A, f (x) = y. (surjective et injective à la
fois).
Définition 2.3.
On dit que deux ensembles A et B sont équipotents s’il existe une bijection entre A et B.
Exemple. 1. [|1, n|] et [|n + 1, 2n|] sont équipotents. 2. N et N∗ sont équipotents. 3. 2N et 2N + 1
sont équipotents. 4. N et 2N sont équipotents. 5. ]0, 1[ et ]1, +∞[ sont équipotents.
Définition 2.4. On dit qu’un ensemble est dénombrable s’il est équipotent à N, ie. s’il existe une
bijection entre cet ensemble et N.
Proposition 2.1.
— Toute partie infinie de N est dénombrable.
— Z est dénombrable.
— Z × N est dénombrable
— N2 , Z × N∗ et Q sont dénombrables.
— Le produit cartésien fini de dénombrable est dénombrable.
— Union dénombrable d’ensembles dénombrables est dénombrables.
Corollaire. L’ensemble des mots sur un alphabet fini est dénombrable.
Montrons par exemple que N∗ × N∗ est dénombrable.
Cette bijection revient à disposer N∗ × N∗ sous forme de matrice infinie et à décrire ce tableau en
parcourant les diagonales : (1, 1), (2, 1), (1, 2), (1, 3), (2, 2), (3, 1), etc · · ·
L’équipotence se conservant dans les produits cartésiens, on en déduit que le produit de deux
ensembles dénombrables est dénombrable.
3
2.2.3 Exemples d’ensembles non dénombrables : la puissance du continu
L’exemple le plus simple d’ensemble non dénombrable est l’ensemble P (N) des parties de N. On
peut en fait démontrer simplement un théorème plus général.
Théorème 2.1 (Cantor, 1891). Soit E un ensemble. Il n’existe pas de bijection E → P(E).
Démonstration. Supposons qu’il existe une telle bijection f : E → P(E). Posons
( )
F = x ∈ E|x ∈
/ f (x) .
Puisque F ⊂ E, on peut trouver x0 tel que f (x0 ) = F. On a donc soit x0 ∈ F, soit x0 ∈
/ F.
— Si x0 ∈ F, par définition, x0 ∈/ f (x0 ) = F, une contradiction
— Si x0 ∈/ F, par définition, x0 ∈ f (x0 ) = F, une contradiction
L’hypothèse de départ était donc absurde : il n’existe pas de telle bijection.
Théorème 2.2 (Cantor-Schröder-Bernstein, 1895). . Soit E et F deux ensembles. S’il existe une
injection de E dans F et une injection de F dans E, E et F sont en bijection.
Ce théorème implique que si l’on a deux fonctions E → F , l’une injective et l’autre surjective,
alors E et F sont en bijection.
Corollaire. L’ensemble Rn est équipotent à R.
Démonstration. On démontre cette propriété pour n = 2, le cas général s’en déduit par récurrence.
Tout d’abord l’application φ de R dans R2 qui à x associe (x, 0) est injective. Soit maintenant (x, y)
dans R2 , si l’on écrit ces nombres en base 10
+∞ +∞
an 10−n bn 10−n
X X
x= et y=
−p −q
on associe à (x, y) le nombre
+∞ +∞
−2n
bn 10−2n−1
X X
ψ(x, y) = an 10 +
−p −q
et l’application ψ est une application injective de R2 dans R.
Exercice 2.1.
Montrer que tout intervalle I de R non vide, et non réduit à un point est équipotent à R.
Théorème 2.3 (Cantor). R n’est pas dénombrable.
Démonstration.(Idée) On va montrer qu’il n’existe pas de surjection de N dans ]0, 1[. Par l’
absurde on suppose que l’ on peut numéroter les éléments de [0, 1] :
x1 = 0, a11 a12 · · · a1n · · ·
x2 = 0, a21 a22 · · · a2n · · ·
··· ...
xp = 0, ap1 ap2 · · · apn · · ·
On considère vi = aii + 1mod10 alors 0, v1 v2 · · · vk · · · a une place dans la liste précédente : mettons la
place m alors am m
m = am + 1mod10 ce qui est absurde.
Les ensembles équipotents à R sont dits de puissance continue.
Hypothèse du continue Tout sous-ensemble de l’ensemble des nombres réels est soit fini, soit
infini dénombrable, soit possède la puissance du continu. Ce n’est pas un théorème. Paul Cohen, en
se basant sur les travaux de Gödel, montra en 1963 que cette conjecture était indécidable.
