Logique et ensembles
Ce chapitre pose les bases du langage mathématique : propositions, prédicats, quantificateurs, ensembles et relations entre ces objets. La manière de traduire ces raisonnements en une rédaction claire et rigoureuse est développée dans l'annexe « La~rédaction mathématique », que nous étudierons en parallèle.
I) Rudiments de logique
A - Proposition et prédicat
- Une proposition (ou assertion) est une affirmation qui a une seule valeur de vérité : vrai ou faux.
- On dit que deux propositions sont équivalentes si elles ont la même valeur de vérité.
- Un prédicat est une affirmation dont la valeur de vérité dépend d'un ou plusieurs paramètres.
- « Pour tout $x \in \R$, $x^2 < -1$ » est une proposition fausse.
- « La fonction $x \mapsto x^2$ est croissante sur $\R_+$ » est une proposition vraie.
- « $x+y \geq 3$ » est un prédicat car ni $x$ ni $y$ ne sont fixés.
- « $x^2 \geq 0$ » est un prédicat car $x$ n'est pas fixé.
B - Négation, conjonction, disjonction
- Négation : La proposition « non $P$ » est $ \begin{cases} \text{vraie} & \text{si $P$ est fausse},\\ \text{fausse} & \text{si $P$ est vraie}. \end{cases} $
- Conjonction : La proposition « $P$ et $Q$ » est $ \begin{cases} \text{vraie} & \text{si $P$ et $Q$ sont vraies},\\ \text{fausse} & \text{sinon}. \end{cases} $
- Disjonction : La proposition « $P$ ou $Q$ » est $ \begin{cases} \text{vraie} & \text{si \underline{au moins une} des propositions $P$ et $Q$ est vraie},\\ \text{fausse} & \text{sinon}. \end{cases} $
Les conjonctions et disjonctions sont symétriques. Par exemple, « $P$ ou $Q$ » et « $Q$ ou $P$ » sont équivalentes.
- « $\pi$ n'est pas un entier et $\pi > 3$ » est vraie.
- « $\pi$ n'est pas un entier ou $\pi > 3$ » est vraie.
- « $\cos$ est continue et $\cos(0) = 0$ » est fausse.
- « $\cos$ est continue ou $\cos(0) = 0$ » est vraie.
En français, le « ou » est souvent exclusif comme dans la phrase « Voulez-vous une boisson ou un dessert ? » alors qu'en mathématiques le « ou » est inclusif, c'est-à-dire que les deux propositions peuvent être vraies.
Dressons les tables de vérité de la négation, de la conjonction et de la disjonction :
| $P$ | $\text{non } P$ |
| F | V |
| V | F |
| $P$ | $Q$ | $P \text{ et } Q$ | $P \text{ ou } Q$ |
| F | F | F | F |
| F | V | F | V |
| V | F | F | V |
| V | V | V | V |
- Non-contradiction : La proposition « $P$ et (non $P$) » est fausse.
- Tiers exclu : La proposition « $P$ ou (non $P$) » est vraie.
- Double négation : Les propositions « $P$ » et « non (non $P$) » sont équivalentes.
- Négation d'une conjonction : Les propositions « non ($P$ et $Q$) » et « (non $P$) ou (non $Q$) » sont équivalentes.
- Négation d'une disjonction : Les propositions « non ($P$ ou $Q$) » et « (non $P$) et (non $Q$) » sont équivalentes.
« Tu aimes le chocolat ou la pistache ? » « Non, je n'aime ni l'un ni l'autre. »
C - Implication et équivalence
Affirmer que la proposition $P$ implique la proposition $Q$, c'est affirmer que la vérité de $P$ entraîne celle de $Q$. Autrement dit, dès que $P$ est vraie, $Q$ doit également être vraie. L'implication est fausse lorsque $P$ est vraie et $Q$ est fausse.
- Implication : La proposition « $P \then Q$ » est $
\begin{cases}
\text{\uline{fausse}} & \text{si $P$ est vraie et $Q$ est fausse},\\
\text{vraie} & \text{sinon}.
\end{cases}
$
On dit alors « $P$ implique $Q$ » ou « si $P$ alors $Q$ ». - Équivalence : La proposition « $P \iff Q$ » est $
\begin{cases}
\text{vraie} & \text{si $P$ et $Q$ ont la même valeur de vérité},\\
\text{fausse} & \text{sinon}.
\end{cases}
$
On dit alors « $P$ et $Q$ sont équivalentes » ou « $P$ si et seulement si $Q$ ».
Il y a certaines choses à bien comprendre sur les implications
- Affirmer que la proposition « $P \then Q$ » est vraie n'implique ni que $P$ est vraie, ni que $Q$ est vraie. Par exemple, il est tout à fait vrai que « si $17$ est divisible par $4$, alors $17$ est un nombre pair ». Pourtant, $17$ n'est ni divisible par $4$, ni un nombre pair.
- Une implication « $P \then Q$ » peut être vraie sans que $P$ et $Q$ n’aient quoi que ce soit en commun. Par exemple, il est vrai que « si $2$ est un nombre premier, alors $\exp$ est une fonction croissante ». De plus, une implication n'exprime pas nécessairement une relation de causalité. Par exemple, on peut dire que « si la lumière est allumée, alors l'interrupteur est activé », alors que c'est l'activation de l'interrupteur qui provoque l'allumage de la lumière, et non l'inverse.
- Enfin, si $P$ est faux, alors l'implication « $P \then Q$ » est automatiquement vraie, peu importe $Q$. Il est par exemple vrai que « Si 0 > 1, alors les vaches ont des plumes ». Pour s'en convaincre, tout le monde serait d'accord avec l'affirmation suivante : Ainsi,
« Pour tout réel $x$, si $x$ est un entier naturel, alors il est positif »
- Pour $x = 3$, on obtient une implication de type « vrai $\then$ vrai ».
- Pour $x = -1$, on obtient une implication de type « faux $\then$ faux ».
- Pour $x = e$, on obtient une implication de type « faux $\then$ vrai ».
Supposons que l'implication « $P \then Q$ » est vraie.
- Condition nécessaire : On dit alors que $Q$ est une condition nécessaire de $P$.
- Condition suffisante : On dit alors que $P$ est une condition suffisante de $Q$.
Si l'équivalence « $P \iff Q$ » est vraie, on dit que $Q$ est une condition nécessaire et suffisante de $P$.
Soit $x \in \R$. On a $-1 \leq x \leq 1 \then x^2 \leq 2$. Donc,
- Pour que $x$ se situe entre $-1$ et $1$, il est nécessaire que son carré soit inférieur à $2$.
- Pour que le carré de $x$ soit inférieur à 2, il suffit que $x$ soit entre $-1$ et $1$.
Il ne faut pas confondre "il faut" et "il suffit". Si on vous demande comment répondre à une question mathématique et que vous répondez "il faut", vous sous-entendez que c'est la seule façon de procéder. Lorsque vous dites "il suffit", vous affirmez uniquement que c'est une méthode qui fonctionne sans nier l'existence d'une autre méthode.
- Réciproque : On appelle réciproque de l'implication « $P \then Q$ » la proposition « $Q \then P$ ».
- Contraposée : On appelle contraposée de l'implication « $P \then Q$ » la proposition « (non $Q$) $\then$ (non $P$) ».
- Négation d'une implication : Les propositions « non ($P \then Q$) » et « $P$ et (non $Q$) » sont équivalentes. Par négation, les propositions « $P \then Q$ » et « (non $P$) ou $Q$ » sont aussi équivalentes.
- Lien entre implication et contraposée : Toute implication est équivalente à sa contraposée. Autrement dit, les propositions « $P \then Q$ » et « (non $Q$) $\then$ (non $P$) » sont équivalentes.
- Lien entre implication et équivalence : Toute équivalence est une double implication. Autrement dit, les propositions « $P \iff Q$ » et « ($P \then Q$) et ($Q \then P$) » sont équivalentes.
Si une implication est vraie, sa contraposée l'est aussi, mais sa réciproque n'a aucune raison de l'être.
- Négation d'une implication : La proposition « Si j'ai 18 ans, alors je peux voter » n'est pas vraie puisqu'il est possible d'avoir 18 ans sans être inscrit sur les listes électorales.
- Lien entre implication et contraposée : Il est équivalent de dire « S'il pleut, alors il y a des nuages » et « S'il n'y a pas de nuages, alors il ne pleut pas ».
D - Quantificateurs
Soit $E$ un ensemble et $P(x)$ un prédicat où $x$ prend ses valeurs dans $E$.
- Quantificateur universel : La proposition « $\forall x \in E, \; P(x)$ » est $ \begin{cases} \text{vraie} & \text{si \uline{tout} $x \in E$ vérifie $P$},\\ \text{fausse} & \text{si au moins un $x \in E$ ne vérifie pas $P$}. \end{cases} $
- Quantificateur existentiel : La proposition « $\exists x \in E, \; P(x)$ » est $ \begin{cases} \text{vraie} & \text{si \uline{au moins} un $x \in E$ vérifie $P$},\\ \text{fausse} & \text{si aucun $x \in E$ ne vérifie $P$}. \end{cases} $
- La proposition « $\forall x \in \R, \quad x^2 \geq 0$ » est vraie.
- La proposition « $\exists z \in \C, \quad z^2 = -1$ » est vraie car $\i^2 = -1$.
Il faut toujours introduire les variables dont on parle. Rappelons toutefois que, dans une proposition universelle ou existentielle, la variable utilisée est muette~: les assertions $\forall x \in E,\; P(x)$ et $\exists x \in E,\; P(x)$ ne dépendent donc pas de la variable $x$ elle-même.
L'emploi de quantificateurs en guise d'abréviation est strictement interdit.
- Négation d'un $\forall$ : Les propositions « non $\bigl(\forall x \in E,\quad P(x)\bigr)$ » et « $\exists x \in E, \quad \text{non }P(x)$ » sont équivalentes.
- Négation d'un $\exists$ : Les propositions « $\text{non } \bigl(\exists x \in E,\quad P(x)\bigr)$ » et « $\forall x \in E, \quad \text{non }P(x)$ » sont équivalentes.
| La négation de | $\forall \eps > 0, \hquad \exists \alpha > 0, \hquad \forall x \in \R, \hquad \biggl(\abs{x} < \alpha \hthenh \abs{f(x) - 7} < \eps\biggr)$ |
| est | $\exists \eps > 0, \hquad \forall \alpha > 0, \hquad \exists x \in \R, \hquad \biggl(\abs{x} < \alpha \heth \abs{f(x) - 7} \geq \eps\biggr).$ |
Il est possible de permuter deux quantificateurs consécutifs lorsqu'ils sont de même nature, c'est-à-dire deux $\forall$ ou deux $\exists$. Par exemple, les propositions « $\exists x \in \R, \exists y \in \R, \hquad x+y = 0$ » et « $\exists y \in \R, \exists x \in \R, \hquad x+y^2 = 0$ » sont équivalentes.
En revanche, on ne peut pas, en général, permuter deux quantificateurs consécutifs de nature différente. Pour le comprendre, considérons les deux propositions suivantes : $$ \forall x\in E, \hquad \exists M\in\mathbb{R}, \hquad x\leq M \qqetqq \exists M\in\mathbb{R}, \hquad \forall x\in E,\hquad x\leq M. $$
Dans la première, chaque élément $x$ de $E$ possède son propre majorant $M$, qui peut dépendre de $x$. Dans la seconde, il existe un majorant global $M$, commun à tous les éléments de $E$.
Il est facile de se convaincre que la seconde proposition est plus forte que la première : si un même $M$ convient pour tous les $x$, alors, a fortiori, chaque $x$ possède un majorant. On retrouve ainsi, de manière générale, $$ \exists y, \hquad \forall x, \hquad P(x,y) \qqthenqq \forall x, \hquad \exists y, \hquad P(x,y). $$
mais la réciproque est fausse en général.
La proposition $\exists !\, x \in E,\; P(x)$ est vraie si l'ensemble $E$ contient exactement un élément de propriété $P$.
La proposition suivante est vraie : $\forall y \in \R_+, \hquad \exists! x \in \R_+, \hquad y = x^2$.
II) Ensembles
A - Généralités
La notion d'ensemble est une notion intuitive : on peut voir un ensemble comme une collection d'objets non-ordonnés, appelés ses éléments. Il ne s'agit pas ici d'en donner une définition rigoureuse ; on admet simplement cette notion et on s'intéresse aux propriétés qu'elle permet d'exprimer. Dire que $x$ est un élément d'un ensemble $E$ se note $x\in E$ et se lit « $x$ appartient à $E$ » ; dans le cas contraire, on écrit $x\notin E$. L'ensemble vide, noté $\varnothing$, est l'ensemble qui ne contient aucun élément ; on admet qu'il existe et qu'il est unique.
Il existe deux manières de définir un ensemble :
- En extension. On énumère explicitement tous les éléments de l'ensemble, entre accolades : $$\{1,3,5,7,11\}.$$ De cette façon, on ne peut définir que des ensembles finis.
- Par compréhension. On donne une règle permettant de caractériser les éléments de l'ensemble. Cette règle peut prendre deux formes.
- Par un prédicat. On part d'un ensemble de référence $F$, et on ne garde que les éléments qui satisfont une condition $P$ : $$\{x \in F \mid P(x)\}$$ Exemple : $E = \{x \in \mathbb{N} \mid x \text{ est premier}\}$. Pour savoir si un élément donné appartient à $E$, on teste la propriété $P$ sur lui.
- Par une formule. On décrit directement la forme des éléments : $$ \{f(n) \mid n \in F\} = \{f(n)\}_{n \in F}. $$ Ces deux notations reviennent à écrire $$ E = \Set[\big]{x \in E}{\exists n \in F,\ x = f(n)}. $$ Par exemple, l'ensemble des entiers pairs peut s'écrire de plusieurs façons : $$ \{2n \mid n \in \mathbb{N}\} = \{2n\}_{n \in \mathbb{N}} = \{n \in \mathbb{N} \mid \exists p \in \mathbb{N},\ n = 2p\}. $$
Un même ensemble peut être décrit de différentes façons : ces descriptions peuvent être différentes, tout en désignant exactement le même ensemble. L'objectif est donc de pouvoir choisir, selon la situation, la description la plus naturelle et la plus pratique.
Pour définir un ensemble par compréhension, on a besoin de connaître un ensemble plus grand. Ainsi, on admet l'existence de certains ensemble comme les réels, les entiers naturels, les fonctions, etc... et on définit des sous-ensembles à partir de ceux-ci.
Si un ensemble $E$ est fini, on appelle cardinal de $E$ son nombre d'éléments. Le cardinal d'un ensemble $E$ est souvent noté $\abs{E}$ ou $\Card{E}$.
Un singleton (resp. une paire) est un ensemble qui contient un (resp. deux) élément(s).
Pour tous $a,b \in \N$ tels que $a \leq b$, $\Card{\Intn{a}{b}} = b - a \, \InlineKey[tight]{+1}$.
Soient $E$ et $F$ deux ensembles.
- Inclusion : On dit que $E$ est inclus dans $F$, que $E$ est une partie de $F$ ou que $F$ contient $E$ (noté $E \subset F$) si tout élement de $E$ est également dans $F$. Autrement dit, si : $\forall x \in E, \quad x \in F$.
- Égalité : On dit que les ensembles $E$ et $F$ sont égaux (noté $E$ = $F$) s'ils ont exactement les mêmes éléments. On a alors : $E = F \qiffq E \subset F \:\et\: F \subset E$.
Attention à ne pas confondre les symboles $\in$ et $\subset$ qui n'ont pas du tout le même sens.
L'appartenance et l'inclusion ne sont pas au même niveau. De manière générale, un ensemble n'est pas à la fois un élément et inclus dans un autre ensemble. Par exemple,
- $1 \in \R$ mais $1 \not\subset \R$
- $\N \subset \R$ mais $\N \not\in \R$.
Pour certains cas particuliers, c'est néanmoins possible, par exemple $\{1\}$ est à la fois inclus et un élément de $\big\{1,\{1\}\big\}$.
Soit $E$ un ensemble. On note $\Pr(E)$ l'ensemble des parties de $E$. Ainsi, pour tout ensemble $A$, $A \subset E \iff A \in \Pr(E)$.
Soit $E$ un ensemble. Les ensembles $E$ et $\varnothing$ sont des parties de $E$.
$\Pr(\{0,1,2\}) = \big\{\varnothing, \{0\}, \{1\}, \{2\}, \{0,1\}, \{0,2\}, \{1,2\}, \{0,1,2\}\big\}$
B - Opérations sur les ensembles
Soient $A, B \subset E$ deux ensembles et $\{A_i\}_{i \in I}$ un ensemble de parties de $E$.
- Réunion : On appelle réunion de $A$ et $B$ l'ensemble $$ A \cup B := {\Set{x \in E}{ x \in A \text{ ou } x \in B}}. $$ On appelle réunion des $A_i$, $i$ décrivant $I$, l'ensemble $$ \bigcup_{i\in I} A_i := \Set{x \in E}{\exists i \in I, x \in A_i}. $$
- Intersection : On appelle intersection de $A$ et $B$ l'ensemble $$ A \cap B := {\Set{x \in E}{x \in A \text{ et } x \in B}}. $$ On appelle intersection des $A_i$, $i$ décrivant $I$, l'ensemble $$ \bigcap_{i\in I} A_i := \Set{x \in E}{\forall i \in I, x \in A_i}. $$
Pour tous ensembles $A$ et $B$ : $A \subset B \iff A \cup B = B \iff A \cap B = A.$
Soient $A, B \subset E$.
- Différence : On appelle différence de $B$ dans $A$ (et on lit « $A$ privé de $B$ ») l'ensemble $$ A \but B := \Set{x \in E}{x \in A \text{ et } x \not\in B}. $$
- Complémentaire : On appelle complémentaire de $A$ dans $E$ l'ensemble $E \but A$ aussi noté $A^c$ ou $\overline{A}$ quand le contexte est clair.
- Si $A \subset B$, alors $\overline{B} \subset \overline{A}$.
- $A \but B = A \cap \overline{B}$.
- Si $\hquad A \cup B = E \heth A \cap B = \emptyset$, alors $B = \overline{A}$.
Soit $\{A_i\}_{i \in I}$ un ensemble de parties de $E$. On a $$ \pa{\bigcup_{i\in I} A_i} \cap B = \bigcup_{i\in I} \pa{A_i \cap B } \qqetqq \pa{\bigcap_{i\in I} A_i} \cup B = \bigcap_{i\in I} \pa{A_i \cup B }. $$ D'autre part, $$ \overline{\bigcup_{i\in I} A_i} = \bigcap_{i\in I} \overline{A_i} \qqetqq \overline{\bigcap_{i\in I} A_i} = \bigcup_{i\in I} \overline{A_i}. $$
- Ensemble disjoint : Soient deux ensembles $A$ et $B$. On dit que $A$ et $B$ sont disjoints si $A \cap B = \varnothing$. Leur réunion est dans ce cas souvent notée $A \sqcup B$. Pour un ensemble $\{A_i\}_{i \in I}$ d'ensembles deux à deux disjoints, leur réunion est souvent notée $\bigsqcup_{i\in I} A_i$.
- Recouvrement disjoint : Soit $E$ un ensemble. On appelle recouvrement disjoint de $E$ tout ensemble $\{A_i\}_{i \in I}$ de parties de $E$ tel que $E = \bigsqcup_{i\in I} A_i$. Si de plus aucun des $A_i$ n'est vide, on dit que c'est une partition de $E$.
L'ensemble $\{\{0\}, \{1,3,4\}, \{2,5\}\}$ est une partition de $\Intn{0}{5}$.
Soient $E_1, \dots, E_n$ des ensembles. On définit le produit cartésien de $E_1, \dots, E_n$ par $$ E_1 \times \dots \times E_n := \Set[\big]{(e_1, \dots, e_n)}{\forall i \in \Intn{1}{n}, \hquad e_i \in E_i}. $$ Si $E_1 = \dots = E_n = E$, ce produit est plutôt noté $E^n$.
$\{0,1\} \times \{1,2,3\} = \{(0,1),(0,2),(0,3),(1,1),(1,2),(1,3)\}$.
Famille $(x_1, \dots, x_n) \ne $ Ensemble $\{x_1, \dots, x_n\}$.
Glissez une image, collez-la (Ctrl+V), ou parcourez un fichier — ou collez directement l'énoncé en texte.