Introduction à la théorie des ensembles
Démonstrations
Une théorie mathématique 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 incontournable, 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 propositionnelle, on enrichit le langage mathématique de symboles spécifiques à la théorie en précisant leur syntaxe et comment ils s'articulent avec la logique propositionnelle. Le langage de la logique des prédicats va permettre de construire de nouvelles propositions qui pourront êtres intégrées dans des formules de la logique des propositions. Ce langage n'entre donc pas en concurrence avec celui de la logique propositionnelle mais au contraire l'enrichit.
Cette vision formaliste ne doit pas faire perdre de vue que les mathématiques seraient impraticables ou pour le moins considérablement entravées si l'on s'interdisait l'usage de la langue naturelle pour s'exprimer. Autrement dit, faire des mathématiques ne peut pas se résumer à la construction d'énoncés formels qui respectent une syntaxe stricte, à la manière d'un langage de programmation. Parler d'un entier naturel \(n\) pair n'est pas moins rigoureux que d'écrire \begin{equation} \label{eq:entierpair} n\in\N\ \ \exists k\in \N\ \ n={\color{yellow}2}k. \end{equation} Cette dernière expression (si elle n'est pas compréhensible à ce stade, elle devrait l'être à la fin de ce chapitre) est en revanche bien plus efficace s'il faut démontrer que le carré d'un entier pair est pair puisque l'on déduit de \((\ref{eq:entierpair})\) que \[n={\color{yellow}2}k\ \then\ n^2=({\color{yellow}2}k)^2\ \then\ n^2=4k^2\ \then\ n^2={\color{yellow}2}(2k^2).\] Le langage mathématique est un outil extrêmement puissant pour exprimer des concepts et les manipuler en les objectivants, mais les mathématiques ne peuvent être réduites à un langage, pas plus que l'informatique d'ailleurs.
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 proposition*(*) au sens de cette définition et non pas d'une formule de la logique propositionnelle, ou encore corollaire lorsqu'il s'agit d'une conséquence 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 paraissent importants, les autres restent dans l'anonymat.
Considérons les deux carrés de côté \(A+B\). On construit chacun des deux rectangles jaunes de la figure à droite en couplant \(2\) triangles jaunes tête-bêche de la figure à gauche. On en déduit que les aires bleues à gauche et à droite sont égales et on obtient le théorème de Pythagore : le carré de l'hypothénuse d'un triangle rectangle est égal à la somme des carrés des autres côtés \(H^2=A^2+B^2\). Cette démonstration est informelle mais justifie de manière compréhensible le résultat.
Nous avons déjà vu trois méthodes communes qui sont utilisées pour faire une démonstration, sans qu'elles soient exclusives*(*) Exemple typique de l'effort à faire pour lever les ambiguïtés ou imprécisions de la langue naturelle. Sans cette précision, le lecteur ne sait pas si ces trois méthodes de démonstration sont les seules possibles ou non. :
Nous verrons au chapitre Combinatoire une autre méthode de démonstration appelée preuve par récurrence.
La théorie mathématique dans laquelle nous discourons, tout au moins dans ce cours, est la théorie des ensembles de Zermelo-Fraenkel (abrégée en théorie ZF). Elle est l'aboutissement de questionnements philosophiques sur la nature du raisonnement 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 contradictions 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. Pour faire une métaphore routière, conduire sur les routes sans fixer quelques règles de circulation peut aboutir à des accidents.
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, 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 mathématiques. 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 construction afin d'éviter des paradoxes. Nous ne ferons qu'effleurer ces questions délicates dans ce cours de licence, elles seront à nouveau abordées dans un cours de calculabilité de master d'informatique. Dans la suite nous ne présenterons que les axiomes que nous utilisons intensivement, ils illustrent 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 ensemble comme une collection d'objets, comme un regroupement, à la manière d'un sac de billes. Cette vision informelle est non seulement légitime mais indispensable pour élaborer nos raisonnements, 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 question :
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 deux éléments quelconques d'un ensemble. 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 ensembles, 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\). On écrit généralement \(x\not\in X\) pour \(\neg (x\in X)\) et \(x\not= y\) pour \(\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 mathématique sans rien changer à son interprétation.
D'autres symboles spécifiques à la théorie des ensembles sont utilisés, en particulier l'accolade ouvrante \(\{\) 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 délimités par ces deux symboles 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 synonyme 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 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.}\]
Prédicats
Prédicats et quantificateurs
Nous allons étudier la logique des prédicats, dite également 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 à \(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)\). On conserve la même terminologie que pour la logique propositionnelle 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. 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 proposition qui est interprétée comme vraie. L'énoncé \(n=2k\) est un prédicat \(P(n,k)\) à deux variables \(n\) et \(k\) dans l'ensemble des entiers naturels \(\N\) et \(P(4,2)\) est une proposition qui est interprétée comme vraie.
La théorie des ensembles de Zermelo-Fraenkel, ou en condensé théorie zf, distingue deux types de prédicats :
Les axiomes de la théorie des ensembles élaborée par Zermelo et Fraenkel ont pour objet de fournir une famille de prédicats collectivisants suffifsamment riche pour pouvoir coder tous les objets dont les mathématiciens ont besoin, mais en bridant la construction de nouveaux ensembles afin de ne pas créer de monstres générant des paradoxes. A contrario, la théorie ne dit pas quels sont les prédicats qui ne sont pas collectivisants. Sont disqualifiés de fait tous ceux dont les ensembles associés, s'ils existaient, permettraient de construire une contradiction. Cantor ne faisait pas ce distinguo et son principe d'abstraction affirmait que tout prédicat définit un ensemble, autrement dit en langage moderne, que tous les prédicats sont collectivisants. L'application de ce principe permet de construire des paradoxes, le plus célèbre d'entre eux étant probablement le paradoxe de Russel *(*) Bertrand Russel était un philosophe et mathématicien anglais et l'un des fondateurs de la logique contemporaine. Il a découvert ce paradoxe 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\}.\]D'après le tiers exclu, la proposition \(X\in X\) est 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éciproquement, 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.
Deux nouveaux symboles permettent de construire des propositions à l'aide d'un prédicat \(P(x)\) :
En pratique, la variable \(x\) est choisie dans un ensemble \(X\), on utilise alors très souvent les deux expressions suivantes : \begin{align} \label{eq:universel} \color{white}\forall x\in X\ &{\color{white} P(x)}\ \equiv\ \forall x\ \left(x\in X\then P(x)\right),\\ \label{eq:existentiel} \color{white}\exists x\in X\ &{\color{white} P(x)}\ \equiv\ \exists x\ \left(x\in X\wedge P(x)\right). \end{align}
Quand un quantificateur précède une variable \(x\), on dit qu'elle est quantifiée et on parle alors de variable muette ou anonyme au sens où elle peut être remplacée partout dans l'expression par n'importe quelle autre (qui ne joue pas déjà un autre rôle dans cette même expression évidemment) sans en changer 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 \(x\) quelconque de l'ensemble \(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'ensemble \(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 cet objet soit également 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} {\color{yellow}(\exists x\in X\ P(x))}\;\wedge\;{\color{#88F}(\forall x\in X\ \forall y\in X\ \ P(x)\wedge P(y)\Rightarrow x=y)}. \end{equation} Le terme gauche de cette conjonction code l'existence et le terme droit l'unicité en exprimant sous forme contraposée que deux éléments distincts \(x\) et \(y\) de l'ensemble \(X\) ne peuvent simultanément satisfaire le prédicat \(P(x)\) : \(x\neq y\then \neg(P(x)\wedge P(y))\).
La négation des deux expressions \((\ref{eq:universel})\) et \((\ref{eq:existentiel})\) est conforme à celle des énoncés correspondants en 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({\color{orange}\forall x\in X\ \ P(x)})&\ \equiv\ {\color{green}\exists x\in X\ \ \neg P(x)}\\ \label{eq:negE}\neg({\color{lightblue}\exists x\in X\ \ P(x)})&\ \equiv\ {\color{lightgreen}\forall x\in X\ \ \neg P(x)} \end{align}
Illustrons l'équivalence logique \((\ref{eq:negA})\) en langue naturelle en supposant que \(X\) désigne l'ensemble des étudiants qui suivent ce cours de mathématiques et \(P(x)\) le prédicat dont l'interprétation est \(P(x)\) est vrai si et seulement si l'étudiant \(x\) comprend le cours. La négation de la proposition tous les étudiants qui suivent ce cours le comprennent est bien sûr 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 naturelles 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 suit ce cours et ne le comprend pas. Ainsi, quand on veut démontrer qu'une proposition du type \(\forall x\in X\ \ P(X)\) est fausse, autrement dit que sa négation est vraie, il suffit d'exhiber un élément \(a\in X\) 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 ! Mathématiquement, 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 mathématique 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})\).
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.
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\leq 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}).
Axiomes
Nous allons à présent introduire la terminologie de base de la théorie des ensembles et définir pas-à-pas les opérations élémentaires sur les ensembles. On commence par l'inclusion.
On note \(X\not\subseteq Y\) plutôt que \(\neg(X\subseteq Y)\). Dans l'assertion \(X\) est une partie de \(Y\), il n'y a plus mention de la variable \(x\) de la proposition \((\ref{eq:inclusion})\), elle est donc bien muette. L'axiome d'extension dit que deux ensembles 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.
Si l'on dispose de deux objets \(a\) et \(b\), l'axiome de la paire permet de considérer l'ensemble constitué de ces deux objets.Dans le cas où \(a=b\), la paire \(\{a,b\}\) est réduite à \(\{a\}\), on l'appelle singleton \(a\). L'axiome de la paire nous permet de considérer un ensemble avec deux objets et c'est grâce à cet axiome et à l'axiome de réunion plus loin, que l'on peut définir l'écriture en extension d'un ensemble.
L'axiome de sélection (ou axiome de compréhension ou encore axiome de séparation) est déjà bien connu du lecteur après le cours de mathématiques générales, il est utilisé en permanence. C'est la version affaiblie du principe d'abstraction de Cantor dans laquelle tout prédicat définit un ensemble du moment que les objets \(x\) sont sélectionnés dans un ensemble pré­existant :
On peut donc collecter les éléments d'un ensemble \(X\) qui satisfont un prédicat \(P(x)\). Il est clair qu'il s'agit d'un sous-ensemble de \(X\) et que cet axiome ne permet donc pas de créer un ensemble trop gros si \(X\) a été construit conformément à la théorie. L'écriture \((\ref{eq:compr})\) d'un ensemble est dite écriture en compréhension de l'ensemble.
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 construction de la liste \(A\) des nombres entiers de \(X\) qui sont pairs correspond à celle de l'ensemble \(A=\{n\in X\such \exists k\in\N\ n=2k\}.\)
L'axiome de la réunion permet de collecter tous les éléments des différents ensembles qui appartiennent à un ensemble donné :
Quand l'ensemble \(X=\{A,B\}\) est une paire d'ensembles, sa réunion est notée \(A\cup B\). C'est grâce à l'axiome de la réunion et à l'axiome de la paire que l'on a pu construire l'ensemble \((\ref{eq:ens4})\), c'est la réunion des paires \(\{1,f\}\) et \(\{3,x\}\). La réunion de l'ensemble \(\{\{a\},\{a,b,d\},\{a,c\},\{b,d\}\}\) est l'ensemble \(\{a,b,c,d\}\).
Exemples : \(X\setminus X=\varnothing\) et \(X\setminus\varnothing=X\) ou encore \(\{a,b\}\setminus\{a\}=\{b\}\).
Deux ensembles \(X\) et \(Y\) dont l'intersection \(X\cap Y=\varnothing\) est vide sont dits disjoints. En particulier l'ensemble vide est disjoint de tout ensemble \(X\). On note parfois la réunion de deux ensembles disjoints \(A\sqcup B\). L'intersection d'un ensemble d'ensembles à la manière de la réunion d'un ensemble sera définie au chapitre prochain. La différence symétrique entre deux ensembles \(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 diagramme de Venn.*(*) John Venn était un mathématicien anglais du début du 20-ème siècle Les ensembles sont représentés sous forme de cercles ou de patates qui se chevauchent. Vous pouvez visualiser le résultat des différentes opérations ensemblistes en les survolant ci-dessous :
L'axiome des parties permet de considérer l'ensemble dont les éléments sont tous les sous-ensembles de \(X\). Nous verrons au chapitre Combinatoire qu'il est considérablement plus grand que \(X\).
L'ensemble vide est une partie de tout ensemble \(X\) puisque \(x\in\varnothing\then x\in X\) est une proposition vraie puisque \(x\in\varnothing\) est fausse. Un ensemble est bien sûr inclus dans lui-même, par conséquent l'ensemble des parties d'un ensemble \(X\) contient toujours la partie vide \(\varnothing\) et l'ensemble \(X\). Par exemple si \(X=\{a,b,c\}\), on a \[\P(X)=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},X\}.\] D'autre part, l'ensemble des parties 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 mathématique 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.
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)\)).
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 \(\leq\). 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. 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'ensemble de tous ces ensembles existe, autrement dit que l'ensemble \(\N\) existe. Nous le retrouverons 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.
On peut revenir à la proposition \((\ref{eq:marmite2})\) qui exprime que tout élément \(x\) de l'ensemble de départ admet une image \(c\) (qui dépend donc de \(x\)), condition satisfaite par toute application.
Une définition commence toujours de la même manière : on fait la liste des objets mathématiques (les ingrédients) qui entrent en jeu dans la description de l'objet et qui est défini grâce à une proposition qui doit être satisfaite par les objets qui le constituent.
Un théorème commence toujours par une liste des objets et une hypothèse, c'est-à-dire une proposition que ces objets satisfont, et une conclusion qui est une nouvelle proposition que ces objets satisfont.
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 à complé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 :
La grille ci-dessous contient 26 indices, il faut compléter les autres cases.
7 | 4 | 3 | ||||||
3 | 8 | |||||||
5 | 6 | |||||||
3 | 4 | |||||||
9 | 4 | 1 | 2 | 3 | 5 | |||
6 | 9 | |||||||
5 | 8 | 7 | ||||||
5 | 3 | 9 | ||||||
4 | 5 | 8 |
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=729\) variables.
On traduit le fait que chaque case contient exactement une valeur par les deux propositions suivantes (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\).