Quiz
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! 🐙
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 2
variable {𝒞 : 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 := by 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ ((p ⊚ q) ⊚ p) ⊚ q = (p ⊚ q ⊚ p) ⊚ q rw [← Category.assoc p 𝒞: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 := by 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (p ⊚ q ⊚ p) ⊚ q = p ⊚ q rw [hpq 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ p ⊚ q = p ⊚ q] All goals completed! 🐙
}
We show that {q \circ p} is idempotent.
example : IsIdempotent (q ⊚ p) := {
idem := by 𝒞: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 := by 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p) ⊚ q ⊚ p = q ⊚ p ⊚ q ⊚ p rw [Category.assoc (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 := by 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ q ⊚ p ⊚ q ⊚ p = q ⊚ p rw [hpq 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ q ⊚ p = q ⊚ p] All goals completed! 🐙
}
Optional questions
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' := by 𝒞: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'
use q ⊚ p ⊚ q h 𝒞: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'
constructor h.left 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ p ⊚ (q ⊚ p ⊚ q) ⊚ p = ph.right 𝒞: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
· h.left 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ p ⊚ (q ⊚ p ⊚ q) ⊚ p = p rw [← Category.assoc p, h.left 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ p ⊚ q ⊚ (p ⊚ q) ⊚ p = p ← Category.assoc, h.left 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ p ⊚ q ⊚ p ⊚ q ⊚ p = p hpq, h.left 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ p ⊚ q ⊚ p = p hpq h.left 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ p = p] All goals completed! 🐙
· h.right 𝒞: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 rw [Category.assoc (q ⊚ p ⊚ q) h.right 𝒞: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] h.right 𝒞: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 rw [← Category.assoc p h.right 𝒞: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] h.right 𝒞: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 h.right 𝒞: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
rw [hpq h.right 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p) ⊚ q ⊚ p ⊚ q = q ⊚ p ⊚ q] h.right 𝒞: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 rw [Category.assoc q h.right 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p) ⊚ (q ⊚ p) ⊚ q = (q ⊚ p) ⊚ q] h.right 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p) ⊚ (q ⊚ p) ⊚ q = (q ⊚ p) ⊚ q h.right 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ ((q ⊚ p) ⊚ q ⊚ p) ⊚ q = (q ⊚ p) ⊚ q
rw [← Category.assoc (q ⊚ p), h.right 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p ⊚ q ⊚ p) ⊚ q = (q ⊚ p) ⊚ q hpq h.right 𝒞:Type uinst✝:Category.{v, u} 𝒞C:𝒞D:𝒞p:C ⟶ Dq:D ⟶ Chpq:p ⊚ q ⊚ p = p⊢ (q ⊚ p) ⊚ q = (q ⊚ p) ⊚ q] All goals completed! 🐙
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 := by ⊢ IsRetraction f
use r id ⊢ autoParam (r ⊚ f = 𝟙 A) SplitMono.id._autoParam
change r ⊚ f = 𝟙 A id ⊢ r ⊚ f = 𝟙 A
ext x id x:A⊢ (ConcreteCategory.hom (r ⊚ f)).toFun x = (ConcreteCategory.hom (𝟙 A)).toFun x
dsimp [f, r] id x:A⊢ ⌊|match x with
| 0 => 0
| Nat.succ n => ↑n + 1|⌋₊ =
x
induction x with
| zero => id.zero ⊢ ⌊|match Nat.zero with
| 0 => 0
| Nat.succ n => ↑n + 1|⌋₊ =
Nat.zero rw [abs_zero, id.zero ⊢ ⌊0⌋₊ = Nat.zero Nat.floor_zero id.zero ⊢ 0 = Nat.zero] All goals completed! 🐙
| succ n => id.succ 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
dsimp id.succ n:ℕn_ih✝:⌊|match n with
| 0 => 0
| Nat.succ n => ↑n + 1|⌋₊ =
n⊢ ⌊|↑n + 1|⌋₊ = n + 1
norm_cast id.succ n:ℕn_ih✝:⌊|match n with
| 0 => 0
| Nat.succ n => ↑n + 1|⌋₊ =
n⊢ ⌊↑(n + 1)⌋₊ = n + 1
rw [Nat.floor_natCast id.succ 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) := by ⊢ ¬IsSection f
by_contra h h:IsSection f⊢ False
obtain ⟨s, hs⟩ := h s:B ⟶ Ahs:f ⊚ s = 𝟙 B⊢ False
have h_false := congr_hom hs 0.5 s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom (f ⊚ s)) 0.5 = (hom (𝟙 B)) 0.5⊢ False
cases hx : s 0.5 with
| zero => zero s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom (f ⊚ s)) 0.5 = (hom (𝟙 B)) 0.5hx:(hom s) 0.5 = Nat.zero⊢ False
rw [types_comp_apply, zero s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom f) ((hom s) 0.5) = (hom (𝟙 B)) 0.5hx:(hom s) 0.5 = Nat.zero⊢ False hx zero s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom f) Nat.zero = (hom (𝟙 B)) 0.5hx:(hom s) 0.5 = Nat.zero⊢ False] at h_false zero s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom f) Nat.zero = (hom (𝟙 B)) 0.5hx:(hom s) 0.5 = Nat.zero⊢ False
dsimp [f] at h_false zero s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:0 = 0.5hx:(hom s) 0.5 = Nat.zero⊢ False
linarith All goals completed! 🐙
| succ n => succ s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom (f ⊚ s)) 0.5 = (hom (𝟙 B)) 0.5n:ℕhx:(hom s) 0.5 = n.succ⊢ False
rw [types_comp_apply, succ s:B ⟶ Ahs:f ⊚ s = 𝟙 Bh_false:(hom f) ((hom s) 0.5) = (hom (𝟙 B)) 0.5n:ℕhx:(hom s) 0.5 = n.succ⊢ False hx succ s:B ⟶ Ahs:f ⊚ s = 𝟙 Bn:ℕh_false:(hom f) n.succ = (hom (𝟙 B)) 0.5hx:(hom s) 0.5 = n.succ⊢ False] at h_false succ s:B ⟶ Ahs:f ⊚ s = 𝟙 Bn:ℕh_false:(hom f) n.succ = (hom (𝟙 B)) 0.5hx:(hom s) 0.5 = n.succ⊢ False
dsimp [f] at h_false succ s:B ⟶ Ahs:f ⊚ s = 𝟙 Bn:ℕh_false:↑n + 1 = 0.5hx:(hom s) 0.5 = n.succ⊢ False
have h_ge_1 : (1 : B) ≤ n + 1 := by ⊢ ¬IsSection f linarith succ s:B ⟶ Ahs:f ⊚ s = 𝟙 Bn:ℕh_false:↑n + 1 = 0.5hx:(hom s) 0.5 = n.succh_ge_1:1 ≤ ↑n + 1⊢ False
linarith All goals completed! 🐙