Introduction à la théorie des ensembles

Démonstrations

Une théorie ma­thé­ma­ti­que est un ensemble d'affirmations, les assertions ou propositions vraies. Une assertion peut être admise, auquel cas on parle d'axiome ou de postulat — c'est in­con­tour­na­ble, on ne peut pas créer une théorie ex nihilo — ou être obtenue à l'aide de règles de déductions logiques et d'autres assertions dont les axiomes. En complément de la logique pro­po­si­tion­nel­le, on enrichit le langage mathématique de symboles spécifiques à la théorie en précisant leur syntaxe et comment ils s'articulent avec la logique propositionnelle. Le langage de la logique des prédicats va permettre de construire de nouvelles propositions qui pourront êtres intégrées dans des formules de la logique des propositions. Ce langage n'entre donc pas en concurrence avec celui de la logique propositionnelle mais au contraire l'enrichit.

Cette vision formaliste ne doit pas faire perdre de vue que les ma­thé­ma­ti­ques seraient im­pra­ti­ca­bles ou pour le moins considérablement entravées si l'on s'in­ter­di­sait l'usage de la langue naturelle pour s'exprimer. Autrement dit, faire des mathématiques ne peut pas se résumer à la construction d'énoncés formels qui respectent une syntaxe stricte, à la manière d'un langage de programmation. Parler d'un entier naturel \(n\) pair n'est pas moins rigoureux que d'écrire \begin{equation} \label{eq:entierpair} (n\in\N) \wedge (\exists k\in \N\ n={\color{#FF8}2}k) \end{equation} Cette expression — si elle n'est pas compréhensible à ce stade, elle devrait l'être à la fin de ce chapitre —, est en revanche bien plus efficace s'il faut démontrer que le carré d'un entier pair est pair. En effet, si \(n\) est pair, on dispose d'après \((\ref{eq:entierpair})\) d'un entier naturel \(k\) tel que \(n=2k\). On démontre alors les trois implications successives grâce aux règles de calcul en arithmétique : \begin{align*} \boxed{n={\color{#FF8}2}k}\ &\then\ n^2=({\color{#FF8}2}k)^2\\ n^2=({\color{#FF8}2}k)^2\ &\then\ n^2=4k^2\\ n^2=4k^2\ &\then\ \boxed{n^2={\color{#FF8}2}(2k^2)}. \end{align*} Et la transitivité de l'implication nous donne \[(n={\color{#FF8}2}k)\ \then\ (n^2={\color{#FF8}2}(2k^2))\] ce qui nous fourni un entier naturel \(k':=2k^2\) tel que \(n^2=2k'\). La règle du modus ponens nous permet d'affirmer que si \(n\) est pair, alors \(n^2\) est pair.

Le langage mathématique est un outil extrêmement puissant pour exprimer des concepts et les manipuler en les objectivants, mais les mathématiques ne peuvent être réduites à un langage, pas plus que l'informatique d'ailleurs.

On rappelle la définition introduite au chapitre précédent :

Une nouvelle assertion obtenue par déduction est appelée théorème ou lemme si le résultat est une étape importante pour l'obtention d'un théorème, ou parfois pro­po­si­tion­*(*) au sens de cette définition et non pas d'une formule de la logique pro­po­si­tion­nel­le, ou encore corollaire lorsqu'il s'agit d'une con­sé­quen­ce directe d'un théorème. Stricto sensu, chaque résultat intermédiaire obtenu dans une démonstration constitue un théorème, mais nous ne mettons en évidence que ceux qui nous pa­rais­sent importants, les autres restent dans l'anonymat.

Le rôle premier d'une démonstration est de valider un résultat, elle agit un peu comme un processus de certification qui n'explique pas nécessairement le résultat en question. Ce processus de certification formel peut-être particulièrement abscons et il est souvent nécessaire de revisiter une preuve de façon informelle pour comprendre les raisons qui permettent d'établir un résultat. De la même manière, un algorithme s'adresse à un être humain et explicite comment obtenir un résultat, alors qu'un programme en as­semb­leur qui réalise cet algorithme n'est plus qu'une suc­ces­sion d'instructions qui sont difficilement compréhensibles par le lecteur et qui n'ont plus aucun rôle explicatif.

Exemple. Considérons les deux carrés à gauche et à droite ci-dessus de mêmes côtés \(A+B\). On construit chacun des deux rectangles jaunes de la figure à droite en couplant \(2\) triangles jaunes tête-bêche de la figure à gauche. On en déduit que les aires bleues à gauche et à droite sont égales et on obtient le théorème de Pythagore : le carré de l'hypothénuse d'un triangle rec­tang­le est égal à la somme des carrés des autres côtés \(H^2=A^2+B^2\). Cette dé­mons­tra­tion est informelle mais justifie de manière compréhensible le résultat. Une preuve formelle utiliserait, par exemple, quelques outils de la géométrie comme les vecteurs et le produit scalaire pour établir algébriquement le résultat.

Nous avons déjà vu trois méthodes communes qui sont utilisées pour faire une dé­mons­tra­tion, sans qu'elles soient ex­clu­si­ves*(*) Exemple ty­pi­que de l'ef­fort à fai­re pour le­ver les am­bi­guï­tés ou imp­ré­ci­sions de la lan­gue na­tu­rel­le. Sans cet­te pré­ci­sion, le lec­teur ne sait pas si ces trois mé­tho­des de dé­mons­tra­tion sont les seu­les pos­si­bles ou non. :

1. Par modus ponens. Si \(P\) et \(Q\) sont deux propositions telles que \(P\Rightarrow Q\) est vraie et que \(P\) est vraie, on en déduit que la proposition \(Q\) est vraie ;
2. Par modus tollens (contraposition). Si \(P\) et \(Q\) sont deux propositions telles que \(P\Rightarrow Q\) est vraie et que \(\neg Q\) est vraie, on en déduit que la proposition \(\neg P\) est vraie ;
3. Par l'absurde. Pour démontrer qu'une proposition \(P\) est vraie, on suppose que la proposition \(\neg P\) est vraie, i.e. \(\neg P\) est un nouvel axiome de la théorie, puis on cherche une proposition \(Q\) telle que la proposition \(Q\wedge \neg Q\) est vraie, prouvant ainsi que cette théorie est contradictoire d'après le tiers exclu ce qui invalide l'axiome.

Nous verrons au chapitre Combinatoire une autre méthode de démonstration appelée preuve par ré­cur­ren­ce.

La théorie ma­thé­ma­ti­que dans laquelle nous discourons, tout au moins dans ce cours, est la théorie des ensembles de Zermelo-Fraenkel (abrégée en théorie ZF). Elle est l'aboutissement de ques­tion­ne­ments philosophiques sur la nature du rai­son­ne­ment et de la construction des ensembles qui ont culminés à la charnière du xix-ème et du xx-ème siècle. Bien entendu, les mathématiciens n'ont pas attendu le xx-ème siècle et cette théorie pour faire des démonstrations. L'apparition de con­tra­dic­tions et de paradoxes, conséquence de manipulations sans contraintes des ensembles infinis, a mis en péril l'édifice mathématique et a nécessité d'en fixer les règles. Pour faire une métaphore routière, conduire sur les routes sans fixer quelques règles de circulation peut aboutir à des accidents.

Cette théorie identifie tous les objets manipulés à des ensembles, nombres, fonctions, relations, vecteurs, etc. Elle fournit un nombre limité d'axiomes et de règles pour justifier leur existence ou pour les construire. Elle n'est pas la théorie des ensembles, au sens défini singulier, bien que nous emploierons souvent cette expression, mais plutôt un codage particulier et cohérent des objets qui étaient déjà utilisés en ma­thé­ma­ti­ques. La plupart des axiomes expriment des propriétés qui semblent évidentes pour les ensembles tels que nous les concevons naïvement. Ils précisent dans quel cadre nous pouvons construire de nouveaux ensembles à partir de ceux que nous connaissons déjà.

L'objet de cette théorie n'est pas d'expliquer ce que sont les ensembles, mais d'établir des règles de cons­truc­tion afin d'éviter des paradoxes. Nous ne ferons qu'effleurer ces questions délicates dans ce cours de li­cen­ce, elles seront à nouveau abordées dans un cours de calculabilité de mas­ter d'in­for­ma­ti­que. Dans la suite nous ne présenterons que les axiomes que nous utilisons in­ten­si­ve­ment, ils il­lus­trent la démarche qui sous-tend cette théorie et dont la dimension systématique est très proche de la théorie des langages en informatique.

Ensembles

Plus prosaïquement, nous concevons un en­sem­ble comme une collection d'objets, comme un re­grou­pe­ment, à la manière d'un sac de billes. Cette vision informelle est non seulement légitime mais in­dis­pen­sa­ble pour élaborer nos rai­son­ne­ments, il est donc exclu de la sacrifier sur l'autel du formalisme, elle est suffisante pour la licence. C'est celle du mathématicien allemand Georg Cantor qui fut l'un des pionniers sur cette ques­tion :

Les deux mots clés dans cette définition sont les mots définis et discernables. Le premier signifie que l'on doit être en mesure de dire pour tout objet s'il est un élément ou non de l'ensemble \(X\). Le second signifie que l'on doit être en mesure de distinguer les éléments d'un ensemble. Ces deux conditions expriment le fait qu'un ensemble est totalement caractérisé par ses éléments.

Les conditions définis et discernables font émerger deux relations spécifiques à la théorie des en­semb­les, respectivement la relation d'appartenance notée \(\in\) et la relation d'égalité notée \(=\). La proposition \(x\) est un élément de \(X\) est codée par l'expression \(x\in X\) et la proposition \(x\) est égal à \(y\) est codée \(x=y\). On écrit généralement \(x\not\in X\) au lieu de \(\neg (x\in X)\) et \(x\not= y\) au lieu de \(\neg(x=y)\). Rien n'empêche un ensemble d'être lui-même l'élément d'un autre ensemble. Si \(x\) et \(y\) satisfont \(x=y\), cela entraîne qu'ils sont synonymes, on peut échanger leurs rôles dans n'importe quelle expression ma­thé­ma­ti­que sans rien changer à son interprétation.

D'autres symboles spécifiques à la théorie des ensembles sont utilisés, en particulier l'accolade ouv­ran­te \(\{\) et l'accolade fermante \(\}\). Quand le nombre d'éléments qui définissent un ensemble \(X\) est fini — nous verrons le sens précis de la finitude dans cette théorie plus tard —, on peut le représenter par la liste de ses éléments délimités par ces deux sym­boles respectivement. Par exemple

dont les éléments sont \(1\), \(f\), \(3\) et \(x\). Cette écriture est appelée écriture en extension de \(X\).

Comme un ensemble est entièrement déterminé par ses éléments, les répétitions éventuelles d'un même élément dans l'écriture en extension d'un ensemble sont redondantes, ainsi \[\{a,a,b,a,c\}=\{a,b,c\}.\] Un même identificateur, \(a\) dans notre exemple, ne peut pas décrire des objets différents d'un ensemble, alors que dans une interprétation physique des ensembles, on peut y ranger plusieurs exemplaires d'un même objet, comme trois stylos bic bleus par exemple, mais s'ils sont indistinguables, il ne sont pas pour autant égaux au sens mathématique. D'autre part, l'ordre dans lequel apparaissent les éléments d'un ensemble n'a aucune importance, par exemple : \[\{a,b,c\}=\{b,a,c\}=\{a,c,b\},\ \text{etc.}\]

Logique des prédicats

Prédicats et quantificateurs

Nous allons étudier la logique des prédicats, dite également logique du premier ordre, dans le cadre de la théorie des ensembles. La démarche est similaire à celle que nous avons présentée pour la logique propositionnelle, nous commençons par étudier sa syntaxe. Contrairement à la logique propositionnelle où les variables ne peuvent prendre leurs valeurs que dans l'ensemble \(\{\top,\bot\}\), les variables de la logique des prédicats peuvent prendre leurs valeurs dans des univers quelconques, en particulier dans des ensembles dans le cadre de la théorie ZF qui nous concerne ici.

Un prédicat à \(q\) variables \(x_1,x_2,\ldots,x_q\) est généralement noté de manière préfixe, c'est-à-dire \(P(x_1,x_2,\ldots,x_q)\) et on dit également que \(P\) est un prédicat \(q\)-aire. Stricto sensu, conformément à la définition ci-dessus, un prédicat contient au moins une variable, sinon il s'agit d'une proposition, mais il est commode de considérer qu'une variable propositionnelle est un prédicat d'arité \(0,\) ce qui va nous permettre d'encapsuler le langage du calcul propositionnel dans celui des prédicats.

La syntaxe des formules de la logique des prédicats hérite des règles du calcul propositionnel, mais on connecte cette fois des prédicats. Notons que si l'on se limite aux prédicats d'arité \(0\), les propositions, on retrouve le langage du calcul propositionnel. Dans le cadre de la théorie ZF on va pouvoir constituer de nouveaux prédicats en enrichissant le lexiqueavec des ensembles et des symboles spécifiques, pour commencer \(=\), \(\in\), \(\{\), et \(\}\).

On conserve la même terminologie que pour la logique pro­po­si­tion­nel­le quand on fixe la valeur d'une ou plusieurs variables d'un prédicat, il s'agit encore d'une interprétation. Notons que si une seule variable a été interprétée dans un prédicat à \(q\) variables, on dispose alors d'un prédicat à \(q-1\) variables.

La théorie des ensembles de Zermelo-Fraenkel, ou en condensé théorie zf, distingue deux types de prédicats :

1. Prédicat collectivisant : c'est un prédicat \(P(x)\) tel que les valeurs de \(x\) pour lesquelles la proposition \(P(x)\) est vraie constituent un ensemble (on peut les collecter) noté \begin{equation} \{x {\color{#FF8}\such} P(x)\}. \end{equation} le symbole \(\color{#FF8}\such\) se lit tel que.

2. Prédicat non-collectivisant : c'est un prédicat \(P(x)\) tel que les valeurs \(x\) pour lesquelles la proposition \(P(x)\) est vraie ne constituent pas un ensemble.

Les axiomes de la théorie des ensembles élaborée par Zermelo et Fraenkel ont pour objet de fournir une famille de prédicats col­lec­ti­vi­sants suf­fi­sam­ment riche pour pouvoir coder tous les objets dont les ma­thé­ma­ti­ciens ont besoin, mais en bridant la construction de nouveaux ensembles afin de ne pas créer de mons­tres gé­né­rant des paradoxes. A contrario, la théorie ne dit pas quels sont les prédicats qui ne sont pas collectivisants. Sont disqualifiés de fait tous ceux dont les en­sem­bles associés, s'ils existaient, permettraient d'en déduire une contradiction. Cantor ne faisait pas ce distinguo et son principe d'abstraction affirmait que tout prédicat définit un ensemble, ce que l'on traduirait dans le langage de la théorie ZF, en affirmant que tous les prédicats sont collectivisants. L'application de ce principe permet de construire des pa­ra­do­xes, le plus célèbre d'entre eux étant probablement le paradoxe de Russel *(*) Bertrand Russel était un phi­lo­so­phe et ma­thé­ma­ti­cien ang­lais et l'un des fon­da­teurs de la lo­gi­que con­tem­po­rai­ne. Il a dé­cou­vert ce pa­ra­do­xe en 1901. : considérons \(P(x)\) le prédicat

Supposons que \(P(x)\) soit collectivisant en \(x\). On dispose alors de l'ensemble

Montrons que \((X\in X)\then (X\not\in X)\). Par construction, les éléments \(x\) de l'ensemble \(X\) satisfont le prédicat \(x\not\in x\) et comme \(X\) est un élément de \(X\), lui aussi et donc \(X\not\in X\). Par conséquent la règle du modus ponens nous permet d'affirmer que si \(X\in X\) alors \(X\not\in X\) ce qui est contradictoire. Le principe de non contradiction nous oblige donc à réfuter l'hypothèse \(X\in X\), autrement dit à affirmer que \(X\not\in X\). Mais dans ce cas, l'ensemble \(X\) satisfait le prédicat \(P(x)\) et doit donc appartenir à l'ensemble \(X\) et on a de nouveau une contradiction. Voilà qui met en lumière la nécessité d'être très attentif à l'articulation entre des objets syntaxiques et l'interprétation que l'on en fait.

Deux nouveaux symboles permettent de construire des propositions à l'aide d'un prédicat \(P(x)\) et des règles syntaxiques suivantes :

1. Le quantificateur universel \(\forall\), qui se lit quel que soit ou pour tout, et s'utilise dans l'ex­pres­sion \begin{equation} \label{eq:universel0} \forall x\ P(x) \end{equation} qui code la proposition Pout tout \(x\), la proposition \(P(x)\) est vraie.
2. Le quan­ti­fi­ca­teur existentiel \(\exists\) qui se lit il existe, et s'utilise dans l'expression \begin{equation} \label{eq:existentiel0} \exists x\ P(x) \end{equation} qui code la proposition Il existe \(x\) tel que la proposition \(P(x)\) est vraie. Notons qu'un tel élément n'est pas nécessairement unique.

En pratique, la variable \(x\) est choisie dans un ensemble \(X\), on utilise alors très souvent les deux expressions suivantes : \begin{align} \label{eq:universel} \color{white}\forall x\in X\ &{\color{white} P(x)}\ \ \text{pour coder}\ \ \forall x\ \left(x\in X\then P(x)\right),\\ \label{eq:existentiel} \color{white}\exists x\in X\ &{\color{white} P(x)}\ \ \text{pour coder}\ \ \exists x\ \left(x\in X\wedge P(x)\right). \end{align}

Quand un quan­ti­fi­ca­teur précède une variable \(x\), on dit qu'elle est quantifiée ou qu'il s'agit d'une variable liée (sous-entendu à un quantificateur). Dans ce cas, on parle également de va­ria­ble muette ou anonyme au sens où elle peut être remplacée partout dans l'expression par n'im­por­te quelle autre sans en chan­ger le sens. On peut s'en convaincre en remplaçant \(x\) par \(y\) dans les deux expressions \((\ref{eq:universel})\) et \((\ref{eq:existentiel})\). Ces deux expressions sont donc bien des propositions et pas des prédicats. Quand une variable n'est pas quantifiée elle est dite libre. Quand toutes les variables d'une formule de la logique des prédicats sont quantifiées, la formule est dite close.

Pour démontrer une proposition du type \(\forall x\in X\ \ P(x)\), on se donne un élément \(x\) quelconque de l'en­sem­ble \(X\) et on montre que \(P(x)\) est vraie. Comme \(x\) est quelconque il symbolise n'importe quel élé­ment de \(X\), ainsi si la proposition \(P(x)\) est vraie, elle l'est aussi pour tout autre élément de \(X\). Pour démontrer une proposition du type \(\exists x\in X\ \ P(x)\), il faut exhiber un élément particulier \(x\) de l'en­sem­ble \(X\) tel que \(P(x)\) soit vraie, il peut d'ailleurs en exister plusieurs.

Il arrive souvent que l'on ait besoin d'exprimer l'existence d'un objet et que celui-ci est unique. On rajoute alors un point d'exclamation à la suite du quantificateur existentiel pour le signifier. La proposition \(\exists!\, x\in X\ P(x)\) est logiquement équivalente à la proposition \begin{equation} \underbrace{(\exists x\in X\ \ P(x))}_{\text{existence}}\;\wedge\;\underbrace{\Big(\forall x\in X\ \forall y\in X\ \ \big((P(x)\wedge P(y))\Rightarrow (x=y)\big)\Big)}_{\text{unicité}}. \end{equation} Le terme gauche de cette conjonction code l'existence de \(x\) et le terme droit son unicité en exprimant sous forme contraposée que deux éléments distincts \(x\) et \(y\) de l'ensemble \(X\) ne peu­vent simultanément satisfaire le prédicat : \((x\neq y)\then \neg(P(x)\wedge P(y))\).

La négation des deux expressions \((\ref{eq:universel0})\) et \((\ref{eq:existentiel0})\) est conforme à celle des énoncés cor­res­pon­dan­ts en langue naturelle : \begin{align*} \neg (\forall x\ P(x))&\equiv \exists x\ \neg P(x)\\ \neg (\exists x\ P(x))&\equiv \forall x\ \neg P(x) \end{align*} avec pour déclinaisons sur un ensemble \(X\) \begin{align} \label{eq:negA} \neg ({\color{orange}\forall x\in X\ P(x)})&\equiv {\color{green}\exists x\in X\ \neg P(x)}\\ \label{eq:negE} \neg ({\color{lightblue}\exists x\in X\ P(x)})&\equiv {\color{lightgreen}\forall x\in X\ \neg P(x)} \end{align}

Illustrons l'équivalence logique \((\ref{eq:negA})\) en langue naturelle en supposant que \(X\) désigne l'ensemble des étudiants qui suivent ce cours de mathématiques et \(P(x)\) le prédicat dont l'interprétation est \(P(x)\) est vrai si et seulement si l'étudiant \(x\) comprend le cours. La négation de la proposition

Ainsi, quand on veut démontrer qu'une pro­po­si­tion du type \(\color{orange}\forall x\in X\ \ P(X)\) est fausse, autrement dit que sa négation est vraie, il suffit d'exhiber un élément \(\color{green}x\in X\) tel que \(\color{green}\neg P(x)\), qu'on appelle un contre-exemple.

Passons à l'équivalence logique \((\ref{eq:negE})\). La négation de la proposition

Le langage ma­thé­ma­ti­que ne peut laisser la place qu'à une unique interprétation. Ces différents énoncés montrent au passage que la variable \(x\) est bien muette, nous ne l'avons jamais mentionnée pour exprimer \((\ref{eq:negA})\) ou \((\ref{eq:negE})\).

Axiomes

Nous allons à présent introduire la terminologie de base de la théorie des ensembles et définir pas-à-pas les opérations élémentaires sur les ensembles. On commence par l'inclusion.

On note \(X\not\subseteq Y\) plutôt que \(\neg(X\subseteq Y)\). Dans l'assertion \(X\) est une partie de \(Y\), il n'y a plus mention de la variable \(x\) de la proposition \((\ref{eq:inclusion})\), elle est donc bien muette. L'axiome d'extension dit que deux en­semb­les sont égaux si et seulement s'ils ont exactement les mêmes éléments :

C'est cet axiome que l'on applique quand on veut démontrer que deux ensembles \(X\) et \(Y\) sont égaux, on démontre la double inclusion. Cela consiste à se donner un élément quelconque \(x\in X\) et à démontrer qu'il appartient à l'ensemble \(Y\), puis à démontrer la réciproque.

Dans le cas où \(a=b\), la paire \(\{a,b\}\) est réduite à \(\{a\}\), on l'appelle singleton \(a\). L'axiome de la paire nous permet de considérer un ensemble avec deux objets et c'est grâce à cet axiome et à l'axiome de réunion plus loin, que l'on peut définir l'écriture en extension d'un ensemble.

L'axiome de sélection (ou axiome de compréhension ou encore axiome de séparation) est déjà bien connu du lecteur après le cours de mathématiques générales, il est utilisé en permanence. C'est la version affaiblie du principe d'abstraction de Cantor dans laquelle tout prédicat définit un ensemble du moment que les objets \(x\) sont sélectionnés dans un ensemble pré­exis­tant :

On peut donc collecter les éléments d'un ensemble \(X\) qui satisfont un prédicat \(P(x)\). Il est clair qu'il s'agit d'un sous-ensemble de \(X\) et que cet axiome ne permet donc pas de créer un ensemble trop gros si \(X\) a été construit conformément à la théorie. L'écriture \((\ref{eq:compr})\) d'un ensemble est dite écriture en comp­ré­hen­sion de l'ensemble.

A = [n for n in range(10) if n % 2 == 0]

L'axiome de la réunion permet de collecter tous les éléments des différents ensembles qui ap­par­tien­nent à un ensemble donné :

Quand l'ensemble \(X=\{A,B\}\) est une paire d'ensembles, sa réunion est notée \(A\cup B\). C'est grâce à l'axiome de la réunion et à l'axiome de la paire que l'on a pu construire l'ensemble \((\ref{eq:ens4})\), c'est la réunion des paires \(\{1,f\}\) et \(\{3,x\}\). La réunion de l'ensemble \(\{\{a\},\{a,b,d\},\{a,c\},\{b,d\}\}\) est l'en­sem­ble \(\{a,b,c,d\}\).

Exemples : \(X\setminus X=\varnothing\) et \(X\setminus\varnothing=X\) ou encore \(\{a,b\}\setminus\{a\}=\{b\}\).

Deux ensembles \(X\) et \(Y\) dont l'intersection \(X\cap Y=\varnothing\) est vide sont dits disjoints. En particulier l'ensemble vide est disjoint de tout ensemble \(X\). On note parfois la réunion de deux ensembles disjoints \(A\sqcup B\). L'intersection d'un ensemble d'ensembles à la manière de la réunion d'un ensemble sera définie au chapitre prochain. La différence symétrique entre deux en­sem­bles \(X\) et \(Y\) est l'ensemble \((X\cup Y)\setminus(X\cap Y)\), on le note \(X\;\Delta\;Y\).

Pour aider à la compréhension, on représente parfois les opérations ensemblistes à l'aide d'un dia­gram­me de Venn.*(*) John Venn était un ma­thé­ma­ti­cien ang­lais du début du 20-ème siècle Les ensembles sont représentés sous forme de cercles ou de patates qui se che­vau­chent. Vous pouvez visualiser le résultat des différentes opérations ensemblistes en les sur­vo­lant ci-dessous :

L'axiome des parties permet de considérer l'ensemble dont les éléments sont tous les sous-ensembles de \(X\). Nous verrons au chapitre Combinatoire qu'il est considérablement plus grand que \(X\).

L'ensemble vide est une partie de tout ensemble \(X\) puisque \(x\in\varnothing\then x\in X\) est une proposition vraie puisque \(x\in\varnothing\) est fausse. Un ensemble est bien sûr inclus dans lui-même, par conséquent l'ensemble des parties d'un ensemble \(X\) contient toujours la partie vide \(\varnothing\) et l'ensemble \(X\). Par exemple si \(X=\{a,b,c\}\), on a \[\P(X)=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},X\}.\] D'autre part, l'ensemble des par­ties de l'ensemble vide \(\P(\varnothing)=\{\varnothing\}\) qui n'est pas l'en­semb­le vide puisqu'il contient l'élément \(\varnothing\).

L'ordre dans lequel nous écrivons les éléments d'un ensemble en extension n'a pas d'importance, la paire \(\{x,y\}\) est donc égale à la paire \(\{y,x\}\). Comment définir un nouvel objet ma­thé­ma­ti­que similaire à une paire mais pour lequel l'ordre dans lequel on écrit les deux objets a une importance ? On admettra le résultat suivant.

Le premier (resp. deuxième) terme d'un couple \(c=(x,y)\) s'appelle la première projection (resp. deuxième projection) du couple \(c\), on la note \(\text{pr}_1(c)\) (resp. \(\text{pr}_2(c)\)).

Il est aisé de vérifier que deux couples sont égaux si et seulement si leurs projections respectives sont égales. (cf. exercice suivant), ce qui répond à notre besoin. On peut bien sûr imaginer d'autres constructions ensemblistes pour ce faire. Il faut être conscient qu'il ne s'agit ici que d'un simple codage et que maintenant que ce nouvel objet est dans notre arsenal, on peut oublier l'échaffaudage qui a permis sa construction.

Formalisation du Sudoku

Le calcul des prédicats permet de modéliser certains problèmes de manière bien plus simple que le calcul propositionnel. Considérons le problème du Sudoku. C'est un jeu solitaire qui consiste à comp­lé­ter une grille de \(9\times 9\) cases réparties en 9 régions carrées \(3\times 3\) par des nombres compris entre 1 et 9 en respectant certaines règles :

1. 1: chaque ligne doit contenir exactement chacun des 9 chiffres de 1 à 9;
2. 2: chaque colonne doit contenir exactement chacun des 9 chiffres de 1 à 9;
3. 3: chaque région doit contenir exactement chacun des 9 chiffres de 1 à 9.

La grille ci-dessous contient 26 indices, il faut compléter les autres cases.

La formalisation du problème du Sudoku se fait avec un langage adapté. Les constantes sont les 9 valeurs de l'ensemble \({\mathscr C}:=\{1,2,3,\ldots,9\}\) et on considère des prédicats \(S(l,c,n)\) à trois variables dans l'ensemble \(\def\CC{{\mathscr C}}\CC\) avec l'interprétation suivante : \(S(l,c,n)\) est vrai si et seulement si la case à la ligne \(l\) et à la colonne \(c\) contient la valeur \(n\). C'est bien plus économique que la logique propositionnelle avec laquelle il aurait fallu définir une variable propositionnelle pour chaque valeur possible dans chaque case, soit \(9\times 9\times 9=729\) va­riab­les.

On traduit le fait que chaque case contient exactement une valeur par les deux propositions sui­van­tes (la première pour exprimer au moins une valeur, la seconde pour au plus une valeur) :

La partie des règles R1 et R2 disant que chaque nombre apparaît une seule fois par ligne et par colonne s'exprime respectivement par les deux propositions suivantes :

Pour la partie de la règle R3 disant que chaque nombre apparaît au plus une fois par région, c'est un peu plus compliqué puisque les régions sont moins faciles à mettre en évidence. On peut régler ce problème de bien des manières. Par exemple en introduisant une fonction \(r:\CC^2\rightarrow\CC\) qui à chaque couple \((l,c)\) associe le numéro de la région où se trouve la case à la ligne \(l\) et à la colonne \(c\), en numérotant les régions de \(1\) à \(9\) dans l'ordre de lecture par exemple. On aurait alors \begin{align*} &\forall (l,l',c,c',n)\in\CC^5\quad S(l,c,n)\wedge S(l',c',n)\wedge r(l,c)=r(l',c')\then (l,c)=(l',c'). \end{align*}

Chacun des 26 indices se traduit par une instanciation \(S(l,c,n) = V\) pour la valeur \(n\) affectée à la ligne \(l\) et la colonne \(c\), par exemple ici \(S(2,3,8)=V\).

Travaux pratiques

L'objectif de ces travaux pratiques est de réaliser un script qui saisit une grille incomplète de Sudoku dans un fichier texte contenant les valeurs dans cette grille (les cases vierges sont codées par un point).

Pour lire le contenu d'un fichier, il faut tout d'abord créer un fichier logique en l'associant à un fichier physique pour une lecture (read). C'est la fonction open qui réalise cette opération. Le mode d'accès au fichier (ici en lecture) et le nom du fichier sont codés par des chaînes de caractères. On récupère ensuite très facilement le contenu du fichier en créant la liste des chaînes de caractères (chaque ligne du fichier), grâce à la fonction readlines puis on ferme le fichier avec close (en réalité, on indique au système que l'accès à ce fichier est à nouveau libre).

fichier = open("nom_du_fichier","r")
liste = fichier.readlines()
fichier.close()

En séance

Compléments hors séance