Eclats de vers : Matemat 02 : Ensembles

Index des Grimoires

Retour à l’accueil

Table des matières

\( \newcommand{\parentheses}[1]{\left(#1\right)} \newcommand{\crochets}[1]{\left[#1\right]} \newcommand{\accolades}[1]{\left\{#1\right\}} \newcommand{\ensemble}[1]{\left\{#1\right\}} \newcommand{\identite}{\mathrm{Id}} \newcommand{\indicatrice}{\boldsymbol{\delta}} \newcommand{\dirac}{\delta} \newcommand{\moinsun}{{-1}} \newcommand{\inverse}{\ddagger} \newcommand{\pinverse}{\dagger} \newcommand{\topologie}{\mathfrak{T}} \newcommand{\ferme}{\mathfrak{F}} \newcommand{\img}{\mathbf{i}} \newcommand{\binome}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\canonique}{\mathfrak{c}} \newcommand{\tenseuridentite}{\boldsymbol{\mathcal{I}}} \newcommand{\permutation}{\boldsymbol{\epsilon}} \newcommand{\matriceZero}{\mathfrak{0}} \newcommand{\matriceUn}{\mathfrak{1}} \newcommand{\christoffel}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\lagrangien}{\mathfrak{L}} \newcommand{\sousens}{\mathfrak{P}} \newcommand{\partition}{\mathrm{Partition}} \newcommand{\tribu}{\mathrm{Tribu}} \newcommand{\topologies}{\mathrm{Topo}} \newcommand{\setB}{\mathbb{B}} \newcommand{\setN}{\mathbb{N}} \newcommand{\setZ}{\mathbb{Z}} \newcommand{\setQ}{\mathbb{Q}} \newcommand{\setR}{\mathbb{R}} \newcommand{\setC}{\mathbb{C}} \newcommand{\corps}{\mathbb{K}} \newcommand{\boule}{\mathfrak{B}} \newcommand{\intervalleouvert}[2]{\relax \ ] #1 , #2 [ \ \relax} \newcommand{\intervallesemiouvertgauche}[2]{\relax \ ] #1 , #2 ]} \newcommand{\intervallesemiouvertdroite}[2]{[ #1 , #2 [ \ \relax} \newcommand{\fonction}{\mathbb{F}} \newcommand{\bijection}{\mathrm{Bij}} \newcommand{\polynome}{\mathrm{Poly}} \newcommand{\lineaire}{\mathrm{Lin}} \newcommand{\continue}{\mathrm{Cont}} \newcommand{\homeomorphisme}{\mathrm{Hom}} \newcommand{\etagee}{\mathrm{Etagee}} \newcommand{\lebesgue}{\mathrm{Leb}} \newcommand{\lipschitz}{\mathrm{Lip}} \newcommand{\suitek}{\mathrm{Suite}} \newcommand{\matrice}{\mathbb{M}} \newcommand{\krylov}{\mathrm{Krylov}} \newcommand{\tenseur}{\mathbb{T}} \newcommand{\essentiel}{\mathfrak{E}} \newcommand{\relation}{\mathrm{Rel}} \newcommand{\strictinferieur}{\ < \ } \newcommand{\strictsuperieur}{\ > \ } \newcommand{\ensinferieur}{\eqslantless} \newcommand{\enssuperieur}{\eqslantgtr} \newcommand{\esssuperieur}{\gtrsim} \newcommand{\essinferieur}{\lesssim} \newcommand{\essegal}{\eqsim} \newcommand{\union}{\ \cup \ } \newcommand{\intersection}{\ \cap \ } \newcommand{\opera}{\divideontimes} \newcommand{\autreaddition}{\boxplus} \newcommand{\autremultiplication}{\circledast} \newcommand{\commutateur}[2]{\left[ #1 , #2 \right]} \newcommand{\convolution}{\circledcirc} \newcommand{\correlation}{\ \natural \ } \newcommand{\diventiere}{\div} \newcommand{\modulo}{\bmod} \newcommand{\pgcd}{pgcd} \newcommand{\ppcm}{ppcm} \newcommand{\produitscalaire}[2]{\left\langle #1 \left|\right\relax #2 \right\rangle} \newcommand{\scalaire}[2]{\left\langle #1 \| #2 \right\rangle} \newcommand{\braket}[3]{\left\langle #1 \right| #2 \left| #3 \right\rangle} \newcommand{\orthogonal}{\bot} \newcommand{\forme}[2]{\left\langle #1 , #2 \right\rangle} \newcommand{\biforme}[3]{\left\langle #1 , #2 , #3 \right\rangle} \newcommand{\contraction}[3]{\left\langle #1 \odot #3 \right\rangle_{#2}} \newcommand{\dblecont}[5]{\left\langle #1 \right| #3 \left| #5 \right\rangle_{#2,#4}} \newcommand{\major}{major} \newcommand{\minor}{minor} \newcommand{\maxim}{maxim} \newcommand{\minim}{minim} \newcommand{\argument}{arg} \newcommand{\argmin}{arg\ min} \newcommand{\argmax}{arg\ max} \newcommand{\supessentiel}{ess\ sup} \newcommand{\infessentiel}{ess\ inf} \newcommand{\dual}{\star} \newcommand{\distance}{\mathfrak{dist}} \newcommand{\norme}[1]{\left\| #1 \right\|} \newcommand{\normetrois}[1]{\left|\left\| #1 \right\|\right|} \newcommand{\adh}{adh} \newcommand{\interieur}{int} \newcommand{\frontiere}{\partial} \newcommand{\image}{im} \newcommand{\domaine}{dom} \newcommand{\noyau}{ker} \newcommand{\support}{supp} \newcommand{\signe}{sign} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\unsur}[1]{\frac{1}{#1}} \newcommand{\arrondisup}[1]{\lceil #1 \rceil} \newcommand{\arrondiinf}[1]{\lfloor #1 \rfloor} \newcommand{\conjugue}{conj} \newcommand{\conjaccent}[1]{\overline{#1}} \newcommand{\division}{division} \newcommand{\difference}{\boldsymbol{\Delta}} \newcommand{\differentielle}[2]{\mathfrak{D}^{#1}_{#2}} \newcommand{\OD}[2]{\frac{d #1}{d #2}} \newcommand{\OOD}[2]{\frac{d^2 #1}{d #2^2}} \newcommand{\NOD}[3]{\frac{d^{#3} #1}{d #2^{#3}}} \newcommand{\deriveepartielle}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dblederiveepartielle}[2]{\frac{\partial^2 #1}{\partial #2 \partial #2}} \newcommand{\dfdxdy}[3]{\frac{\partial^2 #1}{\partial #2 \partial #3}} \newcommand{\dfdxdx}[2]{\frac{\partial^2 #1}{\partial #2^2}} \newcommand{\gradient}{\mathbf{\nabla}} \newcommand{\combilin}[1]{\mathrm{span}\{ #1 \}} \newcommand{\trace}{tr} \newcommand{\proba}{\mathbb{P}} \newcommand{\probaof}[1]{\mathbb{P}\left[#1\right]} \newcommand{\esperof}[1]{\mathbb{E}\left[#1\right]} \newcommand{\cov}[2]{\mathrm{cov} \left( #1 , #2 \right) } \newcommand{\var}[1]{\mathrm{var} \left( #1 \right) } \newcommand{\rand}{\mathrm{rand}} \newcommand{\variation}[1]{\left\langle #1 \right\rangle} \newcommand{\composante}{comp} \newcommand{\bloc}{bloc} \newcommand{\ligne}{ligne} \newcommand{\colonne}{colonne} \newcommand{\diagonale}{diag} \newcommand{\matelementaire}{\mathrm{Elem}} \newcommand{\matpermutation}{permut} \newcommand{\matunitaire}{\mathrm{Unitaire}} \newcommand{\gaussjordan}{\mathrm{GaussJordan}} \newcommand{\householder}{\mathrm{Householder}} \newcommand{\rang}{rang} \newcommand{\schur}{\mathrm{Schur}} \newcommand{\singuliere}{\mathrm{DVS}} \newcommand{\convexe}{\mathrm{Convexe}} \newcommand{\petito}[1]{o\left(#1\right)} \newcommand{\grando}[1]{O\left(#1\right)} \)

1 Ensembles

1.1 Dépendances

Vous êtes à la racine.

1.2 Définition explicite

Les ensembles sont des regroupements d'objets appelés éléments.

Il existe deux méthodes permettant de définir un ensemble. Lorsqu'il n'existe qu'un nombre fini d'éléments distincts, on peut les énumérer :

\[A = \{ a, b, c, ..., z \}\]

On dit alors que \(x\) appartient à \(A\), et on le note :

\[x \in A\]

si \(x\) fait partie de la liste \(a, b, c, ..., z\). Dans le cas contraire, \(x\) n'appartient pas à \(A\), ce que l'on note par :

\[x \notin A\]

1.3 Définition implicite

On peut aussi définir un ensemble en demandant que ses éléments respectent certaines conditions. On dit alors que \(x \in A\) si \(x\) vérifie toutes les conditions nécessaires pour appartenir à l'ensemble \(A\) ou que \(x \notin A\) si au moins une des conditions n'est pas remplie. Le schéma de ce type de définition s'écrit :

\[A = \{ x : \text{ une ou plusieurs conditions sur } x \}\]

Dans ce cas, le nombre d'éléments de l'ensemble peut être fini ou infini.

1.3.1 Variante

On ajoute souvent une condition sur les éléments de l'ensemble :

\[A = \{ x \in \Omega : \text{ conditions sur } x \}\]

Dans ce cas, tout candidat \(x\) doit en plus appartenir à l'ensemble \(\Omega\) s'il veut appartenir à l'ensemble \(A\). Cette définition est donc équivalente à :

\[A = \{ x : x \in \Omega, \text{ conditions sur } x \}\]

1.4 Notations

Le symbole \(\exists\) signifie « il existe » et le symbole \(\forall\) signifie « pour tout »

1.5 Ensemble vide

L'ensemble vide \(\emptyset = \{\}\) est un cas particulier ne contenant aucun élément :

\[x \notin \emptyset\]

quelle que soit la nature de \(x\).

1.6 Naturels

L'ensemble des nombres naturels se construit à partir d'un élément « racine » \(0\), auquel on ajoute indéfiniment des successeurs. Le successeur de \(0\) est noté \(0^+\) ou \(1\). On dit aussi que \(0\) est le prédécesseur de \(1\) et on le note \(1^- = 0\). Arrivé à l'élément \(i\), on ajoute le successeur de \(i\), noté :

\[j = i^+\]

On dit aussi que \(i\) est le prédécesseur de \(j\) et on le note :

\[i = j^-\]

On a donc :

\[i^{+-} = j^- = i\]

et :

\[j^{-+} = i^+ = j\]

L'ensemble des objets ainsi crée est appelé l'ensemble des nombres naturels et noté \(\setN\). En l'exprimant au moyen des symboles usuels, on a dans l'ordre de succession :

\[\setN = \{ 0,1,2,3,4,5,6,7,8,9,10,... \}\]

1.6.1 Notation

On note aussi :

\[i + 1 = i^+\]

et :

\[i - 1 = i^-\]

1.6.2 Element racine

L'élément \(0\) est le seul naturel à de pas posséder de prédécesseur. On l'appelle pour cette raison l'élément racine de \(\setN\).

On dit aussi qu'un élément \(n\) est nul pour signifier que \(n = 0\).

1.6.3 Ensemble discret ou dénombrable

Tout ensemble de la forme :

\[A = \{ a_k : k \in \setN \}\]

est dit discret ou dénombrable.

1.7 Inclusion

On dit que \(A\) est inclus dans \(B\) et on note :

\[A \subseteq B\]

si tous les éléments de \(A\) appartiennent aussi à \(B\) :

\[x \in A \ \Rightarrow \ x \in B\]

On dit alors que \(A\) est un sous-ensemble, ou une partie de \(B\).

1.7.1 Stricte

Il y a inclusion stricte :

\[A \subset B\]

lorsque $A \subseteq B $ et que les deux ensembles ne sont pas égaux, ce que l'on note par :

\[A \ne B\]

1.8 Egalité

Deux ensembles \(A\) et \(B\) sont dit égaux et on le note :

\[A = B\]

si tout élément de \(A\) appartient aussi à \(B\) et si tout élément de \(B\) appartient aussi à \(A\) :

\[x \in A \ \Leftrightarrow \ x \in B\]

ce qui revient à dire que l'on a inclusion mutuelle de \(A\) et \(B\) :

\[A = B \ \Leftrightarrow \ A \subseteq B \text{ et } B \subseteq A\]

1.8.1 Remarque

Dans le cadre des ensembles, on ne se soucie pas de l'ordre :

\[\{a,b\} = \{b,a\}\]

ni du nombre d'apparitions d'un élément :

\[\{a,a,b\} = \{a,b\}\]

1.9 Union

L'union de deux ensembles \(A \cup B\) est l'ensemble contenant les éléments de \(A\) et les éléments de \(B\). Un élément quelconque de \(A \cup B\) peut donc appartenir à \(A\), à \(B\) ou aux deux ensembles simultanément :

\[A \cup B = \{ x : x \in A \text{ ou/et } x \in B \}\]

1.9.1 Jargon

Le « ou » mathématique est non exclusif. La proposition \(a\) ou \(b\) signifie que soit \(a\), soit \(b\), soit (\(a\) et \(b\)) est vérifié.

1.10 Intersection

L'intersection \(A \cap B\) est l'ensemble des éléments qui appartiennent à la fois à \(A\) et à \(B\) :

\[A \cap B = \{ x : x \in A \text{ et } x \in B \}\]

1.10.1 Nomenclature

Lorsque l'intersection de deux ensembles est vide, on dit qu'ils sont disjoints.

1.11 Association

Soit les ensembles \(A,B,C\). On définit :

\[A \cup B \cup C = A \cup (B \cup C)\]

Comme les éléments de \(A \cup B \cup C\) sont les éléments qui appartiennent à au moins un des ensembles \(A,B,C\), on voit que :

\[A \cup B \cup C = (A \cup B) \cup C\]

On en conclut que :

\[A \cup B \cup C = A \cup (B \cup C) = (A \cup B) \cup C\]

On définit aussi :

\[A \cap B \cap C = A \cap (B \cap C)\]

Comme les éléments de \(A \cap B \cap C\) sont les éléments qui appartiennent simultanément à \(A,B,C\), on voit que :

\[A \cap B \cap C = (A \cap B) \cap C\]

On en conclut que :

\[A \cap B \cap C = A \cap (B \cap C) = (A \cap B) \cap C\]

1.12 Commutation

On a clairement :

\( A \cup B = B \cup A \\ A \cap B = B \cap A \)

1.13 Distribution

Soit les ensembles \(A,B,C\). Lorsque \(x\) appartient à la fois à \(A\) et à au moins un des deux ensembles \(B\) et \(C\), on sait que \(x\) appartient à \(A\) et \(B\) ou qu'il appartient à \(A\) et \(C\), et inversément. On a donc :

\[A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\]

On dit que l'intersection se distribue sur l'union. On a également la relation :

\[A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\]

On dit que l'union se distribue sur l'intersection.

1.14 Différence

La différence \(A \setminus B\) est l'ensemble des éléments qui appartiennent à \(A\) mais pas à \(B\) :

\[A \setminus B = \{ x : x \in A \text{ et } x \notin B \}\]

1.15 Décomposition

Soit les ensembles \(A,B\). Les éléments de \(A\) sont de deux types :

  • ceux qui appartiennent également à \(B\)
  • ceux qui n'appartiennent pas à \(B\)

On en conclut que :

\[A = (A \cap B) \cup (A \setminus B)\]

On voit que les deux sous-ensembles de \(A\) sont disjoints :

\[(A \cap B) \cap (A \setminus B) = \emptyset\]

1.15.1 Union

Les éléments de \(A \cup B\) sont de deux types :

  • ceux qui appartiennent seulement à \(A\)
  • ceux qui appartiennent à \(B\)

On en conclut que :

\[A \cup B = (A \setminus B) \cup B\]

On voit que les deux sous-ensembles de \(A \cup B\) sont disjoints :

\[(A \setminus B) \cap B = \emptyset\]

1.16 Complémentaire

Si \(A \subseteq \Omega\), on dit que \(C = \Omega \setminus A\) est le complémentaire de \(A\) dans \(\Omega\), ou simplement que \(C\) est le complémentaire de \(A\) lorsque l'ensemble \(\Omega\) est évident d'après le contexte.

1.16.1 Complémentaire du complémentaire

Soit \(A \subseteq \Omega\). Un élément de \(\Omega\) qui n'appartient pas à \(\Omega \setminus A\) appartient à \(A\), et réciproquement. On a donc :

\[\Omega \setminus (\Omega \setminus A) = A\]

1.16.2 Réciprocité

Soit \(A \subseteq \Omega\) et son complémentaire :

\[B = \Omega \setminus A\]

En prenant le complémentaire de cette équation, on obtient :

\[\Omega \setminus B = \Omega \setminus (\Omega \setminus A) = A\]

Soit à présent \(B \subseteq \Omega\) et son complémentaire :

\[A = \Omega \setminus B\]

En prenant le complémentaire de cette équation, on obtient :

\[\Omega \setminus A = \Omega \setminus (\Omega \setminus B) = B\]

On en conclut l'équivalence :

\[A = \Omega \setminus B \ \Leftrightarrow \ B = \Omega \setminus A\]

1.16.3 Complémentaire d'une union

Soit un ensemble \(\Omega\) et les sous-ensembles \(A,B \subseteq \Omega\). Un élément de \(\Omega\) qui n'appartient pas à \(A \cup B\) n'appartient ni à \(A\) ni à \(B\). Il appartient donc à \(\Omega \setminus A\) et à \(\Omega \setminus B\). Inversément, un élément qui appartient à \(\Omega \setminus A\) et à \(\Omega \setminus B\) n'appartient ni à \(A\) ni à \(B\). On a donc :

\[\Omega \setminus (A \cup B) = (\Omega \setminus A) \cap (\Omega \setminus B)\]

Le complémentaire d'une union est l'intersection des complémentaires.

1.16.4 Complémentaire d'une intersection

Soit \(A,B \in \Omega\). Posons :

\( C = \Omega \setminus A \subseteq \Omega \\ D = \Omega \setminus B \subseteq \Omega \)

L'expression du complémentaire de \(A \cup B\) devient :

\[\Omega \setminus \big[(\Omega \setminus C) \cup (\Omega \setminus D)\big] = C \cap D\]

En prenant le complémentaire des deux membres par rapport à \(\Omega\), on obtient :

\[(\Omega \setminus C) \cup (\Omega \setminus D) = \Omega \setminus (C \cap D)\]

Le complémentaire d'une intersection est l'union des complémentaires.

2 Collections

2.1 Dépendances

  • Chapitre \ref{chap:ensembles} : Les ensembles

2.2 Définition

Une collection est un ensemble d'ensembles, c'est-à-dire un ensemble dont les éléments sont également des ensembles.

2.3 L'ensemble des sous-ensembles

Une collection particulièrement importante est l'ensemble des sous-ensembles d'un ensemble donné \(A\). On le note :

\[\sousens(A) = \{ S : S \subseteq A \}\]

{\em Remarque :} la notation \(\sousens\) est une notation globale, vous la retrouver dans d'autres chapitres.

2.4 Union

Soit un ensemble \(\Omega\) et une collection d'ensembles \(\mathcal{C} \subseteq \sousens(\Omega)\). On définit l'union des ensembles-éléments de \(\mathcal{C}\) par :

\[\bigcup \mathcal{C} = \{ a \in \Omega : \text{ il existe } A \in \mathcal{C} \text{ tel que } a \in A \}\]

Il s'agit donc de l'ensemble dont chaque élément appartient à au moins un des ensembles-éléments de \(\mathcal{C}\).

2.5 Intersection

Soit un ensemble \(\Omega\) et une collection d'ensembles \(\mathcal{C} \subseteq \sousens(\Omega)\). On définit l'intersection des ensembles-éléments de \(\mathcal{C}\) par :

\[\bigcap \mathcal{C} = \{ a \in \Omega : a \in A \text{ pour tout } A \in \mathcal{C} \}\]

Il s'agit donc de l'ensemble dont chaque élément appartient à tous les ensembles-éléments de \(\mathcal{C}\).

2.6 Collection paramétrée

Soit un ensemble \(X\) et la collection :

\[\mathcal{C} = \{ A(x) \in \sousens(\Omega) : x \in X \}\]

On appelle ce type de collection une collection paramétrée. L'ensemble \(X\) est appelé ensemble de paramètres.

2.6.1 Union

L'union de tous ces ensembles est l'ensemble dont les éléments appartiennent à au moins un des \(A(x)\), pour un certain \(x \in X\) :

\[\bigcup_{x \in X} A(x) = \{ a \in \Omega : \text{ il existe } x \in X \text{ tel que } a \in A \}\]

L'intersection est l'ensemble des éléments appartenant à tous les \(A(x)\), pour tout les \(x \in X\) :

\[\bigcap_{x \in X} A(x) = \{ a \in \Omega : a \in A(x) \text{ pour tout } x \in X \}\]

2.7 Collections discrètes

Soit $A1,A2,A3,…$ une collection finie ou infinie d'ensembles. L'union de tous ces ensembles se note :

\[\bigcup_i A_i = A_1 \cup A_2 \cup A_3 \cup ...\]

L'ensemble des éléments qui sont communs à tous ces ensembles se note :

\[\bigcap_i A_i = A_1 \cap A_2 \cap A_3 \cap ...\]

2.7.1 Finie

Dans le cas où la collection est finie, par exemple \(A_1,A_2,...,A_n\), on note simplement :

\[\bigcup_{i = 1}^n A_i = A_1 \cup A_2 \cup ... \cup A_n\]

ainsi que :

\[\bigcap_{i = 1}^n A_i = A_1 \cap A_2 \cap ... \cap A_n\]

2.7.2 Infinie

Dans le cas où la collection est infinie, on note simplement :

\[\bigcup_{i = 1}^{+\infty} A_i = A_1 \cup A_2 \cup ...\]

ainsi que :

\[\bigcap_{i = 1}^{+\infty} A_i = A_1 \cap A_2 \cap ...\]

2.8 Distributivité

On a :

\[A \cap \bigcup_{x \in X} B(x) = \bigcup_{x \in X} \big[A \cap B(x)\big]\]

et :

\[A \cup \bigcap_{x \in X} B(x) = \bigcap_{x \in X} \big[A \cup B(x)\big]\]

Les collections discrètes en sont un cas particulier :

\( A \cap \bigcup_i B_i = \bigcup_i \big[A \cap B_i\big] \\ \\ A \cup \bigcap_i B_i = \bigcap_i \big[A \cup B_i\big] \)

2.9 Complémentaire

Soit une collection \(\{ A(x) : x \in X \} \subseteq \sousens(\Omega)\) de sous-ensembles de \(\Omega\). On a :

\[\Omega \setminus \bigcup_{x \in X} A(x) = \bigcap_{x \in X} \big[\Omega \setminus A(x)\big]\]

et :

\[\Omega \setminus \bigcap_{x \in X} A(x) = \bigcup_{x \in X} \big[\Omega \setminus A(x)\big]\]

Les collections discrètes en sont un cas particulier :

\( \Omega \setminus \bigcup_i A_i = \bigcap_i \big[\Omega \setminus A_i\big] \\ \\ \Omega \setminus \bigcap_i A_i = \bigcup_i \big[\Omega \setminus A_i\big] \)

3 Partitions

3.1 Dépendances

  • Chapitre \ref{chap:collections} : Les collections

3.2 Définition

Une partition, ou découpage, d'un ensemble \(A\) est une collection de sous-ensembles de \(A\) :

\[\mathcal{P} = \{ P(x) \in \sousens(A) : x \in X \}\]

vérifiant certaines propriétés : les ensembles de \(\mathcal{P}\) doivent permettre de reconstituer \(A\) par leur union :

\[A = \bigcup_{x \in X} P(x)\]

et ne doivent pas se chevaucher. Leur intersection est donc vide dès que \(x,y \in X\) vérifient \(x \ne y\) :

\[P(x) \cap P(y) = \emptyset\]

On note \(\partition(A)\) l'ensemble des collections formant une partition de \(A\).

3.3 Discrètes

Pour qu'une collection \(\{A_1,A_2,...\}\) de sous-ensembles de \(A\) forme une partition de \(A\), il faut que :

\[A = \bigcup_i A_i\]

et que :

\[A_i \cap A_j = \emptyset\]

pour tout \(i \ne j\).

4 Produit cartésien

4.1 Dépendances

  • Chapitre \ref{chap:ensembles} : Les ensembles

4.2 Définition

Le produit cartésien \(\times\) de deux ensembles \(A\) et \(B\) permet de construire des ensembles contenant des couples d'éléments \((x,y)\) :

\[A \times B = \{ (x,y) : x \in A \ \text{ et } \ y \in B \}\]

Les éléments \(x\) et \(y\) sont appelée composantes du couple \((x,y)\).

4.3 Tuple

On généralise aux tuples \((x_1,x_2,...,x_n)\) formés d'éléments des ensembles \(A_1, A_2, ..., A_n\) par :

\[A_1 \times A_2 \times ... \times A_n = \{ (x_1,x_2,...,x_n) : x_1 \in A_1, x_2 \in A_2, ..., x_n \in A_n \}\]

Les éléments \(x_1,x_2,...,x_n\) sont appelés composantes du tuple \((x_1,x_2,...,x_n)\)

4.4 Égalité

On dit que les deux tuples :

\[x = (x_1,x_2,...,x_n) \in A_1 \times A_2 \times ... \times A_n\]

et :

\[y = (y_1,y_2,...,y_n) \in A_1 \times A_2 \times ... \times A_n\]

sont égaux et on le note :

\[(x_1,x_2,...,x_n) = (y_1,y_2,...,y_n)\]

ou plus simplement :

\[x = y\]

si et seulement si toutes leurs composantes sont identiques :

\[x_i = y_i\]

pour tout \(i \in \{1,2,...,n\}\).

4.4.1 Remarque

Dans le cadre des tuples, l'ordre compte :

\[(a,b) \ne (b,a)\]

ainsi que le nombre d'apparitions d'un élément :

\[(a,a,b) \ne (a,b)\]

4.5 Puissance

On note \(A^n\) l'ensemble des tuples composés de \(n\) éléments de \(A\) :

\[A^n = \{ (x_1,x_2,...,x_n) : x_1,x_2,...,x_n \in A \}\]

Un exemple courant :

\[A^2 = A \times A\]

5 Relations

5.1 Dépendances

  • Chapitre \ref{chap:ensembles} : Les ensembles
  • Chapitre \ref{chap:produitCartesien} : Produit cartésien

5.2 Définition

Une relation \(R\) est un ensemble de couples \((x,y) \in A \times B\) reliant des éléments de \(A\) à des élements de \(B\). On note \(\relation(A,B)\) l'ensemble des relations sur \(A,B\) :

\[\relation(A,B) = \{ R : R \subseteq A \times B \}\]

On dit que \(x \in A\) est en relation \(R\) avec \(y \in B\) si \((x,y) \in R\). On le note aussi :

\[x \ R \ y\]

5.3 Relation inverse

A toute relation \(R\), on associe une relation inverse \(R^{-1}\) en intervertissant \(x\) et \(y\) :

\[R^{-1} = \{ (y,x) \in B \times A : (x,y) \in R \}\]

5.4 Relation identité

La relation identité \(\identite \subseteq X \times X\) est définie par :

\[\identite = \{ (x,x) : x \in X \}\]

Elle vérifie la propriété :

\[\identite^{-1} = \identite\]

5.4.1 Egalité

Si \(x = y\), on a \((x,y) \in \identite\) et inversément. L'égalité correspond donc à la relation identité.

5.5 Image

L'image de \(x \in A\) par \(R\) est l'ensemble des éléments de \(B\) en relation avec \(x\) :

\[R(x) = \{ y \in B : (x,y) \in R \}\]

On généralise la notion d'image aux sous-ensembles \(X \subseteq A\) :

\[R(X) = \{ y \in B : x \in X, \ (x,y) \in R \}\]

5.6 Image inverse

L'image inverse de \(y \in B\) est l'ensemble des éléments de \(A\) en relation avec \(y\) :

\[R^{-1}(y) = \{ x \in A : (x,y) \in R \}\]

On généralise la notion d'image inverse aux sous-ensembles \(Y \subseteq B\) :

\[R^{-1}(Y) = \{ x \in A : y \in Y, \ (x,y) \in R \}\]

5.7 Image

Lorsqu'on ne précise pas l'ensemble, l'image de \(R\) est simplement l'image de \(A\) :

\[\image R = R(A)\]

5.8 Domaine

Le domaine de \(R\) est un cas particulier d'image inverse :

\[\domaine R = R^{-1}(B) = \{ x \in A : y \in B, \ (x,y) \in R \}\]

5.9 Composée

A partir d'une relation \(R\) reliant \(A\) à \(B\) et d'une relation \(S\) reliant \(B\) à \(C\), on peut construire une relation composée \(S \circ R\) (lire \(S\) après \(R\)) reliant \(A\) a \(C\). Pour que le couple \((x,z)\) appartienne à \(S \circ R\), on doit pouvoir trouver un élément intermédiaire \(y \in B\) tel que \((x,y) \in R\) et \((y,z)\in S\). Ce \(y\) doit donc appartenir simultanément à \(R(x)\) et à \(S^{-1}(z)\). On a par conséquent :

\[S \circ R = \{ (x,z) \in A \times C : R(x) \cap S^{-1}(z) \ne \emptyset \}\]

ou encore :

\[S \circ R = \{ (x,z) \in A \times C : \exists y \in B : (x,y) \in R, \ (y,z) \in S \}\]

5.10 Puissance

Soit une relation \(R \in \relation(A,A)\). On définit la puissance par :

\begin{align} R^0 &= \identite \\ R^n &= R \circ R^{n-1} \end{align}

On a donc en particulier \(R^1 = R\) et :

\[R^n = R \circ ... \circ R\]

6 Fonctions

6.1 Dépendances

  • Chapitre \ref{chap:ensembles} : Les ensembles
  • Chapitre \ref{chap:relations} : Les relations

6.2 Définitions

Une fonction \(f\) de \(A\) vers \(B\) associe à chaque \(x \in A\) un unique élément \(f(x) \in B\). On note \(\fonction(A,B)\) l'ensemble des fonctions \(f\) de \(A\) vers \(B\). On utilise aussi la notation :

\[f : A \mapsto B\]

pour préciser que \(f \in \fonction(A,B)\) et :

\[f : x \mapsto f(x)\]

pour préciser que \(f\) associe \(x \in A\) à \(f(x) \in B\). On dit que \(f(x)\) est la valeur de \(f\) en \(x\).

6.2.1 Remarque

La notation \(f : A \mapsto B\) signifie que :

  • \(f(x)\) est défini pour tout \(x \in A\)
  • \(f(x) \in B\)

Par conséquent, si \(C \subseteq A\) et si \(B \subseteq D\), la condition \(f : A \mapsto B\) implique \(f : C \mapsto D\).

6.2.2 Synonymes

On parle indifféremment de fonction ou d'application.

6.3 Fonctions discrètes

Dans le cas particulier où \(f \in \fonction( \{ 1,2,...,N \} , B )\), on peut associer à \(f\) un nombre \((f_1,f_2,...,f_N) \in B^N\) par :

\[f_i = f(i)\]

pour tout \(i \in \{ 1,2,...,N \}\). Inversément, à tout \((f_1,f_2,...,f_N) \in B^N\), on associe une fonction \(f : \{ 1,2,...,N \} \mapsto B\) par :

\[f(i) = f_i\]

On voit donc l'équivalence :

\[\fonction( \{ 1,2,...,N \} , B ) \equiv B^N\]

6.3.1 Notation

Dans le cas de fonctions quelconques, on pose par analogie :

\[B^A = \fonction(A,B)\]

6.4 Relation associée

On peut associer à toute fonction \(f : A \mapsto B\) une relation \(R \in \relation(A,B)\) définie par :

\[R = \{ (x,f(x)) : x \in A \}\]

On a clairement :

\[R(x) = \{ f(x) \}\]

6.5 Relation inverse

Soit \(f : A \mapsto B\) associée à la relation \(R \in \relation(A,B)\). La relation inverse \(R^{-1} \in \relation(B,A)\) est définie par :

\[R^{-1} = \{ (f(x),x) \in B \times A : x \in A \}\]

6.6 Fonction identité

La fonction identité \(\identite : A \mapsto A\) est définie par :

\[\identite : x \mapsto \identite(x) = x\]

6.6.1 Relation

La relation associée à la fonction identité s'écrit :

\[\{ (x,\identite(x)) \in A^2 : x \in A \} = \{ (x,x) \in A^2 : x \in A \}\]

La fonction identité est donc associée à la relation identité.

6.7 Image d'un ensemble

Soit \(f : A \mapsto B\). L'image d'un sous-ensemble \(X \subseteq A\) par \(f\) est l'ensemble des valeurs que prend \(f\) en tous les éléments de \(X\) :

\[f(X) = \{ f(x) : x \in X \}\]

6.8 Image d'une fonction

Soit \(f : A \mapsto B\). L'image de \(f\) est l'ensemble des valeurs que prend \(f\) en tous les éléments de \(A\) :

\[\image f = f(A) = \{ f(x) : x \in A \}\]

6.9 Image inverse

Soit \(f : A \mapsto B\). Pour tout \(y \in B\), l'image inverse est l'ensemble défini par :

\[f^{-1}(y) = \{ x \in A : f(x) = y \}\]

L'image inverse d'un ensemble \(Y \subseteq B\) est définie par :

\[f^{-1}(Y) = \{ x \in A : f(x) \in Y \}\]

6.10 Domaine

Soit un ensemble \(A \subseteq \Omega\) et une fonction \(f : A \mapsto B\). Le domaine de \(f\) est l'ensemble des éléments de \(x \in \Omega\) tels que \(f(x) \in B\) existe. Autrement dit :

\[\domaine f = A\]

6.11 Composée

Soit les fonctions \(f : A \mapsto B\) et \(g : B \mapsto C\).

Supposons que les grandeurs \(x \in A\), \(y \in B\) et \(z \in C\) soient reliées par les égalités \(y = f(x)\) et \(z = g(y)\). On a a alors \(z = g\left(f(x)\right)\). On définit une nouvelle fonction \(g \circ f : A \mapsto C\) associée à ce résultat par :

\[g \circ f : x \mapsto (g \circ f)(x) = g\left(f(x)\right)\]

On nomme \(g \circ f\) la composée de \(f\) et \(g\). On note aussi :

\[g \circ f(x) = (g \circ f)(x)\]

6.11.1 Association

Soit aussi \(h : C \mapsto D\). On remarque que :

\[\left(h \circ (g \circ f)\right)(x) = h\left(g\left(f(x)\right)\right) = \left((h \circ g) \circ f\right)(x)\]

On note :

\[h \circ g \circ f = (h \circ (g \circ f)) = ((h \circ g) \circ f)\]

6.11.2 Neutre

On constate que

\[\identite \circ f = f \circ \identite = f\]

On dit que la fonction identité est neutre pour la composition.

6.12 Puissance

Soit une fonction \(f : A \mapsto A\). La « puissance » d'une fonction est définie au moyen de la composée \(\circ\) par :

\begin{align} f^0 &= \identite \\ f^n &= f \circ f^{n-1} \end{align}

pour tout \(n \in \setN\). On a donc en particulier \(f^1 = f\) et :

\[f^n = f \circ ... \circ f\]

6.13 Fonction constante

On associe souvent à tout élément \(c \in B\) une fonction constante \(\hat{c} : A \mapsto B\) définie par :

\[\hat{c}(x) = c\]

pour tout \(x \in A\). On note abusivement :

\[\hat{c} = c\]

6.14 Egalité

Deux fonctions \(f,g : A \mapsto B\) sont égales si et seulement si leurs valeurs sont égales en tout point \(x \in A\) :

\[f = g \quad \Leftrightarrow \quad f(x) = g(x)\]

7 Opérations

7.1 Dépendances

  • Chapitre \ref{chap:fonctions} : Les fonctions

7.2 Introduction

Soit un ensemble \(\Omega\). Une opération \(\opera\) sur \(\Omega\), ou loi de composition interne sur \(\Omega\), est une fonction qui, à deux éléments de \(\Omega\), associe un troisième élément de \(\Omega\) appelé résultat. On a donc formellement :

\[\opera : \Omega \times \Omega \mapsto \Omega\]

Si \(z \in \Omega\) est le résultat de l'opération \(\opera\) sur \(x,y \in \Omega\), on le note :

\[z = x \opera y\]

7.3 Neutre

7.3.1 À gauche

On dit qu'un élément \(n \in \Omega\) est neutre à gauche pour la loi \(\opera\) si :

\[n \opera x = x\]

pour tout \(x \in \Omega\).

7.3.2 À droite

On dit qu'un élément \(n \in \Omega\) est neutre à droite pour la loi \(\opera\) si :

\[x \opera n = x\]

pour tout \(x \in \Omega\).

7.3.3 Simultané

On dit qu'un élément \(n \in \Omega\) est neutre pour la loi \(\opera\) si :

\[x \opera n = n \opera x = x\]

pour tout \(x \in \Omega\).

7.3.4 Unicité

Si \(m,n \in \Omega\) sont des éléments neutres pour \(\opera\), on a :

\[m = m \opera n = n\]

Si un neutre existe, il est unique.

7.4 Inverse

Supposons que \(n \in \Omega\) soit l'unique neutre pour la loi \(\opera\).

7.4.1 À gauche

On dit qu'un élément \(y \in \Omega\) est un inverse à gauche de \(x \in \Omega\) pour la loi \(\opera\) si :

\[y \opera x = n\]

7.4.2 À droite

On dit qu'un élément \(y \in \Omega\) est un inverse à droite de \(x \in \Omega\) pour la loi \(\opera\) si :

\[x \opera y = n\]

7.4.3 Simultané

On dit qu'un élément \(x^\inverse \in \Omega\) est l'inverse de \(x \in \Omega\) pour la loi \(\opera\) si :

\[x \opera x^\inverse = x^\inverse \opera x = n\]

7.5 Associativité

On dit que \(\opera\) est associative si :

\[(x \opera y) \opera z = x \opera (y \opera z)\]

pour tout \(x,y,z \in \Omega\). On définit alors :

\[x \opera y \opera z = x \opera (y \opera z) = (x \opera y) \opera z\]

7.5.1 Extension

Soit \(x_1,x_2,...,x_n \in \Omega\). On définit

7.5.2 Unicité de l'inverse

On suppose que \(\opera\) admet \(n\) comme neutre. Soit \(x \in \Omega\) et \(y,z \in \Omega\) deux inverses de \(x\). On a :

\[y \opera x \opera z = y \opera (x \opera z) = y \opera n = y\]

et :

\[y \opera x \opera z = (y \opera x) \opera z = n \opera z = z\]

On a donc :

\[y = z\]

Dans le cadre d'une opération associative, l'inverse d'un élément donné est unique.

7.6 Commutativité

On dit que \(\opera\) est commutative si :

\[x \opera y = y \opera x\]

pour tout \(x,y \in \Omega\).

7.7 Distributivité

Soit \(\autreaddition, \autremultiplication\) deux lois de composition interne sur \(\Omega\). On dit que \(\autremultiplication\) se distribue sur \(\autreaddition\) si :

\[z \autremultiplication (x \autreaddition y) = (z \autremultiplication x) \autreaddition (z \autremultiplication y)\]

et :

\[(x \autreaddition y) \autremultiplication z = (x \autremultiplication z) \autreaddition (y \autremultiplication z)\]

pour tout \(x,y,z \in \Omega\).

7.8 Opération induite

Soit une opération \(\opera\) définie sur l'ensemble \(\Omega\). L'opération induite par \(\opera\) sur \(\Omega^n\) est définie par :

\[(x_1,x_2,...,x_n) \opera (y_1,y_2,...,y_n) = (x_1 \opera y_1, x_2 \opera y_2, ..., x_n \opera y_n)\]

pour tout :

\[(x_1,x_2,...,x_n), (y_1,y_2,...,y_n) \in \Omega^n\]

On note aussi :

\[z = x \opera y\]

pour :

\[x = (x_1,x_2,...,x_n) \in \Omega^n\]

\[y = (y_1,y_2,...,y_n) \in \Omega^n\]

et :

\[z = (z_1,z_2,...,z_n) \in \Omega^n\]

avec :

\[z_i = x_i \opera y_i\]

pour tout \(i \in \{1,2,...,n\}\).

8 Algèbre

8.1 Dépendances

  • Chapitre \ref{chap:operations} : Les opérations

8.2 Monoïde

Soit un ensemble \(M\) sur lequel est défini une opération \(\opera\). On dit que le couple \((M,\opera)\) est un monoïde si \(\opera\) est associative.

8.2.1 Nomenclature

Lorsque l'opération \(\opera\) est évidente d'après le contexte, on dit simplement que \(M\) est un monoïde.

8.3 Groupes

Soit un ensemble \(G\) sur lequel est défini une opération \(\opera\). On dit que le couple \((G,\opera)\) est un groupe si :

  • \(\opera\) est associative
  • Il existe un neutre pour \(\opera\)
  • Chaque élément de \(G\) possède un inverse pour \(\opera\)

8.3.1 Nomenclature

Lorsque l'opération \(\opera\) est évidente d'après le contexte, on dit simplement que \(G\) est un groupe.

8.3.2 Commutatif

Si \(\opera\) est également commutative, on dit que \((G,\opera)\) est un groupe abélien ou commutatif.

8.4 Monoïde et groupe

Soit un monoïde \((G,\opera)\) tel qu'il existe un neutre à droite \(n \in G\) pour \(\opera\) et que chaque élément \(x \in G\) admet un inverse à droite \(x^\inverse\) pour \(\opera\) :

\[x \opera x^\inverse = n\]

Soit :

\[y = x^\inverse \opera x\]

En utilisant l'associativité de \(\opera\), on se rend compte que :

\[y = x^\inverse \opera n \opera x = x^\inverse \opera x \opera x^\inverse \opera x = y \opera y\]

En utilisant ce résultat, on obtient :

\[y = y \opera n = y \opera y \opera y^\inverse = y \opera y^\inverse = n\]

Donc :

\[x^\inverse \opera x = n\]

et \(x^\inverse\) est un inverse de \(x\). On a aussi :

\[n \opera x = x \opera x^\inverse \opera x = x \opera n = x\]

L'élément \(n\) est donc l'unique neutre de \(G\) et tout élément \(x \in G\) admet un inverse. On en conclut que le couple \((G,\opera)\) est un groupe.

8.5 Anneaux

Soit un ensemble \(A\) sur lequel sont définies les opérations \(\autreaddition\), appelée addition, et l'opération \(\autremultiplication\), appelée multiplication. On dit que le tuple \((A,\autreaddition,\autremultiplication)\) est un anneau si :

  • L'addition est commutative et associative
  • Il existe un neutre pour l'addition
  • Chaque élément de \(A\) possède un inverse pour l'addition appelé opposé
  • La multiplication est associative
  • La multiplication se distribue sur l'addition

8.5.1 Nomenclature

Lorsque les opérations sont évidentes d'après le contexte, on dit simplement que \(A\) est un anneau.

8.5.2 Unitaire

Si la multiplication admet également un neutre, on parle d'anneau unitaire.

8.5.3 Notations

Soit un anneau \(A\). L'addition de \(x,y \in A\) est généralement notée :

\[x + y\]

La multiplication est généralement notée :

\[x \cdot y\]

On désigne généralement par \(0\) le neutre pour l'addition :

\[x + 0 = 0 + x = x\]

Si l'anneau \(A\) est unitaire, on désigne généralement par \(1\) le neutre pour la multiplication :

\[x \cdot 1 = 1 \cdot x = x\]

L'inverse de \(x\) pour l'addition, aussi nommé opposé, est noté \(-x\) :

\[x + (-x) = (-x) + x = 0\]

8.5.4 Intègre

Soit un anneau \((A,+,\cdot)\). Si la relation :

\[a \cdot b = 0\]

implique :

\[a = 0 \ \text{ ou } \ b = 0\]

on dit que \((A,+,\cdot)\) est un anneau intègre.

8.6 Corps

Soit un ensemble \(K\) sur lequel sont définies les opérations \(\autreaddition\), appelée addition, et l'opération \(\autremultiplication\), appelée multiplication. On dit que le tuple \((K,\autreaddition,\autremultiplication)\) est un corps si :

  • L'addition est commutative et associative
  • Il existe un neutre pour l'addition
  • Chaque élément de \(K\) possède un inverse pour l'addition appelé opposé
  • La multiplication est associative
  • Il existe un neutre pour la multiplication
  • Chaque élément de \(K\), à l'exception du neutre pour l'addition,

possède un inverse pour la multiplication appelé inverse

  • La multiplication se distribue sur l'addition

8.6.1 Nomenclature

Lorsque les opérations sont évidentes d'après le contexte, on dit simplement que \(K\) est un corps.

8.6.2 Symbole

On utilise souvent le symbole \(\corps\) pour désigner un corps générique.

8.6.3 Commutatif

Si la multiplication est également commutative, on parle de corps commutatif.

8.6.4 Notations

Soit un corps \(K\). L'addition de \(x,y \in K\) est notée :

\[x + y\]

La multiplication est notée :

\[x \cdot y\]

On désigne généralement par \(0\) le neutre pour l'addition :

\[x + 0 = 0 + x = x\]

et par \(1\) le neutre pour la multiplication :

\[x \cdot 1 = 1 \cdot x = x\]

L'inverse de \(x\) pour l'addition, aussi nommé opposé, est noté \(-x\) :

\[x + (-x) = (-x) + x = 0\]

et l'inverse de \(x\) pour la multiplication est noté \(x^{-1}\) ou \(1/x\) :

\[x \cdot x^{-1} = x^{-1} \cdot x = 1\]

8.7 Soustraction et division

Lorsque l'addition est définie et que \(b\) possède un opposé \(-b\), on définit généralement l'opération de soustraction par :

\[a - b = a + (-b)\]

Lorsque la multiplication est définie et que \(b\) dispose d'un inverse \(b^{-1}\), on définit généralement l'opération de division par :

\[\frac{a}{b} = a \cdot b^{-1}\]

On note aussi :

\[a / b = \frac{a}{b}\]

8.8 Les puissances

On définit généralement les puissances positives par :

\begin{align} x^0 &= 1 \\ x^k &= x \cdot x^{k - 1} \end{align}

pour tout \(k \in \setN\). Si l'inverse de \(x\) existe, on définit généralement les puissances négatives par :

\[x^{-k} = (x^{-1})^k\]

pour tout \(k \in \setN\).

8.9 Somme d'ensembles

Soit l'ensemble \(\Omega\) sur lequel est définie une opération d'addition. On définit la somme de deux sous-ensembles \(A,B \subseteq \Omega\) par :

\[A + B = \{ x + y : (x,y) \in A \times B \}\]

8.9.1 Somme directe

Si, pour tout \(s \in S\), il existe un et un seul couple \((x,y) \in A \times B\) tel que \(s = x + y\), on dit que \(S\) est la somme directe de \(A\) et \(B\) et on le note :

\[S = A \bigoplus B\]

8.10 Multiplication mixte

Soit l'ensemble \(\Omega\) sur lequel est définie une opération de multiplication. On définit la multiplication de \(\lambda \in \Omega\) et de \(A \subseteq \Omega\) par :

\[\lambda \cdot A = \{ \lambda \cdot x : x \in A \}\]

9 Equivalences

9.1 Dépendances

  • Chapitre \ref{chap:relations} : Les relations

9.2 Définition

Une équivalence \(\equiv\) sur un ensemble \(A\) est une relation permettant de regrouper les éléments ayant une caractéristique similaire. Choisissons \(x,y,z \in A\). Tout élément \(x\) étant égal à lui-même, il doit bien entendu être équivalent à lui-même. Notre équivalence doit donc respecter la propriété :

\[x \equiv x\]

Par ailleurs, si \(x\) est équivalent à \(y\), l'inverse doit aussi être vrai :

\[x \equiv y \quad \Rightarrow \quad y \equiv x\]

Il est également clair que si \(x\) est équivalent \(y\) et que \(y\) est équivalent à \(z\), notre \(x\) doit être équivalent à \(z\). Donc :

\[x \equiv y, \quad y \equiv z \quad \Rightarrow \quad x \equiv z\]

9.2.1 Relation

On peut associer une relation \(R\) à toute équivalence en posant :

\[R = \{ (x,y) \in A^2 : x \equiv y \}\]

On a alors \(x \equiv y\) si et seulement si \((x,y) \in R\).

9.2.2 Multiple

La notation \(x \equiv y \equiv z\) signifie que \(x \equiv y\) et que \(y \equiv z\).

9.3 Classe d'équivalence

Soit \(x \in A\). La classe d'équivalence associée à \(x\) est l'ensemble des éléments de \(A\) qui lui sont équivalents :

\[\mathcal{E}(x) = \{ y \in A : y \equiv x \}\]

9.4 Ensemble quotient

Soit la relation \(R \subseteq A^2\) associée à l'équivalence \(\equiv\) définie sur \(A\). L'ensemble quotient de \(A\) par \(R\) est la collection des classes d'équivalence :

\[A / R = \{ \mathcal{E}(x) \in \sousens(A) : x \in A \}\]

9.4.1 Intersection

Soit \(x,y \in A\).

  • Supposons que \(x\) n'est pas équivalent à \(y\) et choisissons un \(z\) dans l'intersection :

\[z \in \mathcal{E}(x) \cap \mathcal{E}(y)\]

On doit donc avoir \(x \equiv z\) et \(z \equiv y\), alors que \(x\) n'est pas équivalent à \(y\), ce qui contredit la définition des équivalences. Par conséquent, un tel \(z\) ne peut pas exister et l'intersection est vide :

\[\mathcal{E}(x) \cap \mathcal{E}(y) = \emptyset\]

  • A présent, supposons que \(x\) est équivalent à \(y\) et choisissons un \(z \in \mathcal{E}(x)\). On a donc \(z \equiv x\) et \(x \equiv y\). On en déduit que \(z \equiv y\), d'où \(z \in \mathcal{E}(y)\) et \(\mathcal{E}(x) \subseteq \mathcal{E}(y)\). Symétriquement, si \(w \in \mathcal{E}(y)\), on a \(w \equiv y\) et \(y \equiv x\), d'où \(w \in \mathcal{E}(x)\) et \(\mathcal{E}(y) \subseteq \mathcal{E}(x)\). On a donc :

\[\mathcal{E}(x) = \mathcal{E}(y)\]

9.4.2 Union

Quel que soit \(x \in A\), tous les éléments de \(\mathcal{E}(x)\) sont dans \(A\) par définition. L'union :

\[E = \bigcup_{x \in A} \mathcal{E}(x)\]

est donc également inclue dans \(A\). D'un autre coté, tout \(x \in A\) étant équivalent à lui-même, chaque \(\mathcal{E}(x)\) contient au moins \(x\). On en conclut que \(A\) est inclus dans \(E\). La double inclusion nous montre que :

\[A = \bigcup_{x \in A} \mathcal{E}(x)\]

9.4.3 Partition

On déduit de ce qui précède que la collection des classes d'équivalences :

\[\mathcal{P} = A / R\]

forme une partition de \(A\). Cette constation explique la terminologie de quotient, liée à celle de division et de partition.

10 Ordres

10.1 Dépendances

  • Chapitre \ref{chap:relations} : Les relations

10.2 Ordre large

Un ordre, ou ordre large, est une relation permettant de déterminer si un élément d'un ensemble est « plus petit ou égal » qu'un autre (on dit aussi « inférieur » à un autre).

Soit \(\le\) un ordre sur l'ensemble \(\Omega\). Choisissons \(x,y,z \in \Omega\). Comme tout élément \(x\) est égal à lui-même, il est forcément « plus petit ou égal » à lui-même, et notre ordre doit respecter la propriété :

\[x \le x\]

Par ailleurs, si \(x\) est plus petit ou égal à \(y\) et que l'inverse est vrai aussi, on doit avoir l'égalité entre les deux éléments :

\[x \le y, \quad y \le x \quad \Rightarrow \quad x = y\]

Il est également clair que si \(x\) est plus petit que \(y\) et que si \(y\) est plus petit que \(z\), \(x\) doit être plus petit que \(z\). Donc :

\[x \le y, \quad y \le z \quad \Rightarrow \quad x \le z\]

10.2.1 Multiple

La notation \(x \le y \le z\) signifie que \(x \le y\) et que \(y \le z\).

10.3 Plus grand ou égal

Soit \(x,y \in \Omega\). On dit que \(x\) est « plus grand ou égal », ou « supérieur » à \(y\), et on le note :

\[x \ge y\]

si et seulement si :

\[y \le x\]

10.4 Relation associée

On peut associer une relation \(R\) à tout ordre en posant :

\[R = \{ (x,y) \in \Omega^2 : x \le y \}\]

On a alors \(x \le y\) si et seulement si \((x,y) \in R\).

10.5 Ordonné

Soit un ensemble \(\Omega\) muni d'un ordre \(\le\). On dit alors que \(\Omega\) est un ensemble ordonné ou que le couple \((\Omega,\le)\) est un espace ordonné.

10.6 Ordre total et partiel

Un ordre \(\le\) sur \(\Omega\) est dit total si pour tout \(x,y \in \Omega\), on a \(x \le y\) ou \(y \le x\). Dans le cas contraire, on dit que l'ordre est partiel.

10.7 Ordre sur un produit cartésien

Soit la collection d'ensembles ordonnés \(A_1,A_2,...,A_n\) et les éléments \(x_i,y_i \in A_i\). On définit un ordre partiel sur les $n$-tuples :

\( x = (x_1,x_2,...,x_n) \\ y = (y_1,y_2,...,y_n) \)

en disant que :

\[x \le y\]

si et seulement si :

\[x_i \le y_i\]

pour tout \(i \in \{ 1,2,...,n \}\).

11 Ordre strict

11.1 Dépendances

  • Chapitre \ref{chap:ordres} : Les ordres

11.2 Définition

Un ordre strict sur un ensemble \(\Omega\) est une relation permettant de déterminer si un élément de \(\Omega\) est « strictement plus petit » qu'un autre. La différence fondamentale avec l'ordre large étant que les deux éléments doivent être distincts.

Soit \(\strictinferieur\) un ordre strict sur l'ensemble \(\Omega\) et \(x,y,z \in \Omega\). Comme \(x\) ne peut pas être distinct de lui-même, {\em on ne peut pas avoir} \(x \strictinferieur x\). La relation \(x \strictinferieur y\) implique donc que \(x \ne y\).

La seule solution pour avoir simultanément $x \strictinferieur y $ et \(y \strictinferieur x\) serait que \(x = y\) comme dans le cas de l'ordre large. Ce n'est pas possible par définition. Les relations \(x \strictinferieur y\) et \(z \strictinferieur x\) impliquent donc que \(y \ne z\). Par contre la propriété :

\( x \strictinferieur y, \quad y \strictinferieur z \quad \Rightarrow \quad x \strictinferieur z \)

est analogue à celle de l'ordre large.

11.2.1 Multiple

La notation \(x \strictinferieur y \strictinferieur z\) signifie que \(x \strictinferieur y\) et que \(y \strictinferieur z\).

11.3 Plus grand

Soit \(x, y \in \Omega\). On dit que \(x\) est strictement plus grand que \(y\), et on le note :

\[x \strictsuperieur y\]

si et seulement si :

\[y \strictinferieur x\]

11.4 Dérivé du large

On peut définir un ordre strict à partir d'un ordre large en disant que \(x \strictinferieur y\) si et seulement si \(x \le y\) et \(x \ne y\).

11.5 Complémentarité

Supposons que l'ordre \(\le\) soit total. Si \(x,y\) ne vérifient pas \(x \le y\), on doit forcément avoir \(y \le x\). Si on avait \(x = y\), on aurait aussi \(x \le y\) ce qui contredit l'hypothèse. Par conséquent, on doit avoir \(x \ne y\). On en déduit que \(y \strictinferieur x\).

Réciproquement, si la condition \(y \strictinferieur x\) n'est pas vérifiée, on a soit \(x = y\), soit \(x \le y\). Mais comme \(x \le y\) inclut la possibilité que \(x = y\), on a simplement \(x \le y\).

On a donc soit \(x \le y\), soit \(x \strictsuperieur y\). Ou encore, soit \(x \strictinferieur y\), soit \(x = y\), soit \(x \strictsuperieur y\).

12 Extrema

12.1 Dépendances

  • Chapitre \ref{chap:relations} : Les relations
  • Chapitre \ref{chap:ordres} : Les ordres

12.2 Comparaison élément - ensemble

Soit \(\le\) un ordre sur l'ensemble \(\Omega\) et \(A \subseteq \Omega\). Nous dirons qu'un objet \(m \in \Omega\) est inférieur à l'ensemble \(A\), ou que \(m\) est un minorant de \(A\), et nous le noterons :

\[m \le A\]

si \(m \le a\) pour tout élément \(a \in A\). Inversément, nous dirons que \(m\) est supérieur à \(A\), ou que \(m\) est un majorant de \(A\), et nous le noterons :

\[m \ge A\]

si \(m \ge a\) pour tout élément \(a \in A\) :

12.3 Comparaison ensemble - ensemble

12.3.1 En-dessous

Soit \(\le\) un ordre sur l'ensemble \(\Omega\) et \(A,B \subseteq \Omega\). Nous dirons que \(A\) est en-dessous de l'ensemble \(B\), et nous le noterons :

\[A \ensinferieur B\]

si tout élément \(a \in A\) vérifie \(a \le B\). Cela revient à imposer l'inégalité :

\[a \le b\]

pour tout couple \((a,b) \in A \times B\).

12.3.2 Au-dessus

On dit que \(A\) est au-dessus de l'ensemble \(B\), et on le note :

\[A \enssuperieur B\]

si et seulement si :

\[B \ensinferieur A\]

Cela revient à imposer l'inégalité :

\[a \ge b\]

pour tout couple \((a,b) \in A \times B\).

12.3.3 Remarque

Attention, ces comparaisons ne constituent pas un ordre. En particulier, un ensemble quelconque n'est en général ni au-dessus ni en-dessous de lui-même.

12.4 Majorants et minorants

Soit \(\le\) un ordre sur l'ensemble de référence \(\Omega\) et \(A \subseteq \Omega\). L'ensemble des majorants de \(A\) est l'ensemble des éléments de \(\Omega\) supérieurs à A :

\[\major A = \{ m \in \Omega : m \ge A \}\]

Si \(\major A \ne \emptyset\), on dit que \(A\) est majoré ou encore que \(A\) est borné supérieurement. L'ensemble des minorants de \(A\) est l'ensemble des éléments de \(\Omega\) inférieurs à A :

\[\minor A = \{ m \in \Omega : m \le A \}\]

Si \(\minor A \ne \emptyset\), on dit que \(A\) est minoré ou encore que \(A\) est borné inférieurement.

12.4.1 Préciser l'ordre

Lorsqu'on veut préciser l'ordre \(\le\) utilisé, on note :

\( \major_\le A = \{ m \in \Omega : m \ge A \} \\ \\ \minor_\le A = \{ m \in \Omega : m \le A \} \)

12.4.2 Comparaisons d'ensembles

On se rend compte que si \(B \subseteq \Omega\) vérifie \(B \enssuperieur A\), tous les éléments de \(B\) sont dans l'ensemble des majorants :

\[B \enssuperieur A \ \Rightarrow \ B \subseteq \major A\]

Inversément, si \(B\) est en-dessous de \(A\), tous ses éléments sont dans l'ensemble des minorants :

\[B \ensinferieur A \ \Rightarrow \ B \subseteq \minor A\]

12.5 Éléments maximaux et minimaux

On dit d'un élément \(M \in A\) qu'il est maximal dans \(A\) si pour tout \(a \in A\) vérifiant \(a \ge M\), on a \(M = a\). Autrement dit, aucun élément de \(A\) distinct de \(M\) n'est supérieur à ce dernier. \(M\) est donc le seul élément de \(A\) à être supérieur (au sens large) à lui-même. On a donc \(\major \{ M \} \cap A = \{ M \}\). On note \(\maxim A\) l'ensemble des éléments maximaux de \(A\) :

\[\maxim A = \Big\{ M \in A : \major \{ M \} \cap A = \{ M \} \Big\}\]

Symétriquement, on dit d'un élément \(m \in A\) qu'il est minimal dans \(A\) si pour tout \(a \in A\) vérifiant \(a \le m\), on a \(m = a\). Autrement dit, aucun élément de \(A\) distinct de \(m\) n'est inférieur à ce dernier. \(m\) est donc le seul élément de \(A\) à être inférieur (au sens large) à lui-même. On a donc \(\minor \{ m \} \cap A = \{ m \}\). On note \(\minim A\) l'ensemble des éléments minimaux de \(A\) :

\[\minim A = \Big\{ m \in A : \minor \{ m \} \cap A = \{ m \} \Big\}\]

12.5.1 Préciser l'ordre

Lorsqu'on veut préciser l'ordre \(\le\) utilisé, on note :

\( \maxim_\le A \\ \\ \minim_\le A \)

12.6 Maximum et minimum

Considérons le cas où l'on peut trouver des majorants de \(A\) appartenant à \(A\). Si \(x,y \in A \cap \major A\), on a \(x \ge y\) puisque \(x\) est un majorant de \(A\) et que \(y \in A\). Mais on a aussi \(y \ge x\) puisque \(y\) est également un majorant de \(A\) et que \(x \in A\). On en conclut que \(x = y\) et que l'intersection ne contient qu'un seul élément \(M\) :

\[A \cap \major A = \{ M \}\]

On dit alors que \(M \in A\) est le maximum de l'ensemble \(A\) et on le note :

\[M = \max A = \max_{a \in A} a\]

A présent, supposons que l'on puisse trouver des minorants de \(A\) appartenant à \(A\). Supposons que \(x,y \in A \cap \minor A\). On a alors \(x \le y\) puisque \(x\) est un minorant de \(A\) et que \(y \in A\). Mais on a aussi \(y \le x\) puisque \(y\) est également un minorant de \(A\) et que \(x \in A\). On en conclut que \(x = y\). L'intersection ne contient donc qu'un seul élément \(m\) :

\[A \cap \minor A = \{ m \}\]

On dit alors que \(m\) est le minimum de l'ensemble \(A\) et on le note :

\[m = \min A = \min_{a \in A} a\]

12.6.1 Préciser l'ordre

Lorsqu'on veut préciser l'ordre \(\le\) utilisé, on note plutôt :

\( \max_\le A = \max A \\ \\ \min_\le A = \min A \)

12.6.2 Maximal et minimal

Supposons que \(M = \max A\) existe. On a \(M \in A\). Soit \(a \in A\) vérifiant \(M \le a\). Par définition du maximum, on a aussi \(M \ge a\), d'où \(M = a\). On en conclut que le maximum est un élément maximal. A présent, soit \(x \in \maxim A\). Comme \(x \le M\), on en conclut que \(x = M\). On a donc :

\[\maxim A = \{ \max A \}\]

Supposons que \(m = \min A\) existe. On a \(m \in A\). Soit \(a \in A\) vérifiant \(m \ge a\). Par définition du minimum, on a aussi \(m \le a\), d'où \(m = a\). On en conclut que le minimum est un élément minimal. A présent, soit \(x \in \minim A\). Comme \(x \ge m\), on en conclut que \(x = m\). On a donc :

\[\minim A = \{ \min A \}\]

12.7 Supremum et infimum

Soit un ensemble \(A \subseteq \Omega\) dont le maximum \(M = \max A\) existe et l'élément \(b \in \Omega\) tel que \(b \ge A\). Comme \(M\) est un élément de \(A\), on a forcément \(b \ge M\). Mais d'un autre coté, \(M \ge A\) par définition. Donc :

\[b \ge M \ge A\]

Comme ces relations sont valables pour tout les \(b\) supérieurs à \(A\), on en conclut que :

\[\major A \ge M \ge A\]

Relations qui nous disent que \(M\) est le plus petit des objets supérieurs à \(A\). Considérons à présent un cas plus général où nous ne supposons pas que le maximum de \(A\) existe. Supposons seulement que l'on puisse trouver un \(S \in \Omega\) tel que :

\[\major A \ge S \ge A\]

La première inégalité nous dit que \(S\) est un minorant de \(\major A\). La seconde nous dit que \(S\) est un majorant de \(A\), autrement dit \(S \in \major A\). Les deux conditions nous permettent d'affirmer que \(S\) est le minimum de l'ensemble des majorants de \(A\) :

\[S = \min \major A\]

Cet élément \(S\) est donc unique. On l'appelle supremum et on le note :

\[S = \sup A = \sup_{a \in A} a = \min \major A\]

Il est important de remarquer que \(S\) n'appartient pas forcément à \(A\). On procéde de la même façon pour étendre la notion de minimum. Si on peut trouver un \(I \in \Omega\) tel que :

\[\minor A \le I \le A\]

on en conclut que \(I\) est le maximum de l'ensemble des minorants de \(A\) et qu'il est donc unique. On l'appelle infimum et on le note :

\[I = \inf A = \inf_{a \in A} a = \max \minor A\]

12.7.1 Préciser l'ordre

Lorsqu'on veut préciser l'ordre \(\le\) utilisé, on note :

\( \sup_\le A = \min \major A \\ \\ \inf_\le A = \max \minor A \)

12.7.2 Comparaison des bornes

Si \(A\) est non vide, il suffit de choisir \(x \in A\) pour se rendre compte que :

\[\inf A \le x \le \sup A\]

d'où :

\[\inf A \le \sup A\]

12.7.3 Cas particulier

Dans le cas où le maximum de \(A\) existe, on a par unicité \(\sup A = \max A\). Dans le cas où le minimum de \(A\) existe, on a par unicité \(\inf A = \min A\).

12.8 Ensembles finis

Nous allons montrer que, sous l'hypothèse d'un ordre total, tout ensemble comportant un nombre fini d'éléments admet un maximum et un minimum. Si l'ensemble ne contient qu'un élément, soit \(A_1 = \{a\}\), on a \(a \le a\) et donc :

\[a = \max\{a\} = \min\{a\}\]

Supposons à présent que l'ensemble comporte deux éléments, soit \(A_2 = \{a_1,a_2\}\). Si \(a_1 \ge a_2\), on a \(a_1 \ge \{a_1,a_2\}\). Dans le cas contraire, on a \(a_2 \ge \{a_1,a_2\}\). On en déduit que :

\( max\{a1,a2\} =

\begin{cases} a_1 & \text{ si } a_1 \ge a_2 \\ a_2 & \text{ sinon} \end{cases}

\)

Le minimum est donné par l'expression duale :

\( min\{a1,a2\} =

\begin{cases} a_1 & \text{ si } a_1 \le a_2 \\ a_2 & \text{ sinon} \end{cases}

\)

Supposons à présent avoir démontré que tout ensemble de \(n - 1\) éléments admettait un maximum et un minimum. Soit l'ensemble \(A = \{a_1,a_2,...,a_{n - 1},a_n\}\) comportant \(n\) éléments. L'ensemble \(A_{n - 1} = \{a_1,a_2,...,a_{n - 1}\}\) contient \(n - 1\) éléments et admet donc :

\( \sigma = \max \{a_1,a_2,...,a_{n - 1}\} \\ \lambda = \min \{a_1,a_2,...,a_{n - 1}\} \)

Posons \(\alpha = \max\{\sigma,a_n\}\). On voit que \(\alpha \in A\), que \(\alpha \ge \sigma \ge A_{n - 1}\) et que \(\alpha \ge a_n\). On en déduit que \(\alpha \ge A\). Donc :

\[\max \{a_1,a_2,...,a_{n - 1},a_n\} = \max \Big\{ \max \{a_1,a_2,...,a_{n - 1}\} , a_n \Big\}\]

Posons \(\beta = \min\{\lambda,a_n\}\). On voit que \(\beta \in A\), que \(\beta \le \lambda \le A_{n - 1}\) et que \(\beta \le a_n\). On en déduit que \(\beta \le A\). Donc :

\[\min \{a_1,a_2,...,a_{n - 1},a_n\} = \min \Big\{ \min \{a_1,a_2,...,a_{n - 1}\} , a_n \Big\}\]

Tout ensemble comportant un nombre fini d'éléments et sur lequel est défini un ordre total admet donc un maximum et un minimum. De plus, la démonstration nous donne un moyen d'évaluer récursivement ces extrema.

12.8.1 Notations

On note aussi :

\( \max_{i = 1}^n a_i = \max \{ a_1,a_2,...,a_n \} \\ \\ \min_{i = 1}^n a_i = \min \{ a_1,a_2,...,a_n \} \)

12.9 Infini

Il arrive qu'aucun élément de \(\Omega\) ne soit un majorant de \(\Omega\). On est alors amené à ajouter à l'ensemble une borne supérieure, notée \(+\infty\) (ou \(\infty\)), telle que tout élément \(a \in \Omega\) vérifie \(a \strictinferieur +\infty\). Le concept de l'infini négatif, noté \(-\infty\), est similaire. Il s'agit d'une borne inférieure de \(\Omega\) telle que tout élément \(a \in \Omega\) vérifie \(a \strictsuperieur -\infty\).

12.9.1 Supremum et infimum

Lorsque l'ensemble des majorants de \(A\) est vide, le supremum n'existe pas. On dit alors qu'il est infini et on le note :

\[\sup A = +\infty\]

Lorsque l'ensemble des minorants de \(A\) est vide, l'infimum n'existe pas. On dit alors qu'il est infini et on le note :

\[\inf A = -\infty\]

12.10 Ordre et inclusion

Soit \(A,B \subseteq \Omega\) avec \(A \subseteq B\). Soit l'ordre \(\le\) défini sur \(\Omega\).

12.10.1 Max - Min

Supposons que les maxima existent. Le maximum de \(A\) étant dans \(A\), il est aussi dans \(B\). Par conséquent, le maximum de \(B\) est supérieur au maximum de \(A\) :

\[\max A \le \max B\]

En suivant le même raisonnement avec les minima, on obtient :

\[\min A \ge \min B\]

12.10.2 Sup - Inf

A présent, ne supposons plus l'existence des maxima ou des minima, mais seulement des supremums et infimums. Tout majorant de \(B\) sera aussi un majorant de \(A\). On a donc :

\[\major B \subseteq \major A\]

L'ensemble \(\major B\) étant inclus dans \(\major A\), son minimum doit être supérieur, et on a :

\[\sup A \le \sup B\]

En répétant le même raisonnement avec les minorants, on obtient :

\[\inf A \ge \inf B\]

12.11 Ordre, union et intersection

12.11.1 Max - Min de l'union

Supposons que les maxima de \(A\) et \(B\) existent. Si l'ordre est total, on a soit \(\max A \le \max B\), soit \(\max B \le \max A\). Le maximum :

\[M = \max \{ \max A , \max B \}\]

existe donc. On voit que \(M\) appartient à \(A\) ou à \(B\) suivant les cas, c'est-à-dire à \(A \cup B\) et que :

\( x \le \max A \le M \\ y \le \max B \le M \)

pour tout \(x \in A\) et \(y \in B\). On en conclut que \(M\) majore \(A \cup B\). On a donc :

\[\max \{ \max A , \max B \} = \max (A \cup B)\]

En suivant le même raisonnement avec les minima, on obtient :

\[\min \{ \min A , \min B \} = \min (A \cup B)\]

12.11.2 Max - Min de l'intersection

Supposons que les maxima de \(A\) et \(B\) existent et que leur intersection soit non vide :

\[A \cap B \ne \emptyset\]

Si l'ordre est total, on a soit \(\max A \le \max B\), soit \(\max B \le \max A\). Le minimum :

\[m = \min \{ \max A , \max B \}\]

existe donc. On voit que pour tout \(x \in A \cap B\) :

\( x \in A \ \Rightarrow \ x \le \max A \\ x \in B \ \Rightarrow \ x \le \max B \)

On en conclut que \(x \le m\). L'élément \(m\) est donc un majorant de \(A \cap B\). Si le maximum de l'intersection existe, on a donc :

\[\max (A \cap B) \le \min \{ \max A , \max B \}\]

En suivant le même raisonnement avec les minima, on obtient :

\[\min (A \cap B) \ge \max \{ \min A , \min B \}\]

12.11.3 Sup - Inf de l'union

A présent, ne supposons plus l'existence des maxima ou des minima, mais seulement des supremums et infimums. Comme les majorant de \(A \cup B\) sont ceux qui majorent tous les éléments de \(A\) et tous les éléments de \(B\), on a :

\[\major (A \cup B) = (\major A) \cap (\major B)\]

Il ne nous reste plus qu'à minimiser les deux membres de cette égalité. Le minimum de l'intersection étant supérieure au maximum des minima, on a :

\[\min \Big[ (\major A) \cap (\major B) \Big] \ge \max \{ \min \major A , \min \major B \}\]

et :

\[\min \major (A \cup B) \ge \max \{ \min \major A , \min \major B \}\]

c'est-à-dire :

\[\sup (A \cup B) \ge \max \{ \sup A , \sup B \}\]

En répétant le même raisonnement avec les minorants, on obtient :

\[\minor (A \cup B) = (\minor A) \cap (\minor B)\]

et :

\[\inf (A \cup B) \le \min \{ \inf A , \inf B \}\]

12.11.4 Sup - Inf de l'intersection

Soit \(x \in A \cap B\) et \(M \in (\major A) \cup (\major B)\). On a soit :

  • \(M \in \major A\) et alors \(M \ge x\) car \(x \in A\)
  • \(M \in \major B\) et alors \(M \ge x\) car \(x \in B\)

On en déduit que :

\[(\major A) \cup (\major B) \subseteq \major (A \cap B)\]

Le minimum d'un ensemble inclus dans un autre devant être plus grand, on obtient :

\[\min \Big[ (\major A) \cup (\major B) \Big] \ge \min \major (A \cap B)\]

Comme le minimum de l'union est égal au minimum des minima, on a :

\[\min \Big[ (\major A) \cup (\major B) \Big] = \min \{ \min (\major A) , \min (\major B) \}\]

et :

\[\min \major (A \cap B) \le \min \{ \min (\major A) , \min (\major B) \}\]

On a donc par définition :

\[\sup (A \cap B) \le \min \{ \sup A , \sup B \}\]

En répétant le même raisonnement avec les minorants, on obtient :

\[\inf (A \cap B) \ge \max \{ \inf A , \inf B \}\]

13 Dualité

13.1 Dépendances

  • Chapitre \ref{chap:ordres} : Les ordres

13.2 Ordre dual

Soit un ensemble \(\Omega\) sur lequel est défini un ordre \(\le\). Soit \(x,y \in \Omega\). L'ordre dual de \(\le\), noté \(\le^\dual\), est défini par :

\[x \le^\dual y\]

si et seulement si :

\[y \le x\]

13.2.1 Ordre primal

Par opposition à l'ordre dual \(\le^\dual\), l'ordre \(\le\) est appelé ordre primal.

13.3 Comparaison élément - ensemble

Soit \(A \subseteq \Omega\) et un \(m \in \Omega\) vérifiant \(m \le A\). On a \(m \le a\) pour tout \(a \in A\), autrement dit \(m \ge^\dual a\). On en conclut que :

\[m \ge^\dual A\]

Soit \(m \in \Omega\) vérifiant \(m \ge A\). On a \(m \ge a\) pour tout \(a \in A\), autrement dit \(m \le^\dual a\). On en conclut que :

\[m \le^\dual A\]

13.4 Majorants et minorants

Soit \(A \subseteq \Omega\). Si :

\[m \in \minor_\le A\]

on a \(m \le A\). Donc \(m \ge^\dual A\) et :

\[m \in \major_{\le^\dual} A\]

Si :

\[m \in \major_{\le^\dual} A\]

on a \(m \ge A\). Donc \(m \le^\dual A\) et :

\[m \in \minor_\le A\]

On en conclut que :

\[\major_{\le^\dual} A = \minor_\le A\]

On montre avec des arguments similaires que :

\[\minor_{\le^\dual} A = \major_\le A\]

13.5 Éléments maximaux et minimaux

Soit \(A \subseteq \Omega\). Si :

\[m \in \minim_\le A\]

on a \(m = a\) pour tout \(a \in A\) vérifiant \(a \le m\). Donc, si \(a \ge^\dual m\) on a \(a \le m\) et \(m = a\). Autrement dit :

\[m \in \maxim_{\le^\dual} A\]

Si :

\[m \in \maxim_{\le^\dual} A\]

on a \(m = a\) pour tout \(a \in A\) vérifiant \(a \ge^\dual m\). Donc, si \(a \le m\) on a \(a \ge^\dual m\) et \(m = a\). Autrement dit :

\[m \in \minim_\le A\]

On en conclut que :

\[\maxim_{\le^\dual} A = \minim_\le A\]

On montre avec des arguments similaires que :

\[\minim_{\le^\dual} A = \maxim_\le A\]

13.6 Maximum et minimum

Soit \(A \subseteq \Omega\). Si l'ensemble des éléments minimaux pour \(\le\) se limite au minimum, on a :

\[\maxim_{\le^\dual} A = \minim_\le A = \left{ \min_\le A \right}\]

L'ensemble des éléments maximaux pour \(\le^\dual\) se résumant à un singleton, on en déduit que le maximum pour \(\le^\dual\) existe :

\[\maxim_{\le^\dual} A = \left{ \max_{\le^\dual} A \right}\]

et que :

\[\max_{\le^\dual} A = \min_\le A\]

On montre avec des arguments similaires que :

\[\min_{\le^\dual} A = \max_\le A\]

13.7 Supremum et Infimum

Soit \(A \subseteq \Omega\) admettant le supremum :

\[m = \sup_{\le^\dual} A\]

On a :

\[A \le^\dual m \le^\dual \major_{\le^\dual} A\]

ce qui implique :

\[\minor_\le A = \major_{\le^\dual} A \le m \le A\]

et vice versa. On en déduit que :

\[\sup_{\le^\dual} A = \inf_\le A\]

On montre avec des arguments similaires que :

\[\inf_{\le^\dual} A = \sup_\le A\]

14 Fonctions et ordre

14.1 Dépendances

  • Chapitre \ref{chap:ordres} : Les ordres
  • Chapitre \ref{chap:extrema} : Les extrema

14.2 Monotonie

14.2.1 Croissance

On dit qu'une fonction \(f : A \to F\) est croissante si :

\[f(x) \ge f(y)\]

pour tout \(x,y \in A\) tels que \(x \ge y\). Autrement dit, une fonction croissante conserve l'ordre.

14.2.2 Décroissance

On dit qu'une fonction \(f : A \to F\) est décroissante si :

\[f(x) \le f(y)\]

pour tout \(x,y \in A\) tels que \(x \ge y\). Autrement dit, une fonction décroissante inverse l'ordre.

14.2.3 Stricte

On dit qu'une fonction \(f : A \to F\) est strictement croissante si :

\[f(x) \strictinferieur f(y)\]

pour tout \(x,y \in A\) tels que \(x \strictinferieur y\).

On dit qu'une fonction \(f : A \to F\) est strictement décroissante si :

\[f(x) \strictsuperieur f(y)\]

pour tout \(x,y \in A\) tels que \(x \strictinferieur y\).

14.3 Ordre entre fonctions

Soit les fonctions \(f,g \in B^A\). Supposons qu'il existe un ordre défini sur \(B\). On dit que \(f\) est inférieure à \(g\) et on le note :

\[f \le g\]

si et seulement si les valeurs de \(f\) sont inférieures aux valeurs de \(g\) :

\[f(x) \le g(x)\]

en tout point \(x \in A\). Symétriquement, on dit que \(f\) est supérieure à \(g\) et on le note :

\[f \ge g\]

si :

\[f(x) \ge g(x)\]

pour tout \(x \in A\).

14.3.1 Strict

On note également :

  • \(f \strictinferieur g\) si \(f(x) \strictinferieur g(x)\) pour tout \(x \in A\)
  • \(f \strictsuperieur g\) si \(f(x) \strictsuperieur g(x)\) pour tout \(x \in A\)

14.4 Fonctions extrema

Soit un ensemble de paramètres \(Z\) et la collection paramétrée de fonctions :

\[\{ f_z \in B^A : z \in Z \}\]

Sous réserve d'existence des extrema, on définit la fonction supremum par :

\[\left[ \sup_{z \in Z} f_z \right](x) = \sup_{z \in Z} f_z(x)\]

pour tout \(x \in A\). On définit la fonction infimum par :

\[\left[ \inf_{z \in Z} f_z \right](x) = \inf_{z \in Z} f_z(x)\]

pour tout \(x \in A\).

14.4.1 Maximum et minimum

Lorsque les maximum et minimum existent, on définit :

\( \left[ \max_{z \in Z} f_z \right](x) = \max_{z \in Z} f_z(x) \\ \\ \left[ \min_{z \in Z} f_z \right](x) = \min_{z \in Z} f_z(x) \)

14.4.2 Notation

On note aussi :

\( \sup \{ f_z : z \in Z \} = \sup_{z \in Z} f_z \\ \\ \inf \{ f_z : z \in Z \} = \inf_{z \in Z} f_z \\ \\ \max \{ f_z : z \in Z \} = \max_{z \in Z} f_z \\ \\ \min \{ f_z : z \in Z \} = \min_{z \in Z} f_z \)

14.4.3 Couples

On définit les fonctions \(M = \max\{f,g\}\) et \(m = \min\{f,g\}\) par :

\( M(x) = \max\{ f , g \}(x) = \max\{ f(x) , g(x) \} \\ m(x) = \min\{ f , g \}(x) = \min\{ f(x) , g(x) \} \)

pour tout \(x \in A\).

14.5 Ordre mixte

Soit la fonction \(f \in B^A\) et un \(c \in B\). Supposons qu'il existe un ordre défini sur \(B\). On dit que \(f\) est inférieure à \(c\) et on le note :

\[f \le c\]

si les valeurs de \(f\) sont inférieures à \(c\) :

\[f(x) \le c\]

en tout point \(x \in A\). Symétriquement, on dit que \(f\) est supérieure à \(c\) et on le note :

\[f \ge c\]

si :

\[f(x) \ge c\]

pour tout \(x \in A\).

14.5.1 Strict

On note également :

  • \(f \strictinferieur c\) si \(f(x) \strictinferieur c\) pour tout \(x \in A\).
  • \(f \strictsuperieur c\) si \(f(x) \strictsuperieur c\) pour tout \(x \in A\).

14.5.2 Fonctions max et min

On définit les fonctions \(\max\{f,c\}\) et \(\min\{f,c\}\) par :

\( \max\{ f , c \}(x) = \max\{ f(x) , c \} \\ \min\{ f , c \}(x) = \min\{ f(x) , c \} \)

pour tout \(x \in A\).

14.6 Extrema d'une fonction

Etant donné la fonction \(f : \Omega \mapsto B\) et le sous-ensemble \(A \subseteq \Omega\), on définit les extrema de \(f\) (s'ils existent) par :

\( \max_{x \in A} f(x) = \max \{ f(x) : x \in A \} \\ \\ \min_{x \in A} f(x) = \min \{ f(x) : x \in A \} \\ \\ \sup_{x \in A} f(x) = \sup \{ f(x) : x \in A \} \\ \\ \inf_{x \in A} f(x) = \inf \{ f(x) : x \in A \} \)

14.7 Arguments d'extrema

14.7.1 Maximum et minimum

L'ensemble des éléments de \(A\) qui maximisent \(f\) sur \(A\) est noté :

\[\arg\max_{x \in A} f(x) = \left\{ \alpha \in A : f(\alpha) = \max_{x \in A} f(x) \right\}\]

Dans le cas où cet ensemble contient un unique élément, on le note :

\[\alpha = \arg\max_{x \in A} f(x)\]

L'ensemble des éléments de \(A\) qui minimisent \(f\) sur \(A\) est noté :

\[\arg\min_{x \in A} f(x) = \left\{ \beta \in A : f(\beta) = \min_{x \in A} f(x) \right\}\]

Dans le cas où cet ensemble contient un unique élément, on le note :

\[\beta = \arg\min_{x \in A} f(x)\]

14.7.2 Supremum et infimum

L'ensemble des éléments de \(\Omega\) qui produisent une valeur égale au supremum des valeurs de \(f\) sur \(A \subseteq \Omega\) est noté :

\[\argument_\Omega\sup_{x \in A} f(x) = \left\{ \alpha \in \Omega : f(\alpha) = \sup_{x \in A} f(x) \right\}\]

Dans le cas où cet ensemble contient un unique élément, on le note :

\[\alpha = \argument_\Omega\sup_{x \in A} f(x)\]

L'ensemble des éléments de \(\Omega\) qui produisent une valeur égale à l'infimum des valeurs de \(f\) sur \(A \subseteq \Omega\) est noté :

\[\argument_\Omega\inf_{x \in A} f(x) = \left\{ \beta \in \Omega : f(\beta) = \inf_{x \in A} f(x) \right\}\]

Dans le cas où cet ensemble contient un unique élément, on le note :

\[\beta = \argument_\Omega\inf_{x \in A} f(x)\]

14.8 Extrema locaux

On dit que \(f\) atteint un minimum local en \(a \in A\) si il existe un voisinage \(U\) de \(x\) tel que :

\[f(a) \le f(x)\]

pour tout \(x \in U\). A l'inverse, on dit que \(f\) atteint un maximum local en \(a \in A\) si il existe un voisinage \(U\) de \(x\) tel que :

\[f(a) \ge f(x)\]

pour tout \(x \in U\).

14.9 Ordre entre fonctions et extrema

Soit les fonctions \(f,g : A \mapsto B\) telles que \(f \le g\). Supposons que \(\sigma \in \major g(A)\). On a \(\sigma \ge g(x) \ge f(x)\) pour tout \(x \in A\), d'où \(\sigma \ge f(x)\) et \(\sigma \in \major f(A)\). On en conclut que \(\major g(A) \subseteq \major f(A)\). Si les minima existent, on a donc :

\[\min \major f(A) \le \min \major g(A)\]

c'est-à-dire :

\[\sup_{x \in A} f(x) = \sup f(A) \le \sup g(A) = \sup_{x \in A} g(x)\]

Supposons que \(\lambda \in \minor f(A)\). On a \(\lambda \le f(x) \le g(x)\) pour tout \(x \in A\), d'où \(\lambda \le g(x)\) et \(\lambda \in \minor g(A)\). On en conclut que \(\minor f(A) \subseteq \minor g(A)\). Si les maxima existent, on a donc :

\[\max \minor f(A) \le \max \minor g(A)\]

c'est-à-dire :

\[\inf_{x \in A} f(x) = \inf f(A) \le \inf g(A) = \inf_{x \in A} g(x)\]

15 Bijections

15.1 Dépendances

  • Chapitre \ref{chap:fonctionsEtOrdre} : Fonctions et ordre

15.2 Inverse à gauche

Soit \(f : A \mapsto B\). Si \(l : B \mapsto A\) est une fonction telle que :

\[l \circ f = \identite\]

on dit que \(l\) est un inverse à gauche de \(f\).

15.2.1 Unicité

Soit \(y \in B\). Si \(f\) admet un inverse à gauche, on peut trouver au plus un seul \(x \in A\) tel que \(f(x) = y\). En effet, supposons que \(x_1, x_2 \in A\) avec \(f(x_1) = f(x_2) = y\). On a :

\[l(y) = (l \circ f)(x_1) = (l \circ f)(x_2)\]

mais comme \(l \circ f = \identite\), et que \(\identite(x) = x\) pour tout \(x \in A\), on a :

\[l(y) = x_1 = x_2\]

ce qui prouve l'unicité de la solution.

15.3 Inverse à droite

Soit \(f : A \mapsto B\). Si \(r : B \mapsto A\) est une fonction telle que :

\[f \circ r = \identite\]

on dit que \(r\) est un inverse à droite de \(f\).

15.3.1 Existence

Soit \(y \in B\). Si \(f\) admet un inverse à droite \(r\), on peut trouver au moins un \(x \in A\) tel que \(f(x) = y\). En effet, si l'on choisit \(x = r(y)\), on a :

\[f(x) = (f \circ r)(y) = \identite(y) = y\]

ce qui prouve l'existence de la solution.

15.4 Fonction inverse

Soit \(f : A \mapsto B\). Supposons que \(f\) admette à la fois un inverse à gauche \(l\) et un inverse à droite \(r\). Ces deux inverses sont dès lors identiques :

\[l = l \circ \identite = l \circ f \circ r = \identite \circ r = r\]

15.4.1 Existence et unicité

Soit \(y \in B\). On déduit des résultats précédents que l'on peut trouver un unique \(x \in A\), donné par \(x = r(y)\), tel que \(f(x) = y\). Nous pouvons dès lors définir la fonction inverse, notée \(f^{-1} : B \mapsto A\), par :

\[f^{-1}(y) = r(y)\]

pour tout \(y \in B\). On a donc :

\[f^{-1} = r = l\]

et :

\[f^{-1} \circ f = f \circ f^{-1} = \identite\]

15.4.2 Bijection

Lorsque \(f\) admet un inverse \(f^{-1}\), on dit que \(f\) est inversible ou que \(f\) est une bijection. On note :

\[\bijection(A,B) = \{ f \in B^A : \exists f^{-1} \in A^B \}\]

l'ensemble des bijections de \(A\) vers \(B\).

15.5 Relation

Lorsque \(f\) est inversible, l'image inverse de \(y \in B\) se réduit à un ensemble contenant un unique \(x \in A\). Soit \(R\) la relation associée à \(f\). On a :

\[R^{-1}(y) = \{ f^{-1}(y) \}\]

15.6 Inverse d'une composée

Soit \(f \in \bijection(A,B)\) et \(g \in \bijection(B,C)\). Nous allons essayer de trouver une expression de l'inverse \(h\) de la composée de ces deux fonctions. On part de la relation \(h \circ g \circ f = \identite\) et on compose à droite par l'inverse de \(f\) puis l'inverse de \(g\), ce qui nous donne :

\[h \circ g \circ f \circ f^{-1} \circ g^{-1} = \identite \circ f^{-1} \circ g^{-1} = f^{-1} \circ g^{-1}\]

Mais comme :

\[h \circ g \circ f \circ f^{-1} \circ g^{-1} = h \circ g \circ \identite \circ g^{-1} = h \circ g \circ g^{-1} = h \circ \identite = h\]

on a :

\[h = f^{-1} \circ g^{-1}\]

Partant de la relation \(g \circ f \circ h = \identite\) et composant à gauche par l'inverse de \(g\) puis par l'inverse de \(f\), on arrive au même résultat \(h = f^{-1} \circ g^{-1}\). Donc :

\[(g \circ f)^{-1} = f^{-1} \circ g^{-1}\]

On généralise par récurrence à \(n\) fonctions :

\[(f_n \circ ... \circ f_2 \circ f_1)^{-1} = f_1^{-1} \circ f_2^{-1} \circ ... \circ f_n^{-1}\]

15.7 Puissances négatives

Si \(f\) est inversible, on peut également définir les puissances négatives par :

\[f^{-n} = \left( f^{-1} \right)^n = f^{-1} \circ ... \circ f^{-1}\]

pour tout \(n \in \setN\).

15.8 Inverse d'une puissance

En considérant le cas particulier de fonctions identiques (\(f_1 = ... = f_n = f\)), l'expression de l'inverse d'une composition de fonctions nous montre que :

\[\left( f^{-1} \right)^n = f^{-n} = \left( f^n \right)^{-1}\]

L'inverse de la puissance est identique à la puissance de l'inverse.

15.9 Idempotence

On dit que deux ensembles \(A\) et \(B\) sont idempotents si il existe une bijection inversible de \(A\) vers \(B\) :

\[\bijection(A,B) \ne \emptyset\]

15.9.1 Equivalence

Soit les ensembles \(A\) et \(B\). Supposons qu'il existe une bijection \(f \in \bijection(A,B)\). On peut alors définir une équivalence sur \(A \cup B\) en disant que \(x \equiv y\) si \(x \in A\) avec \(y = f(x) \in B\), ou si \(x \in B\) avec \(y = f^{-1}(x) \in A\). Dans les autres cas, \(x\) ne sera pas équivalent à \(y\). Les classes d'quivalences seront donc de la forme :

\[\mathcal{E}(a) = \{ a , f(a) \}\]

pour tout \(a \in A\) et de la forme :

\[\mathcal{E}(b) = \{ b , f^{-1}(b) \}\]

pour tout \(b \in B\). Il y a donc une « équivalence » entre les éléments de \(A\) et les éléments de \(B\). Dans ce cas, on confond souvent les éléments \(x\) de \(A\) avec les éléments de \(\hat{x}\) de \(B\), et on note abusivement \(x = \hat{x}\).

15.9.2 Ensembles finis

Dans le cas d'ensembles finis, l'idempotence revient à dire que \(A\) et \(B\) ont le même nombre d'éléments.

15.10 Inverse des fonctions monotones

\begin{theoreme} Soit la fonction $f : A \mapsto B$ avec $B = f(A)$. Si $f$ est strictement croissante (ou décroissante), alors la fonction $f$ est inversible. \end{theoreme} \begin{demonstration} Choisissons $y \in B$ et considérons l'ensemble de solutions : $$S(y) = \{ x : f(x) = y \}$$ Comme $B = f(A)$, cet ensemble est non vide. Supposons $x_1,x_2 \in S(y)$ avec $x_1 \strictinferieur x_2$. On a alors, soit $f(x_1) \strictinferieur f(x_2)$ (si $f$ est strictement croissante), soit $f(x_1) \strictsuperieur f(x_2)$ (si $f$ est strictement décroissante). Or, par définition de $S(y)$, on doit avoir $f(x_1) = f(x_2) = y$. Il ne peut donc y avoir d'éléments distincts dans $S(y)$, et cet ensemble est de la forme : $$S(y) = \{ g(y) \}$$ relation qui définit implicitement la fonction $g : B \mapsto A$. On peut trouver un unique $g(y)$ tel que $f(g(y)) = y$. La fonction $f$ est donc inversible et : $$f^{-1} = g$$ \end{demonstration}

16 Ordre inclusif

16.1 Dépendances

  • Chapitre \ref{chap:collections} : Les collections
  • Chapitre \ref{chap:ordres} : Les ordres
  • Chapitre \ref{chap:extrema} : Les extrema

16.2 Ordre sur les ensembles

Soit l'ensemble \(\Omega\) et l'ensemble de ses sous-ensembles :

\[\sousens(\Omega) = \{ A : A \subseteq \Omega \}\]

On dit que \(A \in \sousens(\Omega)\) est plus petit ou égal à \(B \in \sousens(\Omega)\) au sens de l'ordre inclusif si et seulement si :

\[A \subseteq B\]

On voit qu'il s'agit d'un ordre partiel.

16.2.1 Attention

Ne pas confondre l'ordre inclusif \(\subseteq\) avec la comparaison d'ensembles \(\ensinferieur\) qui est elle basée sur l'ordre entre les éléments des ensembles concernés.

16.3 Extrema inclusifs d'une collection

Soit l'ensemble de paramètres \(X\) et la collection paramétrée :

\[\mathcal{C} = \{ A(x) \in \sousens(\Omega) : x \in X \}\]

16.3.1 Majorant

Si on veut qu'un ensemble quelconque \(M \subseteq \Omega\) soit un majorant inclusif de \(\mathcal{C}\), il faut que \(A(x) \subseteq M\) pour tout \(x \in X\). Pour cela, il faut et il suffit que \(M\) contienne tous les \(A(x)\). Autrement dit, il faut et il suffit que \(M\) contienne l'union des ensembles-éléments de la collection. On a donc :

\[\major_\subseteq \mathcal{C} = \left\{ M \in \sousens(\Omega) : \bigcup_{x \in X} A(x) \subseteq M \right\}\]

16.3.2 Supremum

Etudions l'ensemble :

\[S = \bigcup_{x \in X} A(x) \in \sousens(\Omega)\]

Comme :

\[\bigcup_{x \in X} A(x) \subseteq S\]

on a :

\[S \in \major_\subseteq \mathcal{C}\]

On voit aussi que \(S \subseteq M\) pour tout \(M \in \major_\subseteq \mathcal{C}\). On en déduit que :

\[S = \min_\subseteq \major_\subseteq \mathcal{C} = \sup_\subseteq \mathcal{C}\]

16.3.3 Minorant

Si on veut qu'un ensemble quelconque \(L \subseteq \Omega\) soit un minorant inclusif de \(\mathcal{C}\), il faut que \(L \subseteq A(x)\) pour tout \(x \in X\). Pour cela, il faut et il suffit que \(L\) soit contenu dans tous les \(A(x)\). Autrement dit, il faut et il suffit que \(L\) soit contenu dans l'intersection des ensembles-éléments de la collection. On a donc :

\[\minor_\subseteq \mathcal{C} = \left\{ L \in \sousens(\Omega) : L \subseteq \bigcap_{x \in X} A(x) \right\}\]

16.3.4 Infimum

Etudions l'ensemble :

\[I = \bigcap_{x \in X} A(x) \in \sousens(\Omega)\]

Comme :

\[I \subseteq \bigcap_{x \in X} A(x)\]

on a :

\[I \in \minor_\subseteq \mathcal{C}\]

On voit aussi que \(L \subseteq I\) pour tout \(L \in \minor_\subseteq \mathcal{C}\). On en déduit que :

\[I = \max_\subseteq \minor_\subseteq \mathcal{C} = \inf_\subseteq \mathcal{C}\]

16.3.5 Conclusion

Le supremum inclusif d'une collection de sous-ensembles de \(\Omega\) existe toujours dans \(\sousens(\Omega)\) et est égal à l'union de tous ces ensembles :

\[\sup_\subseteq \{ A(x) \in \sousens(\Omega) : x \in X \} = \bigcup_{x \in X} A(x)\]

L'infimum inclusif d'une collection de sous-ensembles de \(\Omega\) existe toujours dans \(\sousens(\Omega)\) et est égal à l'intersection de tous ces ensembles :

\[\inf_\subseteq \{ A(x) \in \sousens(\Omega) : x \in X \} = \bigcap_{x \in X} A(x)\]

17 Treillis

17.1 Dépendances

  • Chapitre \ref{chap:ordreInclusif} : L'ordre inclusif

17.2 Définition

Soit l'ensemble \(\Omega\) et \(A,B \subseteq \Omega\). Au sens inclusif, les supremum et infimum de l'ensemble \(\{A,B\}\) existent toujours et :

\( \sup_\subseteq \{ A,B \} = A \cup B \\ \\ \inf_\subseteq \{ A,B \} = A \cap B \)

Le concept de treillis est une généralisation de cette propriété. Soit un ensemble \(\mathcal{T}\) sur lequel est défini l'ordre \(\le\). On dit que le couple \((\mathcal{T},\le)\) est un treillis si, pour tout éléments \(a,b \in \mathcal{T}\), le supremum et l'infimum de l'ensemble :

\[\{ a,b \}\]

existent :

\[\minor \{ a, b \} \le \inf \{ a, b \} \le \{ a, b \} \le \sup \{ a, b \} \le \major \{ a, b \}\]

Dans la suite, nous considérons un treillis \((\mathcal{T},\le)\).

17.3 Union généralisée

Soit \(a, b \in \mathcal{T}\). Par analogie avec l'union ensembliste, on définit l'opération d'union généralisée \(\sqcup\) par :

\[a \sqcup b = \sup \{ a, b \}\]

17.4 Intersection généralisée

Soit \(a, b \in \mathcal{T}\). Par analogie avec l'intersection ensembliste, on définit l'opération d'intersection généralisée \(\sqcap\) par :

\[a \sqcap b = \inf \{ a, b \}\]

17.5 Treillis dual

Le treillis dual de \((\mathcal{T},\le)\) est noté \((\mathcal{T},\le)^\dual\) et défini par :

\[(\mathcal{T},\le)^\dual = (\mathcal{T},\le^\dual)\]

où \(\le^\dual\) est l'ordre dual de \(\le\). On a bien entendu :

\[\sup_{\le^\dual} \{a,b\} = \inf_\le \{a,b\}\]

et :

\[\inf_{\le^\dual} \{a,b\} = \sup_\le \{a,b\}\]

Le treillis dual est donc également un treillis.

17.5.1 Union

Soit \(a,b \in \mathcal{T}\). On définit l'opération \(\sqcup^\dual\) par :

\[a \sqcup^\dual b = \sup_{\le^\dual} \{a,b\} = \inf_\le \{a,b\} = a \sqcap b\]

17.5.2 Intersection

Soit \(a,b \in \mathcal{T}\). On définit l'opération \(\sqcap^\dual\) par :

\[a \sqcap^\dual b = \inf_{\le^\dual} \{a,b\} = \sup_\le \{a,b\} = a \sqcup b\]

17.5.3 Primal

Par opposition au treillis dual \((\mathcal{T},\le)^\dual\), le treillis \((\mathcal{T},\le)\) est appelé treillis primal.

17.6 Éléments nul et universel

17.6.1 Élément nul

Si \(\mathcal{T}\) admet un minimum, on l'appelle élément nul de \(\mathcal{T}\) et on le note :

\[0 = \min \mathcal{T}\]

Soit \(a \in \mathcal{T}\). Si \(x \in \minor \{ 0, a \}\), on a \(x \le 0\). Comme on a également \(0 \le x\), on en conclut que \(x = 0\) et que :

\[\minor \{ 0, a \} = \{ 0 \}\]

Donc :

\[\inf \{ 0, a \} = \max \{ 0 \} = 0\]

On a aussi :

\[\{ 0, a \} \le a \le \major \{ 0, a \}\]

d'où l'on déduit :

\[\sup \{ 0, a \} = a\]

En termes d'opérations, ces résultats s'écrivent :

\[0 \sqcap a = 0\]

\[0 \sqcup a = a\]

17.6.2 Élément universel

Si \(\mathcal{T}\) admet un maximum, on l'appelle élément universel de \(\mathcal{T}\) et on le note :

\[1 = \max \mathcal{T}\]

Si \(x \in \major \{ 1, a \}\), on a \(x \ge 1\). Comme on a également \(1 \ge x\), on en conclut que \(x = 1\) et que :

\[\major \{ 1, a \} = \{ 1 \}\]

Donc :

\[\sup \{ 1, a \} = \min \{ 1 \} = 1\]

On a aussi :

\[\{ 1, a \} \ge a \ge \minor \{ 1, a \}\]

d'où l'on déduit :

\[\inf \{ 1, a \} = a\]

En termes d'opérations, ces résultats s'écrivent :

\[1 \sqcup a = 1\]

\[1 \sqcap a = a\]

17.6.3 Dualité

Sous réserve d'existence, on a :

\[0 = \min_\le \mathcal{T} = \max_{\le^\dual} \mathcal{T}\]

L'élément universel du treillis dual est donc égal à l'élément nul du treillis primal :

\[1^\dual = 0\]

Sous réserve d'existence, on a :

\[1 = \max_\le \mathcal{T} = \min_{\le^\dual} \mathcal{T}\]

L'élément nul du treillis dual est donc égal à l'élément universel du treillis primal :

\[0^\dual = 1\]

17.7 Complémentaire

On dit que \(x^\ddagger \in \mathcal{T}\) est un complémentaire de \(x \in \mathcal{T}\) si :

\[x \sqcup x^\ddagger = 1\]

\[x \sqcap x^\ddagger = 0\]

17.7.1 Dualité

En termes d'opérations du treillis dual, les conditions de complémentarité s'écrivent :

\[x \sqcap^\dual x^\ddagger = 0^\dual\]

\[x \sqcup^\dual x^\ddagger = 1^\dual\]

On en conclut que \(x^\ddagger\) est également le complémentaire de \(x\) au sens du treillis dual.

17.8 Distributivité

On dit que \((\mathcal{T},\le)\) est un treillis distributif si :

\[a \sqcup (b \sqcap c) = (a \sqcup b) \sqcap (a \sqcup c)\]

\[a \sqcap (b \sqcup c) = (a \sqcap b) \sqcup (a \sqcap c)\]

pour tout \(a,b,c \in \mathcal{T}\).

17.9 Booléen

Un treillis \((\mathcal{T},\le)\) est dit booléen si et seulement si :

  • il comprend un élément nul et un élément universel
  • il est distributif
  • chaque élément de \(\mathcal{T}\) admet un complémentaire

17.10 Idempotence

Soit \(a \in \mathcal{T}\). On a :

\[\{a\} \le a \le \major\{a\}\]

donc :

\[a = \sup\{a\}\]

On en conclut que :

\[a \sqcup a = \sup\{a,a\} = \sup\{a\} = a\]

On a :

\[\minor\{a\} \le a \le \{a\}\]

donc :

\[a = \inf\{a\}\]

On en conclut que :

\[a \sqcap a = \inf\{a,a\} = \inf\{a\} = a\]

17.11 Sous-ensemble fini

17.11.1 Supremum

Nous allons voir que tout sous-ensemble fini d'un treillis admet un supremum. On sait déjà que c'est vrai pour des ensembles comportant un ou deux éléments. Supposons à présent que ce soit vrai pour les sous-ensembles de maximum \(n - 1\) éléments, où \(n\) est un naturel vérifiant \(n \ge 2\). Soit :

\[A = \{ a_1, a_2, ..., a_n \} \subseteq \mathcal{T}\]

Choisissons \(i \in \{ 1, 2, ..., n \}\) et posons :

\[x = a_i\]

\[Z = A \setminus \{ x \} = \{ ..., a_{i - 1}, a_{i + 1}, ... \}\]

L'ensemble \(Z\) comportant \(n - 1\) éléments, il admet un supremum :

\[\mu = \sup Z\]

Posons :

\[\sigma = \sup \{ \mu, x \}\]

On a :

\[\sigma \ge \mu \ge Z\] \[\sigma \ge \{ x \}\]

donc :

\[\sigma \ge Z \cup \{ x \} = A\]

et :

\[\sigma \in \major A\]

Choisissons :

\[\varkappa \in \major A\]

On a :

\[\varkappa \ge Z\] \[\varkappa \ge \{ x \}\]

La première inégalité nous dit que :

\[\varkappa \in \major Z\]

Le supremum étant le plus petit des majorants, on doit donc avoir :

\[\varkappa \ge \mu\]

Comme on a également :

\[\varkappa \ge x\]

on en conclut que :

\[\varkappa \in \major \{ \mu, x \}\]

Le supremum étant le plus petit des majorants, on doit donc avoir :

\[\varkappa \ge \sigma\]

Nous venons de prouver que :

\[\sigma = \min \major A = \sup A\]

Tout sous-ensemble fini non vide \(A \subseteq \mathcal{T}\) possède un supremum. Si \(A\) compte au moins deux éléments, on a :

\[\sup A = \sup \Big\{ \sup\big(A \setminus \{ x \}\big) , x \Big\}\]

17.11.2 Infimum

Nous allons voir que tout sous-ensemble fini d'un treillis admet un infimum. On sait déjà que c'est vrai pour des ensembles comportant un ou deux éléments. Supposons à présent que ce soit vrai pour les sous-ensembles de maximum \(n - 1\) éléments, où \(n\) est un naturel vérifiant \(n \ge 2\). Soit :

\[A = \{ a_1, a_2, ..., a_n \} \subseteq \mathcal{T}\]

Choisissons \(i \in \{ 1, 2, ..., n \}\) et posons :

\[x = a_i\]

\[Z = A \setminus \{ x \} = \{ ..., a_{i - 1}, a_{i + 1}, ... \}\]

L'ensemble \(Z\) comportant \(n - 1\) éléments, il admet un infimum :

\[\gamma = \inf Z\]

Posons :

\[\lambda = \inf \{ \gamma, x \}\]

On a :

\[\lambda \le \gamma \le Z\] \[\lambda \le \{ x \}\]

donc :

\[\lambda \le Z \cup \{ x \} = A\]

et :

\[\lambda \in \minor A\]

Choisissons :

\[\vartheta \in \minor A\]

On a :

\[\vartheta \le Z\] \[\vartheta \le \{ x \}\]

La première inégalité nous dit que :

\[\vartheta \in \minor Z\]

L'infimum étant le plus grand des minorants, on doit donc avoir :

\[\vartheta \le \gamma\]

Comme on a également :

\[\vartheta \le x\]

on en conclut que :

\[\vartheta \in \minor \{ \gamma, x \}\]

L'infimum étant le plus grand des minorants, on doit donc avoir :

\[\vartheta \le \lambda\]

Nous venons de prouver que :

\[\lambda = \max \minor A = \inf A\]

Tout sous-ensemble fini non vide \(A \subseteq \mathcal{T}\) possède un infimum. Si \(A\) compte au moins deux éléments, on a :

\[\inf A = \inf \Big\{ \inf\big(A \setminus \{ x \}\big) , x \Big\}\]

17.12 Commutativité

Soit \(a, b \in \mathcal{T}\). Comme \(\{a,b\} = \{b,a\}\), on a clairement :

\[a \sqcup b = b \sqcup a\]

et :

\[a \sqcap b = b \sqcap a\]

17.13 Associativité

17.13.1 Union

On a :

\[\sup \big\{ a, \sup \{b, c\} \big\} = \sup \{a,b,c\} = \sup \big\{ \sup \{a, b\}, c \big\}\]

En terme d'opération, ce résultat implique l'associativité de l'union généralisée :

\[a \sqcup (b \sqcup c) = (a \sqcup b) \sqcup c\]

On définit donc :

\[a \sqcup b \sqcup c = a \sqcup (b \sqcup c) = (a \sqcup b) \sqcup c\]

Plus généralement, on a :

\[a_1 \sqcup a_2 \sqcup ... \sqcup a_n = \sup \{ a_1, a_2, ..., a_n \}\]

pour tout \(a_1, a_2, ..., a_n \in \mathcal{T}\).

17.13.2 Intersection

Le treillis dual \((\mathcal{T},\le^\dual)\) étant également un treillis, on a la propriété :

\[a \sqcup^\dual (b \sqcup^\dual c) = (a \sqcup^\dual b) \sqcup^\dual c\]

pour tout \(a,b,c \in \mathcal{T}\). Cette relation traduite en terme d'opérations du treillis primal nous donne l'associativité de l'intersection généralisée :

\[a \sqcap (b \sqcap c) = (a \sqcap b) \sqcap c\]

On définit donc :

\[a \sqcap b \sqcap c = a \sqcap (b \sqcap c) = (a \sqcap b) \sqcap c\]

Plus généralement, on a :

\[a_1 \sqcap a_2 \sqcap ... \sqcap a_n = \inf \{ a_1, a_2, ..., a_n \}\]

pour tout \(a_1, a_2, ..., a_n \in \mathcal{T}\).

17.14 Absorption

Soit \(a, b \in \mathcal{T}\). Posons :

\[\sigma = \sup\{a,b\}\]

Comme \(\sigma \ge a\), on a :

\[a \le \{a,\sigma\}\]

Choisissons \(\lambda \in \mathcal{T}\) tel que :

\[\lambda \le \{a,\sigma\}\]

on a alors forcément :

\[\lambda \le a\]

d'où l'on conclut que :

\[\minor \{a,\sigma\} \le a \le \{a,\sigma\}\]

L'élément \(a\) est donc l'infimum de \(\{a,\sigma\}\) :

\[a = \inf \{a,\sigma\}\]

Par définition de \(\sigma\), on a donc :

\[a = \inf \{a, \sup \{a, b\} \}\]

Exprimée en terme d'opérations, cette relation devient :

\[a = a \sqcap (a \sqcup b)\]

Cette même propriété étant valable pour le treillis dual, on a :

\[a = a \sqcap^\dual (a \sqcup^\dual b)\]

Équation qui peut être réexprimée en termes d'opérations du treillis primal, ce qui nous donne :

\[a = a \sqcup (a \sqcap b)\]

17.15 Treillis d'ensemble

Une collection \(\mathcal{C}\) de sous-ensembles d'un ensemble de référence \(\Omega\) :

\[\mathcal{C} \subseteq \sousens(\Omega)\]

est un treillis d'ensembles si et seulement si :

\[\emptyset,\Omega \in \mathcal{C}\]

et :

\[A \cup B \in \mathcal{C}\]

\[A \cap B \in \mathcal{C}\]

pour tout \(A,B \in \mathcal{C}\). Le couple \((\mathcal{C},\subseteq)\) est un cas particulier de treillis.

17.15.1 Élément nul

Un treillis d'ensembles comporte toujours un élément nul :

\[\emptyset = \min_{\subseteq} \mathcal{C}\]

17.15.2 Élément universel

Un treillis d'ensembles comporte toujours un élément universel :

\[\Omega = \max_{\subseteq} \mathcal{C}\]

18 Tribus

\label{chap:tribus}

18.1 Dépendances

  • Chapitre \ref{chap:collections} : Les collections
  • Chapitre \ref{chap:ordreInclusif} : L'ordre inclusif

18.2 Définition

Soit un ensemble \(\Omega\) et une collection de sous-ensembles \(\mathcal{T} \subseteq \sousens(\Omega)\). On dit que \(\mathcal{T}\) forme une tribu sur \(\Omega\) si et seulement si les conditions suivantes sont remplies :

  • \(\emptyset \in \mathcal{T}\)
  • si \(A \in \mathcal{T}\), on a aussi \(\Omega \setminus A \in \mathcal{T}\)
  • l'union de toute suite discrète \(A_1,A_2,... \in \mathcal{T}\)

appartient aussi à la collection :

\[\bigcup_i A_i \in \mathcal{T}\]

On note \(\tribu(\Omega)\) l'ensemble des tribus sur \(\Omega\).

18.3 Corollaire

On conclut directement de la définition que :

\[\Omega = \Omega \setminus \emptyset \in \mathcal{T}\]

18.4 Intersection

Soit les \(A_i \in \mathcal{T}\) et leurs complémentaires :

\[B_i = \Omega \setminus A_i \in \mathcal{T}\]

On a aussi :

\[A_i = \Omega \setminus B_i\]

En prenant l'intersection de tous les \(A_i\), on obtient :

\[\bigcap_i A_i = \Omega \setminus \left[ \bigcup_i B_i \right] \in \mathcal{T}\]

On en déduit que toute intersection dénombrable d'éléments de \(\mathcal{T}\) est également dans \(\mathcal{T}\).

18.5 Différence

Soit \(A,B \in \mathcal{T}\), on a

\[A \setminus B = A \cap (\Omega \setminus B) \in \mathcal{T}\]

18.6 Tribu engendrée

Les collections d'ensemble étant des ensembles d'ensembles, on peut également les comparer au moyen de l'inclusion. En ce sens, la tribu engendrée par la collection \(\mathcal{C} \subseteq \sousens(\Omega)\) est la plus petite tribu contenant les éléments de \(\mathcal{C}\). On la note :

\[\tribu(\mathcal{C},\Omega) = \inf_\subseteq \{ \mathcal{T} \in \tribu(\Omega) : \mathcal{C} \subseteq \mathcal{T} \}\]

19 Topologies

19.1 Dépendances

  • Chapitre \ref{chap:collections} : Les collections
  • Chapitre \ref{chap:ordreInclusif} : L'ordre inclusif

19.2 Définition

Soit un ensemble \(\Omega\) et une collection de sous-ensembles \(\topologie \subseteq \sousens(\Omega)\). On dit que \(\topologie\) forme une topologie sur \(\Omega\) si et seulement si les conditions suivantes sont remplies :

  • \(\emptyset, \Omega \in \topologie\)
  • pour toute sous-collection \(\mathcal{C} \subseteq \topologie\), l'union des ensembles-éléments de \(\mathcal{C}\) appartient également à la topologie :

\[\bigcup \mathcal{C} \in \topologie\]

  • si \(A,B \in \topologie\), leur intersection appartient également à la topologie :

\[A \cap B \in \topologie\]

On note \(\topologies(\Omega)\) l'ensemble des topologies sur \(\Omega\).

19.3 Espace topologique

Si \(\topologie\) est une topologie sur \(\Omega\), on dit que le couple \((\Omega,\topologie)\) forme un espace topologique.

19.4 Ouvert

On appelle « ouvert » tout ensemble \(U \in \topologie\).

19.5 Fermé

On appelle « fermé » tout complémentaire d'un ouvert. Si \(F \subseteq \Omega\) est un fermé, on peut donc écrire :

\[F = \Omega \setminus U\]

pour un certain \(U \in \topologie\). On note la collection des ensembles fermés par :

\[\ferme = \{ \Omega \setminus U : U \in \topologie \}\]

19.5.1 Intersection

Soit une collection d'ouverts \(\mathcal{C} \subseteq \topologie\) et la collection de fermés correspondant :

\[\mathcal{F} = \{ \Omega \setminus U : U \in \mathcal{C} \}\]

L'intersection de tous ces fermés :

\[\bigcap \mathcal{F} = \Omega \setminus \bigcup \mathcal{C}\]

est le complémentaire de l'ensemble :

\[U = \bigcup \mathcal{C}\]

qui est un ouvert. On en conclut qu'une intersection de fermés est un fermé.

19.5.2 Union

Soit les ouverts \(U,V \in \topologie\) et les fermés correspondant :

\( F = \Omega \setminus U \\ G = \Omega \setminus V \)

On a :

\[F \cup G = \Omega \setminus (U \cap V)\]

L'ensemble \(U \cap V\) étant un ouvert, on en conclut que l'union de deux fermés est un fermé.

19.6 Ouverts fermés

On a \(\{\emptyset,\Omega\} \subseteq \topologie \cap \ferme\).

19.7 Voisinage

On dit que \(V \subseteq \Omega\) est un voisinage de \(x \in \Omega\) si il existe un ouvert \(U \in \topologie\) tel que \(x \in U \subseteq V\).

19.8 Adhérence

L'adhérence, ou fermeture, d'un ensemble \(A \subseteq \Omega\) est le plus petit (au sens inclusif) ensemble fermé \(F\) contenant \(A\). On la note :

\[\adh A = \inf_\subseteq \{ F \in \ferme : A \subseteq F \} = \bigcap \{ F \in \ferme : A \subseteq F \}\]

19.9 Intérieur

L'intérieur d'un ensemble \(A \subseteq \Omega\) est le plus grand ensemble ouvert contenu dans \(A\). On le note :

\[\interieur A = \sup_\subseteq \{ U \in \topologie : U \subseteq A \} = \bigcup \{ U \in \topologie : U \subseteq A \}\]

19.10 Frontière

La frontière de \(A\) est la différence entre l'adhérence et l'intérieur :

\[\frontiere A = (\adh A) \setminus (\interieur A)\]

19.11 Propriétés de l'adhérence et de l'intérieur

19.11.1 Inclusions

On a bien entendu :

\[\interieur A \subseteq A \subseteq \adh A\]

19.11.2 Nature

Une union quelconque d'ouverts étant un ouvert, on a \(\interieur A \in \topologie\). Une intersection quelconque de fermés étant un fermé, on a \(\adh A \in \ferme\).

19.11.3 Complémentaire

Les fermés \(F\) contenant \(A\) correspondent aux complémentaires des ouverts \(U = \Omega \setminus F\) inclus dans \(\Omega \setminus A\). Comme \(\bigcap F = \Omega \setminus \bigcup U\), on a :

\[\adh A = \Omega \setminus \interieur (\Omega \setminus A)\]

Les ouverts \(U\) inclus dans \(A\) correspondent aux complémentaires des fermés \(F = \Omega \setminus U\) contenant \(\Omega \setminus A\). La relation \(\bigcup U = \Omega \setminus \bigcap F\) nous dit que :

\[\interieur A = \Omega \setminus \adh (\Omega \setminus A)\]

19.12 Hausdorff

On dit que le couple \((\Omega,\topologie)\) est un espace de Haussdorff si, pour tout \(x,y \in \Omega\) vérifiant \(x \ne y\), on peut trouver des ouverts \(U, V \in \topologie\) tels que :

\[x \in U, \ y \in V\]

et :

\[U \cap V = \emptyset\]

19.13 Topologie engendrée

Les collections d'ensemble étant des ensembles d'ensembles, on peut également les comparer au moyen de l'inclusion. En ce sens, la topologie engendrée par la collection \(\mathcal{C} \subseteq \sousens(\Omega)\) est la plus petite topologie contenant les ensembles-éléments de \(\mathcal{C}\). On la note :

\[\topologies(\mathcal{C},\Omega) = \inf_\subseteq \{ \topologie \in \topologies(\Omega) : \mathcal{C} \subseteq \topologie \}\]

Auteur: chimay

Created: 2019-10-01 mar 12:32

Validate