Algèbre 1 : Structures mathématiques

Tout + Tout −

En attendant la rédaction de cette partie, voir le cours complet au format PDF : Algèbre 1 (PDF)
TD : Algèbre 1 — TD (PDF)
(ou sur Google Drive : lien Drive)
Attention : le PDF est en cours de relecture — des erreurs peuvent subsister.

Logiques Élémentaires

Introduction et lexique
But du cours
Le but du cours est double :
1. Acquérir le raisonnement mathématique.
2. Maîtriser le langage mathématique.
Objet mathématique et définition

(Objet mathématique)

On appelle {objet mathématique} tous les objets qui interviennent en mathématique. Ce sont des choses que l'on nomme et que l'on définit par des propriétés qu'ils satisfont.
1. $\mathbb{N}$ est l'ensemble des entiers.
2. Un cercle est l'ensemble des points du plan qui sont équidistants d'un point donné.
Énoncé mathématique
Elle consiste en la donné d'une propriété concernant des objets mathématiques. Exemples :
1. Théorème de Pythagore.
2. Théorème de Fermat : Si $n \geqslant 3$ avec $n \in \mathbb{N}$, alors : \[ x^n + y^n = z^n \] ne possède pas de solutions entières $x, y, z$ non toutes nulles.
Théorie Mathématique

(Axiome)

Un {axiome} est un énoncé mathématique (assertion) que l'on suppose vraie par évidence sans avoir besoin d'être démontré.

Dans la géométrie dans le plan, il y a les Axiomes d'Euclide. La construction des entiers naturels est l'Axiome de Peano.

(Axiome du tiers exclu)

\warning Principe de non-contradiction : Une assertion ne peut pas être vraie et fausse à la fois. $\implies$ \warning Principe du tiers exclu : Si une assertion n'est pas vraie, alors elle est forcément fausse et inversement. Autrement dit : une assertion est soit vraie, soit fausse, il n'y a pas de troisième possibilité (d'où le nom "tiers exclu") :
Schématiquement : \[ \text{Axiome} \xrightarrow{\text{Règle logique}} \text{Nouveau énoncé} \] Terminologie :
- Assertion importante $\rightarrow$ Théorème
- Assertion moins importante $\rightarrow$ Propriété
- Assertion intermédiaire qui permet de démontrer un théorème $\rightarrow$ Lemme
- Assertion qui découle directement d'un théorème $\rightarrow$ Corolaire
Connecteurs logiques
(Connecteur logique)

On appelle {connecteur logique} un type d'opération agissant sur les assertions pour en construire une nouvelle.

(Logique mathématique)

On appelle {logique mathématique} la description de la manipulation de ces opérations et ce, quelle que soit la véracité des assertions simples qui la composent.

Table de vérité

(Table de vérité)

On appelle {table de vérité} un tableau qui donne la valeur de vérité (Vrai ou Faux) d'une assertion composée en fonction des valeurs de vérité des assertions simples qui la composent.

Soient $P$ et $Q$ deux assertions simples. Une table de vérité de $P$ et de $Q$ avec un connecteur logique entre $P$ et $Q$ est donnée par :

[Tableau LaTeX non converti — à reprendre à la main]
ou encore donnée par :
[Tableau LaTeX non converti — à reprendre à la main]

avec « ? » à définir par $V$ ou $F$ selon le connecteur logique $\bigstar$ que l'on souhaite définir.

(Tautologie)

Un construction logique qui est {toujours vraie} quelque soit la véracité des assertions mises en jeu s'appelle une {tautologie}.

Énoncés équivalents
Soient $P$ et $Q$ deux énoncés.
(Équivalence logique)

On dit que $P$ et $Q$ sont {équivalents} s'ils ont la même table de vérité, autrement dit, s'ils sont tous les deux vrais, soit tous les deux faux (on notera alors « $P \iff Q$ »{}). Table de vérité :

[Tableau LaTeX non converti — à reprendre à la main]

Négation

(Négation d'une assertion)

Soit $P$ un assertion. On appelle {négation} de $P$, notée $\lnot P$ (ou « non $P$ »{}, ou enocre « $\overline{P}$ »{}), l'assertion qui est vraie si $P$ est fausse, et fausse si $P$ est vraie :

[Tableau LaTeX non converti — à reprendre à la main]
1. $P = \text{\og Tous les étudiants présents dans l'amphi auront leur année \fg{}}$ $\neg P = \text{\og Il existe au moins un étudiant qui n'aura pas son année \fg{}}$
2. $P = \text{\og n est un entier pair \fg{}}$ $\neg P = \text{\og n est un entier impair \fg{}}$
(Double négation)

Soit $P$ une assertion, on a : \[ \lnot(\lnot P) \iff P \]

[Tableau LaTeX non converti — à reprendre à la main]

(Raisonnement par l'absurde)

En associant la négation et le principe de non-contradiction, on obtient le {raisonnement par l'absurde}. Pour démontrer qu'une assertion $P$ est vraie, on suppose qu'elle est fausse, c'est-à-dire $\lnot P$ est vraie, et on essaie d'aboutir à une contradiction.

On veut montrer que l'assertion $P$ : « Il existe une infinité de nombres premiers »{} est vraie. Rappel : $p$ est premier si $p$ est un entier naturel strictement supérieur à $1$ qui n'admet aucun diviseur autre que $1$ et lui-même. Par exemple, $2, 3, 5, 7, 11, 13, \ldots$ sont des nombres premiers. Preuve : On suppose que $\lnot P$ est vraie, c'est-à-dire $\lnot P$ = « Les nombres premiers sont en nombre fini »{}. Puisqu'on a un nombre fini de nombres premiers, il existe un plus grand que l'on note $p$. On va considérer l'entier $N = p! + 1$ (avec $p! = p \times (p-1) \times (p-2) \times \cdots \times 4 \times 3 \times 2 \times 1$). On a : $N > p$. Par hypothèse, $N$ est plus grand que le plus grand des nombres premiers, donc $N$ n'est pas premier. Or tout entier s'écrit comme un produit de nombres premiers. Donc il existe un nombre premier qui divise $N$ : absurde car $N$ n'admet pas de diviseurs premiers (puisque pour tout nombre premier $q \leqslant p$, on a $q \mid p!$ donc $q \nmid p! + 1 = N$), donc $N$ est premier. On a donc prouvé que $\lnot P$ est fausse, et donc que la proposition $P$ est vraie.

Montrons que $\sqrt{2}$ est un nombre irrationnel. On rappelle que $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}$. Un nombre irrationnel est un nombre réel qui ne s'écrit pas sous la forme $\dfrac{p}{q}$ avec $p$ un entier relatif et $q$ un entier relatif non nul. Par exemple, $\pi$, $e$, $\ldots$ Preuve : Par l'absurde, on suppose que $\sqrt{2} \in \mathbb{Q}$, c'est-à-dire qu'il existe deux entiers naturels $p$ et $q$ tels que : \[ \sqrt{2} = \frac{p}{q} \quad \text{tel que} \quad \mathrm{PGCD}(p; q) = 1. \] Ici, le $\mathrm{PGCD}(a; b)$ pour $a$ et $b$ des entiers, est le plus grand diviseur commun de $a$ et $b$. On a : \[ \sqrt{2} = \frac{p}{q} \quad \text{donc} \quad q\sqrt{2} = p \] \[ 2q^2 = p^2 \] D'où $2$ divise $p^2$, alors on peut montrer que $2$ divise $p$. Donc $p$ est pair et il existe $k$ un entier tel que $p = 2k$. On a : \[ 2q^2 = (2k)^2 = 4k^2 \quad \text{d'où} \quad q^2 = 2k^2 \] Ainsi $2$ divise $q^2$ et donc $q$ est pair. Finalement, on a : \[ \mathrm{PGCD}(p, q) \geqslant 2 \quad @@MATH29@@ \] Absurde car par hypothèse le $\mathrm{PGCD}$ de $p$ et $q$ vaut $1$. Donc $\sqrt{2}$ n'est pas rationnel, d'où $\sqrt{2}$ est irrationnel.
Autre type de démonstration : On « combine »{} la négation d'une assertion avec le principe du tiers exclu.
(Raisonnement par disjonction de cas) On veut montrer que : \[ P : \text{\og il existe des nombres irrationnels } a > 0 \text{ et } b > 0 \text{ tels que le nombre } a^b \text{ soit rationnel \fg{}} \] est vraie. Preuve : Pour démontrer que $P$ est vraie, on va considérer l'assertion suivante : \[ Q : \text{\og le nombre } \sqrt{2}^{\sqrt{2}} \text{ est rationnel \fg{}}. \]
- [$\implies$] On suppose que $Q$ est vraie : Alors $\sqrt{2}^{\sqrt{2}}$ est rationnel et donc $P$ est vraie car dans ce cas on peut prendre $a = b = \sqrt{2}$ qui sont bien des irrationnels et puisque $Q$ est vraie, $a^b = \sqrt{2}^{\sqrt{2}}$ est rationnel. Donc $P$ est vraie.
- [$\implies$] On suppose que $Q$ est fausse, donc non $Q$ est vraie : Donc $\sqrt{2}^{\sqrt{2}}$ est irrationnel. Si on prend :
  - $a = \sqrt{2}^{\sqrt{2}}$ (est irrationnel) $> 0$
  - $b = \sqrt{2} > 0$
  Alors : \[ a^b = \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{2} = 2 \] Donc $a^b$ est un rationnel. Donc finalement $P$ est vraie.
Conclusion : Dans les deux cas (qui épuisent toutes les possibilités grâce au tiers exclu), la proposition $P$ est vraie.
Conjonction et disjonctions

(Conjonction de deux assertions)

Soient $P$ et $Q$ deux assertions. On appelle {conjonction} de $P$ et $Q$ l'assertion notée {$P \land Q$} que l'on définit comme vraie si $P$ et $Q$ sont vrais, et {$P \land Q$} fausse dans tous les autres cas de $P$ et $Q$. On lit « {$P \land Q$} »{} : {$P$ et $Q$}. Table de vérité :

[Tableau LaTeX non converti — à reprendre à la main]
Si on désigne un nombre entier $n$ :
- $P$ = « $n$ est un multiple de $2$ »{}
- $Q$ = « $n$ est un multiple de $3$ »{}
Alors $P \land Q$ est équivalent à l'assertion « $n$ est un multiple de $6$ »{}. En effet, $n$ est un multiple de $2$ ET de $3$ si et seulement si $n$ est un multiple du PPCM de $2$ et $3$, c'est-à-dire de $6$.
(Idempotence de la conjonction)

Soit $P$ une assertion. On a : \[ P \land P \iff P. \]

Nous vérifions cette équivalence à l'aide d'une table de vérité.
\renewcommand{\arraystretch}{1.2}
[Tableau LaTeX non converti — à reprendre à la main]

La colonne finale contient uniquement des Vrai, ce qui prouve que l'équivalence est une tautologie.

(Disjonction de deux assertions)

Soient $P$ et $Q$ deux assertions. On appelle {disjonction} de $P$ et $Q$ l'assertion notée {$P \lor Q$} que l'on définit comme vraie si au moins l'une des deux assertions $P$ ou $Q$ est vraie, et {$P \lor Q$} fausse uniquement si $P$ et $Q$ sont toutes les deux fausses. On lit « {$P \lor Q$} »{} : {$P$ ou $Q$} (le mot « ou »{} est utilisé en français dans le sens inclusif, c'est-à-dire que si une assertion est vraie, alors la disjonction est vraie, même si l'autre affirmation est fausse). Table de vérité :

[Tableau LaTeX non converti — à reprendre à la main]
Pour un entier naturel $n$ on pose :
- $P$ = « $n$ est pair »{}
- $Q$ = « $n \leqslant 10$ »{}
Donc $P \lor Q$ est équivalent à :
« $n$ est un entier pair ou $n$ est un nombre impair inférieur ou égal à $10$ »{}
Soit $x$ un nombre réel. « $x^2 + 2x - 2 > 0$ »{} $\iff$ « $x \leqslant -1-\sqrt{3}$ »{} $\lor$ « $x \geqslant -1+\sqrt{3}$ »{} Cela revient à résoudre sur $\mathbb{R}$ l'inéquation : \[ x^2 + 2x - 2 > 0 \] On cherche les racines de $x^2 + 2x - 2 = 0$. On a $\Delta = 4 - 4 \times 1 \times (-2) = 12 > 0$. Donc on a deux racines réelles données par : \[ x_1 = \frac{-2-\sqrt{12}}{2} = -1-\sqrt{3} \] \[ x_2 = \frac{-2+\sqrt{12}}{2} = -1+\sqrt{3} \]

(Idempotence de la disjonction)

Soit $P$ une assertion. On a : \[ P \lor P \iff P. \]

Nous vérifions cette équivalence à l'aide d'une table de vérité.
\renewcommand{\arraystretch}{1.2}
[Tableau LaTeX non converti — à reprendre à la main]

La colonne finale contient uniquement des Vrai, ce qui prouve que l'équivalence est une tautologie.

(Associativité de la disjonction)

Soient $P$, $Q$ et $R$ trois assertions. On a : \[ (P \lor (Q \lor R)) \iff ((P \lor Q) \lor R). \]

(à refaire en exercice) Nous comparons les tables de vérité des deux membres de l'équivalence.
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]

Les colonnes correspondant à $P \lor (Q \lor R)$ et $(P \lor Q) \lor R$ sont strictement identiques. La colonne finale contenant uniquement des Vrai prouve l'équivalence logique.

(Associativité de la conjonction)

Soient $P$, $Q$ et $R$ trois assertions. On a : \[ (P \land (Q \land R)) \iff ((P \land Q) \land R). \]

(à refaire en exercice) Nous comparons les tables de vérité des deux membres de l'équivalence.
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]

Les colonnes de $P \land (Q \land R)$ et $(P \land Q) \land R$ coïncident parfaitement. La colonne finale valide l'équivalence logique.

(Distributivité de la conjonction sur la disjonction)

Soient $P$, $Q$ et $R$ trois assertions. On a : \[ P \land (Q \lor R) \iff (P \land Q) \lor (P \land R). \]

(à refaire en exercice) Nous comparons les tables de vérité des deux membres de l'équivalence.
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]

Les colonnes de $P \land (Q \lor R)$ et $(P \land Q) \lor (P \land R)$ coïncident parfaitement sur les 8 cas possibles. La colonne finale valide l'équivalence.

(Distributivité de la disjonction sur la conjonction)

Soient $P$, $Q$ et $R$ trois assertions. On a : \[ P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R). \]

(à refaire en exercice) Nous comparons les tables de vérité des deux membres de l'équivalence.
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]

Les colonnes correspondant à $P \lor (Q \land R)$ et $(P \lor Q) \land (P \lor R)$ sont strictement identiques. La dernière colonne, remplie uniquement de Vrai, confirme l'équivalence logique.

(Commutativité de la conjonction)

Soient $P$ et $Q$ deux assertions. On a l'équivalence : \[ P \land Q \iff Q \land P \]

Nous vérifions cette équivalence à l'aide d'une table de vérité.
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]

Les colonnes de $P \land Q$ et $Q \land P$ sont strictement identiques. La dernière colonne, remplie uniquement de Vrai, confirme l'équivalence logique.

(Commutativité de la disjonction)

Soient $P$ et $Q$ deux assertions. On a l'équivalence : \[ P \lor Q \iff Q \lor P \]

Nous vérifions cette équivalence à l'aide d'une table de vérité.
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]

Les colonnes de $P \lor Q$ et $Q \lor P$ coïncident parfaitement. La colonne finale valide ainsi l'équivalence logique.

(Lois de De Morgan)
Soient $P$ et $Q$ deux assertions, alors :
1. $\lnot(P \lor Q) \iff (\lnot P) \land (\lnot Q)$
2. $\lnot(P \land Q) \iff (\lnot P) \lor (\lnot Q)$
Preuve du i)
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]

Donc finalement : \[ \lnot(P \lor Q) \iff (\lnot P) \land (\lnot Q) \] Preuve du ii)
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]

Donc finalement : \[ \lnot(P \land Q) \iff (\lnot P) \lor (\lnot Q) \]

Implication
L'implication est un connecteur logique essentiel car à la base du raisonnement déductif. Ce connecteur est la traduction de « Si ... , alors ... »{}.
(Implication ($\implies$))

Soient $P$ et $Q$ deux assertions. On dit que « $P$ {implique} $Q$ »{} et on note « $P \implies Q$ »{} si :

[Tableau LaTeX non converti — à reprendre à la main]

(Fausseté d'une implication)

Pour montrer qu'une implication $P \implies Q$ est fausse, il suffit de démontrer que l'assertion de départ $P$ est vraie et que l'assertion d'arrivée $Q$ est fausse.

D'après la table de vérité de la définition , l'assertion $P \implies Q$ n'est fausse que dans un seul cas : lorsque $P$ est vraie et $Q$ est fausse (deuxième ligne du tableau). Ainsi, pour établir la fausseté d'une implication, il suffit de vérifier cette unique configuration.

(Caractérisation de l'équivalence logique)

Soient $P$ et $Q$ deux assertions. On a l'équivalence fondamentale : \[ (P \iff Q) \iff \big((P \implies Q) \land (Q \implies P)\big) \] Autrement dit, démontrer une équivalence revient à démontrer une double implication : l'implication directe et sa réciproque.

Nous allons vérifier cette équivalence à l'aide d'une table de vérité.
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]

Les colonnes correspondant à $P \iff Q$ et $(P \implies Q) \land (Q \implies P)$ sont strictement identiques. La dernière colonne, remplie uniquement de Vrai, confirme l'équivalence logique.

(Simplification de la conjonction)

Soient $P$ et $Q$ deux assertions. Si $P$ et $Q$ sont vraies simultanément, alors $P$ est nécessairement vraie : \[ (P \land Q) \implies P \]

Nous vérifions cette implication à l'aide d'une table de vérité.
\renewcommand{\arraystretch}{1.2}
[Tableau LaTeX non converti — à reprendre à la main]

La colonne finale contient uniquement des Vrai, ce qui prouve que l'implication est une tautologie.

(Affaiblissement par disjonction)

Soient $P$ et $Q$ deux assertions. Si $P$ est vraie, alors l'assertion "$P$ ou $Q$" est également vraie : \[ P \implies (P \lor Q) \]

Nous vérifions cette implication à l'aide d'une table de vérité.
\renewcommand{\arraystretch}{1.2}
[Tableau LaTeX non converti — à reprendre à la main]

La colonne finale contient uniquement des Vrai, ce qui prouve que l'implication est une tautologie.

(Loi de l'implication matérielle)

Soient $P$ et $Q$ deux assertions. L'implication peut se reformuler à l'aide de la négation et de la disjonction : \[ (P \implies Q) \iff (\lnot P \lor Q) \] Autrement dit, démontrer une implication revient à montrer que soit l'hypothèse $P$ est fausse, soit la conclusion $Q$ est vraie. En pratique, cela signifie qu'il est impossible d'avoir $P$ vraie et $Q$ fausse simultanément.

Pour établir cette loi, nous comparons les tables de vérité des deux membres.
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]

Les colonnes correspondant à $\lnot P \lor Q$ et $P \implies Q$ sont strictement identiques sur les quatre cas possibles. La dernière colonne valide ainsi l'équivalence logique.

(Raisonnement par inférence (Modus Ponens))

Soient $P$ et $Q$ deux assertions, alors : \[ P \land (P \implies Q) \implies Q \] est une tautologie. Autrement dit, si l'on sait que $P$ est vraie et que l'implication $P \implies Q$ a été démontrée, alors on peut en déduire avec certitude que $Q$ est vraie. Ce mécanisme est le fondement du raisonnement déductif : il permet de passer d'une hypothèse vérifiée à une conclusion nécessaire, et structure l'enchaînement de la plupart des théorèmes.
Nous allons vérifier que l'assertion est une tautologie en dressant sa table de vérité complète.
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]
1. La 3e colonne calcule l'implication $P \implies Q$.
2. La 4e colonne calcule la conjonction de $P$ avec cette implication (c'est l'hypothèse du raisonnement).
3. La dernière colonne évalue l'implication finale.
Puisque la dernière colonne ne contient que des Vrai (V), l'assertion est toujours vraie, quelle que soit la valeur de vérité de $P$ et $Q$. C'est donc bien une tautologie.
(Transitivité)

Soient $P$, $Q$ et $R$ trois assertions, alors : \[ ((P \implies Q) \land (Q \implies R)) \implies (P \implies R) \] Cela illustre le découpage d'une démonstration en étapes : si $P$ implique $Q$ et que $Q$ implique $R$, alors on peut conclure que $P$ implique $R$. C'est un principe fondamental du raisonnement logique, qui permet de construire des chaînes d'implications pour établir des résultats plus complexes à partir de résultats plus simples.
Nous allons démontrer que cette assertion est une tautologie à l'aide d'une table de vérité.
\renewcommand{\arraystretch}{1.2} \small
[Tableau LaTeX non converti — à reprendre à la main]
1. Les colonnes 4 et 5 calculent les implications intermédiaires.
2. La colonne 6 représente l'hypothèse (les deux implications doivent être vraies).
3. La colonne 7 représente la conclusion.
4. La dernière colonne vérifie : Hypothèse $\implies$ Conclusion.
Puisque la colonne finale ne contient que des Vrai, l'assertion est une tautologie.
(Négation d'une implication)

Soient $P$ et $Q$ deux assertions, alors : \[ \lnot(P \implies Q) \iff (P \land \lnot Q) \]

Il n'est pas toujours nécessaire de faire une table de vérité complète pour prouver une équivalence logique. Nous pouvons utiliser les propriétés déjà établies pour transformer l'expression de la négation de l'implication et montrer qu'elle est équivalente à $P \land \lnot Q$. En effet, en utilisant la propriété , on a : \[ (P \implies Q) \iff (\lnot P \lor Q) \] d'où en appliquant la négation à chaque membre on a : $$\begin{align*} \, & & \lnot(P \implies Q) & \iff \lnot(\lnot P \lor Q) & \text{(Loi de l'implication matérielle )} \\ & & & \iff (\lnot(\lnot P)) \land (\lnot Q) & \text{(Lois de De Morgan )} \\ & & & \iff P \land (\lnot Q) & \text{(Double négation )} \end{align*}$$

(Contraposition)

Soient $P$ et $Q$ deux assertions. L'implication « $P \implies Q$ »{} est logiquement équivalente à sa {contraposée} $\lnot Q \implies \lnot P$: \[ (P \implies Q) \iff (\lnot Q \implies \lnot P). \] Autrement dit, pour démontrer que $P$ implique $Q$, il est tout aussi valide de démontrer que si $Q$ est fausse, alors $P$ est forcément fausse.

Nous allons prouver cette équivalence en transformant le membre de droite (la contraposée) pour retrouver le membre de gauche, à l'aide des propriétés précédentes. $$\begin{align*} \, & & \lnot Q \implies \lnot P & \iff \lnot(\lnot Q) \lor \lnot P & \text{(Loi de l'implication matérielle )} \\ & & & \iff Q \lor \lnot P & \text{(Double négation )} \\ & & & \iff \lnot P \lor Q & \text{(Commutativité de la disjonction )} \\ & & & \iff P \implies Q & \text{(Loi de l'implication matérielle )} \end{align*}$$ L'implication et sa contraposée ont donc exactement la même valeur de vérité.
(Démonstration par contraposition) Soient :
- $P$ : « $n^2$ est un entier pair »
- $Q$ : « $n$ est un entier pair »
On veut démontrer que $(P \implies Q)$ est vraie. On va le montrer par contraposée, c'est-à-dire : $(\lnot Q \implies \lnot P)$. On suppose que $\lnot Q$ est vraie, c'est-à-dire : \[ \lnot Q : \text{\og $n$ est un entier impair \fg} \] Et on veut montrer que $\lnot P$ est vraie, c'est-à-dire que $n^2$ est un entier impair. On suppose que $n$ est impair donc il existe $k$ un entier tel que $n = 2k + 1$, alors : $$\begin{align*} n^2 & = (2k + 1)^2 \\ n^2 & = 4k^2 + 4k + 1 \\ n^2 & = 2(2k^2 + 2k + 1) + 1 \end{align*}$$ d'où $n^2$ est impair. $(\lnot Q \implies \lnot P)$ est vraie donc par contraposée $(P \implies Q)$ est vraie.
Quantificateurs
Les quantificateurs sont des symboles logiques qui permettent de préciser sur quels éléments d'un ensemble porte une assertion. Ils sont indispensables pour formaliser rigoureusement les assertions mathématiques. Certaines assertions sont fondés au travers d'une variable ou indéterminé, c'est-à-dire un objet mathématique qui peut prendre plusieurs valeurs.

« L'entier $n(n + 1)$ est pair ». Soit $E$ un ensemble. Si une assertion $P$ dépend de la variable $x \in E$, on la notera $P\{x\}$ ou $P(x)$. S'il y a plusieurs variables, on notera $P\{x, y\}$ ou $P(x, y)$.

Quantificateur universel ($\forall$)

(Quantificateur universel)

On appelle {quantificateur universel} le symbole {$\forall$}, qui signifie « pour tout »{} , « pour chaque »{} , « quel que soit »{} , « peu importe »{} ou « n'importe quel »{}. Ce quantificateur est utilisé pour décrire une propriété qui est vraie pour tous les éléments d'un ensemble donné. Soit $E$ un ensemble et $P(x)$ une assertion dépendant de $x \in E$. L'assertion : \[ \forall x \in E,\, P(x) \] est vraie si et seulement si $P(x)$ est vraie pour tous les éléments $x$ de $E$. Elle est fausse dès qu'il existe au moins un élément de $E$ pour lequel $P(x)$ est fausse. Dans ce cas, on dit que $P(x)$ est {contredite} par cet élément, qui est alors appelé un {contre-exemple}.
- $\forall x \in \mathbb{R},\, x^2 \geqslant 0$ est vraie.
- $\forall n \in \mathbb{N},\, n^2 \geqslant n$ est vraie.
- $\forall x \in \mathbb{R},\, x > 0$ est fausse (contre-exemple : $x = -1$).
Quantificateur existentiel ($\exists$)

(Quantificateur existentiel)

On appelle {quantificateur existentiel} le symbole {$\exists$}, qui signifie « il existe »{} ou « il existe au moins un »{}. Soit $E$ un ensemble et $P(x)$ une assertion dépendant de $x \in E$. L'assertion : \[ \exists x \in E,\, P(x) \] est vraie s'il existe au moins un élément $x \in E$ tel que $P(x)$ soit vraie. Elle est fausse si $P(x)$ est fausse pour tous les éléments de $E$. Dans le cas où il existe un unique élément $x \in E$ tel que $P(x)$ soit vraie, on peut renforcer l'assertion en écrivant : \[ \exists! x \in E,\, P(x) \] qui se lit « il existe un unique $x$ dans $E$ tel que $P(x)$ soit vraie ». Un élément $x \in E$ vérifiant $P(x)$ est appelé un {témoin} de l'assertion existentielle.
- $\exists x \in \mathbb{R},\, x^2 = 4$ est vraie (témoins : $x=2$ ou $x=-2$).
- $\exists! x \in \mathbb{R},\, x^2 = 4$ est fausse (car il existe deux témoins : $x=2$ et $x=-2$).
- $\exists x \in \mathbb{R},\, x^2 = -1$ est fausse.
- $\exists! x \in \mathbb{R},\, x+1=3$ est vraie (l'unique témoin est $x=2$).
Propriétés de $\forall$ et $\exists$

(Négation des quantificateurs)
Soit $E$ un ensemble et $P\{x\}$ une assertion qui dépend de $x \in E$. Alors :
1. $\lnot(\forall x \in E, P\{x\}) \iff \exists x \in E, \lnot P\{x\}$
2. $\lnot(\exists x \in E, P\{x\}) \iff \forall x \in E, \lnot P\{x\}$
Preuve du i) : Montrons la double implication par analyse sémantique.
- [\fbox{$\Rightarrow$}] Supposons que $\lnot(\forall x \in E,\, P\{x\})$ est vraie. Alors l'assertion $\forall x \in E,\, P\{x\}$ est fausse. Cela signifie qu'il n'est pas vrai que $P\{x\}$ soit satisfaite pour tous les éléments de $E$. Il existe donc au moins un élément $x_0 \in E$ tel que $P\{x_0\}$ est fausse, c'est-à-dire $\lnot P\{x_0\}$ est vraie. Par définition du quantificateur existentiel, $\exists x \in E,\, \lnot P\{x\}$ est vraie.
- [\fbox{$\Leftarrow$}] Supposons que $\exists x \in E,\, \lnot P\{x\}$ est vraie. Il existe alors un élément $x_0 \in E$ tel que $\lnot P\{x_0\}$ est vraie, donc $P\{x_0\}$ est fausse. Puisqu'il existe au moins un contre-exemple dans $E$, l'affirmation « $P\{x\}$ est vraie pour tout $x \in E$ » est nécessairement fausse. Ainsi, $\lnot(\forall x \in E,\, P\{x\})$ est vraie.
Les deux assertions s'impliquant mutuellement, donc d'après , elles sont logiquement équivalentes. Preuve du ii) : On procède de manière analogue.
- [\fbox{$\Rightarrow$}] Supposons $\lnot(\exists x \in E,\, P\{x\})$ vraie. Alors $\exists x \in E,\, P\{x\}$ est fausse, ce qui signifie qu'aucun élément de $E$ ne vérifie $P$. Autrement dit, pour tout $x \in E$, $P\{x\}$ est fausse, donc $\lnot P\{x\}$ est vraie. D'où $\forall x \in E,\, \lnot P\{x\}$.
- [\fbox{$\Leftarrow$}] Supposons $\forall x \in E,\, \lnot P\{x\}$ vraie. Alors pour tout $x \in E$, $P\{x\}$ est fausse. Il est donc impossible de trouver un $x \in E$ tel que $P\{x\}$ soit vraie. L'assertion $\exists x \in E,\, P\{x\}$ est donc fausse, ce qui équivaut à dire que $\lnot(\exists x \in E,\, P\{x\})$ est vraie.
D'après , l'équivalence est ainsi établie par double implication.
(Distributivité des quantificateurs)
Soit $E$ un ensemble et soient $P\{x\}$ et $Q\{x\}$ deux assertions qui dépendent de $x \in E$. Les quantificateurs se distribuent sur les connecteurs logiques de la manière suivante :
1. Le quantificateur universel se distribue sur la conjonction (le « et ») : \[ \forall x \in E,\, (P\{x\} \land Q\{x\}) \iff (\forall x \in E,\, P\{x\}) \land (\forall x \in E,\, Q\{x\}). \]
2. Le quantificateur existentiel se distribue sur la disjonction (le « ou ») : \[ \exists x \in E,\, (P\{x\} \lor Q\{x\}) \iff (\exists x \in E,\, P\{x\}) \lor (\exists x \in E,\, Q\{x\}). \]
(Implications simples (Pièges fréquents))
Soit $E$ un ensemble et soient $P\{x\}$ et $Q\{x\}$ deux assertions qui dépendent de $x \in E$. Il est important de noter que la distributivité ne fonctionne pas toujours dans les deux sens. On a seulement des implications simples dans ce sens (la réciproque est fausse en général) :
1. L'existence d'un élément vérifiant $P$ et $Q$ implique qu'il existe un élément vérifiant $P$ et un (autre potentiellement) vérifiant $Q$ : \[ \exists x \in E,\, (P\{x\} \land Q\{x\}) \implies (\exists x \in E,\, P\{x\}) \land (\exists x \in E,\, Q\{x\}). \]
2. Le fait que $P$ soit vraie pour tout $x \in E$ ou que $Q$ soit vraie pour tout $x \in E$ implique que pour tout $x \in E$, $P$ ou $Q$ est vraie : \[ (\forall x \in E,\, P\{x\}) \lor (\forall x \in E,\, Q\{x\}) \implies \forall x \in E,\, (P\{x\} \lor Q\{x\}). \]
(Contre-exemple pour la réciproque du ii)) Soient les assertions : \[ P\left(n\right) : \text{\og $n$ est un entier pair \fg} \quad \text{et} \quad Q\left(n\right) : \text{\og $n$ est un entier impair \fg}. \] On a :
- $\exists n \in \mathbb{N},\, P\left(n\right)$ est vraie (pour $n = 2$).
- $\exists n \in \mathbb{N},\, Q\left(n\right)$ est vraie (pour $n = 3$).
- Mais $\exists n \in \mathbb{N},\, (P\left(n\right) \land Q\left(n\right))$ est fausse car un nombre ne peut être pair et impair simultanément.
Cette situation illustre que même si $P$ est vérifiée pour au moins un élément de $E$ et que $Q$ est vérifiée pour au moins un élément de $E$, il n'est pas nécessairement vrai qu'il existe un élément de $E$ qui vérifie à la fois $P$ et $Q$. C'est pourquoi la réciproque de l'implication du ii) est fausse en général.
(Permutation des quantificateurs)
Soient $E$ et $F$ deux ensembles et $P\{x; y\}$ une assertion qui dépend de deux variables $x \in E$ et $y \in F$.
1. Si deux quantificateurs successifs sont de même nature, on peut intervertir leur ordre sans changer la valeur de vérité de l'assertion : \[ \forall x \in E,\, \forall y \in F,\, P\{x; y\} \iff \forall y \in F,\, \forall x \in E,\, P\{x; y\} \]
  et
  \[ \exists x \in E,\, \exists y \in F,\, P\{x; y\} \iff \exists y \in F,\, \exists x \in E,\, P\{x; y\}. \]
2. Si deux quantificateurs successifs sont de nature différente, l'ordre est essentiel et ne peut pas être interverti (la réciproque est fausse en général) : \[ \exists x \in E,\, \forall y \in F,\, P\{x; y\} \implies \forall y \in F,\, \exists x \in E,\, P\{x; y\}. \] Explication : La réciproque est fausse. L'assertion « Il existe un $x \in E$ qui marche pour tous les $y \in F$ » est beaucoup plus forte que « Pour chaque $y \in F$, il existe un $x \in E$ (qui peut dépendre de $y$) ».
(Négation des quantificateurs imbriqués)
La négation d'une assertion avec plusieurs quantificateurs s'obtient en :
1. Niant l'assertion principale
2. Remplaçant chaque $\forall$ par $\exists$ et chaque $\exists$ par $\forall$
Exemples :
- $\lnot(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, y \leq x) \iff \exists x \in \mathbb{R}, \forall y \in \mathbb{R}, y > x$
- $\lnot(\exists x \in \mathbb{R}, \forall y \in \mathbb{R}, y \leq x) \iff \forall x \in \mathbb{R}, \exists y \in \mathbb{R}, y > x$
L'assertion $\exists x \in \mathbb{R}, \forall y \in \mathbb{R}, y \leq x$ est fausse car il n'existe aucun nombre réel plus grand que tous les autres. Sa négation $\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, y > x$ est vraie : pour tout réel $x$, on peut prendre $y = x + 1$, alors $y > x$.
Démonstration par récurrence
(Principe de récurrence)
Soit $n_0$ un entier naturel et soit $P\left(n\right)$ une assertion qui dépend d'un entier $n \geq n_0$. Pour démontrer que $P\left(n\right)$ est vraie pour tout $n \geq n_0$, on procède en deux étapes :
1. Initialisation : On vérifie que $P\left(n_0\right)$ est vraie.
2. Hérédité : On suppose que $P\left(n\right)$ est vraie pour un entier $n \geq n_0$ fixé (hypothèse de récurrence), et on démontre que $P\left(n+1\right)$ est vraie.
Si ces deux étapes sont vérifiées, alors $P\left(n\right)$ est vraie pour tout entier $n \geq n_0$.
(Somme des $n$ premiers entiers) Montrons par récurrence que pour tout entier $n \geq 1$ : \[ \sum_{k=1}^{n} k = 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}. \] Soit $P\left(n\right)$ l'assertion : $\displaystyle \sum_{k=1}^{n} k = \frac{n(n+1)}{2}$. Initialisation ($n = 1$) : \[ \sum_{k=1}^{1} k = 1 \quad \text{et} \quad \frac{1(1+1)}{2} = \frac{2}{2} = 1. \] Donc $P\left(1\right)$ est vraie. Hérédité : Supposons que $P\left(n\right)$ soit vraie pour un entier $n \geq 1$ fixé, c'est-à-dire : \[ \,\sum_{k=1}^{n} k = \frac{n(n+1)}{2}. \quad \text{(hypothèse de récurrence)} \] Montrons que $P\left(n+1\right)$ est vraie, c'est-à-dire : \[ \sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}. \] On a : $$\begin{align*} \, & & \sum_{k=1}^{n+1} k & = \sum_{k=1}^{n} k + (n+1) \\ & & & = \frac{n(n+1)}{2} + (n+1) & & \text{(d'après l'hypothèse de récurrence)} \\ & & & = \frac{n(n+1)}{2} + \frac{2(n+1)}{2} \\ & & & = \frac{n(n+1) + 2(n+1)}{2} \\ & & & = \frac{(n+1)(n+2)}{2}. \end{align*}$$ Donc $P\left(n+1\right)$ est vraie. Conclusion : Par le principe de récurrence, $P\left(n\right)$ est vraie pour tout entier $n \geq 1$.

~ Démontrer par récurrence que pour tous réels $a, b$ et tout entier $n \in \mathbb{N}$ : \[ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k} \] où $\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}$ sont les coefficients binomiaux. Indication : Utiliser la relation de Pascal $\displaystyle \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$.

Soient $a, b \in \mathbb{R}$. On note $P(n)$ la propriété : \[ (a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}. \] Initialisation ($n = 0$) : \[ (a + b)^0 = 1 \quad \text{et} \quad \sum_{k=0}^{0} \binom{0}{k} a^k b^{0-k} = \binom{0}{0} a^0 b^0 = 1. \] Donc $P(0)$ est vraie. Hérédité : Supposons que $P(n)$ soit vraie pour un entier $n \geq 0$ fixé. Montrons que $P(n+1)$ est vraie. On a : $$\begin{align*} (a + b)^{n+1} & = (a + b)(a + b)^n \\ & = (a + b) \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k} & & \text{(par hypothèse de récurrence)} \\ & = \sum_{k=0}^{n} \binom{n}{k} a^{k+1} b^{n-k} + \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k+1}. \end{align*}$$ Dans la première somme, on effectue le changement d'indice $j = k+1$ (donc $k = j-1$) : \[ \sum_{k=0}^{n} \binom{n}{k} a^{k+1} b^{n-k} = \sum_{j=1}^{n+1} \binom{n}{j-1} a^j b^{n+1-j}. \] Dans la deuxième somme, on pose $j = k$ : \[ \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k+1} = \sum_{j=0}^{n} \binom{n}{j} a^j b^{n+1-j}. \] Donc : $$\begin{align*} (a + b)^{n+1} & = \sum_{j=1}^{n+1} \binom{n}{j-1} a^j b^{n+1-j} + \sum_{j=0}^{n} \binom{n}{j} a^j b^{n+1-j} \\ & = \binom{n}{n} a^{n+1} b^0 + \sum_{j=1}^{n} \binom{n}{j-1} a^j b^{n+1-j} + \binom{n}{0} a^0 b^{n+1} + \sum_{j=1}^{n} \binom{n}{j} a^j b^{n+1-j} \\ & = a^{n+1} + b^{n+1} + \sum_{j=1}^{n} \left( \binom{n}{j-1} + \binom{n}{j} \right) a^j b^{n+1-j}. \end{align*}$$ D'après la relation de Pascal, $\displaystyle \binom{n}{j-1} + \binom{n}{j} = \binom{n+1}{j}$. Donc : $$\begin{align*} (a + b)^{n+1} & = a^{n+1} + b^{n+1} + \sum_{j=1}^{n} \binom{n+1}{j} a^j b^{n+1-j} \\ & = \binom{n+1}{n+1} a^{n+1} b^0 + \binom{n+1}{0} a^0 b^{n+1} + \sum_{j=1}^{n} \binom{n+1}{j} a^j b^{n+1-j} \\ & = \sum_{j=0}^{n+1} \binom{n+1}{j} a^j b^{n+1-j}. \end{align*}$$ Ainsi, $P(n+1)$ est vraie. Conclusion : Par récurrence, $P(n)$ est vraie pour tout $n \in \mathbb{N}$.

Les ensembles

Pour aller plus loin sur les fondements logiques, on pourra consulter sur internet la théorie axiomatique des ensembles de Zermelo-Fraenkel (en particulier l'axiome du choix).

Notion d'ensemble
(Ensemble, élément et appartenance)

On appelle {ensemble}, intuitivement, une collection d'objets bien définis, appelés les {éléments} de l'ensemble. Si un objet nommé $x$ est un élément de l'ensemble $X$, on note : \[ \, x \ {\color{red}\in} \ X \quad \text{(on lit « $x$ \textbf{\emph{{\color{red}appartient}}} à $X$ »)}. \] Dans le cas contraire, on note : \[ \, {\color{red}\lnot}\left(x \ {\color{red}\in} \ X\right) \iff x \ {\color{red}\notin} \ X \quad \text{(on lit « $x$ \textbf{\emph{{\color{red}n'appartient pas}}} à $X$ »)}. \]
- $\mathbb{N}$ désigne l'ensemble des entiers naturels. On a $3 \in \mathbb{N}$ mais $\sqrt{2} \notin \mathbb{N}$.
- L'ensemble des lettres du mot « algèbre » peut se noter $L = \{\text{a, l, g, è, b, r, e}\}$.
(Cardinal, ensemble fini et ensemble vide)
Un ensemble $X$ est dit {fini} s'il contient un nombre entier naturel {$n$} d'éléments, et on appelle ce nombre le {cardinal} de $X$, noté {$\mathrm{card}(X)$} ou {$|X|$}.
- Si $\mathrm{card}(X) =|X| = n$, on peut énumérer ses éléments (notation {en extension}) : $X = \{x_1, x_2, \dots, x_n\}$.
- Si $\mathrm{card}(X) = |X| = 1$, on dit que $X$ est un {singleton}. On le note alors $X = \{a\}$ pour un certain élément $a$, et on a bien $a \in X$ c'est-à-dire que $a \in \{a\}$. Mais l'écriture $a \subset \{a\}$ est incorrecte, car $a$ n'est pas un ensemble et ne peut donc pas être inclus dans un autre ensemble. Il est important de ne pas confondre $a$ et $\{a\}$ : $a$ est un élément, tandis que $\{a\}$ est un ensemble qui contient cet élément.
- L'ensemble des solutions réelles de $x^2 - 2x + 1 = 0$ est $\mathscr{S} = \{1\}$. C'est un singleton.
- On peut généraliser cette écriture à des ensembles infinis : $\mathbb{N} = \{0, 1, 2, 3, \dots\}$ est un ensemble infini. $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ est un autre ensemble infini. $\mathbb{R}$ est problématique pour être écrit en extension.
- L'ensemble des entiers $n \in \mathbb{N}$ vérifiant $n^2 < 0$ n'a aucun élément, donc il s'agit d'un ensemble sans élément.
(Axiome de l'ensemble vide)

Il existe un unique ensemble de cardinal nul, appelé {ensemble vide}, noté $\emptyset$. Par convention, \[ \mathrm{card}(\emptyset) = 0 \quad \text{et} \quad \forall x,\, x \notin \emptyset. \]

(Notation en compréhension)

Lorsqu'un ensemble est défini par une propriété vérifiée par ses éléments, on utilise la notation {en compréhension} : \[ X = \left\{x \in E ~\middle|~ P(x)\right\} \] où $E$ est un ensemble de référence et $P(x)$ est une assertion dépendant de $x$. Cette notation désigne l'ensemble de tous les éléments $x$ de $E$ qui vérifient la propriété $P(x)$. La barre verticale « $|$ » se lit « tel que » ou « vérifiant ».
- Par exemple, $A = \left\{x \in \mathbb{R} ~\middle|~ x^2 = 4\right\}$ désigne l'ensemble des nombres réels $x$ tels que $x^2 = 4$, c'est-à-dire $\{-2; 2\}$. $A = \left\{x \in \mathbb{R} ~\middle|~ x^2 = 4\right\} = \left\{-2; 2\right\}$.
- $B = \left\{n \in \mathbb{N} ~\middle|~ n \text{ est pair}\right\} = \left\{0; 2; 4; \dots\right\}$.
- $\mathbb{Q} = \left\{\frac{p}{q} ~\middle|~ p \in \mathbb{Z}, q \in \mathbb{N}^* \right\}$ est l'ensemble des nombres rationnels.
- $X = \left\{x \in \mathbb{R} ~\middle|~ x^2 -2x + 1 = 0\right\} = \left\{1\right\}$.
Partie d'un ensemble
(Axiome d'extensionnalité)

Deux ensembles sont égaux si et seulement s'ils ont les mêmes éléments : \[ X = Y \iff \left(\forall x,\, x \in X \iff x \in Y\right). \]

(Sous-ensemble (partie))

Soient $X$ et $Y$ deux ensembles. On dit que $X$ est une {partie} (ou {sous-ensemble}) de $Y$, et on note {$X \subset Y$}, si tout élément de $X$ est aussi élément de $Y$ : \[ X \subset Y \iff \forall x \in X,\, x \in Y. \]

[Figure TikZ non convertie automatiquement — à reprendre à la main]

(Propriétés élémentaires de l'inclusion)
Soit $X$ un ensemble. On a :
1. $\emptyset \subset X$ (l'ensemble vide est inclus dans tout ensemble).
2. $X \subset X$ (tout ensemble est inclus dans lui-même, c'est la réflexivité).
Preuve du i) : Montrons que $\emptyset \subset X$. Par définition, il faut vérifier que pour tout élément $x$, si $x \in \emptyset$, alors $x \in X$. L'assertion "$x \in \emptyset$" est toujours fausse car l'ensemble vide ne contient aucun élément. Donc il n'est pas possible de trouver un élément $x \in \emptyset$ tel que $x \notin X$. Donc, $\emptyset \subset X$. Preuve du ii) : Montrons que $X \subset X$. Par définition, il faut vérifier que pour tout $x \in X$, on a $x \in X$. C'est une évidence (réflexivité de l'égalité). Donc l'inclusion est vraie.

(Caractérisation de l'égalité ensembliste)

Soient $X$ et $Y$ deux ensembles. On a : \[ (X = Y) \iff (X \subset Y \text{ et } Y \subset X). \]

C'est la définition même de l'égalité ensembliste (principe d'extensionnalité ). Deux ensembles sont égaux si et seulement s'ils contiennent exactement les mêmes éléments, ce qui revient à dire que chacun est inclus dans l'autre.

(Transitivité de l'inclusion)

Soient $X$, $Y$ et $Z$ trois ensembles. On a : \[ (X \subset Y \text{ et } Y \subset Z) \implies (X \subset Z). \]
Supposons que $X \subset Y$ et $Y \subset Z$. Soit $x \in X$.
- Comme $X \subset Y$, on a $x \in Y$.
- Comme $Y \subset Z$, on a $x \in Z$.
Ainsi, tout élément de $X$ appartient à $Z$, donc $X \subset Z$.
$(\mathbb{N} \subset \mathbb{Q}$ et $\mathbb{Q} \subset \mathbb{R}) \implies (\mathbb{N} \subset \mathbb{R})$.

(Ensemble des parties)

Soit $X$ un ensemble. Il existe un unique ensemble que l'on note {$\mathcal{P}(X)$} constitué de tous les sous-ensembles de $X$. On appelle {$\mathcal{P}(X)$} l'{ensemble des parties de $X$}, autrement dit : \[ \mathcal{P}(X) = \left\{Y ~\middle|~ Y \subset X\right\}. \] {\warning}{\warning}{\warning} Un élément de $\mathcal{P}(X)$ est un sous-ensemble de $X$. {\warning}{\warning}{\warning} Pour dire que $Y \subset X$ on peut écrire : $Y \in \mathcal{P}(X)$. Par contre, si on écrit $Q \subset \mathcal{P}(X)$, on veut dire que $Q$ est un ensemble constitué de parties de $X$.

$\emptyset \in \mathcal{P}(X)$ et $X \in \mathcal{P}(X)$ (car $X \subset X$). $\left\{\emptyset ; X\right\} \subset \mathcal{P}(X)$.
Opérations ensemblistes
(Intersection de deux ensembles)

Soient $X$ et $Y$ deux ensembles. On appelle {intersection de $X$ et $Y$} l'ensemble noté {$X \cap Y$} (« $X$ inter $Y$ »{}) constitué des éléments qui appartiennent à la fois à $X$ et à $Y$. Autrement dit : \[ x \in X \cap Y \iff x \in X \land x \in Y \] Shématiquement, $X \cap Y$ correspond à la partie commune aux deux ensembles $X$ et $Y$ :

[Figure TikZ non convertie automatiquement — à reprendre à la main]

(Ensembles disjoints)

Deux ensembles $X$ et $Y$ sont dits {disjoints} si leur intersection est vide, c'est-à-dire si : \[ X \cap Y = \emptyset. \] Cela signifie qu'ils n'ont aucun élément en commun.

[Figure TikZ non convertie automatiquement — à reprendre à la main]

(Inclusions triviales de l'intersection)

Soient $X$ et $Y$ deux ensembles. L'intersection de deux ensembles est toujours incluse dans chacun d'eux : \[ X \cap Y \subset X \quad \text{et} \quad X \cap Y \subset Y. \]

Soit $x \in X \cap Y$. $$\begin{align*} \, & & x \in X \cap Y & \implies x \in X \land x \in Y & & (\text{car } ) \\ & & & \implies x \in X & & (\text{car } ) \end{align*}$$ Ce qui prouve que $X \cap Y \subset X$. \columnbreak Soit $x \in X \cap Y$. $$\begin{align*} \, & & x \in X \cap Y & \implies x \in X \land x \in Y & & (\text{car } ) \\ & & & \implies x \in Y & & (\text{car } ) \end{align*}$$ Ce qui prouve que $X \cap Y \subset Y$.

(Idempotence de l'intersection)

Soit $X$ un ensemble. L'intersection d'un ensemble avec lui-même est l'ensemble lui-même : \[ X \cap X = X. \]
Montrons $X \cap X = X$ par double inclusion.
- [\fbox{$\subset$}] Soit $x \in X \cap X$, $$\begin{align*} x \in X \cap X & \implies x \in X \land x \in X & & (\text{car } ) \\ & \implies x \in X & & (\text{car } ) \end{align*}$$ Ainsi {$X \cap X \subset X$}.
- [\fbox{$\supset$}] Soit $x \in X$, $$\begin{align*} x \in X & \implies x \in X \land x \in X & & (\text{car } ) \\ & \implies x \in X \cap X & & (\text{car } ) \end{align*}$$ Ainsi {$X \subset X \cap X $}.
On conclut en faisant la synthèse des deux résultats : $X \subset X \cap X \subset X$. D'où l'égalité $X = X \cap X$.
(Commutativité de l'intersection)

Soient $X$ et $Y$ deux ensembles. Alors : \[ X \cap Y = Y \cap X. \]

Montrons $X \cap Y = Y \cap X$ par double inclusion.
\fbox{$\subset$} Soit $x\in X \cap Y$, $$\begin{align*} x \in X \cap Y & \implies x \in X \land x \in Y & & (\text{car } ) \\ & \implies x \in Y \land x \in X & & (\text{car } ) \\ & \implies x \in Y \cap X & & (\text{car } ) \end{align*}$$ Donc $X \cap Y \subset Y \cap X$. \columnbreak \fbox{$\supset$} Soit $x\in Y \cap X$, $$\begin{align*} x \in Y \cap X & \implies x \in Y \land x \in X & & (\text{car } ) \\ & \implies x \in X \land x \in Y & & (\text{car } ) \\ & \implies x \in X \cap Y & & (\text{car } ) \end{align*}$$ Donc $Y \cap X \subset X \cap Y$.
Donc $X \cap Y \subset Y \cap X \subset X \cap Y$. D'où l'égalité $X \cap Y = Y \cap X$.

(Associativité de l'intersection)

Soient $X$, $Y$ et $Z$ trois ensembles. Alors : \[ (X \cap Y) \cap Z = X \cap (Y \cap Z). \]

Soit $x \in (X \cap Y) \cap Z$. Par définition, cela signifie $x \in X \cap Y$ et $x \in Z$, soit $(x \in X \land x \in Y) \land x \in Z$. Par associativité du connecteur logique $\land$, on a $(x \in X \land x \in Y) \land x \in Z \iff x \in X \land (x \in Y \land x \in Z)$. Ceci équivaut à $x \in X \cap (Y \cap Z)$. Les deux ensembles contiennent donc exactement les mêmes éléments, d'où l'égalité. La preuve peut être écrite de manière plus formelle de la manière suivante : $$\begin{align*} \, & & x \in (X \cap Y) \cap Z & \iff x \in X \cap Y \land x \in Z & & (\text{car } ) \\ & & & \iff (x \in X \land x \in Y) \land x \in Z & & (\text{car } ) \\ & & & \iff x \in X \land (x \in Y \land x \in Z) & & (\text{car } ) \\ & & & \iff x \in X \land (x \in Y \cap Z) & & (\text{car } ) \\ & & & \iff x \in X \cap (Y \cap Z) & & (\text{car } ) \end{align*}$$ En conclusion, $(X \cap Y) \cap Z = X \cap (Y \cap Z)$.

(Élément absorbant pour l'intersection)

Soit $X$ un ensemble. L'ensemble vide est {absorbant} pour l'intersection : \[ X \cap \emptyset = \emptyset. \]
- [\fbox{$\subset$}] D'après la propriété « inclusions triviales de l'intersection »{} , $X \cap \emptyset \subset \emptyset$.
- [\fbox{$\supset$}] D'après les « propriétés élémentaires de l'inclusion »{} , l'ensemble vide est inclus dans tout ensemble, donc $\emptyset \subset X \cap \emptyset$.
Conclusion : $X \cap \emptyset \subset \emptyset \subset X \cap \emptyset$ Par double inclusion, on a donc $X \cap \emptyset = \emptyset$.
(Union de deux ensembles)

Soient $X$ et $Y$ deux ensembles. On appelle {union de $X$ et $Y$} l'ensemble noté {$X \cup Y$} (« $X$ union $Y$ »{}) constitué des éléments de $X$ et de $Y$ : \[ X \cup Y = \left\{x ~\middle|~ x \in X \lor x \in Y\right\} \] Autrement dit : \[ x \in X \cup Y \iff x \in X \lor x \in Y. \] Schématiquement, $X \cup Y$ correspond à la réunion des deux ensembles $X$ et $Y$ :

[Figure TikZ non convertie automatiquement — à reprendre à la main]

(Inclusions triviales de l'union)

Soient $X$ et $Y$ deux ensembles. Chaque ensemble est inclus dans leur union : \[ X \subset X \cup Y \quad \text{et} \quad Y \subset X \cup Y \]

Soit $x \in X$. $$\begin{align*} \, & & x \in X & \implies x \in X \lor x \in Y & & (\text{car } ) \\ & & & \implies x \in X \cup Y & & (\text{car } ) \end{align*}$$ Ce qui prouve que $X \subset X \cup Y$. \columnbreak Soit $x \in Y$. $$\begin{align*} \, & & x \in Y & \implies x \in X \lor x \in Y & & (\text{car } ) \\ & & & \implies x \in X \cup Y & & (\text{car } ) \end{align*}$$ Ce qui prouve que $Y \subset X \cup Y$.

(Idempotence de l'union)

Soit $X$ un ensemble. L'union d'un ensemble avec lui-même est l'ensemble lui-même : \[ X \cup X = X \]
Montrons $X \cup X = X$ par double inclusion.
- [\fbox{$\subset$}] Soit $x \in X \cup X$, $$\begin{align*} x \in X \cup X & \implies x \in X \lor x \in X & & (\text{car } ) \\ & \implies x \in X & & (\text{car } ) \end{align*}$$ Ainsi {$X \cup X \subset X$}.
- [\fbox{$\supset$}] Soit $x \in X$, $$\begin{align*} x \in X & \implies x \in X \lor x \in X & & (\text{car } \text{ ou car } ) \\ & \implies x \in X \cup X & & (\text{car } ) \end{align*}$$ Ainsi {$X \subset X \cup X$}.
On conclut en faisant la synthèse des deux résultats : $X \subset X \cup X \subset X$. D'où l'égalité $X = X \cup X$.
(Commutativité de l'union)

Soient $X$ et $Y$ deux ensembles. Alors : \[ X \cup Y = Y \cup X. \]

Montrons $X \cup Y = Y \cup X$ par double inclusion.
\fbox{$\subset$} Soit $x \in X \cup Y$, $$\begin{align*} x \in X \cup Y & \implies x \in X \lor x \in Y & & (\text{car } ) \\ & \implies x \in Y \lor x \in X & & (\text{car } ) \\ & \implies x \in Y \cup X & & (\text{car } ) \end{align*}$$ Donc $X \cup Y \subset Y \cup X$. \columnbreak \fbox{$\supset$} Soit $x \in Y \cup X$, $$\begin{align*} x \in Y \cup X & \implies x \in Y \lor x \in X & & (\text{car } ) \\ & \implies x \in X \lor x \in Y & & (\text{car } ) \\ & \implies x \in X \cup Y & & (\text{car } ) \end{align*}$$ Donc $Y \cup X \subset X \cup Y$.
Donc $X \cup Y \subset Y \cup X \subset X \cup Y$. D'où l'égalité $X \cup Y = Y \cup X$.

(Associativité de l'union)

Soient $X$, $Y$ et $Z$ trois ensembles. Alors : \[ (X \cup Y) \cup Z = X \cup (Y \cup Z) \]

Soit $x \in (X \cup Y) \cup Z$. Par définition, cela signifie $x \in X \cup Y$ ou $x \in Z$, soit $(x \in X \lor x \in Y) \lor x \in Z$. Par associativité du connecteur logique $\lor$, on a $(x \in X \lor x \in Y) \lor x \in Z \iff x \in X \lor (x \in Y \lor x \in Z)$. Ceci équivaut à $x \in X \cup (Y \cup Z)$. Les deux ensembles contiennent donc exactement les mêmes éléments, d'où l'égalité. La preuve peut être écrite de manière plus formelle de la manière suivante : $$\begin{align*} \, & & x \in (X \cup Y) \cup Z & \iff x \in X \cup Y \lor x \in Z & & (\text{car } ) \\ & & & \iff (x \in X \lor x \in Y) \lor x \in Z & & (\text{car } ) \\ & & & \iff x \in X \lor (x \in Y \lor x \in Z) & & (\text{car } ) \\ & & & \iff x \in X \lor x \in Y \cup Z & & (\text{car } ) \\ & & & \iff x \in X \cup (Y \cup Z) & & (\text{car } ) \end{align*}$$ En conclusion, $(X \cup Y) \cup Z = X \cup (Y \cup Z)$.

(Élément neutre pour l'union)

Soit $X$ un ensemble. L'ensemble vide est {neutre} pour l'union : \[ X \cup \emptyset = X. \]
Montrons $X \cup \emptyset = X$ par double inclusion.
- [\fbox{$\subset$}] Soit $x \in X \cup \emptyset$. $$\begin{align*} & & x \in X \cup \emptyset & \implies x \in X \lor x \in \emptyset & & (\text{car } ) \\ \, & & & \implies x \in X & & (\text{car } : x \in \emptyset \text{ est toujours fausse}) \end{align*}$$ Ainsi {$X \cup \emptyset \subset X$}.
- [\fbox{$\supset$}] Soit $x \in X$. $$\begin{align*} \, & & x \in X & \implies x \in X \lor x \in \emptyset & & (\text{car } ) \\ & & & \implies x \in X \cup \emptyset & & (\text{car } ) \end{align*}$$ Ainsi {$X \subset X \cup \emptyset$}.
On conclut en faisant la synthèse des deux résultats : $X \cup \emptyset \subset X \subset X \cup \emptyset$. D'où l'égalité $X \cup \emptyset = X$.
(Caractérisation de l'inclusion par l'union)

Soient $X$ et $Y$ deux ensembles. On a l'équivalence : \[ X \subset Y \iff X \cup Y = Y. \]
Preuve du sens direct ($\Rightarrow$) : Supposons $X \subset Y$. Montrons $X \cup Y = Y$ par double inclusion.
- [\fbox{$\subset$}] Soit $x \in X \cup Y$. Alors $x \in X$ ou $x \in Y$. Si $x \in X$, alors $x \in Y$ (car c'est l'hypothèse de départ : $X \subset Y$). Donc dans les deux cas de la disjonction, $x \in Y$. Ainsi {$X \cup Y \subset Y$}.
- [\fbox{$\supset$}] D'après les « inclusions triviales de l'union »{} , on a toujours {$Y \subset X \cup Y$}.
On conclut que $X \cup Y \subset Y \subset X \cup Y$, d'où l'égalité $X \cup Y = Y$. Preuve de la réciproque ($\Leftarrow$) : Supposons $X \cup Y = Y$. Montrons $X \subset Y$.
- [\fbox{$\subset$}] D'après les « inclusions triviales de l'union »{} , on a toujours $X \subset X \cup Y$.
- [] Comme $X \cup Y = Y$ par hypothèse, on en déduit par substitution que $X \subset Y$. Ainsi {$X \subset Y$}.
Les deux implications étant établies, l'équivalence est démontrée.
(Distributivité de l'union sur l'intersection)

Soient $X$, $Y$ et $Z$ trois ensembles. On a : \[ X \cup (Y \cap Z) = (X \cup Y) \cap (X \cup Z). \]

Montrons l'égalité par équivalence logique. $$\begin{align*} \, & & x \in X \cup (Y \cap Z) & \iff x \in X \lor x \in Y \cap Z & & (\text{car } ) \\ & & & \iff x \in X \lor (x \in Y \land x \in Z) & & (\text{car } ) \\ & & & \iff (x \in X \lor x \in Y) \land (x \in X \lor x \in Z) & & (\text{car } ) \\ & & & \iff x \in X \cup Y \land x \in X \cup Z & & (\text{car }) \\ & & & \iff x \in (X \cup Y) \cap (X \cup Z). & & (\text{car }) \end{align*}$$ Les deux ensembles contiennent exactement les mêmes éléments, d'où l'égalité.

(Distributivité de l'intersection sur l'union)

Soient $X$, $Y$ et $Z$ trois ensembles. On a : \[ X \cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z). \]

Montrons l'égalité par équivalence logique. $$\begin{align*} \, & & x \in X \cap (Y \cup Z) & \iff x \in X \land x \in Y \cup Z & & (\text{car } ) \\ & & & \iff x \in X \land (x \in Y \lor x \in Z) & & (\text{car } ) \\ & & & \iff (x \in X \land x \in Y) \lor (x \in X \land x \in Z) & & (\text{car } ) \\ & & & \iff x \in X \cap Y \lor x \in X \cap Z & & (\text{car } ) \\ & & & \iff x \in (X \cap Y) \cup (X \cap Z). & & (\text{car } ) \end{align*}$$ Les deux ensembles contiennent exactement les mêmes éléments, d'où l'égalité.

Différences ensemblistes

(Différence entre deux ensembles)

Soient $X$ et $Y$ deux ensembles. On appelle {différence de $X$ par $Y$ }l'ensemble noté {$X \setminus Y$} (« $X$ privé de $Y$ »{}) constitué des éléments qui sont dans $X$ et qui ne sont pas dans $Y$ : \[ X \setminus Y = \{x \in X \mid x \notin Y\}. \]

[Figure TikZ non convertie automatiquement — à reprendre à la main]

(Propriétés de la différence)
Soient $X$, $Y$ et $Z$ des ensembles :
1. $X \setminus \emptyset = X$
2. $X \setminus X = \emptyset$
3. $(X \cup Y) \setminus Z = (X \setminus Z) \cup (Y \setminus Z)$
4. $(X \cap Y) \setminus Z = (X \setminus Z) \cap (Y \setminus Z)$
5. $X \setminus (Y \cap Z) = (X \setminus Y) \cup (X \setminus Z)$
Supposons maintenant que $Y$ est une partie de $X$ (i.e. $Y \in \mathcal{P}(X)$) $\iff Y \subset X$.
(Complémentaire d'un ensemble dans un autre)

Pour $Y \subset X$, on définit le {complémentaire de $Y$ dans $X$} comme étant l'ensemble noté {$\complement_X Y$} et défini par : \[ \complement_X Y = \left\{x \in X ~\middle|~ x \notin Y\right\} = X \setminus Y. \]

[Figure TikZ non convertie automatiquement — à reprendre à la main]

(Propriétés du complémentaire (Lois de De Morgan))
1. $\complement_X \emptyset = X$
2. $\complement_X X = \emptyset$
3. $\complement_X\left(\complement_X Y\right) = Y$
4. $\complement_X Y \cap Y = \emptyset$
5. $Y \cup \complement_X Y = X$
6. $\complement_X\left(Y \cap Z\right) = \left(\complement_X Y\right) \cup \left(\complement_X Z\right)$
7. $\complement_X\left(Y \cup Z\right) = \left(\complement_X Y\right) \cap \left(\complement_X Z\right)$
Partition d'un ensemble

(Partition d'un ensemble)
Soit $X$ un ensemble (non vide) et $Q \subset \mathcal{P}(X)$ un ensemble de parties non vides de $X$. On dit que $Q$ est une {partition} de $X$ si :
1. Si $A, B \in Q$ sont deux éléments distincts de $Q$, alors elles sont disjointes, i.e. $A \cap B = \emptyset$, c'est-à-dire : \[ \forall A, B \in Q \text{ tels que } A \neq B \implies A \cap B = \emptyset. \]
2. $\forall x \in X,\, \exists A \in Q$ tel que $x \in A$, autrement dit « $Q$ recouvre $X$ »{} complètement.
Une manière équivalente de dire que $Q$ est une partition de $X$ : \[ \forall x \in X,\, \exists!\, A \in Q \text{ tel que } x \in A. \]
1. $\mathbb{N} = A \cup B$, $\{A, B\} \subset \mathcal{P}(\mathbb{N})$ avec $A = \{\text{nombres pairs}\}$, $B = \{\text{nombres impairs}\}$. (i) est vérifiée car $A \cap B = \emptyset$. (ii) est vérifiée car $\forall n \in \mathbb{N}$, $n \in A$ ou $n \in B$.
2. Soit $X$ un ensemble $\neq \emptyset$ et soit $A \subset X$, alors $\{A, C_X A\}$ est une partition de $X$. (i) est vérifiée car $A \cap C_X A = \emptyset$. (ii) est vérifiée car $\forall x \in X$, $x \in A$ ou $x \notin A$, i.e. $x \in A$ ou $x \in C_X A$.
Produits cartésiens
Soient $X$, $Y$ deux ensembles.
(Produit cartésien)

Le {produit cartésien} de $X$ et $Y$ est l'ensemble, noté $X \times Y$, défini par : \[ X \times Y = \{(x; y) \mid x \in X,\, y \in Y\}. \] On dit que $(x; y)$ est le couple constitué des éléments $x$ et $y$.

$(y; x) \notin X \times Y$ avec $y \in Y$ et $x \in X$. Ici $(y; x) \in Y \times X$. Exemple : $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$.
Schématiquement : Le produit cartésien $X \times Y$ se représente comme un rectangle dans le plan, dont les côtés sont $X$ (axe horizontal) et $Y$ (axe vertical). $(x; y)$ est un élément de $X \times Y$.

[Figure TikZ non convertie automatiquement — à reprendre à la main]

Notation : on note $X \times X = X^2$. $\mathbb{N}^2 \neq \{a^2 \mid a \in \mathbb{N}\}$, $\mathbb{N}^2 = \{(m; m) \mid m, m \in \mathbb{N}\}$.
(Propriétés du produit cartésien)
Soient $X$, $Y$, $Z$, $T$ quatre ensembles :
1. $X \times (Y \cup Z) = (X \times Y) \cup (X \times Z)$
2. $(X \cup Y) \times Z = (X \times Z) \cup (Y \times Z)$
3. $(X \cap Y) \times (Z \cap T) = (X \times Z) \cap (Y \times T)$
En exercice.
On peut généraliser cette construction dans le cas de $n$ ensembles, i.e. si $X_1, \ldots, X_n$ des ensembles non vides, alors : \[ X_1 \times \cdots \times X_n = \left\{\left(x_1;\, \ldots;\, x_n\right) ~\middle|~ x_1 \in X_1,\, \ldots,\, x_n \in X_n\right\} \]

Si $X_1 = X_2 = \cdots = X_n$, on note : \[ \underbrace{X \times X \times X \times \cdots \times X}_{n \text{ fois}} = X^n. \]

Relations

[$\rightarrow$] Relation d'équivalence (exemple : $\mathbb{Z} = \{\text{pairs}\} \cup \{\text{impairs}\}$, qui donne $\mathbb{Z}/2\mathbb{Z} = \{0; 1\}$).
[$\rightarrow$] Relation d'ordre (exemple : dans $\mathbb{R}$, on sait ordonner les réels : $-1 \leqslant 0 \leqslant \frac{1}{2} \leqslant \sqrt{2} \leqslant \pi \leqslant 7{,}8$).

Relation
Définition

(Relation)

On appelle {relation} ou {correspondance} {$\mathcal{R}$} tout triplet $(X, \Gamma, Y) = \mathcal{R}$ où $X$, $Y$ sont deux ensembles et $\Gamma$ est un sous-ensemble de $X \times Y$ (i.e. $\Gamma \subset X \times Y$). On dit que {$X$} est l'{ensemble de départ}. On dit que {$Y$} est l'{ensemble d'arrivée}. On dit que {$\Gamma$} le {graphe} de la relation. On dira que $\mathcal{R}$ est une relation de $X$ dans $Y$ si $(x; y)$ est un couple de $X \times Y$ qui vérifie $(x; y) \in \Gamma$.
Soient $X = \{a; b; c; d\}$, $Y = \{1; 2; 3\}$ et $\Gamma = \{(a; 3);(b; 1);(c; 2);(d; 3)\}$. $\Gamma \subset X \times Y$. Pour $\mathcal{R} = (X, \Gamma, Y)$ :
1. $a$ est en relation avec $3$ car $(a; 3) \in \Gamma$ ; ici on note $a\,\mathcal{R}\,3$.
2. $a$ n'est pas en relation avec $2$ car $(a; 2) \notin \Gamma$.
Relation binaire

(Relation binaire)

Une relation d'un ensemble dans lui-même s'appelle une {relation binaire}. Si $X$ est un ensemble, une relation binaire est la donnée d'un sous-ensemble : \[ \Gamma \subset X \times X. \] Dans ce cas, on note $(X, \mathcal{R})$ avec $\mathcal{R} = (X, \Gamma, X)$.
1. Si $X$ est un ensemble non vide, alors « être un sous-ensemble de »{} est une relation binaire : \[ \forall A, B \in \mathcal{P}(X),\quad A\,\mathcal{R}\,B \iff (A \subset B \text{ ou } B \subset A). \]
2. Sur $\mathbb{Z}$, on dit que $x\,\mathcal{R}\,y \iff x - y$ est divisible par $3$ : c'est une relation binaire sur $\mathbb{Z}$.
3. Soit $P$ le plan $\mathbb{R}^2$ et soit $D$ l'ensemble des droites de ce plan. Sur $D$, on peut définir pour $\Delta_1, \Delta_2 \in D$ :
  - $\Delta_1 \parallel \Delta_2 \iff \Delta_1$ est parallèle à $\Delta_2$
  - $\Delta_1 \perp \Delta_2 \iff \Delta_1$ est orthogonale à $\Delta_2$
\fbox{Dans toute la suite, on considère un ensemble $X$ muni d'une relation binaire $\mathcal{R}$.}
(Relation réflexive)

La relation $\mathcal{R}$ est {réflexive} si : \[ \forall x \in X,\quad x\,\mathcal{R}\,x. \]
1. On considère $(\mathcal{P}(X), \subset)$ : alors $A\,\mathcal{R}\,A$ car $A \subset A$. Donc l'inclusion est une relation réflexive.
2. Sur $\mathbb{Z}$ avec $x\,\mathcal{R}\,y \iff 3$ divise $(x; y)$ : Est-ce que $x\,\mathcal{R}\,x$, $\forall x \in \mathbb{Z}$ ? On a $x\,\mathcal{R}\,x \iff 3$ divise $x - x = 0$, vrai car $0 = 3 \times 0$.
3. Pour $D_1 \perp D_2$, la relation est fausse car une droite n'est pas orthogonale à elle-même. Pour $D_1 \parallel D_2$, la relation est vraie car toute droite est parallèle à elle-même.
(Relation symétrique)

On dit que $\mathcal{R}$ est une {relation symétrique} si : \[ \forall x, y \in X,\quad x\,\mathcal{R}\,y \implies y\,\mathcal{R}\,x. \]
1. Sur $\mathcal{P}(X)$ : $A\,\mathcal{R}\,B \iff (A \subset B)$. Si $(A\,\mathcal{R}\,B \implies B\,\mathcal{R}\,A) \iff (A \subset B \implies B \subset A)$. $\implies$ Relation non symétrique.
2. Sur $\mathbb{Z}$ : $x\,\mathcal{R}\,y \iff 3$ divise $(x - y)$. Alors $x\,\mathcal{R}\,y \implies y\,\mathcal{R}\,x$ ? \[ (3 \text{ divise } (x-y)) \stackrel{?}{\implies} 3 \text{ divise } (y - x) \] $\iff \exists k \in \mathbb{Z}$ t.q. $x - y = 3k \iff y - x = 3(-k)$, d'où $y - x$ est divisible par $3$ $\implies$ $y\,\mathcal{R}\,x$.
3. $\Delta_1 \perp \Delta_2 \implies \Delta_2 \perp \Delta_1$ : vrai. $\Delta_1 \parallel \Delta_2 \implies \Delta_2 \parallel \Delta_1$ : vrai.
4. Sur $\mathbb{R}$, on pose : $x\,\mathcal{R}\,y \iff x \leqslant y$. Cette relation n'est pas symétrique car $1\,\mathcal{R}\,2$ ($1 \leqslant 2$) mais $2\,\not{\mathcal{R}}\,1$ car $2 \leqslant 1$ est faux.
(Relation anti-symétrique)

On dit que $\mathcal{R}$ est {anti-symétrique} si : \[ \forall (x; y) \in X^2,\quad x\,\mathcal{R}\,y \text{ et } y\,\mathcal{R}\,x \implies x = y. \]
1. Sur $\mathcal{P}(X)$, $A\,\mathcal{R}\,B \iff A \subset B$ : \[ A\,\mathcal{R}\,B \implies A \subset B, \quad B\,\mathcal{R}\,A \implies B \subset A \Bigr\} A \subset B \subset A \implies A = B. \] Elle est donc anti-symétrique.
2. Sur $\mathbb{Z}$ : $x\,\mathcal{R}\,y \iff x - y$ est divisible par $3$. \[ x\,\mathcal{R}\,y \implies x - y = 3k \quad \text{et} \quad y\,\mathcal{R}\,x \implies -(y - x) = 3k' \] \[ x - y = 3k \quad \text{et} \quad x - y = 3(-k') \implies 3(k + k') = 0 \implies k' = -k. \] Trouver des éléments de $\mathbb{Z}$ t.q. $x\,\mathcal{R}\,y$ et $y\,\mathcal{R}\,x$ et $x \neq y$ :
  - $5\,\mathcal{R}\,2$ car $5 - 2 = 3$ donc $3 \mid 5 - 2$.
  - $2\,\mathcal{R}\,5$ car $2 - 5 = -3$ donc $3 \mid 2 - 5$.
  - Et pourtant $2 \neq 5$.
  Donc $\mathcal{R}$ n'est pas anti-symétrique.
(Relation transitive)

On dit que $\mathcal{R}$ est {transitive} si : \[ \forall (x; y; z) \in X^3,\quad x\,\mathcal{R}\,y ~\text{ et }~ y\,\mathcal{R}\,z \implies x\,\mathcal{R}\,z \]
1. Sur $(\mathcal{P}(X), \subset)$ : Soient $A, B, C \in \mathcal{P}(X)$ t.q. $A\,\mathcal{R}\,B$ et $B\,\mathcal{R}\,C$, $\iff A \subset B$ et $B \subset C$, $\implies A \subset C$, $\implies A\,\mathcal{R}\,C$. D'où $\mathcal{R}$ transitive.
2. Sur $\mathbb{Z}$, $x\,\mathcal{R}\,y \iff x - y$ est divisible par $3$ : \[ @@MATH30@@ \] $\implies x - y + y - z = 3(k_1 + k_2) \iff x - z = 3(k_1 + k_2) \iff x\,\mathcal{R}\,z$. $\implies \mathcal{R}$ est transitive.
3. $P$ est le plan $\mathbb{R}^2$, $D = \{\text{ensembles des droites de } P\}$, $\forall D_1, D_2 \in D$ : \[ D_1 \parallel D_2 \iff D_1 \text{ et } D_2 \text{ sont parallèles}, \quad D_1 \perp D_2 \iff D_1 \text{ et } D_2 \text{ sont orthogonales.} \] Si $D_1 \parallel D_2$ et $D_2 \parallel D_3 \implies D_1 \parallel D_3$ : vrai. Si $D_1 \perp D_2$ et $D_2 \perp D_3 \stackrel{?}{\implies} D_1 \perp D_3$ : Faux, donc $\perp$ n'est pas transitive.
Résumé : Soit $X$ un ensemble et $\mathcal{R}$ une relation binaire sur $X$.
1. $\mathcal{R}$ est {réflexive} $\iff \forall x \in X,\, x\,\mathcal{R}\,x$.
2. $\mathcal{R}$ est {symétrique} $\iff \forall (x; y) \in X^2,\, x\,\mathcal{R}\,y \implies y\,\mathcal{R}\,x$.
3. $\mathcal{R}$ est {anti-symétrique} $\iff \forall (x; y) \in X^2,\, x\,\mathcal{R}\,y \text{ et } y\,\mathcal{R}\,x \implies x = y$.
4. $\mathcal{R}$ est {transitive} $\iff \forall (x; y; z) \in X^3$, $x\,\mathcal{R}\,y$ et $y\,\mathcal{R}\,z \implies x\,\mathcal{R}\,z$.
Si $\mathcal{R}$ est symétrique et anti-symétrique : \[ \forall(x, y) \in X^2,\, x\,\mathcal{R}\,y \implies y\,\mathcal{R}\,x \implies x = y \quad \implies \quad \mathcal{R}\ \text{``} \iff \text{''} = \]
Relation d'équivalence
(Relation d'équivalence)
Soit $X$ un ensemble et soit $\mathcal{R}$ une relation binaire sur $X$. On dit que $\mathcal{R}$ est une {relation d'équivalence} si :
1. $\mathcal{R}$ est {réflexive} : $\forall x \in X,\, x\,\mathcal{R}\,x$.
2. $\mathcal{R}$ est {symétrique} : $\forall (x; y) \in X^2,\, x\,\mathcal{R}\,y \implies y\,\mathcal{R}\,x$.
3. $\mathcal{R}$ est {transitive} : $\forall (x; y; z) \in X^3$, $x\,\mathcal{R}\,y$ et $y\,\mathcal{R}\,z \implies x\,\mathcal{R}\,z$.
1. Sur $P$, la relation $D_1 \parallel D_2$ est une relation d'équivalence.
2. Sur $\mathbb{Z}$, la relation sur $\mathbb{Z}$ de congruence modulo $3$ est une relation d'équivalence.
3. La relation (sur $\mathcal{P}(X)$) d'inclusion n'est pas une relation d'équivalence car elle n'est pas symétrique.
Classe d'équivalence
Soit $\mathcal{R}$ une relation d'équivalence.
(Classe d'équivalence)

Soit $x \in X$, on appelle la {classe d'équivalence} de $x$ le sous-ensemble de $X$, notée {$[x]$} ou {$\dot{x}$} ou {$\overline{x}$} ou encore {$\operatorname{Cl}_{\mathcal{R}}(x)$}, et défini par : \[ \operatorname{Cl}_{\mathcal{R}}(x) = \dot{x} = \overline{x} = [x] = \left\{y \in X ~\middle|~ x\,\mathcal{R}\,y\right\} \]
- $[x] \subset X$.
- On a $[x] \neq \emptyset$ car $x\,\mathcal{R}\,x$ (par réflexivité de $\mathcal{R}$), $\implies x \in [x]$.
(Ensemble quotient)

L'ensemble des classes d'équivalence est appelé {ensemble quotient} de $X$ par la relation d'équivalence $\mathcal{R}$. On le note $\EnsembleQuotient{X}{\mathcal{R}}$ : \[ \EnsembleQuotient{X}{\mathcal{R}} = \left\{[x] ~\middle|~ x \in X\right\} \]
1. $\EnsembleQuotient{X}{\mathcal{R}} \subset \mathcal{P}(X)$.
2. L'ensemble quotient $\EnsembleQuotient{X}{\mathcal{R}}$ est un ensemble d'ensembles, c'est-à-dire un ensemble dont les éléments sont des ensembles.
3. La réunion de toutes les classes d'équivalence est égale à $X$. Les classes d'équivalence forment donc une partition de $X$.
Relation de congruence

(Congruence modulo $n$)

Soit $n \in \mathbb{N}^*$ et $(x; y) \in \mathbb{Z}^2$. On dit que $x$ est {congru} à $y$ modulo $n$ si $y - x$ est divisible par $n$. On notera $x \equiv y\, [n]$. \[ x \equiv y\, [n] \iff \exists k \in \mathbb{Z},\quad y - x = kn. \]

(La congruence modulo $n$ est une relation d'équivalence)

Pour $n \in \mathbb{N}^*$, la relation $\mathcal{R}$ notée aussi $\equiv_n$ qui est la relation de congruence modulo $n$ est une relation d'équivalence sur $\mathbb{Z}$.

$\rightarrow$ Réflexivité : $x\,\mathcal{R}\,x \iff x \equiv x\, [n]$. En effet, $x - x = 0 = 0 \times n$. $\rightarrow$ Symétrie : On suppose que $x\,\mathcal{R}\,y \iff x \equiv y\, [n] \implies \exists k \in \mathbb{Z},\, y - x = kn \iff \exists k \in \mathbb{Z},\, x - y = -kn$, avec $-k \in \mathbb{Z} \implies y \equiv x\, [n] \iff y\,\mathcal{R}\,x$. $\rightarrow$ Transitivité : \[ @@MATH31@@ \iff @@MATH32@@ \] $\implies z - x = k_1 n + k_2 n = n(k_1 + k_2) \iff z - x = nk_3$ (avec $k_3 \in \mathbb{Z}$) $\iff x \equiv z\, [n] \iff x\,\mathcal{R}\,z$. $\rightarrow$ Détermination de la classe de $x \in \mathbb{Z}$ : \[ [x] = \{y \in \mathbb{Z} \mid x \equiv y\, [n]\}. \] Or $x \equiv y\, [n] \iff \exists k \in \mathbb{Z},\, y - x = kn \implies y = x + kn$$\implies [x] = \{x + kn \mid k \in \mathbb{Z}\}$ Finalement, on note l'ensemble quotient $\EnsembleQuotient{\mathbb{Z}}{{\cdot\equiv}\cdot[n]}$ par $\mathbb{Z}/n\mathbb{Z}$ ($\mathbb{Z}$ sur $n\mathbb{Z}$).

($\mathbb{Z}$/n$\mathbb{Z}$)

On appelle {$\mathbb{Z}$/n$\mathbb{Z}$} l'ensemble quotient de $\mathbb{Z}$ par la relation de congruence modulo $n$. \[ \mathbb{Z}/n\mathbb{Z} = \EnsembleQuotient{\mathbb{Z}}{{\cdot\equiv}\cdot[n]} =\EnsembleQuotient{\mathbb{Z}}{\equiv_n} = \left\{\text{classes d'équivalence de } \mathbb{Z} \text{ par la relation } \equiv_n\right\} \] Il est important de comprendre que {$\mathbb{Z}/n\mathbb{Z}$} est une {notation} pour l'ensemble quotient de $\mathbb{Z}$ par la relation d'équivalence de congruence modulo $n$. En effet, $n\mathbb{Z}$ n'est pas une relation mais un ensemble. On utilise la notation $\mathbb{Z}/n\mathbb{Z}$ pour aléger la notation $\EnsembleQuotient{\mathbb{Z}}{\equiv_n}$ qui est plus lourde à écrire. De manière générale : \[ \boxed{\mathbb{Z}/n\mathbb{Z} = \left\{[0];\, [1];\, \ldots;\, [n-2];\, [n-1]\right\}} \]

Pour $n = 2 \implies \mathbb{Z}/2\mathbb{Z} = \{[x] \mid x \in \mathbb{Z}\}$. On a $[x] = \{x + 2k \mid k \in \mathbb{Z}\}$. $$\begin{align*} [0] & = \{2k \mid k \in \mathbb{Z}\} = \{\text{entiers pairs}\} \\ [1] & = \{1 + 2k \mid k \in \mathbb{Z}\} = \{\text{entiers impairs}\} \\ [2] & = \{2 + 2k \mid k \in \mathbb{Z}\} = [0] \\ [3] & = \{3 + 2k \mid k \in \mathbb{Z}\} = \{1 + 2(k+1) \mid k \in \mathbb{Z}\} = [1]. \end{align*}$$ Donc $\mathbb{Z}/2\mathbb{Z} = \{[0];\, [1]\}$. Pour $n = 3 \implies \mathbb{Z}/3\mathbb{Z} = \{[x] \mid x \in \mathbb{Z}\}$. On a $[x] = \{x + 3k \mid k \in \mathbb{Z}\}$. $$\begin{align*} [0] & = \{3k \mid k \in \mathbb{Z}\} = \{\text{multiples de } 3\} \\ [1] & = \{1 + 3k \mid k \in \mathbb{Z}\} = \{\text{entiers dont le reste de la division par 3 est 1}\} \\ [2] & = \{2 + 3k \mid k \in \mathbb{Z}\} = \{\text{entiers dont le reste de la division par 3 est 2}\} \\ [3] & = [0];\quad [4] = [1];\quad [27] = [0]. \end{align*}$$ Donc $\mathbb{Z}/3\mathbb{Z} = \{[0];\, [1];\, [2]\}$.

Caractérisation des relations d'équivalence

($\EnsembleQuotient{X}{\mathcal{R}}$ est une partition de $X$)
Soit $X$ un ensemble et soit $\mathcal{R}$ une relation d'équivalence sur $X$ : l'ensemble $\EnsembleQuotient{X}{\mathcal{R}}$ est une partition de $X$. Rappel : On dit que $Q \subset \mathcal{P}(X)$ est une partition si :
1. $\forall A, B \in Q$, $A \neq B \implies A \cap B = \emptyset$.
2. $\forall x \in X$, $\exists A \in Q$, $x \in A$.
Il faut montrer que $\EnsembleQuotient{X}{\mathcal{R}} = \{[x] \mid x \in X\} \subset \mathcal{P}(X)$ est une partition. i) Soient $[x], [y] \in \EnsembleQuotient{X}{\mathcal{R}}$ tels que $[x] \neq [y]$. Est-ce que $[x] \neq [y] \implies [x] \cap [y] = \emptyset$ ? On va montrer que la contraposée est vraie : $[x] \cap [y] \neq \emptyset \stackrel{?}{\implies} [x] = [y]$. $$\begin{align*} [x] \cap [y] \neq \emptyset & \iff \exists z \in [x] \cap [y] \\ & \iff \exists z \in [x] \text{ et } z \in [y] \\ \begin{cases} z \in [x] \iff x\,\mathcal{R}\,z \\ z \in [y] \iff y\,\mathcal{R}\,z \stackrel{\text{Sym.}}{\implies} z\,\mathcal{R}\,y \end{cases} & \\ \mathcal{R} \text{ étant une relation d'équivalence} & \implies \text{par transitivité } x\,\mathcal{R}\,z \text{ et } z\,\mathcal{R}\,y \implies x\,\mathcal{R}\,y. \end{align*}$$ $\rightarrow$ Soit $x_1 \in [x] \iff @@MATH33@@$ $\iff x_1 \in [y]$, d'où $[x] \subset [y]$ et par symétrie $[y] \subset [x]$. $\implies [x] = [y]$, donc la contraposée est vraie. ii) $\forall x \in X$, $\exists A \in \EnsembleQuotient{X}{\mathcal{R}}$ tel que $x \in A = [x]$. On a $x \in [x]$ par réflexivité. $\implies \EnsembleQuotient{X}{\mathcal{R}}$ est une partition de $X$ (i.e. $\EnsembleQuotient{X}{\mathcal{R}} \in \mathcal{P}(X)$).

(Toute partition définit une relation d'équivalence)

Soit $X$ un ensemble et $Q \subset \mathcal{P}(X)$ (une partition de $X$). La relation binaire : \[ x\,\mathcal{R}_Q\,y \iff \exists A \in Q \text{ t.q. } \{x; y\} \subset A,\quad x, y \in X, \] est une relation d'équivalence dont la partition associée est $Q$.
$\rightarrow$ Relation d'équivalence :
1. $\mathcal{R}_Q$ est réflexive : En effet, $Q$ est une partition donc $\forall x \in X$, $\exists A \in Q$, $x \in A$, or $x \in A \iff \{x\} \subset A \iff \{x; x\} \subset A \iff x\,\mathcal{R}_Q\,x$.
2. $\mathcal{R}_Q$ est symétrique : En effet, $x\,\mathcal{R}_Q\,y \iff \exists A \in Q$ t.q. $\{x; y\} \subset A \iff \exists A \in Q$ t.q. $\{y; x\} \subset A \iff y\,\mathcal{R}_Q\,x$.
3. $\mathcal{R}_Q$ est transitive : En effet, $x\,\mathcal{R}_Q\,y$ et $y\,\mathcal{R}_Q\,z$ \[ \iff @@MATH34@@ \] Or $A, B \in Q$ et $y \in A \cap B \implies A \cap B \neq \emptyset \implies A = B$ (car $Q$ est une partition, i.e. $Q \in \mathcal{P}(X)$). \[ \implies \{x; y; z\} \subset A \implies \{x; z\} \subset A \implies x\,\mathcal{R}_Q\,z. \]
$\rightarrow$ La partition associée à $\mathcal{R}_Q$ est $Q$ : i.e. $\EnsembleQuotient{X}{\mathcal{R}_Q} = Q$. Soit $[x] \in \EnsembleQuotient{X}{\mathcal{R}_Q}$. Puisque $x \in X$ et $Q \in \mathcal{P}(X)$ : $\exists!\, A \in Q$ t.q. $x \in A$. Soit $y \in [x] \implies x\,\mathcal{R}_Q\,y \implies \exists B \in Q$ t.q. $\{x; y\} \subset B$. Or $x \in A$ et $x \in B \implies A \cap B \neq \emptyset \implies A = B \implies y \in A$. Donc $[x] \subset A$. Réciproquement : soit $y \in A \implies \{x; y\} \subset A \implies x\,\mathcal{R}_Q\,y \implies y \in [x]$. Donc $A \subset [x]$, d'où $[x] = A$. Ainsi $\EnsembleQuotient{X}{\mathcal{R}_Q} = Q$.
Relation d'ordre
(Relation d'ordre)
Soit $X$ un ensemble et soit $\mathcal{R}$ une relation binaire sur $X$. On dit que $\mathcal{R}$ est une relation d'ordre si :
1. $\mathcal{R}$ est réflexive : $\forall x \in X,\, x\,\mathcal{R}\,x$.
2. $\mathcal{R}$ est anti-symétrique : $\forall (x; y) \in X^2,\, x\,\mathcal{R}\,y \text{ et } y\,\mathcal{R}\,x \implies x = y$.
3. $\mathcal{R}$ est transitive : $\forall (x; y; z) \in X^3,\, x\,\mathcal{R}\,y \text{ et } y\,\mathcal{R}\,z \implies x\,\mathcal{R}\,z$.
On note généralement une relation d'ordre en remplaçant $\mathcal{R}$ par $\leqslant$ (même si ce n'est pas toujours l'ordre usuel) ou encore pour bien inssister qu'il ne s'agit pas de la relation d'ordre uselle par $\preccurlyeq$.
1. Sur $\mathbb{R}$, la relation $\leqslant$ est une relation d'ordre (appelée ordre usuel).
2. Sur $\mathcal{P}(X)$, la relation $\subset$ (inclusion) est une relation d'ordre.
3. Sur $\mathbb{N}^*$, la relation de divisibilité $|$ est une relation d'ordre : \[ a \mid b \iff \exists k \in \mathbb{N},\, b = k \cdot a. \]
4. La relation $\leqslant$ sur $\mathbb{R}$ n'est pas une relation d'équivalence car elle n'est pas symétrique.
Ordre total et ordre partiel

(Ordre total et ordre partiel)
Soit $(X, \preccurlyeq)$ un ensemble muni d'une relation d'ordre.
- On dit que l'ordre est total si deux éléments quelconques de $X$ sont toujours comparables : \[ \forall (x; y) \in X^2,\quad x \preccurlyeq y \text{ ou } y \preccurlyeq x. \]
- On dit que l'ordre est partiel si elle n'est pas total, c'est-à-dire s'il existe au moins deux éléments non comparables : \[ \exists (x; y) \in X^2,\quad x \not\preccurlyeq y \text{ et } y \not\preccurlyeq x. \]
1. $(\mathbb{R}, \leqslant)$ est un ensemble totalement ordonné : deux réels sont toujours comparables.
2. $(\mathcal{P}(X), \subset)$ est un ensemble partiellement ordonné (si $\text{card}(X) \geqslant 2$) : \[ \text{Si } A = \{1\} \text{ et } B = \{2\}, \text{ alors } A \not\subset B \text{ et } B \not\subset A. \]
3. $(\mathbb{N}^*, ~\mid~)$ (où $~\mid~$ est la relation « divise ») est un ensemble partiellement ordonné : \[ 2 \nmid 3 \text{ et } 3 \nmid 2 \text{ donc } 3 \text{ et } 2 \text{ ne sont pas comparable.} \]
Éléments remarquables d'un ensemble ordonné

(Majorant, minorant, maximum, minimum)
Soit $(X, \leqslant)$ un ensemble ordonné et soit $A \subset X$.
- Un élément $M \in X$ est un majorant de $A$ si : \[ \forall a \in A,\quad a \leqslant M. \]
- Un élément $m \in X$ est un minorant de $A$ si : \[ \forall a \in A,\quad m \leqslant a. \]
- Un élément $M \in A$ est le maximum de $A$ (noté $\max A$) si : \[ M \in A ~~\text{ et }~~ \forall a \in A,\quad a \leqslant M. \, \]
- Un élément $m \in A$ est le minimum de $A$ (noté $\min A$) si : \[ m \in A ~~\text{ et }~~ \forall a \in A,\quad m \leqslant a. \, \]
- Un majorant (ou minorant) n'appartient pas nécessairement à $A$.
- Le maximum et le minimum, s'ils existent, sont uniques (par anti-symétrie).
- $\max A$ existe $\implies A$ est majorée, mais la réciproque est fausse en général.
1. Dans $(\mathbb{R}, \leqslant)$, pour $A = [0; 1[$ :
  - Majorants : tous les réels $\geqslant 1$
  - Minorants : tous les réels $\leqslant 0$
  - $\min A = 0$ (existe et appartient à $A$)
  - $\max A$ n'existe pas ($1 \notin A$)
2. Dans $(\mathcal{P}(\{1; 2\}), \subset)$, pour $A = \big\{\emptyset, \{1\}\big\}$ :
  - Majorants : $\{1\}, \{1; 2\}$
  - Minorant : $\emptyset$
  - $\max A = \{1\}$
  - $\min A = \emptyset$
Borne supérieure et borne inférieure

(Borne supérieure et borne inférieure)
Soit $(X, \leqslant)$ un ensemble ordonné et soit $A \subset X$.
- La borne supérieure de $A$ (notée $\sup A$) est le plus petit des majorants de $A$ : \[ \sup A = \min\left\{M \in X ~\middle|~ \forall a \in A,\, a \leqslant M\right\}. \]
- La borne inférieure de $A$ (notée $\inf A$) est le plus grand des minorants de $A$ : \[ \inf A = \max\left\{m \in X ~\middle|~ \forall a \in A,\, m \leqslant a\right\}. \]
(Lien entre extrema et bornes)
Soit $A \subset X$ dans un ensemble ordonné $(X, \leqslant)$.
- Si $\max A$ existe, alors $\sup A$ existe et $\sup A = \max A$.
- Si $\min A$ existe, alors $\inf A$ existe et $\inf A = \min A$.
Dans $(\mathbb{R}, \leqslant)$ :
\renewcommand{\arraystretch}{1.8}
[Tableau LaTeX non converti — à reprendre à la main]

Propriété de la borne supérieure dans $\mathbb{R}$

(Propriété de la borne supérieure (Axiome de complétude de $\mathbb{R}$))

Toute partie non vide et majorée de $\mathbb{R}$ admet une borne supérieure dans $\mathbb{R}$. Autrement dit : \[ \forall A \subset \mathbb{R},\quad A \neq \emptyset \text{ et } A \text{ majorée} \implies \sup A \in \mathbb{R}. \]
- Cette propriété caractérise $\mathbb{R}$ : elle est fausse dans $\mathbb{Q}$.
- Exemple dans $\mathbb{Q}$ : $A = \left\{x \in \mathbb{Q} ~\middle|~ x^2 < 2\right\}$ est majorée dans $\mathbb{Q}$ mais $\sup A = \sqrt{2} \notin \mathbb{Q}$.
- Par symétrie, toute partie non vide et minorée de $\mathbb{R}$ admet une borne inférieure dans $\mathbb{R}$.
Récapitulatif des types de relations
Tableau récapitulatif des propriétés des relations binaires :
\renewcommand{\arraystretch}{1.5}
[Tableau LaTeX non converti — à reprendre à la main]

Différence clé :
- Une relation d'équivalence partitionne l'ensemble en classes disjointes.
- Une relation d'ordre structure l'ensemble en permettant de comparer les éléments.

Applications

Généralités sur les applications

(Application)

Soient $X$ et $Y$ deux ensembles non vides. Une {application} $f$ de $X$ dans $Y$ est une correspondance qui à tout élément $x \in X$ associe un unique élément $y \in Y$, appelé image de $x$ par $f$ et noté $f(x)$. On note : \[ f : @@MATH35@@ \quad \text{ou} \quad @@MATH38@@ \] $X$ est l'{ensemble de départ} (ou domaine de définition) et $Y$ est l'{ensemble d'arrivée} (ou codomaine).

Changer $X$, $Y$, ou la relation $x \mapsto f(x)$ change l'application.

(Graphe d'une application)

Le {graphe} de $f : X \to Y$ est l'ensemble : \[ \Gamma_f = \{(x, f(x)) \mid x \in X\} \subset X \times Y. \]
Image directe et image réciproque
(Image directe)

Soit $f : X \to Y$ et $A \subset X$. L'{image directe} de $A$ par $f$ est : \[ f(A) = \{f(x) \mid x \in A\} = \{y \in Y \mid \exists x \in A,\, y = f(x)\} \subset Y. \] En particulier, $f(X)$ est appelé {image} de $f$.

(Propriétés de l'image directe)
Soient $f : X \to Y$, $A_0 \subset A_1 \subset X$ et $B_0, B_1 \subset X$. Alors :
1. Si $A_0 \subset A_1$, alors $f(A_0) \subset f(A_1)$.
2. $f(A_0 \cup A_1) = f(A_0) \cup f(A_1)$.
3. $f(A_0 \cap A_1) \subset f(A_0) \cap f(A_1)$ (l'inclusion peut être stricte).
(b) : Soit $y \in f(A_0 \cup A_1) \iff \exists x \in A_0 \cup A_1,\, y = f(x) \iff \exists x \in A_0$ ou $x \in A_1,\, y = f(x) \iff y \in f(A_0) \lor y \in f(A_1) \iff y \in f(A_0) \cup f(A_1)$. (c) : Soit $y \in f(A_0 \cap A_1) \implies \exists x \in A_0 \cap A_1,\, y = f(x) \implies x \in A_0$ et $x \in A_1 \implies y \in f(A_0)$ et $y \in f(A_1) \implies y \in f(A_0) \cap f(A_1)$. L'inclusion peut être stricte : exemple $f : \{a,b\} \to \mathbb{R}$, $f(a)=f(b)=1$, $A_0=\{a\}$, $A_1=\{b\}$, $A_0 \cap A_1 = \emptyset$, $f(\emptyset) = \emptyset$ mais $f(A_0) \cap f(A_1) = \{1\}$.

(Image réciproque)

Soit $f : X \to Y$ et $B \subset Y$. L'{image réciproque} de $B$ par $f$ est : \[ f^{-1}(B) = \{x \in X \mid f(x) \in B\} \subset X. \] \warning Ne pas confondre $f^{-1}(B)$ (image réciproque d'un ensemble, toujours définie) et $f^{-1}$ (application réciproque, définie seulement si $f$ est bijective). \warning

(Propriétés de l'image réciproque)
Soient $f : X \to Y$ et $B_0, B_1 \subset Y$. Alors :
1. Si $B_0 \subset B_1$, alors $f^{-1}(B_0) \subset f^{-1}(B_1)$.
2. $f^{-1}(B_0 \cup B_1) = f^{-1}(B_0) \cup f^{-1}(B_1)$.
3. $f^{-1}(B_0 \cap B_1) = f^{-1}(B_0) \cap f^{-1}(B_1)$.
4. $f^{-1}(B_0 \setminus B_1) = f^{-1}(B_0) \setminus f^{-1}(B_1)$.
5. $f^{-1}(C_Y B) = C_X f^{-1}(B)$.
(Relations entre image directe et image réciproque)
Soient $f : X \to Y$, $A \subset X$ et $B \subset Y$. Alors :
1. $A \subset f^{-1}(f(A))$ (avec égalité si $f$ est injective).
2. $f(f^{-1}(B)) \subset B$ (avec égalité si $f$ est surjective).
Injections, surjections, bijections
(Application injective)

L'application $f : X \to Y$ est dite {injective} si tout élément de $Y$ possède au plus un antécédent par $f$ : \[ \forall x_1, x_2 \in X, \quad f(x_1) = f(x_2) \implies x_1 = x_2. \] (De manière équivalente par contraposée : $x_1 \neq x_2 \implies f(x_1) \neq f(x_2)$.)

(Application surjective)

L'application $f : X \to Y$ est dite {surjective} si tout élément de $Y$ possède au moins un antécédent : \[ \forall y \in Y, \exists x \in X, \quad f(x) = y. \] Autrement dit : $f(X) = Y$.

(Application bijective)

L'application $f : X \to Y$ est dite {bijective} si elle est à la fois injective et surjective, c'est-à-dire si tout élément de $Y$ possède un unique antécédent : \[ \forall y \in Y, \exists!\, x \in X, \quad f(x) = y. \]
1. $f : \mathbb{R} \to \mathbb{R}$, $x \mapsto 2x - 3$ est bijective.
2. $f : \mathbb{R} \to \mathbb{R}$, $x \mapsto x^2$ n'est ni injective ($f(1)=f(-1)$) ni surjective ($-1 \notin f(\mathbb{R})$).
3. $f : \mathbb{R} \to \mathbb{R}$, $x \mapsto \cos x$ est ni injective ni surjective.
4. $f : \mathbb{R} \to \mathbb{R}$, $x \mapsto x^3$ est bijective.
5. $f : \mathbb{R} \to \mathbb{R}_+^*$, $x \mapsto e^x$ est bijective.
(Critère d'injectivité via les images réciproques)

$f : X \to Y$ est injective si et seulement si pour tout $y \in Y$, $f^{-1}(\{y\})$ est soit vide soit un singleton.

(Caractérisation de l'injectivité)
Soit $f : X \to Y$. Les assertions suivantes sont équivalentes :
1. $f$ est injective.
2. Pour tous $A, B \in \mathcal{P}(X)$, $f(A \cap B) = f(A) \cap f(B)$.
3. Pour tout $A \subset X$, $f^{-1}(f(A)) = A$.
Composition des applications
(Application composée)

Soient $f : X \to Y$ et $g : Y \to Z$ deux applications (telles que l'ensemble d'arrivée de $f$ est l'ensemble de départ de $g$). On définit l'{application composée} $g \circ f$ par : \[ @@MATH39@@ \] On lit « $g$ rond $f$ »{}.

En général, $f \circ g \neq g \circ f$.

(Composition et injectivité/surjectivité)
Soient $f : A \to B$ et $g : B \to C$ deux applications. Alors :
1. $g \circ f$ injective $\implies$ $f$ injective.
2. $g \circ f$ surjective $\implies$ $g$ surjective.
3. Si $f$ et $g$ sont injectives (resp. surjectives, bijectives), alors $g \circ f$ est injective (resp. surjective, bijective).
(1) : Supposons $g \circ f$ injective. Soient $x_1, x_2 \in A$ tels que $f(x_1) = f(x_2)$. Alors $g(f(x_1)) = g(f(x_2))$, i.e. $(g \circ f)(x_1) = (g \circ f)(x_2)$. Par injectivité de $g \circ f$, $x_1 = x_2$. Donc $f$ est injective. (2) : Supposons $g \circ f$ surjective. Soit $z \in C$. $\exists x \in A$ tel que $(g \circ f)(x) = z$, i.e. $g(f(x)) = z$. Posons $y = f(x) \in B$, alors $g(y) = z$. Donc $g$ est surjective.
Application réciproque
(Application réciproque)

Soit $f : X \to Y$ une bijection. L'{application réciproque} de $f$, notée $f^{-1}$, est l'application : \[ @@MATH40@@ \]

(Caractérisation de la bijectivité)

$f : X \to Y$ est bijective si et seulement s'il existe $g : Y \to X$ telle que : \[ g \circ f = \mathrm{Id}_X \quad \text{et} \quad f \circ g = \mathrm{Id}_Y. \] Dans ce cas, $g = f^{-1}$.

(Propriétés de la réciproque)
Si $f : X \to Y$ est bijective :
1. $f^{-1} \circ f = \mathrm{Id}_X$ et $f \circ f^{-1} = \mathrm{Id}_Y$.
2. $f^{-1}$ est bijective et $(f^{-1})^{-1} = f$.
3. Si $g : Y \to Z$ est aussi bijective, alors $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.
1. $\exp : \mathbb{R} \to \mathbb{R}_+^*$, $x \mapsto e^x$ est bijective, de réciproque $\ln : \mathbb{R}_+^* \to \mathbb{R}$.
2. $f : \mathbb{R}^3 \to \mathbb{R}^3$, $f(x,y,z) = (x-y+2z, -x+y-z, 2x-y+z)$ : étudier l'injectivité, la surjectivité, la bijectivité et déterminer $f^{-1}$ si elle existe (voir Examen 08/01/2013).
Fonction indicatrice
(Fonction indicatrice)

Soit $E$ un ensemble et $A \subset E$. La {fonction indicatrice} (ou caractéristique) de $A$ est l'application $\mathbb{1}_A : E \to \{0, 1\}$ définie par : \[ \mathbb{1}_A(x) = @@MATH36@@ \]

(Propriétés des fonctions indicatrices)
Soient $A, B \subset E$. Alors :
1. $\mathbb{1}_{A \cap B} = \mathbb{1}_A \cdot \mathbb{1}_B$.
2. $\mathbb{1}_{\complement_E A} = 1 - \mathbb{1}_A$.
3. $\mathbb{1}_{A \cup B} = \mathbb{1}_A + \mathbb{1}_B - \mathbb{1}_A \cdot \mathbb{1}_B$.
4. $\mathbb{1}_{A \setminus B} = \mathbb{1}_A(1 - \mathbb{1}_B) = \mathbb{1}_A - \mathbb{1}_A \cdot \mathbb{1}_B$.
5. $\mathbb{1}_{A \Delta B} = \mathbb{1}_A + \mathbb{1}_B - 2\mathbb{1}_A\mathbb{1}_B$ (différence symétrique $A \Delta B = (A \setminus B) \cup (B \setminus A)$).
6. $A = B \iff \mathbb{1}_A = \mathbb{1}_B$.
Cardinal d'un ensemble fini
(Ensemble fini, cardinal)

Un ensemble $E$ est dit {fini} s'il existe $n \in \mathbb{N}$ et une bijection de $\{1, \ldots, n\}$ sur $E$. L'entier $n$ est unique et s'appelle le {cardinal} de $E$, noté $\mathrm{card}(E)$ ou $|E|$. Par convention, $\mathrm{card}(\emptyset) = 0$.

(Dénombrement des applications)
Soient $E$ et $F$ deux ensembles finis avec $\mathrm{card}(E) = n$ et $\mathrm{card}(F) = p$.
1. Le nombre d'applications de $E$ dans $F$ est $p^n$.
2. Le nombre d'injections de $E$ dans $F$ (avec $p \geqslant n$) est $p(p-1)\cdots(p-n+1) = \dfrac{p!}{(p-n)!}$.
3. Le nombre de bijections de $E$ dans $F$ (si $p = n$) est $n!$.
(Cardinal de $\mathcal{P}(A)$)

Si $A$ est un ensemble fini à $n$ éléments, alors $\mathrm{card}(\mathcal{P}(A)) = 2^n$.

On construit une bijection entre $\mathcal{P}(A)$ et les applications de $A$ dans $\{0,1\}$ via les fonctions indicatrices : à $B \subset A$ on associe $\mathbb{1}_B$. Le nombre de telles applications est $2^n$. D'après la Prop précédente avec $p = 2$, on a bien $\mathrm{card}(\mathcal{P}(A)) = 2^n$.

On peut montrer qu'il n'existe pas de bijection entre $\mathcal{P}(X)$ et $X$ (même si $X$ est infini), par l'argument diagonal de Cantor.

Groupes

Loi de composition interne
(Loi de composition interne (LCI))

Soit $E$ un ensemble. Une {loi de composition interne} sur $E$ est une application {$T$} définie par : \[ @@MATH41@@ \] Autrement dit, c'est une application qui à tout couple $(x,y)$ d'éléments de $E$ associe un élément de $E$ (stabilité).
1. L'addition $+$ et la multiplication $\times$ sont des LCI sur $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$.
2. La soustraction n'est pas une LCI sur $\mathbb{N}$ (car $1 - 2 \notin \mathbb{N}$), mais l'est sur $\mathbb{Z}$.
3. La composition $\circ$ est une LCI sur l'ensemble des applications de $E$ dans $E$.
4. Sur $\mathbb{R} \setminus \{1\}$, la loi $x * y = x + y - xy$ est une LCI (à vérifier : $x * y = 1 - (1-x)(1-y) \neq 1$ si $x \neq 1$ et $y \neq 1$).
(Propriétés d'une LCI)
Soit $T$ une LCI sur $E$.
- $T$ est {associative} si : $\forall x, y, z \in E$, $(x \,T\, y) \,T\, z = x \,T\, (y \,T\, z)$.
- $T$ est {commutative} si : $\forall x, y \in E$, $x \,T\, y = y \,T\, x$.
- $e \in E$ est un {élément neutre} pour $T$ si : $\forall x \in E$, $e \,T\, x = x \,T\, e = x$.
- Soit $e$ l'élément neutre. $x' \in E$ est un {symétrique} (ou inverse) de $x$ pour $T$ si : $x \,T\, x' = x' \,T\, x = e$.
(Unicité de l'élément neutre et du symétrique)
1. S'il existe, l'élément neutre est unique.
2. Si $T$ est associative et si $x$ admet un symétrique, celui-ci est unique.
(1) : Supposons $e$ et $e'$ deux éléments neutres. Alors $e = e \,T\, e' = e'$ (en utilisant que $e'$ est neutre puis que $e$ est neutre). (2) : Supposons $x'$ et $x''$ deux symétriques de $x$. Alors : $x' = x' \,T\, e = x' \,T\, (x \,T\, x'') = (x' \,T\, x) \,T\, x'' = e \,T\, x'' = x''$.
Notion de groupe
(Groupe)
On dit que $(G, *)$ est un {groupe} si $*$ est une LCI sur $G$ vérifiant :
1. Associativité : $\forall x, y, z \in G$, $(x * y) * z = x * (y * z)$.
2. Élément neutre : $\exists e \in G$, $\forall x \in G$, $e * x = x * e = x$.
3. Symétrique : $\forall x \in G$, $\exists x^{-1} \in G$, $x * x^{-1} = x^{-1} * x = e$.
Si de plus $*$ est commutative, on dit que $(G, *)$ est un {groupe abélien} (ou commutatif).
1. $(\mathbb{Z}, +)$, $(\mathbb{Q}, +)$, $(\mathbb{R}, +)$ sont des groupes abéliens.
2. $(\mathbb{Q}^*, \times)$, $(\mathbb{R}^*, \times)$ sont des groupes abéliens.
3. $(\mathbb{N}, +)$ n'est pas un groupe (pas de symétrique pour $n \geqslant 1$).
4. $(\mathbb{Z}, \times)$ n'est pas un groupe (pas de symétrique pour $|n| \geqslant 2$).
5. $(\mathbb{Z}/n\mathbb{Z}, +)$ est un groupe abélien.
6. $(\mathcal{P}(X), \Delta)$ est un groupe abélien (élément neutre $\emptyset$, tout élément est son propre symétrique).
7. $(U_1, \times)$ où $U_1 = \{z \in \mathbb{C} \mid |z| = 1\}$ est un groupe abélien.
(Propriétés dans un groupe)
Soit $(G, *)$ un groupe d'élément neutre $e$. Pour tous $x, y \in G$ :
1. $(x^{-1})^{-1} = x$.
2. $(x * y)^{-1} = y^{-1} * x^{-1}$.
3. Lois de simplification : $x * y = x * z \implies y = z$ (simplification à gauche) et $y * x = z * x \implies y = z$ (simplification à droite).
4. L'équation $a * x = b$ (resp. $x * a = b$) a une unique solution $x = a^{-1} * b$ (resp. $x = b * a^{-1}$).
Sous-groupes
(Sous-groupe)
Soit $(G, *)$ un groupe. Un sous-ensemble $H \subset G$ est un {sous-groupe} de $G$ si $(H, *)$ est lui-même un groupe, c'est-à-dire :
1. $H \neq \emptyset$ (ou de manière équivalente $e \in H$).
2. $\forall x, y \in H$, $x * y \in H$ (stabilité).
3. $\forall x \in H$, $x^{-1} \in H$ (stabilité par passage au symétrique).
Les conditions 2 et 3 peuvent se remplacer par une seule : $\forall x, y \in H$, $x * y^{-1} \in H$.

(Intersection de sous-groupes)

Si $G_1$ et $G_2$ sont deux sous-groupes de $G$, alors $G_1 \cap G_2$ est un sous-groupe de $G$.

(Réunion de sous-groupes)

$G_1 \cup G_2$ est un sous-groupe de $G$ si et seulement si $G_1 \subset G_2$ ou $G_2 \subset G_1$.

(Sous-groupes de $\mathbb{Z}$)

Les sous-groupes de $(\mathbb{Z}, +)$ sont exactement les ensembles de la forme : \[ k\mathbb{Z} = \{kn \mid n \in \mathbb{Z}\}, \quad k \in \mathbb{N}. \]
$k\mathbb{Z}$ est un sous-groupe : $0 = k \cdot 0 \in k\mathbb{Z}$, si $x = km$ et $y = kn$ alors $x + y = k(m+n) \in k\mathbb{Z}$, $-x = k(-m) \in k\mathbb{Z}$. Tout sous-groupe est de cette forme : Soit $G$ un sous-groupe de $\mathbb{Z}$. Si $G = \{0\}$, alors $G = 0\mathbb{Z}$. Sinon, $G$ contient un élément non nul $\ell$, donc aussi $-\ell$, donc $G$ contient un entier strictement positif. Posons $k = \min\{\ell \in \mathbb{N}^*, \ell \in G\}$. Montrons $G = k\mathbb{Z}$ :
- Si $\ell \in G$, alors $\ell\mathbb{Z} \subset G$ (par stabilité).
- Soit $g \in G$. Par division euclidienne, $g = kq + r$ avec $0 \leqslant r < k$. Or $r = g - kq \in G$ (stabilité). Par minimalité de $k$, $r = 0$. Donc $g = kq \in k\mathbb{Z}$.
Les sous-groupes de $(\mathbb{Z}, +)$ sont $\{0\} = 0\mathbb{Z}$, $\mathbb{Z} = 1\mathbb{Z}$, $2\mathbb{Z}$ (entiers pairs), $3\mathbb{Z}$, etc.
Morphismes de groupes
(Morphisme de groupes)

Soient $(G, *)$ et $(H, \cdot)$ deux groupes. Une application $f : G \to H$ est un {morphisme de groupes} (ou homomorphisme) si : \[ \forall x, y \in G, \quad f(x * y) = f(x) \cdot f(y). \]

(Propriétés des morphismes)
Soit $f : G \to H$ un morphisme de groupes, $e_G$ (resp. $e_H$) l'élément neutre de $G$ (resp. $H$). Alors :
1. $f(e_G) = e_H$.
2. $\forall x \in G$, $f(x^{-1}) = (f(x))^{-1}$.
3. $f(G)$ (l'image de $f$) est un sous-groupe de $H$.
4. $\mathrm{Ker}(f) = f^{-1}(\{e_H\}) = \{x \in G \mid f(x) = e_H\}$ est un sous-groupe de $G$, appelé {noyau} de $f$.
(Injectivité et noyau)

Un morphisme $f : G \to H$ est injectif si et seulement si $\mathrm{Ker}(f) = \{e_G\}$.

$(\implies)$ : Si $f$ est injective et $x \in \mathrm{Ker}(f)$, alors $f(x) = e_H = f(e_G)$, donc $x = e_G$. $(\Leftarrow)$ : Si $\mathrm{Ker}(f) = \{e_G\}$ et $f(x) = f(y)$, alors $f(x \cdot y^{-1}) = f(x) \cdot f(y)^{-1} = e_H$, donc $x * y^{-1} \in \mathrm{Ker}(f) = \{e_G\}$, d'où $x * y^{-1} = e_G$, soit $x = y$.

(Isomorphisme, automorphisme)
- Un {isomorphisme} est un morphisme bijectif.
- Un {automorphisme} est un isomorphisme de $G$ dans lui-même.
- On dit que $G$ et $H$ sont {isomorphes} ($G \simeq H$) s'il existe un isomorphisme de $G$ dans $H$.
1. $f : (\mathbb{R}, +) \to (\mathbb{R}_+^*, \times)$, $x \mapsto e^x$ est un isomorphisme (réciproque : $\ln$).
2. $f : (\mathbb{Z}, +) \to (k\mathbb{Z}, +)$, $n \mapsto kn$ est un isomorphisme pour tout $k \neq 0$.
3. $f : \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$, $k \mapsto \bar{k}$ est un morphisme surjectif de noyau $n\mathbb{Z}$.
4. Les racines $n$-ièmes de l'unité $R_n = \{e^{2i\pi k/n} \mid k = 0,\ldots,n-1\}$ forment un sous-groupe de $(U_1, \times)$ isomorphe à $(\mathbb{Z}/n\mathbb{Z}, +)$.
(Morphismes de $(\mathbb{Z}, +)$)
Tout morphisme de $(\mathbb{Z}, +)$ dans $(\mathbb{Z}, +)$ est de la forme $n \mapsto kn$ pour un certain $k \in \mathbb{Z}$.
- Il est injectif ssi $k \neq 0$.
- Il est surjectif ssi $k = \pm 1$.
($(\mathbb{Z}/n\mathbb{Z}, +)$ est un groupe abélien)

La loi $\bar{x} + \bar{y} = \overline{x + y}$ est bien définie sur $\mathbb{Z}/n\mathbb{Z}$ et munit cet ensemble d'une structure de groupe abélien, d'élément neutre $\bar{0}$, et où le symétrique de $\bar{x}$ est $\overline{-x}$.

(Critère d'abélianité)

Soit $(G, *)$ un groupe. Alors $G$ est abélien si et seulement si l'application $x \mapsto x^{-1}$ est un morphisme de $G$.

Constitution des réels

Corps des réels
(Corps)
Un {corps} est un ensemble $\mathbb{K}$ muni de deux LCI $+$ et $\times$ telles que :
1. $(\mathbb{K}, +)$ est un groupe abélien, d'élément neutre $0$.
2. $(\mathbb{K}^* , \times)$ est un groupe abélien, d'élément neutre $1$.
3. Distributivité : $\forall x,y,z \in \mathbb{K}$, $x \times (y + z) = x \times y + x \times z$.
$\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$ sont des corps. $\mathbb{Z}$ n'est pas un corps (les entiers $\geqslant 2$ n'ont pas d'inverse pour $\times$).

(Corps ordonné)
Un corps $(\mathbb{K}, +, \times)$ est dit {ordonné} si l'on dispose d'une relation d'ordre $\leqslant$ compatible avec les opérations, c'est-à-dire :
1. $\forall x, y, z \in \mathbb{K}$, $x \leqslant y \implies x + z \leqslant y + z$.
2. $\forall x, y, z \in \mathbb{K}$, $x \leqslant y$ et $0 \leqslant z \implies xz \leqslant yz$.
Propriété de la borne supérieure
(Majorant, minorant, borne supérieure, borne inférieure)
Soit $A \subset \mathbb{R}$, $A \neq \emptyset$.
- $M \in \mathbb{R}$ est un {majorant} de $A$ si $\forall a \in A$, $a \leqslant M$.
- $m \in \mathbb{R}$ est un {minorant} de $A$ si $\forall a \in A$, $a \geqslant m$.
- $A$ est {majorée} (resp. {minorée}) si elle admet un majorant (resp. minorant).
- $A$ est {bornée} si elle est à la fois majorée et minorée.
- S'il existe, le plus petit des majorants de $A$ s'appelle la {borne supérieure} de $A$, notée $\sup A$.
- S'il existe, le plus grand des minorants de $A$ s'appelle la {borne inférieure} de $A$, notée $\inf A$.
(Théorème de la borne supérieure (propriété fondamentale de $\mathbb{R}$))

Toute partie non vide et majorée de $\mathbb{R}$ admet une borne supérieure. Toute partie non vide et minorée de $\mathbb{R}$ admet une borne inférieure.

Ce théorème caractérise la complétude de $\mathbb{R}$. Il est faux dans $\mathbb{Q}$ : par exemple $A = \{x \in \mathbb{Q} \mid x^2 < 2\}$ est majorée dans $\mathbb{Q}$ mais $\sup A = \sqrt{2} \notin \mathbb{Q}$.

(Caractérisation de $\sup A$)

Soit $A \subset \mathbb{R}$ non vide et majorée, et $M \in \mathbb{R}$. Alors : \[ M = \sup A \iff @@MATH37@@ \]
Propriété d'Archimède

(Propriété d'Archimède)

$\mathbb{R}$ est {archimédien} : pour tout $\varepsilon > 0$ et tout $x \in \mathbb{R}$, il existe $n \in \mathbb{N}$ tel que $n\varepsilon > x$. En particulier : \[ \forall \varepsilon > 0,\, \exists n \in \mathbb{N}^*,\, \frac{1}{n} < \varepsilon. \]

(Partie entière)

Pour tout $x \in \mathbb{R}$, il existe un unique entier $n \in \mathbb{Z}$ tel que $n \leqslant x < n + 1$. Cet entier $n$ est appelé {partie entière} de $x$ et noté $\lfloor x \rfloor$ ou $\mathrm{E}(x)$.
Densité de $\mathbb{Q}$ dans $\mathbb{R}$

(Densité de $\mathbb{Q}$ dans $\mathbb{R}$)

Entre deux réels quelconques $x < y$, il existe un rationnel $r \in \mathbb{Q}$ tel que $x < r < y$. Autrement dit, tout intervalle ouvert non vide de $\mathbb{R}$ contient un rationnel.

(Densité des irrationnels dans $\mathbb{R}$)

Entre deux réels quelconques $x < y$, il existe un irrationnel $z \in \mathbb{R} \setminus \mathbb{Q}$ tel que $x < z < y$.
Construction de $\mathbb{R}$
L'ensemble $\mathbb{R}$ peut être construit de plusieurs façons équivalentes à partir de $\mathbb{Q}$ :
1. Coupures de Dedekind : $\mathbb{R}$ est l'ensemble des coupures de Dedekind dans $\mathbb{Q}$, i.e. les partitions $(\mathbb{Q}_1, \mathbb{Q}_2)$ de $\mathbb{Q}$ avec $\mathbb{Q}_1 < \mathbb{Q}_2$ élément par élément et $\mathbb{Q}_1$ sans maximum.
2. Suites de Cauchy : $\mathbb{R}$ est le complété de $\mathbb{Q}$ pour la distance usuelle, obtenu comme ensemble des classes d'équivalence de suites de Cauchy de rationnels.
(Caractérisation de $\mathbb{R}$)

$\mathbb{R}$ est l'unique corps totalement ordonné et complet (au sens de la propriété de la borne supérieure). Plus précisément, si $\mathbb{K}$ est un corps totalement ordonné et vérifiant la propriété de la borne supérieure, alors $\mathbb{K}$ est isomorphe à $\mathbb{R}$ (en tant que corps ordonné).

La propriété de la borne supérieure est ce qui distingue $\mathbb{R}$ de $\mathbb{Q}$ : $\mathbb{Q}$ est un corps totalement ordonné, archimédien, mais pas complet.

(Nombres réels et représentation décimale)

Tout réel $x \in [0, 1[$ admet une {développement décimal} : \[ x = \sum_{n=1}^{+\infty} \frac{a_n}{10^n} = {,}a_1 a_2 a_3 \ldots \] où $a_n \in \{0, 1, \ldots, 9\}$. Ce développement est unique si l'on impose que la suite $(a_n)$ ne soit pas ultimement constante égale à $9$. Un réel est rationnel si et seulement si son développement décimal est ultimement périodique.

$\pi = 3{,}14159265\ldots$ est irrationnel (et même transcendant). $\sqrt{2} = 1{,}41421356\ldots$ est irrationnel. $\dfrac{1}{3} = {,}333\ldots = 0{,}\overline{3}$ est rationnel avec développement périodique.

Algèbre 1 : Structures mathématiques

Logiques Élémentaires

But du cours

Objet mathématique et définition

Énoncé mathématique

Théorie Mathématique

Table de vérité

Énoncés équivalents

Négation

Conjonction et disjonctions

Implication

Quantificateur universel ($\forall$)

Quantificateur existentiel ($\exists$)

Propriétés de $\forall$ et $\exists$

Les ensembles

Différences ensemblistes

Partition d'un ensemble

Relations

Définition

Relation binaire

Classe d'équivalence

Relation de congruence

Caractérisation des relations d'équivalence

Ordre total et ordre partiel

Éléments remarquables d'un ensemble ordonné

Borne supérieure et borne inférieure

Propriété de la borne supérieure dans $\mathbb{R}$

Récapitulatif des types de relations

Applications

Groupes

Constitution des réels