2.6. Injectivity and inversion

A function f : EF is injective (or : an injection ) if tGr f is a functional graph:

Inj f
(∀yF, !:f(y))
(∀x,x′∈E, f(x)=f(x′) ⇒ x=x′)
(∀x,x′∈E, xx′ ⇒ f(x) ≠ f(x′))

Then its inverse is defined by f-1f=(Imfy ↦ ϵf(y)) so that Gr(f-1)=tGr f.
A function f : E → F is said bijective (or a bijection) from E onto F, and we write f : EF, if it is injective and surjective: ∀yF, ∃!: f(y), in which case f-1: FE.
A permutation (or transformation) of a set E is a bijection f : EE.

Proposition. Let f:E → F and g:F → G.
1. (Inj f ∧ Inj g) ⇒ Inj(gf)
2. Inj(gf) ⇒ Inj f
3. Im(gf) = g[Im f] ⊂ Img.
4. Im(gf) = G ⇒ Img=G.
5. Im f = F ⇒ Im(gf) = Im g, so that ((f:EF) ∧ (g:FG)) ⇒ (gf:EG)

Proofs:
1. (Inj f ∧ Inj g)⇒∀x,yE, g(f(x))=g(f(y)) ⇒ f(x)=f(y) ⇒ x=y.
2. ∀x,yE, f(x)=f(y) ⇒ g(f(x)) = (g(f(y)) ⇒ x=y.
3. ∀zG, z ∈ Im(gf) ⇔ (∃xE, g(f(x))=z) ⇔ (∃y ∈ Imf, g(y)=z) ⇔ zg[Imf].
3.⇒ 4. and 3.⇒5. are obvious.∎
Proposition. For any sets E,F,G and any fFE,
Im f=F ⇒ Inj(GFggf) ⇒ (Im f = F ∨ !:G)
(Inj fG ≠ ∅) ⇒{gf| gGF}=GE ⇒(Inj f ∨ !: G)
(EFG ≠ ∅) ⇒{g|E|gGF}=GE
(Inj fE ≠ ∅) ⇒ ∃gEF, gf=IdE
Proofs :
Imf=F⇒∀g,hGF, ((∀xE, g(f(x)) = h(f(x))) ⇔ (∀yF, g(y)=h(y) ⇔ g=h)).
z,z′∈G, (yz)০f = (y ↦ (y ∈ Imf ? z : z′))০f ∴ (Inj(ggf) ⇒ (z=z′∨ Imf=F))
zG,∀hGE, Injf ⇒ (Fy ↦ (y ∈ Imf? hf-1(y):z))০f=h.
z,z′ ∈ G,∀xE, if gGF is such that ∀yE,g(f(y)) = (y=x ? z : z′), then
yE, f(y)=f(x) ⇒ g(f(y)) = g(f(x)) = z ⇒ (y=xz=z′).
The last formulas are particular cases of the second one.∎

Let f:E →  F and f*F: ℘(F) →  ℘(E) defined by f*. Then (by G=V2 and ∀BImf, f[f*(B)]=B),

Inj f ⇔ Im f*F = ℘(E)
Im f = F⇔Inj f*F
Im f*={f[A]|AE}=℘(Im f)

Proposition. Let F = Dom g. Then Inj g ⇒ Inj(FEfgf) ⇒ (Inj gE=∅).

Proofs: ∀f,f′ ∈ FE, (Inj g ∧ ∀xE, g(f(x)) = g(f′(x))) ⇒ (∀xE, f(x)=f'(x)).
Then from the middle formula, ∀y,zF,
g(y) = g(z) ⇒ g০(Exy) = g০(Exz) ⇒ (∀xE, y=z) ⇒ (y=zE=∅).∎

Proposition. Let f: E → F and Dom g=F. Then
gf = IdE ⇔ (∀xE, ∀yF, f(x)=yg(y)=x)

⇔ (Gr ftGr g) ⇔ (∀yF, f(y)⊂{g(y)})

⇔ (∀xE, f(x)∈g(x)) ⇔ (Inj fg|Imf = f-1)

E ⊂ Im g
(g:FEgf= IdE) ⇒ (Im f = F ⇔ Inj g ⇔ fg = IdF ⇔ g=f -1).
Proof of the last formula: (Inj ggfg = gIdF) ⇒ fg=IdF. ∎

Proposition. 1) If f,g are injective and Im f = Dom g, then (gf)-1= f -1g-1.
2) If
f,h : E → F and g : F →E then (gf = IdEhg = IdF).

Proofs:
1) ∀x∈ Dom f, ∀y ∈ Im g, (gf)(x)=yf(x)=g-1(y) ⇔ x= (f -1g-1)(y).
Other method: (gf)-1= (gf)-1gg-1= (gf)-1gff-1g-1 = f-1g-1.
2) We deduce f=h from f = hgf = h, or from Gr ftGr g ⊂ Gr h. The rest is obvious.∎

Set theory and Foundations of Mathematics
1. First foundations of mathematics
2. Set theory (continued)
2.1. Tuples, families
2.2. Boolean operators on families of sets
2.3. Products, graphs and composition
2.4. Uniqueness quantifiers, functional graphs
2.5. The powerset axiom
2.6. Injectivity and inversion
2.7. Properties of binary relations on a set ; ordered sets
2.8. Canonical bijections
2.9. Equivalence relations and partitions
2.10. Axiom of choice
2.11. Notion of Galois connection