DM n°2

N˚ Ñ N
#
˚
N
Exercice 1. On considère l’application de Collatz, définie par Col : 2 si N pair .
N ÞÑ
3N ` 1 si N impair
On note Coln la composée n-ième de l’application Col.
1. Déterminer Coli p14q, pour i P rr0, 5ss.
2. Montrer que Col n’est pas injective.
3. Montrer que Col est surjective.
Exercice 2. Soit E un ensemble.
I. Soit F Ă PpEq un ensemble de parties de E. On dit que F est stable par intersection si @A, B P F, A X B P F.
␣ (
1) On prend n ě 1, E “ rr1, nss, et F “ A Ă E | 1 P A . Justifier que F est stable par intersection.
␣ (
2) On prend n ě 3, E “ rr1, nss, et F “ A Ă E | Card A est divisible par 2 l’ensemble des parties de E de cardinal
pair. La famille F est-elle stable par intersection ?
3) Soient F1 , F2 deux familles stables par intersection. Montrer que F1 X F2 est stable par intersection.
4) On note F d “ tA, A P Fu. Montrer que F d est stable par réunion.
II. Soit F Ă PpEq une famille de parties de E. On suppose que F est stable par intersection.
čn
1) Montrer que pour n ě 1, et A1 , . . . , An P F, on a Ai P F.
i“1
2) ⋆ Donner un exemple d’une famille F Ă PpNq stable par intersection et d’une suite pAn qnPN de parties de N
`8
č
telle que @n P N, An P F et An R F.
n“0
La conjecture suivante est un problème ouvert : Pour toute famille F non triviale et stable par réunion d’ensembles
finis, il existe un élément appartenant à au moins la moitié des ensembles de F. Ou de manière équivalente, pour toute
famille stable par intersection, il existe un élément qui appartient à au plus la moitié des ensembles.
Exercice 3. On cherche à déterminer toutes les fonctions f : R Ñ R qui vérifient

pEq : @x, y P R, f pf px ` yq ` yf pxqq ` px ` 1qf pyq “ x.

1. Préliminaires
(a) Soit f : E Ñ F et g : F Ñ G deux applications. Montrer que si g ˝ f est surjective, g est surjective et que
si g ˝ f est injective, f est injective.
(b) Soit g : R Ñ R une fonction. Montrer g est bijective si et seulement si la fonction g 2 : x ÞÑ gpgpxqq est
bijective.
(c) Soient a, b P R et g : x ÞÑ ax ` b une fonction affine. Montrer que g est bijective si et seulement si a ‰ 0.
2. Montrer que parmi les fonctions affines, c’est-à-dire les fonctions de la forme x ÞÑ ax ` b pour a, b P R, la fonction
x ÞÑ ´x est la seule qui vérifie pEq.
3. On se donne à présent une fonction f vérifiant pEq. Pour x P R, déterminer une expression simple de f pf pxqq en
fonction de x et f p0q. En déduire que f est bijective si et seulement si f p0q ‰ 1.
4. ⋆ On considère le cas où f p0q “ 1. On note E “ f ´1 pt´1uq.
(a) Montrer que E est non vide, puis que ´1 P E.
(b) En appliquant pEq à un couple px, yq judicieusement choisi, montrer que 0 P E. Qu’en déduit-on ?
On peut montrer par ailleurs que si f p0q ‰ 1, f est nécessairement affine.
Exercice 4. Théorème de Cantor-Bernstein.
I. Équipotence.
On dit que deux ensembles E et F sont équipotents, ce que l’on note E „ F , s’il existe une bijection de E sur F ,
c’est-à-dire s’il existe une application g : E Ñ F bijective. On note E ĺ F s’il existe une injection de E dans F .
1) Si E et F sont des ensembles finis. Que peut-on dire sur les cardinaux |E| et |F | si E „ F ? et si E ĺ F ?
2) Montrer que s0,1r „ s1,`8r.
3) Montrer que „ est une relation d’équivalence sur la classe des ensembles («l’ensemble» des ensembles).
4) Montrer que s0,1r „ R.
II. Théorème de Cantor-Bernstein. On veut montrer que si E ĺ F et F ĺ E, alors E „ F . On considère f : E Ñ F
et g : F Ñ E deux injections.
1) Soit h : E Ñ F une application et pAi qiPI une famille de parties de E.
´ď ¯ ď
a) Montrer que h Ai “ hpAi q.
iPI iPI
 b) On suppose h injective et on se donne B une partie de E. Montrer que si y P B, alors hpyq P hpBq.
En déduire que hpBq “ hpEq X hpBq.´č ¯ č
c) Montrer que si h est injective, h Ai “ hpAi q.
iPI iPI
2) ⋆ On définit une suite pAn qnPN de parties de E par Ť A0 “ gpF q “ EzgpF q et @n P N, An`1 “ gpf pAn qq. Autrement
dit, @n P N, An “ pg ˝ f qpnq pA0 q. On pose A “ nPN An .
a) Montrer que pour n P N˚ , A0 et An sont disjoints. En déduire que les An sont deux à deux disjoints.
b) Montrer que f induit une bijection de A sur f pAq.
c) Déterminer l’image de f pAq par g. En déduire que g induit une bijection de f pAq sur AzA0 . Puis de f pAq “
F zf pAq sur A “ EzA. On note g ´1 : A Ñ f pAq la bijection réciproque.
3) Expliciter une bijection entre E et F .
III. Applications
1) ⋆ Déterminer une application injective f : N2 Ñ N. En déduire que N „ N2 , puis que N „ Q.
2) ♣ Soit E un ensemble, on veut montrer que E ≁ PpEq. Plus précisément, on montre par l’absurde qu’il n’existe
pas de surjection f : E Ñ PpEq. En considérant F “ tx P E | x R f pxqu, aboutir à une contradiction.
Exercice 5.
I. Parties syndétiques. Pour p P N˚ , un ensemble S Ă N est dit p-syndétique si pour tout n P N, SXrrn, n ` p ´ 1ss ‰ H.
Un ensemble S Ă N est dit syndétique s’il existe p P N˚ tel que S soit p-syndétique.
1) Que dire d’une partie S Ă N qui soit 1-syndétique ?
2) Montrer que l’ensemble des entiers pairs est syndétique.
3) Montrer que l’ensemble des carrés parfaits n’est pas syndétique.
4) ⋆ Montrer que l’ensemble des nombres premiers n’est pas syndétique.
II. Parties épaisses. On dit que T Ă N est épaisse si pour tout ℓ P N˚ , il existe n P N tel que rrn, n ` ℓ ´ 1ss Ă T .
1) L’ensemble des entiers ␣ npairs est-il épais ?2 (
2) Dessiner l’ensemble 2 ` m | pn, mq P N et m ď n et montrer qu’il est épais.
III. Lien entre les deux notions. Soit S Ă N. Montrer l’équivalence entre
(i) S est syndétique.
(ii) NzS n’est pas épais.
(iii) S rencontre toute partie épaisse, c’est-à-dire que pour toute partie épaisse T Ă N, on a S X T ‰ H.
IV. ⋆ Parties syndétiques par morceaux et régularité par partitions.
Pour p, ℓ P N˚ , on dit qu’une suite a1 ă . . . ă aℓ d’entiers naturels est une p-chaîne de longueur ℓ si @i P
rr1, ℓ ´ 1ss, ai`1 ´ ai ď p.
On dit que S Ă N est p-syndétique par morceaux si S contient des p-chaînes arbitrairement longues.
1) Montrer l’équivalence entre
(i) A est syndétique par morceaux.
(ii) il existe p tel que l’ensemble A ` rr0, p ´ 1ss “ ta ` k, a P A, k P rr0, p ´ 1ssu soit épais.
(iii) il existe S syndétique et T épais tels que A “ S X T .
2) Montrer que si A est syndétique par morceaux, et A “ B Y C est une partition de A, alors B ou C est syndétique
par morceaux.
3) En déduire que si tA1 , . . . , An u est une partition de N, alors l’une des parties est syndétique par morceaux.
Indications Exercice 2.
II. 1) Il s’agit de montrer par récurrence que pour tout n P N˚ , et toutes parties A1 , . . . , An , A1 X ¨ ¨ ¨ X An P F.
Proposition de rédaction : «Soit n P N˚ , on suppose que pour toutes n parties appartenant à F, leur intersection
appartient à F. On considère n ` 1 parties A1 , . . . , An`1 appartenant à F.
2) On peut également chercher une famille F stable par réunion, qui n’est pas stable par réunion dénombrable (sur
N), puis prendre F d .
Indications Exercice 3.
2. Injecter ax ` b dans pEq, puis des valeurs particulières de x, y.
3. Utiliser les questions précédentes.
Indications Exercice 4.
I. 4) Utiliser la transitivité et la question 2 : on a, par exemple s0,1r „„ s1,`8r „ s0,`8r „ R, à justifier.
II. 1) c) On peut procéder par égalités d’ensembles en utilisant les questions précédentes, ou par double inclusion
directement.
2) a) Par l’absurde, si x P An XAm pour des indices n ă m, déterminer une fonction h injective telle que An “ hpA0 q
et Am “ hpAm´n q.
c) Pour déterminer l’image de f pAq par g, puis celle de f pAq, utiliser une question précédente.
III. 1) Penser à la décomposition en facteurs premiers, ou à une application vue en TD.
Indications Exercice 5.
I. 4) Considérer les entiers n! ` 2, n! ` 3, . . . , n! ` n.