
Pour toute partie de
notons
sa fonction indicatrice.
On rappelle que, par définition :
L’hypothèse dit exactement que l’application :
Vu que est entier, cette dernière inégalité équivaut à :
Afin de montrer que cette minoration de est optimale, utilisons le théorème donnant l’existence et l’unicité, pour un entier naturel non nul, de son écriture en base 2.
Si nécessaire, consulter les vidéos Système de numération – 1 et Système de numération – 2, où cette question est étudiée en détail.
Afin de simplifier la présentation, supposons que pour un certain
. Ce qui suit pourrait être facilement adapté si
n’est pas une puissance de 2.
On peut considérer, sans perte de généralité, que :
Chaque entier possède une écriture binaire, de la forme :
Considérons alors, pour tout l’ensemble :
Les ensembles sont des parties distinctes de
En effet, si
et
alors
mais
donc
En outre, étant donnés deux entiers dans
leurs écritures binaires diffèrent, donc il existe
tel que
Autrement dit :
On a donc construit une famille de
Pour consulter l’énoncé, c’est ici