Introduction aux Ensembles et Propriétés Ensemblistes Formelles

1. Définitions formelles : des objets et des propriétés

Bien que la notion d'ensemble soit intuitive (une "collection d'objets"), une définition formelle est nécessaire pour raisonner rigoureusement. La pierre angulaire de la théorie des ensembles est le principe suivant : un ensemble est entièrement défini par ses éléments.

Pour commencer, familiarisons-nous avec le vocabulaire de base et les notations. La vidéo suivante, destinée aux classes préparatoires, offre un excellent panorama.

Maintenant, formalisons ces concepts avec la rigueur attendue. Le document ci-dessous, issu d'un cours universitaire, nous servira de référence.

Synthétisons ces points fondamentaux. Soient A et B deux ensembles.

• Inclusion : $A\subseteq B$ est défini par $\forall x(x\in A\Rightarrow x\in B)$.
  • Pour prouver que $A$ est inclus dans $B$, on prend un élément $x$ arbitraire dans $A$ et on démontre qu'il doit aussi appartenir à $B$.
• Égalité : $A=B$ est défini par $(A\subseteq B)\wedge (B\subseteq A)$.
  • C'est le principe de double inclusion. Pour prouver l'égalité de deux ensembles, on doit effectuer deux démonstrations d'inclusion.

2. Opérations sur les ensembles : la logique en action

Les opérations ensemblistes comme l'union ou l'intersection ne sont pas de nouvelles règles à mémoriser, mais des conséquences directes des connecteurs logiques que vous connaissez déjà.

La vidéo suivante introduit ces opérations et les lois associées (distributivité, lois de De Morgan).

Le lien entre opérations ensemblistes et connecteurs logiques est la clé de cette leçon. En utilisant la définition en compréhension, ce lien devient explicite :

• Union (OU logique) : $x\in A\cup B⟺(x\in A)\vee (x\in B)$
• Intersection (ET logique) : $x\in A\cap B⟺(x\in A)\wedge (x\in B)$
• Complémentaire (NON logique) : $x\in A^c⟺\neg (x\in A)$ (où $A^c$ est le complémentaire de A dans un ensemble de référence E)

Le document LINK, dans sa Proposition 1.35, formalise exactement ce point. Grâce à cette correspondance, les lois de la théorie des ensembles sont directement héritées des lois de la logique propositionnelle.

3. La preuve formelle par manipulation d'éléments

Nous arrivons au cœur de notre objectif : démontrer une identité ensembliste. La méthode consiste à se ramener à une preuve logique en manipulant les éléments. C'est ce qu'on appelle parfois la méthode "element-chasing" (ou "chasse à l'élément").

Le guide de l'université de Stanford ci-dessous est une ressource exceptionnelle qui détaille la structure de ces preuves.

Exemple : Démontrons la loi de distributivité $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

Selon le principe de double inclusion, nous devons prouver deux choses :

1. $A\cap (B\cup C)\subseteq (A\cap B)\cup (A\cap C)$
2. $(A\cap B)\cup (A\cap C)\subseteq A\cap (B\cup C)$

Démonstration de (1) :
Soit $x$ un élément arbitraire de $A\cap (B\cup C)$.
Par définition de l'intersection, cela signifie :
$(x\in A)\wedge (x\in B\cup C)$
Par définition de l'union, on peut développer le second terme :
$(x\in A)\wedge ((x\in B)\vee (x\in C))$
Par la distributivité du $\wedge$ sur le $\vee$ en logique propositionnelle, ceci est équivalent à :
$((x\in A)\wedge (x\in B))\vee ((x\in A)\wedge (x\in C))$
En réappliquant les définitions des opérations ensemblistes :
$(x\in A\cap B)\vee (x\in A\cap C)$
Et finalement, par définition de l'union :
$x\in (A\cap B)\cup (A\cap C)$
Puisque notre choix de $x$ était arbitraire, nous avons montré que tout élément du premier ensemble est aussi dans le second, ce qui prouve l'inclusion.

Démonstration de (2) :
La démonstration de l'inclusion inverse suit exactement le même chemin en sens inverse. Comme toutes nos étapes étaient des équivalences logiques ($⟺$), on peut simplement remonter le fil du raisonnement.

La vidéo suivante montre une démonstration complète d'une loi de De Morgan en utilisant cette méthode de double inclusion. C'est un exemple classique et fondamental.

4. Application en informatique : les ensembles en Python

Pour lier cette théorie à la pratique, il est utile de voir comment ces concepts se matérialisent dans un langage de programmation. Votre maîtrise de Python vous permettra de faire ce lien immédiatement. Python propose un type de données set qui implémente directement la notion mathématique d'ensemble.

Cette implémentation concrète renforce l'idée que la théorie des ensembles n'est pas une abstraction pure, mais un outil fondamental pour la modélisation et la résolution de problèmes en informatique.

Conclusion

Dans cette leçon, nous avons établi un pont solide entre la logique formelle et la théorie des ensembles. Vous êtes désormais équipé pour aborder les ensembles avec la rigueur d'un mathématicien.

Points clés à retenir :

• Un ensemble est formellement défini par ses éléments (principe d'extensionalité).
• Les définitions d'inclusion, d'égalité et des opérations ensemblistes ($\cup ,\cap ,\dots$) reposent sur la logique des prédicats.
• Chaque opération ensembliste correspond à un connecteur logique ($\cup \leftrightarrow \vee$, $\cap \leftrightarrow \wedge$, ${}^c\leftrightarrow \neg$).
• La méthode de référence pour prouver l'égalité de deux ensembles est la démonstration par double inclusion, qui se ramène à une manipulation de propositions logiques au niveau des éléments.

Dans notre prochaine leçon, nous enrichirons notre arsenal de techniques de démonstration en étudiant deux méthodes fondamentales : la preuve par l'absurde et la preuve par contraposée. Ces outils sont omniprésents en analyse d'algorithmes et en informatique théorique.