Article I: Sets, maps, composition
Until the introduction of the definition of category at the end of Article I, we implement all maps in the book as Lean functions.
Check to be sure you understand how we got diagrams (ii) and (iii) from the given diagram (i). Then fill in (iv) and (v) yourself, starting over from (i). Then check to see that (v) and (iii) are the same.
Solution: Exercise 1
For simplicity, we use types here instead of sets. We number the elements in each set/type from top to bottom (top left to bottom right for D).
inductive A
| aβ | aβ | aβ
inductive B
| bβ | bβ | bβ | bβ
inductive C
| cβ | cβ | cβ | cβ | cβ
inductive D
| dβ | dβ | dβ | dβ | dβ
| dβ
def f : A β B
| A.aβ => B.bβ
| A.aβ => B.bβ
| A.aβ => B.bβ
def g : B β C
| B.bβ => C.cβ
| B.bβ => C.cβ
| B.bβ => C.cβ
| B.bβ => C.cβ
def h : C β D
| C.cβ => D.dβ
| C.cβ => D.dβ
| C.cβ => D.dβ
| C.cβ => D.dβ
| C.cβ
=> D.dβ
For diagram (iv), we have f as above and {h \circ g} as follows:
def hg : B β D
| B.bβ => D.dβ
| B.bβ => D.dβ
| B.bβ => D.dβ
| B.bβ => D.dβ
example : hg = h β g := β’ hg = h β g
x:Bβ’ hg x = (h β g) x
β’ hg B.bβ = (h β g) B.bββ’ hg B.bβ = (h β g) B.bββ’ hg B.bβ = (h β g) B.bββ’ hg B.bβ = (h β g) B.bβ β’ hg B.bβ = (h β g) B.bββ’ hg B.bβ = (h β g) B.bββ’ hg B.bβ = (h β g) B.bββ’ hg B.bβ = (h β g) B.bβ All goals completed! π
For diagram (v), we have {(h \circ g) \circ f} as follows, which is indeed the same as {h \circ (g \circ f)} in diagram (iii):
def hgf : A β D
| A.aβ => D.dβ
| A.aβ => D.dβ
| A.aβ => D.dβ
example : hgf = (h β g) β f := β’ hgf = (h β g) β f
x:Aβ’ hgf x = ((h β g) β f) x
β’ hgf A.aβ = ((h β g) β f) A.aββ’ hgf A.aβ = ((h β g) β f) A.aββ’ hgf A.aβ = ((h β g) β f) A.aβ β’ hgf A.aβ = ((h β g) β f) A.aββ’ hgf A.aβ = ((h β g) β f) A.aββ’ hgf A.aβ = ((h β g) β f) A.aβ All goals completed! π
One very useful sort of set is a 'singleton' set, a set with exactly one element.... Call this set '\mathbf{1}'.
We define \mathbf{1} in Lean as the finite set containing the single element of type Unit.
namespace CM_Finset
def One : Finset Unit := Finset.univ
end CM_Finset
A point of a set X is a map {\mathbf{1} \rightarrow X}.
We define Point in Lean as a Map between Finsets. (The coercion allows a term inhabiting Map to be used directly as a function, so we can write f, John, and eggs below rather than f.toFun, John.toFun, and eggs.toFun.)
namespace CM_Finset
structure Map {Ξ± Ξ² : Type*} (X : Finset Ξ±) (Y : Finset Ξ²) where
toFun : Ξ± β Ξ²
maps_to_codomain : β a : Ξ±, a β X β toFun a β Y
instance {Ξ± Ξ² : Type*} (X : Finset Ξ±) (Y : Finset Ξ²)
: CoeFun (Map X Y) (fun _ β¦ Ξ± β Ξ²) where
coe F := F.toFun
abbrev Point {Ξ² : Type*} (Y : Finset Ξ²) := Map One Y
end CM_Finset
Since a point is a map, we can compose it with another map, and get a point again.
We provide a Lean implementation below of the example given in the book on p. 19.
namespace CM_Finset
def A : Finset String := { "John", "Mary", "Sam" }
def B : Finset String := { "eggs", "coffee" }
def John : Point A := {
toFun := fun _ β¦ "John"
maps_to_codomain := β’ β a β One, "John" β A All goals completed! π
}
def f : Map A B := {
toFun
| "John" => "eggs"
| "Mary" => "eggs"
| _ => "coffee"
maps_to_codomain := β’ β a β A,
(match a with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") β
B
aβ:Stringha:aβ β Aβ’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") β
B
aβ:Stringha:aβ β {"John", "Mary", "Sam"}β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") β
{"eggs", "coffee"}
repeat aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ β {"Sam"}β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") β
{"coffee"}
rw [Finset.mem_singleton aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"] at * aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"
rcases ha with ha | ha | ha inl aβ:Stringha:aβ = "John"β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"inr.inl aβ:Stringha:aβ = "Mary"β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"inr.inr aβ:Stringha:aβ = "Sam"β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"
all_goals
subst ha inr.inr β’ (match "Sam" with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match "Sam" with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"
first | exact Or.inl rfl inr.inr β’ (match "Sam" with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match "Sam" with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee" | exact Or.inr rfl All goals completed! π
}
def eggs : Point B := {
toFun := fun _ β¦ "eggs"
maps_to_codomain := by β’ β a β One, "eggs" β B simp [B] All goals completed! π
}
example : f β John = eggs := rfl
end CM_Finset
Replacing Finset with Set broadens the application to any set, not just finite sets.
namespace CM_Set
def One : Set Unit := Set.univ
structure Map {Ξ± Ξ² : Type*} (X : Set Ξ±) (Y : Set Ξ²) where
toFun : Ξ± β Ξ²
maps_to_codomain : β a : Ξ±, a β X β toFun a β Y
instance {Ξ± Ξ² : Type*} (X : Set Ξ±) (Y : Set Ξ²)
: CoeFun (Map X Y) (fun _ β¦ Ξ± β Ξ²) where
coe F := F.toFun
abbrev Point {Ξ² : Type*} (Y : Set Ξ²) := Map One Y
def A : Set String := { "John", "Mary", "Sam" }
def B : Set String := { "eggs", "coffee" }
def John : Point A := {
toFun := fun _ β¦ "John"
maps_to_codomain := by β’ β a β One, "John" β A simp [A] All goals completed! π
}
def f : Map A B := {
toFun
| "John" => "eggs"
| "Mary" => "eggs"
| _ => "coffee"
maps_to_codomain := by β’ β a β A,
(match a with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") β
B
intro _ ha aβ:Stringha:aβ β Aβ’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") β
B
dsimp [A, B] at * aβ:Stringha:aβ β {"John", "Mary", "Sam"}β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") β
{"eggs", "coffee"}
repeat rw [Set.mem_insert_iff aβ:Stringha:aβ = "John" β¨ aβ β {"Mary", "Sam"}β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") β
{"coffee"}] aβ:Stringha:aβ = "John" β¨ aβ β {"Mary", "Sam"}β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") β
{"coffee"} at * aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ β {"Sam"}β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") β
{"coffee"}
rw [Set.mem_singleton_iff aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"] at * aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"
rcases ha with ha | ha | ha inl aβ:Stringha:aβ = "John"β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"inr.inl aβ:Stringha:aβ = "Mary"β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"inr.inr aβ:Stringha:aβ = "Sam"β’ (match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"
all_goals
subst ha inr.inr β’ (match "Sam" with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match "Sam" with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee"
first | exact Or.inl rfl inr.inr β’ (match "Sam" with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"eggs" β¨
(match "Sam" with
| "John" => "eggs"
| "Mary" => "eggs"
| x => "coffee") =
"coffee" | exact Or.inr rfl All goals completed! π
}
def eggs : Point B := {
toFun := fun _ β¦ "eggs"
maps_to_codomain := by β’ β a β One, "eggs" β B simp [B] All goals completed! π
}
example : f β John = eggs := rfl
end CM_Set
Using types instead of sets is cleaner and further broadens the application to any type, not just sets.
abbrev One := Unit
namespace CM_Type
def Point (Y : Type) := One β Y
def A := { a : String // a = "John" β¨ a = "Mary" β¨ a = "Sam" }
def B := { b : String // b = "eggs" β¨ b = "coffee" }
def John : Point A := fun _ β¦ β¨"John", by xβ:Oneβ’ "John" = "John" β¨ "John" = "Mary" β¨ "John" = "Sam" simp All goals completed! πβ©
def f : A β B := fun a β¦
match a.val with
| "John" => β¨"eggs", by a:Aβ’ "eggs" = "eggs" β¨ "eggs" = "coffee" simp All goals completed! πβ©
| "Mary" => β¨"eggs", by a:Aβ’ "eggs" = "eggs" β¨ "eggs" = "coffee" simp All goals completed! πβ©
| _ => β¨"coffee", by a:Axβ:Stringβ’ "coffee" = "eggs" β¨ "coffee" = "coffee" simp All goals completed! πβ©
def eggs : Point B := fun _ β¦ β¨"eggs", by xβ:Oneβ’ "eggs" = "eggs" β¨ "eggs" = "coffee" simp All goals completed! πβ©
example : f β John = eggs := rfl
end CM_Type
We lift our definition for the function Point between types to the morphism Point in the category Type for later use. Note the application of βΆ (\hom) for the morphism type instead of β (\r) for the function arrow.
abbrev Point (Y : Type) := One βΆ Y
For Exercises 2β5 which follow, rather than providing exhaustive lists of maps, it seems more useful at this stage to introduce what the book calls Alysia's formula, even though that formula doesn't appear until slightly later (on pp. 33β34). The formula states that the number of different maps between two finite sets is equal to the number of elements in the codomain raised to the power of the number of elements in the domain β that is, the number of maps is {(\#\beta)^{(\#\alpha)}}, where {\#\alpha} is the size of the domain \alpha and {\#\beta} is the size of the codomain \beta.
def Alysia's_formula (Ξ± Ξ² : Type*) [Fintype Ξ±] [Fintype Ξ²] : β :=
Fintype.card Ξ² ^ Fintype.card Ξ±
How many different maps f are there with domain A and codomain B?
Solution: Exercise 2
By Alysia's formula, we have {(\#B)^{(\#A)} = 2^3 = 8} different maps.
open CM_Finset
#eval Alysia's_formula A B
Same, but for maps {A \xrightarrow{f} A}?
Solution: Exercise 3
By Alysia's formula, we have {(\#A)^{(\#A)} = 3^3 = 27} different maps.
open CM_Finset
#eval Alysia's_formula A A
Same, but for maps {B \xrightarrow{f} A}?
Solution: Exercise 4
By Alysia's formula, we have {(\#A)^{(\#B)} = 3^2 = 9} different maps.
open CM_Finset
#eval Alysia's_formula B A
Same, but for maps {B \xrightarrow{f} B}?
Solution: Exercise 5
By Alysia's formula, we have {(\#B)^{(\#B)} = 2^2 = 4} different maps.
open CM_Finset
#eval Alysia's_formula B B
Exercises 6 and 7 concern idempotence, which the book formally introduces later on p. 54. For the purpose of these two exercises (and again aiming to avoid exhaustive lists of maps), we introduce the formula
\sum_{k=0}^{n} {n \choose k} k^{n-k}
for the total number of possible idempotents on a finite set. (See the Wikipedia article on idempotence for additional information.)
def idempotentCount (Ξ± : Type) [Fintype Ξ±] : β :=
let n := Fintype.card Ξ±
β k β Finset.range (n + 1), (n.choose k) * k ^ (n - k)
How many maps {A \xrightarrow{f} A} satisfy {f \circ f = f}?
Solution: Exercise 6
By the formula above, we have 10 different maps.
open CM_Finset
#eval idempotentCount A
How many maps {B \xrightarrow{g} B} satisfy {g \circ g = g}?
Solution: Exercise 7
By the formula above, we have 3 different maps.
open CM_Finset
#eval idempotentCount B
Can you find a pair of maps {A \xrightarrow{f} B \xrightarrow{g} A} for which {g \circ f = 1_A}? If so, how many such pairs?
Solution: Exercise 8
No such pair exists, since the image of 1_A has 3 elements, but the image of {g \circ f} has only 2 elements.
open CM_Finset
We will begin using the Lean notation π X, for the identity morphism on X, after we finish Article I and start working with morphisms and categories; for now, though, since we are still operating with functions and sets, we must define the identity map on A explicitly.
def idA : Map A A := {
toFun := id
maps_to_codomain := by β’ β a β A, id a β A
intro _ ha aβ:Stringha:aβ β Aβ’ id aβ β A
dsimp [A] at * aβ:Stringha:aβ β {"John", "Mary", "Sam"}β’ aβ β {"John", "Mary", "Sam"}
repeat rw [Finset.mem_insert aβ:Stringha:aβ = "John" β¨ aβ β {"Mary", "Sam"}β’ aβ = "John" β¨ aβ β {"Mary", "Sam"}] aβ:Stringha:aβ = "John" β¨ aβ β {"Mary", "Sam"}β’ aβ = "John" β¨ aβ β {"Mary", "Sam"} at * aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ β {"Sam"}β’ aβ = "John" β¨ aβ = "Mary" β¨ aβ β {"Sam"}
rw [Finset.mem_singleton aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"β’ aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"] at * aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"β’ aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"
rcases ha with ha | ha | ha inl aβ:Stringha:aβ = "John"β’ aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"inr.inl aβ:Stringha:aβ = "Mary"β’ aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"inr.inr aβ:Stringha:aβ = "Sam"β’ aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"
all_goals
subst ha inr.inr β’ "Sam" = "John" β¨ "Sam" = "Mary" β¨ "Sam" = "Sam"
first
| exact Or.inl rfl inr.inr β’ "Sam" = "John" β¨ "Sam" = "Mary" β¨ "Sam" = "Sam"
| exact Or.inr (Or.inl rfl) inr.inr β’ "Sam" = "John" β¨ "Sam" = "Mary" β¨ "Sam" = "Sam"
| exact Or.inr (Or.inr rfl) All goals completed! π
}
open Finset in
example : Β¬(β f : Map A B, β g : Map B A, g β f = idA) := by β’ Β¬β f g, g.toFun β f.toFun = idA.toFun
-- Convert to the equivalent statement β f g, g β f β idA
push Not β’ β (f : Map A B) (g : Map B A), g.toFun β f.toFun β idA.toFun
-- Assume that g β f = idA for some f, g, and derive a contradiction
intro f g h_eq f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunβ’ False
-- Since the functions g β f and idA are equal, so are their images
have h_img_eq
: (image g (image f A)).card = (image idA A).card := by β’ Β¬β f g, g.toFun β f.toFun = idA.toFun
rw [image_image, f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunβ’ #(image (g.toFun β f.toFun) A) = #(image idA.toFun A) h_eq f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunβ’ #(image idA.toFun A) = #(image idA.toFun A)] f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)β’ False
-- But the image of g(f(A)) has at most 2 elements,
have h_card_gfA : (image g (image f A)).card β€ 2 := by β’ Β¬β f g, g.toFun β f.toFun = idA.toFun
apply le_trans a f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)β’ #(image g.toFun (image f.toFun A)) β€ ?ba f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)β’ ?b β€ 2b f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)β’ β
Β· a f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)β’ #(image g.toFun (image f.toFun A)) β€ ?b exact card_image_le All goals completed! π
Β· a f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)β’ #(image f.toFun A) β€ 2 change (image f A).card β€ B.card a f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)β’ #(image f.toFun A) β€ #B
apply card_le_card a f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)β’ image f.toFun A β B
intro _ hfa a f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)xβ:Stringhfa:xβ β image f.toFun Aβ’ xβ β B
rw [mem_image a f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)xβ:Stringhfa:β a β A, f.toFun a = xββ’ xβ β B] at hfa a f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)xβ:Stringhfa:β a β A, f.toFun a = xββ’ xβ β B
obtain β¨a, ha, rflβ© := hfa a f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)a:Stringha:a β Aβ’ f.toFun a β B
exact f.maps_to_codomain a ha f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)h_card_gfA:#(image g.toFun (image f.toFun A)) β€ 2β’ False
-- while the image of idA(A) has 3 elements
have h_card_idA : (image idA A).card = 3 := rfl f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)h_card_gfA:#(image g.toFun (image f.toFun A)) β€ 2h_card_idA:#(image idA.toFun A) = 3β’ False
-- So we have a contradiction
rw [h_img_eq, f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)h_card_gfA:#(image idA.toFun A) β€ 2h_card_idA:#(image idA.toFun A) = 3β’ False h_card_idA f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)h_card_gfA:3 β€ 2h_card_idA:#(image idA.toFun A) = 3β’ False] at h_card_gfA f:Map A Bg:Map B Ah_eq:g.toFun β f.toFun = idA.toFunh_img_eq:#(image g.toFun (image f.toFun A)) = #(image idA.toFun A)h_card_gfA:3 β€ 2h_card_idA:#(image idA.toFun A) = 3β’ False
contradiction All goals completed! π
Can you find a pair of maps {B \xrightarrow{h} A \xrightarrow{k} B} for which {k \circ h = 1_B}? If so, how many such pairs?
Solution: Exercise 9
We define one pair h, k.
open CM_Finset
def h : Map B A := {
toFun
| "eggs" => "John"
| _ => "Mary"
maps_to_codomain := by β’ β a β B,
(match a with
| "eggs" => "John"
| x => "Mary") β
A
intro _ hb aβ:Stringhb:aβ β Bβ’ (match aβ with
| "eggs" => "John"
| x => "Mary") β
A
dsimp [A, B] at * aβ:Stringhb:aβ β {"eggs", "coffee"}β’ (match aβ with
| "eggs" => "John"
| x => "Mary") β
{"John", "Mary", "Sam"}
repeat rw [Finset.mem_insert aβ:Stringhb:aβ = "eggs" β¨ aβ β {"coffee"}β’ (match aβ with
| "eggs" => "John"
| x => "Mary") =
"John" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") β
{"Mary", "Sam"}] aβ:Stringhb:aβ = "eggs" β¨ aβ β {"coffee"}β’ (match aβ with
| "eggs" => "John"
| x => "Mary") =
"John" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") β
{"Mary", "Sam"} at * aβ:Stringhb:aβ = "eggs" β¨ aβ β {"coffee"}β’ (match aβ with
| "eggs" => "John"
| x => "Mary") =
"John" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") =
"Mary" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") β
{"Sam"}
rw [Finset.mem_singleton aβ:Stringhb:aβ = "eggs" β¨ aβ = "coffee"β’ (match aβ with
| "eggs" => "John"
| x => "Mary") =
"John" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") =
"Mary" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") =
"Sam"] at * aβ:Stringhb:aβ = "eggs" β¨ aβ = "coffee"β’ (match aβ with
| "eggs" => "John"
| x => "Mary") =
"John" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") =
"Mary" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") =
"Sam"
rcases hb with hb | hb inl aβ:Stringhb:aβ = "eggs"β’ (match aβ with
| "eggs" => "John"
| x => "Mary") =
"John" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") =
"Mary" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") =
"Sam"inr aβ:Stringhb:aβ = "coffee"β’ (match aβ with
| "eggs" => "John"
| x => "Mary") =
"John" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") =
"Mary" β¨
(match aβ with
| "eggs" => "John"
| x => "Mary") =
"Sam"
all_goals
subst hb inr β’ (match "coffee" with
| "eggs" => "John"
| x => "Mary") =
"John" β¨
(match "coffee" with
| "eggs" => "John"
| x => "Mary") =
"Mary" β¨
(match "coffee" with
| "eggs" => "John"
| x => "Mary") =
"Sam"
first | exact Or.inl rfl inr β’ (match "coffee" with
| "eggs" => "John"
| x => "Mary") =
"John" β¨
(match "coffee" with
| "eggs" => "John"
| x => "Mary") =
"Mary" β¨
(match "coffee" with
| "eggs" => "John"
| x => "Mary") =
"Sam" | exact Or.inr (Or.inl rfl) All goals completed! π
}
def k : Map A B := {
toFun
| "John" => "eggs"
| _ => "coffee"
maps_to_codomain := by β’ β a β A,
(match a with
| "John" => "eggs"
| x => "coffee") β
B
intro _ ha aβ:Stringha:aβ β Aβ’ (match aβ with
| "John" => "eggs"
| x => "coffee") β
B
dsimp [A, B] at * aβ:Stringha:aβ β {"John", "Mary", "Sam"}β’ (match aβ with
| "John" => "eggs"
| x => "coffee") β
{"eggs", "coffee"}
repeat rw [Finset.mem_insert aβ:Stringha:aβ = "John" β¨ aβ β {"Mary", "Sam"}β’ (match aβ with
| "John" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| x => "coffee") β
{"coffee"}] aβ:Stringha:aβ = "John" β¨ aβ β {"Mary", "Sam"}β’ (match aβ with
| "John" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| x => "coffee") β
{"coffee"} at * aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ β {"Sam"}β’ (match aβ with
| "John" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| x => "coffee") β
{"coffee"}
rw [Finset.mem_singleton aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"β’ (match aβ with
| "John" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| x => "coffee") =
"coffee"] at * aβ:Stringha:aβ = "John" β¨ aβ = "Mary" β¨ aβ = "Sam"β’ (match aβ with
| "John" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| x => "coffee") =
"coffee"
rcases ha with ha | ha | ha inl aβ:Stringha:aβ = "John"β’ (match aβ with
| "John" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| x => "coffee") =
"coffee"inr.inl aβ:Stringha:aβ = "Mary"β’ (match aβ with
| "John" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| x => "coffee") =
"coffee"inr.inr aβ:Stringha:aβ = "Sam"β’ (match aβ with
| "John" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "John" => "eggs"
| x => "coffee") =
"coffee"
all_goals
subst ha inr.inr β’ (match "Sam" with
| "John" => "eggs"
| x => "coffee") =
"eggs" β¨
(match "Sam" with
| "John" => "eggs"
| x => "coffee") =
"coffee"
first | exact Or.inl rfl inr.inr β’ (match "Sam" with
| "John" => "eggs"
| x => "coffee") =
"eggs" β¨
(match "Sam" with
| "John" => "eggs"
| x => "coffee") =
"coffee" | exact Or.inr rfl All goals completed! π
}
We define the identity map on B explicitly (see the earlier comment under Exercise 8).
def idB : Map B B := {
toFun
| "eggs" => "eggs"
| _ => "coffee"
maps_to_codomain := by β’ β a β B,
(match a with
| "eggs" => "eggs"
| x => "coffee") β
B
intro _ hb aβ:Stringhb:aβ β Bβ’ (match aβ with
| "eggs" => "eggs"
| x => "coffee") β
B
dsimp [B] at * aβ:Stringhb:aβ β {"eggs", "coffee"}β’ (match aβ with
| "eggs" => "eggs"
| x => "coffee") β
{"eggs", "coffee"}
rw [Finset.mem_insert, aβ:Stringhb:aβ = "eggs" β¨ aβ β {"coffee"}β’ (match aβ with
| "eggs" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "eggs" => "eggs"
| x => "coffee") β
{"coffee"} Finset.mem_singleton aβ:Stringhb:aβ = "eggs" β¨ aβ = "coffee"β’ (match aβ with
| "eggs" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "eggs" => "eggs"
| x => "coffee") =
"coffee"] at * aβ:Stringhb:aβ = "eggs" β¨ aβ = "coffee"β’ (match aβ with
| "eggs" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "eggs" => "eggs"
| x => "coffee") =
"coffee"
rcases hb with hb | hb inl aβ:Stringhb:aβ = "eggs"β’ (match aβ with
| "eggs" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "eggs" => "eggs"
| x => "coffee") =
"coffee"inr aβ:Stringhb:aβ = "coffee"β’ (match aβ with
| "eggs" => "eggs"
| x => "coffee") =
"eggs" β¨
(match aβ with
| "eggs" => "eggs"
| x => "coffee") =
"coffee"
all_goals
subst hb inr β’ (match "coffee" with
| "eggs" => "eggs"
| x => "coffee") =
"eggs" β¨
(match "coffee" with
| "eggs" => "eggs"
| x => "coffee") =
"coffee"
first | exact Or.inl rfl inr β’ (match "coffee" with
| "eggs" => "eggs"
| x => "coffee") =
"eggs" β¨
(match "coffee" with
| "eggs" => "eggs"
| x => "coffee") =
"coffee" | exact Or.inr rfl All goals completed! π
}
A proof that {k β h = 1_B} holds for our pair h, k is given below. (We define a macro for a repeated sequence of tactics to keep the proof concise.)
syntax "eval_map" Lean.Parser.Tactic.rwRule : tactic
macro_rules
| `(tactic| eval_map $fn_name) =>
`(tactic| (
rw [$fn_name]
dsimp only [DFunLike.coe]
split
Β· contradiction
Β· rfl
)
)
example : k β h = idB := by β’ k.toFun β h.toFun = idB.toFun
funext x x:Stringβ’ (k.toFun β h.toFun) x = idB.toFun x
rw [Function.comp_apply x:Stringβ’ k.toFun (h.toFun x) = idB.toFun x] x:Stringβ’ k.toFun (h.toFun x) = idB.toFun x
by_cases h_x_eggs : x = "eggs" pos x:Stringh_x_eggs:x = "eggs"β’ k.toFun (h.toFun x) = idB.toFun xneg x:Stringh_x_eggs:Β¬x = "eggs"β’ k.toFun (h.toFun x) = idB.toFun x
Β· pos x:Stringh_x_eggs:x = "eggs"β’ k.toFun (h.toFun x) = idB.toFun x rw [h_x_eggs pos x:Stringh_x_eggs:x = "eggs"β’ k.toFun (h.toFun "eggs") = idB.toFun "eggs"] pos x:Stringh_x_eggs:x = "eggs"β’ k.toFun (h.toFun "eggs") = idB.toFun "eggs"
have h_eval : h "eggs" = "John" := rfl pos x:Stringh_x_eggs:x = "eggs"h_eval:h.toFun "eggs" = "John"β’ k.toFun (h.toFun "eggs") = idB.toFun "eggs"
have k_eval : k "John" = "eggs" := rfl pos x:Stringh_x_eggs:x = "eggs"h_eval:h.toFun "eggs" = "John"k_eval:k.toFun "John" = "eggs"β’ k.toFun (h.toFun "eggs") = idB.toFun "eggs"
have idB_eval : idB "eggs" = "eggs" := rfl pos x:Stringh_x_eggs:x = "eggs"h_eval:h.toFun "eggs" = "John"k_eval:k.toFun "John" = "eggs"idB_eval:idB.toFun "eggs" = "eggs"β’ k.toFun (h.toFun "eggs") = idB.toFun "eggs"
rw [h_eval, pos x:Stringh_x_eggs:x = "eggs"h_eval:h.toFun "eggs" = "John"k_eval:k.toFun "John" = "eggs"idB_eval:idB.toFun "eggs" = "eggs"β’ k.toFun "John" = idB.toFun "eggs" k_eval, pos x:Stringh_x_eggs:x = "eggs"h_eval:h.toFun "eggs" = "John"k_eval:k.toFun "John" = "eggs"idB_eval:idB.toFun "eggs" = "eggs"β’ "eggs" = idB.toFun "eggs" idB_eval pos x:Stringh_x_eggs:x = "eggs"h_eval:h.toFun "eggs" = "John"k_eval:k.toFun "John" = "eggs"idB_eval:idB.toFun "eggs" = "eggs"β’ "eggs" = "eggs"] All goals completed! π
Β· neg x:Stringh_x_eggs:Β¬x = "eggs"β’ k.toFun (h.toFun x) = idB.toFun x have h_eval : h x = "Mary" := by β’ k.toFun β h.toFun = idB.toFun eval_map h neg x:Stringh_x_eggs:Β¬x = "eggs"h_eval:h.toFun x = "Mary"β’ k.toFun (h.toFun x) = idB.toFun x
have k_eval : k "Mary" = "coffee" := by β’ k.toFun β h.toFun = idB.toFun eval_map k neg x:Stringh_x_eggs:Β¬x = "eggs"h_eval:h.toFun x = "Mary"k_eval:k.toFun "Mary" = "coffee"β’ k.toFun (h.toFun x) = idB.toFun x
have idB_eval : idB x = "coffee" := by β’ k.toFun β h.toFun = idB.toFun eval_map idB neg x:Stringh_x_eggs:Β¬x = "eggs"h_eval:h.toFun x = "Mary"k_eval:k.toFun "Mary" = "coffee"idB_eval:idB.toFun x = "coffee"β’ k.toFun (h.toFun x) = idB.toFun x
rw [h_eval, neg x:Stringh_x_eggs:Β¬x = "eggs"h_eval:h.toFun x = "Mary"k_eval:k.toFun "Mary" = "coffee"idB_eval:idB.toFun x = "coffee"β’ k.toFun "Mary" = idB.toFun x k_eval, neg x:Stringh_x_eggs:Β¬x = "eggs"h_eval:h.toFun x = "Mary"k_eval:k.toFun "Mary" = "coffee"idB_eval:idB.toFun x = "coffee"β’ "coffee" = idB.toFun x idB_eval neg x:Stringh_x_eggs:Β¬x = "eggs"h_eval:h.toFun x = "Mary"k_eval:k.toFun "Mary" = "coffee"idB_eval:idB.toFun x = "coffee"β’ "coffee" = "coffee"] All goals completed! π
There are 12 such pairs: h(\mathit{eggs}) can take any one of three distinct values in A, leaving h(\mathit{coffee}) to take one of the two remaining values, which together gives {3 \times 2 = 6} combinations; and for each combination, k can map the element in A that is not in the image of h to either \mathit{eggs} or \mathit{coffee}.
1. Guide
A category consists of the DATA:
(1) OBJECTS
(2) MAPS
(3) For each map f, one object as DOMAIN of f and one object as CODOMAIN of f
(4) For each object A an IDENTITY MAP, which has domain A and codomain A
(5) For each pair of maps {A \xrightarrow{f} B \xrightarrow{g} C}, a COMPOSITE MAP map {A \xrightarrow{g \;\mathrm{following}\; f} C}
satisfying the following RULES:
(i) IDENTITY LAWS: If {A \xrightarrow{f} B}, then {1_B \circ f = f} and {f \circ 1_A = f}
(ii) ASSOCIATIVE LAW: If {A \xrightarrow{f} B \xrightarrow{g} C \xrightarrow{h} D}, then {(h \circ g) \circ f = h \circ (g \circ f)}
We print the mathlib definition of Category below for reference.
#print Category