## 2.8. Injections, bijections

### Composition, restriction

The composite of any 2 functions f,g such that Im f ⊂ Dom g is defined by

gf = ((Dom f) ∋ xg(f(x)))
(f : E → Fg : F → G) ⇒ gf : E → G

(This notation will be abusively kept if g is a functor, in which case this is a schema of definitions).
Similarly with more than 2 functions: adding a third one h : G →H to the above conditions, we define

hgf = (hg)⚬f = h⚬(gf) = (Exh(g(f(x))))

The restriction of a function f to a set A ⊂ Dom f is

f|A = (Axf(x)) = f⚬IdA.
Gr(f|A) = (Gr f)|A
f[A] = Im(f|A)
Fnc f,g, Gr g ⊂ Gr f ⇔ (Dom g ⊂ Dom fg = f|Dom g)

When g is a restriction of f, we also say that f is an extension of g.

### Injections, bijections, inverse

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

 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))

The inverse of any injection f, is the function f -1 with graph tGr f:

f -1 = ℩f = (Im fy ↦ ℩f(y))
Gr(f -1) = tGr f
(f -1)-1 = f.

A function f : E → F is said bijective (or a bijection) from E onto F, if it is both injective and 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.
In particular IdE : EE.

### Diverse properties

Proposition. Let f : E → F and g : F → G. Then
1. (Inj f ∧ Inj g) ⇒ Inj(gf)
2. Inj(gf) ⇒ Inj f
3. Im(gf) = g[Im f] ⊂ Im g.
Proofs:
1. 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]. ∎
From 3. we can obviously deduce

Im(gf) = G ⇒ Im g = G
Im f = F ⇒ Im(gf) = Im g
(f:EF) ⇒ (g:FGgf:EG)

Let f : E → F, and a function g with Dom g = F. Then, easily,
 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))
Proof of the non-obvious step :

(gf = IdE ∧ Inj g ∧ Im gE) ⇒ (∀yF, g(f(g(y))) = g(y) ∴ y = f(g(y)) ∈ Im f)

Proposition. (f : EFg : FEgf = IdE) ⇒ (Im f = F ⇔ Inj gfg = IdFg = f -1).

Proof : (Inj ggfg = g⚬IdF) ⇒ fg = IdF. ∎

Proposition. 1) If f,g are injective and Im f = Dom g, then (gf)-1 = f -1g-1.
2) If f,h : EF and g : FE then (gf = IdEhg = IdF) ⇔ ((g : FE) ∧ f = h = g−1).

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

### Canonical functions

For any objects x,y we shall say that x determines y if there is an invariant functor T (known but kept implicit) such that T(x) = y. Then the role of y as free variable can be played by the term T(x), thus by the use of x.
Similarly, a function f : EF will be said canonical if it is defined as ExT(x) where T is some invariant functor.
Examples of important canonical injections :
• EF ⇒ IdE : EF
• (x ↦ {x}) : E ↪ ℘(E)
• Gr : FE ↪ ℘(E×F).
A bijection f will be said bicanonical if both f and f−1 are canonical.
When a bijection f : E ↔  F is canonical (resp. bicanonical), we shall write f : EF (resp. f : EF); or, with its defining functor φ as φ : EF which means that (Ex ↦ φ(x)) is injective with image F. We shall write EF (resp. EF) to mean the existence of a canonical (resp. bicanonical) bijection, that is kept implicit. These will often look like equality properties on numbers, as the existence of a bijection between finite sets implies the equality of their numbers of elements.
Canonical bijections can fail to be bicanonical especially when their defining functor is not injective:

V2E ⥬ ℘(E)
E ≠ ∅ ⇒ {x}E ⥬ {x}
E×{x} ⥬ E
E×FF×E
E×{x} ⇌ {xEE{x}
E×{0} ⇌ E.

This meta-relation between sets is preserved by constructions: if EE′ and FF′ then ℘(E) ⥬ ℘(E'), E×FE′×F′ and FEFE (using the direct image of the graph), and the same for ⇌.
This is how transposition (E×FF×E) extends to both graphs and operations:

℘(E×F) ⇌ ℘(F×E)
GE×FGF×E
fGE×F, tf = (F×E∋(x,y) ↦ f(y,x)) ∈ GF×E.

### Sums of functions

The binder ∐ of sum of sets defines canonical bijections (whose inverses, defined by RRI, depend on I):

(℘(E))I ⥬ ℘(I×E)
iI ℘(Ai) ⥬ ℘(∐iI Ai)

Any sum of sets S = ∐iI Ai has its family of natural injections ji given by the curried ordered pair definer :

iI, ji : AiS.

The sum over I of functions fi where ∀iI, Ai = Dom fi is defined by

iI fi = (S ∋ (i,x) ↦ fi(x))
g = ∐iI fi ⇔ (Dom g = S ∧ ∀iI, fi = gji = g(i))

It is the inverse of the currying of binary operations, which we shall denote like for graphs: for any sets E, F and any operation (function) B with domain E×F ≠ ∅ (from which E and F can be restored as E = Dom Dom B and F = Im Dom B, while if E×F = ∅ the notation can be abusively kept while taking E and F from context),

B = (Ex ↦ (FyB(x,y)))
B = tB = (Fy ↦ (ExB(x,y))

Hence the canonical bijections (bicanonical if I = Dom S, thus if E ≠ ∅ in the case I×E)

SetF,
iI
FAiFS
SetE,F, (FE)IFI×E
(∀F : S → Set)
iI

xAi
F(i,x)
cS
Fc
(E×FGE×F×G
f ∈ (FE)I
iI
Gr fi ⊂ ℘(I×(E×F)) ⇌ ℘((I×EF) ⊃ Gr
iI
fi

### Product of functions or recurrying

Both curried forms R and R of graphs RE×F are exchanged by a bijection ℘(F)E  ↔  ℘(E)F defined with parameter F.
The similar bijection between both curried forms of operations with a given domain I×E, is defined by the binder ⊓ of product of functions all with domain E, and indexed by I :

(∀iI, Dom fi = E) ⇒
iI
fi = (Ex ↦ (fi(x))iI)
g, g =
iI
fi  ⇔ (g : E →
iI
Im fi ∧ ∀iI, fi = πig)
(F : I → Set) ⇒ ⊓ :
iI
FiE ⥬ (
iI
Fi)E
Set F ⇒ ⊓ : (FE)I ⥬ (FI)E

These bijections are canonical for nonempty families (I ≠ ∅) as only these determine E, and are usually bicanonical as their inverse uses I which is definable when E ≠ ∅; anyway we shall abusively keep the notation ⥬ for the general case while E remains fixed by the context.
A particular case is the binary product (I = V2):

Fncf,g, Dom f = Dom g = Efg = (Ex ↦ (f(x),g(x)))
IE×FE ⇌ (I×F)E
(
iI
Fi)E
ϕ∈IE

xE
Fϕ(x)
Fncf, Gr f = Im(IdDom ff)

 Set theory and Foundations of Mathematics 1. First foundations of mathematics 2. Set theory 2.1. Formalization of set theory 2.2. Set generation principle 2.3. Tuples 2.4. Uniqueness quantifiers 2.5. Families, Boolean operators on sets 2.6. Graphs 2.7. Products and powerset ⇦ 2.8. Injections, bijections ⇨ 2.9. Properties of binary relations 2.10. Axiom of choice Time in set theory Interpretation of classes Concepts of truth in mathematics 3. Algebra - 4. Arithmetic - 5. Second-order foundations

Other languages:
FR : 2.8. Injections, bijections