A Lean Companion to Conceptual Mathematics

Session 27: Examples of universal constructionsπŸ”—

2. Can objects have negatives?πŸ”—

Exercise 1 (p. 288)

Prove that if A and B are objects and {A \times B = \mathbf{1}}, then {A = B = \mathbf{1}}. More precisely, if \mathbf{1} is terminal and A \xleftarrow{p_1} \mathbf{1} \xrightarrow{p_2} B is a product, then A and B are terminal objects.

Solution: Exercise 1

To prove that A and B are terminal, we construct two binary fans over A and B, one with vertex A and the other with vertex B. The universal property of the product yields a unique map from each vertex to the limit \mathbf{1}. We then use the universal properties of product and terminal object to show that these maps form isomorphisms.

example {π’ž : Type u} [Category.{v, u} π’ž] [HasTerminal π’ž] (A B : π’ž) (p₁ : ⊀_ π’ž ⟢ A) (pβ‚‚ : ⊀_ π’ž ⟢ B) (P : IsLimit (BinaryFan.mk p₁ pβ‚‚)) : Nonempty (A β‰… ⊀_ π’ž) ∧ Nonempty (B β‰… ⊀_ π’ž) := π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žA:π’žB:π’žp₁:⊀_ π’ž ⟢ Apβ‚‚:⊀_ π’ž ⟢ BP:IsLimit (BinaryFan.mk p₁ pβ‚‚)⊒ Nonempty (A β‰… ⊀_ π’ž) ∧ Nonempty (B β‰… ⊀_ π’ž) π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žA:π’žB:π’žp₁:⊀_ π’ž ⟢ Apβ‚‚:⊀_ π’ž ⟢ BP:IsLimit (BinaryFan.mk p₁ pβ‚‚)⊒ Nonempty (A β‰… ⊀_ π’ž)π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žA:π’žB:π’žp₁:⊀_ π’ž ⟢ Apβ‚‚:⊀_ π’ž ⟢ BP:IsLimit (BinaryFan.mk p₁ pβ‚‚)⊒ Nonempty (B β‰… ⊀_ π’ž) π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žA:π’žB:π’žp₁:⊀_ π’ž ⟢ Apβ‚‚:⊀_ π’ž ⟢ BP:IsLimit (BinaryFan.mk p₁ pβ‚‚)⊒ Nonempty (A β‰… ⊀_ π’ž)π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žA:π’žB:π’žp₁:⊀_ π’ž ⟢ Apβ‚‚:⊀_ π’ž ⟢ BP:IsLimit (BinaryFan.mk p₁ pβ‚‚)⊒ Nonempty (B β‰… ⊀_ π’ž) π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žA:π’žB:π’žp₁:⊀_ π’ž ⟢ Apβ‚‚:⊀_ π’ž ⟢ BP:IsLimit (BinaryFan.mk p₁ pβ‚‚)⊒ B β‰… ⊀_ π’ž π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žA:π’žB:π’žp₁:⊀_ π’ž ⟢ Apβ‚‚:⊀_ π’ž ⟢ BP:IsLimit (BinaryFan.mk p₁ pβ‚‚)⊒ A β‰… ⊀_ π’ž π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žA:π’žB:π’žp₁:⊀_ π’ž ⟢ Apβ‚‚:⊀_ π’ž ⟢ BP:IsLimit (BinaryFan.mk p₁ pβ‚‚)fanA:BinaryFan A B := BinaryFan.mk (πŸ™ A) (pβ‚‚ ⊚ terminal.from A)⊒ A β‰… ⊀_ π’ž All goals completed! πŸ™ π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žA:π’žB:π’žp₁:⊀_ π’ž ⟢ Apβ‚‚:⊀_ π’ž ⟢ BP:IsLimit (BinaryFan.mk p₁ pβ‚‚)⊒ B β‰… ⊀_ π’ž π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žA:π’žB:π’žp₁:⊀_ π’ž ⟢ Apβ‚‚:⊀_ π’ž ⟢ BP:IsLimit (BinaryFan.mk p₁ pβ‚‚)fanB:BinaryFan A B := BinaryFan.mk (p₁ ⊚ terminal.from B) (πŸ™ B)⊒ B β‰… ⊀_ π’ž All goals completed! πŸ™

3. Idempotent objectsπŸ”—

Exercise 2 (p. 290)

(a) Show that if C has the property that for each X there is at most one map {X \rightarrow C}, then C \xleftarrow{1_C} C \xrightarrow{1_C} C is a product.

(b) Show that the property above is also equivalent to the following property: The unique map {C \rightarrow \mathbf{1}} is a monomorphism.

Solution: Exercise 2

Since in mathlib the Subsingleton type class represents a type with at most one element, we can use Subsingleton in both parts of the exercise to formalise the property that for each X there is at most one map {X \rightarrow C}.

For part (a), we have

example {π’ž : Type u} [Category.{v, u} π’ž] (C : π’ž) (h : βˆ€ X : π’ž, Subsingleton (X ⟢ C)) : IsLimit (BinaryFan.mk (πŸ™ C) (πŸ™ C)) := { lift s := BinaryFan.fst s fac s := fun ⟨j⟩ ↦ π’ž:Type uinst✝:Category.{v, u} π’žC:π’žh:βˆ€ (X : π’ž), Subsingleton (X ⟢ C)s:Cone (pair C C)x✝:Discrete WalkingPairj:WalkingPair⊒ (BinaryFan.mk (πŸ™ C) (πŸ™ C)).Ο€.app { as := j } ⊚ BinaryFan.fst s = s.Ο€.app { as := j } π’ž:Type uinst✝:Category.{v, u} π’žC:π’žh:βˆ€ (X : π’ž), Subsingleton (X ⟢ C)s:Cone (pair C C)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ C) (πŸ™ C)).Ο€.app { as := WalkingPair.left } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.left }π’ž:Type uinst✝:Category.{v, u} π’žC:π’žh:βˆ€ (X : π’ž), Subsingleton (X ⟢ C)s:Cone (pair C C)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ C) (πŸ™ C)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.right } all_goals π’ž:Type uinst✝:Category.{v, u} π’žC:π’žh:βˆ€ (X : π’ž), Subsingleton (X ⟢ C)s:Cone (pair C C)x✝:Discrete WalkingPair⊒ πŸ™ C ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.right } All goals completed! πŸ™ uniq s m _ := π’ž:Type uinst✝:Category.{v, u} π’žC:π’žh:βˆ€ (X : π’ž), Subsingleton (X ⟢ C)s:Cone (pair C C)m:s.pt ⟢ (BinaryFan.mk (πŸ™ C) (πŸ™ C)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ C) (πŸ™ C)).Ο€.app j ⊚ m = s.Ο€.app j⊒ m = BinaryFan.fst s π’ž:Type uinst✝:Category.{v, u} π’žC:π’žh:βˆ€ (X : π’ž), Subsingleton (X ⟢ C)s:Cone (pair C C)m:s.pt ⟢ (BinaryFan.mk (πŸ™ C) (πŸ™ C)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ C) (πŸ™ C)).Ο€.app j ⊚ m = s.Ο€.app j⊒ m = BinaryFan.fst s All goals completed! πŸ™ }

and for part (b), we have

example {π’ž : Type u} [Category.{v, u} π’ž] [HasTerminal π’ž] (C : π’ž) : (βˆ€ X : π’ž, Subsingleton (X ⟢ C)) ↔ Mono (terminal.from C) := π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žC:π’žβŠ’ (βˆ€ (X : π’ž), Subsingleton (X ⟢ C)) ↔ Mono (terminal.from C) π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žC:π’žβŠ’ (βˆ€ (X : π’ž), Subsingleton (X ⟢ C)) β†’ Mono (terminal.from C)π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žC:π’žβŠ’ Mono (terminal.from C) β†’ βˆ€ (X : π’ž), Subsingleton (X ⟢ C) π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žC:π’žβŠ’ (βˆ€ (X : π’ž), Subsingleton (X ⟢ C)) β†’ Mono (terminal.from C) π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žC:π’ža✝:βˆ€ (X : π’ž), Subsingleton (X ⟢ C)⊒ Mono (terminal.from C) All goals completed! πŸ™ π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žC:π’žβŠ’ Mono (terminal.from C) β†’ βˆ€ (X : π’ž), Subsingleton (X ⟢ C) π’ž:Type uinst✝¹:Category.{v, u} π’žinst✝:HasTerminal π’žC:π’žh:Mono (terminal.from C)X:π’žβŠ’ Subsingleton (X ⟢ C) All goals completed! πŸ™
Exercise 3 (p. 291)

Find all objects C in 𝑺, 𝑺↻, and π‘Ίβ‡Š such that this is a product: C \xleftarrow{1_C} C \xrightarrow{1_C} C

Solution: Exercise 3

In 𝑺, C must either be empty or have a single elementβ€”i.e., C must be a Subsingleton type.

example (C : Type) : Subsingleton C β†’ IsLimit (BinaryFan.mk (πŸ™ C) (πŸ™ C)) := C:Type⊒ Subsingleton C β†’ IsLimit (BinaryFan.mk (πŸ™ C) (πŸ™ C)) C:Typea✝:Subsingleton C⊒ IsLimit (BinaryFan.mk (πŸ™ C) (πŸ™ C)) exact { lift s := BinaryFan.fst s fac s := fun ⟨j⟩ ↦ C:Typea✝:Subsingleton Cs:Cone (pair C C)x✝:Discrete WalkingPairj:WalkingPair⊒ (BinaryFan.mk (πŸ™ C) (πŸ™ C)).Ο€.app { as := j } ⊚ BinaryFan.fst s = s.Ο€.app { as := j } C:Typea✝:Subsingleton Cs:Cone (pair C C)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ C) (πŸ™ C)).Ο€.app { as := WalkingPair.left } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.left }C:Typea✝:Subsingleton Cs:Cone (pair C C)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ C) (πŸ™ C)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.right } all_goals C:Typea✝:Subsingleton Cs:Cone (pair C C)x✝:Discrete WalkingPair⊒ πŸ™ C ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.right } C:Typea✝:Subsingleton Cs:Cone (pair C C)x✝:Discrete WalkingPairx:s.pt⊒ (ConcreteCategory.hom (πŸ™ C ⊚ BinaryFan.fst s)).toFun x = (ConcreteCategory.hom (s.Ο€.app { as := WalkingPair.right })).toFun x All goals completed! πŸ™ uniq s m _ := C:Typea✝:Subsingleton Cs:Cone (pair C C)m:s.pt ⟢ (BinaryFan.mk (πŸ™ C) (πŸ™ C)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ C) (πŸ™ C)).Ο€.app j ⊚ m = s.Ο€.app j⊒ m = BinaryFan.fst s C:Typea✝:Subsingleton Cs:Cone (pair C C)m:s.pt ⟢ (BinaryFan.mk (πŸ™ C) (πŸ™ C)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ C) (πŸ™ C)).Ο€.app j ⊚ m = s.Ο€.app jx:s.pt⊒ (ConcreteCategory.hom m).toFun x = (ConcreteCategory.hom (BinaryFan.fst s)).toFun x All goals completed! πŸ™ }

In 𝑺↻, C must either be empty or have a single element with the identity map. (We re-use relevant definitions from Article IV.)

-- Empty example : IsLimit (BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)) := ⊒ IsLimit (BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)) exact { lift s := BinaryFan.fst s fac s := fun ⟨j⟩ ↦ s:Cone (pair emptySWE emptySWE)x✝:Discrete WalkingPairj:WalkingPair⊒ (BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)).Ο€.app { as := j } ⊚ BinaryFan.fst s = s.Ο€.app { as := j } s:Cone (pair emptySWE emptySWE)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)).Ο€.app { as := WalkingPair.left } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.left }s:Cone (pair emptySWE emptySWE)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.right } all_goals s:Cone (pair emptySWE emptySWE)x✝:Discrete WalkingPair⊒ βˆ€ (x : s.pt.carrier), (ConcreteCategory.hom ((BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)) x = (ConcreteCategory.hom (s.Ο€.app { as := WalkingPair.right })) x s:Cone (pair emptySWE emptySWE)x✝:Discrete WalkingPairx:s.pt.carrier⊒ (ConcreteCategory.hom ((BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)) x = (ConcreteCategory.hom (s.Ο€.app { as := WalkingPair.right })) x All goals completed! πŸ™ uniq s m _ := s:Cone (pair emptySWE emptySWE)m:s.pt ⟢ (BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)).Ο€.app j ⊚ m = s.Ο€.app j⊒ m = BinaryFan.fst s s:Cone (pair emptySWE emptySWE)m:s.pt ⟢ (BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)).Ο€.app j ⊚ m = s.Ο€.app j⊒ βˆ€ (x : s.pt.carrier), (ConcreteCategory.hom m) x = (ConcreteCategory.hom (BinaryFan.fst s)) x s:Cone (pair emptySWE emptySWE)m:s.pt ⟢ (BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ emptySWE) (πŸ™ emptySWE)).Ο€.app j ⊚ m = s.Ο€.app jx:s.pt.carrier⊒ (ConcreteCategory.hom m) x = (ConcreteCategory.hom (BinaryFan.fst s)) x All goals completed! πŸ™ } -- Single element with identity map (terminal object in 𝑺↻) example : IsLimit (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)) := ⊒ IsLimit (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)) exact { lift s := BinaryFan.fst s fac s := fun ⟨j⟩ ↦ s:Cone (pair termSWE termSWE)x✝:Discrete WalkingPairj:WalkingPair⊒ (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)).Ο€.app { as := j } ⊚ BinaryFan.fst s = s.Ο€.app { as := j } s:Cone (pair termSWE termSWE)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)).Ο€.app { as := WalkingPair.left } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.left }s:Cone (pair termSWE termSWE)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.right } s:Cone (pair termSWE termSWE)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)).Ο€.app { as := WalkingPair.left } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.left }s:Cone (pair termSWE termSWE)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.right } All goals completed! πŸ™ uniq s m _ := s:Cone (pair termSWE termSWE)m:s.pt ⟢ (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)).Ο€.app j ⊚ m = s.Ο€.app j⊒ m = BinaryFan.fst s s:Cone (pair termSWE termSWE)m:s.pt ⟢ (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)).Ο€.app j ⊚ m = s.Ο€.app j⊒ βˆ€ (x : s.pt.carrier), (ConcreteCategory.hom m) x = (ConcreteCategory.hom (BinaryFan.fst s)) x s:Cone (pair termSWE termSWE)m:s.pt ⟢ (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ termSWE) (πŸ™ termSWE)).Ο€.app j ⊚ m = s.Ο€.app jx:s.pt.carrier⊒ (ConcreteCategory.hom m) x = (ConcreteCategory.hom (BinaryFan.fst s)) x All goals completed! πŸ™ }

In π‘Ίβ‡Š, C must either be the empty graph, a 'naked dot', or a single dot with one looping arrow. (We again re-use relevant definitions from Article IV.)

-- Empty graph example : IsLimit (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)) := ⊒ IsLimit (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)) exact { lift s := BinaryFan.fst s fac s := fun ⟨j⟩ ↦ s:Cone (pair emptyIG emptyIG)x✝:Discrete WalkingPairj:WalkingPair⊒ (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app { as := j } ⊚ BinaryFan.fst s = s.Ο€.app { as := j } s:Cone (pair emptyIG emptyIG)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app { as := WalkingPair.left } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.left }s:Cone (pair emptyIG emptyIG)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.right } all_goals s:Cone (pair emptyIG emptyIG)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).1 = (↑(s.Ο€.app { as := WalkingPair.right })).1s:Cone (pair emptyIG emptyIG)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).2 = (↑(s.Ο€.app { as := WalkingPair.right })).2 s:Cone (pair emptyIG emptyIG)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).1 = (↑(s.Ο€.app { as := WalkingPair.right })).1s:Cone (pair emptyIG emptyIG)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).2 = (↑(s.Ο€.app { as := WalkingPair.right })).2 s:Cone (pair emptyIG emptyIG)x✝:Discrete WalkingPairx:s.pt.carrierD⊒ (ConcreteCategory.hom (↑((BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).2).toFun x = (ConcreteCategory.hom (↑(s.Ο€.app { as := WalkingPair.right })).2).toFun x s:Cone (pair emptyIG emptyIG)x✝:Discrete WalkingPairx:s.pt.carrierA⊒ (ConcreteCategory.hom (↑((BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).1).toFun x = (ConcreteCategory.hom (↑(s.Ο€.app { as := WalkingPair.right })).1).toFun x All goals completed! πŸ™ s:Cone (pair emptyIG emptyIG)x✝:Discrete WalkingPairx:s.pt.carrierD⊒ (ConcreteCategory.hom (↑((BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).2).toFun x = (ConcreteCategory.hom (↑(s.Ο€.app { as := WalkingPair.right })).2).toFun x All goals completed! πŸ™ uniq s m _ := s:Cone (pair emptyIG emptyIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app j ⊚ m = s.Ο€.app j⊒ m = BinaryFan.fst s s:Cone (pair emptyIG emptyIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).1 = (↑(BinaryFan.fst s)).1s:Cone (pair emptyIG emptyIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).2 = (↑(BinaryFan.fst s)).2 s:Cone (pair emptyIG emptyIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).1 = (↑(BinaryFan.fst s)).1s:Cone (pair emptyIG emptyIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).2 = (↑(BinaryFan.fst s)).2 s:Cone (pair emptyIG emptyIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app j ⊚ m = s.Ο€.app jx:s.pt.carrierD⊒ (ConcreteCategory.hom (↑m).2).toFun x = (ConcreteCategory.hom (↑(BinaryFan.fst s)).2).toFun x s:Cone (pair emptyIG emptyIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app j ⊚ m = s.Ο€.app jx:s.pt.carrierA⊒ (ConcreteCategory.hom (↑m).1).toFun x = (ConcreteCategory.hom (↑(BinaryFan.fst s)).1).toFun x All goals completed! πŸ™ s:Cone (pair emptyIG emptyIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ emptyIG) (πŸ™ emptyIG)).Ο€.app j ⊚ m = s.Ο€.app jx:s.pt.carrierD⊒ (ConcreteCategory.hom (↑m).2).toFun x = (ConcreteCategory.hom (↑(BinaryFan.fst s)).2).toFun x All goals completed! πŸ™ } -- Naked dot open IrreflexiveGraph in example : IsLimit (BinaryFan.mk (πŸ™ D) (πŸ™ D)) := ⊒ IsLimit (BinaryFan.mk (πŸ™ D) (πŸ™ D)) exact { lift s := BinaryFan.fst s fac s := fun ⟨j⟩ ↦ s:Cone (pair D D)x✝:Discrete WalkingPairj:WalkingPair⊒ (BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app { as := j } ⊚ BinaryFan.fst s = s.Ο€.app { as := j } s:Cone (pair D D)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app { as := WalkingPair.left } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.left }s:Cone (pair D D)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.right } all_goals s:Cone (pair D D)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).1 = (↑(s.Ο€.app { as := WalkingPair.right })).1s:Cone (pair D D)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).2 = (↑(s.Ο€.app { as := WalkingPair.right })).2 s:Cone (pair D D)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).1 = (↑(s.Ο€.app { as := WalkingPair.right })).1s:Cone (pair D D)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).2 = (↑(s.Ο€.app { as := WalkingPair.right })).2 s:Cone (pair D D)x✝:Discrete WalkingPairx:s.pt.carrierD⊒ (ConcreteCategory.hom (↑((BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).2).toFun x = (ConcreteCategory.hom (↑(s.Ο€.app { as := WalkingPair.right })).2).toFun x s:Cone (pair D D)x✝:Discrete WalkingPairx:s.pt.carrierA⊒ (ConcreteCategory.hom (↑((BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).1).toFun x = (ConcreteCategory.hom (↑(s.Ο€.app { as := WalkingPair.right })).1).toFun x All goals completed! πŸ™ s:Cone (pair D D)x✝:Discrete WalkingPairx:s.pt.carrierD⊒ (ConcreteCategory.hom (↑((BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).2).toFun x = (ConcreteCategory.hom (↑(s.Ο€.app { as := WalkingPair.right })).2).toFun x All goals completed! πŸ™ uniq s m _ := s:Cone (pair D D)m:s.pt ⟢ (BinaryFan.mk (πŸ™ D) (πŸ™ D)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app j ⊚ m = s.Ο€.app j⊒ m = BinaryFan.fst s s:Cone (pair D D)m:s.pt ⟢ (BinaryFan.mk (πŸ™ D) (πŸ™ D)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).1 = (↑(BinaryFan.fst s)).1s:Cone (pair D D)m:s.pt ⟢ (BinaryFan.mk (πŸ™ D) (πŸ™ D)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).2 = (↑(BinaryFan.fst s)).2 s:Cone (pair D D)m:s.pt ⟢ (BinaryFan.mk (πŸ™ D) (πŸ™ D)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).1 = (↑(BinaryFan.fst s)).1s:Cone (pair D D)m:s.pt ⟢ (BinaryFan.mk (πŸ™ D) (πŸ™ D)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).2 = (↑(BinaryFan.fst s)).2 s:Cone (pair D D)m:s.pt ⟢ (BinaryFan.mk (πŸ™ D) (πŸ™ D)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app j ⊚ m = s.Ο€.app jx:s.pt.carrierD⊒ (ConcreteCategory.hom (↑m).2).toFun x = (ConcreteCategory.hom (↑(BinaryFan.fst s)).2).toFun x s:Cone (pair D D)m:s.pt ⟢ (BinaryFan.mk (πŸ™ D) (πŸ™ D)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app j ⊚ m = s.Ο€.app jx:s.pt.carrierA⊒ (ConcreteCategory.hom (↑m).1).toFun x = (ConcreteCategory.hom (↑(BinaryFan.fst s)).1).toFun x All goals completed! πŸ™ s:Cone (pair D D)m:s.pt ⟢ (BinaryFan.mk (πŸ™ D) (πŸ™ D)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ D) (πŸ™ D)).Ο€.app j ⊚ m = s.Ο€.app jx:s.pt.carrierD⊒ (ConcreteCategory.hom (↑m).2).toFun x = (ConcreteCategory.hom (↑(BinaryFan.fst s)).2).toFun x All goals completed! πŸ™ } -- Single dot with one looping arrow (terminal object in π‘Ίβ‡Š) open IrreflexiveGraph in example : IsLimit (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)) := ⊒ IsLimit (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)) exact { lift s := BinaryFan.fst s fac s := fun ⟨j⟩ ↦ s:Cone (pair termIG termIG)x✝:Discrete WalkingPairj:WalkingPair⊒ (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app { as := j } ⊚ BinaryFan.fst s = s.Ο€.app { as := j } s:Cone (pair termIG termIG)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app { as := WalkingPair.left } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.left }s:Cone (pair termIG termIG)x✝:Discrete WalkingPair⊒ (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s = s.Ο€.app { as := WalkingPair.right } all_goals s:Cone (pair termIG termIG)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).1 = (↑(s.Ο€.app { as := WalkingPair.right })).1s:Cone (pair termIG termIG)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).2 = (↑(s.Ο€.app { as := WalkingPair.right })).2 s:Cone (pair termIG termIG)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).1 = (↑(s.Ο€.app { as := WalkingPair.right })).1s:Cone (pair termIG termIG)x✝:Discrete WalkingPair⊒ (↑((BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).2 = (↑(s.Ο€.app { as := WalkingPair.right })).2 (s:Cone (pair termIG termIG)x✝:Discrete WalkingPairx:s.pt.carrierD⊒ (ConcreteCategory.hom (↑((BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app { as := WalkingPair.right } ⊚ BinaryFan.fst s)).2).toFun x = (ConcreteCategory.hom (↑(s.Ο€.app { as := WalkingPair.right })).2).toFun x; All goals completed! πŸ™) uniq s m _ := s:Cone (pair termIG termIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app j ⊚ m = s.Ο€.app j⊒ m = BinaryFan.fst s s:Cone (pair termIG termIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).1 = (↑(BinaryFan.fst s)).1s:Cone (pair termIG termIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).2 = (↑(BinaryFan.fst s)).2 s:Cone (pair termIG termIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).1 = (↑(BinaryFan.fst s)).1s:Cone (pair termIG termIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app j ⊚ m = s.Ο€.app j⊒ (↑m).2 = (↑(BinaryFan.fst s)).2 (s:Cone (pair termIG termIG)m:s.pt ⟢ (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).ptx✝:βˆ€ (j : Discrete WalkingPair), (BinaryFan.mk (πŸ™ termIG) (πŸ™ termIG)).Ο€.app j ⊚ m = s.Ο€.app jx:s.pt.carrierD⊒ (ConcreteCategory.hom (↑m).2).toFun x = (ConcreteCategory.hom (↑(BinaryFan.fst s)).2).toFun x; All goals completed! πŸ™) }
Exercise 4 (p. 292)

The inverse, call it g, of the isomorphism of sets {\mathbb{N} \xrightarrow{f} \mathbb{N} \times \mathbb{N}} above [the Cantor pairing function] is actually given by a quadratic polynomial, of the form g(x, y) = \tfrac{1}{2}(ax^2 + bxy + cy^2 + dx + ey) where a, b, c, d, and e are fixed natural numbers. Can you find them? Can you prove that the map g defined by your formula is an isomorphism of sets? You might expect that f would have a simpler formula than its inverse g, since a map {\mathbb{N} \xrightarrow{f} \mathbb{N} \times \mathbb{N}} amounts to a pair of maps {f_1 = p_1 f} and {f_2 = p_2 f} from \mathbb{N} to \mathbb{N}. But f_1 and f_2 are not so simple. In fact, no matter what isomorphism {\mathbb{N} \xrightarrow{f} \mathbb{N} \times \mathbb{N}} you choose, f_1 cannot be given by a polynomial. Can you see why?

Solution: Exercise 4

Let the pair {(x, y)} be an arbitary element of {\mathbb{N} \times \mathbb{N}}, and let {n = x + y}. Then the total number of pairs in all northwest diagonals strictly preceding the n-th diagonal is the n-th triangular number {T_n = \frac{1}{2}n(n + 1)}. To obtain the exact position of the pair {(x, y)} on the n-th diagonal, we add y to T_n. Thus, the formula for g is g(x, y) = \tfrac{1}{2}(x + y)(x + y + 1) + y = \tfrac{1}{2}(x^2 + 2xy + y^2 + x + 3y).

To prove that g is an isomorphism of sets, we show that g is a bijective function. (We apply the grind tactic liberally in the remaining proofs in this exercise to keep them succinct.)

We begin our proof by defining triangular numbers and the function g.

def tri : β„• β†’ β„• | 0 => 0 | n + 1 => tri n + n + 1 def g : β„• Γ— β„• ⟢ β„• := β†Ύfun (x, y) ↦ tri (x + y) + y

Next we define some helper lemmas.

lemma tri_le_of_le {a b : β„•} (h : a ≀ b) : tri a ≀ tri b := a:β„•b:β„•h:a ≀ b⊒ tri a ≀ tri b a:β„•b:β„•βŠ’ tri a ≀ tri aa:β„•b:β„•m✝:β„•a✝:a.le m✝a_ih✝:tri a ≀ tri m✝⊒ tri a ≀ tri m✝.succ case refl a:β„•b:β„•βŠ’ tri a ≀ tri a All goals completed! πŸ™ case step m _ ih a:β„•b:β„•m:β„•a✝:a.le m✝ih:tri a ≀ tri m✝⊒ tri a ≀ tri m✝.succ All goals completed! πŸ™ lemma g_ubound {x y : β„•} : g (x, y) < tri (x + y + 1) := x:β„•y:β„•βŠ’ (ConcreteCategory.hom g) (x, y) < tri (x + y + 1) x:β„•y:β„•βŠ’ tri (x + y) + y < tri (x + y + 1) All goals completed! πŸ™ lemma g_lbound {x y : β„•} : tri (x + y) ≀ g (x, y) := Nat.le_add_right (tri (x + y)) y lemma eq_of_g_eq {x y x' y' : β„•} (h : g (x, y) = g (x', y')) : x + y = x' + y' := x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')⊒ x + y = x' + y' x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this:tri (x + y) + y = tri (x' + y') + y'⊒ x + y = x' + y' x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this:tri (x + y) + y = tri (x' + y') + y'hlt:x + y < x' + y'⊒ x + y = x' + y'x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this:tri (x + y) + y = tri (x' + y') + y'heq:x + y = x' + y'⊒ x + y = x' + y'x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this:tri (x + y) + y = tri (x' + y') + y'hgt:x' + y' < x + y⊒ x + y = x' + y' x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this:tri (x + y) + y = tri (x' + y') + y'hlt:x + y < x' + y'⊒ x + y = x' + y' x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this✝:tri (x + y) + y = tri (x' + y') + y'hlt:x + y < x' + y'this:tri (x + y) + y < tri (x + y + 1)⊒ x + y = x' + y' x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this✝¹:tri (x + y) + y = tri (x' + y') + y'hlt:x + y < x' + y'this✝:tri (x + y) + y < tri (x + y + 1)this:tri (x' + y') ≀ tri (x' + y') + y'⊒ x + y = x' + y' All goals completed! πŸ™ x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this:tri (x + y) + y = tri (x' + y') + y'heq:x + y = x' + y'⊒ x + y = x' + y' All goals completed! πŸ™ x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this:tri (x + y) + y = tri (x' + y') + y'hgt:x' + y' < x + y⊒ x + y = x' + y' x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this✝:tri (x + y) + y = tri (x' + y') + y'hgt:x' + y' < x + ythis:tri (x' + y') + y' < tri (x' + y' + 1)⊒ x + y = x' + y' x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this✝¹:tri (x + y) + y = tri (x' + y') + y'hgt:x' + y' < x + ythis✝:tri (x' + y') + y' < tri (x' + y' + 1)this:tri (x + y) ≀ tri (x + y) + y⊒ x + y = x' + y' All goals completed! πŸ™ lemma exists_tri_bound (z : β„•) : βˆƒ n : β„•, tri n ≀ z ∧ z < tri (n + 1) := z:β„•βŠ’ βˆƒ n, tri n ≀ z ∧ z < tri (n + 1) induction z with ⊒ βˆƒ n, tri n ≀ 0 ∧ 0 < tri (n + 1) All goals completed! πŸ™ z:β„•ih:βˆƒ n, tri n ≀ z ∧ z < tri (n + 1)⊒ βˆƒ n, tri n ≀ z + 1 ∧ z + 1 < tri (n + 1) All goals completed! πŸ™

Finally we prove that g is an isomorphism of sets.

example : IsIso g := ⊒ IsIso g ⊒ Function.Bijective ⇑(ConcreteCategory.hom g) ⊒ Function.Injective ⇑(ConcreteCategory.hom g)⊒ Function.Surjective ⇑(ConcreteCategory.hom g) ⊒ Function.Injective ⇑(ConcreteCategory.hom g) ⊒ Function.Injective ⇑(ConcreteCategory.hom g) x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')⊒ (x, y) = (x', y') x:β„•y:β„•x':β„•y':β„•h:(ConcreteCategory.hom g) (x, y) = (ConcreteCategory.hom g) (x', y')this:tri (x + y) + y = tri (x' + y') + y'⊒ (x, y) = (x', y') All goals completed! πŸ™ ⊒ Function.Surjective ⇑(ConcreteCategory.hom g) ⊒ Function.Surjective ⇑(ConcreteCategory.hom g) z:β„•βŠ’ βˆƒ a, (ConcreteCategory.hom g) a = z z:β„•w:β„•left✝:tri w ≀ zright✝:z < tri (w + 1)⊒ βˆƒ a, (ConcreteCategory.hom g) a = z z:β„•w:β„•left✝:tri w ≀ zright✝:z < tri (w + 1)⊒ (ConcreteCategory.hom g) (w - (z - tri w), z - tri w) = z z:β„•w:β„•left✝:tri w ≀ zright✝:z < tri (w + 1)⊒ tri (w - (z - tri w) + (z - tri w)) + (z - tri w) = z All goals completed! πŸ™

The final part of the exercise asks us to show that no isomorphism {\mathbb{N} \xrightarrow{f} \mathbb{N} \times \mathbb{N}} can have a polynomial as its first component function f_1.

In the proof below, we assume that such a polynomial P exists and derive a contradiction. Since f is an isomorphism and hence bijective, it maps infinitely many inputs to pairs starting with any given integer k. Therefore P must also evaluate to k infinitely many times. However, a non-constant polynomial can only have a finite number of roots, meaning P must be the constant polynomial {P(x) = k} for any k. Hence P is forced to be simultaneously the constant polynomial 0 and the constant polynomial 1, yielding the impossible result that {0 = 1}.

open Polynomial in example (f : β„• ⟢ β„• Γ— β„•) [IsIso f] : Β¬βˆƒ P : β„€[X], βˆ€ n : β„•, P.eval (n : β„€) = (f n).1 := f:β„• ⟢ β„• Γ— β„•inst✝:IsIso f⊒ Β¬βˆƒ P, βˆ€ (n : β„•), eval (↑n) P = ↑((ConcreteCategory.hom f) n).1 -- Convert isomorphism f to equivalence f' f:β„• ⟢ β„• Γ— β„•inst✝:IsIso ff':β„• ≃ β„• Γ— β„• := (asIso f).toEquiv⊒ Β¬βˆƒ P, βˆ€ (n : β„•), eval (↑n) P = ↑((ConcreteCategory.hom f) n).1 -- Provide translation for grind f:β„• ⟢ β„• Γ— β„•inst✝:IsIso ff':β„• ≃ β„• Γ— β„• := (asIso f).toEquivthis:βˆ€ (n : β„•), (ConcreteCategory.hom f) n = f' n⊒ Β¬βˆƒ P, βˆ€ (n : β„•), eval (↑n) P = ↑((ConcreteCategory.hom f) n).1 f:β„• ⟢ β„• Γ— β„•inst✝:IsIso ff':β„• ≃ β„• Γ— β„• := (asIso f).toEquivthis:βˆ€ (n : β„•), (ConcreteCategory.hom f) n = f' nP:β„€[X]hP:βˆ€ (n : β„•), eval (↑n) P = ↑((ConcreteCategory.hom f) n).1⊒ False -- Show polynomial P must equal constant polynomial C k for any k f:β„• ⟢ β„• Γ— β„•inst✝:IsIso ff':β„• ≃ β„• Γ— β„• := (asIso f).toEquivthis:βˆ€ (n : β„•), (ConcreteCategory.hom f) n = f' nP:β„€[X]hP:βˆ€ (n : β„•), eval (↑n) P = ↑((ConcreteCategory.hom f) n).1h_P_eq_C:βˆ€ (k : β„•), P = C ↑k⊒ False -- Conclude P must equal both 0 and 1, forcing 0 = 1 f:β„• ⟢ β„• Γ— β„•inst✝:IsIso ff':β„• ≃ β„• Γ— β„• := (asIso f).toEquivthis:βˆ€ (n : β„•), (ConcreteCategory.hom f) n = f' nP:β„€[X]hP:βˆ€ (n : β„•), eval (↑n) P = ↑((ConcreteCategory.hom f) n).1h_P_eq_C:βˆ€ (k : β„•), P = C ↑khC:C 0 = C 1⊒ False All goals completed! πŸ™

4. Solving equations and picturing mapsπŸ”—

Definition: Equalizer (p. 292)

{E \xrightarrow{p} X} is an equalizer of {f, g} if {fp = gp} and for each {T \xrightarrow{x} X} for which {fx = gx}, there is exactly one {T \xrightarrow{e} E} for which {x = pe}.

In mathlib, two parallel morphisms f and g are given by the diagram parallelPair f g. A cone over parallelPair f g is aliased as Fork f g. If that fork is a limit cone, then we have an equalizer of {f, g}. We print the definitions of HasEqualizer, parallelPair, and Fork below for reference.

@[reducible] def CategoryTheory.Limits.HasEqualizer.{v, u} : {C : Type u} β†’ {X Y : C} β†’ [inst : Category.{v, u} C] β†’ (X ⟢ Y) β†’ (X ⟢ Y) β†’ Prop := fun {C} {X Y} [Category.{v, u} C] f g ↦ HasLimit (parallelPair f g)#print HasEqualizer
@[reducible] def CategoryTheory.Limits.HasEqualizer.{v, u} : {C : Type u} β†’
  {X Y : C} β†’ [inst : Category.{v, u} C] β†’ (X ⟢ Y) β†’ (X ⟢ Y) β†’ Prop :=
fun {C} {X Y} [Category.{v, u} C] f g ↦ HasLimit (parallelPair f g)
CategoryTheory.Limits.parallelPair.{v, u} {C : Type u} {X Y : C} [Category.{v, u} C] (f g : X ⟢ Y) : WalkingParallelPair β₯€ C#check parallelPair
CategoryTheory.Limits.parallelPair.{v, u} {C : Type u} {X Y : C} [Category.{v, u} C] (f g : X ⟢ Y) :
  WalkingParallelPair β₯€ C
@[reducible] def CategoryTheory.Limits.Fork.{v, u} : {C : Type u} β†’ {X Y : C} β†’ [inst : Category.{v, u} C] β†’ (X ⟢ Y) β†’ (X ⟢ Y) β†’ Type (max (max 0 u) v) := fun {C} {X Y} [Category.{v, u} C] f g ↦ Cone (parallelPair f g)#print Fork
@[reducible] def CategoryTheory.Limits.Fork.{v, u} : {C : Type u} β†’
  {X Y : C} β†’ [inst : Category.{v, u} C] β†’ (X ⟢ Y) β†’ (X ⟢ Y) β†’ Type (max (max 0 u) v) :=
fun {C} {X Y} [Category.{v, u} C] f g ↦ Cone (parallelPair f g)
Exercise 5 (p. 293)

If both {E, p} and {F, q} are equalizers for the same pair {f, g}, then the unique map {F \xrightarrow{e} E} for which {pe = q} is an isomorphism.

Solution: Exercise 5

Using Mathlib's canonical equalizer f g function would make both {E, p} and {F, q} into the exact same chosen object, reducing the exercise to a triviality about the identity morphism. To preserve the purpose of the exercise, which is to compare two independent equalizers, our proof uses the book definition directly.

example {π’ž : Type u} [Category.{v, u} π’ž] (X Y : π’ž) (f g : X ⟢ Y) (E F : π’ž) (p : E ⟢ X) (hp₁ : f ⊚ p = g ⊚ p) (hpβ‚‚ : βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e : T ⟢ E, x = p ⊚ e) (q : F ⟢ X) (hq₁ : f ⊚ q = g ⊚ q) (hqβ‚‚ : βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e : T ⟢ F, x = q ⊚ e) : βˆƒ e : F β‰… E, p ⊚ e.hom = q := π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žF:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eq:F ⟢ Xhq₁:f ⊚ q = g ⊚ qhqβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = q ⊚ e⊒ βˆƒ e, p ⊚ e.hom = q π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žF:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eq:F ⟢ Xhq₁:f ⊚ q = g ⊚ qhqβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = q ⊚ ee:F ⟢ Ehe_comm:q = p ⊚ eright✝:βˆ€ (y : F ⟢ E), (fun e ↦ q = p ⊚ e) y β†’ y = e⊒ βˆƒ e, p ⊚ e.hom = q π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žF:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eq:F ⟢ Xhq₁:f ⊚ q = g ⊚ qhqβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = q ⊚ ee:F ⟢ Ehe_comm:q = p ⊚ eright✝¹:βˆ€ (y : F ⟢ E), (fun e ↦ q = p ⊚ e) y β†’ y = ee_inv:E ⟢ Fhe_inv_comm:p = q ⊚ e_invright✝:βˆ€ (y : E ⟢ F), (fun e ↦ p = q ⊚ e) y β†’ y = e_inv⊒ βˆƒ e, p ⊚ e.hom = q π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žF:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eq:F ⟢ Xhq₁:f ⊚ q = g ⊚ qhqβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = q ⊚ ee:F ⟢ Ehe_comm:q = p ⊚ eright✝¹:βˆ€ (y : F ⟢ E), (fun e ↦ q = p ⊚ e) y β†’ y = ee_inv:E ⟢ Fhe_inv_comm:p = q ⊚ e_invright✝:βˆ€ (y : E ⟢ F), (fun e ↦ p = q ⊚ e) y β†’ y = e_invw✝:E ⟢ Eleft✝:p = p ⊚ w✝hE_uniq:βˆ€ (y : E ⟢ E), (fun e ↦ p = p ⊚ e) y β†’ y = w✝⊒ βˆƒ e, p ⊚ e.hom = q π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žF:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eq:F ⟢ Xhq₁:f ⊚ q = g ⊚ qhqβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = q ⊚ ee:F ⟢ Ehe_comm:q = p ⊚ eright✝¹:βˆ€ (y : F ⟢ E), (fun e ↦ q = p ⊚ e) y β†’ y = ee_inv:E ⟢ Fhe_inv_comm:p = q ⊚ e_invright✝:βˆ€ (y : E ⟢ F), (fun e ↦ p = q ⊚ e) y β†’ y = e_invw✝:E ⟢ Eleft✝:p = p ⊚ w✝hE_uniq:βˆ€ (y : E ⟢ E), (fun e ↦ p = p ⊚ e) y β†’ y = w✝hE₁:πŸ™ E = w✝⊒ βˆƒ e, p ⊚ e.hom = q π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žF:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eq:F ⟢ Xhq₁:f ⊚ q = g ⊚ qhqβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = q ⊚ ee:F ⟢ Ehe_comm:q = p ⊚ eright✝¹:βˆ€ (y : F ⟢ E), (fun e ↦ q = p ⊚ e) y β†’ y = ee_inv:E ⟢ Fhe_inv_comm:p = q ⊚ e_invright✝:βˆ€ (y : E ⟢ F), (fun e ↦ p = q ⊚ e) y β†’ y = e_invw✝:E ⟢ Eleft✝:p = p ⊚ w✝hE_uniq:βˆ€ (y : E ⟢ E), (fun e ↦ p = p ⊚ e) y β†’ y = w✝hE₁:πŸ™ E = w✝hEβ‚‚:e ⊚ e_inv = w✝⊒ βˆƒ e, p ⊚ e.hom = q π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žF:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eq:F ⟢ Xhq₁:f ⊚ q = g ⊚ qhqβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = q ⊚ ee:F ⟢ Ehe_comm:q = p ⊚ eright✝¹:βˆ€ (y : F ⟢ E), (fun e ↦ q = p ⊚ e) y β†’ y = ee_inv:E ⟢ Fhe_inv_comm:p = q ⊚ e_invright✝:βˆ€ (y : E ⟢ F), (fun e ↦ p = q ⊚ e) y β†’ y = e_invw✝¹:E ⟢ Eleft✝¹:p = p ⊚ w✝hE_uniq:βˆ€ (y : E ⟢ E), (fun e ↦ p = p ⊚ e) y β†’ y = w✝hE₁:πŸ™ E = w✝hEβ‚‚:e ⊚ e_inv = w✝w✝:F ⟢ Fleft✝:q = q ⊚ w✝hF_uniq:βˆ€ (y : F ⟢ F), (fun e ↦ q = q ⊚ e) y β†’ y = w✝⊒ βˆƒ e, p ⊚ e.hom = q π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žF:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eq:F ⟢ Xhq₁:f ⊚ q = g ⊚ qhqβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = q ⊚ ee:F ⟢ Ehe_comm:q = p ⊚ eright✝¹:βˆ€ (y : F ⟢ E), (fun e ↦ q = p ⊚ e) y β†’ y = ee_inv:E ⟢ Fhe_inv_comm:p = q ⊚ e_invright✝:βˆ€ (y : E ⟢ F), (fun e ↦ p = q ⊚ e) y β†’ y = e_invw✝¹:E ⟢ Eleft✝¹:p = p ⊚ w✝hE_uniq:βˆ€ (y : E ⟢ E), (fun e ↦ p = p ⊚ e) y β†’ y = w✝hE₁:πŸ™ E = w✝hEβ‚‚:e ⊚ e_inv = w✝w✝:F ⟢ Fleft✝:q = q ⊚ w✝hF_uniq:βˆ€ (y : F ⟢ F), (fun e ↦ q = q ⊚ e) y β†’ y = w✝hF₁:πŸ™ F = w✝⊒ βˆƒ e, p ⊚ e.hom = q π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žF:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eq:F ⟢ Xhq₁:f ⊚ q = g ⊚ qhqβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = q ⊚ ee:F ⟢ Ehe_comm:q = p ⊚ eright✝¹:βˆ€ (y : F ⟢ E), (fun e ↦ q = p ⊚ e) y β†’ y = ee_inv:E ⟢ Fhe_inv_comm:p = q ⊚ e_invright✝:βˆ€ (y : E ⟢ F), (fun e ↦ p = q ⊚ e) y β†’ y = e_invw✝¹:E ⟢ Eleft✝¹:p = p ⊚ w✝hE_uniq:βˆ€ (y : E ⟢ E), (fun e ↦ p = p ⊚ e) y β†’ y = w✝hE₁:πŸ™ E = w✝hEβ‚‚:e ⊚ e_inv = w✝w✝:F ⟢ Fleft✝:q = q ⊚ w✝hF_uniq:βˆ€ (y : F ⟢ F), (fun e ↦ q = q ⊚ e) y β†’ y = w✝hF₁:πŸ™ F = w✝hFβ‚‚:e_inv ⊚ e = w✝⊒ βˆƒ e, p ⊚ e.hom = q use { hom := e inv := e_inv hom_inv_id := π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žF:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eq:F ⟢ Xhq₁:f ⊚ q = g ⊚ qhqβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = q ⊚ ee:F ⟢ Ehe_comm:q = p ⊚ eright✝¹:βˆ€ (y : F ⟢ E), (fun e ↦ q = p ⊚ e) y β†’ y = ee_inv:E ⟢ Fhe_inv_comm:p = q ⊚ e_invright✝:βˆ€ (y : E ⟢ F), (fun e ↦ p = q ⊚ e) y β†’ y = e_invw✝¹:E ⟢ Eleft✝¹:p = p ⊚ w✝hE_uniq:βˆ€ (y : E ⟢ E), (fun e ↦ p = p ⊚ e) y β†’ y = w✝hE₁:πŸ™ E = w✝hEβ‚‚:e ⊚ e_inv = w✝w✝:F ⟢ Fleft✝:q = q ⊚ w✝hF_uniq:βˆ€ (y : F ⟢ F), (fun e ↦ q = q ⊚ e) y β†’ y = w✝hF₁:πŸ™ F = w✝hFβ‚‚:e_inv ⊚ e = w✝⊒ e_inv ⊚ e = πŸ™ F All goals completed! πŸ™ inv_hom_id := π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žF:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eq:F ⟢ Xhq₁:f ⊚ q = g ⊚ qhqβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = q ⊚ ee:F ⟢ Ehe_comm:q = p ⊚ eright✝¹:βˆ€ (y : F ⟢ E), (fun e ↦ q = p ⊚ e) y β†’ y = ee_inv:E ⟢ Fhe_inv_comm:p = q ⊚ e_invright✝:βˆ€ (y : E ⟢ F), (fun e ↦ p = q ⊚ e) y β†’ y = e_invw✝¹:E ⟢ Eleft✝¹:p = p ⊚ w✝hE_uniq:βˆ€ (y : E ⟢ E), (fun e ↦ p = p ⊚ e) y β†’ y = w✝hE₁:πŸ™ E = w✝hEβ‚‚:e ⊚ e_inv = w✝w✝:F ⟢ Fleft✝:q = q ⊚ w✝hF_uniq:βˆ€ (y : F ⟢ F), (fun e ↦ q = q ⊚ e) y β†’ y = w✝hF₁:πŸ™ F = w✝hFβ‚‚:e_inv ⊚ e = w✝⊒ e ⊚ e_inv = πŸ™ E All goals completed! πŸ™ } All goals completed! πŸ™
Exercise 6 (p. 293)

Any map p which is an equalizer of some pair of maps is itself a monomorphism (i.e. injective).

Solution: Exercise 6

Using the book definition of equalizer, we have

example {π’ž : Type u} [Category.{v, u} π’ž] (X Y : π’ž) (f g : X ⟢ Y) (E : π’ž) (p : E ⟢ X) (hp₁ : f ⊚ p = g ⊚ p) (hpβ‚‚ : βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e : T ⟢ E, x = p ⊚ e) : Mono p := π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ e⊒ Mono p π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ e⊒ βˆ€ {Z : π’ž} (g h : Z ⟢ E), p ⊚ g = p ⊚ h β†’ g = h π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eT:π’že₁:T ⟢ Eeβ‚‚:T ⟢ Eh_eq₁:p ⊚ e₁ = p ⊚ eβ‚‚βŠ’ e₁ = eβ‚‚ π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eT:π’že₁:T ⟢ Eeβ‚‚:T ⟢ Eh_eq₁:p ⊚ e₁ = p ⊚ eβ‚‚h_eqβ‚‚:f ⊚ p ⊚ e₁ = g ⊚ p ⊚ eβ‚βŠ’ e₁ = eβ‚‚ π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YE:π’žp:E ⟢ Xhp₁:f ⊚ p = g ⊚ phpβ‚‚:βˆ€ (T : π’ž) (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ βˆƒ! e, x = p ⊚ eT:π’že₁:T ⟢ Eeβ‚‚:T ⟢ Eh_eq₁:p ⊚ e₁ = p ⊚ eβ‚‚h_eqβ‚‚:f ⊚ p ⊚ e₁ = g ⊚ p ⊚ e₁w✝:T ⟢ Eleft✝:p ⊚ e₁ = p ⊚ w✝h_uniq:βˆ€ (y : T ⟢ E), (fun e ↦ p ⊚ e₁ = p ⊚ e) y β†’ y = w✝⊒ e₁ = eβ‚‚ All goals completed! πŸ™

Alternatively, using mathlib's HasEqualizer type class and the equalizer.hom_ext theorem yields a more concise proof.

example {π’ž : Type u} [Category.{v, u} π’ž] (X Y : π’ž) (f g : X ⟢ Y) [HasEqualizer f g] : Mono (equalizer.ΞΉ f g) := π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasEqualizer f g⊒ Mono (equalizer.ΞΉ f g) π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasEqualizer f gp:equalizer f g ⟢ X := equalizer.ΞΉ f g⊒ Mono (equalizer.ΞΉ f g) π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasEqualizer f gp:equalizer f g ⟢ X := equalizer.ΞΉ f g⊒ βˆ€ {Z : π’ž} (g_1 h : Z ⟢ equalizer f g), equalizer.ΞΉ f g ⊚ g_1 = equalizer.ΞΉ f g ⊚ h β†’ g_1 = h π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasEqualizer f gp:equalizer f g ⟢ X := equalizer.ΞΉ f gT:π’že₁:T ⟢ equalizer f geβ‚‚:T ⟢ equalizer f gh_eq:equalizer.ΞΉ f g ⊚ e₁ = equalizer.ΞΉ f g ⊚ eβ‚‚βŠ’ e₁ = eβ‚‚ All goals completed! πŸ™
Exercise 7 (p. 293)

If {B \xrightarrow{\alpha} A \xrightarrow{\beta} B} compose to the identity {1_B = \beta\alpha} and if f is the idempotent \alpha\beta, then \alpha is an equalizer for the pair {f, 1_A}.

Solution: Exercise 7

Using the book definition of equalizer, we have

example {π’ž : Type u} [Category.{v, u} π’ž] (A B : π’ž) (Ξ± : B ⟢ A) (Ξ² : A ⟢ B) (h_idB : πŸ™ B = Ξ² ⊚ Ξ±) (f : A ⟢ A) (hf : f = Ξ± ⊚ Ξ²) : f ⊚ Ξ± = πŸ™ A ⊚ Ξ± ∧ βˆ€ (T : π’ž) (x : T ⟢ A), f ⊚ x = πŸ™ A ⊚ x β†’ βˆƒ! e : T ⟢ B, x = Ξ± ⊚ e := π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ β⊒ f ⊚ Ξ± = πŸ™ A ⊚ Ξ± ∧ βˆ€ (T : π’ž) (x : T ⟢ A), f ⊚ x = πŸ™ A ⊚ x β†’ βˆƒ! e, x = Ξ± ⊚ e π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ β⊒ f ⊚ Ξ± = πŸ™ A ⊚ Ξ±π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ β⊒ βˆ€ (T : π’ž) (x : T ⟢ A), f ⊚ x = πŸ™ A ⊚ x β†’ βˆƒ! e, x = Ξ± ⊚ e π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ β⊒ f ⊚ Ξ± = πŸ™ A ⊚ Ξ± All goals completed! πŸ™ π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ β⊒ βˆ€ (T : π’ž) (x : T ⟢ A), f ⊚ x = πŸ™ A ⊚ x β†’ βˆƒ! e, x = Ξ± ⊚ e π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²T:π’žx:T ⟢ Ahx:f ⊚ x = πŸ™ A ⊚ x⊒ βˆƒ! e, x = Ξ± ⊚ e π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²T:π’žx:T ⟢ Ahx:f ⊚ x = πŸ™ A ⊚ x⊒ (fun e ↦ x = Ξ± ⊚ e) (Ξ² ⊚ x) ∧ βˆ€ (y : T ⟢ B), (fun e ↦ x = Ξ± ⊚ e) y β†’ y = Ξ² ⊚ x π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²T:π’žx:T ⟢ Ahx:f ⊚ x = πŸ™ A ⊚ x⊒ (fun e ↦ x = Ξ± ⊚ e) (Ξ² ⊚ x)π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²T:π’žx:T ⟢ Ahx:f ⊚ x = πŸ™ A ⊚ x⊒ βˆ€ (y : T ⟢ B), (fun e ↦ x = Ξ± ⊚ e) y β†’ y = Ξ² ⊚ x π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²T:π’žx:T ⟢ Ahx:f ⊚ x = πŸ™ A ⊚ x⊒ (fun e ↦ x = Ξ± ⊚ e) (Ξ² ⊚ x) π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²T:π’žx:T ⟢ Ahx:f ⊚ x = πŸ™ A ⊚ x⊒ x = Ξ± ⊚ Ξ² ⊚ x All goals completed! πŸ™ π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²T:π’žx:T ⟢ Ahx:f ⊚ x = πŸ™ A ⊚ x⊒ βˆ€ (y : T ⟢ B), (fun e ↦ x = Ξ± ⊚ e) y β†’ y = Ξ² ⊚ x π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²T:π’žx:T ⟢ Ahx:f ⊚ x = πŸ™ A ⊚ xy:T ⟢ Bhy:x = Ξ± ⊚ y⊒ y = Ξ² ⊚ x All goals completed! πŸ™

Using the mathlib API, we have

example {π’ž : Type u} [Category.{v, u} π’ž] (A B : π’ž) (Ξ± : B ⟢ A) (Ξ² : A ⟢ B) (h_idB : πŸ™ B = Ξ² ⊚ Ξ±) (f : A ⟢ A) (hf : f = Ξ± ⊚ Ξ²) : βˆƒ (w : f ⊚ Ξ± = πŸ™ A ⊚ Ξ±), Nonempty (IsLimit (Fork.ofΞΉ Ξ± w)) := π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ β⊒ βˆƒ (w : f ⊚ Ξ± = πŸ™ A ⊚ Ξ±), Nonempty (IsLimit (Fork.ofΞΉ Ξ± w)) π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ α⊒ βˆƒ (w : f ⊚ Ξ± = πŸ™ A ⊚ Ξ±), Nonempty (IsLimit (Fork.ofΞΉ Ξ± w)) π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ α⊒ Nonempty (IsLimit (Fork.ofΞΉ Ξ± w)) π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ α⊒ IsLimit (Fork.ofΞΉ Ξ± w) π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ α⊒ βˆ€ (s : Fork f (πŸ™ A)), (Fork.ofΞΉ Ξ± w).ΞΉ ⊚ Ξ² ⊚ s.ΞΉ = s.ΞΉπ’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ α⊒ βˆ€ (s : Fork f (πŸ™ A)) (m : s.pt ⟢ (Fork.ofΞΉ Ξ± w).pt), (Fork.ofΞΉ Ξ± w).ΞΉ ⊚ m = s.ΞΉ β†’ m = Ξ² ⊚ s.ΞΉ π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ α⊒ βˆ€ (s : Fork f (πŸ™ A)), (Fork.ofΞΉ Ξ± w).ΞΉ ⊚ Ξ² ⊚ s.ΞΉ = s.ΞΉ -- fac π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ Ξ±s:Fork f (πŸ™ A)⊒ (Fork.ofΞΉ Ξ± w).ΞΉ ⊚ Ξ² ⊚ s.ΞΉ = s.ΞΉ π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ Ξ±s:Fork f (πŸ™ A)⊒ Ξ± ⊚ Ξ² ⊚ s.ΞΉ = s.ΞΉ All goals completed! πŸ™ π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ α⊒ βˆ€ (s : Fork f (πŸ™ A)) (m : s.pt ⟢ (Fork.ofΞΉ Ξ± w).pt), (Fork.ofΞΉ Ξ± w).ΞΉ ⊚ m = s.ΞΉ β†’ m = Ξ² ⊚ s.ΞΉ -- uniq π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ Ξ±s:Fork f (πŸ™ A)m:s.pt ⟢ (Fork.ofΞΉ Ξ± w).pthm:(Fork.ofΞΉ Ξ± w).ΞΉ ⊚ m = s.ι⊒ m = Ξ² ⊚ s.ΞΉ π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ Ξ±s:Fork f (πŸ™ A)m:s.pt ⟢ (Fork.ofΞΉ Ξ± w).pthm:(Fork.ofΞΉ Ξ± w).ΞΉ ⊚ m = s.ι⊒ m = Ξ² ⊚ s.ΞΉ erw [π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ Ξ±s:Fork f (πŸ™ A)m:s.pt ⟢ (Fork.ofΞΉ Ξ± w).pthm:(Fork.ofΞΉ Ξ± w).ΞΉ ⊚ m = s.ι⊒ m = Ξ² ⊚ (Fork.ofΞΉ Ξ± w).ΞΉ ⊚ m π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ Ξ±s:Fork f (πŸ™ A)m:s.pt ⟢ (Fork.ofΞΉ Ξ± w).pthm:(Fork.ofΞΉ Ξ± w).ΞΉ ⊚ m = s.ι⊒ m = (Ξ² ⊚ (Fork.ofΞΉ Ξ± w).ΞΉ) ⊚ m π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ Ξ±s:Fork f (πŸ™ A)m:s.pt ⟢ (Fork.ofΞΉ Ξ± w).pthm:(Fork.ofΞΉ Ξ± w).ΞΉ ⊚ m = s.ι⊒ m = πŸ™ B ⊚ m π’ž:Type uinst✝:Category.{v, u} π’žA:π’žB:π’žΞ±:B ⟢ AΞ²:A ⟢ Bh_idB:πŸ™ B = Ξ² ⊚ Ξ±f:A ⟢ Ahf:f = Ξ± ⊚ Ξ²w:f ⊚ Ξ± = πŸ™ A ⊚ Ξ±s:Fork f (πŸ™ A)m:s.pt ⟢ (Fork.ofΞΉ Ξ± w).pthm:(Fork.ofΞΉ Ξ± w).ΞΉ ⊚ m = s.ι⊒ m = mAll goals completed! πŸ™
Exercise 8 (p. 293)

Any parallel pair {X \xrightarrow{f} Y}, {X \xrightarrow{g} Y} of maps in sets, no matter how or why it occurred to us in the first place, can always be imagined as the source and target structure of a graph. In a graph, which are the arrows that are named by the equalizer of the source and target maps?

Solution: Exercise 8

In this analogy, the set X represents the arrows of the graph, and the set Y represents the dots. The functions f and g represent the source and target maps. The equalizer of {f, g} is then the subset of elements {x \in X} such that {f(x) = g(x)}, which corresponds to the arrows whose source and target are the same dot. Therefore the arrows named by the equalizer are exactly the self-loops of the graph.

We formalise the proof of this statement below. Instead of using a subset, however, we represent the equalizer as a type E and a morphism p from E to the arrows of the graph, and we assume that p equalizes the source and target maps and satisfies the universal property of a limit.

open ConcreteCategory in example (G : IrreflexiveGraph) (E : Type) (p : E ⟢ G.carrierA) (w : G.toSrc ⊚ p = G.toTgt ⊚ p) (t : IsLimit (Fork.ofΞΉ p w)) : βˆ€ a : G.carrierA, (βˆƒ x : E, p x = a) ↔ G.toSrc a = G.toTgt a := G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)⊒ βˆ€ (a : G.carrierA), (βˆƒ x, (hom p) x = a) ↔ (hom G.toSrc) a = (hom G.toTgt) a G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)a:G.carrierA⊒ (βˆƒ x, (hom p) x = a) ↔ (hom G.toSrc) a = (hom G.toTgt) a G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)a:G.carrierA⊒ (βˆƒ x, (hom p) x = a) β†’ (hom G.toSrc) a = (hom G.toTgt) aG:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)a:G.carrierA⊒ (hom G.toSrc) a = (hom G.toTgt) a β†’ βˆƒ x, (hom p) x = a G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)a:G.carrierA⊒ (βˆƒ x, (hom p) x = a) β†’ (hom G.toSrc) a = (hom G.toTgt) a G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)x:E⊒ (hom G.toSrc) ((hom p) x) = (hom G.toTgt) ((hom p) x) All goals completed! πŸ™ G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)a:G.carrierA⊒ (hom G.toSrc) a = (hom G.toTgt) a β†’ βˆƒ x, (hom p) x = a G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)a:G.carrierAha:(hom G.toSrc) a = (hom G.toTgt) a⊒ βˆƒ x, (hom p) x = a -- Convert a : G.carrierA into a morphism from the terminal object G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)a:G.carrierAha:(hom G.toSrc) a = (hom G.toTgt) atest:Unit ⟢ G.carrierA := β†Ύfun x ↦ a⊒ βˆƒ x, (hom p) x = a -- and show that the morphism equalizes the source and target maps G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)a:G.carrierAha:(hom G.toSrc) a = (hom G.toTgt) atest:Unit ⟢ G.carrierA := β†Ύfun x ↦ ah_test:G.toSrc ⊚ test = G.toTgt ⊚ test⊒ βˆƒ x, (hom p) x = a -- Bundle the morphism into a cone over the parallel pair of maps G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)a:G.carrierAha:(hom G.toSrc) a = (hom G.toTgt) atest:Unit ⟢ G.carrierA := β†Ύfun x ↦ ah_test:G.toSrc ⊚ test = G.toTgt ⊚ tests:Fork G.toSrc G.toTgt := Fork.ofΞΉ test h_test⊒ βˆƒ x, (hom p) x = a -- Use the universal property of the limit to get a witness x : E G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)a:G.carrierAha:(hom G.toSrc) a = (hom G.toTgt) atest:Unit ⟢ G.carrierA := β†Ύfun x ↦ ah_test:G.toSrc ⊚ test = G.toTgt ⊚ tests:Fork G.toSrc G.toTgt := Fork.ofΞΉ test h_test⊒ (hom p) ((hom (t.lift s)) ()) = a -- Appeal to the factorisation property of the limit G:IrreflexiveGraphE:Typep:E ⟢ G.carrierAw:G.toSrc ⊚ p = G.toTgt ⊚ pt:IsLimit (Fork.ofΞΉ p w)a:G.carrierAha:(hom G.toSrc) a = (hom G.toTgt) atest:Unit ⟢ G.carrierA := β†Ύfun x ↦ ah_test:G.toSrc ⊚ test = G.toTgt ⊚ tests:Fork G.toSrc G.toTgt := Fork.ofΞΉ test h_testh_fac:p ⊚ t.lift s = s.ι⊒ (hom p) ((hom (t.lift s)) ()) = a -- Close the goal by applying Unit.unit to both sides All goals completed! πŸ™
Exercise 9 (p. 293)

For any map {X \xrightarrow{f} Y} there is a unique section \Gamma of p_X for which {f = p_Y \Gamma}, namely {\Gamma = \langle ?, f \rangle}.

Solution: Exercise 9

The unique section is {\Gamma = \langle 1_X, f \rangle}.

example {π’ž : Type u} [Category.{v, u} π’ž] (X Y : π’ž) [HasBinaryProduct X Y] : βˆ€ f : X ⟢ Y, βˆƒ! Ξ“ : SplitEpi prod.fst, f = prod.snd ⊚ Ξ“.section_ := π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Y⊒ βˆ€ (f : X ⟢ Y), βˆƒ! Ξ“, f = prod.snd ⊚ Ξ“.section_ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Yf:X ⟢ Y⊒ βˆƒ! Ξ“, f = prod.snd ⊚ Ξ“.section_ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Yf:X ⟢ Y⊒ (fun Ξ“ ↦ f = prod.snd ⊚ Ξ“.section_) { section_ := prod.lift (πŸ™ X) f, id := β‹― } ∧ βˆ€ (y : SplitEpi prod.fst), (fun Ξ“ ↦ f = prod.snd ⊚ Ξ“.section_) y β†’ y = { section_ := prod.lift (πŸ™ X) f, id := β‹― } π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Yf:X ⟢ Y⊒ (fun Ξ“ ↦ f = prod.snd ⊚ Ξ“.section_) { section_ := prod.lift (πŸ™ X) f, id := β‹― }π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Yf:X ⟢ Y⊒ βˆ€ (y : SplitEpi prod.fst), (fun Ξ“ ↦ f = prod.snd ⊚ Ξ“.section_) y β†’ y = { section_ := prod.lift (πŸ™ X) f, id := β‹― } π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Yf:X ⟢ Y⊒ (fun Ξ“ ↦ f = prod.snd ⊚ Ξ“.section_) { section_ := prod.lift (πŸ™ X) f, id := β‹― } All goals completed! πŸ™ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Yf:X ⟢ Y⊒ βˆ€ (y : SplitEpi prod.fst), (fun Ξ“ ↦ f = prod.snd ⊚ Ξ“.section_) y β†’ y = { section_ := prod.lift (πŸ™ X) f, id := β‹― } π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Yf:X ⟢ YΞ“':SplitEpi prod.fsthf:f = prod.snd ⊚ Ξ“'.section_⊒ Ξ“' = { section_ := prod.lift (πŸ™ X) f, id := β‹― } π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Yf:X ⟢ YΞ“':SplitEpi prod.fsthf:f = prod.snd ⊚ Ξ“'.section_⊒ prod.fst ⊚ Ξ“'.section_ = prod.fst ⊚ { section_ := prod.lift (πŸ™ X) f, id := β‹― }.section_π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Yf:X ⟢ YΞ“':SplitEpi prod.fsthf:f = prod.snd ⊚ Ξ“'.section_⊒ prod.snd ⊚ Ξ“'.section_ = prod.snd ⊚ { section_ := prod.lift (πŸ™ X) f, id := β‹― }.section_ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Yf:X ⟢ YΞ“':SplitEpi prod.fsthf:f = prod.snd ⊚ Ξ“'.section_⊒ prod.fst ⊚ Ξ“'.section_ = prod.fst ⊚ { section_ := prod.lift (πŸ™ X) f, id := β‹― }.section_ All goals completed! πŸ™ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žinst✝:HasBinaryProduct X Yf:X ⟢ YΞ“':SplitEpi prod.fsthf:f = prod.snd ⊚ Ξ“'.section_⊒ prod.snd ⊚ Ξ“'.section_ = prod.snd ⊚ { section_ := prod.lift (πŸ™ X) f, id := β‹― }.section_ All goals completed! πŸ™
Exercise 10 (p. 294)

Given two parallel maps {X \xrightarrow{f} Y}, {X \xrightarrow{g} Y} in a category with products (such as 𝑺), consider their graphs \Gamma_f and \Gamma_g. Explain pictorially why the equalizer of {f, g} is isomorphic to the intersection in {X \times Y} of their graphs.

Solution: Exercise 10

We provide two formalisations of the proof that the equalizer of {f, g} is isomorphic to the intersection in {X \times Y} of their graphs. The first proof uses the book definition of equalizer and a manual definition of intersection (since the book has not yet introduced the concept of an intersection). The second uses mathlib's API for equalizers and pullbacks, the latter being how intersections are implemented in mathlib. We have kept the structure of the two proofs essentially the same to aid in undertanding the translation between manual terms and API terms.

The 'manual' proof is as follows:

example {π’ž : Type u} [Category.{v, u} π’ž] (X Y : π’ž) (f g : X ⟢ Y) [HasBinaryProduct X Y] -- Equalizer of f, g (E₁ : π’ž) (p : E₁ ⟢ X) (hp : f ⊚ p = g ⊚ p) (lift₁ : βˆ€ {T : π’ž} (x : T ⟢ X), f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)) (fac₁ : βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = x) (uniq₁ : βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x h) -- Graphs of f and g (Ξ“f Ξ“g : SplitEpi prod.fst) (hΞ“f : f = prod.snd ⊚ Ξ“f.section_) (hΞ“g : g = prod.snd ⊚ Ξ“g.section_) -- Intersection in X Γ— Y of graphs of f and g (Eβ‚‚ : π’ž) (u : Eβ‚‚ ⟢ X) (v : Eβ‚‚ ⟢ X) (h_intersect : Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ v) (liftβ‚‚ : βˆ€ {T : π’ž} (u' v' : T ⟢ X), Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)) (fac_uβ‚‚ : βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u') (_ : βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v') (uniqβ‚‚ : βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' h) : E₁ β‰… Eβ‚‚ := π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' h⊒ E₁ β‰… Eβ‚‚ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = v⊒ E₁ β‰… Eβ‚‚ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ u⊒ E₁ β‰… Eβ‚‚ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eq⊒ E₁ β‰… Eβ‚‚ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = u⊒ E₁ β‰… Eβ‚‚ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ p⊒ E₁ β‰… Eβ‚‚ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ pe₁₂_lift:E₁ ⟢ Eβ‚‚ := liftβ‚‚ p p hp_eq⊒ E₁ β‰… Eβ‚‚ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ pe₁₂_lift:E₁ ⟢ Eβ‚‚ := liftβ‚‚ p p hp_eqe₁₂_fac_u:u ⊚ liftβ‚‚ p p hp_eq = p⊒ E₁ β‰… Eβ‚‚ exact { hom := e₁₂_lift inv := e₂₁_lift hom_inv_id := π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ pe₁₂_lift:E₁ ⟢ Eβ‚‚ := liftβ‚‚ p p hp_eqe₁₂_fac_u:u ⊚ liftβ‚‚ p p hp_eq = p⊒ e₂₁_lift ⊚ e₁₂_lift = πŸ™ E₁ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ pe₁₂_lift:E₁ ⟢ Eβ‚‚ := liftβ‚‚ p p hp_eqe₁₂_fac_u:u ⊚ liftβ‚‚ p p hp_eq = ph:p ⊚ e₂₁_lift ⊚ e₁₂_lift = p⊒ e₂₁_lift ⊚ e₁₂_lift = πŸ™ E₁ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ pe₁₂_lift:E₁ ⟢ Eβ‚‚ := liftβ‚‚ p p hp_eqe₁₂_fac_u:u ⊚ liftβ‚‚ p p hp_eq = ph:p ⊚ e₂₁_lift ⊚ e₁₂_lift = ph₁:πŸ™ E₁ = lift₁ p hp⊒ e₂₁_lift ⊚ e₁₂_lift = πŸ™ E₁ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ pe₁₂_lift:E₁ ⟢ Eβ‚‚ := liftβ‚‚ p p hp_eqe₁₂_fac_u:u ⊚ liftβ‚‚ p p hp_eq = ph:p ⊚ e₂₁_lift ⊚ e₁₂_lift = ph₁:πŸ™ E₁ = lift₁ p hphβ‚‚:e₂₁_lift ⊚ e₁₂_lift = lift₁ p hp⊒ e₂₁_lift ⊚ e₁₂_lift = πŸ™ E₁ All goals completed! πŸ™ inv_hom_id := π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ pe₁₂_lift:E₁ ⟢ Eβ‚‚ := liftβ‚‚ p p hp_eqe₁₂_fac_u:u ⊚ liftβ‚‚ p p hp_eq = p⊒ e₁₂_lift ⊚ e₂₁_lift = πŸ™ Eβ‚‚ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ pe₁₂_lift:E₁ ⟢ Eβ‚‚ := liftβ‚‚ p p hp_eqe₁₂_fac_u:u ⊚ liftβ‚‚ p p hp_eq = phu:u ⊚ e₁₂_lift ⊚ e₂₁_lift = u⊒ e₁₂_lift ⊚ e₂₁_lift = πŸ™ Eβ‚‚ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ pe₁₂_lift:E₁ ⟢ Eβ‚‚ := liftβ‚‚ p p hp_eqe₁₂_fac_u:u ⊚ liftβ‚‚ p p hp_eq = phu:u ⊚ e₁₂_lift ⊚ e₂₁_lift = uhv:v ⊚ e₁₂_lift ⊚ e₂₁_lift = v⊒ e₁₂_lift ⊚ e₂₁_lift = πŸ™ Eβ‚‚ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ pe₁₂_lift:E₁ ⟢ Eβ‚‚ := liftβ‚‚ p p hp_eqe₁₂_fac_u:u ⊚ liftβ‚‚ p p hp_eq = phu:u ⊚ e₁₂_lift ⊚ e₂₁_lift = uhv:v ⊚ e₁₂_lift ⊚ e₂₁_lift = vh₁:πŸ™ Eβ‚‚ = liftβ‚‚ u v h_intersect⊒ e₁₂_lift ⊚ e₂₁_lift = πŸ™ Eβ‚‚ π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasBinaryProduct X YE₁:π’žp:E₁ ⟢ Xhp:f ⊚ p = g ⊚ plift₁:{T : π’ž} β†’ (x : T ⟢ X) β†’ f ⊚ x = g ⊚ x β†’ (T ⟢ E₁)fac₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x), p ⊚ lift₁ x h = xuniq₁:βˆ€ {T : π’ž} (x : T ⟢ X) (h : f ⊚ x = g ⊚ x) (m : T ⟢ E₁), p ⊚ m = x β†’ m = lift₁ x hΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_Eβ‚‚:π’žu:Eβ‚‚ ⟢ Xv:Eβ‚‚ ⟢ Xh_intersect:Ξ“f.section_ ⊚ u = Ξ“g.section_ ⊚ vliftβ‚‚:{T : π’ž} β†’ (u' v' : T ⟢ X) β†’ Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v' β†’ (T ⟢ Eβ‚‚)fac_uβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), u ⊚ liftβ‚‚ u' v' h = u'x✝:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v'), v ⊚ liftβ‚‚ u' v' h = v'uniqβ‚‚:βˆ€ {T : π’ž} (u' v' : T ⟢ X) (h : Ξ“f.section_ ⊚ u' = Ξ“g.section_ ⊚ v') (m : T ⟢ Eβ‚‚), u ⊚ m = u' β†’ v ⊚ m = v' β†’ m = liftβ‚‚ u' v' hhuv:u = vhu_eq:f ⊚ u = g ⊚ ue₂₁_lift:Eβ‚‚ ⟢ E₁ := lift₁ u hu_eqhe₂₁_fac:p ⊚ lift₁ u hu_eq = uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ pe₁₂_lift:E₁ ⟢ Eβ‚‚ := liftβ‚‚ p p hp_eqe₁₂_fac_u:u ⊚ liftβ‚‚ p p hp_eq = phu:u ⊚ e₁₂_lift ⊚ e₂₁_lift = uhv:v ⊚ e₁₂_lift ⊚ e₂₁_lift = vh₁:πŸ™ Eβ‚‚ = liftβ‚‚ u v h_intersecthβ‚‚:e₁₂_lift ⊚ e₂₁_lift = liftβ‚‚ u v h_intersect⊒ e₁₂_lift ⊚ e₂₁_lift = πŸ™ Eβ‚‚ All goals completed! πŸ™ }

The API proof is as follows:

noncomputable example {π’ž : Type u} [Category.{v, u} π’ž] (X Y : π’ž) (f g : X ⟢ Y) [HasBinaryProduct X Y] -- Equalizer of f, g [HasEqualizer f g] -- Graphs of f and g (Ξ“f Ξ“g : SplitEpi prod.fst) (hΞ“f : f = prod.snd ⊚ Ξ“f.section_) (hΞ“g : g = prod.snd ⊚ Ξ“g.section_) -- Intersection in X Γ— Y of graphs of f and g [HasPullback Ξ“f.section_ Ξ“g.section_] : equalizer f g β‰… pullback Ξ“f.section_ Ξ“g.section_ := π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_⊒ equalizer f g β‰… pullback Ξ“f.section_ Ξ“g.section_ π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f g⊒ equalizer f g β‰… pullback Ξ“f.section_ Ξ“g.section_ π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_⊒ equalizer f g β‰… pullback Ξ“f.section_ Ξ“g.section_ π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_v:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.snd Ξ“f.section_ Ξ“g.section_⊒ equalizer f g β‰… pullback Ξ“f.section_ Ξ“g.section_ π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_v:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.snd Ξ“f.section_ Ξ“g.section_huv:u = v⊒ equalizer f g β‰… pullback Ξ“f.section_ Ξ“g.section_ π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_v:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.snd Ξ“f.section_ Ξ“g.section_huv:u = vhu_eq:f ⊚ u = g ⊚ u⊒ equalizer f g β‰… pullback Ξ“f.section_ Ξ“g.section_ π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_v:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.snd Ξ“f.section_ Ξ“g.section_huv:u = vhu_eq:f ⊚ u = g ⊚ uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ p⊒ equalizer f g β‰… pullback Ξ“f.section_ Ξ“g.section_ exact { hom := pullback.lift p p hp_eq inv := equalizer.lift u hu_eq hom_inv_id := π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_v:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.snd Ξ“f.section_ Ξ“g.section_huv:u = vhu_eq:f ⊚ u = g ⊚ uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ p⊒ equalizer.lift u hu_eq ⊚ pullback.lift p p hp_eq = πŸ™ (equalizer f g) π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_v:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.snd Ξ“f.section_ Ξ“g.section_huv:u = vhu_eq:f ⊚ u = g ⊚ uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ p⊒ equalizer.ΞΉ f g ⊚ equalizer.lift u hu_eq ⊚ pullback.lift p p hp_eq = equalizer.ΞΉ f g ⊚ πŸ™ (equalizer f g) All goals completed! πŸ™ inv_hom_id := π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_v:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.snd Ξ“f.section_ Ξ“g.section_huv:u = vhu_eq:f ⊚ u = g ⊚ uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ p⊒ pullback.lift p p hp_eq ⊚ equalizer.lift u hu_eq = πŸ™ (pullback Ξ“f.section_ Ξ“g.section_) π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_v:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.snd Ξ“f.section_ Ξ“g.section_huv:u = vhu_eq:f ⊚ u = g ⊚ uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ p⊒ pullback.fst Ξ“f.section_ Ξ“g.section_ ⊚ pullback.lift p p hp_eq ⊚ equalizer.lift u hu_eq = pullback.fst Ξ“f.section_ Ξ“g.section_ ⊚ πŸ™ (pullback Ξ“f.section_ Ξ“g.section_)π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_v:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.snd Ξ“f.section_ Ξ“g.section_huv:u = vhu_eq:f ⊚ u = g ⊚ uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ p⊒ pullback.snd Ξ“f.section_ Ξ“g.section_ ⊚ pullback.lift p p hp_eq ⊚ equalizer.lift u hu_eq = pullback.snd Ξ“f.section_ Ξ“g.section_ ⊚ πŸ™ (pullback Ξ“f.section_ Ξ“g.section_) π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_v:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.snd Ξ“f.section_ Ξ“g.section_huv:u = vhu_eq:f ⊚ u = g ⊚ uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ p⊒ pullback.fst Ξ“f.section_ Ξ“g.section_ ⊚ pullback.lift p p hp_eq ⊚ equalizer.lift u hu_eq = pullback.fst Ξ“f.section_ Ξ“g.section_ ⊚ πŸ™ (pullback Ξ“f.section_ Ξ“g.section_) All goals completed! πŸ™ π’ž:Type uinst✝³:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝²:HasBinaryProduct X Yinst✝¹:HasEqualizer f gΞ“f:SplitEpi prod.fstΞ“g:SplitEpi prod.fsthΞ“f:f = prod.snd ⊚ Ξ“f.section_hΞ“g:g = prod.snd ⊚ Ξ“g.section_inst✝:HasPullback Ξ“f.section_ Ξ“g.section_p:equalizer f g ⟢ X := equalizer.ΞΉ f gu:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.fst Ξ“f.section_ Ξ“g.section_v:pullback Ξ“f.section_ Ξ“g.section_ ⟢ X := pullback.snd Ξ“f.section_ Ξ“g.section_huv:u = vhu_eq:f ⊚ u = g ⊚ uhp_eq:Ξ“f.section_ ⊚ p = Ξ“g.section_ ⊚ p⊒ pullback.snd Ξ“f.section_ Ξ“g.section_ ⊚ pullback.lift p p hp_eq ⊚ equalizer.lift u hu_eq = pullback.snd Ξ“f.section_ Ξ“g.section_ ⊚ πŸ™ (pullback Ξ“f.section_ Ξ“g.section_) All goals completed! πŸ™ }

Between Exercises 10 and 11, the book discusses cographs and coequalizers.

To emphasize the duality between graphs and cographs, we first provide a formalisation of graph of f (cf. Exercise 9).

noncomputable def graphOf {π’ž : Type u} [Category.{v, u} π’ž] {X Y : π’ž} [HasBinaryProduct X Y] (f : X ⟢ Y) : X ⟢ X β¨― Y := prod.lift (πŸ™ X) f lemma graphOf_is_section {π’ž : Type u} [Category.{v, u} π’ž] {X Y : π’ž} [HasBinaryProduct X Y] (f : X ⟢ Y) : prod.fst ⊚ graphOf f = πŸ™ X := prod.lift_fst (πŸ™ X) f lemma graphOf_commutes {π’ž : Type u} [Category.{v, u} π’ž] {X Y : π’ž} [HasBinaryProduct X Y] (f : X ⟢ Y) : prod.snd ⊚ graphOf f = f := prod.lift_snd (πŸ™ X) f

Dualizing the definition of graph of f then gives the following formalisation of cograph of g.

noncomputable def cographOf {π’ž : Type u} [Category.{v, u} π’ž] {X Y : π’ž} [HasBinaryCoproduct X Y] (g : Y ⟢ X) : X β¨Ώ Y ⟢ X := coprod.desc (πŸ™ X) g lemma cographOf_is_retraction {π’ž : Type u} [Category.{v, u} π’ž] {X Y : π’ž} [HasBinaryCoproduct X Y] (g : Y ⟢ X) : cographOf g ⊚ coprod.inl = πŸ™ X := coprod.inl_desc (πŸ™ X) g lemma cographOf_commutes {π’ž : Type u} [Category.{v, u} π’ž] {X Y : π’ž} [HasBinaryCoproduct X Y] (g : Y ⟢ X) : cographOf g ⊚ coprod.inr = g := coprod.inr_desc (πŸ™ X) g

Similarly, the definition of coequalizer is dual to that of equalizer. That is, {X \xrightarrow{q} C} is a coequalizer of {u, v} if {qu = qv} and for each {X \xrightarrow{t} T} for which {tu = tv}, there is exactly one {C \xrightarrow{c} T} for which {t = cq} (cf. the definition of equalizer above).

In mathlib, two parallel morphisms have a coequalizer if their parallel pair diagram has a colimit. We print the definition of HasCoequalizer below for reference.

@[reducible] def CategoryTheory.Limits.HasCoequalizer.{v, u} : {C : Type u} β†’ {X Y : C} β†’ [inst : Category.{v, u} C] β†’ (X ⟢ Y) β†’ (X ⟢ Y) β†’ Prop := fun {C} {X Y} [Category.{v, u} C] f g ↦ HasColimit (parallelPair f g)#print HasCoequalizer
@[reducible] def CategoryTheory.Limits.HasCoequalizer.{v, u} : {C : Type u} β†’
  {X Y : C} β†’ [inst : Category.{v, u} C] β†’ (X ⟢ Y) β†’ (X ⟢ Y) β†’ Prop :=
fun {C} {X Y} [Category.{v, u} C] f g ↦ HasColimit (parallelPair f g)
Exercise 11 (p. 294)

Say that {Y \xrightarrow{h} Z} is a cosolution of the co-equation represented by a given source/target structure {X \xrightarrow{f} Y}, {X \xrightarrow{g} Y} if {hf = hg}. Show that if such a cosolution h is universal, in the sense that any other cosolution {Y \xrightarrow{h'} Z'} can be uniquely expressed as {h' = qh}, then h is an epimorphism. (A universal cosolution is called a coequalizer of the pair {f, g}; in many categories every epimorphism is a coequalizer of some pair.)

Solution: Exercise 11

This exercise is the dual of Exercise 6, so our proof here is essentially the same but with all arrows reversed. Following the approach taken in Exercise 6, we provide formalisations using both the book definition of coequalizer and mathlib's HasCoequalizer type class.

example {π’ž : Type u} [Category.{v, u} π’ž] (X Y : π’ž) (f g : X ⟢ Y) (Z : π’ž) (h : Y ⟢ Z) (hh₁ : h ⊚ f = h ⊚ g) (hhβ‚‚ : βˆ€ (Z' : π’ž) (h' : Y ⟢ Z'), h' ⊚ f = h' ⊚ g β†’ βˆƒ! q : Z ⟢ Z', h' = q ⊚ h) : Epi h := π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YZ:π’žh:Y ⟢ Zhh₁:h ⊚ f = h ⊚ ghhβ‚‚:βˆ€ (Z' : π’ž) (h' : Y ⟢ Z'), h' ⊚ f = h' ⊚ g β†’ βˆƒ! q, h' = q ⊚ h⊒ Epi h π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YZ:π’žh:Y ⟢ Zhh₁:h ⊚ f = h ⊚ ghhβ‚‚:βˆ€ (Z' : π’ž) (h' : Y ⟢ Z'), h' ⊚ f = h' ⊚ g β†’ βˆƒ! q, h' = q ⊚ h⊒ βˆ€ {Z_1 : π’ž} (g h_1 : Z ⟢ Z_1), g ⊚ h = h_1 ⊚ h β†’ g = h_1 π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YZ:π’žh:Y ⟢ Zhh₁:h ⊚ f = h ⊚ ghhβ‚‚:βˆ€ (Z' : π’ž) (h' : Y ⟢ Z'), h' ⊚ f = h' ⊚ g β†’ βˆƒ! q, h' = q ⊚ hZ':π’žq₁:Z ⟢ Z'qβ‚‚:Z ⟢ Z'h_eq₁:q₁ ⊚ h = qβ‚‚ ⊚ h⊒ q₁ = qβ‚‚ π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YZ:π’žh:Y ⟢ Zhh₁:h ⊚ f = h ⊚ ghhβ‚‚:βˆ€ (Z' : π’ž) (h' : Y ⟢ Z'), h' ⊚ f = h' ⊚ g β†’ βˆƒ! q, h' = q ⊚ hZ':π’žq₁:Z ⟢ Z'qβ‚‚:Z ⟢ Z'h_eq₁:q₁ ⊚ h = qβ‚‚ ⊚ hh_eqβ‚‚:(q₁ ⊚ h) ⊚ f = (q₁ ⊚ h) ⊚ g⊒ q₁ = qβ‚‚ π’ž:Type uinst✝:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ YZ:π’žh:Y ⟢ Zhh₁:h ⊚ f = h ⊚ ghhβ‚‚:βˆ€ (Z' : π’ž) (h' : Y ⟢ Z'), h' ⊚ f = h' ⊚ g β†’ βˆƒ! q, h' = q ⊚ hZ':π’žq₁:Z ⟢ Z'qβ‚‚:Z ⟢ Z'h_eq₁:q₁ ⊚ h = qβ‚‚ ⊚ hh_eqβ‚‚:(q₁ ⊚ h) ⊚ f = (q₁ ⊚ h) ⊚ gw✝:Z ⟢ Z'left✝:q₁ ⊚ h = w✝ ⊚ hh_uniq:βˆ€ (y : Z ⟢ Z'), (fun q ↦ q₁ ⊚ h = q ⊚ h) y β†’ y = w✝⊒ q₁ = qβ‚‚ All goals completed! πŸ™ example {π’ž : Type u} [Category.{v, u} π’ž] (X Y : π’ž) (f g : X ⟢ Y) [HasCoequalizer f g] : Epi (coequalizer.Ο€ f g) := π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasCoequalizer f g⊒ Epi (coequalizer.Ο€ f g) π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasCoequalizer f gh:Y ⟢ coequalizer f g := coequalizer.Ο€ f g⊒ Epi (coequalizer.Ο€ f g) π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasCoequalizer f gh:Y ⟢ coequalizer f g := coequalizer.Ο€ f g⊒ βˆ€ {Z : π’ž} (g_1 h : coequalizer f g ⟢ Z), g_1 ⊚ coequalizer.Ο€ f g = h ⊚ coequalizer.Ο€ f g β†’ g_1 = h π’ž:Type uinst✝¹:Category.{v, u} π’žX:π’žY:π’žf:X ⟢ Yg:X ⟢ Yinst✝:HasCoequalizer f gh:Y ⟢ coequalizer f g := coequalizer.Ο€ f gZ':π’žq₁:coequalizer f g ⟢ Z'qβ‚‚:coequalizer f g ⟢ Z'h_eq:q₁ ⊚ coequalizer.Ο€ f g = qβ‚‚ ⊚ coequalizer.Ο€ f g⊒ q₁ = qβ‚‚ All goals completed! πŸ™
Exercise 12 (p. 294)

For a given map {Y \xrightarrow{h} Z}, consider all parallel pairs {X \xrightarrow{f} Y}, {X \xrightarrow{g} Y} (for various X) such that {hf = hg}. Formulate the notion of a universal such; call it X_h. Show that {X_h \rightrightarrows Y} is reflexive, symmetric, transitive, and jointly monomorphic. Here 'reflexive' you know from our discussion of directed graphs, 'symmetric' means there is an involution \sigma of X_h whose right action interchanges the universal f and g. 'Jointly monomorphic' means the map {X \rightarrow Y \times Y} with label {\langle f, g \rangle} is injective. 'Transitivity' involves a trio of test maps {T \rightarrow Y}. (An STM reflexive graph is called an equivalence relation on Y; in many categories every equivalence relation arises as the universal X_h, for some h.)

Solution: Exercise 12

We take each of the four properties in turn.

{X_h \rightrightarrows Y} is reflexive:

example {π’ž : Type u} [Category.{v, u} π’ž] (Y Z : π’ž) (h : Y ⟢ Z) (Xh : π’ž) (f g : Xh ⟢ Y) (_ : h ⊚ f = h ⊚ g) (h_univ : βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u : X ⟢ Xh, f ⊚ u = f' ∧ g ⊚ u = g') : βˆƒ r : Y ⟢ Xh, f ⊚ r = πŸ™ Y ∧ g ⊚ r = πŸ™ Y := π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yx✝:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'⊒ βˆƒ r, f ⊚ r = πŸ™ Y ∧ g ⊚ r = πŸ™ Y π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yx✝:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'r:Y ⟢ Xhhr_comm:f ⊚ r = πŸ™ Y ∧ g ⊚ r = πŸ™ Yright✝:βˆ€ (y : Y ⟢ Xh), (fun u ↦ f ⊚ u = πŸ™ Y ∧ g ⊚ u = πŸ™ Y) y β†’ y = r⊒ βˆƒ r, f ⊚ r = πŸ™ Y ∧ g ⊚ r = πŸ™ Y All goals completed! πŸ™

{X_h \rightrightarrows Y} is symmetric:

example {π’ž : Type u} [Category.{v, u} π’ž] (Y Z : π’ž) (h : Y ⟢ Z) (Xh : π’ž) (f g : Xh ⟢ Y) (hh : h ⊚ f = h ⊚ g) (h_univ : βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u : X ⟢ Xh, f ⊚ u = f' ∧ g ⊚ u = g') : βˆƒ Οƒ : Xh ⟢ Xh, Οƒ ⊚ Οƒ = πŸ™ Xh ∧ f ⊚ Οƒ = g ∧ g ⊚ Οƒ = f := π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'⊒ βˆƒ Οƒ, Οƒ ⊚ Οƒ = πŸ™ Xh ∧ f ⊚ Οƒ = g ∧ g ⊚ Οƒ = f π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'Οƒ:Xh ⟢ XhhΟƒ_comm:f ⊚ Οƒ = g ∧ g ⊚ Οƒ = fright✝:βˆ€ (y : Xh ⟢ Xh), (fun u ↦ f ⊚ u = g ∧ g ⊚ u = f) y β†’ y = ΟƒβŠ’ βˆƒ Οƒ, Οƒ ⊚ Οƒ = πŸ™ Xh ∧ f ⊚ Οƒ = g ∧ g ⊚ Οƒ = f π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'Οƒ:Xh ⟢ XhhΟƒ_comm:f ⊚ Οƒ = g ∧ g ⊚ Οƒ = fright✝:βˆ€ (y : Xh ⟢ Xh), (fun u ↦ f ⊚ u = g ∧ g ⊚ u = f) y β†’ y = ΟƒβŠ’ Οƒ ⊚ Οƒ = πŸ™ Xh π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'Οƒ:Xh ⟢ XhhΟƒ_comm:f ⊚ Οƒ = g ∧ g ⊚ Οƒ = fright✝:βˆ€ (y : Xh ⟢ Xh), (fun u ↦ f ⊚ u = g ∧ g ⊚ u = f) y β†’ y = Οƒw✝:Xh ⟢ Xhleft✝:f ⊚ w✝ = f ∧ g ⊚ w✝ = gh_uniq:βˆ€ (y : Xh ⟢ Xh), (fun u ↦ f ⊚ u = f ∧ g ⊚ u = g) y β†’ y = w✝⊒ Οƒ ⊚ Οƒ = πŸ™ Xh π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'Οƒ:Xh ⟢ XhhΟƒ_comm:f ⊚ Οƒ = g ∧ g ⊚ Οƒ = fright✝:βˆ€ (y : Xh ⟢ Xh), (fun u ↦ f ⊚ u = g ∧ g ⊚ u = f) y β†’ y = Οƒw✝:Xh ⟢ Xhleft✝:f ⊚ w✝ = f ∧ g ⊚ w✝ = gh_uniq:βˆ€ (y : Xh ⟢ Xh), (fun u ↦ f ⊚ u = f ∧ g ⊚ u = g) y β†’ y = w✝h1Xh:πŸ™ Xh = w✝⊒ Οƒ ⊚ Οƒ = πŸ™ Xh π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'Οƒ:Xh ⟢ XhhΟƒ_comm:f ⊚ Οƒ = g ∧ g ⊚ Οƒ = fright✝:βˆ€ (y : Xh ⟢ Xh), (fun u ↦ f ⊚ u = g ∧ g ⊚ u = f) y β†’ y = Οƒw✝:Xh ⟢ Xhleft✝:f ⊚ w✝ = f ∧ g ⊚ w✝ = gh_uniq:βˆ€ (y : Xh ⟢ Xh), (fun u ↦ f ⊚ u = f ∧ g ⊚ u = g) y β†’ y = w✝h1Xh:πŸ™ Xh = w✝hσσ:Οƒ ⊚ Οƒ = w✝⊒ Οƒ ⊚ Οƒ = πŸ™ Xh All goals completed! πŸ™

{X_h \rightrightarrows Y} is transitive:

example {π’ž : Type u} [Category.{v, u} π’ž] (Y Z : π’ž) (h : Y ⟢ Z) (Xh : π’ž) (f g : Xh ⟢ Y) (hh : h ⊚ f = h ⊚ g) (h_univ : βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u : X ⟢ Xh, f ⊚ u = f' ∧ g ⊚ u = g') : βˆ€ {T : π’ž} (y₁ yβ‚‚ y₃ : T ⟢ Y) (v₁ vβ‚‚ : T ⟢ Xh), f ⊚ v₁ = y₁ β†’ g ⊚ v₁ = yβ‚‚ β†’ f ⊚ vβ‚‚ = yβ‚‚ β†’ g ⊚ vβ‚‚ = y₃ β†’ βˆƒ v₃ : T ⟢ Xh, f ⊚ v₃ = y₁ ∧ g ⊚ v₃ = y₃ := π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'⊒ βˆ€ {T : π’ž} (y₁ yβ‚‚ y₃ : T ⟢ Y) (v₁ vβ‚‚ : T ⟢ Xh), f ⊚ v₁ = y₁ β†’ g ⊚ v₁ = yβ‚‚ β†’ f ⊚ vβ‚‚ = yβ‚‚ β†’ g ⊚ vβ‚‚ = y₃ β†’ βˆƒ v₃, f ⊚ v₃ = y₁ ∧ g ⊚ v₃ = y₃ π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'T:π’žy₁:T ⟢ Yyβ‚‚:T ⟢ Yy₃:T ⟢ Yv₁:T ⟢ Xhvβ‚‚:T ⟢ Xhhf₁:f ⊚ v₁ = y₁hg₁:g ⊚ v₁ = yβ‚‚hfβ‚‚:f ⊚ vβ‚‚ = yβ‚‚hgβ‚‚:g ⊚ vβ‚‚ = yβ‚ƒβŠ’ βˆƒ v₃, f ⊚ v₃ = y₁ ∧ g ⊚ v₃ = y₃ π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'T:π’žy₁:T ⟢ Yyβ‚‚:T ⟢ Yy₃:T ⟢ Yv₁:T ⟢ Xhvβ‚‚:T ⟢ Xhhf₁:f ⊚ v₁ = y₁hg₁:g ⊚ v₁ = yβ‚‚hfβ‚‚:f ⊚ vβ‚‚ = yβ‚‚hgβ‚‚:g ⊚ vβ‚‚ = y₃hy:h ⊚ y₁ = h ⊚ yβ‚ƒβŠ’ βˆƒ v₃, f ⊚ v₃ = y₁ ∧ g ⊚ v₃ = y₃ π’ž:Type uinst✝:Category.{v, u} π’žY:π’žZ:π’žh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'T:π’žy₁:T ⟢ Yyβ‚‚:T ⟢ Yy₃:T ⟢ Yv₁:T ⟢ Xhvβ‚‚:T ⟢ Xhhf₁:f ⊚ v₁ = y₁hg₁:g ⊚ v₁ = yβ‚‚hfβ‚‚:f ⊚ vβ‚‚ = yβ‚‚hgβ‚‚:g ⊚ vβ‚‚ = y₃hy:h ⊚ y₁ = h ⊚ y₃v₃:T ⟢ Xhleft✝:f ⊚ v₃ = y₁ ∧ g ⊚ v₃ = y₃right✝:βˆ€ (y : T ⟢ Xh), (fun u ↦ f ⊚ u = y₁ ∧ g ⊚ u = y₃) y β†’ y = vβ‚ƒβŠ’ βˆƒ v₃, f ⊚ v₃ = y₁ ∧ g ⊚ v₃ = y₃ All goals completed! πŸ™

{X_h \rightrightarrows Y} is jointly monomorphic:

example {π’ž : Type u} [Category.{v, u} π’ž] (Y Z : π’ž) [HasBinaryProduct Y Y] (h : Y ⟢ Z) (Xh : π’ž) (f g : Xh ⟢ Y) (hh : h ⊚ f = h ⊚ g) (h_univ : βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u : X ⟢ Xh, f ⊚ u = f' ∧ g ⊚ u = g') : βˆ€ {T : π’ž} (a b : T ⟢ Xh), prod.lift f g ⊚ a = prod.lift f g ⊚ b β†’ a = b := π’ž:Type uinst✝¹:Category.{v, u} π’žY:π’žZ:π’žinst✝:HasBinaryProduct Y Yh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'⊒ βˆ€ {T : π’ž} (a b : T ⟢ Xh), prod.lift f g ⊚ a = prod.lift f g ⊚ b β†’ a = b π’ž:Type uinst✝¹:Category.{v, u} π’žY:π’žZ:π’žinst✝:HasBinaryProduct Y Yh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'T:π’ža:T ⟢ Xhb:T ⟢ Xhhp_comm:prod.lift f g ⊚ a = prod.lift f g ⊚ b⊒ a = b π’ž:Type uinst✝¹:Category.{v, u} π’žY:π’žZ:π’žinst✝:HasBinaryProduct Y Yh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'T:π’ža:T ⟢ Xhb:T ⟢ Xhhp_comm:prod.lift f g ⊚ a = prod.lift f g ⊚ bhf:f ⊚ a = f ⊚ b⊒ a = b π’ž:Type uinst✝¹:Category.{v, u} π’žY:π’žZ:π’žinst✝:HasBinaryProduct Y Yh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'T:π’ža:T ⟢ Xhb:T ⟢ Xhhp_comm:prod.lift f g ⊚ a = prod.lift f g ⊚ bhf:f ⊚ a = f ⊚ bhg:g ⊚ a = g ⊚ b⊒ a = b π’ž:Type uinst✝¹:Category.{v, u} π’žY:π’žZ:π’žinst✝:HasBinaryProduct Y Yh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'T:π’ža:T ⟢ Xhb:T ⟢ Xhhp_comm:prod.lift f g ⊚ a = prod.lift f g ⊚ bhf:f ⊚ a = f ⊚ bhg:g ⊚ a = g ⊚ bw✝:T ⟢ Xhleft✝:f ⊚ w✝ = f ⊚ a ∧ g ⊚ w✝ = g ⊚ ah_uniq:βˆ€ (y : T ⟢ Xh), (fun u ↦ f ⊚ u = f ⊚ a ∧ g ⊚ u = g ⊚ a) y β†’ y = w✝⊒ a = b π’ž:Type uinst✝¹:Category.{v, u} π’žY:π’žZ:π’žinst✝:HasBinaryProduct Y Yh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'T:π’ža:T ⟢ Xhb:T ⟢ Xhhp_comm:prod.lift f g ⊚ a = prod.lift f g ⊚ bhf:f ⊚ a = f ⊚ bhg:g ⊚ a = g ⊚ bw✝:T ⟢ Xhleft✝:f ⊚ w✝ = f ⊚ a ∧ g ⊚ w✝ = g ⊚ ah_uniq:βˆ€ (y : T ⟢ Xh), (fun u ↦ f ⊚ u = f ⊚ a ∧ g ⊚ u = g ⊚ a) y β†’ y = w✝ha:a = w✝⊒ a = b π’ž:Type uinst✝¹:Category.{v, u} π’žY:π’žZ:π’žinst✝:HasBinaryProduct Y Yh:Y ⟢ ZXh:π’žf:Xh ⟢ Yg:Xh ⟢ Yhh:h ⊚ f = h ⊚ gh_univ:βˆ€ {X : π’ž} (f' g' : X ⟢ Y), h ⊚ f' = h ⊚ g' β†’ βˆƒ! u, f ⊚ u = f' ∧ g ⊚ u = g'T:π’ža:T ⟢ Xhb:T ⟢ Xhhp_comm:prod.lift f g ⊚ a = prod.lift f g ⊚ bhf:f ⊚ a = f ⊚ bhg:g ⊚ a = g ⊚ bw✝:T ⟢ Xhleft✝:f ⊚ w✝ = f ⊚ a ∧ g ⊚ w✝ = g ⊚ ah_uniq:βˆ€ (y : T ⟢ Xh), (fun u ↦ f ⊚ u = f ⊚ a ∧ g ⊚ u = g ⊚ a) y β†’ y = w✝ha:a = w✝hb:b = w✝⊒ a = b All goals completed! πŸ™