Category theory emphasizes that preorders themselves (each a minature world, composed of many relationships) can be related to one another.
Monotone maps are important because they are the right notion of structure-preserving map for preorders.
The map (‘cardinality’) sending a power-set (with inclusion ordering) to the natural numbers with standard ordering is a monotone map.
Given a preorder, the inclusion map of the upper sets of \(P\) (ordered by inclusion) to the power set of \(P\) (ordered by inclusion) is a monotone map.
A monotone map between preorders \((A, \leq_A), (B, \leq_B)\)
A function \(A \xrightarrow{f} B\) such that \(\forall x,y \in A: x \leq_A y \implies f(x) \leq_B f(y)\)
A dagger preorder
\(q \leq p \iff p \leq q\) - this is tantamount to an equivalence relation.
A preorder isomorphism
A monotone map for which there exists an inverse monotone map (\(f;g=id\) and \(g;f = id\))
If this exists, we say the preorders involved are isomorphic.
A pullback along a monotone map \(P \xrightarrow{f} Q\)
We take the preimage of \(f\), but not for a single element of \(Q\) but rather an upper set of \(Q\).
Noting that upper sets are monotone maps to Bool, it follows that the result of a pullback is an upper set in \(P\) follows from the fact that composition preserves monotonicity.
Therefore the type of the pullback is \(U(Q) \xrightarrow{f^*} U(P)\)
Let \((P, \leq)\) be a preorder and recall the opposite preorder.
Show that the set \(\uparrow(p) := \{p' \in P\ |\ p \leq p'\}\) is an upper set for any \[p \in P\]
Show that this construction defines a monotone map \((P, \leq^{op}) \xrightarrow{\uparrow} U(P)\)
Show that \(p \leq p' \iff \uparrow(p') \subseteq \uparrow(p)\)
Draw a picture of the map \(\uparrow\) in the case where \(P\) is the preorder \((b\geq a \leq c)\).
This is the Yoneda lemma for preorders (up to equivalence, to know an element is the same as knowing its upper set).
This is basically the definition an upper set starting at some element.
Interpreting the meaning of the preorder in the domain and codomain of \(\uparrow\), this boils down to showing \(p \leq p'\) implies \(\uparrow(p') \subseteq \uparrow(p)\) - This is shown by noting that \(p' \in \uparrow(p)\) and anything ‘above’ \(p'\) (i.e. \(\uparrow(p')\)) will therefore be in \(\uparrow(p)\).
Forward direction has been shown above - The other direction is shown just by noting that \(p\prime\) must be an element of \(\uparrow(p\prime)\) and by the subset relation also in \(\uparrow(p')\), therefore \(p \leq p'\).
Show that when \(P\) is a discrete preorder, then every function \(P \rightarrow Q\) is a monotone map, regardless of the order \(\leq_Q\).
The only time the monotonicity criterion is deployed is when two elements of \(P\) are related, and for a discrete category this means we only have to check whether \(f(a) \leq_Q f(a)\), which is true because preorders are reflexive.
Recall skeletal preorders and dagger preorders.
Show that a skeletal dagger preorder is just a discrete preorder (and hence can be identified with a set)
Because preorders are reflexive, we just have to show \(a \ne b \implies a \not\leq b\), or its contrapositive: \(a \leq b \implies a = b\).
\(a \leq b \overset{dagger}{\implies} b \leq a \overset{skeletal}{\implies} a = b\)
For any preorder, the identity function is a monotone map.
The composition of two monotone maps (\(P \xrightarrow{f} Q \xrightarrow{g} R\)) is also monotone.
Monotonicity translates to \(a \leq b \implies a \leq b\) and is trivially true.
Need to show: \(a \leq_P b \implies g(f(a)) \leq_R g(f(b))\)
The monotonicity of \(f\) gives us \(f(a) \leq_Q f(b)\) and the monotonicity of \(g\) gives us the result we need.
Let \(P\) be a preorder. Monotone maps \(P \rightarrow \mathbb{B}\) are in one-to-one correspondance with upper sets of \(P\).
Let \(P \xrightarrow{f} \mathbb{B}\) be a monotone map. The subset \(f^{-1}(true)\) is an upper set.
Suppose \(p \in f^{-1}(true)\) and \(p \leq q\).
Then \(true = f(p) \leq f(q)\) because \(f\) is monotonic.
But there is nothing strictly greater than \(true\) in \(\mathbb{B}\), so \(f(q) = true\) and therefore \(q \in f^{-1}(true)\) too.
Suppose \(U \in U(P)\), and define \(P\xrightarrow{f_U}\mathbb{B}\) such that \(f_U=true \iff p \in U\)
Given there are only two values in \(B\) and an arbitrary \(p\leq q\), the only way for this to not be monotone is for \(f_U(p) \land \neg f_U(q)\) but this defies the definition of an upper set.
The two constructions are mutually inverse.