2.6. Injections, bijections
Composition, restriction
La composée de 2 fonctions f,g telles que Im f
⊂ Dom g est définie par
g⚬f = ((Dom f) ∋ x ↦
g(f(x)))
(f : E →
F ∧ g : F → G) ⇒ g⚬f
: E → G
(Cette notation sera abusivement conservée si g est un foncteur, auquel cas
il s'agit d'un schéma de définitions).
De même avec plus de 2 fonctions: ajoutant une troisième
h:G →H aux conditions ci-dessus, on définit
h⚬g⚬f
= (h⚬g)⚬f = h⚬(g⚬f) = (E
∋ x ↦ h(g(f(x))))
La restriction d'une fonction f à un ensemble
A ⊂ Dom f est
f|A =
(A ∋ x ↦ f(x)) = f⚬IdA.
Gr(f|A) = (Gr f)|A
f[A] = Im(f|A)
∀Fnc f,g, Gr g ⊂ Gr f
⇔ (Dom g ⊂ Dom f ∧ g = f|Dom g)
Quand g est une restriction de f, on dit aussi que f est une extension de
g.
Injections, bijections, inverse
Une fonction f : E → F est dite
injective (ou : une injection ) si tGr f
est un graphe fonctionnel:
| Inj f ⇔ |
(∀x≠x′∈Dom f, f(x) ≠ f(x′)) |
| ⇔ |
(∀x,x′∈Dom f, f(x) = f(x′)
⇒ x=x′) |
| (f : E ↪ F) ⇔ |
(f : E → F ∧ Inj f) |
| Im f ⊂ F ⇒ |
(Inj f ⇔ ∀y∈F, !:f•(y)) |
L'inverse de toute injection f est la fonction
f -1 de graphe tGr f:
f -1 = ℩f•
= (Im f ∋ y ↦ ℩f•(y))
Gr(f -1) = tGr f
(f -1)-1 = f.
Une fonction f : E → F est dite bijective
(ou une bijection) de E sur F, si elle est injective et surjective:
| f : E ↔ F ⇔ |
(f : E → F ∧ ∀y∈F, ∃!: f•(y))
|
| ⇔ |
(f : E ↪ F ∧ Im f = F) |
| ⇔ |
(f : E ↠ F ∧ Inj f) |
| ⇒ |
f -1: F ↔ E. |
En particulier IdE : E ↔ E.
Diverses propriétés
Proposition. Soit f : E → F
et g : F → G. Alors-
(Inj f ∧ Inj g) ⇒ Inj(g⚬f)
- Inj(g⚬f) ⇒ Inj f
- Im(g⚬f) = g[Im f] ⊂ Im g.
Preuves:
- ∀x,y∈E,
g(f(x)) = g(f(y)) ⇒
f(x) = f(y) ⇒ x = y.
- ∀x,y ∈ E, f(x) = f(y)
⇒ g(f(x)) = (g(f(y)) ⇒
x = y.
- ∀z∈G, z ∈ Im(g⚬f) ⇔
(∃x∈E, g(f(x))=z) ⇔
(∃y∈ Imf, g(y)=z) ⇔ z
∈ g[Imf]. ∎
De 3. on déduit évidemment
Im(g⚬f) = G ⇒ Im g = G
Im f = F ⇒ Im(g⚬f) = Im g
(f:E ↠ F) ⇒ (g:F
↠ G ⇔ g⚬f:E ↠ G)
Soit f : E → F, et une fonction g avec Dom g = F.
Alors, facilement
| g⚬f
= IdE |
⇔ (∀x∈E, ∀y∈F,
f(x) = y ⇒ g(y) = x)
|
|
⇔ Gr f ⊂ tGr g ⇔ (∀y∈F, f•(y)⊂{g(y)}) |
|
⇔ (∀x∈E, f(x)∈g•(x))
⇔ (Inj f ∧ g|Im f = f -1) |
|
⇒ (Im f = F ⇔ g = f -1 ⇔ (Inj g ∧ Im g ⊂ E)) |
Preuve de l'étape non-évidente : (g⚬f
= IdE ∧ Inj g ∧ Im g ⊂ E) ⇒ (∀y∈F, g(f(g(y))) =
g(y) ∴ y = f(g(y)) ∈ Im f)
Proposition. (f : E → F ∧ g : F
→ E ∧ g⚬f = IdE) ⇒ (Im f = F ⇔
Inj g ⇔ f⚬g = IdF ⇔ g = f -1).
Preuve : (Inj g
∧ g⚬f⚬g = g⚬IdF)
⇒ f⚬g = IdF.
∎
Proposition. 1) Si f,g sont injectives et Im f =
Dom g, alors (g⚬f)-1 = f -1⚬g-1.
2) Si f,h : E→F et g : F→E alors
(g⚬f = IdE ∧ h⚬g = IdF)
⇔ ((g : F ↔ E) ∧ f = h = g−1).
Preuves:
1) ∀x∈Dom f, ∀y∈ Im g, (g⚬f)(x) = y
⇔ f(x) = g-1(y) ⇔ x =
(f -1⚬g-1)(y).
Autre méthode: (g⚬f)-1= (g⚬f)-1⚬g⚬g-1=
(g⚬f)-1⚬g⚬f⚬f -1⚬g-1
= f -1⚬g-1.
2) On déduit f = h de f = h⚬g⚬f = h,
ou de Gr f ⊂ tGr g ⊂ Gr h. Le reste est évident. ∎
Fonctions canoniques
Pour tous objets x,y on dira que x détermine y s'il y a un
foncteur invariant T (connu mais gardé implicite) tel que T(x) =
y. Alors le rôle de y comme variable libre peut être joué par
le terme T(x), donc en utilisant x.
De même, une fonction f : E → F sera dite canonique
si elle se définit par E ∋ x ↦ T(x) où T est un
foncteur invariant.
Exemples d'injections canoniques importantes
- E ⊂ F ⇒ IdE :
E ↪ F
- (x ↦ {x}) : E ↪ ℘(E)
- Gr : FE ↪ ℘(E×F).
Une bijection f sera dite bicanonique si f et f−1
sont canoniques.
Quand une bijection f : E ↔ F
est canonique (resp. bicanonique), on écrira f : E ⥬ F
(resp. f : E ⇌ F); ou, avec son foncteur de définition φ
comme φ : E ⥬ F qui signifie que (E ∋ x ↦ φ(x)) est
injective d'image F. On écrira E ⥬ F (resp. E ⇌ F)
pour signifier l'existence d'une bijection
canonique (resp. bicanonique), qui reste implicite. Cela aura souvent une
allure d'identité remarquable sur les nombres car l'existence
d'une bijection entre ensembles finis implique l'égalité de leurs
nombres d'éléments.
Les bijections canoniques peuvent n'être pas bicanoniques surtout
lorsque leur foncteur de définition n'est pas injectif:
V2E ⥬ ℘(E)
E ≠ ∅ ⇒ {x}E ⥬ {x}
E×{x} ⥬ E
E×F ⇌ F×E
E×{x} ⇌ {x}×E
⇌ E{x}
E×{0} ⇌ E.
Cett meta-relation entre ensembles est préservée par constructions: si
E ⥬ E′ et F ⥬ F′ alors ℘(E) ⥬ ℘(E'),
E×F ⥬ E′×F′ et FE
⥬ F′E′ (en utilisant l'image directe du
graphe), et de même pour ⇌.
Ainsi la transposition (E×F ⇌ F×E) s'étend aux
graphes et aux operations:
℘(E×F) ⇌ ℘(F×E)
GE×F ⇌ GF×E
∀f∈GE×F, tf
= (F×E∋(x,y) ↦ f(y,x)) ∈
GF×E.
Sommes de fonctions
Le symbole liant ∐ de somme d'ensembles
définit des bijections canoniques (dont les inverses, définies par R ↦
R⃗I, dépendent de I):
(℘(E))I ⥬ ℘(I×E)
∏i∈I ℘(Ai)
⥬ ℘(∐i∈I Ai)
Toute somme d'ensembles S = ∐i∈I Ai
a sa famille d'injections naturelles ji données par
le définisseur de couples curryfié :
∀i∈I, ji : Ai
↪ S.
La somme sur I des functions fi où ∀i∈I,
Ai = Dom fi se définit par
∐i∈I fi
= (S ∋ (i,x) ↦ fi(x))
g = ∐i∈I fi ⇔
(Dom g = S ∧ ∀i∈I, fi =
g⚬ji = g⃗(i))
C'est l'inverse de la curryfication des opérations binaires, qu'on désignera comme pour les
graphes: pour tous ensembles E, F et toute opération (fonction) B de
domaine E×F ≠ ∅ (d'où E et F peuvent être restaurés par
E = Dom Dom B et F = Im Dom B, tandis que si E×F = ∅
la notation peut être conservée abusivement en prenant E et F du contexte),
B⃗ = (E ∋ x ↦
(F ∋ y ↦ B(x,y)))
B⃖ = tB⃗ = (F ∋ y ↦
(E ∋ x ↦ B(x,y))
d'où les bijections canoniques (bicanoniques si I = Dom S, donc si E ≠ ∅ dans le
cas I×E)
∀SetF, ∏
i∈I
FAi ⥬ FS
∀SetE,F,
(FE)I ⥬ FI×E
(∀F : S → Set) ∏
i∈I
∏
x∈Ai
F(i,x) ⥬ ∏
c∈SFc
(E×F)×G ⇌ E×F×G
f ∈ (FE)I ⇒ ∐
i∈I
Gr fi ⊂ ℘(I×(E×F))
⇌ ℘((I×E)×F) ⊃ Gr ∐
i∈I
fi
Produit de fonctions ou recurryfication
Les deux formes curryfiées R⃗ et R⃖ des graphes
R ⊂ E×F s'échangent par une bijection ℘(F)E
↔ ℘(E)F définie avec paramètre F.
La bijection similaire entre les deux formes curryfiées des operations de domaine donné
I×E, se définit par un symbole liant ⊓ de produit
de fonctions, toutes de même domaine E, et indexées par I :
(∀i∈I, Dom fi =
E) ⇒ ⊓
i∈I
fi = (E ∋ x ↦
(fi(x))i∈I)
∀g, g = ⊓
i∈I
fi ⇔ (g : E →
∏
i∈I
Im fi ∧ ∀i∈I, fi
= πi⚬g)
(F : I → Set) ⇒ ⊓ : ∏
i∈I
FiE ⥬ (∏
i∈I
Fi)E
Set F ⇒ ⊓ : (FE)I ⥬
(FI)E
Ces bijections sont canoniques pour les families non vides (I
≠ ∅) comme elles seules déterminent E, et sont généralement bicanoniques car
leur inverse utilise I qui est définissable lorsque E ≠ ∅; néanmoins on gardera
abusivement la notation ⥬ pour le cas général tandis que E reste fixé par le contexte.
Un cas particulier est le produit binaire (I = V2):
∀Fncf,g, Dom f = Dom g = E ⇒ f⊓g =
(E ∋ x ↦ (f(x),g(x)))
IE×FE ⇌
(I×F)E
(∐
i∈I
Fi)E ⇌
∐
ϕ∈IE ∏
x∈E
Fϕ(x)
∀Fncf, Gr f = Im(IdDom f ⊓ f)