Accueil H&K
Recherche:
logo

Solution des jeux de PM34

Cherchez l'erreur

Existe-t-il un infini ou plusieurs ?

L'infini est une bestiole bigrement compliquée que l'intuition appréhende particulièrement mal. Par exemple, Archimède a été le premier à considérer que les grains de sable sur une plage sont en nombre fini, puisque l'on pourrait théoriquement la vider de son sable en un nombre fini de transports de seaux embarquant chacun un nombre fini de grains. C'est dire qu'avant lui, tout nombre extrêmement grand était considéré comme égal à l'infini.

La distinction entre fini et infini, vous l'avez apprise au lycée. Maintenant, en prépa, vous apprenez qu'il y a des infinis qui sont plus grands que d'autres. Et qu'il y a aussi des infinis de même taille, y compris dans des situations surprenantes. Voici une occasion de mettre les idées au clair.

  1. VRAI

    Considérons un moment l'ensemble des nombres pairs. Il est strictement inclus dans N, et il est infini. Possède-t-il « autant d'éléments » que N ? En général, on évite d'utiliser une relation d'ordre sur les infinis. On dit de manière informelle, mais on ne l'écrit pas, que le cardinal de tel ensemble infini est plus petit ou plus grand que celui de tel autre. D'ailleurs, on convient en prépa (cela change ensuite) de n'utiliser le terme « cardinal » que pour les ensembles finis. Pour éviter que l'intuition ne nous induise en erreur, ce qu'elle est toujours prompte à faire quand il s'agit d'infinis, on raisonne sur des bijections: deux ensembles A et B (finis ou infinis) ont « autant d'éléments » si, et seulement si, il existe une bijection entre A et B.

    Rappelons qu'une bijection est une sorte de table de correspondance parfaite. Par exemple, l'ensemble {a;b;...;y;z} des 26 lettres de l'alphabet est en bijection avec l'ensemble {1;2;...;26}. Se donner l'un ou l'autre ensemble revient au même (du point de vue du comptage), il suffit de convenir que toute lettre peut être remplacée par son numéro dans l'alphabet. Dit encore autrement, un groupe de voyageurs et les sièges d'un bus sont en bijection si et seulement si tous les voyageurs peuvent s'asseoir et si aucun siège ne reste vide. Remarquons au passage que lorsqu'il existe une bijection entre deux ensembles, il en existe généralement d'autres: il suffit de demander aux voyageurs de changer de siège.

    L'ensemble des nombres pairs, qui est un sous-ensemble strict de N, est en bijection avec N. En effet, l'application qui à tout entier n associe 2n réalise une bijection entre ces deux ensembles. Ils ont donc le même « nombre d'éléments ». De même, l'application qui à tout entier n associe 2n+1 est une bijection entre N et l'ensemble des nombres impairs.

    En considérant les nombres pairs, on a « perdu » en chemin la moitié des entiers. On aurait pu se permettre d'en perdre bien plus: par exemple, l'application qui à n associe 2n est une bijection entre N et l'ensemble des puissances de 2: encore deux ensembles qui ont le même nombre d'éléments.

    Une manière commode de comprendre intuitivement pourquoi deux ensembles infinis dont l'un est strictement inclus dans l'autre peuvent avoir le même nombre d'éléments est d'imaginer un hôtel possédant une infinité de chambres numérotées 0, 1, 2, etc. Supposons qu'elles soient toutes occupées et qu'un nouveau client se présente. Pas de problème, on le met dans la chambre 0, l'ancien occupant de la chambre 0 passe dans la chambre 1, et ainsi de suite. Toute personne ayant déjà une chambre en retrouvera une autre. Remarquez qu'on ne s'intéresse guère à l'infini proprement dit, on raisonne sur des quantités arbitrairement grandes mais toujours finies, comme le numéro de la chambre.

    L'ensemble des nombres premiers n'est que l'un des sous-ensembles stricts de N qui ont autant d'éléments que lui. Comme il est inclus dans N il suffit de montrer qu'il est infini. Supposons le contraire: on peut alors dresser une liste finie de tous les nombres premiers. Multiplions-les ensemble et ajoutons 1: le nombre obtenu n'étant divisible par aucun des éléments de la liste, il est lui-même premier, ce qui contredit l'hypothèse de finitude.

    En conclusion, N et l'ensemble des nombres premiers ont bien le même nombre d'éléments.

  2. VRAI

    Considérons l'application dont les termes successifs sont 0, 1, -1, 2, -2, 3, -3, etc. On peut la formaliser par l'expression u(n) = (-1)n+1 × E((n+1)/2) pour tout entier naturel n, où E est la fonction partie entière. On vérifie aisément que c'est une injection (si u(n) = u(p) alors n = p) et une surjection de N sur Z (pour tout z entier relatif il existe p entier naturel tel que u(p) = z). C'est donc une bijection de N dans Z, ce qui montre que ces deux ensembles ont le même nombre d'éléments.

  3. VRAI

    Q a autant d'éléments que Z. Commençons par écarter quelques difficultés de définition. Q est l'ensemble des fractions p/q avec p dans Z et q dans Z*. Il contient par exemple les fractions 2/2 et 4/4, qui sont distinctes même si elles sont égales. Usuellement, quand on travaille sur Q, on se ramène à des fractions irréductibles, ce qui est tout à fait licite et pratique; quand il s'agit de compter, toutefois, on a vraiment besoin de prendre tous les éléments. On aura également besoin de l'écriture décimale d'une fraction. Il y en a toujours deux, par exemple 3,14000... et 3,13999... Ces deux écritures représentent le même nombre. On convient de ne jamais choisir celle qui ne contient que des 9 à partir d'un certain rang.

    On note Q+ l'ensemble des rationnels dont le numérateur et le dénominateur sont positifs. Cet ensemble ne contient qu'un quart des éléments de Q. Si l'on montre qu'il est équipotent à N, c'est-à-dire en bijection avec N, on saura que l'ensemble des rationnels dont le dénominateur est positif est en bijection avec Z; mais comme Z est en bijection avec N, cela revient à dire que ce deuxième ensemble de rationnels est en bijection avec N. D'où l'on déduira que Q est en bijection avec Z. On s'est ainsi ramené à des fractions qui sont des quotients d'entiers positifs.

    Répartissons les fractions p/q d'une manière qui nous arrange: on met dans un même sac toutes celles qui ont la même valeur pour p+q. Dans un premier sac on a donc 0/1, dans un deuxième 0/2 et 1/1, dans un troisième 0/3, 1/2 et 2/1, etc. Comme p et q sont des entiers naturels non nuls, il y a exactement n fractions p/q vérifiant p+q=n: il suffit de faire varier p entre 0 et n-1 et de prendre q = n-p.

    Maintenant, dans chaque sac, ordonnons les fractions par p croissant. Par exemple, dans le 5e sac, la somme p+q vaut 5 et les fractions sont, dans l'ordre, 0/5, 1/4, 2/3, 3/2 et 4/1.

    Notons # la relation binaire définie sur Q+ par:

    • si p1+q1 < p2+q2, alors p1/q1 # p2/q2;
    • si p1+q1 = p2+q2, alors p1 <= p2 est équivalent à p1/q1 # p2/q2.
    (En d'autres termes, si p1/q1 est dans un sac qui vient avant celui de p2/q2, alors p1/q1 # p2/q2, et si les deux fractions sont dans le même sac, on se ramène à l'ordre sur le numérateur.)

    Il s'agit d'une relation d'ordre puisqu'on vérifie aisément que # est réflexive (p/q # p/q), antisymétrique (si p1/q1 # p2/q2 et p2/q2 # p1/q1 alors p1/q1 = p2/q2) et transitive (si p1/q1 # p2/q2 et p2/q2 # p3/q3 alors p1/q1 # p3/q3). En outre, il est immédiat de constater que toute fraction est bien dans un sac, autrement dit que l'on a établi un ordre total sur Q. Ce n'est pas un petit résultat intermédiaire perdu dans les détails d'une longue preuve: en fait on a construit l'ordre usuel sur Q. Retenez l'idée (1° grouper par p+q constant puis 2° trier par p croissant).

    Dès lors, on peut numéroter les fractions. L'unique fraction du premier sac, 0/1, prend le numéro 0. Dans le deuxième sac on trouve successivement 0/2 et 1/1, qui prennent les numéros 1 et 2. De proche en proche, on établit ainsi une application de Q+ dans N. Cette application est surjective: tous les entiers vont servir au moins une fois à numéroter. Elle est aussi injective: si deux fractions portent le même numéro alors elles sont égales dans l'ordre #, donc égales. C'est donc une bijection donc Q+ et N ont le même nombre d'éléments.

    Plus généralement, dès que les éléments d'un ensemble peuvent être numérotés par des entiers, cet ensemble est en bijection avec N. C'est pour cette raison que N et tous les ensembles en bijection avec lui sont dits dénombrables.

    Enfin, il est commode de retenir l'ordre que nous avons défini à l'aide d'un dessin, en identifiant une fraction p/q au couple de coordonnées (p,q):

    Dans cette représentation, les « sacs » correspondent aux diagonales et l'ordre au sein d'un sac revient à se décaler vers la droite.

  4. FAUX

    L'ensemble des nombres premiers, N, Z et Q ont le même nombre d'éléments. En regardant ces ensembles comme les premiers termes d'une suite, on serait tenté de conjecturer que tous les ensembles infinis ont le même cardinal. Mais bien sûr, il n'en est pas ainsi. Il se passe quelque chose de passionnant quand on arrive à R. Commençons par montrer que N et R n'ont pas le même cardinal.

    Plaçons-nous sur un terrain qui nous arrange: on va montrer que l'intervalle [0;1[ contient plus d'éléments que N. Pour cela, considérons un ensemble dénombrable inclus dans [0;1[. Puisque cet ensemble est dénombrable, ses éléments peuvent être indicés par des entiers: notons-les r1, r2, ..., rn, etc., sans ordre particulier. Chacun de ces nombres réels peut s'écrire sous forme décimale comme un zéro, une virgule et une suite de nombres entiers. Cette suite est infinie, quitte à n'utiliser que des zéros à partir d'un certain rang.

    On construit maintenant un nombre x de la manière suivante: un zéro, une virgule, puis, à la k-ième décimale, un 7 si le k-ième chiffre après la virgule de rk vaut 4, un 4 sinon. Ainsi, avec la suite de nombres suivante:

    r1 = 0,123254...
    r2 = 0,743854...
    r3 = 0,290644...
    r4 = 0,405190...
    r5 = 0,654847...
    ...

    on construit x = 0,47447... Le choix d'un 4 et d'un 7 est arbitraire. Ce qui compte, c'est de ne jamais prendre le même chiffre que celui de la diagonale. (Pour cette raison, cette démonstration est un exemple de raisonnement dit « diagonal ».)

    Le nombre x ainsi construit n'est égal à aucun des rk: il n'est pas égal à r1 puisqu'ils n'ont pas le même premier chiffre après la virgule, il n'est pas égal à r2 puisqu'ils n'ont pas le même deuxième chiffre après la virgule, et ainsi de suite. On voit ainsi que pour tout ensemble dénombrable E inclus dans [0;1[, il existe un élément de [0;1[ qui n'est pas dans E. En particulier, [0;1[ n'est pas lui-même dénombrable, donc a fortiori R n'est pas dénombrable.

    (Au sujet de cette preuve, une remarque sur le style. On aurait tout à fait pu raisonner par l'absurde: « Supposons que [0;1[ est dénombrable et montrons que l'on obtient une contradiction ». Entre cet énoncé et la conclusion, tout le reste est quasiment identique. Mais on considère comme plus élégant de se passer du raisonnement par l'absurde lorsque, comme ici, il n'apporte strictement rien. Les mathématiciens ont tendance à préférer les spaghettis crus, qui sont géométriquement simples et, sous une forme dépouillée, dotés d'une élégante rigueur, aux spaghettis cuits et à leurs contorsions indémêlables.)

  5. VRAI

    Q est à peu de choses près N×N et il a le même cardinal que N, donc il n'est pas étonnant que R et R² aient eux aussi le même cardinal. Mais la méthode utilisée pour construire une bijection entre N et Q+ ne s'applique pas du tout pour R et R² puisque l'on ne peut pas énumérer les éléments de R.

    Comme nous le verrons deux questions plus bas, R et ]0;1[ ont le même cardinal, donc on est ramené à prouver que ]0;1[ et ]0;1[² ont le même cardinal. Pour tout couple de réels dans ]0;1[, utilisons leur notation décimale:

    0,35045627...
    0,02340958...

    Mixons maintenant leurs chiffres:

    0,3052034450...

    Cette opération est une bijection de ]0;1[² sur ]0;1[, ce qui montre que R et R² ont le même cardinal. La même idée s'étend bien pour montrer que R et Rn ont le même cardinal pour tout entier naturel n non nul.

  6. VRAI

    L'application qui à tout (x,y) associe x+iy est une bijection de R² dans C, et R² et R sont équipotents, donc C et R sont bien équipotents.

  7. VRAI

    Commençons par constater que l'on ne change pas le cardinal d'un ensemble infini en lui ajoutant ou en lui enlevant un élément: par suite, ]0;1[ et [0;1] ont le même nombre d'éléments. R et ]0;1[ sont en bijection: en effet, la fonction tan x est une bijection de ]-pi/2;pi/2[ sur R, donc tan (x pi/2) est une bijection de ]-1;1[ sur R, puis tan (x-1)pi/2 est une bijection de ]0;2[ sur R, et enfin tan (2x-1)pi/2 est une bijection de ]0;1[ sur R.

Nous vous proposons de télécharger aussi un superbe complément écrit par M. Walter Appel, professeur au Lycée du Parc (Lyon).

La balance

Énigmes

  1. Il fait du trafic d'âne.
  2. Leur fille.
  3. Vous pouvez prêter votre voiture à votre ami pour qu'il conduise la grand-mère à l'hôpital puis qu'il aille à son rendez-vous, et pendant ce temps vous discutez une heure avec le vieux sage.
  4. Toutes les cartes rouges qui manquent dans le jeu rouge y sont remplacées par des cartes noires. Comme les deux jeux contiennent le même nombre de cartes à la fin, à chaque carte noire dans le paquet rouge correspond un carte rouge dans le paquet noir. Chaque jeu contient donc exactement autant de cartes étrangères que l'autre.
  5. Il faut prendre un ticket dans la boîte étiquetée « 1 ticket gagnant + 1 ticket perdant ». On sait par hypothèse que cette étiquette ne reflète pas le contenu de cette boîte, donc elle contient soit deux tickets gagnants, soit deux tickets perdants. Si le ticket que l'on a sorti de la boîte est gagnant, on sait qu'elle contient deux tickets gagnants et il faut donc choisir celle-là.

    Si le ticket que l'on a sorti était perdant, on sait que cette boîte contient deux tickets perdants. Choisissons maintenant parmi les deux boîtes restantes. Celle étiquetée « 2 tickets gagnants » ne contient ni deux tickets gagnants (par hypothèse), ni deux tickets perdants (cette boîte a déjà été trouvée). Elle contient donc un ticket gagnant et un ticket perdant. Par suite, la dernière boîte, étiquetée « 2 tickets perdants », est celle qui contient les deux tickets gagnants.

    On peut donc gagner à coup sûr.
  6. Si l'on suppose que les poissons marqués se sont uniformément mélangés aux autres et que les poissons se déplacent aléatoirement dans tout le lac, la deuxième capture permet d'affirmer que le biologiste avait marqué, le premier jour, environ 2/50 = 4% des poissons de lac. Ce dernier en contient donc environ 1250.

Logimages et sudokus