Definitions¶
While read a book ‘Seven Sketches in Compositionality: An Invitation to Applied Category Theory’ by Fong, Spivak
when a function \(f : \mathbb{R} → \mathbb{R}\)
order-preserving if \(x ≤ y\) implies \(f (x) ≤ f (y)\), for all \(x, y ∈ \mathbb{R}\);
metric-preserving if \(|x − y|=| f (x) − f (y)|\);
addition-preserving if \(f (x + y) = f (x) + f (y)\).
compositionality
compositionality emphasizes that the whole can be understood by studying its parts and their interactions. it plays a vital role in understanding how structures and properties of mathematical objects are preserved or transformed when they are combined or related through morphisms. Category theory provides a high-level, abstract framework to study compositionality by focusing on objects, morphisms, and their compositions, as well as functors and natural transformations between categories. This abstraction enables mathematicians to identify and study compositional principles that are common to various areas of mathematics and, in some cases, other disciplines.
generative effects
“generative effects” can be defined as the unexpected results or “surprises” that arise when observing the operations of a system in category theory, particularly when less structure is preserved by the observation.
skeletality
the requirement that x \(\cong\) y implies x = y. so partial orders are skeletal preorders. For short, we also use the term poset, a contraction of partially ordered set.
set
informally, as a collection of things, known as elements.
monotone
it preserves order whenever there is a path \(x → y\) upstairs, there is a path \(F(x) → F(y)\) downstairs.
cardinality
The map \(|·|: P(X) → N\), where \(P(X)\) is power set, sending each subset S to its numberof elements |S|.
dagger preorder
Galois connections
which are pairs of monotone maps between preorders, one of which preserves all joins and the other of which preserves all meets.
given two preorders P and Q, a Galois connection is a pair of maps back and forth – from P to Q and from Q to P – with certain properties, which make it like a relaxed version of isomorphisms. To be a bit more precise, preorder isomorphisms are examples of Galois connections, but Galois connections need not be preorder isomorphisms.
We say that an A “can be identified with” a B when any A gives us a unique B and any B gives us a unique A, and both round-trips – from an A to a B and back to an A, or from a B to an A and back to a B – return us where we started.
An isomorphism between preorders is basically just a relabeling of the elements.
Given any set \(S\), there is a set \(\mathbf{Rel}(S)\) of binary relations on \(S\). An element \(R ∈ \mathbf{Rel}(S)\) is formally a subset \(R ⊆ S × S\). The set \(\mathbf{Rel}(S)\) can be given an order via the subset relation, \(R ⊆ R'\), i.e. if whenever \(R(s_1,s_2)\) holds then so does \(R'(s_1,s_2)\).
For any set \(S\), there is also a set \(\mathbf{Pos}(S)\), consisting of all the preorder relations on \(S\). In fact there is a preorder structure \(\sqsubseteq\) on \(\mathbf{Pos}(S)\), again given by inclusion: \(≤\) is below \(≤'\) (we’ll write \(≤\sqsubseteq≤'\)) if \(a ≤ b\) implies \(a ≤' b\) for every \(a, b ∈ S\). A preorder of preorder structures? That’s what we mean by a level shift.
Yoneda lemma¶
The Yoneda lemma is a crucial principle in category theory that emphasizes the importance of understanding objects in a category by examining their relationships with other objects, as represented by morphisms. The lemma highlights the role of morphisms and their compositions in revealing connections among various mathematical structures.
In formal terms, let C be a locally small category (meaning that the collection of morphisms between any pair of objects in C forms a set), and let Set denote the category of sets. For any object A in C, there exists a covariant functor Hom(A, -): C → Set. This functor maps an object B in C to the set of morphisms Hom(A, B) in C and maps a morphism f: B → C to the morphism Hom(A, f): Hom(A, B) → Hom(A, C), which is the result of postcomposition with f.
The Yoneda lemma states that for any covariant functor F: C → Set and any object A in C, there is a natural bijection between the set of natural transformations from Hom(A, -) to F and the set F(A), i.e., Nat(Hom(A, -), F) ≅ F(A). The bijection is established as follows: given a natural transformation η: Hom(A, -) → F, η_A: Hom(A, A) → F(A) is obtained by applying η to A, and the element η_A(id_A) ∈ F(A) corresponds to η, where id_A denotes the identity morphism on A.
In essence, the Yoneda lemma asserts that an object A can be described by the morphisms from A to all other objects in the category. This means that an object’s properties are determined by its relationships with other objects through morphisms. This understanding has significant implications across various areas of mathematics and offers a powerful method for investigating mathematical structures and concepts.
One important consequence of the Yoneda lemma is the Yoneda embedding, which embeds any category into a category of functors. This embedding enables the study of categories and their objects through the behavior of functors and natural transformations, leading to further generalizations and unifying insights across different areas of mathematics.
\(∅\) denotes the empty set; it has no elements.
\(\{1\}\) denotes a set with one element; it has one element, 1.
\(\mathbb{B}\) denotes the set of booleans; it has two elements, \(true\) and \(false\).
\(\mathbb{N}\) denotes the set of natural numbers; it has elements 0, 1, 2, 3,…, 90717,….
\(\underline{n}\), for any \(n ∈ \mathbb{N}\), denotes the \(n\)th ordinal; it has \(n\) elements 1, 2,…, \(n\). For example, 0 = \(∅\), 1 = {1}, and 5 = {1, 2, 3, 4, 5}.
\(\mathbb{Z}\), the set of integers; it has elements …, −2, −1, 0, 1, 2,…, 90717,….
\(\mathbb{R}\), the set of real numbers; it has elements like π, 3.14, 5 ∗ √2, e, e2, −1457, 90717, etc.
\(A ≤ B\) denote whenever x is connected to y in \(A\), then x is connected to y in \(B\).
\(A ∨ B\) denotes the join of systems \(A\) and \(B\) in ordered set. the joined system \(A ∨ B\) is the smallest system that is bigger than both \(A\) and \(B\). a least upper bound (join)
\(A \wedge B\) denotes the meet of systems \(A\) and \(B\) in ordered set, a greatest lower bound
\(A ∪ B\) denotes the union
\(A ∩ B\) denotes the intersection
\(A × B\) denotes the product \(A × B\). Given two sets \(A\) and \(B\), \(A\) and \(B\) is the set of pairs \((a, b)\), where \(a ∈ A\) and \(b ∈ B\)
\(a ∼ b\) denotes \(a\) and \(b\) are both in the same part.
\(A \sqcup B\) Given two sets A and B, the set of pairs of the form (a, 1) or (b, 2), where \(a ∈ A\) and \(b ∈ B\)
\(\mathbf{Rel}(S)\) a set \(\mathbf{Rel}(S)\) of binary relations on S. An element \(R ∈ \mathbf{Rel}(S)\) is formally a subset \(R ⊆ S × S\)
\(\mathbf{Pos}(S)\) a set \(\mathbf{Pos}(S)\), consisting of all the preorder relations on \(S\)
\(\text{id}_{X}\) denote identity function. It is the bijective function \(\text{id}_{X}(x) = x\)
\(F;G\)* denote compsition of function \(F\) and \(G\). it whitch same as \(G ◦ F\) for \(x ∈ X\), \(G(F(x))\)
“Iff” is short for “if and only if.”
Kinds of categorys
\(\mathbf{Top}\): the category of topological spaces (neighborhood),
\(\mathbf{Grph}\): the category of graphs (connection),
\(\mathbf{Meas}\): the category of measure spaces (amount),
\(\mathbf{Mon}\): the category of monoids (action),
\(\mathbf{Grp}\): the category of groups (reversible action, symmetry),
\(\mathbf{Cat}\): the category of categories (action in context, structure).
1.8¶
Let \(X\) and \(Y\) be sets. A relation between \(X\) and \(Y\) is a subset \(R ⊆ X × Y\). A binary relation on \(X\) is a relation between \(X\) and \(X\), i.e. a subset \(R ⊆ X × X\).
1.10¶
If A is a set, a partition of \(A\) consists of a set \(P\) and, for each \(p ∈ P\), a nonempty subset \(A_p ⊆ A\), such that
We may denote the partition by \(\{A_p\}_{p∈P}\). We refer to \(P\) as the set of part labels and if \(p ∈ P\) is a part label, we refer to \(A_p\) as the \(p\)th part. The condition (1.5) says that each element \(a ∈ A\) is in exactly one part.
We consider two different partitions \(\{A_p\}_{p∈P}\) and \(\{A'_{p'}\}_{p'∈P'}\) of \(A\) to be the same if for each \(p ∈ P\) there exists a \(p' ∈ P'\) with \(A_p = A'_{p'}\) . In other words, if two ways to divide \(A\) into parts are exactly the same – the only change is in the labels – then we don’t make a distinction between them.
1.13¶
Let \(A\) be a set. An equivalence relation on \(A\) is a binary relation, let’s give it infix notation ∼, satisfying the following three properties:
\(a ∼ a\), for all \(a ∈ A\), (reflexivity)
\(a ∼ b\) iff \(b ∼ a\), for all \(a, b ∈ A\), (symmetry)
if \(a ∼ b\) and \(b ∼ c\) then \(a ∼ c\), for all \(a, b, c ∈ A\). (transitivity)
1.16¶
Given a set A and an equivalence relation ∼ on A, we say that the quotient A/ ∼ of A under ∼ is the set of parts of the corresponding partition.
1.17¶
Let \(S\) and \(T\) be sets. A function from \(S\) to \(T\) is a subset \(F ⊆ S × T\) such that for all \(s ∈ S\), there exists a unique \(t ∈ T\) with \((s, t) ∈ F\).
The function \(F\) is often denoted \(F : S → T\) . From now on, we write \(F(s) = t\), or sometimes \(s \mapsto t\), to mean \((s, t) ∈ F\). For any \(t ∈ T\) , the preimage of \(t\) along \(F\) is the subset \(f^{−1}(t) := {s ∈ S | F(s) = t}\).
A function is called surjective, or a surjection, if for all \(t ∈ T\) , there exists \(s ∈ S\) with \(F(s) = t\). A function is called injective, or an injection, if for all \(t ∈ T\) and \(s_1,s_2 ∈ S\) with \(F(s_1) = t\) and \(F(s_2) = t\), we have \(s_1 = s_2\). A function is called bijective if it is both surjective and injective.
[img serjective_injective]
1.23¶
If \(F : X → Y\) is a function and \(G : Y → Z\) is a function, their composite is the function \(X → Z\) defined to be \(G(F(x))\) for any \(x ∈ X\). It is often denoted \(G ◦ F\), but we prefer to denote it \(F;G\). It takes any element \(x ∈ X\), evaluates \(F\) to get an element \(F(x) ∈ Y\) and then evaluates \(G\) to get an element \(G(F(x))\).
1.25.¶
A preorder relation on a set \(X\) is a binary relation on \(X\), here denoted with infix notation \(≤\), such that
x ≤ x; (reflexivity) and
if x ≤ y and y ≤ z, then x ≤ z. (transitivity)
If \(x ≤ y\) and \(y ≤ x\), we write \(x \cong y\) and say \(x\) and \(y\) are equivalent. We call a pair \((X, ≤)\) consisting of a set equipped with a preorder relation a preorder.
1.31.¶
A graph \(G = (V, A,s, t)\) consists of a set \(V\) whose elements are called vertices, a set \(A\) whose elements are called arrows, and two functions \(s, t : A → V\) known as the source and target functions respectively. Given \(a ∈ A\) with \(s(a) = v\) and \(t(a) = w\), we say that a is an arrow from \(v\) to \(w\).
By a path in \(G\) we mean any sequence of arrows such that the target of one arrow is the source of the next. This includes sequences of length 1, which are just arrows \(a ∈ A\) in \(G\), and sequences of length 0, which just start and end at the same vertex \(v\), without traversing any arrows.
1.54¶
A monotone map between preorders \((A, ≤_A)\) and \((B, ≤_B)\) is a function \(f : A → B\) such that, for all elements \(x, y ∈ A\), if \(x ≤_A y\) then \(f (x) ≤_B f (y)\).
1.70.¶
Let \((P, ≤_P)\) and \((Q, ≤_Q)\) be preorders. A monotone function \(f : P → Q\) is called an isomorphism if there exists a monotone function \(g : Q → P\) such that \(f ; g = id_P\) and \(g ; f = id_Q\). This means that, for any \(p ∈ P\) and \(q ∈ Q\), we have
\(p = g( f (p))\) and \(q = f (g(q))\).
We refer to \(g\) as the inverse of \(f\) , and vice versa: \(f\) is the inverse of \(g\). If there is an isomorphism \(P → Q\), we say that \(P\) and \(Q\) are isomorphic.
1.76¶
Let \((P, ≤)\) be a preorder, and let \(A ⊆ P\) be a subset. We say that an element \(p ∈ P\) is a meet of \(A\) if
for all \(a ∈ A\), we have \(p ≤ a\),
for all \(q\) such that \(q ≤ a\) for all \(a ∈ A\), we have that \(q ≤ p\).
We write \(p = \bigwedge A\), \(p = \bigwedge_{a∈A} a\), or, if the dummy variable a is clear from context, just \(p = \bigwedge_A a\). If \(A\) just consists of two elements, say \(A = {a, b}\), we can denote \(\bigwedge A\) simply by \(a ∧ b\).
Similarly, we say that p is a join of \(A\) if
for all \(a ∈ A\) we have \(a ≤ p\),
for all \(q\) such that \(a ≤ q\) for all \(a ∈ A\), we have that \(p ≤ q\).
We write \(p = \bigvee_A\) or \(p = \bigvee_{a∈A} a\), or when \(A = {a, b}\) we may simply write \(p = a ∨ b\).
1.87¶
We say that a monotone map \(f : P → Q\) preserves meets if \(f (a ∧ b) \cong f (a) ∧ f (b)\) for all \(a, b ∈ P\). We similarly say \(f\) preserves joins if \(f (a ∨ b) \cong f (a) ∨ f (b)\) for all \(a, b ∈ P\).
1.88¶
We say that a monotone map \(f : P → Q\) has a generative effect ifthere exist elements \(a, b ∈ P\) such that \(f (a) ∨ f (b) \ncong f (a ∨ b)\).
1.90¶
A Galois connection between preorders \(P\) and \(Q\) is a pair of monotone maps \(f : P → Q\) and \(g : Q → P\) such that
\(f (p) ≤ q\) if and only if \(p ≤ g(q)\). (1.6)
We say that \(f\) is the left adjoint and \(g\) is the right adjoint of the Galois connection.
1.112¶
A closure operator \(j : P → P\) on a preorder \(P\) is a monotone map such that for all \(p ∈ P\) we have
\(p ≤ j(p)\),
\(j(j(p)) \cong j(p)\).