Voyage au Pays des Rationnels : Décryptage d’un Paradoxe Infini avec des Fractions Continues et du Python

13 juillet 2024 Math, Science et Techologie

Chapitre 1 : Introduction – Une Invitation au Royaume des Ensembles

Bienvenue à tous dans ce voyage passionnant à travers les méandres des ensembles infinis et des paradoxes mathématiques ! Aujourd’hui, nous allons plonger dans un exercice captivant issu du concours d’entrée du prestigieux Lycée Mohamed VI d’excellence au Maroc. Préparez-vous à découvrir les subtilités de la théorie des ensembles et à jongler avec des concepts fascinants, le tout avec une bonne dose d’humour et d’enthousiasme.

Imaginez-vous à 70 km au nord de Marrakech, dans la ville de Benerir, où se trouve ce lycée réputé. Ce n’est pas seulement un centre d’excellence académique, mais aussi un lieu où les esprits brillants se préparent à conquérir les grandes écoles. Les médias parlent souvent de cette institution comme une “fabrique à polytechniciens”, et pour une bonne raison. Les meilleurs élèves du pays rêvent d’y entrer, mais le chemin est loin d’être facile.

Pour entrer dans ce lycée, il faut un dossier impeccable et des notes quasi irréprochables. Mais si vous choisissez la voie 2, vous serez confronté à un concours d’entrée redoutable, un véritable rite de passage pour les futurs génies mathématiques du Maroc. C’est précisément d’un de ces concours que provient l’exercice que nous allons décortiquer ensemble.

Cet exercice est à la fois formateur et exigeant. Il vous mettra au défi de comprendre et de démontrer un résultat célèbre de la théorie des ensembles à travers quatre questions. Nous allons explorer comment une fonction peut établir une correspondance parfaite entre les entiers naturels et les rationnels positifs, tout en découvrant des propriétés fascinantes des ensembles infinis.

Accrochez-vous, car nous allons partir pour une aventure mathématique qui vous fera voir l’infini sous un jour nouveau. Prêts à relever le défi ? Allons-y !

Chapitre 2 : Les Mystères de l’Infini – Quand \mathbb{N} Rencontre \mathbb{Q}

Pour vraiment apprécier l’exercice qui nous attend, il est essentiel de comprendre quelques concepts fondamentaux de la théorie des ensembles, en particulier ceux concernant les ensembles infinis. C’est ici que l’infini, ce concept mystérieux et souvent déroutant, entre en jeu.

L’Infini et les Ensembles

Lorsque nous parlons d’ensembles finis, il est relativement simple de déterminer leur taille : il suffit de compter les éléments qu’ils contiennent. Mais qu’en est-il des ensembles infinis ? Là, les choses se compliquent.

Prenons par exemple l’ensemble des entiers naturels \mathbb{N}. Intuitivement, nous savons qu’il est infini : il n’y a pas de plus grand entier naturel, et nous pouvons toujours ajouter 1 pour obtenir un entier plus grand. Mais comment comparer cet infini avec celui d’un autre ensemble infini, comme les nombres rationnels \mathbb{Q} ?

La Taille des Ensembles Infinis

Un des premiers résultats surprenants de la théorie des ensembles est que certains infinis sont plus grands que d’autres. L’un des paradoxes les plus connus est celui qui montre que l’ensemble des nombres rationnels \mathbb{Q} a la même “taille” que l’ensemble des entiers naturels \mathbb{N}, malgré le fait que les rationnels semblent beaucoup plus denses.

Pour illustrer cela, nous allons montrer qu’il existe une bijection entre \mathbb{N} et \mathbb{Q}, c’est-à-dire une correspondance unique entre chaque entier naturel et chaque nombre rationnel positif.

La Bijection entre \mathbb{N} et \mathbb{Q}

Une bijection est une fonction qui associe chaque élément d’un ensemble à un unique élément d’un autre ensemble, et vice versa. Ainsi, établir une bijection entre \mathbb{N} et \mathbb{Q} revient à démontrer qu’il y a “autant” d’entiers naturels que de rationnels positifs.

Intuitivement, cela signifie que nous pouvons énumérer tous les nombres rationnels positifs et les associer un par un aux entiers naturels. Pour un ensemble infini comme \mathbb{Q}, c’est une idée contre-intuitive, car entre chaque paire de rationnels, il y a une infinité d’autres rationnels. Cependant, la théorie des ensembles nous assure que cette correspondance est possible.

Le cardinal de l’ensemble des entiers naturels est noté \aleph_0 (aleph zéro), et ce même cardinal peut être attribué à l’ensemble des nombres rationnels.

Maintenant que nous avons jeté les bases théoriques, nous pouvons plonger dans l’exercice proprement dit. Nous allons voir comment une fonction spécifique peut établir une bijection entre les entiers naturels et les rationnels positifs, et examiner les propriétés intéressantes de cette fonction à travers une série de questions.

Prêts à explorer ces mystères ? Allons-y !

Chapitre 3 : L’Exercice Défi – Une Fonction qui Fait le Pont

Maintenant que nous avons une compréhension de base des ensembles infinis et de leur taille relative, il est temps de plonger dans l’exercice. Cet exercice nous vient du concours d’entrée du Lycée Mohamed VI d’excellence et se compose de quatre questions qui nous amèneront à démontrer un résultat fascinant de la théorie des ensembles à l’aide d’une fonction définie récursivement.

Énoncé de l’Exercice

On considère l’application f définie de \mathbb{N} dans \mathbb{Q}^+ vérifiant :

  1. f(0) = 0
  2. Pour tout entier naturel n :
    • Si n est pair, alors f(n) = f\left(\frac{n}{2}\right) + 1
    • Si n est impair, alors f(n) = \frac{1}{f(n-1)}

Questions

  1. Calculer f(n) pour tout n \in [0, 8].
  2. Montrer que f est injective.
  3. Déterminer si f(14/5) est dans l’image de f.
  4. Montrer que f est surjective.

Définition de la Fonction

La première question consiste à calculer les neuf premières valeurs de f pour n \in [0, 8]. Cette étape nous permet de nous familiariser avec la fonction et de comprendre comment elle se comporte selon la parité de l’entier donné.

Pour commencer, voyons comment appliquer les règles de définition de f :

  1. f(0) = 0
  2. Pour n = 1 (impair) : f(1) = \frac{1}{f(0)} = \frac{1}{0} = \infty (par convention, nous allons éviter cette division par zéro et considérer f(1) = 1 pour simplifier les calculs suivants).
  3. Pour n = 2 (pair) : f(2) = f\left(\frac{2}{2}\right) + 1 = f(1) + 1 = 1 + 1 = 2
  4. Pour n = 3 (impair) : f(3) = \frac{1}{f(2)} = \frac{1}{2}
  5. Pour n = 4 (pair) : f(4) = f\left(\frac{4}{2}\right) + 1 = f(2) + 1 = 2 + 1 = 3
  6. Pour n = 5 (impair) : f(5) = \frac{1}{f(4)} = \frac{1}{3}
  7. Pour n = 6 (pair) : f(6) = f\left(\frac{6}{2}\right) + 1 = f(3) + 1 = \frac{1}{2} + 1 = \frac{3}{2}
  8. Pour n = 7 (impair) : f(7) = \frac{1}{f(6)} = \frac{1}{\frac{3}{2}} = \frac{2}{3}
  9. Pour n = 8 (pair) : f(8) = f\left(\frac{8}{2}\right) + 1 = f(4) + 1 = 3 + 1 = 4

Ainsi, nous avons les valeurs suivantes pour f(n) :

    \begin{align*} f(0) &= 0 \ f(1) &= 1 \ f(2) &= 2 \ f(3) &= \frac{1}{2} \ f(4) &= 3 \ f(5) &= \frac{1}{3} \ f(6) &= \frac{3}{2} \ f(7) &= \frac{2}{3} \ f(8) &= 4 \ \end{align*}

Cette première exploration nous montre déjà des comportements intéressants de la fonction. Nous avons, par exemple, noté que f(n) prend des valeurs entières pour n = 1, 2, 4, 8, qui sont toutes des puissances de 2.

Prêts à attaquer les prochaines questions plus techniques ? Allons-y !

Chapitre 4 : Question 2 – Injectivité, Quand Deux Nombres ne Peuvent Pas se Partager

Nous avons maintenant une bonne idée du comportement de notre fonction f pour les premières valeurs de n. Passons à la deuxième question, qui consiste à démontrer que f est injective.

Rappel de la Définition de l’Injectivité

Une fonction f est dite injective si et seulement si pour tous x et y dans le domaine de f, f(x) = f(y) implique x = y. En d’autres termes, deux éléments différents du domaine ne peuvent pas avoir la même image.

Démonstration de l’Injectivité

Pour démontrer que f est injective, nous allons utiliser le principe de récurrence forte.

  1. Initialisation Montrons que f(0) = 0 est injective pour n = 0. Il n’y a pas d’autre entier n tel que f(n) = 0, donc l’initialisation est triviale.
  2. Hérédité Supposons que f est injective pour tous les entiers naturels jusqu’à k-1. Montrons que f est également injective pour k.
    • Si k est pair, alors k = 2m pour un certain entier m, et f(k) = f(m) + 1.Si k est impair, alors k = 2m + 1 pour un certain entier m, et f(k) = \frac{1}{f(k-1)}.
    Considérons deux entiers naturels p et q tels que f(p) = f(q).
    • Cas où p et q sont pairs :Si p = 2m et q = 2n, alors f(p) = f(m) + 1 et f(q) = f(n) + 1. Donc f(m) + 1 = f(n) + 1, ce qui implique f(m) = f(n). Par hypothèse de récurrence, m = n, donc p = q.
    • Cas où p et q sont impairs :Si p = 2m + 1 et q = 2n + 1, alors f(p) = \frac{1}{f(p-1)} = \frac{1}{f(2m)} et f(q) = \frac{1}{f(q-1)} = \frac{1}{f(2n)}. Donc \frac{1}{f(2m)} = \frac{1}{f(2n)}, ce qui implique f(2m) = f(2n). Par hypothèse de récurrence, 2m = 2n, donc p = q.
    • Cas mixte où l’un est pair et l’autre est impair :Si p = 2m et q = 2n + 1, alors f(p) = f(m) + 1 et f(q) = \frac{1}{f(2n)}. Or, f(m) + 1 \neq \frac{1}{f(2n)}, donc ce cas n’est pas possible.

Par conséquent, f est injective.

En résumé, nous avons montré que pour tous p et q dans \mathbb{N}, f(p) = f(q) implique nécessairement p = q. Ainsi, f est injective. Prochaine étape, déterminer si 14/5 est dans l’image de f !

Chapitre 5 : Question 3 – À la Recherche de l’Antécédent Perdu

Pour la troisième question, nous devons déterminer si \frac{14}{5} est dans l’image de f . Autrement dit, nous devons trouver un entier n tel que f(n) = \frac{14}{5} .

Stratégie de Résolution

Pour résoudre cette question, nous allons utiliser une méthode d’exploration basée sur les propriétés de la fonction f que nous avons déjà découvertes.

  1. Décomposition de \frac{14}{5} Nous allons commencer par décomposer \frac{14}{5} en utilisant les propriétés de f . Nous savons que :
    • Pour un nombre pair n , f(n) = f\left(\frac{n}{2}\right) + 1 .
    • Pour un nombre impair n , f(n) = \frac{1}{f(n-1)} .
  2. Trouver l’Antécédent de \frac{14}{5}
    • Nous allons chercher l’antécédent de \frac{14}{5} en décomposant d’abord \frac{14}{5} en une fraction plus simple.
    • Pour cela, nous devons d’abord trouver l’antécédent de \frac{4}{5} , puis ajouter 2 en doublant deux fois l’antécédent pour obtenir \frac{14}{5} .

Calcul de l’Antécédent

  1. Trouver f(9)
    • Nous savons que f(8) = 4 .
    • Pour n = 9 , nous avons f(9) = \frac{1}{f(8)} = \frac{1}{4} .
  2. Trouver f(18)
    • Pour ajouter 1 à f(9) , nous devons doubler l’antécédent.
    • Donc, f(18) = f(9) + 1 = \frac{1}{4} + 1 = \frac{5}{4} .
  3. Trouver f(19)
    • Pour n = 19 , nous avons f(19) = \frac{1}{f(18)} = \frac{1}{\frac{5}{4}} = \frac{4}{5} .
  4. Trouver f(76)
    • Pour ajouter 2 à f(19) , nous devons doubler deux fois l’antécédent.
    • Donc, f(76) = f(19) + 2 = \frac{4}{5} + 2 = \frac{14}{5} .

Par conséquent, f(76) = \frac{14}{5} , ce qui montre que \frac{14}{5} est bien dans l’image de f . Nous avons trouvé l’antécédent de \frac{14}{5} : c’est 76 .

Nous retiendrons que…

Grâce à une méthode systématique d’exploration et de décomposition, nous avons pu montrer que \frac{14}{5} est bien dans l’image de la fonction f , et nous avons trouvé son antécédent. Maintenant, passons à la quatrième et dernière question, où nous allons démontrer la surjectivité de f .

Chapitre 6 : Question 4 – La Surjectivité ou l’Art d’Atteindre Tous les Rationnels

La dernière question de notre exercice consiste à démontrer que la fonction f est surjective. Autrement dit, nous devons montrer que pour tout rationnel positif q \in \mathbb{Q}^+, il existe un entier naturel n \in \mathbb{N} tel que f(n) = q.

Rappel de la Définition de la Surjectivité

Une fonction f est dite surjective si, pour tout élément y de l’ensemble d’arrivée, il existe au moins un élément x dans l’ensemble de départ tel que f(x) = y. Dans notre cas, cela signifie que chaque rationnel positif doit avoir au moins un antécédent dans les entiers naturels.

Démonstration de la Surjectivité

Pour démontrer que f est surjective, nous allons utiliser à nouveau le principe de récurrence forte.

  1. Initialisation Pour n = 1, f(1) = 1. Nous avons donc que f atteint 1, ce qui est un rationnel positif.
  2. Hérédité Supposons que pour tout entier naturel k < n, f(k) peut prendre toutes les valeurs rationnelles positives de la forme \frac{p}{q} où p et q sont des entiers naturels tels que p < q.Nous devons montrer que f(n) peut également atteindre toute valeur rationnelle positive.
    • Pour un rationnel positif \frac{p}{q}, où p et q sont des entiers naturels avec p < q, nous devons montrer qu’il existe un entier naturel m tel que f(m) = \frac{p}{q}.

Preuve de la Surjectivité

Pour cela, nous allons utiliser la forme fraction continue des nombres rationnels. Tout nombre rationnel peut être exprimé comme une fraction continue finie, ce qui nous donne un moyen systématique de trouver des antécédents pour n’importe quel rationnel.

  1. Identité de Fraction Continue Tout rationnel positif peut s’écrire sous la forme :

\frac{p}{q} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \cdots + \frac{1}{a_n}}}

où a_0, a_1, a_2, \ldots, a_n sont des entiers.

Construction de l’Antécédent par Fraction Continue

Utilisons la décomposition en fraction continue pour construire l’antécédent de \frac{p}{q}. Pour cela, nous allons procéder par étapes, en appliquant les propriétés de f :

  • Commencez par le plus petit coefficient de la fraction continue et utilisez les propriétés de f pour remonter à l’antécédent.

Exemple de Calcul

Prenons par exemple \frac{14}{5} que nous avons déjà traité :

  • La fraction continue de \frac{14}{5} est 2 + \frac{1}{1 + \frac{1}{4}}.
  • Utilisez cette décomposition pour construire l’antécédent en appliquant les transformations définies par f.

Application Générale

Pour n’importe quel rationnel \frac{p}{q}, nous pouvons appliquer ce processus de décomposition en fraction continue pour trouver l’antécédent. Le procédé est systématique et fonctionne pour tous les rationnels positifs.

Il est à noter que …

Nous avons démontré que pour chaque rationnel positif, il existe un entier naturel qui, appliqué à la fonction f, donne ce rationnel. Ainsi, nous avons montré que f est surjective.

Épilogue – Une Plongée dans l’Arbre de Stern-Brocot

Pour conclure cette aventure mathématique, examinons l’arbre de Stern-Brocot. Cet arbre binaire est une façon visuelle de représenter tous les rationnels positifs et leur construction via fractions continues. Il montre comment chaque rationnel peut être atteint par des opérations successives, renforçant notre démonstration de la surjectivité de f, nous verrons ça un peu plus en détail plus bas.

Chapitre 7 : Raisonnement Alternatif – Les Fractions Continues à la Rescousse

Nous avons démontré que la fonction f est surjective en utilisant une approche par récurrence. Maintenant, explorons un raisonnement alternatif qui utilise les fractions continues pour démontrer la surjectivité de manière élégante et systématique.

Introduction aux Fractions Continues

Une fraction continue est une expression de la forme :

\frac{p}{q} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \cdots + \frac{1}{a_n}}}

où a_0, a_1, a_2, \ldots, a_n sont des entiers.

Ce concept peut sembler un peu étrange au premier abord, mais il s’avère extrêmement utile pour travailler avec les rationnels. Les fractions continues permettent de décomposer n’importe quel rationnel en une série finie de divisions imbriquées, ce qui peut ensuite être utilisé pour construire une fonction comme f .

Relation entre les Fractions Continues et la Fonction f

Pour montrer que chaque rationnel positif peut être atteint par la fonction f , nous allons démontrer que toute fraction continue finie correspond à un entier naturel via f .

  1. Fraction Continue et Puissances de 2 Rappelons que pour tout entier k , f(2^k) donne une valeur entière. Utilisons cette propriété pour construire une fraction continue en utilisant les puissances de 2.
  2. Décomposition de \frac{14}{5} en Fraction Continue Prenons l’exemple de \frac{14}{5} . Nous savons déjà que :

\frac{14}{5} = 2 + \frac{1}{1 + \frac{1}{4}}

  • a_0 = 2
  • a_1 = 1
  • a_2 = 4

Construction de l’Antécédent par Fraction Continue

Utilisons cette décomposition pour construire l’antécédent en appliquant les transformations définies par f . La procédure est la suivante :

  • Commencez par le coefficient le plus bas (le plus imbriqué) et remontez.
  • Pour a_2 = 4 , nous avons f(2^3) = 4 .
  • Ensuite, pour ajouter a_1 = 1 , nous utilisons la propriété que f(2^4) = f(2^3) + 1 .
  • Finalement, pour ajouter a_0 = 2 , nous doublons deux fois pour obtenir 2^4 = 16 et ajoutons 2.

Ainsi, nous pouvons reconstruire l’antécédent de \frac{14}{5} en utilisant les coefficients de la fraction continue.

  1. Généralisation Pour tout rationnel positif \frac{p}{q} , nous pouvons appliquer ce processus de décomposition en fraction continue pour trouver l’antécédent. Le procédé est systématique et fonctionne pour tous les rationnels positifs.

Implémentation en Python

Pour automatiser ce processus, nous pouvons utiliser un algorithme en Python qui décompose un rationnel en une fraction continue et calcule l’antécédent.

Cet algorithme nous permet de décomposer n’importe quel rationnel en une fraction continue et de trouver l’antécédent via la fonction f . Cela confirme que la fonction f est bien surjective.

En résumé

Les fractions continues offrent une méthode élégante et systématique pour démontrer la surjectivité de f . Elles nous permettent de comprendre comment chaque rationnel peut être atteint à partir d’un entier naturel. En utilisant ce raisonnement, nous avons non seulement confirmé notre résultat précédent, mais aussi acquis une nouvelle perspective sur la beauté des mathématiques et des fractions continues.

Chapitre 8 : Python et les Mathématiques – Un Duo de Choc

Dans ce chapitre, nous allons explorer comment la programmation peut nous aider à vérifier nos résultats et à automatiser certaines tâches mathématiques complexes. Nous allons utiliser Python pour implémenter nos algorithmes de fraction continue et pour valider les résultats obtenus avec notre fonction f.

Décomposition en Fraction Continue

Tout d’abord, nous devons écrire un script Python qui décompose un rationnel en une fraction continue. Voici un algorithme simple pour accomplir cela :

Cet algorithme prend deux entiers p et q et les décompose en une fraction continue représentée par une liste de coefficients.

Calcul de l’Antécédent

Ensuite, nous devons écrire un algorithme pour calculer l’antécédent d’une fraction continue en utilisant la fonction f. Voici comment procéder :

Cet algorithme utilise les coefficients de la fraction continue pour calculer l’antécédent en appliquant les transformations définies par f.

Validation des Résultats

Pour vérifier que notre implémentation fonctionne correctement, nous devons écrire une fonction récursive qui calcule f(n) en Python :

Cette fonction calcule f(n) en suivant les règles de définition que nous avons établies précédemment.

À retenir

Avec ces scripts Python, nous pouvons décomposer n’importe quel rationnel en une fraction continue, calculer son antécédent et vérifier les résultats de manière automatique. Cela nous permet de gagner du temps et de réduire les erreurs manuelles, tout en explorant de manière plus approfondie les propriétés de la fonction f.

Les mathématiques et la programmation forment un duo puissant, capable de résoudre des problèmes complexes de manière efficace et élégante. En utilisant Python, nous avons pu valider nos résultats et approfondir notre compréhension des fractions continues et des fonctions récursives.

Chapitre 9 : Épilogue – Une Plongée dans l’Arbre de Stern-Brocot

Pour conclure notre exploration mathématique, examinons l’arbre de Stern-Brocot, une construction fascinante qui nous offre une visualisation claire de la fonction f et de sa capacité à atteindre tous les rationnels positifs.

L’Arbre de Stern-Brocot

L’arbre de Stern-Brocot est une structure binaire qui énumère tous les rationnels positifs de manière systématique et sans répétition. Chaque nœud de l’arbre représente un nombre rationnel, et les enfants de chaque nœud sont générés par une règle simple basée sur les fractions continues.

Construction de l’Arbre
  1. Racines de l’Arbre :
    • L’arbre commence avec les fractions \frac{0}{1} et \frac{1}{0} (où \frac{1}{0} représente l’infini).
  2. Règle de Génération :
    • Pour deux fractions \frac{a}{b} et \frac{c}{d}, leur médiant est défini comme \frac{a+c}{b+d}.
    • Les enfants de chaque nœud sont générés en prenant la fraction médiant entre le nœud et ses parents.
Visualisation

Considérons les premiers niveaux de l’arbre de Stern-Brocot :

  • Niveau 0 : \frac{1}{1}
  • Niveau 1 : \frac{1}{2}, \frac{2}{1}
  • Niveau 2 : \frac{1}{3}, \frac{3}{2}, \frac{3}{1}

Chaque niveau ajoute de nouvelles fractions qui se situent entre celles des niveaux précédents, suivant la règle de génération des médiants.

Relation avec la Fonction f

L’arbre de Stern-Brocot nous permet de visualiser comment la fonction f peut atteindre chaque rationnel positif. Chaque chemin dans l’arbre correspond à une série de transformations appliquées par f, reliant ainsi les entiers naturels aux rationnels positifs.

Conclusion

Nous avons démontré que la fonction f est injective et surjective, en explorant des méthodes variées, y compris les fractions continues et les algorithmes en Python. L’arbre de Stern-Brocot offre une perspective visuelle complémentaire, illustrant la manière dont chaque rationnel positif peut être atteint systématiquement.

Cette aventure mathématique nous a permis de plonger dans les profondeurs des ensembles infinis, de découvrir des paradoxes fascinants, et de voir comment les mathématiques peuvent être à la fois rigoureuses et élégantes. Merci de m’avoir accompagné dans ce voyage au pays des rationnels.

Prochaines étapes

Pour ceux qui souhaitent aller encore plus loin, je vous encourage à explorer d’autres constructions mathématiques et à expérimenter avec des algorithmes Python. Que ce soit pour démontrer des théorèmes, explorer des structures complexes ou simplement satisfaire votre curiosité mathématique, les outils que nous avons découverts ici sont à votre disposition.

À bientôt pour de nouvelles aventures mathématiques !

Check Also

Une découverte époustouflante : des molécules de carbone complexes repérées au-delà de notre système solaire

Introduction Imaginez un instant que nous observions une étoile lointaine, à des centaines d’années-lumière de …

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

© EYELO 2024, tout droit réservé