-
Notifications
You must be signed in to change notification settings - Fork 55
/
Limits.jl
153 lines (129 loc) · 6.36 KB
/
Limits.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
export CategoryWithProducts, ob, terminal, delete, product, proj1, proj2, pair,
CategoryWithCoproducts, initial, create, coproduct, coproj1, coproj2, copair,
CompleteCategory, equalizer, incl, factorize,
CocompleteCategory, coequalizer, proj
# Limits
########
""" Theory of a *category with (finite) products*
Finite products are presented in biased style, via the nullary case (terminal
objects) and the binary case (binary products). The equational axioms are
standard, especially in type theory (Lambek & Scott, 1986, Section 0.5 or
Section I.3). Strictly speaking, this theory is not of a "category with finite
products" (a category in which finite products exist) but of a "category with
*chosen* finite products".
For a monoidal category axiomatization, see [`CartesianCategory`](@ref).
"""
@theory CategoryWithProducts{Ob,Hom,Terminal,Product} <: Category{Ob,Hom} begin
Terminal()::TYPE
Product(foot1::Ob, foot2::Ob)::TYPE
# Terminal object.
terminal()::Terminal()
ob(⊤::Terminal())::Ob
delete(⊤::Terminal(), C::Ob)::(C → ob(⊤))
# Binary products.
product(A::Ob, B::Ob)::Product(A,B)
ob(Π::Product(A,B))::Ob ⊣ (A::Ob, B::Ob)
proj1(Π::Product(A,B))::(ob(Π) → A) ⊣ (A::Ob, B::Ob)
proj2(Π::Product(A,B))::(ob(Π) → B) ⊣ (A::Ob, B::Ob)
(pair(Π::Product(A,B), f::(C → A), g::(C → B))::(C → ob(Π))
⊣ (A::Ob, B::Ob, C::Ob))
# Projection axioms.
(pair(Π,f,g) ⋅ proj1(Π) == f
⊣ (A::Ob, B::Ob, C::Ob, Π::Product(A,B), f::(C → A), g::(C → B)))
(pair(Π,f,g) ⋅ proj2(Π) == g
⊣ (A::Ob, B::Ob, C::Ob, Π::Product(A,B), f::(C → A), g::(C → B)))
# Uniqueness axioms.
f == g ⊣ (C::Ob, ⊤::Terminal(), f::(C → ob(⊤)), g::(C → ob(⊤)))
(pair(h⋅proj1(Π), h⋅proj2(Π)) == h
⊣ (A::Ob, B::Ob, C::Ob, Π::Product(A,B), h::(C → ob(Π))))
end
""" Theory of a *(finitely) complete category*
Finite limits are presented in biased style, via finite products and equalizers.
The equational axioms for equalizers are obscure, but can found in (Lambek &
Scott, 1986, Section 0.5), which follow "Burroni's pioneering ideas". Strictly
speaking, this theory is not of a "finitely complete category" (a category in
which finite limits exist) but of a "category with *chosen* finite limits".
"""
@theory CompleteCategory{Ob,Hom,Terminal,Product,Equalizer} <:
CategoryWithProducts{Ob,Hom,Terminal,Product} begin
Equalizer(f::(A → B), g::(A → B))::TYPE ⊣ (A::Ob, B::Ob)
# Equalizers.
equalizer(f::(A → B), g::(A → B))::Equalizer(f,g) ⊣ (A::Ob, B::Ob)
ob(eq::Equalizer(f,g))::Ob ⊣ (A::Ob, B::Ob, f::(A → B), g::(A → B))
(incl(eq::Equalizer(f,g))::(ob(eq) → A)
⊣ (A::Ob, B::Ob, f::(A → B), g::(A → B)))
(factorize(eq::Equalizer(f,g), h::(C → A),
eq_h::Equalizer(h⋅f,h⋅g))::(ob(eq_h) → ob(eq))
⊣ (A::Ob, B::Ob, C::Ob, f::(A → B), g::(A → B)))
# Equalizer axioms.
(incl(eq)⋅f == incl(eq)⋅g
⊣ (A::Ob, B::Ob, f::(A → B), g::(A → B), eq::Equalizer(f,g)))
(incl(eq) == id(A)
⊣ (A::Ob, B::Ob, f::(A → B), eq::Equalizer(f,f)))
(factorize(eq,h,eq_h) ⋅ incl(eq) == incl(eq_h) ⋅ h
⊣ (A::Ob, B::Ob, C::Ob, f::(A → B), g::(A → B), h::(C → A),
eq::Equalizer(f,g), eq_h::Equalizer(h⋅f, h⋅g)))
(factorize(eq, k⋅incl(eq), eq_k) == k
⊣ (A::Ob, B::Ob, D::Ob, f::(A → B), g::(A → B), eq::Equalizer(f,g),
k::(D → ob(eq)), eq_k::Equalizer(k⋅incl(eq)⋅f, k⋅incl(eq)⋅g)))
end
# Colimits
##########
""" Theory of a *category with (finite) coproducts*
Finite coproducts are presented in biased style, via the nullary case (initial
objects) and the binary case (binary coproducts). The axioms are dual to those
of [`CategoryWithProducts`](@ref).
For a monoidal category axiomatization, see [`CocartesianCategory`](@ref).
"""
@theory CategoryWithCoproducts{Ob,Hom,Initial,Coproduct} <: Category{Ob,Hom} begin
Initial()::TYPE
Coproduct(foot1::Ob, foot2::Ob)::TYPE
# Initial object.
initial()::Initial()
ob(⊥::Initial())::Ob
create(⊥::Initial(), C::Ob)::(ob(⊥) → C)
# Binary coproducts.
coproduct(A::Ob, B::Ob)::Coproduct(A,B)
ob(⨆::Coproduct(A,B))::Ob ⊣ (A::Ob, B::Ob)
coproj1(⨆::Coproduct(A,B))::(A → ob(⨆)) ⊣ (A::Ob, B::Ob)
coproj2(⨆::Coproduct(A,B))::(B → ob(⨆)) ⊣ (A::Ob, B::Ob)
(copair(⨆::Coproduct(A,B), f::(A → C), g::(B → C))::(ob(⨆) → C)
⊣ (A::Ob, B::Ob, C::Ob))
# Coprojection axioms.
(coproj1(⨆) ⋅ copair(⨆,f,g) == f
⊣ (A::Ob, B::Ob, C::Ob, ⨆::Coproduct(A,B), f::(A → C), g::(B → C)))
(coproj2(⨆) ⋅ copair(⨆,f,g) == g
⊣ (A::Ob, B::Ob, C::Ob, ⨆::Coproduct(A,B), f::(A → C), g::(B → C)))
# Uniqueness axioms.
f == g ⊣ (C::Ob, ⊥::Initial(), f::(ob(⊥) → C), g::(ob(⊥) → C))
(copair(coproj1(⨆)⋅h, coproj2(⨆)⋅h) == h
⊣ (A::Ob, B::Ob, C::Ob, ⨆::Coproduct(A,B), h::(ob(⨆) → C)))
end
""" Theory of a *(finitely) cocomplete category*
Finite colimits are presented in biased style, via finite coproducts and
coequalizers. The axioms are dual to those of [`CompleteCategory`](@ref).
"""
@theory CocompleteCategory{Ob,Hom,Initial,Coproduct,Coequalizer} <:
CategoryWithCoproducts{Ob,Hom,Initial,Coproduct} begin
Coequalizer(f::(A → B), g::(A → B))::TYPE ⊣ (A::Ob, B::Ob)
# Coequalizers.
coequalizer(f::(A → B), g::(A → B))::Coequalizer(f,g) ⊣ (A::Ob, B::Ob)
ob(eq::Coequalizer(f,g))::Ob ⊣ (A::Ob, B::Ob, f::(A → B), g::(A → B))
(proj(eq::Coequalizer(f,g))::(B → ob(eq))
⊣ (A::Ob, B::Ob, f::(A → B), g::(A → B)))
(factorize(coeq::Coequalizer(f,g), h::(B → C),
coeq_h::Coequalizer(f⋅h,g⋅h))::(ob(coeq) → ob(coeq_h))
⊣ (A::Ob, B::Ob, C::Ob, f::(A → B), g::(A → B)))
# Coequalizer axioms.
(f⋅proj(coeq) == g⋅proj(coeq)
⊣ (A::Ob, B::Ob, f::(A → B), g::(A → B), coeq::Coequalizer(f,g)))
(proj(coeq) == id(B)
⊣ (A::Ob, B::Ob, f::(A → B), coeq::Coequalizer(f,f)))
(proj(coeq) ⋅ factorize(coeq,h,coeq_h) == h ⋅ proj(coeq_h)
⊣ (A::Ob, B::Ob, C::Ob, f::(A → B), g::(A → B), h::(B → C),
coeq::Coequalizer(f,g), coeq_h::Coequalizer(f⋅h, g⋅h)))
(factorize(coeq, proj(coeq)⋅k, coeq_k) == k
⊣ (A::Ob, B::Ob, D::Ob, f::(A → B), g::(A → B),
coeq::Coequalizer(f,g), k::(ob(coeq) → D),
coeq_k::Coequalizer(f⋅proj(coeq)⋅k, g⋅proj(coeq)⋅k)))
end