$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Résumé de cours : ensembles, applications, relations

Ensembles
  • On appelle élément d'un ensemble $E$ tout objet qui appartient à $E$.
  • Si $E$ et $F$ sont deux ensembles, on dit que $E$ est une partie de $F$, que $E$ est un sous-ensemble de $F$, ou encore que $E$ est inclus dans $F$ si tout élément de $E$ est aussi élément de $F$. On note $E\subset F$.
  • Il existe un unique ensemble qui ne contient aucun élément, l'ensemble vide. Il est noté $\varnothing$.
  • Un ensemble peut être écrit en extension, c'est-à-dire que l'on donne la liste de tous ses éléments, ou en compréhension, c'est-à-dire que l'on définit cet ensemble par une propriété. Par exemple, $A=\{2,3,4,5\}$ est défini en extension, et $B=\{n\in\mathbb N;\ 2\leq n<6\}$ est défini en compréhension. Remarquons que $A=B$.
  • L'ensemble des parties de $E$ est lui-même un autre ensemble, appelé ensemble des parties et noté $\mathcal P(E)$.
  • Étant donné un ensemble $E$ et deux parties $A$ et $B$ de $E$, on peut définir
    • la réunion de $A$ et $B$, noté $A\cup B$. $A\cup B$ est l'ensemble des éléments qui appartiennent à $A$ ou à $B$.
    • l'intersection de $A$ et $B$, noté $A\cap B$. $A\cap B$ est l'ensemble des éléments qui appartiennent à $A$ et à $B$.
    • la différence $A\backslash B$ : $A\backslash B$ est l'ensemble des éléments qui sont dans $A$, mais pas dans $B$.
    • le complémentaire de $A$ dans $E$, noté $\bar A$, ou $C_E A$, ou $E\backslash A$, l'ensemble des éléments de $E$ qui ne sont pas dans $A$.
  • Si $A$ et $B$ sont deux ensembles, le produit cartésien de $A$ et $B$, noté $A\times B$, est l'ensemble constitué de tous les couples $(a,b)$, où $a$ est un élément de $A$ et $b$ est un élément de $B$.
Applications

Soit $E$ et $F$ deux ensembles. Une application ou fonction de $E$ dans $F$ associe à tout élément de $E$ un unique élément de $F$. L'ensemble des applications de $E$ dans $F$ est noté $\mathcal F(E,F)$, ou $F^E$. On appelle graphe de l'application $f:E\to F$ la partie $\Gamma$ de $E\times F$ définie par $$\Gamma=\{(x,f(x));\ x\in E\}.$$ Si $A$ est une partie de $E$, la fonction indicatrice de $A$, notée $\mathbf 1_A$, est la fonction définie par $$\mathbf 1_A(x)=\left\{ \begin{array}{ll} 1&\textrm{ si }x\in A\\ 0&\textrm{ sinon}. \end{array} \right. $$ Si $E$ est un ensemble, la fonction identité de $E$ est la fonction $Id_E$, définie de $E$ dans $E$ par $Id_E(x)=x$.

Si $f$ est une fonction de $E$ dans $F$, on appelle restriction de $f$ à $A$, et on note $f_{|A}$ la fonction définie sur $A$ par $$f_{|A}(x)=f(x).$$ Si $A$ est une partie de l'ensemble $E$, et si $f$ est une application de $A$ dans $F$, on appelle prolongement de $f$ à $E$ toute fonction $g:E\to F$ vérifiant $g(x)=f(x)$ si $x\in A$. Notons qu'il peut exister plusieurs prolongements d'une application à un ensemble donné.

Si $f$ est une application de $E$ dans $F$ et si $A$ est une partie de $E$, on appelle image directe de $A$ par $f$ l'ensemble $f(A)=\{f(x);\ x\in A\}$. Ainsi, $$y\in f(A)\iff \exists x\in A,\ y=f(x).$$

Si $f$ est une application de $E$ dans $F$ et si $B$ est une partie de $F$, on appelle image réciproque de $B$ par $f$ l'ensemble $f^{-1}(B)=\{x\in E;\ f(x)\in B\}$. Ainsi, $$x\in f^{-1}(B)\iff f(x)\in B.$$

Si $E$, $F$ et $G$ sont 3 ensembles et si $f:E\to F$ et $g:F\to G$ sont deux applications, on appelle application composée de $f$ et $g$ l'application notée $g\circ f:E\to G$ définie par la formule $$g\circ f(x)=g(f(x)).$$

Injection, surjection, bijection

Soit $f:E\to F$ une application. On dit que f est

  • injective si, pour tout $y\in F$, l'équation $y=f(x)$ admet au plus une solution $x\in E;$
  • surjective si, pour tout $y\in F$, l'équation $y=f(x)$ admet au moins une solution $x\in E;$
  • bijective si, pour tout $y\in F$, l'équation $y=f(x)$ admet exactement une solution $x\in E.$

Souvent pour démontrer que $f$ est, ou n'est pas, injective, on utilise la caractérisation suivante : $f:E\to F$ est injective si, et seulement si, pour tout couple $(x,x')\in E^2$, si $f(x)=f(x')$, alors $x=x'$.

La composée de deux injections est une injection; la composée de deux surjections est une surjection; la composée de deux bijections est une bijection.

Si $f:E\to F$ est une bijection, il existe une unique application notée $f^{-1}$, définie de $F$ dans $E$, telle que $$f\circ f^{-1}=Id_F\textrm{ et }f^{-1}\circ f=Id_E.$$ $f^{-1}$ est appelée fonction réciproque de $f$. On a $$y=f(x)\iff x=f^{-1}(y).$$

Si $f:E\to F$ et $g:F\to G$ sont bijectives, alors $$(g\circ f)^{-1}=f^{-1}\circ g^{-1}.$$

Relations

    On appelle relation binaire sur un ensemble $E$ la donnée d'une partie $\Gamma$ de $E\times E$. On dit que $x$ est en relation avec $y$ et on écrit $x\mathcal R y$ lorsque $(x,y)\in \Gamma$.

    On dit que la relation $\mathcal R$ est

    • réflexive si, pour tout $x\in E$, $x\mathcal R x$.
    • symétrique si, pour tous $x,y\in E$, si $x\mathcal R y$, alors $y\mathcal R x$.
    • anti-symétrique si, pour tous $x,y\in E$, si $x\mathcal R y$ et $y\mathcal R x$, alors $x=y$.
    • transitive si, pour tous $x,y,z\in E$, si $x\mathcal R y$ et $y\mathcal R z$, alors $x\mathcal R z$.

    Une relation d'équivalence est une relation réflexive, symétrique, transitive.

    Si $\mathcal R$ est une relation d'équivalence et $x$ est un élément de $E$, on appelle classe d'équivalence de $x$ l'ensemble des éléments $y$ de $E$ tels que $x\mathcal R y$.

    Théorème : Soit $E$ un ensemble muni d'une relation d'équivalence $\mathcal R$. Alors les classes d'équivalence pour $\mathcal R$ forment une partition de $E$.

    Exemple : la relation de congruence

    Soit $a$ un entier strictement positif. On définit une relation d'équivalence sur $\mathbb R$ notée $\equiv$ par $$x\equiv y\ [a]\iff \exists k\in\mathbb Z,\ x=y+ka.$$ Ceci se lit "x est congru à $y$ modulo $a$". On utilise ceci souvent avec $a=\pi$ ou $a=2\pi$. Si $x\equiv y\ [2\pi]$, on a $\cos(x)=\cos(y)$ et $\sin(x)=\sin(y)$.

    On peut aussi définir la relation "être congrue" sur $\mathbb Z$. Si $p$ est un entier strictement positif, on dit que deux entiers $n$ et $m$ sont congrus modulo $p$, et on note $n\equiv m\ [p]$, s'il existe $k\in\mathbb Z$ tel que $n=m+kp$. A nouveau, on définit une relation d'équivalence sur $\mathbb Z$. Les classes d'équivalence sont $\Gamma_0,\dots,\Gamma_{p-1}$ où, pour $\ell\in\{0,\dots,p-1\}$, on a $$\Gamma_\ell=\{\ell+kp:\ k\in\mathbb Z\}.$$

    Une relation d'ordre est une relation réflexive, anti-symétrique, transitive.

    Si $\prec$ est une relation d'ordre sur $E$, alors

    • on dit que l'ordre est total si on peut toujours comparer deux éléments de $E$ : pour tous $x,y\in E$, on a $x\prec y$ ou $y\prec x$. Dans le cas contraire, on dit que l'ordre est partiel.
    • si $A$ est une partie de $E$ et $M$ est un élément de $E$, on dit que $M$ est un majorant de $A$ si, pour tout $x\in A$, on a $x\prec M$.