Logique, applications, relations

Conditions nécessaires, conditions suffisantes

Lorsque $P\implies Q$, on dit que $P$ est une condition suffisante à $Q$, et que $Q$ est une condition nécessaire à $P$.

Méthodes de raisonnement

par implication : pour prouver que $P\implies Q$, on suppose que $P$ est vraie et on utilise différentes propriétés déjà connues pour établir que $Q$ est vraie.

par double implication / par équivalence : Pour démontrer que $P\iff Q$, il y a deux méthodes standard :

On raisonne par double implication : on suppose d'abord que $P$ est vraie, et on démontre que $Q$ est vraie. Ensuite, on suppose que $Q$ est vraie, et on démontre que $P$ est vraie.
On passe de $P$ à $Q$ en utilisant uniquement des équivalences. C'est une méthode souvent déconseillée, car il faut faire très attention à ce que chaque enchaînement logique de la démonstration est bien une équivalence.

par contraposée : pour démontrer que $P\implies Q$, il suffit de démontrer la contraposée de cette proposition, c'est-à-dire $\textrm{non }Q\implies\textrm{non }P$.

par l'absurde : pour démontrer que $P\implies Q$, on peut supposer que $P$ et $\textrm{non }Q$ sont toutes les deux vraies, et obtenir une contradiction; pour démontrer que $P$ est vraie, on peut supposer que $\textrm{non }P$ est vraie et obtenir une contradiction.

par récurrence : Le raisonnement par récurrence est utilisé pour démontrer des propriétés qui dépendent d'un entier $n$. Il est basé sur le principe suivant :

Théorème (principe de récurrence) : Soit $P(n)$ une propriété concernant un entier naturel $n$. On suppose que $P(0)$ est vraie et que, pour tout entier naturel $k$, si $P(k)$ est vraie, alors $P(k + 1)$ est vraie. Alors la propriété $P(n)$ est vraie pour tout entier naturel $n$.

Pour bien rédiger une démonstration par récurrence, il est nécessaire de faire apparaitre clairement les 4 étapes : définir précisément quelle est la propriété $ P(n)$ que l'on souhaite démontrer, écrire la phase d'initialisation, la phase d'hérédité, puis la conclusion. Il existe deux erreurs fréquentes de rédaction de la phase d'hérédité.

commencer cette phase par la phrase : ``supposons que, pour tout $n\in\mathbb N$, $P(n)$ est vraie et prouvons $P(n+1)$''. Si $P(n)$ est vraie pour tout entier $n$, il n'y a plus rien à prouver!
commencer cette phase par la phrase : ``supposons qu'il existe un $n\in\mathbb N$ tel que $P(n)$ est vraie et prouvons $P(n+1)$. L'erreur est plus subtile. Le principe de récurrence s'écrit formellement $$\big (P(0) \textrm{ vraie ET }(\forall n\in \mathbb N\ P(n)\implies P(n+1)\big)\implies \forall n\in\mathbb N, P(n)\textrm{ vraie.}$$ La dernière rédaction serait correcte si le principe de récurrence s'écrivait $$\big (P(0) \textrm{ vraie ET }(\exists n\in \mathbb N\ P(n)\implies P(n+1)\big)\implies \forall n\in\mathbb N, P(n)\textrm{ vraie.}$$ ce qui est faux.

Pour ne pas faire d'erreurs, je vous conseille de toujours commencer la phase d'hérédité par : ``Soit $n\in\mathbb N$ tel que $P(n)$ est vraie'' ou alors ``Supposons que $P(n)$ est vraie pour un certain $n\in\mathbb N$''.

par récurrence double : si on veut prouver qu'une proposition $P(n)$ dépendant de l'entier naturel $n$ est vraie pour tout entier $n$, on peut procéder de la façon suivante :

initialisation : prouver que $P(0)$ et $\mathcal P(1)$ sont vraies.
hérédité : prouver que, pour tout entier $n$, si $P(n)$ et $P(n+1)$ sont vraies, alors $P(n+2)$ est vraie.

par récurrence forte : si on veut prouver qu'une proposition $P(n)$ dépendant de l'entier naturel $n$ est vraie pour tout entier $n$, on peut procéder de la façon suivante :

initialisation : prouver que $P(0)$ est vraie.
hérédité : prouver que, pour tout entier $n$, si $P(0),P(1),\dots,P(n)$ sont toutes vraies, alors $P(n+1)$ est vraie.

par disjonction de cas : le raisonnement par disjonction de cas s'utilise quand on veut démontrer une propriété $P$ dépendant d'un paramètre $x$ appartenant à un ensemble $E$, et que la justification dépend de la valeur de $x$. On écrit alors $E=E_1\cup\dots\cup E_n$, et on sépare les raisonnements suivant que $x\in E_1$, $x\in E_2,\dots$. On emploie fréquemment ce raisonnement pour résoudre des (in)équations avec des valeurs absolues (le raisonnement dépend du signe de la quantité à l'intérieur de la valeur absolue), démontrer des propriétés en arithmétique (on sépare le raisonnement suivant la parité de certains entiers, leur congruence modulo $n$...), résoudre des problèmes de géométrie (disjonction selon la position relative de deux objets géométriques).

par analyse/synthèse : le raisonnement par analyse/synthèse, qu'on pourrait aussi appeler raisonnement par condition nécessaire/condition suffisante, est un raisonnement que l'on emploie souvent lorsqu'on cherche toutes les solutions d'un problème donné. Il comporte deux phases :

L'analyse. On suppose que $x$ est solution du problème, et on trouve un certain nombre de conditions nécessaires satisfaites par $x$.
La synthèse. On vérifie que les conditions obtenues à l'issue de la phase d'analyse sont en fait également suffisantes pour que $x$ soit solution du problème.

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$.