Devoir 03

corrigé

Notations

• P( A ) désigne l'ensemble des parties de l'ensemble A .
• Soit f une application A ® B . Pour une partie X de A (c'est à dire X Î P( A ) ), on pose [^f]( X ) ={ f( x)  |  x Î X } (= image directe), tandis que pour une partie Y de B (c'est à dire Y Î P( B ) ), on pose [^( ^tf)]( Y ) ={ x Î A |  f( x) Î Y } (=image réciproque).

1  Premiers résultats

On considère une application f : E ® F .

1. Montrer que, pour tout X Î P( E ) , on a : X Ì [^( ^tf)]( [^f]( X ) ) .

   1. Soient x Î X , y=f( x) et Y=[^f]( X ) . Par définition, on a f( x) Î [^f]( X ) c'est à dire y Î Y et donc x Î [^( ^tf)]( Y ) .
2. Montrer que si f est injective, on a en fait une égalité.

   1. Soit z Î [^( ^tf)]( [^f]( X ) ) . Il existe donc y Î Y tel que y=f( z) . Mais cet y est l'image d'un x Î X , soit y=f( x) = f( z) ce qui prouve z=x et donc z Î X .

      1

3. Montrer que, pour tous A B Î P( E ) , on a : [^f]( AÇB ) Ì ( [^f]( A ) Ç[^f]( B ) ) .

   1. Soit x Î AÇB . On a x Î A et donc x Î [^f]( A ) . De même x Î [^f]( B ) .
4. Montrer que, si f est injective, on a en fait une égalité.

   1. Soit y Î ( [^f]( A ) Ç[^f]( B ) ) . On a y Î [^f]( A ) et il existe donc un a Î A tel que y=f( a) . De même il existe b Î B tel que y=f( b) . Par injectivité, on a a=b et donc a Î AÇB . D'où y Î [^f]( AÇB ) .

      1

5. Une partition d'un ensemble est une famille de sous ensembles, non vides, deux à deux disjoints et dont la réunion recouvre l'ensemble initial. Montrer que, si f est injective, et si { A, B, C} est une partition de E , alors { [^f]( A ) , [^f]( B ) , [^f]( C ) } est une partition de [^f]( E ) . Donner un contre-exemple pour une application non-injective.

   1. Comme A_j est non vide, [^f]( A_j ) ne peut être vide.
   2. S'il existait z Î [^f]( A ) Ç[^f]( B ) on aurait (Q 1.4) z Î [^f]( AÇB ) ce qui imposerait AÇB ¹ Æ.
   3. Le cours donne directement que [^f]( E ) =È[^f]( A_j ) .
   4. Un contre-exemple simple est fourni par une application constante : pour X ¹ Æ, tous les [^f]( X ) sont égaux.

      2

6. Soient p Î N, { D₀, D₁ .. D_p} une partition de E et { K₁, K₂, K₃} une partition de D₀ . Montrer que { K₁, K₂, K₃, D₁ .. D_p} est alors une partition de E .

   1. Par définition même, ces ensembles sont non vides.
   2. Un élément commun à K_j et à D_k serait élément de D₀ÇD_k , tandis que toutes les autres intersections deux à deux sont vides par définition.
   3. On a K₁ÈK₂ÈK₃ÈD₁È .. ÈD_p=D₀ÈD₁È .. ÈD_p=E .

      1

2  Théorème de la double injection (Bernstein)

On suppose que E, F sont deux ensembles non vides, et qu'il existe une injection f : E ® F et une injection g : F ® E . L'objectif est de montrer qu'il existe alors une bijection de E vers F . On pose h=g°f et A=[^h]( E ) .

2.1  Cas particuliers

1. Montrer que si A=[^g]( F ) , alors f est bijective.

   1. La fonction f est déjà injective. En appliquant [^( ^tg)]( ) aux deux membres de A=[^g]( [^f]( E ) ) =[^g]( F ) , on obtient (Q1.2) [^f]( E ) =F : f est donc également surjective.
2. Montrer que si [^g]( F ) =E , alors g est bijective.

   1. La fonction g est déjà injective, et la condition [^g]( F ) =E n'est rien d'autre que la surjectivité de g .

      1

2.2  Exemple

Pour cette seule question, on choisit E=F=N, f : x® 2x et g : y® 3y . On sait que chaque nombre entier m ³ 1 peut s'écrire m=2^{a( m)} 3^{b( m)} q , le nombre entier q n'étant divisible ni par 2 ni par 3. On pose a( 0) = b( 0) = ¥. Montrer que les ensembles A, B, C puis les ensembles A_n , B_n et C_n sont caractérisés par des relations portant sur les a et les b de leurs éléments.

1. Les ensembles E=F sont caractérisés par a ³ 0, b ³ 0 . L'ensemble [^f]( E ) , obtenu en multipliant par 2 , est caractérisé par a ³ 1 . L'ensemble [^g]( F ) est l'ensemble des multiples de 3 et se caractérise par b ³ 1 . L'ensemble A=[^h]( E ) est l'ensemble des multiples de 6 : on a donc A₀={ x Î N |  a( x) ³ 1, b( x) ³ 1 } . On remarquera que 0 Î A .
2. L'ensemble B=[^g]( F ) \A est donc caractérisé par ( b ³ 1)  et non( a ³ 1, b ³ 1) c'est à dire B₀={ x |  a = 0, b ³ 1 } . De même C=E\[^g]( F ) est caractérisé par ( b ³ 0)  et non( b ³ 1) c'est à dire C₀={ x |  a ³ 0, b = 0 } .
3. Appliquer h consiste à multiplier par 6. On a donc A_n={ x |  a ³ n+1, b ³ n+1 } , B_n={ x |  a = n, b ³ n+1 } et C_n={ x |  a ³ n, b = n } .

   3

2.3  Cas général

1. Montrer que { A, B, C} est une partition de E , puis que, pour tout n Î N, { A_n+1, B_n+1, C_n+1} est une partition de A_n .

   1. C=Æ serait g surjective, B=Æ serait f surjective et enfin A=[^h]( E ) ¹ Æ.
   2. Puis AÈB=[^g]( F ) , AÇB=Æ tandis que ( AÈB) ÇC=Æ et ( AÈB) ÈC=E .
   3. Tout cela se perpétue par Q1.5.
2. Montrer que, pour tout n Î N, { A_n, B₀, B₁, .. B_n, C₀, C₁, .. C_n} est une partition de E .

   1. application directe de Q1.6.

      2

3. On pose U=Ç_{n Î N}A_n , V₀=È_{n Î N}B_n , W=È_{n Î N}C_n et enfin V=UÈV₀ . Montrer que V et W forment une partition de E .

   1. On a : Æ ¹ B₀ Ì V et Æ ¹ C₀ Ì W .
   2. Si y Î ÈC_m , il existe au moins un n Î N tel que y Î C_n . Par Q2.3 ce n est unique, y n'appartient à aucun B_m et y Ï A_n . On a donc y Ï U et y Ï V₀ : les ensembles V et W sont donc disjoints.
   3. Les éléments qui sortent d'un A vont vers un B ou un C : tout élément de E se retrouve dans E .
   4. Et donc {  V, W } est une partition de E .
   5. Une remarque : si x Î U , alors x Î A₀ . Si x Î V₀\B₀ , on a aussi x Î A₀ . Par conséquent, tout élément de V=UÈV₀ est appartient à A₀ÈB₀ i.e. V Ì [^g]( F ) .

      2

4. Montrer que ``si x Î V alors k( x) = x et si x Î W alors k( x) = h( x) '' définit une bijection k : E ® [^g]( F ) .

   1. Si x Î V , on a x Î A₀ ou x Î B₀ , et donc k( x) = x Î [^g]( F ) . Si x Î W alors k( x) = g( f( x) ) Î [^g]( F ) . L'ensemble des images est donc contenu dans [^g]( F ) .
   2. Un élément z Î [^g]( F ) ne peut appartenir à C₀=E\[^g]( F ) . Il est donc situé soit dans V soit dans W\C₀ . Dans le premier cas, z=k( z) . Dans le second cas, il existe n Î N et c₀ Î C₀ tels que z=( hⁿ⁺¹) ( c₀) = h( ( hⁿ) ( c₀) ) . Posons c_n=( hⁿ) ( c₀) Î C_n. Comme c_n Î W , on a k( c_n) = h( c_n) = z . Dans les deux cas, z est une image par k : on voit que k est une application sur [^g]( F ) .
   3. Si k( x) = k( y) avec x, y Î V on a directement x=y . Si k( x) = k( y) avec x, y Î W on a h( x) = h( y) , mais h est injective. Enfin, si l'on avait k( x) = k( y) avec x Î V , y Î W , on aurait x=h( y) . Or [^h]( ÈC_m ) =È_{m ³ 1}C_m Ì W alors que (Q2.3) x Ï W .
   4. On a donc montré que k est une bijection E ® [^g]( F ) .

      3

5. Montrer que, pour tout x Î E , k( x) possède un et un seul antécédent par g . Soit alors m( x) cet antécédent. Montrer que m est une bijection de E sur F .

   1. On a vu que tout k( x) est dans [^g]( F ) (existence) et on sait que g est injective (unicité). Soit alors m( x) l'unique z tel que g( z) = k( x) . Il est clair que m va de E vers F , et que "x Î E : ( g°m) ( x) = k( x) .
   2. Si m( x₁) = m( x₂) on a g( m( x₁) ) = g( m( x₂) ) c'est à dire k( x₁) = k( x₂) et donc x₁=x₂ puisque k injective. L'application m est donc injective à son tour.
   3. Soit y Î F . Il a déjà été remarqué que g( y) Î C₀ est exclus. On a donc soit g( y) Î V , soit g( y) Î W\C₀ . Dans le premier cas, posons v=g( y) Î V : on a g( y) = v=k( v) i.e. m( v) = y . Dans le deuxième cas, w=g( y) Î W peut s'écrire w=( hⁿ⁺¹) ( c₀) . On a donc w=h( x) avec un x Î W , d'où g( y) = w=k( x) soit m( x) = y . On a donc montré que m est surjective.

      3

   .../...
6. On reprend l'exemple 2.2. Décrire ce que sont les ensembles U, V, W ainsi que les applications k et m à l'aide des fonctions a et b.

   1. On voit que U={ 0} , tandis que :

      X	règle pour x	k( x)	m( x)	règle pour m( x)
      V0	a < b	[ a, b]	m( x) = x/3 i.e. [ a, b-1]	a £ b
      W	a ³ b	[ a+1,b+1]	m( x) = 2 x i.e. [ a+1, b]	a > b

   2. La tabulation des premières valeurs de la fonction m donne :