Input Type
(Domain)
Instance1
Instance2
Output Type
(Codomain)
InstanceC
Function1
Function2
Image
InstanceA
InstanceB
Input Type
(Domain)
Instance1
Instance2
Instance3
Output Type
(Codomain)
Function1
Function2
Image
InstanceA
InstanceB
Input Type
(Domain)
Instance1
Instance2
Instance3
Output Type
(Codomain)
Function1
Image
Instance1
Instance2
Instance3
Input Type
(Domain)
Instance1
Instance2
Instance3
Output Type
(Codomain)
InstanceC
Function1
Image
InstanceA
InstanceB
Input Type
(Domain)
Instance1
Instance2
Instance3
Instance4
Review the various terms for a Function
Output Type
(Codomain)
Instance5
Instance6
A Function
(as shown by the blue arrow)
uses it's implementation
(as shown by the red arrows)
to map
an instance of the Input type (Domain)
to an instance of the Output type (Codomain)
InputType -> OutputType
The Set of Output instances that the function "returns"
is called the "Image"
(Image)
Instance1
Instance2
Instance3
Instance4
Start
Instance1
Instance2
Instance3
Instance4
Intermediate
Function1
Image1
Instance1
Instance2
Instance3
Instance4
End
Function2
Image2
Instance1
Instance2
Instance3
Instance4
Functions can "compose"
The below example is written "Function2 ∘ Function1" and is read as
"Pass Input into Function1 and
then pass Function1's output into Function2
as Function2's Input"
Input / Output
(Domain / Codomain)
Instance1
Instance2
Instance3
Instance4
There is a function called "identity."
It maps the Input instance back to itself
as its Output instance
identity
Type1
Instance1
Instance2
Instance3
Instance4
Type2
Instance1
Instance2
Instance3
Instance4
If two functions can compose in such a way
that they simulate the 'identity' function, then
- the second function is the "inverse" of the first function
- the composition of the two functions form an "isomorphism"
A Total Function and its inverse cannot always form an "isomorphism"
because the inverse is not always a Total Function
There are 4 types of Total Functions and
the inverse of only one type of a Total Function
forms an "isomorphism"
Only Bijective functions are Isomorphisms.
All other functions are Homomorphisms
"Output -> Input" is a partial function:
InstanceB maps to two Input instances,
not one
SURJECTIVE, non-INJECTIVE
The Image contains all instances
of the Output Type
(Every Output instance has
AT LEAST 1 arrow pointing to it)
"Ouput -> Input" is a partial function:
InstanceC cannot map to
an Input Instance
?
INJECTIVE, non-SURJECTIVE
Every Input instance maps to
a UNIQUE Output instance
(Each Output instance in the
Image has ONLY 1 arrow pointing to it)
A blue-background rectangle explains
why a type of a Total Function
is/is not an isomorphism and why
BIJECTIVE
(SURJECTIVE & INJECTIVE)
A function that is both
Injective and Surjective
(Each Input instance maps directly
to a unique Output instance
and all Output instances are
included in the Image)
non-SURJECTIVE, non-INJECTIVE
A function that is neither
Injective or Surjective
The inverse of a non-surjective, non-injective function
is a partial function
SURjective = "onto" (Latin) or "epi-" (Greek) = Epimorphism
Function1
Function2
(Inverse of Function1)
Input Type
Instance1
Instance2
Instance3
Instance4
Instance5
Instance6
Output Type
Instance1
Instance2
Instance3
Instance4
Instance5
Instance6
A Function is "TOTAL" if it knows how
to map EVERY instance of the Input Type
to an instance of the Output Type
These are Mathematical Functions (y = x + 1)
Input Type
Instance1
Instance2
Instance3
Instance4
Instance5
Instance6
Output Type
Instance1
Instance2
Instance3
Instance4
Instance5
Instance6
For these specific instances of the Input Type,
the function cannot return an instance of Output Type.
Functions can be "TOTAL" or "PARTIAL
A Function is "PARTIAL" if it knows how
to map SOME BUT NOT ALL instances of the Input Type
to an instance of the Output Type
These are NOT Mathematical Functions
Start
Instance1
Instance2
Intermediate
Instance3
Instance4
Instance1
Instance2
Function1
End
Instance3
Instance4
Instance1
Instance2
Law of Epimorphism
Given Function2 and Function3 are functions that map Intermediate to End
(Intermediate -> End)
and
"Function2 ∘ Function1" and "Function3 ∘ Function1" produce the same Output instances,
then
Function2 ∘ Function1 = Function3 ∘ Function1
Since we can cancel out 'Function1', then
Function2 = Function3
Thus,
'Function1' is an Epimorphism
Law of Monomorphism
Given Function1 and Function2 are functions that map Start to Intermediate
(Start -> Intermediate)
and
"Function3 ∘ Function1" and "Function3 ∘ Function2" produce the same Output instances,
then
Function3 ∘ Function1 = Function3 ∘ Function2
Since we can cancel out 'Function3', then
Function1 = Function2
Thus,
'Function3' is a Monomorphism
Function2
Function3
Start
Instance1
Intermediate
Instance1
Instance2
Function1
Function2
End
Instance1
INjective = "?" (Latin) or "moni-" or "mono-" (Greek) = Monomorphism
Function3
The two primitive concepts in Category Theory are...
... "objects" ...
... and "morphisms"/"arrows" ...
f
... where "objects" merely
mark the start and end of
"morphisms"/"arrows"
a
b
c
Law of Composition
if
two arrows exist
'f' exists (a -> b)
'g' exists (b -> c),
and
one arrow ends where another starts
('f' ends at 'b' and 'g' starts at 'g')
then
'g ∘ f' must exist
and
is different from other similar arrows ('x' and 'y')
Note: 'g ∘ f ' means first take the "f" path and then the "g" path
Different compositions of "morphisms"/"arrows" result in different Categories
because the Category's "structure" only appears when multiple "arrows" are composed
a
b
Law of Identity
if
two arrows exists
'f' (a -> b)
'g' (b -> b)
and
one arrow ends at 'b' ('f')
the other arrow starts and ends at 'b' ('g')
then
g ∘ f = f
f ∘ g = f
a
b
a
b
Law of Associativity
(the position of the parenthesis don't matter)
if
three arrows exists
'f' (a -> b)
'g' (b -> c)
'h' (c -> d)
and
the previous arrow ends where
the next starts
then
h ∘ (g ∘ f) = (h ∘ g) ∘ f
c
d
By encoding things using Categories, objects "shrink" into points where one does not
know what is inside that point. The only way to interact with that point is through
its interface (i.e. how arrows to and from that object compose with other arrows).
a
b
c
d
e
A Category satisfies 3 laws
To help make this idea concrete,
let's say (for now) that
objects = Types
arrows = Total Functions
As an example, consider the below object, "b". We don't know what 'b' really is,
but we do know these things from this graph:
- one can get TO 'b' if one starts at 'a', 'e', 'c', or 'd'
- 'b' can never get to 'a' or 'e'
- 'b' can only get to 'c' directly and 'd' indirectly
Input / Output
Input
Type
Output
Type
Start
Intermediate
End
Type1
Type2
Start
Intermediate
End
Start
Intermediate
End
Let's now change what objects and 'arrows' mean
Objects = Values (e.g. the Integer type's value, 4)
Arrows = Relations
This models a "pre-order" whose only requirement is that arrows must compose
Since
A <= B and B <= C
Then
A <= C
a
b
c
A relationship exists if there is an arrow from one object to another. Here are some examples
4
8
a
b
For this 'pre-order' concept to be a category, we also need to include the identity arrows
The above category is called a "Thin Category". Every Pre-Order corresponds to a Thin Category and vice versa
What is a HomSet?
HomSet = A set of all arrows between two objects
"C(a, b)" is notation that reads, "C is a set of all arrows between the object, a, and the object, b"
a
b
g
f
f
g
g ∘ f
y
x
f
g
g
f
f
g
g ∘ f
h
h ∘ g
f2
f4
f5
f6
f1
f3
identity
Total
Function
Function1
Function2
Function1
Function2
Function1
Function2
Function3
Function1
Function2
Function3
<=
<=
<=
<=
This arrow's "dotted" line
indicates that it does not exist
There is no arrow
from 8 to 4 because
such a relationship
does not exist
"8 <=" is false
<=
<=
<=
g
f
h
C(a, b)
f
g
h
A "Thin Category" is a category where every HomSet in the category is a set with zero or one arrow
Example
Thin Category
a
b
identity
f
identity
All Homsets in this Category have
only 0 or 1 elements
C(a, b)
f
C(b, b)
identity
C(a, a)
identity
Example
Not a Thin Category
a
b
identity
g
f
h
identity
At least one HomSet in this Category
has more than 1 element
C(a, b)
f
g
h
C(b, b)
identity
C(a, a)
identity
Arrows in a Thin Category are both epimorphic and monomorphic, but not isomorphic
a
b
c
d
Black arrow is monomorphic when considering BLUE arrows
Black arrow is epimorphic when considering RED arrows
Consider a category with only 1 object
Even though there is only one object,
it can have many arrows
M
<=
<=
<=
<=
<=
<=
In this category,
there cannot be an arrow
the points from C to B
Thus, (b -> c) does not have
an inverse, (c -> b), which
would make this isomorphic
<=
<=
identity
f
g
h
A Category is
- zero or more objects
- with arrows between them
- each object has an "identity" arrow
- the law of associativity holds
Example
identity
Example
identity
identity
Example
identity
identity
g
f
h
Learning how to create categories
To create a category, we start with objects
Then we draw arrows, starting first with the identity arrows
Then we draw arrows from one object to another
Then we draw arrows that are compositions of our 'base' arrows
At some point, we'll finish.
Assuming the law of associtivity holds,
we have defined a category
a
b
c
a
b
c
a
b
c
a
b
c
f
g
g ∘ f
Examples of Arrows that show relationships
The arrow represents a
"less than or equal to" relationship
3
4
<=
The arrow represents a
"less than" relationship
2
5
<
Brief Explanation on Orders
(so that upcoming diagrams make more sense)
Order
A function that tests whether a relationship exists
between two values of the same type (i.e. "(A, A) -> Boolean")
There are 3 types
3 Types of Order Functions
Pre Order
(This is the one used in below examples)
Reflexive
(identity)
x "has an arrow pointing to" x
Transitive
(composition)
If
x "has an arrow pointing to" y
and
y "has an arrow pointing to" z
then
x "has an arrow pointing to" z
Example: "less than or equal to"
Transitive: 3 <= 4 <= 5
Reflexive: 3 <= 3
Total Order
(Optional Reading)
Total
Only one (but not both) of
these statements can be true:
x "has an arrow pointing to" y
y "has an arrow pointing to" x
Transitive
If
x "has an arrow pointing to" y
and
y "has an arrow pointing to" z
then
x "has an arrow pointing to" z
Antisymmetric
If
x "has an arrow pointing to" y
then
y cannot "have an arrow pointing to" x
Example: "less than"
Transitive: if 3 < 4 and 4 < 5, then 3 < 5
Total: either 3 < 4 (true) or 4 < 3 (false)
Antisymmetry: if 3 < 4, then 4 cannot be < 3
... which
implies...
Partial Order
(Optional reading)
Antisymmetric
If
x "has an arrow pointing to" y
and
y "has an arrow pointing to" x
then
x is y
(two different objects cannot
have a bidirectional arrow)
Reflexive
x "has an arrow pointing to" x
Transitive
If
x "has an arrow pointing to" y
and
y "has an arrow pointing to" z
then
x "has an arrow pointing to" z
No Example Given
In a category that only has one object,
each arrow ends where another begins,
thus every arrow composes with another.
M
If a category only has one object,
it is called a "Monoid", which means "single"
Note: "Monoid" in this context refers to a single-object category.
"Monoid" in Algebra or Set Theory refers to something else.
The Set Theory one was discovered before the Category one.
identity
f
identity ∘ f
g
g ∘ f
identity ∘ g ∘ f
Monoid
(Category Theory Term)
Monoid
identity
f
identity ∘ f
g
g ∘ f
identity ∘ g ∘ f
"Monoid"
(Algebra / Set Theory)
A
value...
2
4
"John"
combined
(via operation)
+
*
concat
with a
"unit" value
0
1
""
... produces the
same value.
2
4
"John"
Are these two terms equivalent/identical?
Yes
If our objects are Integers from 0 to infinity
and our arrows are the "<arg> + <some value>" functions,
we can get this
Integer
identity
(x + 0)
f
(x + 1)
g
(x + 2)
... all other
functions...
Integer
(Type)
where instances are 'x'
in the arrow
2
0
1
3
... and so forth ...
identity
(0 + 0)
g
(0 + 2)
f
(0 + 1)
identity
(1 + 0)
f
(1 + 1)
g
(1 + 2)
C(Integer, Integer)
(HomSet of our
Monoid category)
f
g
... all other functions
identity
A non-Monoid category whose objects are
types corresponds to strongly-typed
programming languages because a function
can only compose if its output type
corresponds with the next
function's input type
A Monoid is a very special category
because any two functions can compose.
A weakly-typed programming language
corresponds to a Monoid category
because any and all functions compose
(even if it's not logical for them to do so)
The "Primitives" of Category Theory
Categories = Ultimate Data Hiding
Defining objects and arrows
Approach 1: Types and Functions
There and Back Again:
Isomorphic Arrows
4 Types of Total Functions:
Injective, Surjective, Bijective, and Neither
Arrow Laws:
Epimorphism & Monomorphism
Examples of Categories
A Category is
- zero or more objects
- with arrows between them
- each object has an "identity" arrow
- the law of associativity holds
Example
identity
Example
identity
identity
f
Example
1-Object Categories
Defining Objects and Arrows:
Approach 2: Values and Relations
identity
identity
g
f
h
Legend
(Use these background colors to
know what is inside each box)
Explanations
Major Idea/Theme/Section
Read from top to bottom
by scrolling down