Chapter_2_monoidal_Preorders

--- title: Chapter_2_monoidal_Preorders tags: Category, V-category description: Monoidal Preorders and V-Category type: pdf slideOptions: theme: white --- ###### tags: `Category` `V-category` # **<div align="center">Chapter Two: Monoidal Preorders and V-category</div>** <div class="alert alert-info">Example text highlighted in blue background.</div> ### **2.1 Symmetric Monoidal Preorders** In the last chapter, we have introduces preorders, as a enriched property to a set, which allow us to not just doing ordering to a set, but also partitioning, up-networking (i.e. Upper Set), and analysis function between sets with monotonic requirement. In this chapter, we want to continue our process of set enrichment, that making our "set" more fit to real world application. We will add concept of operations between any two elements of a set. But firstly, we will put preorder aside a bit, just define some simple structure on sets that allow operation between two elements. > **Definiton (monoid)** >> A monoid consists of a set M, a function ∗ : M × M → M called the monoid multiplication, and an element e ∈ M called the monoid unit, such that, when you write ∗(m, n) as m ∗ n, i.e. using infix notation, the following properties hold: >> (a). $m * e = e * m = m$; >> (b). $(m * n) * p = m * (m * n)$ for all $m,n,p \in M$, denote $(M,e,*)$ The monoid is called commutative if also $m * n = n * m$ > **Example 2.1.1** >- $(\Bbb{N},0,+)$, $(\Bbb{Z},0,+)$, and $(\Bbb{R},0,+)$ are all commutative monoid. Now we can define our target of this chapter > **Definiton (symmetric monoidal structure)** >> A symmetric monoidal structure is a commutative monoid on a preorder $(M, \le)$ with folloing property: >> (a). fol all $x_1, x_2,y_1,y_2\in M,\ if\ x_1\le y_1\ and\ x_2\le y_2,\ then\ x_1*x_2\le y_1*y_2$ >> We call this condition monotonicity. We denote the symmetric monoid structure $(M, \le, e, *)$ > **Example 2.1.2** >- $(\Bbb{N},\le, 0,+)$, $(\Bbb{Z},\le, 0,+)$, and $(\Bbb{R},\le, 0,+)$ are all symmetric monoid structure. >- However, $(\Bbb{Z},\le, 1,\times)$, and $(\Bbb{R},\le, 1,\times)$ are not symmetric monoid structure.(why?) <div class="alert alert-info">We will know introduce more examples.</div> - #### Boolean with AND/OR We can define a monoidal structure on B by letting the monoidal unit be **True** and the monoidal product be ∧ (AND). If one thinks of false = 0 and true = 1, then ∧ corresponds to the usual multiplication operation ∗. So we have a monoidal preorder which we denote Bool:=(B, ≤, true, ∧). We can also define monoidal product be $\lor$ (Or), then the monoidal unit would be **False**, we have $(\Bbb{B},\le, False, \lor)$. - #### Natual Number and Divisibility We write m|n to mean that m divides n, for all $m,n\in \Bbb{N}$. Then with monoidal unit 1 and monoidal product be normal multiplication, we can see that the monotonicity follows. Indeed, if $x_1|y_1$ and $x_2|y_2$ then $(x_1*x_2)|(y_1*y_2)$. So except from $(\Bbb{N},\le,0,+)$, we also have $(\Bbb{N},|,1,\times)$. - #### Power Set It is not the first time we meet power set. So for a set S, consider the structure $(\wp(S), \le, S, \cap)$. This is a symmetric monoidal structure. Indeed, $(\wp(S),S,\cap)$ is a commutative monoid (check it!). We only need to check the monotonicity. For $A,B,C,D \in \wp(S)$, if $A \subseteq B$ and $C \subseteq D$, then $\forall x \in A\cap C,\ a\in B\cap C,\ then\ a\in B\cap D$, implies $A\cap C\subseteq B\cap D$. > **Proposition 2.1** > Suppose $M = (M, ≤)$ is a preorder and $M^{op} = (M, ≥)$ is its opposite. If (M, ≤, e, *) is a symmetric monoidal preorder then so is its opposite, (M, ≥, e, *). >> **Proof:** >> Ommited. We only need to show monotonicity. > **Exercises 2.1* >1. Check that **example 2.1.1** are correct claims. >2. Check that **example 2.1.2** are correct claims for the first part. >3. Show why $(\Bbb{Z},\le, 1,\times)$, and $(\Bbb{R},\le, 1,\times)$ are not symmetric monoid structure. >4. Show that $(\wp(S),S,\cap)$ is a commutative monoid >5. Prove the Propostion 2.1. --- ### **2.2 V-Category and its constructions** We have "enriched" preorders with operation between elements and unit of a preorder. This section we are going to do further enrichment. But we will introduce the Monoidal monotone map first. > **Definiton (monoidal monotone map)** >> Let P = (P, $≤_P$ , $e_P$ , $*_P$ ) and Q = (Q, $≤_Q$ , $e_Q$ , $*_Q$ ) be monoidal preorders. A monoidal monotone from P to Q is a monotone map f : (P, $≤_P$ ) → (Q, $≤_Q$ ), satisfying two conditions: >> (a). $e_Q \le_Q f(e_P)$, and >> (b). $f(p_1) * f(p_2) \le_Q f(p_1 * p_2)$, for all $p_1, p_2 \in P$ > **Example 2.2.1** >- There is a monoidal monotone i : (N, ≤, 0, +) → (R, ≤, 0, +), where i(n) = n for all n ∈ N. It is clearly monotonic, m ≤ n implies i(m) ≤ i(n). It is even strict monoidal because i(0) = 0 and i(m + n) = i(m) + i(n). Now we formally introduce "Enrichment". > **Definiton (V-categories)** >> Let V = (M, ≤, e, *) be a symmetric monoidal preorder. A V-category X consists of two constituents, satisfying two properties. To specify X, >> (i). one specifies a set Ob(X), elements of which are called objects; >> (ii).for every two objects x, y, one specifies an element X(x, y) ∈ V, called the hom- object. >> The above constituents are required to satisfy two properties: >> (a). for every object x ∈ Ob(X) we have e ≤ X(x, x), and >> (b). for every three objects x, y, z ∈ Ob(X), we have X(x, y) * X(y, z) ≤ X(x, z). We call V the base of the enrichment for X or say that X is enriched in V. > **Example 2.2.2** >- From every preorder we can construct a Bool-category, the objects of X are simply the elements of the preorder, for every pair of objects (x, y) we need an element of B = {false, true}: simply take true if x ≤ y, and false if otherwise. The monoidal unit e of Bool is true with operation "AND". It is easy to check that this construction obey (a) and (b) in definition of V-catetory. We can also construct a preorder from a Bool-Category. >- A metric space (X, d) with only reflexive, i.e. d(x, x) = 0, and triangle inequality is called Lawvere Metric Space. A Lawvere Metric Space is a Cost-category, with the Cost monoidal preorder be Cost = $([0,\infty], \ge, 0, +)$. So the set $\Bbb{R}$ of real numbers with metric $d(x,y) = |y-x|$ is a Cost-category. >- A weighted graph is a Cost-category. More interestingly. A Cost-weighted graph might have a Matrix-representation that will have great feature in compuation. We will discuss its details in the next section. Now that we have a good intuition for what V-categories are, we give three examples of what can be done with V-categories, which are change of basis, enriched functors, and V-product. > **Definiton (Changing basis)** >> Let f : V → W be a monoidal monotone. Given a V-category X, one forms the associated W-category, say $X_f$ as follows. >> (i). We take the same objects: $Ob(X_f) := Ob(X)$. >> (ii). For any c, d ∈ Ob(X), put $X_f(c, d) := f (X(c, d))$. >> One can check that $X_f$ is a W-category: >> (a). $e_W \le f(e_v) \le f(X(c,c)) = e_f(c,c)$ >> (b). for every $c,d,e \in Ob(X)$, we have $$X_f(c,d) *_W X_f(d,e) = f(X(c,d)) *_W f(X(d,e)) \le f(X(c,d) *_V X(d,e)) \le f(X(c,e)) = X_f(c,e)$$ > **Example 2.2.3** >- As an example, consider the function f : [0, ∞] → {true, false} given by $$f(x) := \begin{cases} \text{True} &\quad\text{if x = 0}\\ \text{False} &\quad\text{if x > 0} \\ \end{cases}$$ > It is easy to check that f is monotonic and that f preserves the monoidal product and monoidal unit; that is, it’s easy to show that f is a monoidal monotone. Thus f lets us convert Lawvere metric spaces into preorders. > **Definiton (Enriched functors)** >> Let X and Y be V-categories. A V-functor from X to Y, denoted F : X → Y, consists of one constituent: >> (i). a function $F: Ob(X) \mapsto Ob(Y)$ >> subject to one constraint >> (a). for all $x_1, x_2 \in Ob(X)$, one has $X(x_1, x_2) \le Y(F(x_1), F(x_2))$ > **Example 2.2.4** >- Preorders are Bool-categories, where $X(x_1 , x_2) = true$ is denoted $x_1 ≤ x_2$, thus monotone maps between preorders would correspond exactly to Bool-functors. >- Lawvere metric spaces are Cost-categories. The definition of Cost-functor recovers the notion of Lipschitz function. A Lipschitz (or more precisely, 1-Lipschitz) function is one under which the distance between any pair of points does not increase. That is, given Lawvere metric spaces $(X, d_X)\ and\ (Y, d_Y)$, a Cost-functor between them is a function F : X → Y such that for every $x_1 , x_2 ∈ X$ we have $d_X(x_1, x_2) ≥ d_Y(F(x_1), F(x_2))$. > **Definiton (V-products)** >> Let X and Y be V-categories. Define their V-product, or simply product, to be the V-category X × Y with >> (i). $Ob(X \times Y) := Ob(X)\times Ob(Y)$,\ >> (ii). $(X\times Y)((x,y),(x^, ,y^,)) := X(x,x^,)*Y(y,y^,)$ In the next section, we will find V-categories' mattrix representation. > **Exercises 2.2** >1. construct a preorder from a Bool-Category. >2. Check that the set of reals $\Bbb{R}$ is indeed a Cost-Category. >3. Find a metric for $\Bbb{R}^2$, the 2-dimensional space of reals. Check if it is still a Cost-Category with the metric you found. >4. Check that the f function in **Example 2.2.3** is indeed monoidal monotonic. >5. Find two Bool-category X, Y, construct the Bool-functor between them. --- ### **2.3 V-Category and its representation** The definition of V-category makes sense for any symmetric monoidal preorder V. But that does not mean that any base of enrichment V is as useful as any other. In this section we define closed monoidal categories, which in particular enrich themselves! “Before you can really enrich others, you should really enrich yourself.” > **Definiton (closed)** >> A symmetric monoidal preorder V = (M, ≤, e, *) is called symmetric monoidal closed if, for every two elements v, w ∈ V, there is an element $v\to w \in V$, called the hom-element, with the property $$(a * v) \le w \iff \ a\le (v\to w)$$, for all $a,v,w \in M$ This definition says precisely that there is a Galois connection in the sense of Definition of Galois connection. i.e. he map $(− * v) : V → V$ given by multiplying with v has a right adjoint. We write this right adjoint $(v \to -) : V → V$. > **Example 2.3.1** >- The monoidal preorder Cost = ([0, ∞], ≥, 0, +) is monoidal closed. Indeed, for any x, y ∈ [0, ∞], define $x \to y := max(0, y-x)$. Then for any $a,x,y \in [0, \infty]$, we have >$$a + x \ge y \ \iff \ a \ge (x \to y)$$ > **Proposition 2.2** > Suppose V = (M, ≤, e, *, $\to$) is a symmetric monoidal preorder that is closed. Then > (a). For every v ∈ V, the monotone map − * v : (M, ≤) → (M, ≤) is left adjoint to v $\to$ - : (M, ≤) → (M, ≤). > (b). For any element v ∈ M and set of elements A ⊆ M, if the join $\lor_{a∈A} a$ exists then so does $\lor_{a∈A} (v * a)$ and we have $(v * \lor_{a\in A} a) \cong \lor_{a\in A}(v*a)$; > c). For any $v,w \in M$, we have $v * (v \to w) \le w$ > (d). For any $v \in M$, we have $v \cong (e \to v)$ > (e). For any $u,v,w \in M$, we have $(u \to v) * (v\to w)\le (u \to w)$ >> **Proof:** >> (a). This follows directly from definition of closed symmetric monoidal preorder >> (b). This follows from the Theorem of Galois connection that left adjoint preserve joins >> c). This is exacly $f(g(q))\le q$, where $f() := - * v$, and $g() := v\to -$ >> (d). $v *e \le v \implies v \le e \to v$ from definition of closure. >> (e). apply (c) twice. $\blacksquare$ To perform matrix multiplication over a monoidal preorder, we need one more thing: joins. > **Definiton (Quantales)** >> A unital commutative quantale is a symmetric monoidal closed preorder V = $(M, ≤, e, *, \to )$ that has all joins: $\lor A$ exist for every $A \subseteq M$. In particular, we often denote the empty join by $0 := \lor \phi$ > **Example 2.3.2** >- Cost = $([0, \infty], \ge, 0, +, \to)$ is a quantale. Now let's look at the definition of matrix multiplication in V-category. > **Definiton (V-Matrix)** >> Let V = (M, ≤, e, *) be a quantale. Given sets X and Y, a matrix with entries in V, or simply a V-matrix, is a function M : X × Y → V. For any x ∈ X and y ∈ Y, we call M(x, y) the (x, y)-entry. Here is how you multiply V-matrices M : X × Y → V and N : Y × Z → V. Their product is defined to be the matrix (M ∗ N) : X × Z → V, with formula >> $$(M*N)(x,z):=\lor_{y\in Y} M(x,y) * N(y,z)$$ Here are an interesting example