Logique des prédicats, théorie des ensembles

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. Plus précisément, le langage de la logique des prédicats va nous permettre de construire de nouvelles propositions. Ce langage n'entre donc pas en concurrence avec celui de la logique propositionnelle mais 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 \(n\in\N\) et que \(n\) satisfait la proposition suivante \begin{equation} \label{eq:entierpair} \exists k\ \ (k\in\N) \wedge (n={\color{#FF8}2}k). \end{equation} Cette proposition — 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 que les trois implications suivantes sont vraies grâce aux propriétés des opérations 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}(\underbrace{2k^2}_K)). \] En supposant que \(n=2k\), on a donc pu construire l'entier \(K:=2k^2\) tel que \(n^2=2K\), prouvant ainsi d'après la règle du modus ponens que si \(n\) est pair, son carré l'est aussi.

Le langage mathématique est un outil extrêmement puissant pour exprimer des concepts et les manipuler en les objectivants, mais en aucun cas les mathématiques ne sauraient être réduites à un langage. Les langages naturels permettent d'écrire des chefs d'œuvre de la littérature, mais ne sont que des moyens d'exprimer la pensée.

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 chemin inverse. La nécessité d'un cadre rigoureux pour raisonner a contraint les mathématiciens à s'éloigner de la langue naturelle en développant un langage de plus en plus formel et astreignant, 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 idéalisé, ne serait-ce que 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.

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

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 une 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 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 proposition intermédiaire obtenue dans une démonstration constitue un théorème, mais nous ne mettons en évidence que celles qui nous pa­rais­sent importantes, les autres restent dans l'anonymat.

Le rôle premier d'une démonstration est de valider une proposition. Elle agit comme un processus de certification qui n'explique pas nécessairement pourquoi cette proposition est vraie, mais comment. En général, on débute par la compréhension du résultat, même parcellaire, puis on tente de le valider formellement, rarement l'inverse. Parfois, l'explication est transposable en preuve, en particulier quand il s'agit d'un processus constructif.

Ce processus formel de certification peut donc être particulièrement abscons. Il est donc essentiel, de trouver des arguments, même informels pour comprendre pourquoi une proposition est vraie. De la même manière, un algorithme s'adresse à un être humain et explicite comment obtenir un résultat, alors que le code exécutable qui le réalise n'est plus qu'une suc­ces­sion d'instructions parfaitement obscures, le lecteur peut s'en convaincre en lisant le code exécutable de n'importe quel programme compilé.

A B A B B A A B H H 2 A A B B A B A B A 2 B 2 H H
Version géométrique du théorème de Pythagore.

Les deux carrés à gauche et à droite ci-dessus ont des côtés de même longueur \(A+B.\) En recomposant les \(4\) triangles du carré gauche de manière à former deux rectangles de côtés de longueurs \(A\) et \(B\) dans le carré droit, on en déduit que les aires bleues à gauche et à droite sont égales ce qui nous permet d'obtenir le fameux 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 : \[{\color{#08F}H^2}={\color{#08F}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, les outils de la géométrie cartésienne comme les vecteurs et le produit scalaire pour établir le résultat de manière algébrique.

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 la nouvelle théorie et disqualifie cet 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 une axiomatisation de la théorie des ensembles développée par G. Cantor*Mathématicien allemand de la fin du 19ème siècle. à la fin du 19ème siècle, proposée par les mathématiciens allemands E. Zermelo et A. Fraenkel pour en éliminer les paradoxes. 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 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 de Georg Cantor :

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 que l'objet appartient à \(X\) ou encore que \(X\) contient cet objet.

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 — le sens précis de la finitude sera introduit 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 \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 \(\{\) et \(\}\) 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, ce que représentent explicitement ces symboles.

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.}\]

Nous utiliserons deux symboles pour l'égalité, le symbole simple \(=\) et le symbole composé \(:=\) qui sont strictement synonymes du point de vue logique. Les deux points qui précèdent l'égalité ont un simple rôle sémantique et signifient que l'objet à gauche est défini par celui de droite, généralement une construction mathématique, l'égalité logique qui en découle est alors une conséquence de cette définition. Ainsi on distinguera l'assertion \(3=1+2\) de la définition \(X:=\{a,b,c\}\) qui signifie que \(X\) est l'ensemble constitué des trois objets \(a\), \(b\) et \(c\), faisant alors de \(X=\{a,b,c\}\) une nouvelle assertion. C'est une notation extrêmement commode héritée des concepteurs de langages de programmation comme le Pascal, qui ont eu l'idée inspirée de distinguer l'égalité de l'affectation.

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 est un énoncé contenant une ou plusieurs 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, 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 de celles des formules propositionnelles, mais on connecte cette fois des prédicats. Notons que si l'on se limite aux prédicats d'arité \(0\), autrement dit 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 lexique avec des ensembles et des symboles spécifiques, pour commencer \(=\), \(\in\), \(\{\), et \(\}\).

Exemples. L'expression \(x\in\{1,2\}\) est un prédicat d'une variable \(x.\) L'expression \(\neg(x\in y)\) est un prédicat à deux variables \(x\) et \(y.\) Ainsi l'expression \((x\in\{1,2\})\wedge(\neg(x\in y))\) est un nouveau prédicat à deux variables \(x\) et \(y.\) On peut, bien sûr, combiner des prédicats (au sens strict) et des propositions comme \((1=2)\then (x\in y)\) qui définit ici un prédicat à deux variables \(x\) et \(y\).

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.

Exemples. L'expression \(x\in\{1,2\}\) est un prédicat \(P(x)\) à une variable \(x\) et \(P(4)\) est une pro­po­si­tion­ qui est interprétée comme fausse. En anticipant sur l'étude de l'arithmétique, l'expression \(n\leqslant 2k\) est un prédicat \(P(n,k)\) à deux variables \(n\) et \(k\) entières, \(P(n,2)\) est le prédicat \(n\leqslant 4\) à une variable \(n\), et \(P(1,2)\) est une proposition interprétée comme vraie, alors que \(P(2,1)\) est une proposition interprétée comme fausse.

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{steelblue}\such} P(x)\}. \end{equation} le symbole \(\color{steelblue}\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. De manière imagée, les axiomes et le langage de cette théorie s'apparentent à un jeu de construction dont les pièces détachées et les règles d'assemblage permettent de construire de nouveaux objets dont on peut étudier les propriétés. Pour valider cette boite de jeu, il fallait être capable de reconstruire*plus précisément coder au sens informatique du terme les objets utilisés depuis des lustres par les mathématiciens et montrer que le prix à payer pour cette restriction de mouvement constituait un gage de sécurité.

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 affirme que tout prédicat définit un ensemble, ce que l'on traduirait dans le langage de la théorie ZF, par 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

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

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

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

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.

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 qu'il n'existe aucune preuve qu'elles sont vraies ni qu'elles sont fausses dans cette théorie*Ce qui ne signifie pas que ces mêmes propositions exprimées dans une autre théorie des ensembles le res­te­raient. (dans le cas contraire une proposition est dé­ci­da­ble). 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 cal­cu­la­bi­li­té.

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\ {\color{#08F}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\ {\color{#F80}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\) décrit des éléments d'un ensemble fixé \(X\), on utilise alors très souvent les deux expressions raccourcies suivantes : \begin{align} \label{eq:universel} \color{white}\forall x\in X\ \ &{\color{white} Q(x)}\ \ \equiv\ \ \forall x\ {\color{#08F}(x\in X)\then Q(x)},\\ \label{eq:existentiel} \color{white}\exists x\in X\ \ &{\color{white} Q(x)}\ \ \equiv\ \ \exists x\ {\color{#F80}(x\in X)\wedge Q(x)}. \end{align}

La première expression a été construite sur la base de l'expression \((\ref{eq:universel0})\) avec le prédicat \({\color{#08F}(x\in X)\then Q(x)}\), la seconde sur la base de l'expression \((\ref{eq:existentiel0})\) avec le prédicat \({\color{#F80}(x\in X)\wedge Q(x)}\).

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 se convaincre que les expressions \((\ref{eq:universel})\) et \((\ref{eq:existentiel})\) sont bien des propositions et pas des prédicats, il suffit de considérer la première comme la conjonction des propositions \(P(x)\) pour tous les \(x\) et la seconde comme la disjonction des propositions \(P(x)\) pour tous les \(x\).

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}

Soit \(X\) est un ensemble et \(P(x)\) un prédicat de la variable \(x\) définie sur \(X.\) Démontrez les équivalences logiques \((\ref{eq:negA})\) et \((\ref{eq:negE})\).
En partant de \((\ref{eq:universel})\), on a  : \begin{align*} \neg(\forall x\in X\ \ P(x))\ &\ \equiv\neg(\forall x\ \ (x\in X)\ \Rightarrow\ P(x))\\ &\ \equiv\neg(\forall x\ \ \neg(x\in X)\ \vee\ P(x))\\ &\ \equiv\exists x\ \ (x\in X)\ \wedge\ \neg P(x)\\ \text{et finalement}\quad \neg(\forall x\in X\ \ \ P(x))&\ \equiv\ \exists x\in X\ \ \neg P(x)\\ \end{align*} De la même manière, en partant de \((\ref{eq:existentiel})\) on obtient : \begin{align*} \neg(\exists x\in X\ \ P(x))\ &\ \equiv \neg(\exists x\ (x\in X)\wedge P(x))\\ &\ \equiv \forall x\ \neg((x\in X)\wedge P(x))\\ &\ \equiv \forall x\ \neg(x\in X)\vee \neg P(x)\\ &\ \equiv \forall x\ (x\in X)\Rightarrow \neg P(x)\\ \text{et finalement}\quad \neg(\exists x\in X\ \ P(x))\ &\ \equiv\ \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

tous les étudiants qui suivent ce cours le comprennent
est possiblement il existe un étudiant qui suit ce cours et ne le comprend pas plutôt que tous les étudiants qui suivent ce cours ne le comprennent pas qui peut prêter à interprétation, veut-on signifier qu'aucun étudiant ne comprend le cours ou que certains étudiants ne le comprennent pas ? 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 d'exprimer la négation par

il existe au moins un étudiant qui suit ce cours et ne le comprend pas

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

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.

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

La langue française est truffée de chausse-trappes, et il est très facile de faire un faux raisonnement en lui donnant l'apparence de justesse, on parle alors de sophisme (ce que ne manquent jamais de faire les po­li­ti­ciens) ou de paralogisme quand c'est involontaire.
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. 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.

On dit qu'une fonction \(f:\R\rightarrow\R\) est simplement continue en un point \({\color{#FF8}x}\in\R\) si la pro­po­si­tion sui­van­te est satisfaite : \begin{equation} \label{eq:continuitesimple} \forall\varepsilon>0\quad\exists\delta>0\quad\forall y\in \R\quad |{\color{#FF8}x}-y|<\delta\Rightarrow |f({\color{#FF8}x})-f(y)|<\varepsilon. \end{equation} Si l'on comprend que \(|x-y|\) désigne la distance de \(x\) à \(y\), cette proposition exprime formellement l'idée que l'on peut toujours cantonner l'image de \(y\) dans un rayon arbitraire \(\epsilon\) autour de l'image de \(x\), en limitant les déplacements de \(y\) autour de \(x\) dans un rayon \(\delta\) qui existe et dépend du rayon \(\epsilon\) qu'on s'était fixé.

Dessinez le graphe de la fonction \(f\) définie par \(x\mapsto x^2-3\) et illustrez sur ce graphe la continuité ou non-continuité de cette fonction en \(x=2.\) Faites de même avec la fonction définie par \(x\mapsto 2x\) si \(x\leqslant 2\) et \(x\mapsto x\) si \(x > 2.\)

Quelle proposition doit satisfaire une fonction \(f:\R\rightarrow\R\) pour qu'elle soit simplement continue en tout point \(x\in\R\) ?

Une fonction \(f:\R\rightarrow\R\) est uniformément continue sur \(\R\) si elle satisfait la proposition :

\begin{equation} \label{eq:continuiteuniforme} \forall\varepsilon>0\quad\exists\delta>0\quad\forall x\in \R\quad\forall y\in \R\quad |x-y|<\delta\Rightarrow |f(x)-f(y)|<\varepsilon. \end{equation} Quelle différence remarquez-vous entre la proposition de continuité simple en tout réel et la proposition de continuité uniforme ?

Écrivez la négation des deux propositions (\ref{eq:continuitesimple}) et (\ref{eq:continuiteuniforme}).

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 ensembles et définir pas-à-pas les opérations élémentaires sur les ensembles. On commence par l'inclusion.

Certains axiomes peuvent paraître déroutants tant ce qu'ils affirment paraît évident. Leur rôle est précisément d'intégrer ces évidences, ou ces résultats qui nous semblent naturels dans la théorie. Cela sous-entend souvent que l'on ne peut pas établir ces résultats autrement.
Soit \(X\) et \(Y\) deux ensembles. On dit que \(X\) est inclus dans \(Y\) ou que \(X\) est une partie de \(Y\) ou encore que \(X\) est un sous-ensemble de \(Y\), ce que l'on note \(X\subseteq Y\) ou \(Y\supseteq X\) si et seulement si \begin{equation*} \forall x\quad x\in X\then x\in Y. \end{equation*}
Attention aux confusions possibles à cause des différences d'acception d'un mot en langue naturelle ou en mathématiques. En français, l'inclusion est synonyme d'appartenance, alors que l'inclusion \(\subseteq\) et l'appartenance \(\in\) ne signifient pas la même chose en théorie des ensembles.

On note \(X\not\subseteq Y\) plutôt que \(\neg(X\subseteq Y).\) Dans la proposition \(X\) est une partie de \(Y\), il n'y a plus mention de la variable \(x\) présente dans son homologue formalisée \(\forall x\ \ x\in X\then x\in Y\), elle est donc bien muette.

L'axiome d'extension exprime que deux en­semb­les sont égaux si et seulement s'ils ont exactement les mêmes éléments :

Soit \(X,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 parle souvent de 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.

Si l'on dispose de deux objets \(a\) et \(b\), l'axiome de la paire assure l'existence de l'ensemble constitué de ces deux objets.
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\such (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 la 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 restriction du principe d'abstraction de Cantor, tout prédicat \(P(x)\) définit un ensemble, à condition que les objets \(x\) qui vérifient \(P(x)\) soient sélectionné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\such P(x)\}. \end{equation}

On peut donc collecter les éléments d'un ensemble \(X\) qui satisfont un prédicat quelconque \(P(x).\) Il est clair qu'il s'agit d'un sous-ensemble de \(X.\) Ainsi, cet axiome est inoffensif, il ne permet donc pas de créer un ensemble trop gros. 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)\such x\in X\}\] pour l'ensemble \[\{y\in Y\such \exists x\in X\ y=f(x)\}.\] Ainsi l'ensemble \(\{7n\such n\in \N\}\) décrit l'ensemble des entiers naturels multiples de \(7.\) Certains langages de programmation autorisent une écriture similaire à l'écriture en compréhension pour construire de nouveaux objets. Par exemple en Python la liste \(L\) ci-dessous est définie en compréhension : 
L = [n for n in range(10) if n % 2 == 0]
En effet, si l'on considère \(P(n)\) le prédicat \(\exists k\in\N\ n=2k\), la cons­truc­tion de la liste \(L\) des nombres entiers dans l'intervalle \(\ab{0}{9}\) qui sont pairs est inspirée de la construction de l'en­sem­ble \[L:=\{n\in \ab{0}{9}\such \exists k\in\N\ n=2k\}\] grâce à l'axiome de sélection.

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 qui contient tous les éléments appartenant aux éléments de \(Y.\) On l'appelle réunion de \(Y\) et on le note \begin{equation}\label{eq:union} \displaystyle\bigcup_{X\in Y}X \end{equation}

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

Soit \(X\) un ensemble. L'ensemble \(\{x\in X\such 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\such 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\such P(x)\}\) et \(\{x\in Y\such 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. axiome d'extension).

Soit \(P(x)\) un prédicat quelconque. En se souvenant de (\ref{eq:universel}) et (\ref{eq:existentiel}), on comprend pourquoi la proposition \(\forall x\in\varnothing\ P(x)\) est une tautologie qui affirme que tout élément de l'ensemble vide satisfait le prédicat \(P(x)\) (on rappelle que \(\bot\then A\) est toujours vrai) et la proposition \(\exists x\in\varnothing\ P(x)\) est une antilogie qui affirme qu'aucun élément de l'ensemble vide ne satisfait le prédicat \(P(x)\).

Soit \(X\) et \(Y\) deux ensembles. La différence entre les ensembles \(X\) et \(Y\) est l'ensemble \(\{x\in X\such x\not\in Y\}\) noté \(X\setminus Y.\) Si de plus \(Y\subseteq X\), alors \(X\setminus Y\) est appelé complémentaire de \(Y\) dans \(X\).

On note parfois \(\complement_XY\) le complémentaire de \(Y\) dans \(X\) ou encore \(\overline{Y}\) si le contexte discursif établit clairement quel est l'ensemble de référence \(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\cup Y)\such (x\in X)\wedge (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.\) 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 :

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

L'axiome des parties* nettement moins inoffensif que l'axiome de sélection 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 \such 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'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.

Soit \(x\) et \(y\) deux objets. La paire \(\{\{x\},\{x,y\}\}\) est appelée couple \(x\), \(y\) noté \((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.\) Si \(c=(x,y)\), on définit \(\text{pr}_1(c):=x\) et \(\text{pr}_2(c):=y\) appelés première projection et deuxième projection de \(c\) respectivement.

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.

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)\such c\in G\}=\{x\such \exists (x,y)\in G\}\\ \text{pr}_2(G)&:=\{\text{pr}_2(c)\such c\in G\}=\{y\such \exists (x,y)\in G\}. \end{align*}

On peut facilement généraliser la notion de couple à la notion de \(n\)-uplet \((x_1,x_2,\ldots,x_n)\) en posant* Nous verrons au chapitre 3 la définition de l'écriture indicielle \(x_i\) parachutée par endroit depuis le début de ce cours. \begin{equation} (x_1,x_2,\ldots,x_n):=\{\{x_1\},\{x_1,x_2\},\ldots,\{x_1,x_2,\ldots,x_n\}\}. \end{equation} en utilisant inductivement l'axiome de la paire et l'axiome de la réunion puis en définissant le produit cartésien de \(n\) ensembles \(X_1, X_2,\ldots,X_n\) par \begin{equation} X_1\times X_2\times\cdots\times X_n:=\{(x_1,x_2,\ldots,x_n)\such \forall i\in\{1,\ldots,n\}\ x_i\in X_i\}. \end{equation} On définit alors la \(i\)-ème projection \(\text{pr}_i\) pour tout \(i\in\{1,\ldots,n\}\) et un ensemble \(G\) de \(n\)-uplets est qualifié de \(n\)-graphe.

Nous verrons qu'on peut définir les \(n\)-uplets de manière plus simple et plus générale à l'aide des familles d'éléments d'un ensemble, introduites au chapitre consacré aux relations. Il ne faut pas s'étonner que plusieurs constructions d'un objet mathématique puissent coexister. Ne pas perdre de vue que la théorie des ensembles est avant tout une proposition de codage cohérent des outils mathématiques. À l'instar d'un langage de programmation qui nous permet de coder des objets complexes à l'aide de combinaisons d'objets élémentaires parfois différentes, il est possible de coder des outils mathématiques de plusieurs façons.
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{#FF8}\{\varnothing\}} &{\color{orange}\{\varnothing,{\color{#FF8}\{\varnothing\}}\}} &\{\varnothing,\{\varnothing\},{\color{orange}\{\varnothing,{\color{#FF8}\{\varnothing\}}\}}\} &\cdots\\ \{\,\}& \{0\}&\{0,1\}&\{0,1,2\}&\cdots\\ 0 & 1 & 2 & 3 &\cdots \end{matrix} \end{equation}

Cette ingénieuse construction assure que chaque ensemble est contenu dans le suivant, mimant ainsi grâce à l'inclusion \(\subseteq\) ensembliste l'ordre naturel sur les entiers \(\leqslant.\) On identifie l'ensemble vide à \(0\) et chaque nouvel ensemble 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. Ce codage des entiers naturels en théorie des ensembles est dû 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 notre choix de chaque ensemble d'une famille d'ensembles pour en faire un ensemble, une sorte de menu à la carte. Cet axiome peut être intégré ou non dans la théorie des ensembles, si c'est le cas elle est appelée théorie zfc.

Soit \((X_i)_{i\in I}\) une famille d'ensembles. Il existe une fonction de choix \begin{equation*} f:I\;\rg\;\bigcup_{i\in I}X_i \end{equation*} telle que \(\forall i\in I\ f(i)\in X_i\).
Nous ne verrons la définition d'une application qu'au chapitre Relations, applications, mais l'étudiant a déjà été familiarisé avec cet outil ma­thé­ma­ti­que en cours d'analyse. Notons simplement que l'ensemble des applications d'un ensemble \(X\) dans un ensemble \(Y\) est noté* L'ensemble \(X\) est bien en exposant \(Y^X\).

Considérons l'énoncé suivant : \(f\) est une application constante de l'ensemble des réels dans lui-même. On peut l'exprimer plus formellement par l'application \(f\in\R^{\R}\) vérifie la proposition \begin{equation} \label{eq:marmite0} \forall (x_1,x_2)\in\R\times\R\ \ f(x_1)=f(x_2), \end{equation} que l'on condense parfois en \begin{equation*} f\in\R^\R:\quad \forall (x_1,x_2)\in\R\times\R\quad f(x_1)=f(x_2). \end{equation*}

On peut écrire une proposition équivalente à celle de l'énoncé \((\ref{eq:marmite0})\) : \begin{equation} \label{eq:marmite} {\color{#88F}\exists c\in\R}\ \ {\color{orange}\forall x\in\R}\quad f(x)=c. \end{equation} Attention la proposition \((\ref{eq:marmite})\) n'est pas logiquement équivalente à la proposition \begin{equation} \label{eq:marmite2} {\color{orange}\forall x\in\R}\ \ {\color{#88F}\exists c\in\R}\quad f(x)=c. \end{equation} La pro­po­si­tion \((\ref{eq:marmite2})\) exprime que tout nombre réel \(x\) admet une image \(c\) dans \(\R\) pour \(f\) qui dépend donc de \(x.\) Il s'agit là d'une tautologie, puisque cette proposition est satisfaite par toute application par définition.

La métaphore suivante devrait aider à le comprendre. Considérons l'expression fran­çai­se Toute marmite a son couvercle. En notant \(M\) l'ensemble des marmites, \(C\) l'ensemble des cou­ver­cles et \(P(m,c)\) le prédicat à deux variables dont l'interprétation est \(P(m,c)\) est vrai si et seulement si le couvercle \(m\) est adapté à la marmite \(m\), la proposition suivante a exactement la même tructure que celle de la proposition \((\ref{eq:marmite2})\) : \begin{equation*} {\color{orange}\forall m\in M}\ \ {\color{#88F}\exists c\in C}\quad P(m,c). \end{equation*} Il est évident que le couvercle \(c\) dépend de la mar­mi­te \(m\) considérée. En permutant les quantificateurs, la pro­po­si­tion \begin{equation*} {\color{#88F}\exists c\in C}\ \ {\color{orange}\forall m\in M}\quad P(m,c). \end{equation*} exprime qu'il existe un couvercle qui convient à toutes les marmites, ce qui n'est bien sûr pas la même chose.

Exprimez formellement les énoncés suivants ainsi que la négation des propositions qu'ils contiennent :
  1. \(f\) est l'application identité du plan réel dans lui-même.
  2. \(f\) est une application du plan réel dans lui-même qui admet un point fixe.
  3. \(f\) est une application de l'ensemble des réels dans lui-même et l'équation \(f(x)=0\) admet une unique solution.
  4. \(f\) et \(g\) sont des applications de l'ensemble des réels dans lui-même \(f\) n'est pas inférieure à \(g.\)
  5. \(f\) est une application paire de l'ensemble des réels dans lui-même.
  6. \(f\) est une application paire de l'ensemble des réels dans lui-même strictement décroissante.
  7. \((u_n)_{n\in\N}\) est une suite réelle bornée.
  8. \((u_n)_{n\in\N}\) est une suite réelle croissante.
  9. \((u_n)_{n\in\N}\) est une suite réelle constante à partir d'un certain rang.
  10. \((u_n)_{n\in\N}\) est une suite réelle périodique.
  11. \((u_n)_{n\in\N}\) est une suite réelle ultimement périodique.
Comme tous les énoncés en langue naturelle, il peut y avoir des ambiguïtés donnant lieu à des interprétations différentes, et par conséquent à différentes formalisations. Dans chacun des différents énoncés, il est implicite que l'on s'intéresse à un objet appartenant à un ensemble particulier et qui vérifie une certaine propriété.
Dans ce cas, pour le premier énoncé \(f\) est l'application identité du plan réel dans lui-même, on écrirait que \(f\in{(\R\times\R)}^{\R\times\R}\) et que cette application satisfait la proposition \[\forall(x,y)\in\R\times\R\ f((x,y))=(x,y)\] ce que l'on condense parfois en une expression (informelle) \begin{equation*} f\in{(\R\times\R)}^{\R\times\R}:\ \forall(x,y)\in\R\times\R\ f((x,y))=(x,y). \end{equation*} en séparant la donnée de l'énoncé de la propriété qu'elle satisfait.
On a donc avec les abus de langage usuels : \begin{align*} &(1) & f\in{(\R^2)}^{\R^2} :\quad & \forall (x,y)\in\R^2\ \ f(x,y)=(x,y)\\ &(2) & f\in{(\R^2)}^{\R^2} :\quad & \exists (x,y)\in\R^2\ \ f(x,y)=(x,y)\\ &(3) & f\in{\R}^{\R} :\quad & \exists! x\in\R\ \ f(x)=0\\ &(4) & (f,g)\in({\R}^{\R})^2 :\quad & \forall x\in\R\ \ f(x) > g(x)\\ &(5) & f\in{\R}^{\R} :\quad & \forall x\in\R\ \ f(x)=f(-x)\\ &(6) & f\in{\R}^{\R} :\quad & (\forall x\in\R\ \ f(x)=f(-x))\wedge (\forall (x,y)\in\R^2\ \ x \leqslant y \Rightarrow f(x)\leqslant f(y))\\ &(7) & (u_n)_{n\in\N}\in{\R}^{\N} :\quad & \exists B\in\R\ \forall x\in\R\ \ f(x)\leqslant B\\ &(8) & (u_n)_{n\in\N}\in{\R}^{\N} :\quad & \forall (n,m)\in\N^2\ \ n\leqslant m \Rightarrow u_n\leqslant u_m\\ &(9) & (u_n)_{n\in\N}\in{\R}^{\N} :\quad & \exists N\in\N\ \exists c\in\R\ \forall n\in\N\ \ n > N \Rightarrow u_n=c\\ &(10) & (u_n)_{n\in\N}\in{\R}^{\N} :\quad & \exists k\in\N\ \forall n\in\N\ \ u_{n+k}=u_n\\&(10) & (u_n)_{n\in\N}\in{\R}^{\N} :\quad & \exists k\in\N\ \forall n\in\N\ \ u_{n+k}=u_n\\ &(11) & (u_n)_{n\in\N}\in{\R}^{\N} :\quad & \exists k\in\N\ \exists N\in\N\ \forall n\in\N\ \ n\geqslant N\then u_{n+k}=u_n\\ \end{align*}
Comme nous l'avions déjà évoqué dans le chapitre précédent, la structure d'un texte mathématique est une simple alternance de définitions et de théorèmes. Ce cours n'y échappe pas, on a simplement inclus des commentaires au sein de cette litanie pour en saisir les tenants et les aboutissants. À ce stade, il est donc essentiel de comprendre la structuration archétypale d'une définition et d'un théorème.

Pour une définition d'un nouvel objet mathématique, on commence par établir la liste des objets (les ingrédients) qui entrent en jeu dans sa composition que l'on complète souvent par une proposition qui doit être satisfaite par cette construction.

Pour un théorème, on commence par la liste des objets invoqués dans une proposition appelée hypothèse, que ces objets sont supposés satisfaire, puis on fournit la conclusion qui est une nouvelle proposition que ces objets satisfont comme conséquence de l'hypothèse.

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 par exemple le jeu du Sudoku. Ce jeu solitaire consiste à comp­lé­ter les cases vierges d'une grille de \(9\) lignes par \(9\) colonnes avec des nombres compris entre 1 et 9 en respectant les règles suivantes :

  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 \(3 \times 3\) doit contenir exactement chacun des 9 chiffres de 1 à 9.

Les valeurs déjà présentes dans la grille, ont été choisies de manière à ce qu'il n'existe qu'une seule façon de compléter la grille, et le jeu consiste à les trouver. La grille ci-dessous est un exemple de grille à résoudre.

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 d'indice \(l\) et à la colonne d'indice \(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) :

\begin{align*} &{\color{#88F}\forall (l,c)}\in\CC^2\ {\color{orange}\exists n}\in\CC\quad S(l,c,n),\\ &{\color{#88F}\forall (l,c)}\in\CC^2\ {\color{#FF8}\forall(n,n')}\in\CC^2\quad S(l,c,n)\wedge S(l,c,n')\then {\color{#FF8}n=n'}. \end{align*}

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 :

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

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 24 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,5,2)=V\) ou encore \(S(3,7,5)=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.

Travaux pratiques

L'objectif de ces travaux pratiques est de réaliser un script qui lit une grille de Sudoku codée dans un fichier texte et tente de la compléter. Les indices dans la grille sont codés par les caractères 1 à 9 et les cases vides dont les valeurs sont à découvrir sont codées par le symbole point. Cliquez pour télécharger ce fichier exemple dans le répertoire où vous écrirez votre script.

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 nom du fichier et le mode d'accès à ce fichier (ici en lecture) 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 constituées par chacune des lignes du fichier, grâce à la méthode readlines(), puis on ferme le fichier avec la méthode 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()

Attention, le dernier caractère de chaque chaîne de caractères de la liste est le caractère invisible retour charriot puisqu'il est présent à la fin de chaque ligne d'un fichier texte. On peut s'en débarrasser à l'aide de la méthode rstrip(), qui élimine tous les caractères de type espacement en fin d'une chaîne : chaine.rstrip().

On découpe une chaîne de caractères chaine suivant un séparateur sep (une chaîne de caractère également, par défaut un espace) grâce à la méthode split(sep) (chaine.split(sep)) qui renvoie la liste des sous-chaînes séparées par la chaîne sep. Par exemple, l'exécution des instructions 

    chaine = "maths:en:folie"
    print(chaine.split(":"))
affichera la liste 
    ["maths","en","folie"]

Un ensemble s'écrit comme en mathématique, par exemple {a,b} est la paire constituée de a et de b. Malheureusement l'initialisation d'un ensemble \(X\) à l'ensemble vide qui devrait s'écrire naturellement X = {} n'est pas possible car c'est la syntaxe réservée à la création d'un dictionnaire vide, il faut plutôt écrire X = set(). On rajoute un élément x à un ensemble X à l'aide de l'instruction X.add(x) et on élimine un élément x d'un ensemble X à l'aide de l'instruction X.discard(x). Les opérations ensemblistes de réunion, d'intersection, de différence, de différence symétrique sont codées respectivement |, &, -, ^ en Python. Exemple : {a,c} | {a,b,d} est l'ensemble {a,b,c,d} et {a,c} & {a,b,d} est le singleton {a}.

En séance

Écrivez une fonction LireGrille(nomfichier) qui lit la grille dans le fichier dont le nom est passé en paramètre de cette fonction et qui renvoie une liste de 9 listes contenant chacune les 9 valeurs sur une ligne.
Écrivez une procédure AfficherGrille(grille) qui affiche la grille passée en paramètre sous forme de tableau en séparant les 9 régions* Le ? n'ap­pa­raît à la place d'un . que pour il­lus­trer la ques­tion 4 :
9 . . | . 7 . | 3 . . . 1 5 | . 2 . | . 4 6 . . 8 | 6 . . | 2 5 . ------+-------+------ 4 6 ? | 1 8 2 | . . . . 7 9 | . . . | 8 3 . . . . | 9 3 7 | . 6 2 ------+-------+------ . 3 7 | . . 1 | 5 . . 1 8 . | . 5 . | 6 9 . . . 4 | . 6 . | . . 3
Écrivez une fonction Inconnues(grille) qui renvoie le tuple des coordonnées des cases de la grille passée en paramètre qui ne sont pas des indices.
Écrivez les deux fonctions LibreL(ligne) et LibreC(colonne) qui renvoient respectivement l'ensemble des valeurs encore libres sur la ligne et la colonne. Pour la grille de l'exemple à la ligne 4 et la colonne 2 (on numérote à partir de 0) marquée par un point d'interrogation, ces deux fonctions renvoient respectivement les ensembles {3,5,7,9} et {1,2,3,6}.
Écrivez une fonction LibreR(ligne, colonne) qui renvoie l'ensemble des valeurs encore libres dans la région qui contient la case en (ligne,colonne). Pour la même case de coordonnées (3,2) de la question précédente, la fonction renvoie l'ensemble {1,2,3,5,8}. Indication : pour pouvoir parcourir toutes les cases de cette région, partez des coordonnées de celle dans son angle supérieur gauche obtenues à l'aide de divisions euclidiennes.
Écrivez la fonction Libre(ligne, colonne), qui renvoie l'ensemble des valeurs encore libres dans la case de coordonnées (ligne,colonne) à l'aide des trois fonctions précédentes. Pour la grille de l'exemple et la case de coordonnées (4,2), la fonction renvoie l'ensemble \[{\color{#FF8}\{3\}}=\{3,5,7,9\}\cap\{1,2,3,6\}\cap\{1,2,3,5,8\}.\]
Écrivez une fonction MAJ(grille), qui met à jour toutes les cases de coordonnées (ligne,colonne) pour lesquelles la fonction Libre a renvoyé un singleton— signifiant qu'une seule valeur y est possible — en remplaçant la valeur inconnue par celle contenue dans ce singleton. La fonction devra renvoyer un booléen indiquant s'il y a eu ou non une ou des valeurs dévoilées dans la grille.

Compléments hors séance

Écrivez une fonction Completer(grille), qui utilise les fonctions précédentes pour tenter de compléter la grille de Sudoku passée en paramètre et qui recommence tant que de nouvelles valeurs sont dévoilées. Testez votre script sur l'exemple ci-dessus ainsi que celui donné dans le cours.