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.
Un ensemble est dénombrable s'il existe une bijection entre l'ensemble des nombres naturels et l'ensemble en question.
Un ensemble $A$ est dénombrable s'il existe une fonction bijective $ƒ : ℕ → A$.
$A$ dénombrable $⇔ ∃ ƒ : ℕ → A$ bijective.
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.
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))
Quelle est la formule pour $h∘g$ dans cet exemple?
h(g(x))
Donnez un exemple de plus de composition avec des expressions symboliques.
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 :
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$
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∘ƒ$.
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\}$.
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
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.
∎
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.
∎
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. ∎
Utilisons maintenant tout cela pour les ensembles dénombrables.
Proposition : Soit $A$ un ensemble infini. Les affirmations suivantes sont équivalentes
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$.
À 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 :
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.∎
$\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)
$ℕ×ℕ$ 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)
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)
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)
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