Lecon7.ipynb

Kernel: SageMath 7.4

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 $ƒ : A → B$ est injective si et seulement si tout élément de son image $ƒ(A)$ est l'image par $ƒ$ de précisement un élément de $A$.

Exemple : A = {'a','b','c'} B = {1, 5} $ƒ : A → B$ est définie par

f = {'a' : 1, 'b' : 5, 'c' : 1 }

Est-ce que $ƒ : A → B$ est injective dans cet exemple?

NON, parce que $1\in B$ a deux antécédents, c'est à dire qu'il existe deux éléments de $A$ dont l'image par $ƒ$ est $1$. Plus précisement :

$ƒ($'a'$) = ƒ($'b'$) = 1$

alors que 'a' $\neq$ 'b'.

Définition équivalente de fonction injective

$ƒ : A → B$ est injective si, et seulement si,

$$\forall x,y\in B: ƒ(x)=ƒ(y) \Rightarrow x=y$$

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 $ƒ : A → B$ 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 $A$ est dénombrable s'il existe une fonction bijective $ƒ : ℕ → A$.

• définition avec beaucoup de symboles

$A$ dénombrable $⇔ ∃ ƒ : ℕ → A$ 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 $g$ telle $f$ composée avec $g$ et $g$ 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 $ƒ:A → B$ et $g:C → D$, où B⊆C, la composition $g∘ƒ$ est la fonction de $A$ dans $D$ définie par $g∘ƒ(a)=g(ƒ(a))$ pour tout $a∈A$.

Dans Sage, on peut calculer la composition $g∘ƒ$ de deux fonctions $ƒ$ et $g$ définies par des expressions symboliques $g(y)$ et $ƒ(x)$ en substituant tout simplement $f(x)$ à la place de $y$.

Par exemple, si $g$ est définie par $g(x)=x²+23x$

g(x) = x^2+23*x

et $h$ est définie par $h(x) = √x$

h(x) = sqrt(x)

alors $ƒ=g∘h$ est définie par $ƒ(x) = x+23√x$, ce qu'on peut calculer avec la commande

g(h(x))

Essayez par vous-mêmes!

g(x) = x^2+23*x
h(x) = sqrt(x)
g(h(x))

x + 23*sqrt(x)

Quelle est la formule pour $h∘g$ dans cet exemple?

h(g(x))

sqrt(x^2 + 23*x)

Donnez un exemple de plus de composition avec des expressions symboliques.

La fonction identité

Pour tout ensemble $A$, la fonction identité sur $A$ est la fonction qui à tout $a∈A$ fait correspondre $a$ lui-même.

La fonction identité sur $A$ est habituellement notée par $id_A$

Propriété Soit $g:A→B$ alors $g∘id_A=g=id_B∘g$.

Remarque: Comment montrer que deux fonctions sont égales? $f:A\to B$ est la même fonction que $g:C\to D$ si, et seulement si :

• $A = C$ et $B = D$

• $\forall x\in A : f(x) = g(x)$

Preuve du fait que l'identité agit comme élément neutre pour la composition de fonctions (propriété $g∘id_A=g=id_B∘g$ énoncée ci-dessus)

Soit $a\in A$ quelconque.

$(g∘id_A)(a) = g ( id_A (a) )$ par définition de la composition.

Or, $id_A(a) = a$ par définition de la fonction identité.

Il s'en suit que $(g∘id_A)(a) = g(a)$.

On conclut que $g∘id_A=g$

La preuve de $id_B∘g = g$ 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 $ƒ:A→B$ et $C⊆A$ non-vide, alors la restriction de $ƒ$ à $C$, notée $ƒ|_C$, est la fonction $ƒ∘id_C$.

**Remarque : ** Etant données deux fonctions $ƒ:A → B$ et $g:C → D$, telles que $B ⊆ C$, alors $g∘ƒ=g|_B∘ƒ$.

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 $ƒ:A → B$ et $g:C → D$, sans aucune rélation à priori entre $B$ et $C$. Par l'axiome de la réunion, il existe un ensemble $E$ qui contient $B$ et $C$. Par l'axiome de compréhension, on peut considérer le sous-ensemble de tous les éléments de $E$ qui appartiennent aussi bien à $B$ qu'à $C$, c'est à dire l'intersection de $B$ et $C$.

Maintenant, si $B$ et $C$ sont disjoints, c'est-à-dire $B∩C=∅$, on va convenir $g∘ƒ$ n'est pas définie.

Par contre, si $B∩C≠∅$ alors on va convenir que $g∘ƒ = g|_{B∩C}∘ƒ|_H: H → D$ où $H = \{x∈A|ƒ(x)\in B∩C\}$.

Les fonctions injectives et l'inverse à gauche

Une inverse à gauche d'une fonction $ƒ:A→B$ est une fonction $g:B→A$ telle que $(g∘ƒ)(x) = x$ pour tout $x∈A$. Autrement dit, $g∘ƒ=id_A$.

Proposition : Soit $A≠∅$ et soit $ƒ : A → B$. La fonction $ƒ$ est injective si et seulement si elle possède une inverse à gauche.

**Preuve : **

($⇒$)

Comme $A\neq \emptyset$, $A$ possède au moins un élément $a₀$.

Supposons que $ƒ$ est injective. Considérons la fonction $g:B → A$ définie par

1. $g(b) = a₀$ si $b∉ƒ(A)$

2. $g(b) =a$ si $b∈ƒ(A)$ et $a$ est l'unique élément de $A$ tel que $ƒ(a) = b$.

Dans le deuxième cas, $a$ est unique car $ƒ$ est injective. On a, par la définition même de $g$ que $g(ƒ(a))=a$ pour tout $a∈A$. Donc $g∘ƒ=id_A$ et $g$ est une inverse à gauche de $f$.

($⇐$) Supposons que $g : B → A$ est une inverse à gauche de $ƒ$. Considérons $x∈A$, $y∈A$ tels que $ƒ(x)=ƒ(y)$. Alors : $$x=id_A(x)=(g∘ƒ)(x)=g(ƒ(x))=g(ƒ(y))=(g∘ƒ)(y)=id_A(y)=y.$$ On peut donc conclure que $f$ est injective. ∎

Les fonctions surjectives et l'inverse à droite

Une inverse à droite d'une fonction $ƒ:A→B$ est une fonction $g:B→A$ telle que $(ƒ∘g)(x) = x$ pour tout $x∈B$. Autrement dit, $ƒ∘g=id_B$.

Proposition : Soit $A≠∅$ et soit $ƒ : A → B$. 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 $$∀b∈B:∃a∈A|ƒ(a)=b$$

Dit autrement : $$∀b∈B:\{a∈A|ƒ(a)=b\}≠∅$$

Par l'axiome du choix, nous pouvons trouver une fonction $g:B → A$ tel que pour tout $b∈B$ on a que $g(b)∈\{a∈A|ƒ(a)=b\}$.

Par la définition même de $b$ on aura donc que : $$∀b∈B:ƒ(g(b))=b$$

D'où $g$ est une inverse à droite de $ƒ$.

($⇐$) Supposons que $g : B → A$ est une inverse à droite de $ƒ$. Considérons $y∈B$, et $x=g(y)∈A$, alors $$ƒ(x)=ƒ(g(y))=(ƒ∘g)(y)=id_A(y)=y$$ On peut donc conclure que $f$ est surjective. ∎

Les fonctions bijectives et l'inverse

L'inverse d'une fonction $ƒ:A→B$ est une fonction $g:B→A$ telle que $g∘ƒ=id_A$ et $ƒ∘g=id_B$. Autrement dit, $g$ est une inverse à droite et une inverse à gauche.

**Proposition : ** Soit A≠∅ et $ƒ : A → B$ une fonction. Si l'inverse de $ƒ$ existe alors elle est unique.

Preuve : Supposons que $g : B → A$ et $h : B → A$ sont inverses de $ƒ$. Soit $b∈B$ quelconque. Alors : $$g(b) = g(id_B(b))=g((ƒ∘h)(b))=g(ƒ(h(b)))=(g∘ƒ)(h(b))=id_A(h(b))=h(b)$$ On peut donc conclure que $g=h$. 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 $A≠∅$ et soit $ƒ : A → B$. 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 $A$ un ensemble infini. Les affirmations suivantes sont équivalentes

1. $A$ est dénombrable

2. Il existe une fonction surjective $ƒ : ℕ → A$.

3. Il existe une fonction injective $ƒ : A → ℕ$.

Preuve

($1⇒2$) $A$ dénombrable$⇒ ∃ ƒ : ℕ → A$ bijective $ƒ$ bijective$⇒ ƒ$ surjective

($2⇒3$) $ƒ$ surjective ⇒ $ƒ$ possède inverse à droite $g : A → ℕ$ $g$ est l'inverse à droite de $ƒ$ ⇔ $ƒ$ est l'inverse à gauche de $g$ $g : A → ℕ$ possède inverse à gauche ⇒ $g$ est injective

($3⇒1$) Soit $g : A → ℕ$ injective. On définit par récurrence une fonction $ƒ : ℕ → A$.

1. $ƒ(0)$ est l'unique $a∈A$ tel que $g(a)$ est le plus petit nombre naturel dans $g(A)$.

2. Pour tout $n≥0$, $ƒ(n+1)$ est l'unique $a∈A$ tel que $g(a)$ est le plus petit nombre naturel dans $g(A)$∖$\{ƒ(k)|k≤n\}$.

À chaque étape, $a$ est unique car $g$ est injective. On peut itérer ce processus à l'infini car $A$ 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 :

1. Tout ensemble infini contenu dans un ensemble dénombrable est dénombrable.

2. Tout ensemble infini qui contient un ensemble non-dénombrable est non-dénombrable.

**Preuve de 1. ** (2. découle de 1. ) Soient $A$ et $B$ des ensembles infinis tels que $A⊆B$. Comme $B$ est infini, il existe une fonction injective $ƒ : B → ℕ$. Comme $A$ est inclus dans $B$, on peut restreindre $ƒ$ à $A$ pour obtenir la fonction $ƒ|_A=ƒ∘id_A$ qui sera encore une fonction injective. Par conséquent $A$ est dénombrable aussi.∎

Exemples :

• $ℕ$ est dénombrable, il suffit de prendre la fonction identité.

• Tout sous-ensemble de $\mathbb N$ est dénombrable :

  • L'ensemble des nombres pairs (positifs) $\{0,2,4,\dots\}$

  • L'ensemble des nombres premiers (positifs) $\{1,2,3,5,7,11,\dots\}$

  • L'ensemble de tous les carrés de nombres entiers. $\{0,1,4,9,\dots\}$

• ℤ est dénombrable, il suffit de considérer la fonction $ƒ : ℕ → ℤ$ définie par $ƒ(n)=(−1)ⁿ⌈n/2⌉$.

$\forall x\in\mathbb R$ : $⌈x⌉$ denote le plus petit nombre entier qui est plus grand que $x$.

Dans Sage cette fonction est calculée avec la méthode ceil.

f(x) = (-1)^x*ceil(x/2)

for i in range(10):
     print f(i)

0
-1
1
-2
2
-3
3
-4
4
-5

• $ℕ×ℕ$ 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 $ℕ$.

x,y = var('x','y')
f(x,y) = ((x+y)^2+3*x+y)/2

Par le théorème de Fueter et Polya cité dans le site web signalé, $f$ défini une bijection entre ℕ×ℕ et ℕ.

Trouver avec une boucle les nombres naturels $m$ et $n$ tels que $f(m,n) = 101$

m = 0
n = 0
while f(m,n)!= 101:
    if( m == 100):
        m = 0
        n = n + 1
    else:
        m = m + 1
(m,n)

(10, 3)

Justification de la borne $m=100$

Sage n'arrive pas à le montrer automatiquement "out-of-the-box"

assume(f(x,y)==101)
bool(x<=100)

False

On peut remarquer que

$$\forall m,n\in \mathbb N : f(m,n) = \frac12((m+n)^2+3m+n)\ge \frac32 m$$

assume(x>0)
assume(y>0)
bool(f(x,y)>=3*x/2)

True

On peut en déduire que si $f(m,n) = 101$, alors $101\ge \frac32 m$ donc $m \le \frac23 \cdot 101 <\frac23 \cdot 102 = 68$.

Il s'en suit que pour chercher $m,n$ tels que $f(m,n)=101$ on peut s'arrêter à $m=68$, ce n'est pas la peine de chercher plus loin.

En particulier, si on s'arrête à $m= 100$, c'est bon aussi, puisque $100>68$.

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 $f$.

C'est à dire que pour chaque $k\in\mathbb N$, votre fonction doit calculer les uniques $m,n\in\mathbb N$ tels que $f(m,n) = k$

Solution :

def inverse_de_f(k):
    m = 0
    n = 0
    while f(m,n)!=k:
        if (2*k >= 3*m):
            m = 0
            n = n + 1
        else:
            m = m + 1
    return (m,n)

Pour être sûrs que ça marche bien, écrivons aussi un test de vérification

def test_inverse_de_f(k):
    c = inverse_de_f(k)
    print 'l\'inverse de f en ',k,' est ',c,' car f',c,' = ',f(c[0],c[1])

Appliquons ce test à quelques nombres

test_inverse_de_f(105)

l'inverse de f en  105  est  (0, 14)  car f (0, 14)  =  105

test_inverse_de_f(215)