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.

Exemple 1

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\]

Exemple 2

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, le symbole ('x' ou 'r') peut être choisi librement … tant qu’il ne s’agit pas d’un symbole déjà utilisé dans le contexte !

Terminologie

Le symbole \forall se lit « quel que soit » ou « pour tout » : c’est le quantificateur universel.

Le symbole \exists se lit « il existe » : c’est le quantificateur existentiel. Il signifie, plus précisément : « il existe au moins »

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 :

    \[\boxed{\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 :

    \[\boxed{\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 si nos deux quantificateurs se suivent … et ne se ressemblent pas, alors les choses se compliquent …

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

Considérons l’exemple suivant :

    \[\boxed{\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 :

    \[\boxed{\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.

Remarque

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 en des termes 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. En effet, 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 est parfois valide … et peut révéler quelque chose de profond. C’est ce que nous allons maintenant détailler 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) :

    \[\boxed{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 simplement :

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

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

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


    \[\boxed{\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 la remarque qui termine la section 2, 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 :

Proposition

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

Preuve (cliquer pour déplier / replier)

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.

Rappel : 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 \boxed{\left(\clubsuit\right)\Rightarrow\left(\spadesuit\right)} est banale (cf. la remarque qui termine la section 2 …) et l’énoncé \left(\clubsuit\right) dit que u est une homothétie.

Nous allons prouver que l’implication \boxed{\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 :

Premier cas : 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}.

Deuxième cas : 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 la remarque qui termine la section 2, on voit que : \boxed{\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 \displaystyle{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 \boxed{\left(\triangleleft\right)\Rightarrow\left(\triangleright\right)} devient fausse !

Contre-exemple en dimension infinie

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.

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

6 – Continuité vs. continuité uniforme

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 vous facilitera les choses, mais elle ne s’impose pas puisque tout est défini ci-dessous.

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

    \[\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 (et même é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 fermé et borné), alors l’implication \boxed{\left(\flat\right)\Rightarrow\left(\sharp\right)} est vraie : c’est le théorème de Heine.

Pour en savoir plus à ce sujet, voir cet article, consacré à la notion de convergence uniforme.


Vos questions ou remarques seront toujours les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.

Partager cet article
  •  
  •  
  •  
  •  

Laisser un commentaire