Article II: Isomorphisms
1. Isomorphisms
A map {A \xrightarrow{f} B} is called an isomorphism, or invertible map, if there is a map {B \xrightarrow{g} A} for which {g \circ f = 1_A} and {f \circ g = 1_B}.
A map g related to f by satisfying these equations is called an inverse for f.
Two objects A and B are said to be isomorphic if there is at least one isomorphism {A \xrightarrow{f} B}.
The corresponding mathlib definition for isomorphism is Iso (and IsIso), which we print below for reference.
#print Iso
#print IsIso
Reflexive: A is isomorphic to A.
Symmetric: If A is isomorphic to B, then B is isomorphic to A.
Transitive: If A is isomorphic to B, and B is isomorphic to C, then A is isomorphic to C.
The respective mathlib definitions are Iso.refl, Iso.symm, and Iso.trans, which we print below for reference.
#print Iso.refl
#print Iso.symm
#print Iso.trans
(R) Show that {A \xrightarrow{1_A} A} is an isomorphism. (Hint: find an inverse for 1_A.)
(S) Show that if {A \xrightarrow{f} B} is an isomorphism, and {B \xrightarrow{g} A} is an inverse for f; then g is also an isomorphism. (Hint: find an inverse for g.)
(T) Show that if {A \xrightarrow{f} B} and {B \xrightarrow{k} C} are isomorphisms, {A \xrightarrow{k \circ f} C} is also an isomorphism.
Solution: Exercise 1
variable {π : Type u} [Category.{v, u} π] {A B C : π}
(R) 1_A is an inverse for itself, so 1_A is an isomorphism.
example : IsIso (π A) := π:Type uinstβ:Category.{v, u} πA:πB:πC:πβ’ IsIso (π A)
π:Type uinstβ:Category.{v, u} πA:πB:πC:πβ’ π A β π A = π A β§ π A β π A = π A
π:Type uinstβ:Category.{v, u} πA:πB:πC:πβ’ π A β π A = π Aπ:Type uinstβ:Category.{v, u} πA:πB:πC:πβ’ π A β π A = π A π:Type uinstβ:Category.{v, u} πA:πB:πC:πβ’ π A β π A = π Aπ:Type uinstβ:Category.{v, u} πA:πB:πC:πβ’ π A β π A = π A All goals completed! π
(S) f is an inverse for g, so g is an isomorphism. (Note that the hypothesis "f is an isomorphism" is redundant here and could be omitted.)
example (f : A βΆ B) (_ : IsIso f)
(g : B βΆ A) (hg : g β f = π A β§ f β g = π B)
: IsIso g := π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bxβ:IsIso fg:B βΆ Ahg:g β f = π A β§ f β g = π Bβ’ IsIso g
π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bxβ:IsIso fg:B βΆ Ahg:g β f = π A β§ f β g = π Bβ’ f β g = π B β§ g β f = π A
All goals completed! π
(T) Composition of isomorphisms is transitive, so {k \circ f} is an isomorphism.
example (f : A βΆ B) (hf : IsIso f) (k : B βΆ C) (hk : IsIso k)
: IsIso (k β f) := π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bhf:IsIso fk:B βΆ Chk:IsIso kβ’ IsIso (k β f)
π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Chk:IsIso kfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ IsIso (k β f)
π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ IsIso (k β f)
π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ (finv β kinv) β k β f = π A β§ (k β f) β finv β kinv = π C
π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ (finv β kinv) β k β f = π Aπ:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ (k β f) β finv β kinv = π C
π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ (finv β kinv) β k β f = π A h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ (finv β kinv β k) β f = π A
rw [hkinv.1, h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ (finv β π B) β f = π A Category.id_comp, h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ finv β f = π A hfinv.1 h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ π A = π A] All goals completed! π
Β· h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ (k β f) β finv β kinv = π C rw [Category.assoc, h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ ((k β f) β finv) β kinv = π C β Category.assoc finv h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ (k β f β finv) β kinv = π C] h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ (k β f β finv) β kinv = π C
rw [hfinv.2, h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ (k β π B) β kinv = π C Category.id_comp, h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ k β kinv = π C hkinv.2 h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bk:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bkinv:C βΆ Bhkinv:kinv β k = π B β§ k β kinv = π Cβ’ π C = π C] All goals completed! π
Suppose {B \xrightarrow{g} A} and {B \xrightarrow{k} A} are both inverses for {A \xrightarrow{f} B}. Show that {g = k}.
Solution: Exercise 2
The inverse of a map is unique (when it exists).
example {π : Type u} [Category.{v, u} π] {A B : π} (f : A βΆ B)
(g : B βΆ A) (hg : g β f = π A β§ f β g = π B)
(k : B βΆ A) (hk : k β f = π A β§ f β k = π B)
: g = k := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bg:B βΆ Ahg:g β f = π A β§ f β g = π Bk:B βΆ Ahk:k β f = π A β§ f β k = π Bβ’ g = k
calc
g = π A β g := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bg:B βΆ Ahg:g β f = π A β§ f β g = π Bk:B βΆ Ahk:k β f = π A β§ f β k = π Bβ’ g = π A β g rw [Category.comp_id π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bg:B βΆ Ahg:g β f = π A β§ f β g = π Bk:B βΆ Ahk:k β f = π A β§ f β k = π Bβ’ g = g] All goals completed! π
_ = (k β f) β g := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bg:B βΆ Ahg:g β f = π A β§ f β g = π Bk:B βΆ Ahk:k β f = π A β§ f β k = π Bβ’ π A β g = (k β f) β g rw [hk.1 π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bg:B βΆ Ahg:g β f = π A β§ f β g = π Bk:B βΆ Ahk:k β f = π A β§ f β k = π Bβ’ π A β g = π A β g] All goals completed! π
_ = k β (f β g) := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bg:B βΆ Ahg:g β f = π A β§ f β g = π Bk:B βΆ Ahk:k β f = π A β§ f β k = π Bβ’ (k β f) β g = k β f β g rw [Category.assoc π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bg:B βΆ Ahg:g β f = π A β§ f β g = π Bk:B βΆ Ahk:k β f = π A β§ f β k = π Bβ’ (k β f) β g = (k β f) β g] All goals completed! π
_ = k β π B := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bg:B βΆ Ahg:g β f = π A β§ f β g = π Bk:B βΆ Ahk:k β f = π A β§ f β k = π Bβ’ k β f β g = k β π B rw [hg.2 π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bg:B βΆ Ahg:g β f = π A β§ f β g = π Bk:B βΆ Ahk:k β f = π A β§ f β k = π Bβ’ k β π B = k β π B] All goals completed! π
_ = k := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bg:B βΆ Ahg:g β f = π A β§ f β g = π Bk:B βΆ Ahk:k β f = π A β§ f β k = π Bβ’ k β π B = k rw [Category.id_comp π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bg:B βΆ Ahg:g β f = π A β§ f β g = π Bk:B βΆ Ahk:k β f = π A β§ f β k = π Bβ’ k = k] All goals completed! π
If f has an inverse, then f satisfies the two cancellation laws:
(a) If {f \circ h = f \circ k}, then {h = k}.
(b) If {h \circ f = k \circ f}, then {h = k}.
Warning: The following 'cancellation law' is not correct, even if f has an inverse.
(c) (wrong): If {h \circ f = f \circ k}, then {h = k}.
Solution: Exercise 3
variable {π : Type u} [Category.{v, u} π] {A B : π}
(a) We show that f is left-cancellative.
example (f : A βΆ B)
(hf : β finv : B βΆ A, finv β f = π A β§ f β finv = π B)
(h : B βΆ A) (k : B βΆ A)
: f β h = f β k β h = k := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bhf:β finv, finv β f = π A β§ f β finv = π Bh:B βΆ Ak:B βΆ Aβ’ f β h = f β k β h = k
obtain β¨finv, hfinvβ, hfinvββ© := hf π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bβ’ f β h = f β k β h = k
intro hβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:f β h = f β kβ’ h = k
have hβ : finv β f β h = finv β f β k := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bhf:β finv, finv β f = π A β§ f β finv = π Bh:B βΆ Ak:B βΆ Aβ’ f β h = f β k β h = k rw [hβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:f β h = f β kβ’ finv β f β k = finv β f β k] π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:f β h = f β khβ:finv β f β h = finv β f β kβ’ h = k
repeat rw [Category.assoc π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:f β h = f β khβ:(finv β f) β h = finv β f β kβ’ h = k] π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:f β h = f β khβ:(finv β f) β h = finv β f β kβ’ h = k at hβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:f β h = f β khβ:(finv β f) β h = (finv β f) β kβ’ h = k
rw [hfinvβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:f β h = f β khβ:π A β h = π A β kβ’ h = k] at hβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:f β h = f β khβ:π A β h = π A β kβ’ h = k
repeat rw [Category.comp_id π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:f β h = f β khβ:h = π A β kβ’ h = k] π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:f β h = f β khβ:h = π A β kβ’ h = k at hβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:f β h = f β khβ:h = kβ’ h = k
exact hβ All goals completed! π
(b) We show that f is right-cancellative.
example (f : A βΆ B)
(hf : β finv : B βΆ A, finv β f = π A β§ f β finv = π B)
(h : B βΆ A) (k : B βΆ A)
: h β f = k β f β h = k := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bhf:β finv, finv β f = π A β§ f β finv = π Bh:B βΆ Ak:B βΆ Aβ’ h β f = k β f β h = k
obtain β¨finv, hfinvβ, hfinvββ© := hf π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bβ’ h β f = k β f β h = k
intro hβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:h β f = k β fβ’ h = k
have hβ : (h β f) β finv = (k β f) β finv := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bhf:β finv, finv β f = π A β§ f β finv = π Bh:B βΆ Ak:B βΆ Aβ’ h β f = k β f β h = k rw [hβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:h β f = k β fβ’ (k β f) β finv = (k β f) β finv] π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:h β f = k β fhβ:(h β f) β finv = (k β f) β finvβ’ h = k
repeat rw [β Category.assoc π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:h β f = k β fhβ:h β f β finv = (k β f) β finvβ’ h = k] π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:h β f = k β fhβ:h β f β finv = (k β f) β finvβ’ h = k at hβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:h β f = k β fhβ:h β f β finv = k β f β finvβ’ h = k
rw [hfinvβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:h β f = k β fhβ:h β π B = k β π Bβ’ h = k] at hβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:h β f = k β fhβ:h β π B = k β π Bβ’ h = k
repeat rw [Category.id_comp π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:h β f = k β fhβ:h = k β π Bβ’ h = k] π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:h β f = k β fhβ:h = k β π Bβ’ h = k at hβ π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bh:B βΆ Ak:B βΆ Afinv:B βΆ Ahfinvβ:finv β f = π Ahfinvβ:f β finv = π Bhβ:h β f = k β fhβ:h = kβ’ h = k
exact hβ All goals completed! π
(c) We take our counterexample from endomaps on Fin 2, the canonical type with two elements.
def f : Fin 2 βΆ Fin 2 := βΎfun
| 0 => 1
| 1 => 0
f has an inverse, as required. (f is self-inverse.)
example : f β f = π (Fin 2) := by π:Type uinstβ:Category.{v, u} πA:πB:πβ’ f β f = π (Fin 2)
ext x π:Type uinstβ:Category.{v, u} πA:πB:πx:Fin 2β’ β((ConcreteCategory.hom (f β f)).toFun x) = β((ConcreteCategory.hom (π (Fin 2))).toFun x)
fin_cases x Β«0Β» π:Type uinstβ:Category.{v, u} πA:πB:πβ’ β((ConcreteCategory.hom (f β f)).toFun ((fun i β¦ i) β¨0, β―β©)) =
β((ConcreteCategory.hom (π (Fin 2))).toFun ((fun i β¦ i) β¨0, β―β©))Β«1Β» π:Type uinstβ:Category.{v, u} πA:πB:πβ’ β((ConcreteCategory.hom (f β f)).toFun ((fun i β¦ i) β¨1, β―β©)) =
β((ConcreteCategory.hom (π (Fin 2))).toFun ((fun i β¦ i) β¨1, β―β©)) <;> Β«0Β» π:Type uinstβ:Category.{v, u} πA:πB:πβ’ β((ConcreteCategory.hom (f β f)).toFun ((fun i β¦ i) β¨0, β―β©)) =
β((ConcreteCategory.hom (π (Fin 2))).toFun ((fun i β¦ i) β¨0, β―β©))Β«1Β» π:Type uinstβ:Category.{v, u} πA:πB:πβ’ β((ConcreteCategory.hom (f β f)).toFun ((fun i β¦ i) β¨1, β―β©)) =
β((ConcreteCategory.hom (π (Fin 2))).toFun ((fun i β¦ i) β¨1, β―β©)) dsimp [f] All goals completed! π
def h : Fin 2 βΆ Fin 2 := βΎfun
| 0 => 1
| 1 => 1
def k : Fin 2 βΆ Fin 2 := βΎfun
| 0 => 0
| 1 => 0
example : Β¬(h β f = f β k β h = k) := by π:Type uinstβ:Category.{v, u} πA:πB:πβ’ Β¬(h β f = f β k β h = k)
push Not π:Type uinstβ:Category.{v, u} πA:πB:πβ’ h β f = f β k β§ h β k
constructor left π:Type uinstβ:Category.{v, u} πA:πB:πβ’ h β f = f β kright π:Type uinstβ:Category.{v, u} πA:πB:πβ’ h β k
Β· left π:Type uinstβ:Category.{v, u} πA:πB:πβ’ h β f = f β k ext x left π:Type uinstβ:Category.{v, u} πA:πB:πx:Fin 2β’ β((ConcreteCategory.hom (h β f)).toFun x) = β((ConcreteCategory.hom (f β k)).toFun x)
fin_cases x left.Β«0Β» π:Type uinstβ:Category.{v, u} πA:πB:πβ’ β((ConcreteCategory.hom (h β f)).toFun ((fun i β¦ i) β¨0, β―β©)) =
β((ConcreteCategory.hom (f β k)).toFun ((fun i β¦ i) β¨0, β―β©))left.Β«1Β» π:Type uinstβ:Category.{v, u} πA:πB:πβ’ β((ConcreteCategory.hom (h β f)).toFun ((fun i β¦ i) β¨1, β―β©)) =
β((ConcreteCategory.hom (f β k)).toFun ((fun i β¦ i) β¨1, β―β©)) <;> left.Β«0Β» π:Type uinstβ:Category.{v, u} πA:πB:πβ’ β((ConcreteCategory.hom (h β f)).toFun ((fun i β¦ i) β¨0, β―β©)) =
β((ConcreteCategory.hom (f β k)).toFun ((fun i β¦ i) β¨0, β―β©))left.Β«1Β» π:Type uinstβ:Category.{v, u} πA:πB:πβ’ β((ConcreteCategory.hom (h β f)).toFun ((fun i β¦ i) β¨1, β―β©)) =
β((ConcreteCategory.hom (f β k)).toFun ((fun i β¦ i) β¨1, β―β©)) dsimp [f, h, k] All goals completed! π
Β· right π:Type uinstβ:Category.{v, u} πA:πB:πβ’ h β k by_contra hβ right π:Type uinstβ:Category.{v, u} πA:πB:πhβ:h = kβ’ False
have hβ : h 0 = 1 := rfl right π:Type uinstβ:Category.{v, u} πA:πB:πhβ:h = khβ:(ConcreteCategory.hom h) 0 = 1β’ False
have hβ : k 0 = 0 := rfl right π:Type uinstβ:Category.{v, u} πA:πB:πhβ:h = khβ:(ConcreteCategory.hom h) 0 = 1hβ:(ConcreteCategory.hom k) 0 = 0β’ False
rw [β hβ, right π:Type uinstβ:Category.{v, u} πA:πB:πhβ:h = khβ:(ConcreteCategory.hom h) 0 = 1hβ:(ConcreteCategory.hom h) 0 = 0β’ False hβ right π:Type uinstβ:Category.{v, u} πA:πB:πhβ:h = khβ:(ConcreteCategory.hom h) 0 = 1hβ:1 = 0β’ False] at hβ right π:Type uinstβ:Category.{v, u} πA:πB:πhβ:h = khβ:(ConcreteCategory.hom h) 0 = 1hβ:1 = 0β’ False
contradiction All goals completed! π
For each of the five maps below: decide whether it is invertible; and if it is invertible, find a 'formula' for the inverse map.
-
\mathbb{R} \xrightarrow{f} \mathbb{R},\; f(x) = 3x + 7 -
\mathbb{R}_{\ge 0} \xrightarrow{g} \mathbb{R}_{\ge 0},\; g(x) = x^2 -
\mathbb{R} \xrightarrow{h} \mathbb{R},\; h(x) = x^2 -
\mathbb{R} \xrightarrow{k} \mathbb{R}_{\ge 0},\; k(x) = x^2 -
\mathbb{R}_{\ge 0} \xrightarrow{l} \mathbb{R}_{\ge 0},\; l(x) = \dfrac{1}{x + 1}
Solution: Exercise 4
Since all five maps have their domain and codomain as the real numbers (or a subset of the real numbers), we implement them as functions in Lean.
f is invertible, with inverse {f^{-1}(x) = \dfrac{x - 7}{3}}.
example (f : β β β) (hf : β x : β, f x = 3 * x + 7)
: β finv : β β β, finv β f = id β§ f β finv = id := by f:β β βhf:β (x : β), f x = 3 * x + 7β’ β finv, finv β f = id β§ f β finv = id
use fun x β¦ (x - 7) / 3 h f:β β βhf:β (x : β), f x = 3 * x + 7β’ (fun x β¦ (x - 7) / 3) β f = id β§ (f β fun x β¦ (x - 7) / 3) = id -- fβ»ΒΉ(x)
constructor h.left f:β β βhf:β (x : β), f x = 3 * x + 7β’ (fun x β¦ (x - 7) / 3) β f = idh.right f:β β βhf:β (x : β), f x = 3 * x + 7β’ (f β fun x β¦ (x - 7) / 3) = id
Β· h.left f:β β βhf:β (x : β), f x = 3 * x + 7β’ (fun x β¦ (x - 7) / 3) β f = id funext x h.left f:β β βhf:β (x : β), f x = 3 * x + 7x:ββ’ ((fun x β¦ (x - 7) / 3) β f) x = id x
rw [Function.comp_apply, h.left f:β β βhf:β (x : β), f x = 3 * x + 7x:ββ’ (f x - 7) / 3 = id x id_eq, h.left f:β β βhf:β (x : β), f x = 3 * x + 7x:ββ’ (f x - 7) / 3 = x hf x h.left f:β β βhf:β (x : β), f x = 3 * x + 7x:ββ’ (3 * x + 7 - 7) / 3 = x] h.left f:β β βhf:β (x : β), f x = 3 * x + 7x:ββ’ (3 * x + 7 - 7) / 3 = x
ring All goals completed! π
Β· h.right f:β β βhf:β (x : β), f x = 3 * x + 7β’ (f β fun x β¦ (x - 7) / 3) = id funext x h.right f:β β βhf:β (x : β), f x = 3 * x + 7x:ββ’ (f β fun x β¦ (x - 7) / 3) x = id x
rw [Function.comp_apply, h.right f:β β βhf:β (x : β), f x = 3 * x + 7x:ββ’ f ((x - 7) / 3) = id x id_eq, h.right f:β β βhf:β (x : β), f x = 3 * x + 7x:ββ’ f ((x - 7) / 3) = x hf ((x - 7) / 3) h.right f:β β βhf:β (x : β), f x = 3 * x + 7x:ββ’ 3 * ((x - 7) / 3) + 7 = x] h.right f:β β βhf:β (x : β), f x = 3 * x + 7x:ββ’ 3 * ((x - 7) / 3) + 7 = x
ring All goals completed! π
g is invertible, with inverse {g^{-1}(x) = \sqrt{x}}.
open NNReal in
example (g : ββ₯0 β ββ₯0) (hg : β x : ββ₯0, g x = x * x)
: β ginv : ββ₯0 β ββ₯0, ginv β g = id β§ g β ginv = id := by g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xβ’ β ginv, ginv β g = id β§ g β ginv = id
use fun x β¦ NNReal.sqrt x h g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xβ’ (fun x β¦ sqrt x) β g = id β§ (g β fun x β¦ sqrt x) = id -- gβ»ΒΉ(x)
constructor h.left g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xβ’ (fun x β¦ sqrt x) β g = idh.right g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xβ’ (g β fun x β¦ sqrt x) = id
Β· h.left g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xβ’ (fun x β¦ sqrt x) β g = id funext x h.left g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xx:ββ₯0β’ ((fun x β¦ sqrt x) β g) x = id x
rw [Function.comp_apply, h.left g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xx:ββ₯0β’ sqrt (g x) = id x id_eq, h.left g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xx:ββ₯0β’ sqrt (g x) = x hg x h.left g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xx:ββ₯0β’ sqrt (x * x) = x] h.left g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xx:ββ₯0β’ sqrt (x * x) = x
exact NNReal.sqrt_mul_self x All goals completed! π
Β· h.right g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xβ’ (g β fun x β¦ sqrt x) = id funext x h.right g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xx:ββ₯0β’ (g β fun x β¦ sqrt x) x = id x
rw [Function.comp_apply, h.right g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xx:ββ₯0β’ g (sqrt x) = id x id_eq, h.right g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xx:ββ₯0β’ g (sqrt x) = x hg (sqrt x) h.right g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xx:ββ₯0β’ sqrt x * sqrt x = x] h.right g:ββ₯0 β ββ₯0hg:β (x : ββ₯0), g x = x * xx:ββ₯0β’ sqrt x * sqrt x = x
exact mul_self_sqrt x All goals completed! π
h is not invertible, since {h(1) = h(-1) = 1}.
example (h : β β β) (hh : β x : β, h x = x * x)
: Β¬(β hinv : β β β, hinv β h = id β§ h β hinv = id) := by h:β β βhh:β (x : β), h x = x * xβ’ Β¬β hinv, hinv β h = id β§ h β hinv = id
push Not h:β β βhh:β (x : β), h x = x * xβ’ β (hinv : β β β), hinv β h = id β h β hinv β id
intro hinv h_inv_left _ h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idβ’ False
have hβ : h 1 = 1 := by h:β β βhh:β (x : β), h x = x * xβ’ Β¬β hinv, hinv β h = id β§ h β hinv = id
rw [hh 1 h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idβ’ 1 * 1 = 1] h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idβ’ 1 * 1 = 1
norm_num1 h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1β’ False
have hβ : h (-1) = 1 := by h:β β βhh:β (x : β), h x = x * xβ’ Β¬β hinv, hinv β h = id β§ h β hinv = id
rw [hh (-1) h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1β’ -1 * -1 = 1] h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1β’ -1 * -1 = 1
norm_num1 h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1β’ False
have hβ : (hinv β h) 1 = 1:= by h:β β βhh:β (x : β), h x = x * xβ’ Β¬β hinv, hinv β h = id β§ h β hinv = id
rw [h_inv_left, h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1β’ id 1 = 1 id_eq h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1β’ 1 = 1] h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1hβ:(hinv β h) 1 = 1β’ False
have hβ : (hinv β h) (-1) = -1 := by h:β β βhh:β (x : β), h x = x * xβ’ Β¬β hinv, hinv β h = id β§ h β hinv = id
rw [h_inv_left, h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1hβ:(hinv β h) 1 = 1β’ id (-1) = -1 id_eq h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1hβ:(hinv β h) 1 = 1β’ -1 = -1] h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1hβ:(hinv β h) 1 = 1hβ:(hinv β h) (-1) = -1β’ False
dsimp at hβ hβ h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1hβ:hinv (h 1) = 1hβ:hinv (h (-1)) = -1β’ False
rw [hβ h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1hβ:hinv 1 = 1hβ:hinv (h (-1)) = -1β’ False] at hβ h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1hβ:hinv 1 = 1hβ:hinv (h (-1)) = -1β’ False
rw [hβ h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1hβ:hinv 1 = 1hβ:hinv 1 = -1β’ False] at hβ h:β β βhh:β (x : β), h x = x * xhinv:β β βh_inv_left:hinv β h = idaβ:h β hinv = idhβ:h 1 = 1hβ:h (-1) = 1hβ:hinv 1 = 1hβ:hinv 1 = -1β’ False
linarith All goals completed! π
k is not invertible, since {k(1) = k(-1) = 1}.
open NNReal in
example (k : β β ββ₯0) (hk : β x : β, k x = x * x)
: Β¬(β kinv : ββ₯0 β β, kinv β k = id β§ k β kinv = id) := by k:β β ββ₯0hk:β (x : β), β(k x) = x * xβ’ Β¬β kinv, kinv β k = id β§ k β kinv = id
push Not k:β β ββ₯0hk:β (x : β), β(k x) = x * xβ’ β (kinv : ββ₯0 β β), kinv β k = id β k β kinv β id
intro kinv h_inv_left _ k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idβ’ False
have hβ : k 1 = 1 := by k:β β ββ₯0hk:β (x : β), β(k x) = x * xβ’ Β¬β kinv, kinv β k = id β§ k β kinv = id
rw [β coe_eq_one, k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idβ’ β(k 1) = 1 hk 1 k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idβ’ 1 * 1 = 1] k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idβ’ 1 * 1 = 1
norm_num1 k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1β’ False
have hβ : k (-1) = 1 := by k:β β ββ₯0hk:β (x : β), β(k x) = x * xβ’ Β¬β kinv, kinv β k = id β§ k β kinv = id
rw [β coe_eq_one, k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1β’ β(k (-1)) = 1 hk (-1) k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1β’ -1 * -1 = 1] k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1β’ -1 * -1 = 1
norm_num1 k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1β’ False
have hβ : (kinv β k) 1 = 1:= by k:β β ββ₯0hk:β (x : β), β(k x) = x * xβ’ Β¬β kinv, kinv β k = id β§ k β kinv = id
rw [h_inv_left, k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1β’ id 1 = 1 id_eq k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1β’ 1 = 1] k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1hβ:(kinv β k) 1 = 1β’ False
have hβ : (kinv β k) (-1) = -1 := by k:β β ββ₯0hk:β (x : β), β(k x) = x * xβ’ Β¬β kinv, kinv β k = id β§ k β kinv = id
rw [h_inv_left, k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1hβ:(kinv β k) 1 = 1β’ id (-1) = -1 id_eq k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1hβ:(kinv β k) 1 = 1β’ -1 = -1] k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1hβ:(kinv β k) 1 = 1hβ:(kinv β k) (-1) = -1β’ False
dsimp at hβ hβ k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1hβ:kinv (k 1) = 1hβ:kinv (k (-1)) = -1β’ False
rw [hβ k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1hβ:kinv 1 = 1hβ:kinv (k (-1)) = -1β’ False] at hβ k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1hβ:kinv 1 = 1hβ:kinv (k (-1)) = -1β’ False
rw [hβ k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1hβ:kinv 1 = 1hβ:kinv 1 = -1β’ False] at hβ k:β β ββ₯0hk:β (x : β), β(k x) = x * xkinv:ββ₯0 β βh_inv_left:kinv β k = idaβ:k β kinv = idhβ:k 1 = 1hβ:k (-1) = 1hβ:kinv 1 = 1hβ:kinv 1 = -1β’ False
linarith All goals completed! π
l is invertible, with inverse {l^{-1}(x) = \dfrac{1}{x} - 1}, provided that we restrict the codomain of l to the interval {(0,1]}.
TODO Exercise II.4.5
2. General division problems: Determination and choice
Exercise 5 concerns counting the number of sections and retractions for a map (though those terms aren't formally defined until a short while later on p. 49). Rather than providing an exhaustive list of maps, we introduce here two formulas β what the book later calls Chad's formula and Danilo's formula (p. 117).
The former states that the number of sections for a map p is given by
\prod_{\mathbf{1} \xrightarrow{a} A} \#(p^{-1}a),
where A is the codomain of p.
def Chad's_formula {Ξ± Ο : Type*} [DecidableEq Ξ±]
[Fintype Ξ±] [Fintype Ο] (X : Finset Ο) (A : Finset Ξ±)
(p : Ο β Ξ±)
: β :=
β a β A, pinvCount a
where
pinvCount (a : Ξ±) : β := X.filter (fun x β¦ p x = a) |>.card
The latter states that the number of retractions for a map j, assuming j is injective, is given by
(\#A)^{(\#X - \#A)},
where A is the domain of j and X is the codomain of j.
open Finset in
def Danilo's_formula {Ξ± Ο : Type*}
[Fintype Ξ±] [Fintype Ο] (A : Finset Ξ±) (X : Finset Ο)
(j : Ξ± β Ο) (p : Ο β Ξ±) (_ : p β j = id) (_ : Function.Injective j)
: β :=
#A ^ (#X - #A)
Given
\{b, p, q, r, s\} \xrightarrow{g} \{0, 1\}\\\
\qquad b \mapsto 0\\\
\qquad p \mapsto 0\\\
\qquad q \mapsto 0\\\
\qquad r \mapsto 1\\\
\qquad s \mapsto 1,
how many maps f are there with {g \circ f = 1_{\{0, 1\}}}?
Choosing a particular such f, how many maps g (including the given one) satisfy the same equation?
Solution: Exercise 5
set_option backward.isDefEq.respectTransparency false in
inductive XElems
| b | p | q | r | s
deriving Fintype
def A : Finset (Fin 2) := Finset.univ
def X : Finset XElems := Finset.univ
open XElems in
def g : XElems β Fin 2
| b => 0
| p => 0
| q => 0
| r => 1
| s => 1
By Chad's formula, we have 6 different maps f with {g \circ f = 1_{\{0, 1\}}}.
#eval Chad's_formula X A g
We choose f to be
open XElems in
def f : Fin 2 β XElems
| 0 => b
| 1 => r
Then, by Danilo's formula, we have {(\#A)^{(\#X - \#A)} = 2^3 = 8} different maps g.
#eval Danilo's_formula A X f g
(by β’ g β f = id
funext x x:Fin 2β’ (g β f) x = id x
fin_cases x Β«0Β» β’ (g β f) ((fun i β¦ i) β¨0, β―β©) = id ((fun i β¦ i) β¨0, β―β©)Β«1Β» β’ (g β f) ((fun i β¦ i) β¨1, β―β©) = id ((fun i β¦ i) β¨1, β―β©) <;> Β«0Β» β’ (g β f) ((fun i β¦ i) β¨0, β―β©) = id ((fun i β¦ i) β¨0, β―β©)Β«1Β» β’ (g β f) ((fun i β¦ i) β¨1, β―β©) = id ((fun i β¦ i) β¨1, β―β©) rfl All goals completed! π)
(by β’ Function.Injective f
intro x y _ x:Fin 2y:Fin 2aβ:f x = f yβ’ x = y
fin_cases x Β«0Β» y:Fin 2aβ:f ((fun i β¦ i) β¨0, β―β©) = f yβ’ (fun i β¦ i) β¨0, β―β© = yΒ«1Β» y:Fin 2aβ:f ((fun i β¦ i) β¨1, β―β©) = f yβ’ (fun i β¦ i) β¨1, β―β© = y <;> Β«0Β» y:Fin 2aβ:f ((fun i β¦ i) β¨0, β―β©) = f yβ’ (fun i β¦ i) β¨0, β―β© = yΒ«1Β» y:Fin 2aβ:f ((fun i β¦ i) β¨1, β―β©) = f yβ’ (fun i β¦ i) β¨1, β―β© = y fin_cases y Β«1Β».Β«0Β» aβ:f ((fun i β¦ i) β¨1, β―β©) = f ((fun i β¦ i) β¨0, β―β©)β’ (fun i β¦ i) β¨1, β―β© = (fun i β¦ i) β¨0, β―β©Β«1Β».Β«1Β» aβ:f ((fun i β¦ i) β¨1, β―β©) = f ((fun i β¦ i) β¨1, β―β©)β’ (fun i β¦ i) β¨1, β―β© = (fun i β¦ i) β¨1, β―β©
all_goals
first | rfl All goals completed! π
| simp only [Fin.zero_eta, Fin.isValue, Fin.mk_one,
zero_ne_one] Β«1Β».Β«0Β» aβ:f ((fun i β¦ i) β¨1, β―β©) = f ((fun i β¦ i) β¨0, β―β©)β’ 1 = 0; trivial All goals completed! π)
3. Retractions, sections, and idempotents
If {A \xrightarrow{f} B}:
a retraction for f is a map {B \xrightarrow{r} A} for which {r \circ f = 1_A};
a section for f is a map {B \xrightarrow{s} A} for which {f \circ s = 1_B}.
The mathlib definition corresponding to retraction is SplitMono (and IsSplitMono), which we print below for reference.
#print SplitMono
#print IsSplitMono
We alias SplitMono and IsSplitMono as Retraction and IsRetraction, respectively, to remain aligned with the terminology in the book.
abbrev Retraction {π : Type u} [Category.{v, u} π] {A B : π}
(f : A βΆ B) :=
SplitMono f
abbrev IsRetraction {π : Type u} [Category.{v, u} π] {A B : π}
(f : A βΆ B) :=
IsSplitMono f
The mathlib definition corresponding to section is SplitEpi (and IsSplitEpi), which we print below for reference.
#print SplitEpi
#print IsSplitEpi
We alias SplitEpi and IsSplitEpi as Section and IsSection, respectively, to remain aligned with the terminology in the book.
abbrev Section {π : Type u} [Category.{v, u} π] {A B : π}
(f : A βΆ B) :=
SplitEpi f
abbrev IsSection {π : Type u} [Category.{v, u} π] {A B : π}
(f : A βΆ B) :=
IsSplitEpi f
If a map {A \xrightarrow{f} B} has a section, then for any T and for any map {T \xrightarrow{y} B} there exists a map {T \xrightarrow{x} A} for which {f \circ x = y}.
The assumption means that we have a map s for which {f \circ s = 1_B}. Thus for any given map {T \xrightarrow{y} B} we see that we could define a map x with at least the correct domain and codomain by taking the composite s following y
x = s \circ y.
Does this map x actually satisfy the required equation? Calculating
f \circ x = f \circ (s \circ y) = (f \circ s) \circ y = 1_B \circ y = y
we see that it does.
Our implementation in Lean faithfully follows the argument of the book proof given above.
theorem prop1 {π : Type u} [Category.{v, u} π] {A B T : π}
(f : A βΆ B) [hf : IsSection f]
: β y : T βΆ B, β x : T βΆ A, f β x = y := by π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bhf:IsSection fβ’ β (y : T βΆ B), β x, f β x = y
obtain β¨s, hfβ© := hf π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Bβ’ β (y : T βΆ B), β x, f β x = y
intro y π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π By:T βΆ Bβ’ β x, f β x = y
use s β y h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π By:T βΆ Bβ’ f β s β y = y
rw [Category.assoc h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π By:T βΆ Bβ’ (f β s) β y = y] h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π By:T βΆ Bβ’ (f β s) β y = y
rw [hf h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π By:T βΆ Bβ’ π B β y = y] h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π By:T βΆ Bβ’ π B β y = y
exact Category.comp_id y All goals completed! π
If the map {A \xrightarrow{f} B} has a retraction, then for any map {A \xrightarrow{g} T}, there is a map {B \xrightarrow{t} T} for which {t \circ f = g}. (This is Proposition 1*.)
Solution: Exercise 6
Put {t = g \circ r}.
theorem Β«prop1*Β» {π : Type u} [Category.{v, u} π] {A B T : π}
(f : A βΆ B) [hf : IsRetraction f]
: β g : A βΆ T, β t : B βΆ T, t β f = g := by π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bhf:IsRetraction fβ’ β (g : A βΆ T), β t, t β f = g
obtain β¨r, hfβ© := hf π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Aβ’ β (g : A βΆ T), β t, t β f = g
intro g π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Ag:A βΆ Tβ’ β t, t β f = g
use g β r h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Ag:A βΆ Tβ’ (g β r) β f = g
rw [β Category.assoc, h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Ag:A βΆ Tβ’ g β r β f = g hf, h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Ag:A βΆ Tβ’ g β π A = g Category.id_comp h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Ag:A βΆ Tβ’ g = g] All goals completed! π
Suppose a map {A \xrightarrow{f} B} has a retraction. Then for any set T and for any pair of maps {T \xrightarrow{x_1} A}, {T \xrightarrow{x_2} A} from any set T to A
\text{if}\; f \circ x_1 = f \circ x_2 \;\text{then}\; x_1 = x_2.
Looking back at the definition, we see that the assumption means that we have a map r for which {r \circ f = 1_A}. Using the assumption that x_1 and x_2 are such that f composes with them to get the same {T \rightarrow B}, we can compose further with r as follows:
x_1 = 1_A \circ x_1 = (r \circ f) \circ x_1 = r \circ (f \circ x_1) = r \circ (f \circ x_2) = (r \circ f) \circ x_2 = 1_A \circ x_2 = x_2.
Our implementation in Lean generalises the proposition from sets to any categorical object but otherwise faithfully follows the argument of the book proof given above.
theorem prop2 {π : Type u} [Category.{v, u} π] {A B T : π}
(f : A βΆ B) [hf : IsRetraction f]
: β xβ xβ : T βΆ A, f β xβ = f β xβ β xβ = xβ := by π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bhf:IsRetraction fβ’ β (xβ xβ : T βΆ A), f β xβ = f β xβ β xβ = xβ
obtain β¨r, hfβ© := hf π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Aβ’ β (xβ xβ : T βΆ A), f β xβ = f β xβ β xβ = xβ
intro xβ xβ h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ xβ = xβ
rw [β Category.comp_id xβ π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ π A β xβ = xβ] π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ π A β xβ = xβ
rw [β hf π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ (r β f) β xβ = xβ] π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ (r β f) β xβ = xβ
rw [β Category.assoc π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ r β f β xβ = xβ] π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ r β f β xβ = xβ
rw [h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ r β f β xβ = xβ] π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ r β f β xβ = xβ
rw [Category.assoc π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ (r β f) β xβ = xβ] π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ (r β f) β xβ = xβ
rw [hf π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ π A β xβ = xβ] π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Br:B βΆ Ahf:r β f = π Axβ:T βΆ Axβ:T βΆ Ah:f β xβ = f β xββ’ π A β xβ = xβ
exact Category.comp_id xβ All goals completed! π
A map f satisfying the conclusion of Proposition 2 (for any pair of maps {T \xrightarrow{x_1} A} and {T \xrightarrow{x_2} A}, if {f \circ x_1 = f \circ x_2} then {x_1 = x_2}) is said to be injective for maps from T.
If f is injective for maps from T for every T, one says that f is injective, or is a monomorphism.
The corresponding mathlib definition is Mono, which we print below for reference.
#print Mono
Suppose the map {A \xrightarrow{f} B} has a section. Then for any set T and any pair {B \xrightarrow{t_1} T}, {B \xrightarrow{t_2} T} of maps from B to T, if {t_1 \circ f = t_2 \circ f} then {t_1 = t_2}. (This is Proposition 2*.)
Solution: Exercise 7
A proof of Proposition 2* is given below.
theorem Β«prop2*Β» {π : Type u} [Category.{v, u} π] {A B T : π}
(f : A βΆ B) [hf : IsSection f]
: β tβ tβ : B βΆ T, tβ β f = tβ β f β tβ = tβ := by π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bhf:IsSection fβ’ β (tβ tβ : B βΆ T), tβ β f = tβ β f β tβ = tβ
obtain β¨s, hfβ© := hf π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Bβ’ β (tβ tβ : B βΆ T), tβ β f = tβ β f β tβ = tβ
intro tβ tβ h π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Btβ:B βΆ Ttβ:B βΆ Th:tβ β f = tβ β fβ’ tβ = tβ
rw [β Category.id_comp tβ, π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Btβ:B βΆ Ttβ:B βΆ Th:tβ β f = tβ β fβ’ tβ β π B = tβ β hf π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Btβ:B βΆ Ttβ:B βΆ Th:tβ β f = tβ β fβ’ tβ β f β s = tβ] π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Btβ:B βΆ Ttβ:B βΆ Th:tβ β f = tβ β fβ’ tβ β f β s = tβ
rw [Category.assoc, π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Btβ:B βΆ Ttβ:B βΆ Th:tβ β f = tβ β fβ’ (tβ β f) β s = tβ h, π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Btβ:B βΆ Ttβ:B βΆ Th:tβ β f = tβ β fβ’ (tβ β f) β s = tβ β Category.assoc π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Btβ:B βΆ Ttβ:B βΆ Th:tβ β f = tβ β fβ’ tβ β f β s = tβ] π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Btβ:B βΆ Ttβ:B βΆ Th:tβ β f = tβ β fβ’ tβ β f β s = tβ
rw [hf, π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Btβ:B βΆ Ttβ:B βΆ Th:tβ β f = tβ β fβ’ tβ β π B = tβ Category.id_comp π:Type uinstβ:Category.{v, u} πA:πB:πT:πf:A βΆ Bs:B βΆ Ahf:f β s = π Btβ:B βΆ Ttβ:B βΆ Th:tβ β f = tβ β fβ’ tβ = tβ] All goals completed! π
A map f with this cancellation property (if {t_1 \circ f = t_2 \circ f} then {t_1 = t_2}) for every T is called an epimorphism.
The corresponding mathlib definition is Epi, which we print below for reference.
#print Epi
Thus both 'monomorphism' and 'epimorphism' are 'cancellation' properties.
The mathlib theorems cancel_mono and cancel_epi are relevant here.
example {π : Type u} [Category.{v, u} π] {X Y Z : π}
(f : X βΆ Y) [Mono f] {g h : Z βΆ X}
: f β g = f β h β g = h := cancel_mono f
example {π : Type u} [Category.{v, u} π] {X Y Z : π}
(f : X βΆ Y) [Epi f] {g h : Y βΆ Z}
: g β f = h β f β g = h := cancel_epi f
If {A \xrightarrow{f} B} has a retraction and if {B \xrightarrow{g} C} has a retraction, then {A \xrightarrow{g \circ f} C} has a retraction.
Let {r_1 \circ f = 1_A} and {r_2 \circ g = 1_B}. Then a good guess for a retraction of the composite would be the composite of the retractions in the opposite order (which is anyway the only order in which they can be composed). Does it in fact work?
r \circ (g \circ f) = (r_1 \circ r_2) \circ (g \circ f) = r_1 \circ (r_2 \circ g) \circ f = r_1 \circ 1_B \circ f = r_1 \circ f = 1_A
proves that r is a retraction for {g \circ f}.
Our implementation in Lean faithfully follows the argument of the book proof given above.
theorem prop3 {π : Type u} [Category.{v, u} π] {A B C : π}
(f : A βΆ B) [hf : IsRetraction f] (g : B βΆ C) [hg : IsRetraction g]
: IsRetraction (g β f) := by π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bhf:IsRetraction fg:B βΆ Chg:IsRetraction gβ’ IsRetraction (g β f)
obtain β¨rβ, hfβ© := hf π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Chg:IsRetraction grβ:B βΆ Ahf:rβ β f = π Aβ’ IsRetraction (g β f)
obtain β¨rβ, hgβ© := hg π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Crβ:B βΆ Ahf:rβ β f = π Arβ:C βΆ Bhg:rβ β g = π Bβ’ IsRetraction (g β f)
use rβ β rβ id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Crβ:B βΆ Ahf:rβ β f = π Arβ:C βΆ Bhg:rβ β g = π Bβ’ autoParam ((rβ β rβ) β g β f = π A) SplitMono.id._autoParam
change (rβ β rβ) β (g β f) = π A id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Crβ:B βΆ Ahf:rβ β f = π Arβ:C βΆ Bhg:rβ β g = π Bβ’ (rβ β rβ) β g β f = π A
rw [Category.assoc, id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Crβ:B βΆ Ahf:rβ β f = π Arβ:C βΆ Bhg:rβ β g = π Bβ’ ((rβ β rβ) β g) β f = π A β Category.assoc g id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Crβ:B βΆ Ahf:rβ β f = π Arβ:C βΆ Bhg:rβ β g = π Bβ’ (rβ β rβ β g) β f = π A] id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Crβ:B βΆ Ahf:rβ β f = π Arβ:C βΆ Bhg:rβ β g = π Bβ’ (rβ β rβ β g) β f = π A
rw [hg id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Crβ:B βΆ Ahf:rβ β f = π Arβ:C βΆ Bhg:rβ β g = π Bβ’ (rβ β π B) β f = π A] id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Crβ:B βΆ Ahf:rβ β f = π Arβ:C βΆ Bhg:rβ β g = π Bβ’ (rβ β π B) β f = π A
rw [Category.id_comp id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Crβ:B βΆ Ahf:rβ β f = π Arβ:C βΆ Bhg:rβ β g = π Bβ’ rβ β f = π A] id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Crβ:B βΆ Ahf:rβ β f = π Arβ:C βΆ Bhg:rβ β g = π Bβ’ rβ β f = π A
exact hf All goals completed! π
We note that the corresponding mathlib instance is instIsSplitMonoComp.
example {π : Type u} [Category.{v, u} π] {A B C : π}
(f : A βΆ B) [hf : IsRetraction f] (g : B βΆ C) [hg : IsRetraction g]
: IsRetraction (g β f) := instIsSplitMonoComp
Prove that the composite of two maps, each having sections, has itself a section.
Solution: Exercise 8
The section of the composite is the composite of the sections in the opposite order (cf. Proposition 3).
example {π : Type u} [Category.{v, u} π] {A B C : π}
(f : A βΆ B) [hf : IsSection f] (g : B βΆ C) [hg : IsSection g]
: IsSection (g β f) := by π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bhf:IsSection fg:B βΆ Chg:IsSection gβ’ IsSection (g β f)
obtain β¨sβ, hfβ© := hf π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Chg:IsSection gsβ:B βΆ Ahf:f β sβ = π Bβ’ IsSection (g β f)
obtain β¨sβ, hgβ© := hg π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Csβ:B βΆ Ahf:f β sβ = π Bsβ:C βΆ Bhg:g β sβ = π Cβ’ IsSection (g β f)
use sβ β sβ id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Csβ:B βΆ Ahf:f β sβ = π Bsβ:C βΆ Bhg:g β sβ = π Cβ’ autoParam ((g β f) β sβ β sβ = π C) SplitEpi.id._autoParam
change (g β f) β (sβ β sβ) = π C id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Csβ:B βΆ Ahf:f β sβ = π Bsβ:C βΆ Bhg:g β sβ = π Cβ’ (g β f) β sβ β sβ = π C
rw [Category.assoc, id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Csβ:B βΆ Ahf:f β sβ = π Bsβ:C βΆ Bhg:g β sβ = π Cβ’ ((g β f) β sβ) β sβ = π C β Category.assoc sβ id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Csβ:B βΆ Ahf:f β sβ = π Bsβ:C βΆ Bhg:g β sβ = π Cβ’ (g β f β sβ) β sβ = π C] id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Csβ:B βΆ Ahf:f β sβ = π Bsβ:C βΆ Bhg:g β sβ = π Cβ’ (g β f β sβ) β sβ = π C
rw [hf id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Csβ:B βΆ Ahf:f β sβ = π Bsβ:C βΆ Bhg:g β sβ = π Cβ’ (g β π B) β sβ = π C] id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Csβ:B βΆ Ahf:f β sβ = π Bsβ:C βΆ Bhg:g β sβ = π Cβ’ (g β π B) β sβ = π C
rw [Category.id_comp id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Csβ:B βΆ Ahf:f β sβ = π Bsβ:C βΆ Bhg:g β sβ = π Cβ’ g β sβ = π C] id π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Csβ:B βΆ Ahf:f β sβ = π Bsβ:C βΆ Bhg:g β sβ = π Cβ’ g β sβ = π C
exact hg All goals completed! π
We note that the corresponding mathlib instance is instIsSplitEpiComp.
example {π : Type u} [Category.{v, u} π] {A B C : π}
(f : A βΆ B) [hf : IsSection f] (g : B βΆ C) [hg : IsSection g]
: IsSection (g β f) := instIsSplitEpiComp
An endomap e is called idempotent if {e \circ e = e}.
We implement Idempotent and IsIdempotent in Lean as follows:
structure Idempotent {π : Type u} [Category.{v, u} π] (A : π) where
e : A βΆ A
idem : e β e = e
class IsIdempotent {π : Type u} [Category.{v, u} π] {A : π}
(e : A βΆ A) where
idem : e β e = e
Suppose r is a retraction of f (equivalently f is a section of r) and let {e = f \circ r}. Show that e is an idempotent.... Show that if f is an isomorphism, then e is the identity.
Solution: Exercise 9
variable {π : Type u} [Category.{v, u} π] {A B : π}
(f : A βΆ B) (e : B βΆ B)
We show that e is an idempotent.
example (r : Retraction f) (he : e = f β r.retraction)
: IsIdempotent e := {
idem := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Br:Retraction fhe:e = f β r.retractionβ’ e β e = e
rw [he, π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Br:Retraction fhe:e = f β r.retractionβ’ (f β r.retraction) β f β r.retraction = f β r.retraction Category.assoc, π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Br:Retraction fhe:e = f β r.retractionβ’ ((f β r.retraction) β f) β r.retraction = f β r.retraction β Category.assoc f, π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Br:Retraction fhe:e = f β r.retractionβ’ (f β r.retraction β f) β r.retraction = f β r.retraction r.id, π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Br:Retraction fhe:e = f β r.retractionβ’ (f β π A) β r.retraction = f β r.retraction
Category.id_comp π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Br:Retraction fhe:e = f β r.retractionβ’ f β r.retraction = f β r.retraction] All goals completed! π
}
We show that e is the identity if f is an isomorphism.
example [hf : IsIso f]
(r : Retraction f) (he : e = f β r.retraction)
: e = π B := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionβ’ e = π B
have β¨finv, hfinvβ© := hf π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ e = π B
rw [β hfinv.2, π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ e = f β finv β Category.id_comp f, π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ e = (f β π A) β finv β r.id π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ e = (f β r.retraction β f) β finv] π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ e = (f β r.retraction β f) β finv
repeat rw [β Category.assoc π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ e = f β (r.retraction β f) β finv] π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ e = f β (r.retraction β f) β finv π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ e = f β r.retraction β f β finv
rwa [hfinv.2, π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ e = f β r.retraction β π B Category.id_comp π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ e = f β r.retraction] π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Be:B βΆ Bhf:IsIso fr:Retraction fhe:e = f β r.retractionfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ e = f β r.retraction
If f has both a retraction r and a section s then {r = s}.
From the definition we have, if {A \xrightarrow{f} B}, both of the equations
r \circ f = 1_A \quad\text{and}\quad f \circ s = 1_B.
Then by the identity laws and the associative law
r = r \circ 1_B = r \circ (f \circ s) = (r \circ f) \circ s = 1_A \circ s = s.
Our implementation in Lean faithfully follows the argument of the book proof given above.
theorem uniqueness_of_inverses {π : Type u} [Category.{v, u} π]
{A B : π} (f : A βΆ B) (r : Retraction f) (s : Section f)
: r.retraction = s.section_ := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fβ’ r.retraction = s.section_
obtain β¨r, hrβ© := r π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bs:Section fr:B βΆ Ahr:r β f = π Aβ’ { retraction := r, id := hr }.retraction = s.section_
obtain β¨s, hsβ© := s π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ { retraction := r, id := hr }.retraction = { section_ := s, id := hs }.section_
change r = s π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r = s
calc
r = r β π B := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r = r β π B rw [Category.id_comp π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r = r] All goals completed! π
_ = r β (f β s) := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r β π B = r β f β s rw [hs π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r β π B = r β π B] All goals completed! π
_ = (r β f) β s := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r β f β s = (r β f) β s rw [β Category.assoc π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r β f β s = r β f β s] All goals completed! π
_ = π A β s := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ (r β f) β s = π A β s rw [β hr π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ (r β f) β s = (r β f) β s] All goals completed! π
_ = s := Category.comp_id s
4. Isomorphisms and automorphisms
A map {A \xrightarrow{f} B} is called an isomorphism if there exists another map {B \xrightarrow{f^{-1}} A} which is both a retraction and a section for f:
f \circ fβ»ΒΉ = 1_B,\\\
fβ»ΒΉ \circ f = 1_A.
Such a map f^{-1} is called the inverse map for f; since both of the two equations are required, the theorem of uniqueness of inverses shows that there is only one inverse.
We compare these definitions of isomorphism and inverse with the earlier definitions on p. 40. A proof that the two definitions of isomorphism are equivalent is given below.
example {π : Type u} [Category.{v, u} π] {A B : π}
(f : A βΆ B) (r : Retraction f) (s : Section f)
: r.retraction = s.section_ β IsIso f := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fβ’ r.retraction = s.section_ β IsIso f
constructor mp π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fβ’ r.retraction = s.section_ β IsIso fmpr π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fβ’ IsIso f β r.retraction = s.section_
Β· mp π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fβ’ r.retraction = s.section_ β IsIso f intro h mp π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fh:r.retraction = s.section_β’ IsIso f
exact {
out := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fh:r.retraction = s.section_β’ β inv, inv β f = π A β§ f β inv = π B
use r.retraction h π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fh:r.retraction = s.section_β’ r.retraction β f = π A β§ f β r.retraction = π B
constructor h.left π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fh:r.retraction = s.section_β’ r.retraction β f = π Ah.right π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fh:r.retraction = s.section_β’ f β r.retraction = π B
Β· h.left π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fh:r.retraction = s.section_β’ r.retraction β f = π A exact r.id All goals completed! π
Β· h.right π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fh:r.retraction = s.section_β’ f β r.retraction = π B rw [h h.right π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fh:r.retraction = s.section_β’ f β s.section_ = π B] h.right π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fh:r.retraction = s.section_β’ f β s.section_ = π B
exact s.id All goals completed! π
}
Β· mpr π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section fβ’ IsIso f β r.retraction = s.section_ rintro β¨finv, hfinvβ© mpr π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Br:Retraction fs:Section ffinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ r.retraction = s.section_
obtain β¨r, hrβ© := r mpr π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bs:Section ffinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Br:B βΆ Ahr:r β f = π Aβ’ { retraction := r, id := hr }.retraction = s.section_
obtain β¨s, hsβ© := s mpr π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ { retraction := r, id := hr }.retraction = { section_ := s, id := hs }.section_
change r = s mpr π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r = s
calc
r = r β π B := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r = r β π B rw [Category.id_comp π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r = r] All goals completed! π
_ = r β (f β s) := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r β π B = r β f β s rw [hs π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r β π B = r β π B] All goals completed! π
_ = (r β f) β s := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r β f β s = (r β f) β s rw [β Category.assoc π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ r β f β s = r β f β s] All goals completed! π
_ = π A β s := by π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ (r β f) β s = π A β s rw [β hr π:Type uinstβ:Category.{v, u} πA:πB:πf:A βΆ Bfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Br:B βΆ Ahr:r β f = π As:B βΆ Ahs:f β s = π Bβ’ (r β f) β s = (r β f) β s] All goals completed! π
_ = s := Category.comp_id s
When working with inverse maps in Excercise 10, we make use of mathlib's CategoryTheory.inv, which we print below for reference.
#print CategoryTheory.inv
If {A \xrightarrow{f} B \xrightarrow{g} C} are both isomorphisms, then {g \circ f} is an isomorphism too, and {(g \circ f)^{-1} = f^{-1} \circ g^{-1}}.
Solution: Exercise 10
The inverse of the composite is the composite of the inverses in the opposite order.
open CategoryTheory in
example {π : Type u} [Category.{v, u} π] {A B C : π}
(f : A βΆ B) [hf : IsIso f] (g : B βΆ C) [hg : IsIso g]
: IsIso (g β f) β§ inv (g β f) = inv f β inv g := by π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bhf:IsIso fg:B βΆ Chg:IsIso gβ’ IsIso (g β f) β§ inv (g β f) = inv f β inv g
constructor left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bhf:IsIso fg:B βΆ Chg:IsIso gβ’ IsIso (g β f)right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bhf:IsIso fg:B βΆ Chg:IsIso gβ’ inv (g β f) = inv f β inv g
Β· left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bhf:IsIso fg:B βΆ Chg:IsIso gβ’ IsIso (g β f) obtain β¨finv, hfinvβ© := hf left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Chg:IsIso gfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bβ’ IsIso (g β f)
obtain β¨ginv, hginvβ© := hg left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ IsIso (g β f)
exact {
out := by π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ β inv, inv β g β f = π A β§ (g β f) β inv = π C
use finv β ginv h π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (finv β ginv) β g β f = π A β§ (g β f) β finv β ginv = π C
constructor h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (finv β ginv) β g β f = π Ah.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (g β f) β finv β ginv = π C
Β· h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (finv β ginv) β g β f = π A rw [Category.assoc, h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ ((finv β ginv) β g) β f = π A β Category.assoc g h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (finv β ginv β g) β f = π A] h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (finv β ginv β g) β f = π A
rw [hginv.1 h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (finv β π B) β f = π A] h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (finv β π B) β f = π A
rw [Category.id_comp h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ finv β f = π A] h.left π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ finv β f = π A
exact hfinv.1 All goals completed! π
Β· h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (g β f) β finv β ginv = π C rw [Category.assoc, h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ ((g β f) β finv) β ginv = π C β Category.assoc finv h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (g β f β finv) β ginv = π C] h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (g β f β finv) β ginv = π C
rw [hfinv.2 h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (g β π B) β ginv = π C] h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ (g β π B) β ginv = π C
rw [Category.id_comp h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ g β ginv = π C] h.right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bg:B βΆ Cfinv:B βΆ Ahfinv:finv β f = π A β§ f β finv = π Bginv:C βΆ Bhginv:ginv β g = π B β§ g β ginv = π Cβ’ g β ginv = π C
exact hginv.2 All goals completed! π
}
Β· right π:Type uinstβ:Category.{v, u} πA:πB:πC:πf:A βΆ Bhf:IsIso fg:B βΆ Chg:IsIso gβ’ inv (g β f) = inv f β inv g exact IsIso.inv_comp All goals completed! π
If {A = \{\mathit{Fatima}, \mathit{Omer}, \mathit{Alysia}\}} and {B = \{\mathit{coffee}, \mathit{tea}, \mathit{cocoa}\}}, find an example of an isomorphism {A \xrightarrow{f} B}. If {C = \{\mathit{true}, \mathit{false}\}}, can you find any isomorphism {A \rightarrow C}?
Solution: Exercise 11
namespace ExII_11
For convenience, we use finite types here instead of finite sets.
set_option backward.isDefEq.respectTransparency false in
inductive A
| Fatima | Omer | Alysia
deriving Fintype
set_option backward.isDefEq.respectTransparency false in
inductive B
| coffee | tea | cocoa
deriving Fintype
We give a map f and its inverse f^{-1} below, along with a proof that f is an isomorphism.
def f : A βΆ B := βΎfun
| A.Fatima => B.coffee
| A.Omer => B.tea
| A.Alysia => B.cocoa
def finv : B βΆ A := βΎfun
| B.coffee => A.Fatima
| B.tea => A.Omer
| B.cocoa => A.Alysia
example : IsIso f := {
out := by β’ β inv, inv β f = π A β§ f β inv = π B
use finv h β’ finv β f = π A β§ f β finv = π B
constructor h.left β’ finv β f = π Ah.right β’ f β finv = π B
all_goals
ext x h.right x:Bβ’ (ConcreteCategory.hom (f β finv)).toFun x = (ConcreteCategory.hom (π B)).toFun x
fin_cases x h.right.Β«0Β» β’ (ConcreteCategory.hom (f β finv)).toFun B.coffee = (ConcreteCategory.hom (π B)).toFun B.coffeeh.right.Β«1Β» β’ (ConcreteCategory.hom (f β finv)).toFun B.tea = (ConcreteCategory.hom (π B)).toFun B.teah.right.Β«2Β» β’ (ConcreteCategory.hom (f β finv)).toFun B.cocoa = (ConcreteCategory.hom (π B)).toFun B.cocoa <;> h.right.Β«0Β» β’ (ConcreteCategory.hom (f β finv)).toFun B.coffee = (ConcreteCategory.hom (π B)).toFun B.coffeeh.right.Β«1Β» β’ (ConcreteCategory.hom (f β finv)).toFun B.tea = (ConcreteCategory.hom (π B)).toFun B.teah.right.Β«2Β» β’ (ConcreteCategory.hom (f β finv)).toFun B.cocoa = (ConcreteCategory.hom (π B)).toFun B.cocoa dsimp [f, finv] All goals completed! π
}
end ExII_11
Since {\#A > \#C}, there can be no pair {A \xrightarrow{j} C}, {C \xrightarrow{p} A} such that {p \circ j = 1_A}; hence there is no isomorphism {A \rightarrow C}.
A map which is both an endomap and at the same time an isomorphism is usually called by the one word automorphism.
The corresponding mathlib definition is Aut, which we print below for reference.
#print Aut
Compare this to the mathlib definition End for endomorphisms of an object in a category.
#print End
How many isomorphisms are there from {A = \{\mathit{Fatima}, \mathit{Omer}, \mathit{Alysia}\}} to {B = \{\mathit{coffee}, \mathit{tea}, \mathit{cocoa}\}}? How many automorphisms of A are there? The answers should be less than 27 β why?
Solution: Exercise 12
Provided two sets/types have the same number n of elements, the number of isomorphisms between them is n!; if the sets/types have different numbers of elements, then there are no isomorphisms between them. We implement this formula in Lean as follows:
def isoCount (Ξ± Ξ² : Type*) [Fintype Ξ±] [Fintype Ξ²] : β :=
if Fintype.card Ξ± = Fintype.card Ξ² then
Nat.factorial (Fintype.card Ξ±)
else
0
By the formula above, we have 6 different isomorphisms.
open ExII_11
#eval isoCount A B
Essentially the same formula applies to automorphisms, since an automorphism is just an isomorphism from a set/type to itself. Thus, there are also 6 different automorphisms of A.
abbrev autCount (Ξ± : Type*) [Fintype Ξ±] := isoCount Ξ± Ξ±
open ExII_11
#eval autCount A
By Alysia's formula, {3^3 = 27} is the number of distinct maps {A \rightarrow B} (or {A \rightarrow A}), so the number of isomorphisms between A and B (or automorphisms of A) must be less than 27.
An automorphism in the category of sets is also traditionally called a permutation, suggesting that it shifts the elements of its set around in a specified way.
Repeating the second part of Exercise 12, now using sets instead of types, we have
def permCount {Ξ± : Type*} (s : Finset Ξ±) : β :=
if 0 < Finset.card s then
Nat.factorial (Finset.card s)
else
0
open ExII_11
#eval permCount (Finset.univ (Ξ± := A))