Mathématiques pour l'informatique 201-N11 • Cégep à Montréal

Fiche de révision : théorie des ensembles et relations (201-N11)

La théorie des ensembles paraît abstraite jusqu'au premier contrôle, où l'on découvre que la moitié des points se perdent sur deux symboles : $\in$ et $\subset$ . Écrire $3\subset A$ n'est pas une maladresse d'écriture, c'est une phrase qui n'a pas de sens.

Cette fiche rassemble les gestes qui décident : distinguer les deux niveaux, remplir un diagramme de Venn depuis le centre, et réfuter une propriété de relation par un seul contre-exemple bien choisi.

Mis à jour le 17 octobre 2026

Marque ici la fiche comme lue ou mets-la en favori : un compte gratuit, sans mot de passe, retient tes fiches lues et tes favoris d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander la méthode ou l'exercice qui te manque. Crée ton espace, un courriel suffit.

Le fil du chapitre

Presque toutes les erreurs du chapitre viennent d'un mélange de NIVEAUX : celui des éléments et celui des ensembles, autrement dit l'appartenance et l'inclusion.

Ce chapitre fait partie de Mathématiques pour l'informatique, 201-N11

Pour s'entraîner Les exercices corrigés de ce chapitre, 10 exercices

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Logique booléenne et mathématique Exercices

Notions couvertes

Appartenance et inclusion
Ensemble des parties
Produit cartésien
Lois de De Morgan
Principe d'inclusion-exclusion
Diagramme de Venn
Relation binaire
Relation d'équivalence
Relation d'ordre
Classe d'équivalence
Partition d'un ensemble
Fermeture transitive

L'essentiel

Deux niveaux : les éléments et les ensembles

• $x\in A$ relie un ÉLÉMENT à un ensemble ; $A\subset B$ relie deux ENSEMBLES.
• $3$ et $\{3\}$ ne sont pas la même chose : le second est un ensemble qui contient le premier.
• $\varnothing\subset A$ toujours, et $\varnothing\in\mathcal{P}(A)$ toujours ; mais $\varnothing\in A$ presque jamais.
• $|\mathcal{P}(X)|=2^{|X|}$ : chaque élément est pris ou laissé, ce qui fait deux choix par élément.

L'ensemble

A

contient les éléments

1

2

et l'ensemble

\{3\}

: donc

\{3\}\in A

3\notin A

Le test à faire avant d'écrire un symbole : ce qui est à gauche est-il un élément ou un ensemble ? La réponse choisit le symbole, et l'inverse n'est jamais vrai.

Opérations, De Morgan et comptage

• De Morgan : $\overline{A\cup B}=\overline{A}\cap\overline{B}$ et $\overline{A\cap B}=\overline{A}\cup\overline{B}$ .
• Différence : $A\setminus B=A\cap\overline{B}$ , ce qui ramène toute différence à une intersection.
• Inclusion-exclusion à deux ensembles : $|A\cup B|=|A|+|B|-|A\cap B|$ .
• À trois ensembles : on retranche les trois intersections deux à deux, puis on RAJOUTE l'intersection triple, retirée trois fois.

La partie bleue de gauche est

\overline{A\cup B}

: hors de

A

ET hors de

B

\overline{A}\cap\overline{B}

. À droite,

\overline{A\cap B}

: hors de la lentille,

\overline{A}\cup\overline{B}

Remplir un diagramme de Venn commence TOUJOURS par la région centrale, puis les intersections deux à deux, puis les zones isolées : dans cet ordre, aucune soustraction ne se fait à l'aveugle.

Les quatre propriétés d'une relation

• RÉFLEXIVE : tous les couples $(x,x)$ y sont. SYMÉTRIQUE : si $(x,y)$ y est, alors $(y,x)$ aussi.
• ANTISYMÉTRIQUE : si $(x,y)$ et $(y,x)$ y sont tous deux, alors $x=y$ . TRANSITIVE : si $(x,y)$ et $(y,z)$ y sont, alors $(x,z)$ aussi.
• Réflexive, antisymétrique et transitive : relation d'ORDRE. Réflexive, symétrique et transitive : relation d'ÉQUIVALENCE.
• Une relation se décrit par ses couples, par sa matrice booléenne ou par son graphe sagittal : trois écritures du même objet.

Boucle sur chaque sommet (réflexive) ; chaque flèche a son retour (symétrique) ; aucun aller-retour entre sommets distincts (antisymétrique) ; chaque chemin de deux flèches a son raccourci vert (transitive).

Une propriété se PROUVE sur tous les cas, mais se RÉFUTE par un seul contre-exemple. C'est ce qui rend la réfutation trois fois plus rapide, et c'est ce que le barème attend.

Classes, partitions et fermeture transitive

• Les classes d'une relation d'équivalence forment une PARTITION : non vides, deux à deux disjointes, de réunion l'ensemble entier.
• Deux classes sont donc égales ou disjointes : elles ne se chevauchent jamais partiellement.
• Fermeture transitive : réunion de toutes les puissances $S$ , $S^{2}$ , $S^{3}$ ... Un couple $(i,j)$ y figure s'il existe un CHEMIN de $i$ vers $j$ , de n'importe quelle longueur.

Modulo

3

, l'ensemble

\{0,\ldots,8\}

se range en trois classes

[0]

[1]

[2]

: non vides, disjointes, et dont la réunion est tout l'ensemble.

Sur un ensemble à $n$ éléments, il suffit d'aller jusqu'à $S^{n-1}$ : un chemin plus long repasserait par un sommet déjà visité, sans rien ajouter.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Écrire une inclusion là où il faut une appartenance

0,5 point par occurrence, et il y en a plusieurs par copie

Ce qu'il ne faut pas écrire

« $3\subset A$ , puisque $3$ est dans $A$ . »

Ce qu'il faut écrire

« $3\in A$ : $3$ est un élément. On écrirait $\{3\}\subset A$ pour dire la même chose au niveau des ensembles. »

Pourquoi : Les deux symboles relient des objets de nature différente. L'un des deux est toujours faux, et le correcteur le repère avant même de lire le raisonnement.

2. Faire appartenir l'ensemble vide à tout

1,5 point, et deux lignes du tableau vrai-faux

Ce qu'il ne faut pas écrire

« $\varnothing\in A$ pour tout ensemble $A$ . »

Ce qu'il faut écrire

« $\varnothing\subset A$ toujours, et $\varnothing\in\mathcal{P}(A)$ toujours ; mais $\varnothing\in A$ seulement si on l'a explicitement mis dans $A$ . »

Pourquoi : L'ensemble vide est inclus partout parce qu'il n'a aucun élément à faire échouer l'inclusion. Y appartenir est tout autre chose : il faudrait qu'il soit listé comme élément.

3. Compter les parties comme un carré

1,5 point, et un dénombrement complet à refaire

Ce qu'il ne faut pas écrire

« $X$ a $5$ éléments, donc $\mathcal{P}(X)$ en a $25$ . »

Ce qu'il faut écrire

« $|\mathcal{P}(X)|=2^{5}=32$ : chaque élément est pris ou laissé. »

Chaque élément est pris ou laissé : trois éléments donnent

2\times 2\times 2=8

parties, de

\varnothing

\{a,b,c\}

, et non

3^{2}=9

Pourquoi : Le choix se fait élément par élément, indépendamment : deux possibilités par élément donnent une puissance de deux, jamais un carré. Le contrôle : $\mathcal{P}(\varnothing)$ a exactement une partie.

4. Additionner les effectifs de deux ensembles qui se recouvrent

2 points, et un total qui peut dépasser l'effectif interrogé

Ce qu'il ne faut pas écrire

« $65$ connaissent Python et $45$ connaissent Java, donc $110$ connaissent au moins l'un des deux. »

Ce qu'il faut écrire

« $|P\cup J|=65+45-25=85$ : les $25$ qui connaissent les deux ont été comptés deux fois. »

Les

25

qui connaissent les deux langages sont dans les deux cercles (rouge) :

65+45

les compte deux fois, d'où

40+25+20=85

Pourquoi : Le contrôle est immédiat : un sous-total supérieur à la population totale est impossible. C'est le premier réflexe de vérification du chapitre.

5. Remplir un diagramme de Venn en partant de l'extérieur

2 points, et un diagramme entier à refaire

Ce qu'il ne faut pas écrire

« Je mets $65$ dans la zone Python, $45$ dans Java, puis j'ajuste. »

Ce qu'il faut écrire

« Je commence par la région CENTRALE, $10$ , puis je remonte : $P\cap J$ seul vaut $25-10=15$ , et $P$ seul vaut $65-25-20+10=30$ . »

L'ordre de remplissage : d'abord le centre (1), puis les trois intersections deux à deux (2), enfin les zones d'un seul ensemble (3) ; chaque zone se déduit des précédentes.

Pourquoi : Chaque zone extérieure se déduit des zones intérieures déjà connues. En partant du bord, chaque nombre écrit doit être corrigé ensuite, et les corrections s'emmêlent.

6. Prendre l'antisymétrie pour l'absence de symétrie

2 points, et la classification en ordre ou équivalence tombe

Ce qu'il ne faut pas écrire

« La relation n'est pas symétrique, donc elle est antisymétrique. »

Ce qu'il faut écrire

« Antisymétrique signifie : si $(x,y)$ ET $(y,x)$ y sont, alors $x=y$ . Une relation peut n'être ni l'une ni l'autre. »

À gauche, les deux flèches entre

a

b

: symétrique. À droite, une seule : antisymétrique. L'absence de la seconde flèche ne suffit pas à conclure dans l'autre sens.

Pourquoi : Les deux propriétés ne sont pas complémentaires. La relation $\{(1,2),(2,1),(2,3)\}$ n'est ni symétrique, puisque $(3,2)$ manque, ni antisymétrique, puisque $1\neq 2$ .

7. Réfuter une propriété en vérifiant un seul cas favorable

2 points, et la conclusion est inversée

Ce qu'il ne faut pas écrire

« $(1,2)$ et $(2,3)$ sont dans $R$ , et $(1,3)$ aussi, donc $R$ est transitive. »

Ce qu'il faut écrire

« Il faut vérifier TOUS les couples enchaînables ; un seul enchaînement sans raccourci suffit à réfuter la transitivité. »

Un chemin de

1

vers

3

en passant par

2

, sans arc direct : la relation n'est pas transitive, et ce seul dessin le prouve.

Pourquoi : Une propriété universelle se prouve sur tous les cas et se réfute par un seul. Vérifier un cas favorable ne démontre rien du tout.

8. Croire que des classes d'équivalence peuvent se chevaucher

2 points, et la question sur la partition

Ce qu'il ne faut pas écrire

« La classe de $2$ et celle de $5$ ont un élément commun, mais elles restent distinctes. »

Ce qu'il faut écrire

« Deux classes ayant un élément commun sont ÉGALES : les classes forment une partition. »

Pourquoi : Si $z$ appartient aux deux classes, la transitivité relie tous les éléments de l'une à tous ceux de l'autre. Il n'y a donc pas de chevauchement partiel possible.

9. Arrêter la fermeture transitive aux chemins de longueur deux

1,5 point, et des couples manquants dans la matrice finale

Ce qu'il ne faut pas écrire

« J'ajoute les couples obtenus par $S^{2}$ et c'est terminé. »

Ce qu'il faut écrire

« La fermeture est la réunion de $S$ , $S^{2}$ , jusqu'à $S^{n-1}$ : un chemin peut traverser trois arcs ou plus. »

S

relie

1

2

3

4

en chaîne ;

S^{2}

ajoute

(1,3)

(2,4)

(orange) ; s'arrêter là oublie

(1,4)

, chemin de trois flèches (rouge).

Pourquoi : Ajouter les raccourcis de longueur deux crée de nouveaux enchaînements, qui en créent d'autres. Sur $n$ sommets, un chemin utile ne dépasse jamais $n-1$ arcs, mais il peut les atteindre.

Quelle méthode choisir

Tester les quatre propriétés d'une relation

On liste les couples, puis on teste dans cet ordre, en cherchant d'abord à RÉFUTER.

Si un élément $x$ n'a pas son couple $(x,x)$ → la relation n'est pas réflexive, et c'est terminé

Exemple : sur un ensemble à trois éléments, il manque le couple 3-3

c'est le test le plus rapide : il se lit sur la diagonale de la matrice
Si un couple $(x,y)$ y est sans que $(y,x)$ y soit → elle n'est pas symétrique

Exemple : $(1,2)$ présent, $(2,1)$ absent
Si deux couples $(x,y)$ et $(y,x)$ y sont avec $x\neq y$ → elle n'est pas antisymétrique

Exemple : $(1,2)$ et $(2,1)$ avec $1\neq 2$
Si deux couples $(x,y)$ et $(y,z)$ y sont sans $(x,z)$ → elle n'est pas transitive

Exemple : $(1,2)$ et $(2,3)$ sans $(1,3)$
Si aucun contre-exemple n'apparaît → démontrer la propriété dans le cas général, en partant des hypothèses

Exemple : « soit $(x,y)$ et $(y,z)$ dans $R$ ; alors... »

L'ordre compte : réflexivité d'abord, car elle se lit d'un coup d'œil sur la diagonale et disqualifie aussitôt un ordre comme une équivalence.

Quel outil de comptage

On regarde ce que l'énoncé demande de compter.

Si les éléments d'une réunion de deux ensembles qui se recouvrent → $|A|+|B|-|A\cap B|$

Exemple : $65+45-25=85$
Si les éléments d'une réunion de trois ensembles → les trois effectifs, moins les trois intersections doubles, plus l'intersection triple

Exemple : $65+45+30-25-20-15+10=90$
Si les éléments qui ne sont dans AUCUN des ensembles → effectif total moins le cardinal de la réunion

Exemple : $100-90=10$
Si les sous-ensembles d'un ensemble → $2^{|X|}$ , y compris l'ensemble vide et $X$ lui-même

Exemple : $2^{5}=32$
Si les couples d'un produit cartésien → $|A|\times|B|$ , l'ordre comptant dans un couple

Exemple : $4\times 3=12$ couples

Un diagramme de Venn rend l'inclusion-exclusion inutile : une fois les sept régions remplies, tout se lit par simple addition. C'est aussi ce qui permet de vérifier la formule.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Démontrer une égalité d'ensembles par double inclusion

Quand l'utiliser : L'énoncé demande de montrer que deux expressions ensemblistes sont égales, comme une loi de De Morgan.

1 Annoncer la méthode : « Je montre les deux inclusions. »
2 Premier sens : « Soit $x\in$ membre de gauche », puis dérouler les définitions jusqu'au membre de droite.
3 Second sens : reprendre depuis « Soit $x\in$ membre de droite ».
4 Conclure : les deux inclusions donnent l'égalité.

Phrase de conclusion

« Soit $x\in\overline{A\cup B}$ . Alors $x\notin A$ et $x\notin B$ , donc $x\in\overline{A}\cap\overline{B}$ . La réciproque se démontre de même, donc les deux ensembles sont égaux. »

Le piège : Ne faire qu'une inclusion et conclure à l'égalité : le barème compte les deux sens séparément.

Barème : 1,5 point par inclusion, 0,5 point la conclusion. Un raisonnement par équivalences vaut les trois points s'il est écrit avec des « si et seulement si ».

Classer une relation en ordre ou en équivalence

Quand l'utiliser : L'énoncé donne une relation et demande sa nature.

1 Écrire la liste des couples, ou la matrice booléenne si elle est fournie.
2 Tester la réflexivité sur la diagonale, et conclure aussitôt si elle échoue.
3 Tester symétrie et antisymétrie, en donnant un contre-exemple explicite quand la propriété échoue.
4 Tester la transitivité sur tous les enchaînements, puis nommer la nature de la relation.

Phrase de conclusion

« $R$ est réflexive, symétrique et transitive : c'est une relation d'équivalence, et ses classes forment une partition de $E$ . »

Le piège : Conclure « ce n'est pas une relation d'ordre » sans dire laquelle des trois propriétés échoue ni donner le contre-exemple.

Barème : 0,5 point par propriété correctement tranchée avec sa justification, 1 point la conclusion nommée.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

Le total ne dépasse pas la population

Après une inclusion-exclusion, comparer le cardinal obtenu à l'effectif total interrogé.

$110$ pour une réunion dans un groupe de $100$ : une intersection a été oubliée.
La somme des régions du diagramme

Additionner les sept régions du Venn : on doit retrouver le cardinal de la réunion, et en ajoutant l'extérieur, l'effectif total.

$30+15+5+15+10+5+10=90$ , plus $10$ à l'extérieur, soit $100$ .
Le compte des parties est une puissance de deux

Vérifier que le nombre de sous-ensembles trouvé est bien $2^{|X|}$ , et qu'il inclut l'ensemble vide et $X$ .

Un ensemble à $4$ éléments a $16$ parties, dont $\varnothing$ et lui-même.
Le contre-exemple est écrit

Chaque propriété réfutée doit être accompagnée du couple précis qui la met en défaut, pas d'une phrase générale.

« Pas transitive » sans couple ne rapporte rien ; « $(1,2)$ et $(2,3)$ sans $(1,3)$ » rapporte le point.

L'exercice type décortiqué

Sondage sur les langages de programmation

Sur $100$ étudiants, $65$ connaissent Python, $45$ Java, $30$ le langage C. De plus, $25$ connaissent Python et Java, $20$ Python et C, $15$ Java et C, et $10$ connaissent les trois.

Combien n'en connaissent aucun, et combien n'en connaissent qu'un seul ?

Les trois langages et leurs sept régions, encore vides : on les remplit en partant du centre, avant de répondre.

Étape 1

Région centrale : $10$ étudiants connaissent les trois langages.

Pourquoi

C'est la seule donnée qui n'a besoin d'aucune soustraction. Toutes les autres régions se déduiront d'elle, ce qui impose de commencer ici.

Étape 2

Intersections doubles exclusives : $25-10=15$ pour Python et Java seuls, $20-10=10$ pour Python et C, $15-10=5$ pour Java et C.

Pourquoi

Les $25$ de l'énoncé incluent les $10$ qui connaissent aussi le troisième langage. On retire donc la région centrale une fois, et une seule.

Étape 3

Python seul : $65-25-20+10=30$ .

Pourquoi

On retire les deux intersections, ce qui enlève deux fois les $10$ du centre ; on les remet donc une fois. C'est l'inclusion-exclusion appliquée à une seule zone.

Étape 4

Java seul : $45-25-15+10=15$ . Langage C seul : $30-20-15+10=5$ .

Pourquoi

Le même schéma se répète, avec les deux intersections qui concernent chaque ensemble. Trois calculs de même forme, donc trois occasions de vérifier le motif.

Étape 5

Réunion : $65+45+30-25-20-15+10=90$ , donc $100-90=10$ ne connaissent aucun des trois.

Pourquoi

La formule donne directement la réunion, et le complément se lit par soustraction sur l'effectif total. Les deux voies, formule et diagramme, doivent coïncider.

Étape 6

Exactement un langage : $30+15+5=50$ étudiants.

Pourquoi

« Exactement un » ne se lit que sur les régions exclusives, jamais sur les données brutes de l'énoncé, qui comptent chacun plusieurs fois.

Étape 7

Contrôle : $30+15+5+15+10+5+10=90$ , et $90+10=100$ .

Pourquoi

La somme des sept régions plus l'extérieur redonne l'effectif total. Un écart d'une unité signale une soustraction faite deux fois.

Conclusion rédigée

« $10$ étudiants ne connaissent aucun des trois langages, et $50$ n'en connaissent qu'un seul. »

L'erreur classique sur cet exercice : Répondre $65$ à la question « combien ne connaissent que Python » : ce nombre compte aussi ceux qui en connaissent deux ou trois.

À savoir par cœur

• $\in$ relie un élément à un ensemble, $\subset$ relie deux ensembles. $3$ et $\{3\}$ sont deux objets différents.
• $\varnothing\subset A$ toujours ; $\varnothing\in A$ presque jamais.
• $|\mathcal{P}(X)|=2^{|X|}$ : deux choix par élément, pris ou laissé.
• $|A\cup B|=|A|+|B|-|A\cap B|$ ; à trois ensembles, on retranche les trois doubles puis on RAJOUTE la triple.
• Un diagramme de Venn se remplit depuis la région CENTRALE.
• Ordre : réflexive, antisymétrique, transitive. Équivalence : réflexive, symétrique, transitive.
• Les classes d'équivalence forment une PARTITION : égales ou disjointes, jamais partiellement communes.
• Une propriété se réfute par UN contre-exemple, et se prouve sur tous les cas.

Questions fréquentes

Quelle différence entre appartenir et être inclus ?

Appartenir relie un élément à un ensemble, être inclus relie deux ensembles. Le nombre trois appartient à un ensemble qui le contient, tandis que l'ensemble formé du seul nombre trois y est inclus. Écrire le mauvais symbole ne donne pas une phrase maladroite mais une phrase sans signification.

Combien de sous-ensembles a un ensemble à cinq éléments ?

Trente-deux, soit deux puissance cinq. Chaque élément est indépendamment pris ou laissé, ce qui fait deux possibilités par élément. Ce compte inclut l'ensemble vide et l'ensemble tout entier. Un ensemble vide a donc exactement une partie, lui-même.

Comment remplir un diagramme de Venn à trois ensembles ?

En commençant toujours par la région centrale, celle des éléments communs aux trois. On remonte ensuite aux intersections deux à deux en retirant le centre, puis aux zones isolées en retirant les deux intersections qui les touchent et en remettant le centre. Dans cet ordre, aucun nombre écrit n'a besoin d'être corrigé ensuite.

Une relation non symétrique est-elle antisymétrique ?

Non, les deux notions ne sont pas complémentaires. L'antisymétrie exige que la présence simultanée des deux couples force l'égalité des deux éléments. Une relation peut parfaitement n'être ni symétrique ni antisymétrique, par exemple si elle contient les couples un vers deux, deux vers un, et deux vers trois.

Deux classes d'équivalence peuvent-elles avoir un élément commun ?

Seulement si elles sont égales. Dès qu'un élément appartient aux deux, la transitivité relie tous les éléments de la première à tous ceux de la seconde, et les deux classes coïncident. C'est ce qui fait des classes une partition : elles sont non vides, deux à deux disjointes, et leur réunion est l'ensemble entier.

Passer à la pratique

Exercices corrigés : Théorie des ensembles et relations

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

10 exercices corrigés
100 points
150 minutes

Faire les exercices

Il manque quelque chose dans cette fiche ? Une méthode, un piège, un exercice pour l'appliquer, une erreur repérée : dis-le-moi, je lis chaque demande.

L'envoi passe par ton espace gratuit : c'est ce qui me permet de te répondre et de te prévenir quand l'exercice est ajouté. Un courriel suffit, pas de mot de passe. Crée ton espace. Pas envie de créer un compte ? Écris-moi directement.

Fiche précédente L'arithmétique modulaire Fiche suivante Fonctions injectives, surjectives, bijectives

Ce chapitre resservira dans

Les chapitres qui le réclament en amont, plus tard dans l'année ou dans les années suivantes.

Fonctions injectives, surjectives, bijectives Récurrence et récursivité Introduction aux graphes et aux matrices Dénombrement et probabilités

© Ahmed Squalli Houssaini. Fiche publiée sur www.letuteurscientifique.ca/fiches/n11-ensembles-relations. Libre pour l'usage personnel et en classe ; sa republication ailleurs demande une autorisation écrite (mentions légales).

Voir aussi

Toutes les fiches Tous les exercices Tutorat au cégep Maths et informatique au cégep

Vous suivez le cours 201-N11 en informatique au cégep ?

Contactez-moi pour une première séance. Bachelier en informatique de McGill et maître en informatique appliquée de Concordia, je relie les ensembles et les relations à ce qu'ils deviennent ensuite : les requêtes SQL, les tables de hachage et les graphes.

Me contacter WhatsApp

Site par Studio Squalli