A Lean Companion to Conceptual Mathematics

Session 11: Ascending to categories of richer structuresπŸ”—

1. A category of richer structures: Endomaps of setsπŸ”—

Exercise 1 (p. 153)

How many maps can you find? (There are fewer than seven.)

Solution: Exercise 1

Label the elements in the three-element set A as a_1, a_2, a_3 (clockwise starting with any element); label the elements in the set X as x_1 for the element forming the one-element loop and x_2, x_3, x_4 (anticlockwise starting with any element) for the elements forming the three-element cycle, ignoring all other elements.

inductive A | a₁ | aβ‚‚ | a₃ inductive X | x₁ | xβ‚‚ | x₃ | xβ‚„ def A' : SetWithEndomap := { carrier := A toEnd := β†Ύfun | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₃ | A.a₃ => A.a₁ } def X' : SetWithEndomap := { carrier := X toEnd := β†Ύfun -- a restriction of Ξ± to the subset {x₁, xβ‚‚, x₃, xβ‚„} | X.x₁ => X.x₁ | X.xβ‚‚ => X.x₃ | X.x₃ => X.xβ‚„ | X.xβ‚„ => X.xβ‚‚ }

Then there are four structure-preserving maps from A to X, which we call f_1, f_2, f_3, f_4 below.

def f₁ : A ⟢ X := β†Ύfun | A.a₁ => X.x₁ | A.aβ‚‚ => X.x₁ | A.a₃ => X.x₁ -- f₁ is structure-preserving example : A' ⟢ X' := ⟨ f₁, ⊒ f₁ ⊚ A'.toEnd = X'.toEnd ⊚ f₁ a:A'.carrier⊒ (ConcreteCategory.hom (f₁ ⊚ A'.toEnd)).toFun a = (ConcreteCategory.hom (X'.toEnd ⊚ f₁)).toFun a ⊒ (ConcreteCategory.hom (f₁ ⊚ A'.toEnd)).toFun A.a₁ = (ConcreteCategory.hom (X'.toEnd ⊚ f₁)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom (f₁ ⊚ A'.toEnd)).toFun A.aβ‚‚ = (ConcreteCategory.hom (X'.toEnd ⊚ f₁)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom (f₁ ⊚ A'.toEnd)).toFun A.a₃ = (ConcreteCategory.hom (X'.toEnd ⊚ f₁)).toFun A.a₃ ⊒ (ConcreteCategory.hom (f₁ ⊚ A'.toEnd)).toFun A.a₁ = (ConcreteCategory.hom (X'.toEnd ⊚ f₁)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom (f₁ ⊚ A'.toEnd)).toFun A.aβ‚‚ = (ConcreteCategory.hom (X'.toEnd ⊚ f₁)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom (f₁ ⊚ A'.toEnd)).toFun A.a₃ = (ConcreteCategory.hom (X'.toEnd ⊚ f₁)).toFun A.a₃ All goals completed! πŸ™ ⟩ def fβ‚‚ : A ⟢ X := β†Ύfun | A.a₁ => X.xβ‚‚ | A.aβ‚‚ => X.x₃ | A.a₃ => X.xβ‚„ -- fβ‚‚ is structure-preserving example : A' ⟢ X' := ⟨ fβ‚‚, ⊒ fβ‚‚ ⊚ A'.toEnd = X'.toEnd ⊚ fβ‚‚ a:A'.carrier⊒ (ConcreteCategory.hom (fβ‚‚ ⊚ A'.toEnd)).toFun a = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚‚)).toFun a ⊒ (ConcreteCategory.hom (fβ‚‚ ⊚ A'.toEnd)).toFun A.a₁ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚‚)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom (fβ‚‚ ⊚ A'.toEnd)).toFun A.aβ‚‚ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚‚)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom (fβ‚‚ ⊚ A'.toEnd)).toFun A.a₃ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚‚)).toFun A.a₃ ⊒ (ConcreteCategory.hom (fβ‚‚ ⊚ A'.toEnd)).toFun A.a₁ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚‚)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom (fβ‚‚ ⊚ A'.toEnd)).toFun A.aβ‚‚ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚‚)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom (fβ‚‚ ⊚ A'.toEnd)).toFun A.a₃ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚‚)).toFun A.a₃ All goals completed! πŸ™ ⟩ def f₃ : A ⟢ X := β†Ύfun | A.a₁ => X.x₃ | A.aβ‚‚ => X.xβ‚„ | A.a₃ => X.xβ‚‚ -- f₃ is structure-preserving example : A' ⟢ X' := ⟨ f₃, ⊒ f₃ ⊚ A'.toEnd = X'.toEnd ⊚ f₃ a:A'.carrier⊒ (ConcreteCategory.hom (f₃ ⊚ A'.toEnd)).toFun a = (ConcreteCategory.hom (X'.toEnd ⊚ f₃)).toFun a ⊒ (ConcreteCategory.hom (f₃ ⊚ A'.toEnd)).toFun A.a₁ = (ConcreteCategory.hom (X'.toEnd ⊚ f₃)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom (f₃ ⊚ A'.toEnd)).toFun A.aβ‚‚ = (ConcreteCategory.hom (X'.toEnd ⊚ f₃)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom (f₃ ⊚ A'.toEnd)).toFun A.a₃ = (ConcreteCategory.hom (X'.toEnd ⊚ f₃)).toFun A.a₃ ⊒ (ConcreteCategory.hom (f₃ ⊚ A'.toEnd)).toFun A.a₁ = (ConcreteCategory.hom (X'.toEnd ⊚ f₃)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom (f₃ ⊚ A'.toEnd)).toFun A.aβ‚‚ = (ConcreteCategory.hom (X'.toEnd ⊚ f₃)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom (f₃ ⊚ A'.toEnd)).toFun A.a₃ = (ConcreteCategory.hom (X'.toEnd ⊚ f₃)).toFun A.a₃ All goals completed! πŸ™ ⟩ def fβ‚„ : A ⟢ X := β†Ύfun | A.a₁ => X.xβ‚„ | A.aβ‚‚ => X.xβ‚‚ | A.a₃ => X.x₃ -- fβ‚„ is structure-preserving example : A' ⟢ X' := ⟨ fβ‚„, ⊒ fβ‚„ ⊚ A'.toEnd = X'.toEnd ⊚ fβ‚„ a:A'.carrier⊒ (ConcreteCategory.hom (fβ‚„ ⊚ A'.toEnd)).toFun a = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚„)).toFun a ⊒ (ConcreteCategory.hom (fβ‚„ ⊚ A'.toEnd)).toFun A.a₁ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚„)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom (fβ‚„ ⊚ A'.toEnd)).toFun A.aβ‚‚ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚„)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom (fβ‚„ ⊚ A'.toEnd)).toFun A.a₃ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚„)).toFun A.a₃ ⊒ (ConcreteCategory.hom (fβ‚„ ⊚ A'.toEnd)).toFun A.a₁ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚„)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom (fβ‚„ ⊚ A'.toEnd)).toFun A.aβ‚‚ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚„)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom (fβ‚„ ⊚ A'.toEnd)).toFun A.a₃ = (ConcreteCategory.hom (X'.toEnd ⊚ fβ‚„)).toFun A.a₃ All goals completed! πŸ™ ⟩

3. The category of graphsπŸ”—

Exercise 2 (p. 158)inductive X | a | b | c def Ξ± : X ⟢ X := β†Ύfun | X.a => X.c | X.b => X.a | X.c => X.b def XΞ± : SetWithEndomap := { carrier := X toEnd := Ξ± } inductive Y | p | q | r def Ξ² : Y ⟢ Y := β†Ύfun | Y.p => Y.q | Y.q => Y.r | Y.r => Y.p def YΞ² : SetWithEndomap := { carrier := Y toEnd := Ξ² }

Find an isomorphism from X^{↻\alpha} to Y^{↻\beta}. How many such isomorphisms are there?

Hint: You need to find {X \xrightarrow{f} Y} such that {f \alpha = \beta f}, and check that f has an inverse {Y \xrightarrow{f^{-1}} X} (meaning {f^{-1}f = 1_X} and {ff^{-1} = 1_Y}). Then you'll still need to check that f^{-1} is a map in 𝑺↻ (meaning {f^{-1} \beta = \alpha f^{-1}}), but see Exercise 4, below.

Solution: Exercise 2

There are three such isomorphisms, which we call f_1, f_2, f_3 below.

def f₁ : X ⟢ Y := β†Ύfun | X.a => Y.r | X.b => Y.q | X.c => Y.p --f₁ is an isomorphism example : βˆƒ f : XΞ± ⟢ YΞ², IsIso f := ⊒ βˆƒ f, IsIso f f:XΞ± ⟢ YΞ² := ⟨f₁, β‹―βŸ©βŠ’ βˆƒ f, IsIso f f:XΞ± ⟢ YΞ² := ⟨f₁, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.c | Y.q => X.b | Y.r => X.a, β‹―βŸ©βŠ’ βˆƒ f, IsIso f f:XΞ± ⟢ YΞ² := ⟨f₁, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.c | Y.q => X.b | Y.r => X.a, β‹―βŸ©βŠ’ IsIso f f:XΞ± ⟢ YΞ² := ⟨f₁, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.c | Y.q => X.b | Y.r => X.a, β‹―βŸ©βŠ’ finv ⊚ f = πŸ™ XΞ± ∧ f ⊚ finv = πŸ™ YΞ² f:XΞ± ⟢ YΞ² := ⟨f₁, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.c | Y.q => X.b | Y.r => X.a, β‹―βŸ©βŠ’ finv ⊚ f = πŸ™ XΞ±f:XΞ± ⟢ YΞ² := ⟨f₁, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.c | Y.q => X.b | Y.r => X.a, β‹―βŸ©βŠ’ f ⊚ finv = πŸ™ YΞ² f:XΞ± ⟢ YΞ² := ⟨f₁, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.c | Y.q => X.b | Y.r => X.a, β‹―βŸ©βŠ’ finv ⊚ f = πŸ™ XΞ± -- f⁻¹f = πŸ™ X f:XΞ± ⟢ YΞ² := ⟨f₁, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.c | Y.q => X.b | Y.r => X.a, β‹―βŸ©h:↑finv ⊚ ↑f = πŸ™ X⊒ finv ⊚ f = πŸ™ XΞ± All goals completed! πŸ™ f:XΞ± ⟢ YΞ² := ⟨f₁, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.c | Y.q => X.b | Y.r => X.a, β‹―βŸ©βŠ’ f ⊚ finv = πŸ™ YΞ² -- ff⁻¹ = πŸ™ Y f:XΞ± ⟢ YΞ² := ⟨f₁, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.c | Y.q => X.b | Y.r => X.a, β‹―βŸ©h:↑f ⊚ ↑finv = πŸ™ Y⊒ f ⊚ finv = πŸ™ YΞ² All goals completed! πŸ™ def fβ‚‚ : X ⟢ Y := β†Ύfun | X.a => Y.q | X.b => Y.p | X.c => Y.r --fβ‚‚ is an isomorphism example : βˆƒ f : XΞ± ⟢ YΞ², IsIso f := ⊒ βˆƒ f, IsIso f f:XΞ± ⟢ YΞ² := ⟨fβ‚‚, β‹―βŸ©βŠ’ βˆƒ f, IsIso f f:XΞ± ⟢ YΞ² := ⟨fβ‚‚, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.b | Y.q => X.a | Y.r => X.c, β‹―βŸ©βŠ’ βˆƒ f, IsIso f f:XΞ± ⟢ YΞ² := ⟨fβ‚‚, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.b | Y.q => X.a | Y.r => X.c, β‹―βŸ©βŠ’ IsIso f f:XΞ± ⟢ YΞ² := ⟨fβ‚‚, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.b | Y.q => X.a | Y.r => X.c, β‹―βŸ©βŠ’ finv ⊚ f = πŸ™ XΞ± ∧ f ⊚ finv = πŸ™ YΞ² f:XΞ± ⟢ YΞ² := ⟨fβ‚‚, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.b | Y.q => X.a | Y.r => X.c, β‹―βŸ©βŠ’ finv ⊚ f = πŸ™ XΞ±f:XΞ± ⟢ YΞ² := ⟨fβ‚‚, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.b | Y.q => X.a | Y.r => X.c, β‹―βŸ©βŠ’ f ⊚ finv = πŸ™ YΞ² f:XΞ± ⟢ YΞ² := ⟨fβ‚‚, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.b | Y.q => X.a | Y.r => X.c, β‹―βŸ©βŠ’ finv ⊚ f = πŸ™ XΞ± -- f⁻¹f = πŸ™ X f:XΞ± ⟢ YΞ² := ⟨fβ‚‚, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.b | Y.q => X.a | Y.r => X.c, β‹―βŸ©h:↑finv ⊚ ↑f = πŸ™ X⊒ finv ⊚ f = πŸ™ XΞ± All goals completed! πŸ™ f:XΞ± ⟢ YΞ² := ⟨fβ‚‚, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.b | Y.q => X.a | Y.r => X.c, β‹―βŸ©βŠ’ f ⊚ finv = πŸ™ YΞ² -- ff⁻¹ = πŸ™ Y f:XΞ± ⟢ YΞ² := ⟨fβ‚‚, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.b | Y.q => X.a | Y.r => X.c, β‹―βŸ©h:↑f ⊚ ↑finv = πŸ™ Y⊒ f ⊚ finv = πŸ™ YΞ² All goals completed! πŸ™ def f₃ : X ⟢ Y := β†Ύfun | X.a => Y.p | X.b => Y.r | X.c => Y.q --f₃ is an isomorphism example : βˆƒ f : XΞ± ⟢ YΞ², IsIso f := ⊒ βˆƒ f, IsIso f f:XΞ± ⟢ YΞ² := ⟨f₃, β‹―βŸ©βŠ’ βˆƒ f, IsIso f f:XΞ± ⟢ YΞ² := ⟨f₃, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.a | Y.q => X.c | Y.r => X.b, β‹―βŸ©βŠ’ βˆƒ f, IsIso f f:XΞ± ⟢ YΞ² := ⟨f₃, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.a | Y.q => X.c | Y.r => X.b, β‹―βŸ©βŠ’ IsIso f f:XΞ± ⟢ YΞ² := ⟨f₃, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.a | Y.q => X.c | Y.r => X.b, β‹―βŸ©βŠ’ finv ⊚ f = πŸ™ XΞ± ∧ f ⊚ finv = πŸ™ YΞ² f:XΞ± ⟢ YΞ² := ⟨f₃, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.a | Y.q => X.c | Y.r => X.b, β‹―βŸ©βŠ’ finv ⊚ f = πŸ™ XΞ±f:XΞ± ⟢ YΞ² := ⟨f₃, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.a | Y.q => X.c | Y.r => X.b, β‹―βŸ©βŠ’ f ⊚ finv = πŸ™ YΞ² f:XΞ± ⟢ YΞ² := ⟨f₃, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.a | Y.q => X.c | Y.r => X.b, β‹―βŸ©βŠ’ finv ⊚ f = πŸ™ XΞ± -- f⁻¹f = πŸ™ X f:XΞ± ⟢ YΞ² := ⟨f₃, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.a | Y.q => X.c | Y.r => X.b, β‹―βŸ©h:↑finv ⊚ ↑f = πŸ™ X⊒ finv ⊚ f = πŸ™ XΞ± All goals completed! πŸ™ f:XΞ± ⟢ YΞ² := ⟨f₃, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.a | Y.q => X.c | Y.r => X.b, β‹―βŸ©βŠ’ f ⊚ finv = πŸ™ YΞ² -- ff⁻¹ = πŸ™ Y f:XΞ± ⟢ YΞ² := ⟨f₃, β‹―βŸ©finv:YΞ² ⟢ XΞ± := βŸ¨β†Ύfun x ↦ match x with | Y.p => X.a | Y.q => X.c | Y.r => X.b, β‹―βŸ©h:↑f ⊚ ↑finv = πŸ™ Y⊒ f ⊚ finv = πŸ™ YΞ² All goals completed! πŸ™
Exercise 3 (p. 159)

Prove that there is no isomorphism (in 𝑺↻)

from

inductive X | x₁ | xβ‚‚ | x₃ | xβ‚„ def Ξ± : X ⟢ X := β†Ύfun | X.x₁ => X.xβ‚‚ | X.xβ‚‚ => X.x₃ | X.x₃ => X.xβ‚„ | X.xβ‚„ => X.xβ‚‚ def XΞ± : SetWithEndomap := { carrier := X toEnd := Ξ± }

to

inductive Y | y₁ | yβ‚‚ | y₃ | yβ‚„ def Ξ² : Y ⟢ Y := β†Ύfun | Y.y₁ => Y.yβ‚‚ | Y.yβ‚‚ => Y.y₃ | Y.y₃ => Y.yβ‚„ | Y.yβ‚„ => Y.y₁ def YΞ² : SetWithEndomap := { carrier := Y toEnd := Ξ² }

Hint: In fact, more is true: there is no map (in 𝑺↻) from X^{↻\alpha} to Y^{↻\beta}.

Solution: Exercise 3

We give a proof by contradiction below.

example : Β¬(βˆƒ f : XΞ± ⟢ YΞ², IsIso f) := ⊒ Β¬βˆƒ f, IsIso f f:XΞ± ⟢ YΞ²h✝:IsIso f⊒ False -- X.xβ‚‚ is a fixed point of Ξ± ⊚ Ξ± ⊚ Ξ±, f:XΞ± ⟢ YΞ²h✝:IsIso fh₁:(ConcreteCategory.hom (XΞ±.toEnd ⊚ XΞ±.toEnd ⊚ XΞ±.toEnd)) X.xβ‚‚ = X.xβ‚‚βŠ’ False -- but Ξ² ⊚ Ξ² ⊚ Ξ² has no fixed points in Y f:XΞ± ⟢ YΞ²h✝:IsIso fh₁:(ConcreteCategory.hom (XΞ±.toEnd ⊚ XΞ±.toEnd ⊚ XΞ±.toEnd)) X.xβ‚‚ = X.xβ‚‚hβ‚‚:βˆ€ (y : Y), (ConcreteCategory.hom (YΞ².toEnd ⊚ YΞ².toEnd ⊚ YΞ².toEnd)) y β‰  y⊒ False -- Since f ⊚ (Ξ± ⊚ Ξ± ⊚ Ξ±) = (Ξ² ⊚ Ξ² ⊚ Ξ²) ⊚ f, we can derive a -- contradiction f:XΞ± ⟢ YΞ²h✝:IsIso fh₁:(ConcreteCategory.hom (XΞ±.toEnd ⊚ XΞ±.toEnd ⊚ XΞ±.toEnd)) X.xβ‚‚ = X.xβ‚‚hβ‚‚:βˆ€ (y : Y), (ConcreteCategory.hom (YΞ².toEnd ⊚ YΞ².toEnd ⊚ YΞ².toEnd)) y β‰  yh_contra:(ConcreteCategory.hom ↑f) ((ConcreteCategory.hom (XΞ±.toEnd ⊚ XΞ±.toEnd ⊚ XΞ±.toEnd)) X.xβ‚‚) = (ConcreteCategory.hom (YΞ².toEnd ⊚ YΞ².toEnd ⊚ YΞ².toEnd)) ((ConcreteCategory.hom ↑f) X.xβ‚‚)⊒ False f:XΞ± ⟢ YΞ²h✝:IsIso fh₁:(ConcreteCategory.hom (XΞ±.toEnd ⊚ XΞ±.toEnd ⊚ XΞ±.toEnd)) X.xβ‚‚ = X.xβ‚‚hβ‚‚:βˆ€ (y : Y), (ConcreteCategory.hom (YΞ².toEnd ⊚ YΞ².toEnd ⊚ YΞ².toEnd)) y β‰  yh_contra:(ConcreteCategory.hom ↑f) ((ConcreteCategory.hom (XΞ±.toEnd ⊚ XΞ±.toEnd ⊚ XΞ±.toEnd)) X.xβ‚‚) = (ConcreteCategory.hom (YΞ².toEnd ⊚ YΞ².toEnd ⊚ YΞ².toEnd)) ((ConcreteCategory.hom ↑f) X.xβ‚‚)this:(ConcreteCategory.hom (YΞ².toEnd ⊚ YΞ².toEnd ⊚ YΞ².toEnd)) ((ConcreteCategory.hom ↑f) X.xβ‚‚) = (ConcreteCategory.hom ↑f) X.xβ‚‚βŠ’ False f:XΞ± ⟢ YΞ²h✝:IsIso fh₁:(ConcreteCategory.hom (XΞ±.toEnd ⊚ XΞ±.toEnd ⊚ XΞ±.toEnd)) X.xβ‚‚ = X.xβ‚‚hβ‚‚:βˆ€ (y : Y), (ConcreteCategory.hom (YΞ².toEnd ⊚ YΞ².toEnd ⊚ YΞ².toEnd)) y β‰  yh_contra:(ConcreteCategory.hom ↑f) ((ConcreteCategory.hom (XΞ±.toEnd ⊚ XΞ±.toEnd ⊚ XΞ±.toEnd)) X.xβ‚‚) = (ConcreteCategory.hom (YΞ².toEnd ⊚ YΞ².toEnd ⊚ YΞ².toEnd)) ((ConcreteCategory.hom ↑f) X.xβ‚‚)this✝:(ConcreteCategory.hom (YΞ².toEnd ⊚ YΞ².toEnd ⊚ YΞ².toEnd)) ((ConcreteCategory.hom ↑f) X.xβ‚‚) = (ConcreteCategory.hom ↑f) X.xβ‚‚this:(ConcreteCategory.hom (YΞ².toEnd ⊚ YΞ².toEnd ⊚ YΞ².toEnd)) ((ConcreteCategory.hom ↑f) X.xβ‚‚) β‰  (ConcreteCategory.hom ↑f) X.xβ‚‚βŠ’ False All goals completed! πŸ™
Exercise 4 (p. 159)

Suppose {A^{↻\alpha} \xrightarrow{f} B^{↻\beta}} is a map in 𝑺↻, and that as a map of sets, {A \xrightarrow{f} B} has an inverse {B \xrightarrow{f^{-1}} A}. Show that f^{-1} is automatically a map in 𝑺↻.

Solution: Exercise 4

Let {g = f^{-1}}.

example {AΞ± BΞ² : SetWithEndomap} (f : AΞ± ⟢ BΞ²) (g : BΞ².carrier ⟢ AΞ±.carrier) (h : g ⊚ f.val = πŸ™ AΞ±.carrier ∧ f.val ⊚ g = πŸ™ BΞ².carrier) : βˆƒ finv : BΞ² ⟢ AΞ±, finv.val = g := AΞ±:SetWithEndomapBΞ²:SetWithEndomapf:AΞ± ⟢ BΞ²g:BΞ².carrier ⟢ AΞ±.carrierh:g ⊚ ↑f = πŸ™ AΞ±.carrier ∧ ↑f ⊚ g = πŸ™ BΞ².carrier⊒ βˆƒ finv, ↑finv = g AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrier⊒ βˆƒ finv, ↑finv = g use ⟨ g, AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrier⊒ g ⊚ BΞ².toEnd = AΞ±.toEnd ⊚ g AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrierb:BΞ².carrier⊒ (ConcreteCategory.hom (g ⊚ BΞ².toEnd)).toFun b = (ConcreteCategory.hom (AΞ±.toEnd ⊚ g)).toFun b AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrierb:BΞ².carrier⊒ (ConcreteCategory.hom f) ((ConcreteCategory.hom (g ⊚ BΞ².toEnd)).toFun b) = (ConcreteCategory.hom f) ((ConcreteCategory.hom (AΞ±.toEnd ⊚ g)).toFun b)AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrierb:BΞ².carrier⊒ Function.Injective ⇑(ConcreteCategory.hom f) AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrierb:BΞ².carrier⊒ (ConcreteCategory.hom f) ((ConcreteCategory.hom (g ⊚ BΞ².toEnd)).toFun b) = (ConcreteCategory.hom f) ((ConcreteCategory.hom (AΞ±.toEnd ⊚ g)).toFun b) AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrierb:BΞ².carrier⊒ (ConcreteCategory.hom (f ⊚ g ⊚ BΞ².toEnd)) b = (ConcreteCategory.hom (f ⊚ AΞ±.toEnd ⊚ g)) b AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrierb:BΞ².carrier⊒ (ConcreteCategory.hom BΞ².toEnd) b = (ConcreteCategory.hom (f ⊚ AΞ±.toEnd ⊚ g)) b All goals completed! πŸ™ AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrierb:BΞ².carrier⊒ Function.Injective ⇑(ConcreteCategory.hom f) AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrierb:BΞ².carriera₁:AΞ±.carrieraβ‚‚:AΞ±.carrierhf:(ConcreteCategory.hom f) a₁ = (ConcreteCategory.hom f) aβ‚‚βŠ’ a₁ = aβ‚‚ AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrierb:BΞ².carriera₁:AΞ±.carrieraβ‚‚:AΞ±.carrierhf:(ConcreteCategory.hom f) a₁ = (ConcreteCategory.hom f) aβ‚‚hgf:(ConcreteCategory.hom g) ((ConcreteCategory.hom f) a₁) = (ConcreteCategory.hom g) ((ConcreteCategory.hom f) aβ‚‚)⊒ a₁ = aβ‚‚ repeat AΞ±:SetWithEndomapBΞ²:SetWithEndomapg:BΞ².carrier ⟢ AΞ±.carrierf:AΞ±.carrier ⟢ BΞ².carrierhf_comm:f ⊚ AΞ±.toEnd = BΞ².toEnd ⊚ fh:g ⊚ β†‘βŸ¨f, hf_comm⟩ = πŸ™ AΞ±.carrier ∧ β†‘βŸ¨f, hf_comm⟩ ⊚ g = πŸ™ BΞ².carrierb:BΞ².carriera₁:AΞ±.carrieraβ‚‚:AΞ±.carrierhf:(ConcreteCategory.hom f) a₁ = (ConcreteCategory.hom f) aβ‚‚hgf:(ConcreteCategory.hom (πŸ™ AΞ±.carrier)) a₁ = (ConcreteCategory.hom (πŸ™ AΞ±.carrier)) aβ‚‚βŠ’ a₁ = aβ‚‚ All goals completed! πŸ™ ⟩
Exercise 5 (p. 159)

{\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, 3, \ldots\}} is the set of integers, and \mathbb{Z}^{↻\alpha} and \mathbb{Z}^{↻\beta} are the maps which add 2 and 3: {\alpha(n) = n + 2}, {\beta(n) = n + 3}. Is \mathbb{Z}^{↻\alpha} isomorphic to \mathbb{Z}^{↻\beta}? (If so, find an isomorphism {\mathbb{Z}^{↻\alpha} \xrightarrow{f} \mathbb{Z}^{↻\beta}}; if not, explain how you know they are not isomorphic.)

Solution: Exercise 5

Define the maps \mathbb{Z}^{↻\alpha} and \mathbb{Z}^{↻\beta} as SetWithEndomap structures.

def Ξ± := (Β· + (2 : β„€)) def Ξ² := (Β· + (3 : β„€)) abbrev β„€Ξ± : SetWithEndomap := { carrier := β„€ toEnd := β†ΎΞ± } abbrev β„€Ξ² : SetWithEndomap := { carrier := β„€ toEnd := β†ΎΞ² }

We show that \mathbb{Z}^{↻\alpha} is not isomorphic to \mathbb{Z}^{↻\beta}.

open ConcreteCategory in example (f : β„€Ξ± ⟢ β„€Ξ²) : Β¬(IsIso f) := f:β„€Ξ± ⟢ β„€Ξ²βŠ’ Β¬IsIso f -- Assume f is an isomorphism, and derive a contradiction f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso f⊒ False -- We begin by extracting the structure-preserving property of f f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) x⊒ False -- and unfolding the definitions of Ξ± and Ξ² f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) xhf_comm':βˆ€ (x : β„€), (hom ↑f) (x + 2) = (hom ↑f) x + 3⊒ False -- The key observation: f.val(x + 2) and f.val(x) have the same -- remainder when divided by 3 f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) xhf_comm':βˆ€ (x : β„€), (hom ↑f) (x + 2) = (hom ↑f) x + 3hf_mod_3_eq:βˆ€ (x : β„€), (hom ↑f) (x + 2) ≑ (hom ↑f) x [ZMOD 3]⊒ False -- Hence all even numbers map to values with the same remainder -- mod 3 as f.val(0), f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) xhf_comm':βˆ€ (x : β„€), (hom ↑f) (x + 2) = (hom ↑f) x + 3hf_mod_3_eq:βˆ€ (x : β„€), (hom ↑f) (x + 2) ≑ (hom ↑f) x [ZMOD 3]hf_even_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x) ≑ (hom ↑f) 0 [ZMOD 3]⊒ False -- and all odd numbers map to values with the same remainder mod 3 -- as f.val(1) f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) xhf_comm':βˆ€ (x : β„€), (hom ↑f) (x + 2) = (hom ↑f) x + 3hf_mod_3_eq:βˆ€ (x : β„€), (hom ↑f) (x + 2) ≑ (hom ↑f) x [ZMOD 3]hf_even_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x) ≑ (hom ↑f) 0 [ZMOD 3]hf_odd_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x + 1) ≑ (hom ↑f) 1 [ZMOD 3]⊒ False -- So the image of f.val can have at most two distinct remainders -- mod 3 f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) xhf_comm':βˆ€ (x : β„€), (hom ↑f) (x + 2) = (hom ↑f) x + 3hf_mod_3_eq:βˆ€ (x : β„€), (hom ↑f) (x + 2) ≑ (hom ↑f) x [ZMOD 3]hf_even_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x) ≑ (hom ↑f) 0 [ZMOD 3]hf_odd_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x + 1) ≑ (hom ↑f) 1 [ZMOD 3]hf_img_set₁:(Set.range fun x ↦ (hom ↑f) x % 3) = {(hom ↑f) 0 % 3, (hom ↑f) 1 % 3}⊒ False -- Now, since f is an isomorphism, f.val is bijective f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) xhf_comm':βˆ€ (x : β„€), (hom ↑f) (x + 2) = (hom ↑f) x + 3hf_mod_3_eq:βˆ€ (x : β„€), (hom ↑f) (x + 2) ≑ (hom ↑f) x [ZMOD 3]hf_even_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x) ≑ (hom ↑f) 0 [ZMOD 3]hf_odd_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x + 1) ≑ (hom ↑f) 1 [ZMOD 3]hf_img_set₁:(Set.range fun x ↦ (hom ↑f) x % 3) = {(hom ↑f) 0 % 3, (hom ↑f) 1 % 3}hf_bij:Function.Bijective ⇑(hom ↑f)⊒ False -- and hence surjective, f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) xhf_comm':βˆ€ (x : β„€), (hom ↑f) (x + 2) = (hom ↑f) x + 3hf_mod_3_eq:βˆ€ (x : β„€), (hom ↑f) (x + 2) ≑ (hom ↑f) x [ZMOD 3]hf_even_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x) ≑ (hom ↑f) 0 [ZMOD 3]hf_odd_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x + 1) ≑ (hom ↑f) 1 [ZMOD 3]hf_img_set₁:(Set.range fun x ↦ (hom ↑f) x % 3) = {(hom ↑f) 0 % 3, (hom ↑f) 1 % 3}hf_bij:Function.Bijective ⇑(hom ↑f)hf_surj:Function.Surjective ⇑(hom ↑f)⊒ False -- but a surjective function on β„€ must hit all three remainders -- mod 3 f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) xhf_comm':βˆ€ (x : β„€), (hom ↑f) (x + 2) = (hom ↑f) x + 3hf_mod_3_eq:βˆ€ (x : β„€), (hom ↑f) (x + 2) ≑ (hom ↑f) x [ZMOD 3]hf_even_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x) ≑ (hom ↑f) 0 [ZMOD 3]hf_odd_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x + 1) ≑ (hom ↑f) 1 [ZMOD 3]hf_img_set₁:(Set.range fun x ↦ (hom ↑f) x % 3) = {(hom ↑f) 0 % 3, (hom ↑f) 1 % 3}hf_bij:Function.Bijective ⇑(hom ↑f)hf_surj:Function.Surjective ⇑(hom ↑f)hf_img_setβ‚‚:(Set.range fun x ↦ (hom ↑f) x % 3) = {0, 1, 2}⊒ False -- Since we have found that the image of f.val can have at most -- two distinct elements and must also have exactly three distinct -- elements, we have a contradiction f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) xhf_comm':βˆ€ (x : β„€), (hom ↑f) (x + 2) = (hom ↑f) x + 3hf_mod_3_eq:βˆ€ (x : β„€), (hom ↑f) (x + 2) ≑ (hom ↑f) x [ZMOD 3]hf_even_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x) ≑ (hom ↑f) 0 [ZMOD 3]hf_odd_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x + 1) ≑ (hom ↑f) 1 [ZMOD 3]hf_img_set₁:(Set.range fun x ↦ (hom ↑f) x % 3) = {(hom ↑f) 0 % 3, (hom ↑f) 1 % 3}hf_bij:Function.Bijective ⇑(hom ↑f)hf_surj:Function.Surjective ⇑(hom ↑f)hf_img_setβ‚‚:(Set.range fun x ↦ (hom ↑f) x % 3) = {0, 1, 2}h_card₁:{(hom ↑f) 0 % 3, (hom ↑f) 1 % 3}.ncard ≀ 2⊒ False f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) xhf_comm':βˆ€ (x : β„€), (hom ↑f) (x + 2) = (hom ↑f) x + 3hf_mod_3_eq:βˆ€ (x : β„€), (hom ↑f) (x + 2) ≑ (hom ↑f) x [ZMOD 3]hf_even_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x) ≑ (hom ↑f) 0 [ZMOD 3]hf_odd_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x + 1) ≑ (hom ↑f) 1 [ZMOD 3]hf_img_set₁:(Set.range fun x ↦ (hom ↑f) x % 3) = {(hom ↑f) 0 % 3, (hom ↑f) 1 % 3}hf_bij:Function.Bijective ⇑(hom ↑f)hf_surj:Function.Surjective ⇑(hom ↑f)hf_img_setβ‚‚:(Set.range fun x ↦ (hom ↑f) x % 3) = {0, 1, 2}h_card₁:{(hom ↑f) 0 % 3, (hom ↑f) 1 % 3}.ncard ≀ 2h_cardβ‚‚:{0, 1, 2}.ncard = 3⊒ False f:β„€Ξ± ⟢ β„€Ξ²hf_iso:IsIso fhf_comm:βˆ€ (x : β„€), (⇑(hom ↑f) ∘ ⇑(hom β„€Ξ±.toEnd)) x = (⇑(hom β„€Ξ².toEnd) ∘ ⇑(hom ↑f)) xhf_comm':βˆ€ (x : β„€), (hom ↑f) (x + 2) = (hom ↑f) x + 3hf_mod_3_eq:βˆ€ (x : β„€), (hom ↑f) (x + 2) ≑ (hom ↑f) x [ZMOD 3]hf_even_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x) ≑ (hom ↑f) 0 [ZMOD 3]hf_odd_congr:βˆ€ (x : β„€), (hom ↑f) (2 * x + 1) ≑ (hom ↑f) 1 [ZMOD 3]hf_img_set₁:(Set.range fun x ↦ (hom ↑f) x % 3) = {(hom ↑f) 0 % 3, (hom ↑f) 1 % 3}hf_bij:Function.Bijective ⇑(hom ↑f)hf_surj:Function.Surjective ⇑(hom ↑f)hf_img_setβ‚‚:(Set.range fun x ↦ (hom ↑f) x % 3) = {0, 1, 2}h_card₁:3 ≀ 2h_cardβ‚‚:{0, 1, 2}.ncard = 3⊒ False All goals completed! πŸ™
Exercise 6 (p. 159)

Each of the following graphs is isomorphic to exactly one of the others. Which?

Solution: Exercise 6

We label the arrows in each graph from top to bottom.

inductive A | a₁ | aβ‚‚ | a₃

We label the dots in each graph from left to right.

inductive D | d₁ | dβ‚‚ | d₃

Then the six graphs (a) to (f) are as follows:

def graph_a : IrreflexiveGraph := { carrierA := A carrierD := D toSrc := β†Ύfun | A.a₁ => D.dβ‚‚ | A.aβ‚‚ => D.d₁ | A.a₃ => D.d₃ toTgt := β†Ύfun | A.a₁ => D.d₃ | A.aβ‚‚ => D.dβ‚‚ | A.a₃ => D.dβ‚‚ } def graph_b : IrreflexiveGraph := { carrierA := A carrierD := D toSrc := β†Ύfun | A.a₁ => D.d₁ | A.aβ‚‚ => D.dβ‚‚ | A.a₃ => D.dβ‚‚, toTgt := β†Ύfun | A.a₁ => D.dβ‚‚ | A.aβ‚‚ => D.d₃ | A.a₃ => D.d₁ } def graph_c : IrreflexiveGraph := { carrierA := A carrierD := D toSrc := β†Ύfun | A.a₁ => D.d₁ | A.aβ‚‚ => D.d₁ | A.a₃ => D.d₁ toTgt := β†Ύfun | A.a₁ => D.d₃ | A.aβ‚‚ => D.dβ‚‚ | A.a₃ => D.d₃ } def graph_d : IrreflexiveGraph := { carrierA := A carrierD := D toSrc := β†Ύfun | A.a₁ => D.d₃ | A.aβ‚‚ => D.d₁ | A.a₃ => D.dβ‚‚ toTgt := β†Ύfun | A.a₁ => D.dβ‚‚ | A.aβ‚‚ => D.dβ‚‚ | A.a₃ => D.d₃ } def graph_e : IrreflexiveGraph := { carrierA := A carrierD := D toSrc := β†Ύfun | A.a₁ => D.d₁ | A.aβ‚‚ => D.d₁ | A.a₃ => D.d₃ toTgt := β†Ύfun | A.a₁ => D.d₃ | A.aβ‚‚ => D.dβ‚‚ | A.a₃ => D.d₁ } def graph_f : IrreflexiveGraph := { carrierA := A carrierD := D toSrc := β†Ύfun | A.a₁ => D.d₁ | A.aβ‚‚ => D.d₁ | A.a₃ => D.d₁ toTgt := β†Ύfun | A.a₁ => D.dβ‚‚ | A.aβ‚‚ => D.d₃ | A.a₃ => D.d₃ }

Graph (a) is isomorphic to graph (d).

def f₁ : graph_a ⟢ graph_d := { val := ( β†Ύfun -- maps arrows | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun -- maps dots | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃ ) property := ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_a.toSrc = graph_d.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 ∧ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_a.toTgt = graph_d.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_a.toSrc = graph_d.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_a.toTgt = graph_d.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 all_goals x:graph_a.carrierA⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_a.toTgt)).toFun x = (ConcreteCategory.hom (graph_d.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun x; ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_a.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_d.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_a.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_d.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_a.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_d.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.a₃ ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_a.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_d.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_a.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_d.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_a.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_d.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.a₃ All goals completed! πŸ™ } def finv₁ : graph_d ⟢ graph_a := { val := ( β†Ύfun -- maps arrows | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun -- maps dots | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃ ) property := ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_d.toSrc = graph_a.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 ∧ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_d.toTgt = graph_a.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_d.toSrc = graph_a.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_d.toTgt = graph_a.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 all_goals x:graph_d.carrierA⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_d.toTgt)).toFun x = (ConcreteCategory.hom (graph_a.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun x; ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_d.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_a.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_d.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_a.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_d.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_a.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.a₃ ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_d.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_a.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_d.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_a.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_d.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_a.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.a₃ All goals completed! πŸ™ } example : graph_a β‰… graph_d := { hom := f₁, inv := finv₁, hom_inv_id := ⊒ finv₁ ⊚ f₁ = πŸ™ graph_a h₁:(↑finv₁).1 ⊚ (↑f₁).1 = πŸ™ graph_a.carrierA ∧ (↑finv₁).2 ⊚ (↑f₁).2 = πŸ™ graph_a.carrierD⊒ finv₁ ⊚ f₁ = πŸ™ graph_a h₁:(↑finv₁).1 ⊚ (↑f₁).1 = πŸ™ graph_a.carrierA ∧ (↑finv₁).2 ⊚ (↑f₁).2 = πŸ™ graph_a.carrierDhβ‚‚:((↑finv₁).1 ⊚ (↑f₁).1, (↑finv₁).2 ⊚ (↑f₁).2) = (πŸ™ graph_a.carrierA, πŸ™ graph_a.carrierD)⊒ finv₁ ⊚ f₁ = πŸ™ graph_a All goals completed! πŸ™, inv_hom_id := ⊒ f₁ ⊚ finv₁ = πŸ™ graph_d h₁:(↑f₁).1 ⊚ (↑finv₁).1 = πŸ™ graph_d.carrierA ∧ (↑f₁).2 ⊚ (↑finv₁).2 = πŸ™ graph_d.carrierD⊒ f₁ ⊚ finv₁ = πŸ™ graph_d h₁:(↑f₁).1 ⊚ (↑finv₁).1 = πŸ™ graph_d.carrierA ∧ (↑f₁).2 ⊚ (↑finv₁).2 = πŸ™ graph_d.carrierDhβ‚‚:((↑f₁).1 ⊚ (↑finv₁).1, (↑f₁).2 ⊚ (↑finv₁).2) = (πŸ™ graph_d.carrierA, πŸ™ graph_d.carrierD)⊒ f₁ ⊚ finv₁ = πŸ™ graph_d All goals completed! πŸ™ }

Graph (b) is isomorphic to graph (e).

def fβ‚‚ : graph_b ⟢ graph_e := { val := ( β†Ύfun -- maps arrows | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun -- maps dots | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚ ) property := ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).2 ⊚ graph_b.toSrc = graph_e.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).1 ∧ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).2 ⊚ graph_b.toTgt = graph_e.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).1 ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).2 ⊚ graph_b.toSrc = graph_e.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).1⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).2 ⊚ graph_b.toTgt = graph_e.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).1 all_goals x:graph_b.carrierA⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).2 ⊚ graph_b.toTgt)).toFun x = (ConcreteCategory.hom (graph_e.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).1)).toFun x; ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).2 ⊚ graph_b.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_e.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).2 ⊚ graph_b.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_e.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).2 ⊚ graph_b.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_e.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).1)).toFun A.a₃ ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).2 ⊚ graph_b.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_e.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).2 ⊚ graph_b.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_e.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).2 ⊚ graph_b.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_e.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.d₁ | D.d₃ => D.dβ‚‚).1)).toFun A.a₃ All goals completed! πŸ™ } def finvβ‚‚ : graph_e ⟢ graph_b := { val := ( β†Ύfun -- maps arrows | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun -- maps dots | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁ ) property := ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).2 ⊚ graph_e.toSrc = graph_b.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).1 ∧ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).2 ⊚ graph_e.toTgt = graph_b.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).1 ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).2 ⊚ graph_e.toSrc = graph_b.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).1⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).2 ⊚ graph_e.toTgt = graph_b.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).1 all_goals x:graph_e.carrierA⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).2 ⊚ graph_e.toTgt)).toFun x = (ConcreteCategory.hom (graph_b.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).1)).toFun x; ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).2 ⊚ graph_e.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_b.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).2 ⊚ graph_e.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_b.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).2 ⊚ graph_e.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_b.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).1)).toFun A.a₃ ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).2 ⊚ graph_e.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_b.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).2 ⊚ graph_e.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_b.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).2 ⊚ graph_e.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_b.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚‚ | A.a₃ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.dβ‚‚ | D.dβ‚‚ => D.d₃ | D.d₃ => D.d₁).1)).toFun A.a₃ All goals completed! πŸ™ } example : graph_b β‰… graph_e := { hom := fβ‚‚, inv := finvβ‚‚, hom_inv_id := ⊒ finvβ‚‚ ⊚ fβ‚‚ = πŸ™ graph_b h₁:(↑finvβ‚‚).1 ⊚ (↑fβ‚‚).1 = πŸ™ graph_b.carrierA ∧ (↑finvβ‚‚).2 ⊚ (↑fβ‚‚).2 = πŸ™ graph_b.carrierD⊒ finvβ‚‚ ⊚ fβ‚‚ = πŸ™ graph_b h₁:(↑finvβ‚‚).1 ⊚ (↑fβ‚‚).1 = πŸ™ graph_b.carrierA ∧ (↑finvβ‚‚).2 ⊚ (↑fβ‚‚).2 = πŸ™ graph_b.carrierDhβ‚‚:((↑finvβ‚‚).1 ⊚ (↑fβ‚‚).1, (↑finvβ‚‚).2 ⊚ (↑fβ‚‚).2) = (πŸ™ graph_b.carrierA, πŸ™ graph_b.carrierD)⊒ finvβ‚‚ ⊚ fβ‚‚ = πŸ™ graph_b All goals completed! πŸ™, inv_hom_id := ⊒ fβ‚‚ ⊚ finvβ‚‚ = πŸ™ graph_e h₁:(↑fβ‚‚).1 ⊚ (↑finvβ‚‚).1 = πŸ™ graph_e.carrierA ∧ (↑fβ‚‚).2 ⊚ (↑finvβ‚‚).2 = πŸ™ graph_e.carrierD⊒ fβ‚‚ ⊚ finvβ‚‚ = πŸ™ graph_e h₁:(↑fβ‚‚).1 ⊚ (↑finvβ‚‚).1 = πŸ™ graph_e.carrierA ∧ (↑fβ‚‚).2 ⊚ (↑finvβ‚‚).2 = πŸ™ graph_e.carrierDhβ‚‚:((↑fβ‚‚).1 ⊚ (↑finvβ‚‚).1, (↑fβ‚‚).2 ⊚ (↑finvβ‚‚).2) = (πŸ™ graph_e.carrierA, πŸ™ graph_e.carrierD)⊒ fβ‚‚ ⊚ finvβ‚‚ = πŸ™ graph_e All goals completed! πŸ™ }

Graph (c) is isomorphic to graph (f).

def f₃ : graph_c ⟢ graph_f := { val := ( β†Ύfun -- maps arrows | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun -- maps dots | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃ ) property := ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_c.toSrc = graph_f.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 ∧ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_c.toTgt = graph_f.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_c.toSrc = graph_f.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_c.toTgt = graph_f.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 all_goals x:graph_c.carrierA⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_c.toTgt)).toFun x = (ConcreteCategory.hom (graph_f.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun x; ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_c.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_f.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_c.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_f.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_c.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_f.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.a₃ ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_c.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_f.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_c.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_f.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_c.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_f.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.a₃ All goals completed! πŸ™ } def finv₃ : graph_f ⟢ graph_c := { val := ( β†Ύfun -- maps arrows | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun -- maps dots | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃ ) property := ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_f.toSrc = graph_c.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 ∧ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_f.toTgt = graph_c.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_f.toSrc = graph_c.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_f.toTgt = graph_c.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1 all_goals x:graph_f.carrierA⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_f.toTgt)).toFun x = (ConcreteCategory.hom (graph_c.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun x; ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_f.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_c.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_f.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_c.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_f.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_c.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.a₃ ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_f.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_c.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_f.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_c.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).2 ⊚ graph_f.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_c.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.aβ‚‚ | A.aβ‚‚ => A.a₁ | A.a₃ => A.a₃, β†Ύfun x ↦ match x with | D.d₁ => D.d₁ | D.dβ‚‚ => D.dβ‚‚ | D.d₃ => D.d₃).1)).toFun A.a₃ All goals completed! πŸ™ } example : graph_c β‰… graph_f := { hom := f₃, inv := finv₃, hom_inv_id := ⊒ finv₃ ⊚ f₃ = πŸ™ graph_c h₁:(↑finv₃).1 ⊚ (↑f₃).1 = πŸ™ graph_c.carrierA ∧ (↑finv₃).2 ⊚ (↑f₃).2 = πŸ™ graph_c.carrierD⊒ finv₃ ⊚ f₃ = πŸ™ graph_c h₁:(↑finv₃).1 ⊚ (↑f₃).1 = πŸ™ graph_c.carrierA ∧ (↑finv₃).2 ⊚ (↑f₃).2 = πŸ™ graph_c.carrierDhβ‚‚:((↑finv₃).1 ⊚ (↑f₃).1, (↑finv₃).2 ⊚ (↑f₃).2) = (πŸ™ graph_c.carrierA, πŸ™ graph_c.carrierD)⊒ finv₃ ⊚ f₃ = πŸ™ graph_c All goals completed! πŸ™, inv_hom_id := ⊒ f₃ ⊚ finv₃ = πŸ™ graph_f h₁:(↑f₃).1 ⊚ (↑finv₃).1 = πŸ™ graph_f.carrierA ∧ (↑f₃).2 ⊚ (↑finv₃).2 = πŸ™ graph_f.carrierD⊒ f₃ ⊚ finv₃ = πŸ™ graph_f h₁:(↑f₃).1 ⊚ (↑finv₃).1 = πŸ™ graph_f.carrierA ∧ (↑f₃).2 ⊚ (↑finv₃).2 = πŸ™ graph_f.carrierDhβ‚‚:((↑f₃).1 ⊚ (↑finv₃).1, (↑f₃).2 ⊚ (↑finv₃).2) = (πŸ™ graph_f.carrierA, πŸ™ graph_f.carrierD)⊒ f₃ ⊚ finv₃ = πŸ™ graph_f All goals completed! πŸ™ }
Exercise 7 (p. 160)

If these two graphs are isomorphic, find an isomorphism between them; if they are not isomorphic, explain how you know they are not.

Solution: Exercise 7

We label the arrows in each graph starting with the arrow at the bottom left and moving clockwise through the four outer arrows (a_1 to a_4) and then vertically upwards through the two inner arrows (a_5 and a_6).

inductive A | a₁ | aβ‚‚ | a₃ | aβ‚„ | aβ‚… | a₆

We label the dots in each graph starting with the bottom dot and moving clockwise through the four outer dots (d_1 to d_4) and then finishing with the centre dot (d_5).

inductive D | d₁ | dβ‚‚ | d₃ | dβ‚„ | dβ‚…

Then the two graphs are as follows:

def graph_L : IrreflexiveGraph := { carrierA := A carrierD := D toSrc := β†Ύfun | A.a₁ => D.d₁ | A.aβ‚‚ => D.dβ‚‚ | A.a₃ => D.d₃ | A.aβ‚„ => D.dβ‚„ | A.aβ‚… => D.d₁ | A.a₆ => D.dβ‚… toTgt := β†Ύfun | A.a₁ => D.dβ‚‚ | A.aβ‚‚ => D.d₃ | A.a₃ => D.dβ‚„ | A.aβ‚„ => D.d₁ | A.aβ‚… => D.dβ‚… | A.a₆ => D.d₃ } def graph_R : IrreflexiveGraph := { carrierA := A carrierD := D toSrc := β†Ύfun | A.a₁ => D.dβ‚‚ | A.aβ‚‚ => D.d₃ | A.a₃ => D.d₃ | A.aβ‚„ => D.dβ‚„ | A.aβ‚… => D.d₁ | A.a₆ => D.dβ‚… toTgt := β†Ύfun | A.a₁ => D.d₁ | A.aβ‚‚ => D.dβ‚‚ | A.a₃ => D.dβ‚„ | A.aβ‚„ => D.d₁ | A.aβ‚… => D.dβ‚… | A.a₆ => D.d₃ }

The two graphs are isomorphic, with an isomorphism between them given by f below.

def f : graph_L ⟢ graph_R := { val := ( β†Ύfun -- maps arrows | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁ , β†Ύfun -- maps dots | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚ ) property := ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toSrc = graph_R.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1 ∧ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt = graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1 ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toSrc = graph_R.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt = graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1 all_goals x:graph_L.carrierA⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun x = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun x; ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.aβ‚ƒβŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.aβ‚„ = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.aβ‚„βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.aβ‚… = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.aβ‚…βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.a₆ = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.a₆ ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.aβ‚ƒβŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.aβ‚„ = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.aβ‚„βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.aβ‚… = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.aβ‚…βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).2 ⊚ graph_L.toTgt)).toFun A.a₆ = (ConcreteCategory.hom (graph_R.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₃ | A.aβ‚‚ => A.aβ‚„ | A.a₃ => A.aβ‚… | A.aβ‚„ => A.a₆ | A.aβ‚… => A.aβ‚‚ | A.a₆ => A.a₁, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚„ | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚… | D.dβ‚… => D.dβ‚‚).1)).toFun A.a₆ All goals completed! πŸ™ } def finv : graph_R ⟢ graph_L := { val := ( β†Ύfun -- maps arrows | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun -- maps dots | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„ ) property := ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toSrc = graph_L.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1 ∧ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt = graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1 ⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toSrc = graph_L.toSrc ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1⊒ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt = graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1 all_goals x:graph_R.carrierA⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun x = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun x; ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.aβ‚ƒβŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.aβ‚„ = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.aβ‚„βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.aβ‚… = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.aβ‚…βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.a₆ = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.a₆ ⊒ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.a₁ = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.aβ‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.aβ‚‚ = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.aβ‚‚βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.a₃ = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.aβ‚ƒβŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.aβ‚„ = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.aβ‚„βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.aβ‚… = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.aβ‚…βŠ’ (ConcreteCategory.hom ((β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).2 ⊚ graph_R.toTgt)).toFun A.a₆ = (ConcreteCategory.hom (graph_L.toTgt ⊚ (β†Ύfun x ↦ match x with | A.a₁ => A.a₆ | A.aβ‚‚ => A.aβ‚… | A.a₃ => A.a₁ | A.aβ‚„ => A.aβ‚‚ | A.aβ‚… => A.a₃ | A.a₆ => A.aβ‚„, β†Ύfun x ↦ match x with | D.d₁ => D.d₃ | D.dβ‚‚ => D.dβ‚… | D.d₃ => D.d₁ | D.dβ‚„ => D.dβ‚‚ | D.dβ‚… => D.dβ‚„).1)).toFun A.a₆ All goals completed! πŸ™ } example : graph_L β‰… graph_R := { hom := f, inv := finv, hom_inv_id := ⊒ finv ⊚ f = πŸ™ graph_L h₁:(↑finv).1 ⊚ (↑f).1 = πŸ™ graph_L.carrierA ∧ (↑finv).2 ⊚ (↑f).2 = πŸ™ graph_L.carrierD⊒ finv ⊚ f = πŸ™ graph_L h₁:(↑finv).1 ⊚ (↑f).1 = πŸ™ graph_L.carrierA ∧ (↑finv).2 ⊚ (↑f).2 = πŸ™ graph_L.carrierDhβ‚‚:((↑finv).1 ⊚ (↑f).1, (↑finv).2 ⊚ (↑f).2) = (πŸ™ graph_L.carrierA, πŸ™ graph_L.carrierD)⊒ finv ⊚ f = πŸ™ graph_L All goals completed! πŸ™, inv_hom_id := ⊒ f ⊚ finv = πŸ™ graph_R h₁:(↑f).1 ⊚ (↑finv).1 = πŸ™ graph_R.carrierA ∧ (↑f).2 ⊚ (↑finv).2 = πŸ™ graph_R.carrierD⊒ f ⊚ finv = πŸ™ graph_R h₁:(↑f).1 ⊚ (↑finv).1 = πŸ™ graph_R.carrierA ∧ (↑f).2 ⊚ (↑finv).2 = πŸ™ graph_R.carrierDhβ‚‚:((↑f).1 ⊚ (↑finv).1, (↑f).2 ⊚ (↑finv).2) = (πŸ™ graph_R.carrierA, πŸ™ graph_R.carrierD)⊒ f ⊚ finv = πŸ™ graph_R All goals completed! πŸ™ }
Exercise 8 (p. 160)

(Impossible journeys) J is the graph

inductive A | a₁ | aβ‚‚ | a₃ abbrev D := Fin 2 def J : IrreflexiveGraph := { carrierA := A carrierD := D toSrc := β†Ύfun | A.a₁ => 0 | A.aβ‚‚ => 1 | A.a₃ => 1 toTgt := β†Ύfun | A.a₁ => 0 | A.aβ‚‚ => 0 | A.a₃ => 1 }

G is any graph, and b and e are dots of G.

variable (G : IrreflexiveGraph) (b e : G.carrierD)

(a) Suppose that {G \xrightarrow{f} J} is a map of graphs with {fb = 0} and {fe = 1}. Show that there is no path in G that begins at b and ends at e.

(b) Conversely, suppose that there is no path in G that begins at b and ends at e. Show that there is a map {G \xrightarrow{f} J} with {fb = 0} and {fe = 1}.

Solution: Exercise 8

TODO Exercise 11.8