Let X and Y be sets. A function f:X→Y is called an isomorphism, denoted X→≅Y, if there exists a function g:Y→X such that g∘f=idX and f∘g=idY.
We also say that f is invertible and we say that g is the inverse of f. If there exists an isomorphism X→≅Y we say that X and Y are isomorphic sets and may write X≅Y.
We represent each type as a box containing a singular indefinite noun phrase…
The text in the box should:
begin with the word “a” or “an”.
refer to a distinction made and recognizable by the olog’s author.
refer to a distinction for which instances can be documented.
declare all variables in a compound structure.
We consider aspects as functions. for example:
we can say “a woman has an aspect of being a person”, and “a molecule has an aspect (where we call mass usually) of a positive real number.”
However, “a person has a child” is not a valid aspect, since there exists people who don’t have children.
Remark: since a father can have many children, so we write achild→hasafather instead of afather→hasachild.
A path in an olog is a head-to-tail sequence of arrows. The number of arrows is the length of the path.
We all know that “the woman in parents is called mother” and “mother is the woman in parents” (though it sounds weird), so the two paths are equivalent, the triangle is commutative. And the checker-mark √ in the region is bounded by the two paths.
Let X and Y be sets. The product of X and Y, denoted X×Y, is defined as
X×Y={(x,y)∣x∈X,y∈Y}
There are two natural project functions π1:X×Y→X and π2:X×Y→Y.
Now we can construct more examples of non-commutative diagrams:
Lemma(Universal property for product)
Let X and Y be sets. For any set A and functions f:A→X and g:A→Y, there exists a unique function A→X×Y such that the following diagram commutes.
We may write the unique function as ⟨f,g⟩:A→X×Y. And obviously, ⟨f,g⟩(a)=(f(a),g(a)).
Definition(coproducts)
Let X and Y be sets. The coproduct of X and Y, denoted X⊔Y, is defined as the “disjoint union” of X and Y. If an element is both in X and Y, then we need to copy it in X⊔Y so we can distinguish where each of it comes from.
There are two natural project functions i1:X→X⊔Y and i2:Y→X⊔Y.
Example:
{a,b}⊔{a,c}={i1a,b,i2a,c}
Lemma(Universal property for coproduct)
Let X and Y be sets. For any set A and functions f:X→A and g:Y→A, there exists a unique function X⊔Y→A such that the following diagram commutes.
Suppose given the diagram of sets and functions below:
Its fiber product is the set
X×ZY:={(x,w,y)∣f(x)=w=g(y)}
There are obvious projections π1:X×ZY→X and π2:X×ZY→Y. Note that if W=X×ZY then the diagram
commutes. So given the setup diagram we define the pullback of X and Y over Z to be any set W for which we have an isomorphism W→≅X×ZY.
The corner symbol ┘ indicates that W is the pullback.
Lemma(Universal property for pullback)
Suppose given the diagram as below:
For any set A and commutative solid arrow diagram as below (i.e. t∘f=u∘g)
there exists a unique arrow ⟨f,f⟩Z:A→X×ZY making everything commute.
Definition(Preimage)
Let f:X→Y be a function and y∈Y an element. The preimage of y under f, denoted f−1(y), is the subset f−1(y):={x∈X∣f(x)=y}. If Y′⊆Y is any subset, the preimage of Y′ under f, denoted f−1(Y′), is the subset f−1(Y′)={x∈X∣f(x)∈Y′}.
Proposition: Consider the diagram below:
where B′≅B×CC′ is a pullback. Then there is an isomorphism A×BB′≅A×CC′. Said another way,
A×B(B×CC′)≅A×CC′
Exercise: Consider the diagram on the left below, where both squares commute.
Let W=X×ZY and W′=X′×ZY′, and form the diagram to the right. Use the universal property of fiber products to construct a map W→W′ such that all squares commute.
Solution:
Definition
Given sets A and B, a span on A and B is a set R together with functions f:R→A and g:R→B.
Definition
Let A,B and C be sets, and let A←fR→gC and B←f′R′→g′C be spans. Their composite span is given by the fiber product R×BR′ as in the diagram below:
Let’s look at a example of span, which may be a little confusing but reveals the relationship between matrix plus and span.
Let A and B be sets and let A←R→B be a span. By the universal property of products, we have a unique map R→pA×B.
We make a matrix of natural numbers out of this data as follows. The set of rows is A, the set of columns is B. For elements a∈A and b∈B, the (a,b)-entry is the cardinality of its preimage, ∣p−1(a,b)∣, i.e. the number of elements in R that are sent by p to (a,b). For example, if R={(1,1),(1,2),(2,1),(2,2)} and p(a,b)=(a,b), then we can make the matrix (1111).
Given two spans A←R→B and A←R′→B, by the universal property of coproducts we have a unique span A←R⊔R′→B making the diagram commute. The matrix corresponding to this new span will be the sum of the two matrices corresponding to span R and R′.
Definition
Suppose given two parallel arrows:
The equalizer of f and g is the commutative diagram as to the right shown above, where we define
Suppose given the diagram of sets and functions below:
Its fiber sum, denoted X⊔WY, is defined as the quotient of X⊔W⊔Y by the equivalence relation ∼ generated by w∼f(w) and w∼g(w) for all w∈W.
X⊔WY:=(X⊔W⊔Y)/∼
where ∀w∈W,w∼f(w) and w∼g(w).
There are obvious inclusions i1:X→X⊔WY and i2:X→X⊔WY. The following diagram commutes:
We define the pushout of X and Y over W to be any set Z for which we have an isomorphism Z→≅X⊔WY. The corner symbol ┌ indicates that Z is the pushout.
Example: W={1,2},X={0,1,2,3},Y={0,1,2,3,4} and f(x)=x+1,g(x)=x. Then
Example: For any sets A,B, let’s consider the function ev:BA×A→B. ev(f,a)=f(a).
specially, ev:53×3→5. Since it’s not an isomorphism, so the corresponding arithmetic expression is not equality. However, 575→5 seems weird and meaningless.
Definition
Let V be a set and let P(V) be its powerset. A subset X⊆P(V) is called downward-closed if, for every u∈X and every u′⊆u, we have u′∈X. We say that Xcontains all atoms if for every v∈V the singleton set {v} is an element of X.
A simplicial complex is a pair (V,X) where V is a set and X⊆P(V) is a downward-closed subset that contains all atoms. The elements of X are called simplices. We have a function X→N sending each simplex to its cardinality. The set of simplices with cardinality n+1 is denoted as Xn. Since X contains all atoms, so X0≅V. Sometimes we call 0-simplices vertices and 1-simplices edges.
Example: let n be a natural number and V=n+1. Define the n-simplex denoted Δn to be (V,P(V)), obviously P(V) is downward-closed and contains all atoms.
We can draw Δ0,Δ1,Δ2,Δ3 as follows:
Definition
Define the subobject classifier for Set, denoted Ω, to be the set Ω:={True,False}, together with the function {♡}→Ω sending the unique element to True.
Proposition: Let B be a set. There is an isomorphism
Let f:X→Y be a function. We say that f is surjective if, for all y∈Y there exists some x∈X such that f(x)=y. We say that f is injective if, for all x∈X and all x′∈X with f(x)=f(x′) we have x=x′.
Definition
Let f:X→Y be a function. We say that f is a monomorphism if for all sets A and pairs of functions g, g′:A→X,
if f∘g=f∘g′ then g=g′.
We say that f is an epimorphism if for all sets B and pairs of functions h,h′:Y→B,
if h∘f=h∘f′ then h=h′.
Proposition: Let f:X→Y be a function. Then f is injective if and only if it is a monomorphism; f is surjective if and only if it is an epimorphism.
Proposition: Let f:X→Y be a monomorphism. Then for any function g:A→Y, the top map f′:X×YA→A in the diagram
is a monomorphism.
Proof: Consider the diagram:
B is an arbitrary set and we have
f′∘m=f′∘n
we need to prove that m=n. Firstly we construct two morphism
q=g′∘mr=g′∘n
Then
f∘q=f∘g′∘m=g∘f′∘m=g∘f′∘n=f∘g′∘n=f∘r
since f is a monomorphism, so q=r. Due to the universal property of pullback, there is a unique morphism B→X×YA. So m=n.
Remark: if the morphism from B to A and from B to X is unique (f′∘m=f′∘n and q=r) then the morphism from B to X×YA is unique.
Corollary: Let i:A→X be a monomorphism. Then there is a fiber product square of the form:
emmm… it’s quite self-evident if you think carefully. The behavior of f and f′ is obvious.
Definition
A multiset is a sequence X:=(E,B,π) where E and B are sets and π:E→B is a surjective function. We refer to E as the set of element instances of X, we refer to b as the set of element names of X and we refer to π as the naming function for X. Given an element name x∈B, let π−1(x)⊆E be the preimage; the number of elements in π−1(x) is called the multiplicity of x.
Example: E={1,2,3,4,5}, B={a,b,c} ,
π(1)=a,π(2)=aπ(3)=bπ(4)=c,π(5)=c
then it is somehow representing multiset {a,a,b,c,c}.
Suppose that X=(E,B,π) and X′=(E′,B′,π′) are multisets. A mapping from X to Y, denoted f:X→Y, consists of a pair (f1,f0) such that f1:E→E′ and f0:B→B′ are functions and such that the following diagram commutes:
We can understand it as “the map preserves the instance-name mapping”.
Definition(Relative set)
Let B be a set. A relative set over B, or simply a set over B, is a pair (E,π) such that E is a set and π:E→B is a function. A mapping of relative sets over B, denoted f:(E,B)→(E′,B′), is a function f:E→E′ such that the triangle below commutes, i.e. π=π′∘f.
Definition(Indexed set)
Let A be a set. An A-indexed set is a collection of sets Sa, one for each element a∈A; for now we denote this by (Sa)a∈A. If (Sa′)a∈A is another A-indexed set, a mapping of A-indexed sets from (Sa)a∈A to (Sa′)a∈A, denoted
(fa)a∈A:(Sa)a∈A→(Sa′)a∈A
is a collection of functions fa:Sa→Sa′, one for each element a∈A.
A monoid is a sequence (M,e,∗), where M is a set, e∈m is an element, and ∗:M×M→M is a function, such that the following conditions hold for all m,n,p∈M:
m∗e=m
e∗m=m
(m∗n)∗p=m∗(n∗p)
We refer to e as the identity element and to ∗ as the multiplication formula for the monoid. We call the first two rules identity laws and the third rule the associativity law for monoids.
Example (Trivial monoid) There is a monoid with only one element, M=({e},e,∗) where ∗:(e,e)→e. We call this monoid the trivial monoid and sometimes denoted it 1/
Definition
Let X be a set. A list in X is a pair (n,f) where n∈N is a natural number (called the length of the list) and f:n→X is a function. We may denote such a list by
(n,f)=[f(1),f(2),...,f(n)]
Given two lists L=(n,f),L′=(n′,f′), the concatenation of L and L′ is denoted L++L′=(n+n′,f++f′). The behavior of f++f′:n+n′→X is natural:
(f++f′)(i):={f(i)f′(i−n)i≤ni≥n+1
Definition(Free monoid)
Let X be a set. The free monoid generated by X is the sequence M:=(List(X),[],++), where List(X) is the set of lists of elements in X. We refer to X as the set of generators for the monoid M.
Definition(Presented monoid)
Let G be a finite set, and n be a natural number, and for each 1≤i≤n, let mi and mi′ be elements of List(G). The monoid presented by generators G and relations {(mi,mi′)∣1≤i≤n} is the monoid M=(M,e,∗) defined as follows:
Let ∼ denote the equivalence relation on List(G) generated by \
define M=List(G)/∼
e=[]
∗ is concatenating lists.
Example: Let G={a,b,c,d} representing four buttons that can be pressed. The free monoid List(G) is the set of all ways of pressing buttons, like [a,a,c,c,d] means you push button a, then a, then c, then c, then d.
But when you notice that you press [a,a,c] is always equivalent to [d,d], and you press [a,c,a,c] is actually doing nothing. So we can have relation:
([a,a,c],[d,d]),([a,c,a,c],[])
So we can have the equivalent relation in Presented monoid:
A monoid is called cyclic if it has a representation involving only one generator, In other words, ∣G∣=1.
Example: Consider the monoid where G={a} and the relation is empty. We get the additive monoid of natural numbers now since [a,a]++[a]=[a,a,a]. With the really strong relation [a]∼[] we would get the trivial monoid having only one element [].
Let M=(M,e,∗) and M′=(M′,e′,∗′) be monoids. A monoid homomorphismf from M to M′, denoted f:M→M′, is a function f:M→M′, satisfying:
f(e)=e′
f(m1∗m2)=f(m1)∗′f(m2)
The set of monoid homomorphisms from M to M′ is denoted HomMon(M,M′).
Example: Given any monoid M there is a unique monoid homomorphism from M to the trivial monoid 1. There is also a unique homomorphism 1→M. These facts together have an upshot: we can always construct a homomorphism:
M→!1→!M′
which we call the trivial homomorphism.
Proposition: Let M=(Z,0,+) and M′=(N,0,+). The only monoid homomorphism f:M→M′ sends every element m∈Z to 0∈N.
Proposition: Let M=(M,e,∗) and M′=(M′,e′,∗′) be monoids, f:M→M′ a monoid homomorphism, S a set, and suppose that α:M′×S→S is an action of M′ on S. Then Δf(α):M×S→S, defined as:
Let (M,e,∗) be a monoid. An element m∈M is said to have an inverse if there exists an m′∈M such that mm′=e and m′m=e. A group is a monoid in which every element m∈M has an inverse.
Proposition: The inverse element is unique.
Definition (Group action)
Let (G,e,∗) be a group and S a set. An action of G on S is a function:
↺:G×S→S
such that for all s∈S and g,g′∈G, we have
e↺s=s
g↺(g′↺s)=(g∗g′)↺s.
Definition(orbit)
Let G be a group acting on a set X. For any point x∈X, the orbit of x, denoted Gx, is the set
Gx:={x′∈X∣∃g∈G,g↺x=x′}
Definition
Let G and G′ be groups. A group homomorphismf:G→G′ is defined to be a monoid homomorphism.
src:A→V is a function, called the source function.
tgt:A→V is a function, called the target function.
Definition(Path)
Let G=(V,A,src,tgt) be a graph. A path of length n in G, denoted p∈PathG(n) is a head-to-tail sequence
p=(v0→a1v1→a2v2→a3...→anvn)
of arrows in G, which we denote by v0a1a2...an. In particular we have canonical isomorphism PathG(1)≅A and PathG(0)≅V. And
PathG=n∈N⋃PathG(n)
we denote the source and the target vertex of a path by
srcˉ,tgtˉ:PathG→V
Definition
Let G=(V,A,src,tgt) and G′=(V′,A′,src′,tgt′) be graphs. A graph homomorphismf from G to G′, denoted f:G→G′, consists of two functions f0:V→V′ and f1:A→A′ such that the two diagrams below commute:
Let S be a set and R⊆S×S a binary relation on S; if (s,s′)∈R we will write s≤s′, then we say that R is a preorder if, for all s,s′,s′′∈S we have
s≤s
if s≤s′ and s′≤s′′ then s≤s′′
If we want it to be a partial order, then we need to add
If s≤s′ and s′≤s then s=s′
If we want it to be a linear order, then we need to add
Either s≤s′ or s′≤s.
Definition(clique)
Let (S,≤) be a preorder. A clique is a subset S′⊆S such that for each a,b∈S′ one has a≤b.
Definition(meet, join)
Let (S,≤) be a preorder and let s,t∈S be elements. A meet of s and t is an element w∈S satisfying
w≤s and w≤t
for any x∈S, if x≤s and x≤t then x≤w
We write as w≅s∧t.
A join of s and t is an element w∈S satisfying
s≤w and t≤w
for any x∈S, if s≤x and t≤x then w≤x
We write as w≅s∨t.
Definition(opposite order)
Let S=(S,≤) be a preorder. The opposite preorder, denoted Sop is the preorder (S,≤op) having the same set of elements but where s≤ops′ iff s′≤s.
Definition(opposite order)
Let S=(S,≤) and S′=(S′,≤′) be preorders, A morphism of preorders denoted f:S→S′ is a function f:S→S′ such that, for every pair of elements s1,s2∈S, if s1≤s2 then f(s1)≤′f(s2).
A categoryC is defined as follows: One announces some constituents (objects, morphisms, identities, compositions) and asserts (identity law, associativity law) that they conform to some laws. Specifically, one announces:
a collection Ob(C), elements of which are called objects.
for every pair x,y∈Ob(C), a set HomC(x,y). It is called the hom-set from x to y; its elements are called morphisms from x to y.
for every object x∈Ob(C), a specified morphism denoted idx∈HomC(x,x) called the identity morphism on x.
for every three objects x,y,z∈Ob(C), a function
∘:HomC(y,z)×HomC(x,y)→HomC(x,z)
called the composition formula.
Given objects x,y∈Ob(C), we can denote a morphism f∈HomC(x,y) by f:x→y; we say that x is the domain of f and that y is the codomain of f. Given also g:y→z, the composition formula is written using infix notation, so g∘f:x→z means ∘(g,f)∈HomC(x,z).
for every x,y∈Ob(C) and every morphism f:x→y, we have
f∘idx=fidy∘f=f
if w,x,y,z,∈Ob(C) are any objects and f:w→x,g:x→y and h:y→z are any morphisms, then the two ways to compose are the same:
(h∘g)∘f=h∘(g∘f)
Remark: Although we say Ob(C) is a collection of objects(that’s because sometimes we want to talk about set category, where all objects are sets), at the beginning of study, we still consider Ob(C) as a set.
Example: Inside the category Set is a subcategory Fin⊆Set, called the category of finite sets. Whereas an object S∈Ob(Set) is a set that can have arbitrary cardinality, we define Fin such that its objects include all the sets S with finitely many elements, i.e. ∣S∣=n for some natural number n. Every object of Fin is an object of Set, but not vice versa. The morphisms are the same:
HomFin(S,S′)=HomSet(S,S′)
Example(The category Mon of monoids): objects are monoids, and morphisms are the homomorphisms in monoids.
Example(The category Grp of groups): objects are groups, and morphisms are the homomorphisms in groups.
Example(The category PrO of preorders): objects are preorders, and morphisms are the homomorphisms in preorders.
Example(The category Grph of graphs): objects are graphs, and morphisms are the graph homomorphisms. Notice that since the left rectangular and the right rectangular commute, the whole diagram commutes.
So the associativity is ensured.
Definition(isomorphism)
Let C be a category and let X,Y∈Ob(C) be objects. An isomorphism f from X to Y is a morphism f:X→Y in C, such that there exists a morphism g:Y→X in C such that
g∘f=idX,f∘g=idY
In this case we say that the morphism f is invertible and that g is the inverse of f. We may also say that the objects X and Y are isomorphic.
Lemma
Let C be a category and let ∼ be the relation on Ob(C) given by saying X∼Y iff X and Y are isomorphic. Then ∼ is an equivalence relation.
Let’s consider another definition of category:
Definition
A categoryC consists of a sequence (Ob(C),HomC,dom,cod,ids,∘) where
Ob(C) is a set
HomC is a set, and dom,cod:HomC→Ob(C) are functions
ids:Ob(C)→HomC is a function
∘ is a function as depicted in the commutative diagram below
Definition(functors)
Let C and C′ be categories. A functor F from C to C′, denoted F:C→C′, is defined as follows: One announces some constituents and asserts that they conform to some laws. Specifically, one announces
a function Ob(F):Ob(C)→Ob(C′) which we sometimes denote simply by F:Ob(C)→Ob(C′)
for every pair of objects c,d∈Ob(C), a function
HomF(c,d):HomC(c,d)→HomC′(F(c),F(d))
which we sometimes denote simply by F:HomC(c,d)→HomC′(F(c),F(d)).
One asserts that the following laws hold:
Identities are preserved by F:
F(idc)=idF(c)
Composition is preserved by F:
F(h∘g)=F(h)∘F(g)
Example: Consider the functor:
U:Mon→Set
Which means every monoid has a underlying set, and every homomorphisms between monoids has a corresponding function between sets.
Proposition: Let PrO be the category of preorders and Grph be the category of graphs. There is function P:PrO→Grph such that for any preorder X=(X,≤), the graph P(X) has vertices X.
Proposition: There exists a category, called the category of small categories and denoted Cat, in which the objects are the small categories and the morphisms are the functors:
HomCat(C,D)={F:C→D∣Fisafunctor}
# Categories and functors commonly arising in mathematics
Let (M,e,∗) be a monoid. We consider it as a category M with one object, Ob(M)={Δ}, and
HomM(Δ,Δ)=M
The identity morphism idΔ serves as the monoid identity e, and the composition formula
∘:HomM(Δ,Δ)×HomM(Δ,Δ)→HomM(Δ,Δ)
is given by ∗:M×M→M. The associativity and identity laws for the monoid match precisely with the associativity and identity for categories.
The homomorphism between two monoids can be interpreted as the functor between two one-object categories.
"A monoid is a category with one object. A monoid homomorphism is just a functor between one-object categories."
Theorem:
There is a functor i:Mon→Cat with the following properties:
for every monoid M∈Ob(Mon), the category i(M)∈Ob(Cat) itself has exactly one object.
for every pair of monoids M,M′∈Ob(Mon) the function
HomMon(M,M′)→≅HomCat(i(M),i(M′))
induced by the functor i, is a bijection.
Example: Let C be a category and x∈Ob(C) an object. Let M=HomC(x,x). Note that for any two elements f,g∈m we have f∘g∈M. Let M=(M,idx,∘). It is easy to check that M is a monoid; it is called the endomorphism monoid of x in C.