Jupyter notebook Lecons/Lecon7.ipynb
Bijections, ensembles dénombrables
Rappels
C'est quoi une bijection ?
Une fonction, par définition, fait correspondre un unique élément de l'ensemble d'arrivée à tout élément de l'ensemble de départ.
Une fonction est injective si et seulement si tout élément de son image est l'image par de précisement un élément de .
Exemple : A = {'a','b','c'} B = {1, 5} est définie par
Est-ce que est injective dans cet exemple?
NON, parce que a deux antécédents, c'est à dire qu'il existe deux éléments de dont l'image par est . Plus précisement :
'a''b'
alors que 'a' 'b'.
Définition équivalente de fonction injective
est injective si, et seulement si,
Déf. Une fonction est surjective si, et seulement si, tout élément de son ensemble d'arrivée a au moins un antécédent.
Une fonction est bijective si et seulement si elle est injective et surjective.
C'est quoi un ensemble dénombrable?
Définition sans beaucoup de symboles
Un ensemble est dénombrable s'il existe une bijection entre l'ensemble des nombres naturels et l'ensemble en question.
définition avec un peu plus de symboles
Un ensemble est dénombrable s'il existe une fonction bijective .
définition avec beaucoup de symboles
dénombrable bijective.
La composition de fonctions, la fonction identité et les fonctions inversibles.
Pour mieux appréhender le concept d'ensemble dénombrable, nous avons besoin de connaître mieux les fonctions bijectives. Plus concrètement:
Une fonction est bijective si et seulement elle est inversible, c'est à dire s'il existe une fonction telle composée avec et composée avec donnent une fonction identité.
Là, il y a quelques mots que nous n'avons pas encore définis. Les définitions sont données à continuation.
Composition de fonctions
Etant données deux fonctions et , où B⊆C, la composition est la fonction de dans définie par pour tout .
Dans Sage, on peut calculer la composition de deux fonctions et définies par des expressions symboliques et en substituant tout simplement à la place de .
Par exemple, si est définie par
et est définie par
alors est définie par , ce qu'on peut calculer avec la commande
Essayez par vous-mêmes!
Quelle est la formule pour dans cet exemple?
Donnez un exemple de plus de composition avec des expressions symboliques.
La fonction identité
Pour tout ensemble , la fonction identité sur est la fonction qui à tout fait correspondre lui-même.
La fonction identité sur est habituellement notée par
Propriété Soit alors .
Remarque: Comment montrer que deux fonctions sont égales? est la même fonction que si, et seulement si :
et
Preuve du fait que l'identité agit comme élément neutre pour la composition de fonctions (propriété énoncée ci-dessus)
Soit quelconque.
par définition de la composition.
Or, par définition de la fonction identité.
Il s'en suit que .
On conclut que
La preuve de est similaire.
∎
La restriction d'une fonction
L'idée de la restriction des fonctions est que la restriction d'une fonction est une fonction définie sur un sous-ensemble du domaine de qui coïncide avec sur ce sosus-ensemble.
Les concepts de fonction identité et de composition de fonction nous permettent de préciser rapidement cette idée.
Soit et non-vide, alors la restriction de à , notée , est la fonction .
**Remarque : ** Etant données deux fonctions et , telles que , alors .
La composition de fonctions dans le cas général
Comment composer des fonctions qui ne rentrent pas dans le cadre ci-dessus, c'est à dire qui n'ont pas l'ensemble d'arrivée de l'une qui est égale à l'ensemble de départ (domaine) de l'autre?
Considérons deux fonctions et , sans aucune rélation à priori entre et . Par l'axiome de la réunion, il existe un ensemble qui contient et . Par l'axiome de compréhension, on peut considérer le sous-ensemble de tous les éléments de qui appartiennent aussi bien à qu'à , c'est à dire l'intersection de et .
Maintenant, si et sont disjoints, c'est-à-dire , on va convenir n'est pas définie.
Par contre, si alors on va convenir que où .
Les fonctions injectives et l'inverse à gauche
Une inverse à gauche d'une fonction est une fonction telle que pour tout . Autrement dit, .
Proposition : Soit et soit . La fonction est injective si et seulement si elle possède une inverse à gauche.
**Preuve : **
()
Comme , possède au moins un élément .
Supposons que est injective. Considérons la fonction définie par
si
si et est l'unique élément de tel que .
Dans le deuxième cas, est unique car est injective. On a, par la définition même de que pour tout . Donc et est une inverse à gauche de .
() Supposons que est une inverse à gauche de . Considérons , tels que . Alors : On peut donc conclure que est injective. ∎
Les fonctions surjectives et l'inverse à droite
Une inverse à droite d'une fonction est une fonction telle que pour tout . Autrement dit, .
Proposition : Soit et soit . La fonction est surjective si et seulement si elle possède une inverse à droite.
**Preuve : **
() Supposons que est surjective. Par définition, on a alors que
Dit autrement :
Par l'axiome du choix, nous pouvons trouver une fonction tel que pour tout on a que .
Par la définition même de on aura donc que :
D'où est une inverse à droite de .
() Supposons que est une inverse à droite de . Considérons , et , alors On peut donc conclure que est surjective. ∎
Les fonctions bijectives et l'inverse
L'inverse d'une fonction est une fonction telle que et . Autrement dit, est une inverse à droite et une inverse à gauche.
**Proposition : ** Soit A≠∅ et une fonction. Si l'inverse de existe alors elle est unique.
Preuve : Supposons que et sont inverses de . Soit quelconque. Alors : On peut donc conclure que . Il s'en suit qe l'inverse, quand elle existe, est unique.
On dit qu'une fonction est inversible si son inverse existe.
Proposition : Soit et soit . La fonction est bijective si et seulement si elle est inversible.
**Preuve : ** Suit facilement des propositions précédentes sur les inverses à droite ou à gauche. ∎
Propriétés élémentaires des ensembles dénombrables.
Utilisons maintenant tout cela pour les ensembles dénombrables.
**Proposition : ** Soit un ensemble infini. Les affirmations suivantes sont équivalentes
est dénombrable
Il existe une fonction surjective .
Il existe une fonction injective .
Preuve
() dénombrable bijective bijective surjective
() surjective ⇒ possède inverse à droite est l'inverse à droite de ⇔ est l'inverse à gauche de possède inverse à gauche ⇒ est injective
() Soit injective. On définit par récurrence une fonction .
est l'unique tel que est le plus petit nombre naturel dans .
Pour tout , est l'unique tel que est le plus petit nombre naturel dans ∖.
À chaque étape, est unique car est injective. On peut itérer ce processus à l'infini car a plus qu'un nombre fini d'éléments.
Par construction, la fonction est une bijection. (La preuve complète se fait par récurrence). ∎
Corollaire :
Tout ensemble infini contenu dans un ensemble dénombrable est dénombrable.
Tout ensemble infini qui contient un ensemble non-dénombrable est non-dénombrable.
**Preuve de 1. ** (2. découle de 1. ) Soient et des ensembles infinis tels que . Comme est infini, il existe une fonction injective . Comme est inclus dans , on peut restreindre à pour obtenir la fonction qui sera encore une fonction injective. Par conséquent est dénombrable aussi.∎
Exemples :
est dénombrable, il suffit de prendre la fonction identité.
Tout sous-ensemble de est dénombrable :
L'ensemble des nombres pairs (positifs)
L'ensemble des nombres premiers (positifs)
L'ensemble de tous les carrés de nombres entiers.
ℤ est dénombrable, il suffit de considérer la fonction définie par .
: denote le plus petit nombre entier qui est plus grand que .
Dans Sage cette fonction est calculée avec la méthode ceil
.
est dénombrable. Voir le site :
http://jean-paul.davalan.pagesperso-orange.fr/divers/bij/index.html
pour une description explicite du polynôme de Cantor qui réalise une bijection entre et .
Par le théorème de Fueter et Polya cité dans le site web signalé, défini une bijection entre ℕ×ℕ et ℕ.
Trouver avec une boucle les nombres naturels et tels que
Justification de la borne
Sage n'arrive pas à le montrer automatiquement "out-of-the-box"
On peut remarquer que
On peut en déduire que si , alors donc .
Il s'en suit que pour chercher tels que on peut s'arrêter à , ce n'est pas la peine de chercher plus loin.
En particulier, si on s'arrête à , c'est bon aussi, puisque .
En généralisant ce raisonnement, réutilisez la boucle while
de toute à l'heure pour coder la fonction informatique qui calcule la fonction inverse de .
C'est à dire que pour chaque , votre fonction doit calculer les uniques tels que
Solution :
Pour être sûrs que ça marche bien, écrivons aussi un test de vérification
Appliquons ce test à quelques nombres