Ensembles dénombrables, suites¶

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.

$\cqfd$

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

$g(b) = a₀$ si $b∉ƒ(A)$
$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

$A$ est dénombrable
Il existe une fonction surjective $ƒ : ℕ → A$.
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$.

$ƒ(0)$ est l'unique $a∈A$ tel que $g(a)$ est le plus petit nombre naturel dans $g(A)$.
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 :

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

ℚ est dénombrable