Interversion de quantificateurs

1 – Les quantificateurs (en 2 minutes …)

La plupart des énoncés mathématiques que nous manipulons comportent des quantificateurs.

Oui, vous savez bien … ces petits symboles ésotériques qui ressemblent soit à un ‘A’ renversé, soit à un ‘E’ vu dans un miroir.

Rappelons brièvement de quoi il s’agit, en donnant deux exemples très simples.

  • Pour exprimer, avec des symboles, la phrase « le carré de tout nombre réel est positif ou nul », on écrit :

        \[ \forall x\in\mathbb{R},\thinspace x^{2}\geqslant0 \]

  • Quant à la phrase « il existe un nombre réel positif dont le carré est égal à 2 », voici sa version formalisée :

        \[ \exists r\in\left[0,+\infty\right[;\thinspace r^{2}=2 \]

Dans chacun des deux cas, la lettre ('x' ou 'r') peut être choisie librement … tant qu’il ne s’agit pas d’une lettre déjà utilisée dans le contexte !

Le symbole \forall se lit « quel que soit » ou « pour tout » : c’est le quantificateur universel.
Le symbole \exists se lit « il existe » (et signifie : « il existe au moins ») : c’est le quantificateur existentiel.

Dans certaines circonstances, deux quantificateurs se suivent … et se ressemblent !

Par exemple, la phrase « pour tout entier naturel n et pour tout réel positif x, la puissance n-ème de 1+x est minorée (au sens large) par 1+nx » devient, en symboles :

    \[ \forall n\in\mathbb{N},\thinspace\forall x\in\left[0,+\infty\right[,\thinspace\left(1+x\right)^{n}\geqslant1+nx \]

Cet énoncé est vrai (on le prouve aisément par récurrence) et l’on peut, sans rien changer au sens de la formule, permuter les deux quantificateurs. On obtient ainsi l’énoncé équivalent :

    \[ \forall x\in\left[0,+\infty\right[,\thinspace\forall n\in\mathbb{N},\thinspace\left(1+x\right)^{n}\geqslant1+nx \]

Pour le quantificateur existentiel, c’est le même topo.

Bref, on peut librement échanger deux quantificateurs qui se suivent lorsque ceux-ci sont de même nature (deux fois \forall ou bien deux fois \exists).

Mais les choses se compliquent si nos deux quantificateurs se suivent … et ne se ressemblent pas !

2 – Quel que soit, il existe … ou le contraire ?

Considérons l’exemple suivant :

    \[ \forall x\in\mathbb{R},\thinspace\exists y\in\mathbb{R};\thinspace y>x \]

Cet énoncé dit que, pour tout réel x, il existe un réel y plus grand que x.

C’est évidemment vrai : il suffit de choisir y=x+1 (par exemple) et le tour est joué.

Maintenant, intervertissons les quantificateurs … L’énoncé précédent fait place à celui-ci :

    \[ \exists y\in\mathbb{R};\thinspace\forall x\in\mathbb{R},\thinspace y>x \]

Ce nouvel énoncé dit qu’il existe un réel plus grand que tous les réels. C’est évidemment faux !

Cet exemple montre bien que l’interversion de deux quantificateurs distincts (un \forall et un \exists) n’est pas neutre. Elle peut transformer un énoncé vrai en un énoncé faux et vice versa.

Formulons à présent une remarque assez générale.

Considérons deux ensembles E,F et une propriété P, portant sur les couples \left(x,y\right) d’éléments du produit cartésien E\times F. Lorsqu’on écrit P\left(x,y\right), cela signifie que le couple \left(x,y\right) appartient à E\times F et qu’il vérifie la propriété en question. Intéressons-nous aux énoncés :

    \[ \boxed{\forall x\in E,\thinspace\exists y\in F;\thinspace P\left(x,y\right)\qquad\left(\alpha\right)} \]

et

    \[ \boxed{\exists y\in F,\thinspace\forall x\in E,\thinspace P\left(x,y\right)\quad\left(\beta\right)} \]

Si l’énoncé \left(\beta\right) est vrai, alors l’énoncé \left(\alpha\right) l’est certainement aussi !

Pour le dire avec des mots simples : s’il existe dans F un y_{0} « universel », c’est-à-dire un y_{0} qui convient à tous les x\in E, alors évidemment, pour chaque x particulier dans E, on peut trouver un y dans F qui fera l’affaire (il suffit de prendre pour y ce fameux y_{0}).
En revanche, l’implication réciproque peut être en défaut : ce n’est pas parce qu’on peut toujours trouver un y « local » (c’est-à-dire trouver, pour chaque x de E, un y qui convient … et qui dépendra a priori de ce x), que l’on peut pour autant affirmer l’existence d’un y_{0} « universel » au sens précédent.

Pourtant, l’interversion de quantificateurs se fait parfois sans heurts … et peut révéler quelque chose de profond. C’est ce que nous allons maintenant observer en détail, dans quatre contextes assez différents.

3 – Permutations d’ordre fini

Peut-être avez-vous jeté un coup d’œil au dernier exercice de cette fiche ? Nous allons utiliser les mêmes notations…

On considère donc un ensemble E ainsi qu’une application f:E\rightarrow E.

Pour tout n\in\mathbb{N}, on note f^{n} la n-ème itérée de f.

Par sécurité, rappelons que (par définition) :

    \[ f^{0}=id_{E}\qquad\text{et}\qquad\forall n\in\mathbb{N},\thinspace f^{n+1}=f\circ f^{n} \]

c’est-à-dire, pour formuler les choses plus simplement :

    \[ f^{n}=\underbrace{f\circ\cdots\circ f}_{n\text{ facteurs}} \]

Intéressons-nous aux deux énoncés suivants :

    \[ \forall x\in E,\thinspace\exists n\in\mathbb{N}^{\star};\thinspace f^{n}\left(x\right)=x\qquad\left(\diamondsuit\right) \]

    \[ \exists n\in\mathbb{N}^{\star};\thinspace\forall x\in E,\thinspace f^{n}\left(x\right)=x\qquad\left(\heartsuit\right) \]

Sont-ils équivalents ? Conformément à ce qui a été dit dans l’encadré rose, il est clair que \left(\heartsuit\right)\Rightarrow\left(\diamondsuit\right).

Autant le dire tout de suite, l’implication \left(\diamondsuit\right)\Rightarrow\left(\heartsuit\right) n’est pas vraie en toute généralité.

Et pour s’en convaincre, rien de tel qu’un contre-exemple :

Prenons E=\mathbb{N}^{\star} et l’application :

    \[ f=\left(1\right)\circ\left(2,3\right)\circ\left(4,5,6\right)\circ\left(7,8,9,10\right)\circ\cdots \]

Ces notations sont peut-être cryptées !… expliquons un peu.
Dans le cadre de l’étude des groupes symétriques \left(\mathfrak{S}_{n},\circ\right), on note habituellement \left(x_{1},\cdots,x_{p}\right) le p-cycle qui envoie x_{1} sur x_{2}, x_{2} sur x_{3}, etc … x_{p-1} sur x_{p} et x_{p} sur x_{1} (et qui laisse fixes les autres éléments de l’ensemble \left\{ 1,\cdots,n\right\}).

Ici, f désigne la permutation de \mathbb{N}^{\star} qui :

  • laisse 1 fixe,
  • envoie 2 sur 3 et 3 sur 2
  • envoie 4 sur 5, 5 sur 6 et 6 sur 4
  • envoie 7 sur 8, 8 sur 9, 9 sur 10 et 10 sur 7
  • et ainsi de suite …

Il est facile de comprendre que f vérifie \left(\diamondsuit\right). Vite fait : chaque entier x\geqslant1 appartient au support de l’un des cycles, disons le cycle \left(1+T_{i},\thinspace2+T_{i},\cdots,T_{i+1}\right)T_{i} désigne le i-ème nombre triangulaire :

    \[ T_{i}=1+2+\cdots+i \]

Ce cycle ayant pour longueur T_{i+1}-T_{i}=i+1, on voit que f^{i+1}\left(x\right)=x.

Mais f ne vérifie pas \left(\heartsuit\right), car peu importe l’entier n considéré, si l’entier x est assez grand, il appartiendra au support d’un cycle de longueur >n et fatalement, on aura f^{n}\left(x\right)\neq x.

Cependant : si E est supposé fini, alors les énoncés \left(\diamondsuit\right) et \left(\heartsuit\right) sont équivalents !

Observons déjà que si, pour un certain couple \left(x,n\right)\in E\times\mathbb{N}^{\star}, on a f^{n}\left(x\right)=x, alors f^{kn}\left(x\right)=x pour tout k\in\mathbb{N}^{\star} (en d’autres termes, si l’exposant n convient pour x, alors tout exposant multiple de n convient aussi).

Maintenant, posons E=\left\{ x_{1},\cdots,x_{N}\right\} et, pour chaque i\in\left\{ 1,\cdots,N\right\}, notons :

    \[ n_{i}=\min\left\{ n\in\mathbb{N}^{\star};\thinspace f^{n}\left(x_{i}\right)=x_{i}\right\} \]

Alors, en posant n=\text{ppcm}\left\{ n_{1},\cdots,n_{N}\right\}, on constate que :

    \[ f^{n}\left(x_{i}\right)=x_{i}\text{ pour tout }i\in\left\{ 1,\cdots,N\right\} \]

Et si vous êtes gêné(e) par cette histoire de ppcm, il vous suffit de poser plutôt n=\prod_{i=1}^{N}n_{i} (le produit des entiers n_{1},\cdots,n_{N}) et ça marche très bien aussi ! La seule chose qui importe est de choisir un entier n qui soit multiple de chacun des n_{i}.

4 – Caractérisation des homothéties

Cette section et la suivante supposent que vous connaissiez un peu d’algèbre linéaire : notions d’espace vectoriel, de famille libre ou liée et d’endomorphisme…

On considère :

  • un \mathbb{K}-espace vectoriel E (dont le vecteur nul est noté 0_{E}),
  • un endomorphisme u de E.

On rappelle que les homothéties de E sont les endomorphismes de la forme \lambda\thinspace id_{E} (pour \lambda\in\mathbb{K} arbitraire).

Cela dit, considérons les deux énoncés suivants, qui concernent notre endomomorphisme u :

    \[ \forall x\in E,\thinspace\exists\lambda\in\mathbb{K};\thinspace u\left(x\right)=\lambda x\qquad\left(\spadesuit\right) \]

    \[ \exists\lambda\in\mathbb{K};\thinspace\forall x\in E,\thinspace u\left(x\right)=\lambda x\qquad\left(\clubsuit\right) \]

L’implication \left(\clubsuit\right)\Rightarrow\left(\spadesuit\right) est banale (cf. encadré rose…) et l’énoncé \left(\clubsuit\right) dit que u est une homothétie.

Nous allons prouver que l’implication \left(\spadesuit\right)\Rightarrow\left(\clubsuit\right) est aussi vraie, ce qui nous donnera un nouvel exemple d’interversion de quantificateurs. Mais pour cela, il va falloir bosser un peu…

Pour commencer, observons que sous l’hypothèse \left(\spadesuit\right), si x\in E-\left\{ 0_{E}\right\} alors il existe un unique \lambda\in\mathbb{K} tel que u\left(x\right)=\lambda x. Par conséquent, on dispose de l’application qui à tout vecteur non nul x associe cet unique scalaire. Ce dernier peut être noté \lambda_{x}.

Pour conclure que \left(\clubsuit\right) est vraie, il suffit de prouver que l’application E-\left\{ 0_{E}\right\} \rightarrow\mathbb{K},\thinspace x\mapsto\lambda_{x} est constante. Pour cela, considérons un couple \left(x,y\right) de vecteurs non nuls et montrons que \lambda_{x}=\lambda_{y}, en distinguant deux cas :

  • cas I – la famille \left(x,y\right) est libre

Nécessairement x+y\neq0_{E}. On peut donc écrire :

    \[ u\left(x+y\right)=\lambda_{x+y}\thinspace\left(x+y\right) \]

Mais comme u est linéaire, on a aussi :

    \[ u\left(x+y\right)=u\left(x\right)+u\left(y\right)=\lambda_{x}\thinspace x+\lambda_{y}\thinspace y \]

Il s’ensuit que :

    \[ \lambda_{x+y}\thinspace\left(x+y\right)=\lambda_{x}\thinspace x+\lambda_{y}\thinspace y \]

c’est-à-dire :

    \[ \left(\lambda_{x+y}-\lambda_{x}\right)\thinspace x+\left(\lambda_{x+y}-\lambda_{y}\right)\thinspace y=0_{E} \]

Et comme \left(x,y\right) est libre, on en déduit que les deux coefficients de cette combinaison linéaire sont nuls. En particulier : \lambda_{x}=\lambda_{y}.

  • cas II – la famille \left(x,y\right) est liée

Il existe alors \alpha\in\mathbb{K}-\left\{ 0\right\} tel que y=\alpha x. On a d’une part :

    \[ u\left(y\right)=u\left(\alpha x\right)=\alpha\thinspace u\left(x\right)=\alpha\lambda_{x}x \]

et d’autre part :

    \[ u\left(y\right)=\lambda_{y}\thinspace y=\alpha\lambda_{y}x \]

Par conséquent :

    \[ \alpha\left(\lambda_{x}-\lambda_{y}\right)x=0_{E} \]

et comme \alpha\neq0 et x\neq0_{E}, on en conclut que \lambda_{x}=\lambda_{y} comme souhaité.

L’équivalence des énoncés \left(\spadesuit\right) et \left(\clubsuit\right) est établie.

5 – Endomorphismes nilpotents

A nouveau, on considère un endomorphisme u d’un \mathbb{K}-espace vectoriel E.

Cette fois, les deux énoncés qui nous occupent sont :

    \[ \forall x\in E,\exists q\in\mathbb{N}^{\star};\thinspace u^{q}\left(x\right)=0_{E}\qquad\left(\triangleleft\right) \]

    \[ \exists q\in\mathbb{N}^{\star};\thinspace\forall x\in E,\thinspace u^{q}\left(x\right)=0_{E}\qquad\left(\triangleright\right) \]

L’énoncé \left(\triangleright\right), on l’aura sans doute reconnu, dit que u est un endomorphisme nilpotent (c’est-à-dire qu’il existe q\in\mathbb{N}^{\star} tel que u^{q} soit l’endomorphisme nul).

De nouveau, et toujours avec l’encadré rose de la section 2, on a d’évidence : \left(\triangleright\right)\Rightarrow\left(\triangleleft\right).

Montrons que l’implication réciproque est vraie, sous l’hypothèse que E est de dimension finie. Fixons pour cela une base \left(e_{1},\cdots,e_{n}\right) de E et appliquons l’hypothèse \left(\triangleleft\right) :

Pour chaque i\in\left\{ 1,\cdots,n\right\}, il existe un entier naturel non nul q tel que u^{q}\left(e_{i}\right)=0_{E}. Notons q_{i} le plus petit tel entier et posons :

    \[ Q=\max\left\{ q_{1},\cdots,q_{n}\right\} \]

Pour tout i\in\left\{ 1,\cdots,n\right\}, puisque u^{q_{i}}\left(e_{i}\right)=0_{E} et vu que Q\geqslant q_{i}, on voit que u^{Q}\left(e_{i}\right)=0_{E}.

Soit maintenant x un vecteur quelconque de E. En décomposant x dans la base \left(e_{1},\cdots,e_{n}\right) sous la forme x=\sum_{i=1}^{n}x_{i}e_{i}, on constate que :

    \[ u^{Q}\left(x\right)=\sum_{i=1}^{n}x_{i}\thinspace u^{Q}\left(e_{i}\right)=0_{E} \]

Ainsi u^{Q}=0, ce qui prouve \left(\triangleright\right).

Ajoutons que, lorsque E est de dimension infinie, l’implication \left(\triangleleft\right)\Rightarrow\left(\triangleright\right) devient fausse. Voici un contre-exemple :

Prenons pour E l’espace \mathbb{K}\left[X\right] des polynômes à une indéterminée et à coefficients dans \mathbb{K}, et pour u l’endomorphisme de dérivation. La dérivation d’un polynôme (non constant) faisant chuter son degré d’un unité, la condition \left(\triangleleft\right) est remplie : en dérivant un quelconque polynôme un nombre suffisant de fois, on finit par tomber sur le polynôme nul.

Mais l’endomorphisme de dérivation n’est pas nilpotent, puisqu’il existe de polynômes de degré arbitrairement grand.

6 – Continuité vs. continuité uniforme : encore une histoire de quantificateurs

Cette dernière section suppose connue la définition de la continuité d’une fonction numérique. Une certaine familiarité avec la notion de continuité uniforme pourra vous faciliter les choses, mais elle ne s’impose pas.

Soit I un intervalle non trivial de \mathbb{R} (« non trivial », c’est-à-dire ni vide, ni réduit à un singleton) et soit f:I\rightarrow\mathbb{R} une application.

Voici deux énoncés qui concernent f :

    \[ \forall\epsilon>0,\thinspace\forall a\in I,\thinspace\exists\delta>0;\thinspace\forall x\in I,\thinspace\left|x-a\right|\leqslant\delta\Rightarrow\left|f\left(x\right)-f\left(a\right)\right|\leqslant\epsilon\qquad\left(\flat\right) \]

et

    \[ \forall\epsilon>0,\thinspace\exists\delta>0;\thinspace\forall a\in I,\thinspace\forall x\in I,\thinspace\left|x-a\right|\leqslant\delta\Rightarrow\left|f\left(x\right)-f\left(a\right)\right|\leqslant\epsilon\qquad\left(\sharp\right) \]

L’énoncé \left(\flat\right) dit que f est continue (par définition).

L’énoncé \left(\sharp\right) dit que f est uniformément continue (toujours par définition).

Ces deux énoncés ne sont pas équivalents en général (c’est-à-dire sans hypothèse particulière sur I). On peut le voir en considérant l’application

    \[ K:\mathbb{R}\rightarrow\mathbb{R},\thinspace x\mapsto x^{2} \]

qui est continue (comme toute fonction polynôme), mais non uniformément. Une preuve directe de cette dernière affirmation consiste à établir (pour K) la négation de \left(\sharp\right). Il faut donc prouver que :

    \[ \exists\epsilon>0;\thinspace\forall\delta>0,\thinspace\exists a\in\mathbb{R},\thinspace\exists x\in\mathbb{R};\thinspace\left|x-a\right|\leqslant\delta\:\text{et}\:\left|x^{2}-a^{2}\right|>\epsilon \]

Choisissons \epsilon=1 (toute autre réel >0 ferait aussi bien l’affaire). Pour tout \delta>0, considérons le couple \left(a,x\right)=\left(n,n+\delta\right)n désigne un entier naturel non nul. On a bien :

    \[ \left|x-a\right|\leqslant\delta\qquad\text{(puisqu'on a même l'égalité)} \]

et

    \[ \left|x^{2}-a^{2}\right|=\left(n+\delta\right)^{2}-n^{2}=2\delta n+\delta^{2} \]

donc :

    \[ \left|x^{2}-a^{2}\right|>1\qquad\text{dès que }n>\frac{1-\delta^{2}}{2\delta} \]

Cependant, si I est un segment (intervalle de la forme \left[a,b\right] avec a<b), alors l’implication \left(\flat\right)\Rightarrow\left(\sharp\right) est vraie. Ce résultat mériterait un article à lui seul, vues le nombre et l’étendue de ses applications… c’est le théorème de Heine (connu outre-atlantique sous le nom de « Heine-Cantor theorem »). Une preuve du théorème de Heine traîne dans tous les cours de MPSI/MP/MP*, mais on va tout de même détailler …

Théorème. Si f:\left[a,b\right]\rightarrow\mathbb{R} est continue, alors f est uniformément continue.

Preuve

On suppose le contraire. Il existe alors \epsilon>0 tel que :

    \[ \forall\delta>0,\exists\left(s,t\right)\in\left[a,b\right]^{2};\,\left|s-t\right|\leqslant\delta\mbox{ et }\left|f\left(s\right)-f\left(t\right)\right|>\epsilon \]

Pour tout n\in\mathbb{N}^{\star}, on peut choisir \delta=\frac{1}{n} et construire ainsi une suite \left(s_{n},t_{n}\right)_{n\geqslant1} à termes dans \left[a,b\right]^{2} vérifiant :

    \[ \forall n\in\mathbb{N}^{\star},\,\left|s_{n}-t_{n}\right|\leqslant\frac{1}{n}\mbox{ et }\left|f\left(s_{n}\right)-f\left(t_{n}\right)\right|>\epsilon \]

D’après le théorème de Bolzano-Weierstrass (selon lequel on peut extraire, de toute suite réelle bornée, une sous-suite convergente), il existe une suite \left(s_{\varphi\left(n\right)}\right)_{n\geqslant1} extraite de \left(s_{n}\right)_{n\geqslant1}, qui converge vers un réel c\in\left[a,b\right].

Comme \varphi\left(n\right)\geqslant n pour tout n\geqslant1, on a :

    \[ \forall n\in\mathbb{N}^{\star},\,\left|s_{\varphi\left(n\right)}-t_{\varphi\left(n\right)}\right|\leqslant\frac{1}{n} \]

et donc (inégalité triangulaire) :

    \[ \forall n\in\mathbb{N}^{\star},\thinspace\left|c-t_{\varphi\left(n\right)}\right|\leqslant\left|c-s_{\varphi\left(n\right)}\right|+\left|s_{\varphi\left(n\right)}-t_{\varphi\left(n\right)}\right|\leqslant\left|c-s_{\varphi\left(n\right)}\right|+\frac{1}{n} \]

Ceci prouve la convergence de \left(t_{\varphi\left(n\right)}\right)_{n\geqslant1} vers c. La continuité de f en c entraîne alors la convergence de chacune des suites \left(f\left(s_{\varphi\left(n\right)}\right)\right)_{n\geqslant1} et \left(f\left(t_{\varphi\left(n\right)}\right)\right)_{n\geqslant1} vers f\left(c\right), d’où, dès que n est assez grand :

    \[ \left|f\left(s_{\varphi\left(n\right)}\right)-f\left(t_{\varphi\left(n\right)}\right)\right|\leqslant\epsilon \]

On a obtenu une contradiction.


Merci de m’avoir lu jusqu’au bout ! J’espère que cet article de synthèse vous aura plu. N’hésitez à me laisser vos commentaires…

Partager cet article
  •  
  •  
  •  
  •  
  •  

Laisser un commentaire

Fermer le menu