Ensembles et logique des prédicats
\(\def\Id{{\text{Id}}}\def\rel{\,{\mathscr R}\,}\def\rg{{\rightarrow}}\def\Rg{{\Rightarrow}}\def\iff{{\;\Leftrightarrow\;}}\def\N{{\mathbb N}}\def\Z{{\mathbb Z}}\def\Q{{\mathbb Q}}\def\R{{\mathbb R}}\def\then{{\;\Rightarrow\;}}\def\iff{{\;\Leftrightarrow\;}}\)

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. Les ma­thé­ma­ti­ques seraient im­pra­ti­ca­bles ou tout au moins considérablement ralenties si l'on s'in­ter­di­sait l'usage de la langue naturelle pour s'exprimer, mais le prix à payer pour cette liberté est d'être excessivement attentif à ce que l'on énonce.

Il est intéressant de noter que sur le terrain du langage, la ma­thé­ma­ti­que et l'informatique font en quelque sorte le chemin inverse. La nécessité de rigueur a contraint les mathématiciens à s'éloigner de la langue naturelle en développant un langage de plus en plus formel et contraint, alors que les informaticiens cherchent au contraire à développer des langages de programmation de plus en plus proches de la langue naturelle. Les langages de pro­gram­ma­tion sont en quelque sorte l'achèvement de ce qu'est censé être un langage ma­thé­ma­ti­que, tout au moins du point de vue lexical et syntaxique, les pro­gram­meurs en font la douloureuse expérience au quo­ti­dien, la moindre erreur est im­mé­dia­te­ment sanc­tion­née. Ceci explique éga­le­ment les nombreux points de convergence entre ces deux disciplines.
Une séquence de déductions logiques permettant d'établir de nouvelles as­ser­tions à partir d'as­ser­tions déjà acquises (initialement les axiomes), s'appelle une dé­mons­tra­tion ou preu­ve.

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 pro­po­si­tion­, 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.

Considérons les deux carrés de côté \(A+B\). On construit les deux rectangles jaunes dans la figure de droite en couplant \(2\) triangles jaunes tête-bêche dans 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 deux 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.

Nous avons déjà vu plus haut 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 une proposition \(P\) est vraie et que l'on a \(P\Rightarrow Q\), on en déduit que la proposition \(Q\) est vraie ;
  2. Par modus tollens (contraposition). Pour démontrer la proposition \(P\Rightarrow Q\), il peut être plus simple de démontrer la proposition \(\neg Q\Rightarrow\neg P\) ;
  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 exclus ce qui invalide l'axiome.

Nous verrons au chapitre Combinatoire une autre méthode de démonstration appelée preuve par récurrence.

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 Zermello-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 d'une trop grande liberté dans la construction des ensembles, a mis en péril l'édifice mathématique et a nécessité d'en fixer les règles.

Dans cette théorie absolument tous les objets manipulés sont identifiés à des ensembles. Nombres, fonctions, relations, vecteurs, etc. Cette théorie fournit un nombre limité d'axiomes et de règles de construction des ensembles, elle n'est pas la théorie des ensembles, 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.

On appelle en­sem­ble toute collection \(X\) d'objets définis et discernables. Un tel objet est appelé élément ou membre de \(X\) et on dit aussi que l'objet appartient à \(X\).

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 décider si deux objets quelconques d'un ensemble sont égaux ou distincts. Ces deux conditions expriment le fait qu'un ensemble est totalement déterminé par ses éléments.

Les conditions définis et discernables font émerger deux relations spécifiques à la théorie des en­semb­les, respectivement l'appartenance notée \(\in\) et l'égalité notée \(=\). La phrase \(x\) est un élément de \(X\) est codée \(x\in X\) et la phrase \(x\) est égal à \(y\) est codée \(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 à sa valeur logique. On écrit généralement \(x\not\in X\) pour \(\neg (x\in X)\) et \(x\not= y\) pour \(\neg(x=y)\).

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, on peut le représenter par la liste de ses éléments entourée par ces deux sym­boles respectivement. Par exemple

\begin{align} \label{eq:ens4} X=\{1,f,3,x\}. \end{align}

dont les éléments sont \(1\), \(f\), \(3\) et \(x\). Cette écriture est appelée écriture en extension de \(X\). Les deux symboles sont chargés de sens, faire l'accolade est sy­no­ny­me d'embrasser et ceci désigne l'action qui consiste à entourer quelque chose ou quelqu'un avec ses bras \(\{\;\}\).

Comme un ensemble est entièrement déterminé par ses éléments, les répétitions éventuelles du même élément dans l'écriture en extension d'un ensemble sont redondantes, ainsi \[\{a,a,b,a,c\}=\{a,b,c\}.\] 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.}\]

Nous utiliserons dans ce cours deux symboles pour re­pré­sen­ter l'égalité, le symbole \(=\) et le symbole \(:=\) en deux parties. Le \(:\) qui précède l'égalité dans ce dernier a pour objectif de signifier au lecteur qu'il s'agit d'une définition d'un nouvel objet et que l'égalité entre les deux opérandes gauche et droit du symbole provient de cette définition. Ainsi on écrira \(3=1+2\) qui est une assertion et plutôt \(X:=\{a,b,c\}\) pour signifier que nous notons \(X\) l'ensemble constitué des trois objets \(a\), \(b\) et \(c\). C'est une notation bien commode héritée des concepteurs de langages de programmation comme le Pascal, qui ont eu l'idée bien inspirée de distinguer l'égalité de l'affectation.

Prédicats

Prédicats et quantificateurs

Nous allons étudier la logique des prédicats ou logique du premier ordre dans le cadre du langage de la théorie des ensembles. On rajoute au lexique de la logique propositionnelle, les ensembles et les symboles spécifiques à la théorie des ensembles, à savoir \(=\), \(\in\), \(\{\), et \(\}\). 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 un ensemble quelconque.

Un prédicat est un énoncé contenant des variables tel qu'en substituant chaque variable par une valeur choisie dans un ensemble, on obtient une proposition.

Un prédicat à \(q\) variables \(x_1,x_2,\ldots,x_q\) est généralement noté de manière préfixe \(P(x_1,x_2,\ldots,x_n)\). 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 variable a été interprétée dans un prédicat à \(q\) variables, on dispose alors d'un prédicat à \(q-1\) variables. Par exemple \(x\geq \pi\) est un prédicat \(P(x)\) à une variable \(x\) de l'ensemble des nombres réels \(\R\) et \(P(4)\) est une pro­po­si­tion­ vraie. L'énoncé \(n=2k\) est un prédicat \(P(n,k)\) à deux variables \(n\) et \(k\) dans l'en­sem­ble des entiers naturels \(\N\) et \(P(4,2)\) est une proposition vraie.

La théorie des ensembles de Zermello-Fraenkel distingue deux types de prédicats :

  1. Prédicat collectivisant : c'est un prédicat \(P(x)\) tel que les objets \(a\) pour lesquels la proposition \(P(a)\) est vraie constituent un ensemble qui est alors noté

    \begin{equation} \{x\mid P(x)\}. \end{equation}
  2. Prédicat non-collectivisant : c'est un prédicat \(P(x)\) tel que les objets \(a\) pour lesquels la proposition \(P(a)\) est vraie ne constituent pas un ensemble.

Les axiomes de la théorie des ensembles élaborée par Zermello et Fraenkel ont pour objet de fournir une famille de prédicats col­lec­ti­vi­sants assez riche pour pouvoir coder les objets que les ma­thé­ma­ti­ciens manipulaient déjà 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 les prédicats dont les en­sem­bles associés, s'ils existaient, permettraient de construire une contradiction. Cantor ne faisait pas ce distingo et avait énoncé le principe d'abstraction affirmant que tout prédicat définissait un ensemble, autrement dit que tout prédicat était collectivisant. Ce principe trop généreux engendrait justement des pa­ra­do­xes. Le plus célèbre est probablement le paradoxe de Russel : considérons \(P(x)\) le prédicat

\begin{equation} x\not\in x. \end{equation}

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

\[X:=\{x\mid x\not\in x\}.\]

et d'après le tiers exclus, la proposition \(X\in X\) doit être vraie ou fausse. Or si \(X\in X\) est vraie, l'ensemble \(X\) doit satisfaire le prédicat \(x\not\in x\), c'est-à-dire \(X\not\in X\) ce qui est contradictoire. Ré­ci­pro­que­ment, si \(X\not\in X\), l'ensemble \(X\) satisfait le prédicat \(x\not\in x\), il appartient donc à l'ensemble \(X\) ce qui est encore contradictoire.

La théorie des ensembles avait pour principal objectif de s'assurer que ce nouveau langage ma­thé­ma­ti­que n'aboutirait jamais plus à des contradictions. Mal­heu­reu­se­ment le logicien autrichien Kurt Gödel a mis fin à cet espoir en démontrant en 1931 que dans toute théorie ma­thé­ma­ti­que suffisamment riche pour coder l'ari­thmé­ti­que, il existe des propositions in­dé­ci­da­bles, c'est-à-dire telles que l'on ne peut pas démontrer qu'elles sont vraies ni qu'elles sont fausses. D'autre part une théorie ma­thé­ma­ti­que ne permet pas de prouver sa propre cohérence, c'est-à-dire qu'elle ne permet pas de prouver qu'elle n'engendre pas des paradoxes. Les con­sé­quen­ces des travaux de Gödel ont un impact tout aussi dé­vas­ta­teur en in­for­ma­ti­que, c'est ce que vous étudierez dans un cours de calculabilité.

Deux nouveaux symboles permettent de construire des propositions à partir d'un ensemble \(X\) et d'un prédicat \(P(x)\). 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:universel} \forall x\in X\ \ P(x) \end{equation}

qui code la proposition Pout tout élément \(x\) de l'ensemble \(X\), la proposition \(P(x)\) est vraie. Le quan­ti­fi­ca­teur existentiel \(\exists\) qui se lit il existe, et s'utilise dans l'expression

\begin{equation} \label{eq:existentiel} \exists x\in X\ \ P(x) \end{equation}

qui code la proposition il existe un élément \(x\) de l'ensemble \(X\) tel que la proposition \(P(x)\) est vraie.

Quand un quan­ti­fi­ca­teur précède une variable \(x\), on dit qu'elle est quantifiée et on parle alors 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 lettre (qui ne joue pas déjà un rôle dans l'expression évidemment) 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.

Pour démontrer une proposition du type \(\forall x\in X\ \ P(x)\), on se donne un élément \(a\) quelconque de l'en­sem­ble \(X\) et on montre que \(P(a)\) est vraie. Comme \(a\) est quelconque il symbolise n'importe quel élé­ment de \(X\), ainsi si la proposition \(P(a)\) 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 \(a\) de l'en­sem­ble \(X\) tel que \(P(a)\) est vraie, il peut d'ailleurs en exister plus d'un.

La négation des deux expressions \((\ref{eq:universel})\) et \((\ref{eq:existentiel})\) est conforme à la négation des phrases cor­res­pon­dan­tes dans la langue naturelle. Soit \(X\) un ensemble et \(P(x)\) un prédicat de la variable \(x\) définie sur \(X\), alors \begin{align} \label{eq:negA}\neg(\forall x\in X\ \ P(x))&\ \equiv\ \exists x\in X\ \ \neg P(x)\\ \label{eq:negE}\neg(\exists x\in X\ \ P(x))&\ \equiv\ \forall x\in X\ \ \neg P(x) \end{align}

Illustrons l'équivalence logique \((\ref{eq:negA})\). La négation de la proposition tous les étudiants comprennent le cours est bien sûr il existe un étudiant qui ne comprend pas le cours plutôt que tous les étudiants ne comprennent pas le cours qui prête à interprétation, veut-on dire qu'aucun étudiant ne comprend le cours ou que certains étudiants ne comprennent par le cours ? Et l'ambiguïté des langues na­tu­rel­les ne s'arrête pas là, le mot un induit souvent l'unicité, il est donc préférable de dire il existe au moins un étudiant qui ne comprend pas le cours. Ainsi, quand on veut démontrer qu'une pro­po­si­tion \(\forall x\in X\ \ P(X)\) est fausse, autrement dit que sa négation est vraie, il suffit d'exhiber un élément \(a\) tel que \(\neg P(a)\), qu'on appelle un contre-exemple.

Passons à l'équivalence logique \((\ref{eq:negE})\). La négation de la proposition il existe un éléphant rose peut être la proposition il n'existe pas d'éléphants roses ou encore tous les éléphants ne sont pas roses, mais cette dernière laisse entendre que certains peuvent l'être mais pas tous ! Ma­thé­ma­ti­quement, on dirait quel que soit l'éléphant, celui-ci n'est pas rose ce qui s'exprime plus élégamment sous la forme aucun éléphant n'est rose.

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})\). La langue française est truffée de chausse-trappes, et il est très facile de faire un raisonnement fallacieux en lui donnant l'apparence de justesse — on parle de sophisme — ce que ne manquent jamais de faire les po­li­ti­ciens. Le langage ma­thé­ma­ti­que ne peut laisser la place qu'à une unique interprétation.

Les difficultés commencent quand on manipule des prédicats de plu­sieurs variables et que l'on quantifie tout ou partie de leurs variables. Par exemple, un prédicat \(P(x,y)\) dont la variable \(x\) a été quantifiée est un prédicat de la variable \(y\). Considérons le prédicat \(P(x,y)\) défini sur deux variables réelles \(x\) et \(y\) suivant : \[x^2-y= 1\] On peut définir le prédicat \(Q(x)\) de la variable \(x\) suivant \[\exists y\in\R\quad x^2-y= 1\] et la proposition \(\forall x\in\R\ Q(x)\), soit \[\forall x\in\R\ (\exists y\in\R\quad x^2-y = 1)\] que l'on écrit souvent en omettant les parenthèses : \begin{equation}\label{eq:AE} \forall x\in\R\ \exists y\in\R\quad x^2-y = 1. \end{equation} Cette proposition est vraie. En effet, quelle que soit la valeur du réel \(x\), le nombre réel \(y\) défini par \(y=x^2-1\) satisfait l'équation de la proposition \((\ref{eq:AE})\). Échangeons à présent les deux quantificateurs et étudions la signification de cette nouvelle proposition : \[\exists y\in\R\ \forall x\in\R\quad x^2-y = 1.\] Replaçons tout d'abord les parenthèses (ce n'est qu'une fois que ces écritures seront familières que l'on pourra se dispenser de cette étape) : \begin{equation}\label{eq:EA} \exists y\in\R\ (\forall x\in\R\quad x^2-y = 1). \end{equation} Cette nouvelle proposition est fausse. En effet, notons \(y_0\) un nombre réel \(y\) tel que tout nombre réel \(x\) satisfait l'égalité de la proposition \((\ref{eq:EA})\). Si tous les nombres réels \(x\) satisfont l'égalité \((\ref{eq:EA})\) pour \(y=y_0\), c'est le cas en particulier des nombres \(0\) et \(1\). On peut donc affirmer que \begin{align*} 0^2-y_0&=1^2-y_0 \end{align*} proposition équivalente à la proposition (prouvez le) : \begin{align*} 0=1 \end{align*} qui est fausse. Nous avons exhibé là un contre-exemple.

Il faut donc prendre garde à l'ordre des quantificateurs et en particulier replacer les parenthèses absentes si l'on doit propager une négation comme \((\ref{eq:negA})\) ou \((\ref{eq:negE})\) pour des prédicats à plusieurs variables.

La continuité simple d'une fonction \(f:\R\rightarrow\R\) s'écrit \[\forall x\in X\quad\forall\varepsilon>0\quad\exists\delta>0\quad\forall y\in X\quad |x-y|<\delta\Rightarrow |f(x)-f(y)|<\varepsilon.\] Alors que la continuité uniforme s'écrit \[\forall\varepsilon>0\quad\exists\delta>0\quad\forall x\in X\quad\forall y\in X\quad |x-y|<\delta\Rightarrow |f(x)-f(y)|<\varepsilon.\] Écrivez la négation de ces deux propositions.
Soit \(X\) un ensemble et \(P(x)\) et \(Q(x)\) deux prédicats. Écrivez la négation des deux propositions suivantes : \begin{align*} \forall x\in X&\quad P(x)\Rightarrow Q(x),\\ \exists x\in X&\quad P(x)\Rightarrow Q(x). \end{align*}

Axiomes

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

Soit \(X\) et \(Y\) deux ensembles. On dit que \(X\) est inclus dans \(Y\) ou que \(X\) est une partie de \(Y\) ce que l'on note \(X\subseteq Y\) ou \(Y\supseteq X\) si et seulement si \begin{equation} \label{eq:inclusion} \forall x\in X\quad x\in Y. \end{equation} On dit également que \(Y\) contient \(X\) ou que \(X\) est un sous-ensemble de \(Y\).

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 :

Soit \(X\) et \(Y\) deux ensembles, alors \(X=Y\) si et seulement si \begin{equation} \label{eq:egaliteensembles} (X\subseteq Y)\wedge (Y\subseteq X). \end{equation}

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.

Soit \(a\) et \(b\) deux objets. Le prédicat \((x=a)\vee(x=b)\) est col­lec­ti­vi­sant en \(x\). L'ensemble des éléments qui le satisfont est noté \(\{a,b\}\), \[\{a,b\}=\{x\mid (x=a)\vee(x=b)\}.\] Il est appelé paire \(\{a,b\}\).

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 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 collectés dans un ensemble pré­exis­tant :

Soit \(X\) un ensemble et \(P(x)\) un prédicat. Le prédicat \((x\in X)\wedge P(x)\) est collectivisant en \(x\). L'ensemble des éléments \(x\) de \(X\) tels que \(P(x)\) est vrai est noté \begin{equation} \label{eq:compr} \{x\in X\mid P(x)\}. \end{equation}

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 pas 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.

Une fois étudiées les fonctions \(f:X\to Y\) au chapitre Re­la­tions, app­li­ca­tions, on écrira \[\{f(x)\mid x\in X\}\] pour l'ensemble \[\{y\in Y\mid \exists x\in X\ y=f(x)\}.\] Ainsi l'ensemble \(\{3n\mid n\in \N\}\) décrit l'ensemble des entiers naturels multiples de \(3\). Certains langages de programmation autorisent une écriture similaire à l'écriture en compréhension pour construire de nouveaux objets. Par exemple en Python la liste \(A\) ci-dessous est définie en compréhension :
A = [n for n in range(10) if n % 2 == 0]
En notant \(X=\{0,1,2,3,4,5,6,7,8,9\}\) et \(P(n)\) le prédicat \(\exists k\in\N\ n=2k\), la cons­truc­tion de la liste \(A\) des nombres entiers de \(X\) qui sont pairs correspond à celle de l'en­sem­ble \(A=\{x\in X\mid \exists n\in\N\ x=2n\}.\)

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é.

Soit \(Y\) un ensemble. Le prédicat \(\exists X\ \ ((X\in Y)\wedge(x\in X))\) est col­lec­ti­vi­sant en \(x\). Il existe donc un ensemble noté \begin{equation}\label{eq:union} \displaystyle\bigcup_{X\in Y}X \end{equation} qui contient tous les éléments appartenant aux éléments de \(Y\). Il est appelé réunion de \(Y\).

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\},\varnothing\}\) est l'en­sem­ble \(\{a,b,c,d\}\). Plus généralement, l'écriture en extension est obtenue grâce à cet axiome.

Soit \(X\) un ensemble. L'ensemble \(\{x\in X\mid x\not= x\}\) existe et ne dé­pend pas de \(X\). On l'appelle l'en­sem­ble vide et on le note \(\varnothing\).
À un ensemble \(X\) on associe l'ensemble \(\varnothing_X:=\{x\in X\mid x\not=x\}\) qui formalise l'idée naïve qu'il ne contient aucun élément (aucun élément de l'ensemble \(X\) ne satisfait le prédicat \(x\not=x\)). Nous allons montrer que cet ensemble ne dépend pas de \(X\). D'après l'axiome de la paire, on peut définir la paire \(\{X,Y\}\) puis l'ensemble \(U=X\cup Y\) d'après l'axiome de réunion. Soit \(P(x)\) le prédicat \(\neg (x=x)\). L'axiome de sélection permet de construire les deux ensembles \(\{x\in X\mid P(x)\}\) et \(\{x\in Y\mid P(x)\}\). La proposition \[\forall x\in U\quad x\in X \Rightarrow x\in Y\] est vraie puisque \(x\in X\) est fausse, on a donc montré que \(X\subseteq Y\) et il suffit d'échanger le rôle de \(X\) et \(Y\) pour obtenir \(Y\subseteq X\). Nous venons donc de démontrer que ces deux ensembles sont égaux (cf. \((\ref{eq:egaliteensembles})\)).
Soit \(X\) et \(Y\) deux ensembles. La différence entre les ensembles \(X\) et \(Y\) est l'ensemble \(\{x\in X\mid x\not\in Y\}\). On le note \(X\setminus Y\) ou encore \(\complement_XY\). Si de plus \(Y\subseteq X\), alors la différence \(X\setminus Y\) est appelée complémentaire de \(Y\) dans \(X\).

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

Soit \(X\) et \(Y\) deux ensembles. L'in­ter­sec­tion des ensembles \(X\) et \(Y\) est l'ensemble \(\{x\in X\mid x\in Y\}\). On le note \(X\cap Y\).

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\). 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 bri­tan­ni­que 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 :

 Y
 
Diagramme de Venn et opérations ensemblistes sur deux ensembles \(X\) et \(Y\). Ensemble : aucune.

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\).

Soit \(X\) un ensemble. Le prédicat \(Y\subseteq X\) est collectivisant en \(Y\). Il existe donc un ensemble noté \(\def\P={\mathscr P}\P(X)\) tel que \begin{equation} \P(X)=\{Y \mid Y\subseteq X\} \end{equation} Cet ensemble est appelé ensemble des parties de \(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'ensemble vide puisqu'il contient l'élément \(\varnothing\).

Comme pour n'importe quel ensemble, la paire \(\{x,y\}\) est égale à la paire \(\{y,x\}\), l'ordre dans lequel nous écrivons les éléments d'un ensemble n'a pas d'importance. On souhaite 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 théorème suivant.

Soit \(x\) et \(y\) deux objets. La paire \(\{\{x\},\{x,y\}\}\) est appelé couple \(x\), \(y\) et on le note \((x,y)\). Soit \(X\) et \(Y\) deux ensembles. L'en­sem­ble des couples \((x,y)\) tels que \(x\in X\) et \(y\in Y\) existe, on le note \(X\times Y\) et on l'appelle produit car­té­sien de \(X\) et \(Y\).

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)\)).

Un ensemble \(G\) de couples est appelé graphe. On définit respectivement la première et la deuxième projection d'un graphe \(G\) : \begin{align*} \text{pr}_1(G)&:=\{\text{pr}_1(c)\mid c\in G\}=\{x\mid \exists (x,y)\in G\}\\ \text{pr}_2(G)&:=\{\text{pr}_2(c)\mid c\in G\}=\{y\mid \exists (x,y)\in G\}. \end{align*}
On généralise cette construction pour construire des \(n\)-uplets avec \(n\in\N\).

Démontrez que \((x,y)=(x',y')\Rightarrow (x=x')\wedge(y=y').\)
À partir de l'ensemble vide \(\varnothing\), on peut construire inductivement les ensembles ci-dessous en définissant chaque nouvel ensemble à l'aide du précédent \(X\) par la réunion \(X\cup\{X\}\) : \begin{equation} \begin{matrix} \varnothing & {\color{yellow}\{\varnothing\}} &{\color{orange}\{\varnothing,{\color{yellow}\{\varnothing\}}\}} &\{\varnothing,\{\varnothing\},{\color{orange}\{\varnothing,{\color{yellow}\{\varnothing\}}\}}\} &\cdots\\ \{\,\}& \{0\}&\{0,1\}&\{0,1,2\}&\cdots\\ 0 & 1 & 2 & 3 &\cdots \end{matrix} \end{equation}

On identifie l'ensemble vide à \(0\) et chaque nouvel ensemble ainsi construit au nombre entier suivant (c'est le cardinal de l'ensemble en question). On code ainsi les entiers naturels tels qu'on les connaissait avant la théorie des ensembles les uns après les autres. Cette construction (ou plutôt ce codage) des entiers naturels est due au mathématicien John Von Neumann. L'axiome de l'infini assure que l'en­sem­ble de tous ces ensembles existe, autrement dit que l'ensemble \(\N\) existe. Nous le re­trou­ve­rons au chapitre Combinatoire.

Un dernier axiome, et nous achèverons là cette introduction à la théorie des ensembles, l'axiome du choix. Cet axiome nous autorise à extraire un élément de son choix de chaque ensemble d'une famille d'ensembles pour en faire un ensemble. Cet axiome peut être intégré ou non dans la théorie, si c'est le cas elle est appelée théorie ZFC.

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. chaque ligne doit contenir exactement chacun des 9 chiffres de 1 à 9;
  2. chaque colonne doit contenir exactement chacun des 9 chiffres de 1 à 9;
  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.

74 3
38
5 6
3 4
94 1 2 3 5
6 9
5 8 7
5 3 9
4 5 8
Exemple de grille de Sudoku \(9\times 9\) à compléter

La formalisation du problème du Sudoku se fait avec un langage adapté. Les constantes sont les 9 entiers de l'ensemble \({\mathscr C}:=\{1,2,3,\ldots,9\}\) et les prédicats sont des prédicats à trois variables \(S(l,c,n)\) de l'ensemble \(\def\CC{{\mathscr C}}\CC\) auxquels on donne la signification 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=243\) variables.

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) :

\begin{align*} &\forall (l,c)\in\CC^2\ \exists n\in\CC\quad S(l,c,n),\\ &\forall (l,c,n,n')\in\CC^4\quad S(l,c,n)\wedge S(l,c,n')\then n=n'. \end{align*}

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

\begin{align*} &\forall (l,c,c',n)\in\CC^4\quad S(l,c,n)\wedge S(l,c',n)\then c=c',\\ &\forall (l,l',c,n)\in\CC^4\quad S(l,c,n)\wedge S(l,c,n)\then l=l'. \end{align*}

Pour la partie de la règle (3) 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(i,j)=r(i',j')\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\).

La théorie de la démonstration et l'intelligence ar­ti­fi­ciel­le développent des techniques pour répondre à des problèmes de cette nature en formalisant le langage du raisonnement. Le langage Prolog dont la première version est parue en 1972 (et qui est toujours disponible), a été l'un des précurseurs sur la résolution de problèmes logiques en logique des prédicats.
On cherche à placer \(8\) reines sur un échiquier sans qu'elles ne se mettent en échec. En vous inspirant de la formalisation du Sudoku, formalisez le problème des huit reines à l'aide de la logique des prédicats.
Formalisez le problème des Tee-shirts avec la logique des prédicats.