A Lean Companion to Conceptual Mathematics

Quiz🔗

Problem 1 (p. 108)

Give an example of two explicit sets A and B and an explicit map {A \xrightarrow{f} B} satisfying both:

(a) there is a retraction for f, and

(b) there is no section for f.

Then explain how you know that f satisfies (a) and (b).

Solution: Problem 1

We use Fintypes here instead of sets.

We give explicit types A and B and an explicit map f.

set_option backward.isDefEq.respectTransparency false in inductive A | a deriving Fintype set_option backward.isDefEq.respectTransparency false in inductive B | b₁ | b₂ deriving Fintype def f : A ⟶ B := ↾fun | A.a => B.b₁

Our candidate retraction for f is

def r : B ⟶ A := ↾fun | B.b₁ => A.a | B.b₂ => A.a

and we show that (a) is satisfied.

example : IsRetraction f := ⊢ IsRetraction f ⊢ autoParam (r ⊚ f = 𝟙 A) SplitMono.id._autoParam ⊢ r ⊚ f = 𝟙 A x:A⊢ (ConcreteCategory.hom (r ⊚ f)).toFun x = (ConcreteCategory.hom (𝟙 A)).toFun x ⊢ (ConcreteCategory.hom (r ⊚ f)).toFun A.a = (ConcreteCategory.hom (𝟙 A)).toFun A.a All goals completed! 🐙

We show that f also satisfies (b).

open ConcreteCategory in example : ¬(IsSection f) := ⊢ ¬IsSection f h:IsSection f⊢ False s:B ⟶ Ahs:f ⊚ s = 𝟙 B⊢ False s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom (f ⊚ s)) B.b₂ = (hom (𝟙 B)) B.b₂⊢ False All goals completed! 🐙
Problem 2 (p. 108)

If {C \xrightarrow{p} D \xrightarrow{q} C} satisfy {p \circ q \circ p = p}, can you conclude that

(a) {p \circ q} is idempotent? If so, how?

(b) {q \circ p} is idempotent? If so, how?

Solution: Problem 2variable {𝒞 : Type u} [Category.{v, u} 𝒞] {C D : 𝒞} (p : C ⟶ D) (q : D ⟶ C) (hpq : p ⊚ q ⊚ p = p)

We show that {p \circ q} is idempotent.

example : IsIdempotent (p ⊚ q) := { idem := 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (p ⊚ q) ⊚ p ⊚ q = p ⊚ q calc (p ⊚ q) ⊚ p ⊚ q _ = ((p ⊚ q) ⊚ p) ⊚ q := 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (p ⊚ q) ⊚ p ⊚ q = ((p ⊚ q) ⊚ p) ⊚ q All goals completed! 🐙 _ = (p ⊚ q ⊚ p) ⊚ q := 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ ((p ⊚ q) ⊚ p) ⊚ q = (p ⊚ q ⊚ p) ⊚ q All goals completed! 🐙 _ = p ⊚ q := 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (p ⊚ q ⊚ p) ⊚ q = p ⊚ q All goals completed! 🐙 }

We show that {q \circ p} is idempotent.

example : IsIdempotent (q ⊚ p) := { idem := 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p) ⊚ q ⊚ p = q ⊚ p calc (q ⊚ p) ⊚ q ⊚ p _ = q ⊚ p ⊚ q ⊚ p := 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p) ⊚ q ⊚ p = q ⊚ p ⊚ q ⊚ p All goals completed! 🐙 _ = q ⊚ p := 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ q ⊚ p ⊚ q ⊚ p = q ⊚ p All goals completed! 🐙 }

Optional questions🔗

Problem 2* (p. 108)

If {C \xrightarrow{p} D \xrightarrow{q} C} satisfy {p \circ q \circ p = p}, use the given maps p and q to devise a map q' satisfying both: p \circ q' \circ p = p and q' \circ p \circ q' = q' (and explain how you know that your q' has these properties).

Solution: Problem 2*variable {𝒞 : Type u} [Category.{v, u} 𝒞] {C D : 𝒞} (p : C ⟶ D) (q : D ⟶ C) (hpq : p ⊚ q ⊚ p = p)

We show that {q' = q \circ p \circ q} has the required properties.

example : ∃ q', p ⊚ q' ⊚ p = p ∧ q' ⊚ p ⊚ q' = q' := 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ ∃ q', p ⊚ q' ⊚ p = p ∧ q' ⊚ p ⊚ q' = q' 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ p ⊚ (q ⊚ p ⊚ q) ⊚ p = p ∧ (q ⊚ p ⊚ q) ⊚ p ⊚ q ⊚ p ⊚ q = q ⊚ p ⊚ q -- q' 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ p ⊚ (q ⊚ p ⊚ q) ⊚ p = p𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p ⊚ q) ⊚ p ⊚ q ⊚ p ⊚ q = q ⊚ p ⊚ q 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ p ⊚ (q ⊚ p ⊚ q) ⊚ p = p All goals completed! 🐙 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p ⊚ q) ⊚ p ⊚ q ⊚ p ⊚ q = q ⊚ p ⊚ q 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ ((q ⊚ p ⊚ q) ⊚ p) ⊚ q ⊚ p ⊚ q = q ⊚ p ⊚ q repeat 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p ⊚ q ⊚ p) ⊚ q ⊚ p ⊚ q = q ⊚ p ⊚ q 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p) ⊚ q ⊚ p ⊚ q = q ⊚ p ⊚ q repeat 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ ((q ⊚ p) ⊚ q ⊚ p) ⊚ q = (q ⊚ p) ⊚ q All goals completed! 🐙
Problem 1* (p. 108)

Same question as Problem 1 at top of page, except that both sets A and B are required to be infinite sets.

Solution: Problem 1*

We use (non-finite) types here instead of infinite sets.

We give explicit types A and B and an explicit map f.

abbrev A := ℕ abbrev B := ℝ def f : A ⟶ B := ↾fun | 0 => 0 | n + 1 => n + 1

Our candidate retraction for f is

noncomputable def r : B ⟶ A := ↾fun | r => ⌊abs r⌋₊

and we show that (a) is satisfied.

example : IsRetraction f := ⊢ IsRetraction f ⊢ autoParam (r ⊚ f = 𝟙 A) SplitMono.id._autoParam ⊢ r ⊚ f = 𝟙 A x:A⊢ (ConcreteCategory.hom (r ⊚ f)).toFun x = (ConcreteCategory.hom (𝟙 A)).toFun x x:A⊢ ⌊|match x with | 0 => 0 | Nat.succ n => ↑n + 1|⌋₊ = x induction x with ⊢ ⌊|match Nat.zero with | 0 => 0 | Nat.succ n => ↑n + 1|⌋₊ = Nat.zero All goals completed! 🐙 n:ℕn_ih✝:⌊|match n with | 0 => 0 | Nat.succ n => ↑n + 1|⌋₊ = n⊢ ⌊|match n.succ with | 0 => 0 | Nat.succ n => ↑n + 1|⌋₊ = n.succ n:ℕn_ih✝:⌊|match n with | 0 => 0 | Nat.succ n => ↑n + 1|⌋₊ = n⊢ ⌊|↑n + 1|⌋₊ = n + 1 n:ℕn_ih✝:⌊|match n with | 0 => 0 | Nat.succ n => ↑n + 1|⌋₊ = n⊢ ⌊↑(n + 1)⌋₊ = n + 1 All goals completed! 🐙

We show that f also satisfies (b).

open ConcreteCategory in example : ¬(IsSection f) := ⊢ ¬IsSection f h:IsSection f⊢ False s:B ⟶ Ahs:f ⊚ s = 𝟙 B⊢ False s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom (f ⊚ s)) 0.5 = (hom (𝟙 B)) 0.5⊢ False cases hx : s 0.5 with s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom (f ⊚ s)) 0.5 = (hom (𝟙 B)) 0.5hx:(hom s) 0.5 = Nat.zero⊢ False s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom f) Nat.zero = (hom (𝟙 B)) 0.5hx:(hom s) 0.5 = Nat.zero⊢ False s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:0 = 0.5hx:(hom s) 0.5 = Nat.zero⊢ False All goals completed! 🐙 s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom (f ⊚ s)) 0.5 = (hom (𝟙 B)) 0.5n:ℕhx:(hom s) 0.5 = n.succ⊢ False s:B ⟶ Ahs:f ⊚ s = 𝟙 Bn:ℕh_false:(hom f) n.succ = (hom (𝟙 B)) 0.5hx:(hom s) 0.5 = n.succ⊢ False s:B ⟶ Ahs:f ⊚ s = 𝟙 Bn:ℕh_false:↑n + 1 = 0.5hx:(hom s) 0.5 = n.succ⊢ False s:B ⟶ Ahs:f ⊚ s = 𝟙 Bn:ℕh_false:↑n + 1 = 0.5hx:(hom s) 0.5 = n.succh_ge_1:1 ≤ ↑n + 1⊢ False All goals completed! 🐙