[>] Usage des quantificateurs

 
Exercice 1  1481  Correction  

Décrire les parties de dans lesquelles évoluent x pour que les assertions suivantes soient vraies:

  • (a)

    (x>0 et x<1) ou x=0

  • (b)

    x>3 et x<5 et x4

  • (c)

    (x0 et x>1) ou x=4

  • (d)

    x0x2.

Solution

  • (a)

    [0;1[

  • (b)

    ]3;4[]4;5[

  • (c)

    {4}

  • (d)

    ]-;0[[2;+[ (et il n’y a pas d’erreurs!)

 
Exercice 2  1482  Correction  

Étant donné P, Q et R trois assertions, vérifier en dressant la table de vérité:

  • (a)

    P ou (Q et R)(P ou Q) et (P ou R)

  • (b)

    non(PQ)P et non(Q).

Solution

  • (a)

    Dans les deux cas on obtient la table

    PvvvvffffQvvffvvffRvfvfvfvfvvvvvfff.
  • (b)

    Dans les deux cas on obtient la table

    PvvffQvfvffvff.
 
Exercice 3  1483   Correction  

On dispose de neuf billes visuellement identiques, huit d’entre elles ont même masse mais la neuvième est plus lourde. Comment, en deux pesées sur une balance à deux plateaux, peut-on démasquer l’intrus?

Solution

On compare deux paquets de trois billes.
Si l’un est plus lourd que l’autre, c’est qu’il contient l’intrus.
Sinon, l’intrus est parmi les trois billes restantes.
Ainsi, on sait dans quel paquet de trois billes se situe l’intrus.
Dans ce celui-ci, on compare deux billes.
Si l’une est plus lourde que l’autre, c’est l’intrus.
Sinon, l’intrus est la troisième.

 
Exercice 4  1484    Correction  

On dispose de neuf billes visuellement identiques, elles ont toutes la même masse sauf une.
Comment, à l’aide d’une balance à deux plateaux, démasquer l’intrus en trois pesées?

Solution

L’exercice serait facile à résoudre en deux pesées si l’on savait si la bille différente était plus lourde ou plus légère que les autres. Ignorant ce fait, l’exercice devient d’autant plus croustillant…
Notons 1,2,3,4,5,6,7,8,9 nos billes.
On commence par comparer 2 lots constituées de 1,2,3 et de 4,5,6.
Si ceux-ci ont même masse alors l’intrus figure parmi 7,8,9 et l’on peut utiliser la bille 1 comme bille témoin. On compare alors les billes 1 et 7 puis les billes 1 et 8 pour démasquer l’intrus.
Si en revanche les deux premiers lots n’ont pas même masse, l’intrus se trouve parmi l’un deux. La bille 9 servira alors de bille témoin. Pour fixer les idées (et sans perte de généralités), supposons que le premier lot est plus lourd que le second. Comparons maintenant les billes 1 et 4 avec les billes 2 et 5.
Si celles-ci ont même masse commune, l’intrus se trouve dans les deux autres billes 3 et 6. Une comparaison de 3 avec 9 permet alors de savoir qui est l’intrus de 3 ou de 6.
Si celles-ci n’ont pas même masse commune, pour fixer les idées (et sans perte de généralités), supposons que 1 et 4 soient plus lourdes que 2 et 5.
Si l’intrus est plus lourd que ses congénères alors cela ne peut ni être 4 ni être 2 à cause respectivement des première et deuxième pesées.
Si l’intrus est plus léger que ses congénères alors cela ne peut ni être 2 ni être 4 à cause respectivement des première et deuxième pesées.
Dans tous les cas l’intrus est soit 1, soit 5.
Une comparaison de la bille 1 avec la bille 9 permet alors de démasquer cet intrus.

[<] Logique[>] Raisonnements

 
Exercice 5  4466  

Soit f une fonction de vers . Que signifient les phrases quantifiées suivantes?

  • (a)

    M,x,f(x)M.

  • (b)

    M,x,f(x)M.

  • (c)

    x,x0f(x)0.

  • (d)

    x,f(x)=0x=0.

  • (e)

    A,C,x,xAf(x)=C.

 
Exercice 6  1485  Correction  

Soient I un intervalle de et f:I une fonction définie sur I à valeurs réelles.
Exprimer verbalement la signification des assertions suivantes:

  • (a)

    C,xI,f(x)=C

  • (b)

    xI,f(x)=0x=0

  • (c)

    y,xI,f(x)=y

  • (d)

    x,yI,xyf(x)f(y)

  • (e)

    x,yI,f(x)=f(y)x=y.

Solution

  • (a)

    la fonction f est constante

  • (b)

    la fonction f ne peut s’annuler qu’en 0 (mais n’y est pas forcée de s’y annuler)

  • (c)

    la fonction f prend toute valeur réelle

  • (d)

    la fonction f est croissante

  • (e)

    la fonction f ne prend jamais deux fois la même valeur

 
Exercice 7  4468  

Soit f: une application. Signifier à l’aide de phrases quantifiées les affirmations suivantes:

  • (a)

    La fonction f est la fonction nulle.

  • (b)

    La fonction f s’annule.

  • (c)

    La fonction f ne s’annule que sur +.

  • (d)

    La fonction f s’annule au plus une fois.

 
Exercice 8  1486  Correction  

Soient I un intervalle de et f:I une fonction définie sur I à valeurs réelles.
Exprimer à l’aide de quantificateurs les assertions suivantes:

  • (a)

    la fonction f s’annule

  • (b)

    la fonction f est la fonction nulle

  • (c)

    f n’est pas une fonction constante

  • (d)

    f ne prend jamais deux fois la même valeur

  • (e)

    la fonction f présente un minimum

  • (f)

    f prend des valeurs arbitrairement grandes

  • (g)

    f ne peut s’annuler qu’une seule fois.

Solution

  • (a)

    xI,f(x)=0

  • (b)

    xI,f(x)=0

  • (c)

    x,yI,f(x)f(y)

  • (d)

    x,yI,xyf(x)f(y) ou encore
    x,yI,f(x)=f(y)x=y

  • (e)

    aI,xI,f(x)f(a)

  • (f)

    M,xI,f(x)>M

  • (g)

    x,yI,f(x)=0 et f(y)=0x=y.

 
Exercice 9  4467  

Soit f: une application. Écrire les négations des phrases quantifiées suivantes:

  • (a)

    M,(x,f(x)M) ou (x,f(x)M).

  • (b)

    x,f(x)0x0.

  • (c)

    (x,y)2,xyf(x)f(y).

  • (d)

    a,ε>0,α>0,x,|x-a|α|f(x)-f(a)|ε.

 
Exercice 10  1487  Correction  

Soient I un intervalle de non vide et f:I une fonction à valeurs réelles définie sur I.
Exprimer les négations des assertions suivantes:

  • (a)

    xI,f(x)0

  • (b)

    y,xI,f(x)=y

  • (c)

    M,xI,|f(x)|M

  • (d)

    x,yI,xyf(x)f(y)

  • (e)

    x,yI,f(x)=f(y)x=y

  • (f)

    xI,f(x)>0x0.

Solution

  • (a)

    xI,f(x)=0

  • (b)

    y,[xI]f(x)y

  • (c)

    M,xI,|f(x)|>M

  • (d)

    x,yI,xy et f(x)>f(y)

  • (e)

    x,yI,f(x)=f(y) et xy

  • (f)

    xI,f(x)>0 et x>0.

 
Exercice 11  1488  

Soit f:EF une application. Dans chaque cas, donner la différence de sens entre les deux assertions proposées:

  • (a)

    « xE,yF,y=f(x) » et « yF,xE,y=f(x) ».

  • (b)

    « yF,xE,y=f(x) » et « xE,yF,y=f(x) ».

Soit 𝒫(x,y) une assertion dépendant d’un couple (x,y) élément de E×F.

  • (c)

    Laquelle des deux assertions suivantes entraîne l’autre?

    « xE,yF,𝒫(x,y) »et« yF,xE,𝒫(x,y) ».

    Pourquoi ne sont-elles généralement pas équivalentes?

 
Exercice 12  1489  Correction  

Soit f: une fonction continue.
On considère les assertions suivantes:

P« x,f(x)=0 »,Q« x,f(x)=0 »

et

R« (x,f(x)>0) ou (x,f(x)<0) ».

Parmi les implications suivantes lesquelles sont exactes:

  • (a)

    PQ

  • (b)

    QP

  • (c)

    QR

  • (d)

    non(R)Q

  • (e)

    non(Q)non(P)

  • (f)

    non(P)non(R)?

Solution

  • (a)

    d) e) sont les assertions exactes (d) car f est continue…

 
Exercice 13  1490   Correction  

Soit a.

  • (a)

    Montrer que (ε0,|a|ε)a=0.

  • (b)

    Montrer que (ε>0,|a|ε)a=0.

Solution

  • (a)

    Supposons ε0,|a|ε. En particulier, pour ε=0, on a |a|0 donc a=0.

  • (b)

    Par contraposée, montrons: a0ε>0,|a|>ε.
    Supposons a0. Pour ε=|a|2 on a ε>0 et |a|>ε ce qui détermine un ε convenable.

[<] Usage des quantificateurs[>] Raisonnements par récurrence

 
Exercice 14  4469  

Montrer que 2 est un nombre irrationnel.

 
Exercice 15  3947  Correction  

Sachant 2, montrer

x,x+2.

Solution

Soit x. Si par l’absurde y=x+2 alors

2=y-x.
 
Exercice 16  3946  Correction  

Montrer

n,n(n2+1)2.

Solution

Opérons par disjonction de cas.

Cas: n pair. On peut écrire n=2p avec p et alors

n(n2+1)2=p(n2+1).

Cas: n impair. On peut écrire n=2p+1 avec p et alors

n(n2+1)2=n(2p2+2p+1).

Dans les deux cas la propriété est vraie.

 
Exercice 17  2054  Correction  

Soient 𝒫={2k|k} et ={2k+1|k} les ensembles formés respectivement des entiers pairs et impairs. Écrire une démonstration de l’identité 𝒫=.

Solution

Par l’absurde, si 𝒫, considérons x𝒫.
Comme x𝒫, il existe k tel que x=2k.
Comme x, il existe tel que x=2+1.
Par suite, 2k=2+1 puis 1/2=k- ce qui est absurde
Une erreur de raisonnement classique est de décrire x comme un nombre pair et impair en choisissant le même entier k.

 
Exercice 18  4470  
  • (a)

    Vérifier que x2+x+1 est strictement positif quelle que soit la valeur du réel x.

  • (b)

    Vérifier que lorsque n est un entier naturel, le nombre n(n2+1)2 l’est aussi.

  • (c)

    Vérifier que lorsque le produit de deux réels est nul, l’un des facteurs est nul.

 
Exercice 19  4471   
  • (a)

    Montrer que tout nombre rationnel peut s’écrire comme somme de deux nombres irrationnels.

  • (b)

    Montrer que pour tout entier naturel, il existe un nombre premier11 1 Un nombre premier est un entier p2 dont les seuls diviseurs positifs sont 1 et lui-même: 2, 3, 5, 7, 11, 13,… sont les premiers nombres premiers. Le théorème d’Euclide () assure l’existence d’une infinité de nombres premiers. qui lui est strictement supérieur.

  • (c)

    À quelle condition un réel peut-il s’écrire à la fois comme la somme et le produit des deux mêmes réels?

 
Exercice 20  4472   
  • (a)

    Soit a. Établir l’implication

    (ε0,|a|ε)a=0.
  • (b)

    Soit a. Établir l’implication

    (ε>0,|a|ε)a=0.
  • (c)

    Soient x et y deux réels. Établir l’équivalence

    x2+y2=0x=0 et y=0.

[<] Raisonnements[>] Sous-ensemble, appartenance, inclusion

 
Exercice 21  2057  Correction  

Soit (un) la suite réelle déterminée par

u0=2,u1=3 et n,un+2=3un+1-2un.

Montrer

n,un=2n+1.

Solution

Par récurrence double.
Pour n=0 et n=1: ok
Supposons la propriété établie aux rangs n et n+1 (avec n0).

un+2=3un+1-2un=HR3.2n+1+3-2.2n-2=2n+2+1.

Récurrence établie

 
Exercice 22  2060  Correction  

Le raisonnement suivant est erroné:
Montrons, par récurrence sur n*, la propriété:
𝒫(n) = n points deux à deux distincts quelconques du plan sont toujours alignés.
Pour n=1 et n=2, la propriété est vraie.
Supposons la propriété établie au rang n2.
Considérons alors n+1 points deux à deux distincts A1,A2,,An,An+1.
(HR) Les points A1,A2,,An sont alignés sur une droite 𝒟.
(HR) Les points A2,,An,An+1 sont alignés sur une droite 𝒟.
Or 𝒟 et 𝒟 contiennent les deux points distincts A2 et An, donc 𝒟=𝒟.
Par suite, A1,A2,,An,An+1 sont alignés sur la droite 𝒟=𝒟.
Récurrence établie.
Où est l’erreur?

Solution

À l’avant dernière ligne, pour que A2 et An soient distincts, il est nécessaire que n3.
L’hérédité de la récurrence ne s’enchaîne alors plus avec l’initialisation.

 
Exercice 23  2061  

Établir que tout entier naturel non nul n s’écrit

n=2k(2p+1) avec (p,k)2

en procédant de deux manières:

  • (a)

    En introduisant le plus grand entier k tel que 2k divise n.

  • (b)

    En raisonnant par récurrence.

 
Exercice 24  1274   

Soit x un réel non nul tel que x+1x soit entier.

  • (a)

    Montrer que pour tout n,

    xn+1xn.
  • (b)

    Donner un exemple de réel x non trivial11 1 Les solutions x=1 et x=-1 sont évidentes, on cherche ici une solution qui ne l’est pas. ayant la propriété qui précède.

 
Exercice 25  2058   Correction  

Montrer que

n{0,1}, 1+122++1n2>3n2n+1.

Solution

Par récurrence sur n2.
Pour n=2 ok.
Supposons la propriété établie au rang n2.

1++1n2+1(n+1)2HR3n2n+1+1(n+1)2?3(n+1)2n+3.

Vérifions l’inégalité proposée:

3n2n+1+1(n+1)2-3(n+1)2n+3=n2+2n(2n+1)(n+1)2(2n+3)0.

Récurrence établie.

 
Exercice 26  2059   Correction  

Montrer que

n*, 1! 3!(2n+1)!((n+1)!)n+1.

Solution

Par récurrence sur n1.
Pour n=1: ok
Supposons la propriété établie au rang n1.

1! 3!(2n+1)!(2n+3)!HR((n+1)!)n+1(2n+3)!?((n+2)!)n+2.

Vérifions l’inégalité proposée:

((n+1)!)n+1(2n+3)!((n+2)!n+2=(2n+3)!(n+1)!(n+2)n+2=(n+2)(n+3)(2n+3)(n+2)(n+2)(n+2)1.

Récurrence établie.

[<] Raisonnements par récurrence[>] Opérations sur les parties d'un ensemble

 
Exercice 27  1491  Correction  

Soit E={a,b,c} un ensemble. Peut-on écrire:

  • (a)

    aE

  • (b)

    aE

  • (c)

    {a}E

  • (d)

    E

  • (e)

    E

  • (f)

    {}E?

Solution

On peut écrire: a), c), e).

 
Exercice 28  1492  Correction  

Un ensemble est dit décrit en compréhension lorsqu’il réunit les éléments d’un ensemble vérifiant une propriété. Un ensemble est dit décrit en extension lorsque l’on cite ses éléments. Par exemple, {n|k,n=2k} et {2k|k} sont des descriptions respectivement en compréhension et en extension de l’ensemble des entiers pairs.

  • (a)

    Décrire en compréhension et en extension l’ensemble {1,3,5,7,}.

  • (b)

    Décrire en compréhension et en extension l’ensemble {1,10,100,1000,}.

  • (c)

    Décrire en extension l’ensemble des nombres rationnels.

  • (d)

    Décrire en compréhension l’ensemble ]0;1].

  • (e)

    Décrire en compréhension et en extension l’ensemble des valeurs prises par une fonction f:.

  • (f)

    Décrire en compréhension l’ensemble des antécédents d’un réel y par une fonction f:.

Solution

  • (a)

    {1,3,5,7,}={n|k,n=2k+1}={2k+1|k}.

  • (b)

    {1,10,100,1000,}={x|k,x=10k}={10k|k}.

  • (c)

    ={pq|p,q*}.

  • (d)

    ]0;1]={x| 0<x1}.

  • (e)

    {y|x,y=f(x)}={f(x)|x}.

  • (f)

    {x|f(x)=y}.

 
Exercice 29  1493   Correction  

Décrire 𝒫(𝒫({a}))a désigne un élément.

Solution

𝒫({a})={,{a}} et 𝒫(𝒫({a}))={,{},{{a}},{,{a}}}.

 
Exercice 30  2200   Correction  

Soit A une partie d’un ensemble E. On appelle fonction indicatrice de la partie A dans E, l’application 1A:E définie par:

1A(x)={1 si xA0 sinon.

De quels ensembles les fonctions suivantes sont-elles les fonctions indicatrices?

  • (a)

    min(1A,1B)

  • (b)

    max(1A,1B)

  • (c)

    1A.1B

  • (d)

    1-1A

  • (e)

    1A+1B-1A.1B

  • (f)

    (1A-1B)2

Solution

  • (a)

    AB

  • (b)

    AB

  • (c)

    AB

  • (d)

    EA complémentaire de A dans E.

  • (e)

    AB

  • (f)

    AΔB=(AB)(AB)

[<] Sous-ensemble, appartenance, inclusion[>] Injectivité, surjectivité, bijectivité

 
Exercice 31  1494  

Soient A, B et C trois parties d’un ensemble E.

  • (a)

    Montrer A(BC)=(AB)(AC).

  • (b)

    On suppose ABAC et ABAC. Montrer BC.

  • (c)

    On suppose AB=C. Montrer AB=BC.

  • (d)

    On suppose AB=BC=CA et AB=BC=CA. Montrer que les trois ensembles A, B et C sont égaux.

 
Exercice 32  4478  

Soient A, B et C trois parties d’un ensemble E. Vérifier

(AB)(BC)(CA)=(AB)(BC)(CA).
 
Exercice 33  1496   Correction  

Étant donné A, B et C trois parties de E, justifier les équivalences suivantes:

  • (a)

    ABAB=B.

  • (b)

    A=BAB=AB.

  • (c)

    AB=ACBAC

  • (d)

    {AB=ACAB=ACB=C

Solution

  • (a)

    () Supposons AB. On a toujours BAB.
    Pour xAB. Que xA ou xB on a xB donc ABB. Ainsi AB=B.

    () Supposons AB=B. Puisque AAB, on a AB.

  • (b)

    () Supposons A=B. On a AB=A=AB.

    () Supposons AB=AB. On a AABABB et de même BA donc A=B.

  • (c)

    () Supposons AB=AC.
    On a BAB=ACAAB=ACC.

    () Supposons BAC. AB=A=AC.

  • (d)

    () Supposons AB=AC et AB=AC.
    Soit xB.
    Si xA alors xAB=AC donc xC.
    Si xA alors sachant xAB on a xAC, or xA donc xC.
    Dans les deux cas, xC. Ainsi, BC et de manière symétrique CB d’où l’égalité.

    () Si B=C alors clairement AB=AC et AB=AC.

 
Exercice 34  1495  Correction  

Étant donné A et B deux parties de E, justifier

EAEB=BA.

Solution

Puisque la privation correspond à l’intersection avec le complémentaire

EAEB=EAEEB=BEA=BA.
 
Exercice 35  1497  Correction  

Soient A et B deux parties de E, on appelle différence symétrique de A et B, l’ensemble

AΔB=(AB)(BA).

Montrer

AΔB=(AB)(AB).

Solution

Soit xE.

xAΔB (xA et xB) ou (xB et xA)
(xA ou xB) et (xA ou xA)
   et (xB ou xB) et (xB ou xA)
xAB et xAB
x(AB)(AB)

d’où l’égalité des ensembles.

 
Exercice 36  1498  Correction  

Étant données A, B et C trois parties d’un ensemble E, montrer que:

  • (a)

    AΔB=AΔCB=C

  • (b)

    AB=ABA=B

  • (c)

    AΔB=ABA=B=.

Solution

  • (a)

    Si AΔB=AΔC alors pour tout xB:
    Si xA alors xAΔB et donc xAΔC et puisque xA, xC.
    Si xA alors xAΔB et donc xAΔC et puisque xA, xC.
    Dans les deux cas xC. Ainsi BC et un raisonnement symétrique donne CB puis l’égalité.
    Réciproque immédiate.

  • (b)

    AB=AAEB=AAEB or AEBBEA et donc AB=ABA=B.

  • (c)

    AΔB=(AB)(AB) donc AΔB=ABAB==ABA=B=.

 
Exercice 37  4479   

(Différence symétrique)

On définit la différence symétrique de deux parties A et B d’un ensemble E par

AΔB=déf(AB)(AB¯).

Soient A, B et C trois parties de E.

  • (a)

    Calculer AΔA, AΔA¯, AΔE et AΔ.

  • (b)

    Vérifier la propriété d’associativité

    AΔ(BΔC)=(AΔB)ΔC.
  • (c)

    Établir

    AΔB=AΔCB=C.
 
Exercice 38  1499   

Soient A et B des parties d’un ensemble E.

Discuter et résoudre l’équation AX=B d’inconnue X(E).

 
Exercice 39  1500   Correction  

Soient A,B deux parties de E.
Discuter et résoudre l’équation AX=B d’inconnue X𝒫(E).

Solution

Si BA alors l’équation n’a pas de solution.
Si BA. Soit X une solution de l’équation.
On a X=(AX)(A¯X)=BC avec C=A¯XA¯.
Inversement, pour X=BC avec CA¯, AX=(AB)(AC)=B.
Ainsi 𝒮={X=BC|CA¯}={X𝒫(E)|BXBA¯}.

[<] Opérations sur les parties d'un ensemble[>] Image directe, image réciproque d'une partie

 
Exercice 40  4476  

Soit s:* l’application définie par s(n)=n+1. Montrer que l’application s est bijective:

  • (a)

    En constatant la définition d’une application bijective.

  • (b)

    En vérifiant injectivité et surjectivité.

  • (c)

    En déterminant une application susceptible d’être sa bijection réciproque.

 
Exercice 41  1502  

Soient a, b et c trois réels tels que c0 et a2+bc0. On introduit E={a/c}.

On considère la fonction f:EE définie par

f(x)=ax+bcx-a.
  • (a)

    Justifier que l’application f est bien définie.

  • (b)

    Calculer ff. En déduire que f est une bijection dont on déterminera l’application réciproque.

 
Exercice 42  4483   

On considère l’application f: définie par

f(n)={n2 si n est pair-n+12 sinon.

Montrer que l’application f est bijective et exprimer sa bijection réciproque.

 
Exercice 43  4475   

Soient f: et g: les applications déterminées par:

f(k)=2ketg(k)={k/2 si k est pair(k-1)/2 si k est impair.
  • (a)

    Étudier la bonne définition des applications f et g.

  • (b)

    Étudier les injectivités des applications f et g.

  • (c)

    Étudier les surjectivités des applications f et g.

  • (d)

    Préciser les applications gf et fg. Sont-elles bijectives?

 
Exercice 44  4481   

Soit f: l’application définie par f(z)=z2.

  • (a)

    Montrer que l’application f est surjective mais non injective.

On note Ω={z|Re(z)>0}.

  • (b)

    On considère f|Ω:Ω la restriction de f au départ de Ω. Montrer que f|Ω est injective. Est-elle surjective?

  • (c)

    On considère l’application f:Ω- définie par f(z)=z2. Montrer que celle-ci est bijective.

 
Exercice 45  1511    

Soient A et B deux parties d’un ensemble E et

f:{(E)(A)×(B)X(XA,XB).
  • (a)

    Montrer que f est injective si, et seulement si, AB=E.

  • (b)

    À quelle condition la fonction f est-elle surjective?

 
Exercice 46  4480  

Soit f une fonction réelle définie au départ d’un intervalle I.

Montrer que, si f est strictement monotone, alors f est injective.

 
Exercice 47  1508  Correction  

Soient E,F,G trois ensembles, f1,f2:EF et g:FG.
On suppose gf1=gf2 et g injective. Montrer que f1=f2.

Solution

Pour tout xE on a (gf1)(x)=(gf2)(x) c’est-à-dire g(f1(x))=g(f2(x)) donc f1(x)=f2(x). Ainsi f1=f2.

 
Exercice 48  1509  Correction  

Soient E,F,G trois ensembles, f:EF et g1,g2:FG.
On suppose f surjective et g1f=g2f. Montrer que g1=g2.

Solution

Pour tout yF, il existe xE tel que y=f(x) et alors g1(y)=(g1f)(x)=(g2f)(x)=g2(y) donc g1=g2.

 
Exercice 49  4482   

Soit f:EF une application.

Que dire de la restriction de f au départ de E et à valeurs dans f(E))? Que dire de plus si l’on sait f injective?

 
Exercice 50  1504   

Soient f:EF et g:FG deux applications. Établir:

  • (a)

    gf injective f injective.

  • (b)

    gf surjective g surjective.

  • (c)

    gf injective et f surjective g injective.

  • (d)

    gf surjective et g injective f surjective.

 
Exercice 51  1505   Correction  

Soient E,F,G trois ensembles, f:EF, g:FG et h:GE
Établir que si hgf est injective et que gfh et fhg sont surjectives alors f,g et h sont bijectives.

Solution

Supposons hgf injective et gfh ainsi que fhg surjectives.
Puisque (hg)f est injective, on a f injective.
Puisque f(hg) est surjective, on a f surjective.
Par suite, f est bijective et l’on peut introduire f-1.
Par composition hg=(hgf)f-1 est injective et par suite g est injective.
D’autre part gfh est surjective et donc g aussi.

Finalement, g est bijective. Par composition, h=(hg)g-1 est injective et h=f-1(fhg)g-1 est surjective donc h est bijective.

 
Exercice 52  1507   Correction  

Soient f:EF et g:FE deux applications telles que fgf soit bijective.
Montrer que f et g sont bijectives

Solution

Par l’exercice précédent, fgf bijective implique f injective et f surjective.
Ainsi f est bijective et l’on peut introduire f-1.
g=f-1(fgf)f-1 est bijective par composition d’applications bijectives.

 
Exercice 53  1506    

Soient E un ensemble et f:EE une application telle que fff=f.

Montrer que f est injective si, et seulement si, f est surjective.

 
Exercice 54  4489    

Soient E et F des ensembles non vides. Montrer qu’il existe une injection de E dans F si, et seulement si, il existe une surjection de F sur E.

 
Exercice 55  4490    

Soit E un ensemble. Montrer qu’il n’existe pas d’applications surjectives de E vers (E).

[<] Injectivité, surjectivité, bijectivité[>] Relations d'équivalence

 
Exercice 56  4473  

Soit f: la fonction définie par f(x)=x2. Déterminer les ensembles suivants:

  • (a)

    f([-1;2])

  • (b)

    f-1([1;2[).

 
Exercice 57  1512  Correction  

Décrire l’image directe de par la fonction exponentielle.
Déterminer l’image réciproque de l’intervalle [-1;4] par la fonction f:xx2 définie sur .

Solution

exp()=+* et f-1([-1;4])=[-2;2].

 
Exercice 58  1510  Correction  

Soit f:EI une application surjective. On pose, pour tout iI, Ai=f-1({i}).
Montrer que les Ai sont non vides, deux à deux disjoints, de réunion égale à E.

Solution

Puisque f est surjective, les Ai sont non vides.
Si AiAj alors pour xAiAj on a f(x)=i et f(x)=j donc i=j.
Par contraposée: ijAiAj=.
Soient xE et i=f(x). On a xAi. Ainsi EiIAi puis l’égalité.

 
Exercice 59  4474  

Soit f:EF une application.

  • (a)

    Soient A et A deux parties de E. Montrer

    AAf(A)f(A).
  • (b)

    Soient B et B deux parties de F. Établir

    BBf-1(B)f-1(B).
  • (c)

    Soient A une partie de E et B une partie de F. Établir

    Af-1(f(A))etf(f-1(B))B.
 
Exercice 60  4485   

Soit f:EF une application.

  • (a)

    Établir

    A(E),Af-1(f(A))etB(F),f(f-1(B))B.
  • (b)

    Montrer

    f est injectiveA(E),A=f-1(f(A)).
  • (c)

    Montrer

    f est surjectiveB(F),f(f-1(B))=B.
 
Exercice 61  1513   

Soit f:EF une application.

  • (a)

    Soient A1 et A2 deux parties de E. Montrer

    f(A1A2)=f(A1)f(A2)etf(A1A2)f(A1)f(A2).
  • (b)

    Soient B1 et B2 deux parties de F. Montrer

    f-1(B1B2)=f-1(B1)f-1(B2)etf-1(B1B2)=f-1(B1)f-1(B2).
 
Exercice 62  4484   

Soit f:EF une application. À quelle condition sur f peut-on affirmer

(A1,A2)(E)2,f(A1A2)=f(A1)f(A2)?
 
Exercice 63  1517    

Soit f:EF une application. Montrer

f est bijectiveA(E),f(EA)=Ff(A).
 
Exercice 64  4491    

Soit f:(E)(E) une application croissante au sens de l’inclusion, c’est-à-dire une application vérifiant

(A,B)(E)2,ABf(A)f(B).

Montrer qu’il existe une partie A de E vérifiant f(A)=A.

[<] Image directe, image réciproque d'une partie[>] Relations d'ordre

 
Exercice 65  4477  

On définit une relation11 1 C’est la relation de commensurabilité: deux longueurs sont commensurables lorsqu’elles sont multiples d’une longueur commune. binaire sur l’ensemble + en posant

xy(k,)(*)2,kx=y.
  • (a)

    Montrer que définit une relation d’équivalence.

  • (b)

    Soit x+. Décrire la classe d’équivalence de x.

 
Exercice 66  2643  Correction  

Soit une relation binaire sur un ensemble E à la fois réflexive et transitive.
On définit les nouvelles relations 𝒮 et 𝒯 par:

x𝒮y(xy et yx) et x𝒯y(xy ou yx).

Les relations 𝒮 et 𝒯 sont-elles des relations d’équivalences?

Solution

Les relations 𝒮 et 𝒯 sont clairement réflexives et symétriques.
Soient x,y,zE.
Supposons x𝒮y et y𝒮z.
On a alors xy et yz donc xz et aussi yx et zy donc zx puis x𝒮z.
Le raisonnement n’est plus valable avec 𝒯 et l’on peut présumer que 𝒯 ne sera pas une relation d’équivalence.
Prenons pour la relation divise définie sur *. On a 26 et 36 donc 2𝒯6 et 6𝒯3 or 23.
Ici la relation 𝒯 n’est pas transitive.

 
Exercice 67  2983  Correction  

On considère sur (E,E) la relation binaire définie par:

fgφ𝒮(E),fφ=φg.
  • (a)

    Montrer que est une relation d’équivalence.

  • (b)

    Décrire la classe d’équivalence d’une fonction donnée f(E,E).

Solution

  • (a)

    fIdE=IdEf donc ff.

    Si fg alors il existe φ𝒮(E) telle que fφ=φg mais alors gφ-1=φ-1f donc gf.

    Si fg et gh alors il existe φ,ψ𝒮(E) telles que fφ=φg et gψ=ψh donc fθ=θh avec θ=φψ𝒮(E). Ainsi, fh.

    Finalement, est une relation d’équivalence.

  • (b)

    Pour g(E,E),

    gCl(f)φ𝒮(E),g=φ-1fφ.

    Finalement,

    Cl(f)={φ-1fφ|φ𝒮(E)}.
 
Exercice 68  4488   

Soit f:EF une application. On définit une relation binaire sur E par:

xyf(x)=f(y).
  • (a)

    Montrer que définit une relation d’équivalence sur E.

  • (b)

    Exprimer la classe d’équivalence d’un élément x quelconque de E.

 
Exercice 69  2357     CENTRALE (MP)Correction  

Soient E un ensemble de cardinal n, une relation d’équivalence sur E ayant k classes d’équivalence et G={(x,y)E2|xy} le graphe de supposé de cardinal p.

Montrer que n2kp.

Solution

Notons n1,,nk les cardinaux respectifs des k classes d’équivalence de . D’une part,

n=n1++nk,

et d’autre part,

p=n12++nk2.

Par l’inégalité de Cauchy-Schwarz,

(n1++nk)2k(n12++nk2).
 
Exercice 70  2644   Correction  

Soient E un ensemble et A une partie de E.

On définit une relation sur (E) par:

XYXA=YA.
  • (a)

    Montrer que est une relation d’équivalence

  • (b)

    Décrire la classe d’équivalence de X(E)

Solution

  • (a)

    La relation étudiée est évidemment réflexive, symétrique et transitive.

  • (b)

    Pour Y(E),

    YCl(X)YA=XA.

    Soit YCl(X). On a YA=XA. Pour tout xYA, on a xYA=XA et xA donc xXA. Ainsi, YAXA et inversement XAYA donc XA=YA.

    Puisque Y=(YA)(YA), on a Y=(XA)B avec B(A).

    Inversement, soit Y=(XA)B avec B(A). On a

    YA=(XA)(BA)=(XA¯)A=XA.

    Finalement,

    Cl(X)={(XA)B|B(A)}.
 
Exercice 71  2984   Correction  

Soit une relation binaire réflexive et transitive sur un ensemble E. On définit une relation 𝒮 sur E par

x𝒮yxy et yx.

Montrer que 𝒮 est une relation d’équivalence et que permet de définir une relation d’ordre sur les classes d’équivalences de 𝒮.

Solution

𝒮 est réflexive, symétrique et transitive sans difficultés.

On définit

Cl(x)Cl(y)xy.

La relation est bien définie, réflexive transitive.

Si Cl(x)Cl(y) et Cl(y)Cl(x) alors x𝒮y donc Cl(x)=Cl(y).

 
Exercice 72  2985   Correction  

Soient (G,×) un groupe et H un-sous groupe de (G,×).

On définit une relation binaire sur G par:

xyxy-1H.

Montrer que est une relation d’équivalence et en décrire les classes d’équivalence.

Solution

Soit xG. On a xx car xx-1=1H.

Soient x,yG. Si xy alors xy-1H et donc yx-1H d’où yx.

Soient x,y,zG. Si xy et yz alors xy-1H et yz-1H donc xz-1H d’où xz.

Finalement, est une relation d’équivalence.

Pour aG,

xCl(a) xa
xa-1H

On en déduit

Cl(a)=Ha={ha|hH}.
 
Exercice 73  3243      X (MP)Correction  

Soit G un groupe multiplicatif de cardinal pα avec p premier et α*.
Montrer que

Z(G){1}.

Solution

Considérons la relation binaire sur G définie par

y1y2xG,xy1=y2x.

Il est immédiat de vérifier que est une relation d’équivalence sur G. Les classes d’équivalence de forment donc une partition de G ce qui permet d’affirmer que le cardinal de G est la somme des cardinaux des classes d’équivalence de .
Une classe d’équivalence d’un élément y est réduite à un singleton si, et seulement si,

xG,xy=yx.

c’est-à-dire

yZ(G).

En dénombrant G en fonction des classes d’équivalence de et en isolant parmi celles-ci celles qui sont réduites à un singleton on a

Card(G)=Card(Z(G))+N

avec N la somme des cardinaux des classes d’équivalence de qui ne sont pas réduites à un singleton.
Pour poursuivre, montrons maintenant que le cardinal d’une classe d’équivalence de la relation divise le cardinal de G.
Considérons une classe d’équivalence {y1,,yn} pour la relation et notons

Hi={xG|xy1=yix}.

Pour i{1,,n}, puisque y1yi, il existe xiG tel que

xiy1=yixi.

Considérons alors l’application φ:H1Hi définie par

φ(x)=xix.

On vérifie que cette application est bien définie et qu’elle est bijective.
On en déduit

Card(H1)==Card(Hn)=m

et puisque G est la réunion disjointes des H1,,Hn

Card(G)=mn=pα.

Ainsi, toutes les classes d’équivalences qui ne sont pas réduites à un élément ont un cardinal multiple de p et donc pN.
Puisque p divise Card(G)=Card(Z(G))+N, on a

pCard(Z(G)).

Sachant Z(G) (car 1Z(G)) on peut affirmer

Card(Z(G))p.

[<] Relations d'équivalence

 
Exercice 74  1518  Correction  

On définit une relation binaire sur +* par:

xyn,y=xn.

Montrer que est une relation d’ordre. Cet ordre est-il total?

Solution

Soit x>0, on a x=xn pour n=1 donc xx. La relation est réflexive.
Soient x,y>0, si xy et yx alors il existe n,m tels que y=xn et x=ym.
On a alors x=xnm donc ln(x)=nmln(x)
Si x=1 alors y=xn=1=x.
Si x1 alors ln(x)0 puis 1=nm. Or n,m donc n=m=1 puis x=y.

Finalement, la relation est antisymétrique.
Soient x,y,z>0. Si xy et yz alors il existe n,m tels que y=xn et z=ym.
On a z=xmn avec mn donc xz. La relation est transitive.

Finalement, est une relation d’ordre.
Cet ordre n’est pas total car, par exemple, 2 et 3 ne sont pas comparables.

 
Exercice 75  1522  

Soit f:E une application injective. On définit sur E une relation binaire par

xyf(x)f(y).
  • (a)

    Montrer que est une relation d’ordre sur E.

  • (b)

    S’agit-il d’une relation d’ordre totale?

 
Exercice 76  4486   

(Ordre lexicographique)

Sur E=2, on définit une relation binaire par

(x,y)(x,y)x<x ou (x=x et yy).
  • (a)

    Vérifier que définit une relation d’ordre sur E.

  • (b)

    S’agit-il d’une relation d’ordre totale?

 
Exercice 77  4487   

Soit la relation binaire définie sur le demi-plan E={(a,b)2|ab} par

(a,b)(a,b)(a,b)=(a,b) ou ba.
  • (a)

    Montrer que est une relation d’ordre sur E.

  • (b)

    S’agit-il d’une relation d’ordre totale?

 
Exercice 78  1520   Correction  

On définit une relation binaire sur {z|Im(z)0} par:

zz|z|<|z| ou (|z|=|z| et Re(z)Re(z)).

Montrer qu’il s’agit d’une relation d’ordre total.

Solution

est clairement réflexive.
Si zz et zz alors nécessairement |z|=|z| et Re(z)=Re(z) donc z=z car Im(z),Im(z)0.
Si zz et zz′′ alors si |z|<|z′′| alors zz′′ et sinon |z|=|z|=|z′′| et donc Re(z)Re(z)Re(z′′) ce qui permet à nouveau d’affirmer zz′′.
Pour z,z{z|Im(z)0}.
Si |z|<|z| alors zz
Si |z|>|z| alors zz.
Si |z|=|z| alors dans le cas où Re(z)Re(z) on a zz et, dans le cas complémentaire, on a zz.
Dans tout les cas z et z sont comparables, la relation d’ordre est totale.

 
Exercice 79  1521  Correction  

Soit E l’ensemble des couples (I,f) formé d’un intervalle I et d’une fonction réelle définie sur I.
On définit une relation sur E par: (I,f)(J,g)IJ et g|I=f.
Montrer que est une relation d’ordre sur E.

Solution

La relation est clairement réflexive.
Si (I,f)(J,g) et (J,g)(I,f) alors IJ, JI et g|I=f donc I=J et f=g.
Si (I,f)(J,g) et (J,g)(K,h) alors IJK et hI=(h|J)|I=g|I=f donc (I,f)(K,h).

Finalement, est une relation d’ordre.

 
Exercice 80  1523   Correction  

Soient A,B deux parties d’un ensemble E ordonné par .
On suppose que A et B ont chacun un plus grand élément.
Qu’en est-il de AB lorsque l’ordre est total? lorsqu’il ne l’est pas?
Que dire de AB?

Solution

Si l’ordre est total AB possède un plus grand élément: max(AB)=max(max(A),max(B)).
Si l’ordre n’est pas total, les plus grands éléments de A et de B peuvent ne pas être comparés aux éléments de A et B. Dans (*,), pour A={2,4} et B={3,9}, A et B ont un plus grand élément alors que AB n’en a pas.
AB peut ne pas posséder de plus grand élément, cet ensemble peut notamment être vide.

 
Exercice 81  1525   Correction  

Soit E un ensemble ordonné par une relation .
Un tableau à n lignes et p colonnes est formé d’éléments ai,jE avec i indice de ligne(1in) et j indice de colonne(1jp).
On note le plus petit élément de chaque colonne et l’on prend le plus grand de ces plus petits:

max1jp(min1inai,j).

On note aussi le plus grand élément de chaque ligne et l’on prend le plus petit de ces plus grands:

min1in(max1jpai,j).
  • (a)

    Comparer ces deux nombres.

  • (b)

    Donner un exemple de non égalité.

Solution

  • (a)

    Pour tout 1mp,

    ai,mmax1jpai,j

    donc

    min1inai,mmin1inmax1jpai,j

    puis

    max1mpmin1inai,mmin1inmax1jpai,j.
  • (b)

    Pour le tableau (1432)

    max1j2min1i2ai,j=2 et min1i2max1j2ai,j=3.
 
Exercice 82  2055   Correction  

Montrer qu’il n’existe pas de suite strictement décroissante d’entiers naturels.

Solution

Par l’absurde, supposons que (un) soit une telle suite.
A={un|n} est une partie non vide de , elle possède donc un plus petit élément m.
Puisque mA, il existe n tel que m=un. Mais alors un+1<unm=minA. Absurde.

 
Exercice 83  1524   Correction  

Soit (E,) un ensemble ordonné tel que toute partie non vide admet un plus petit élément et un plus grand élément.
Montrer que E est fini.

Solution

Par l’absurde supposons E infini.
Posons x0=minE, x1=minE{x0},…, xn=minE{x0,x1,,xn-1},…
L’ensemble {x0,,xn,} n’a pas de plus grand élément. Absurde.



Édité le 08-11-2019

Bootstrap Bootstrap 3 - LaTeXML [LOGO] - Powered by MathJax Powered by MathJax