Noam Zeilberger imploid (changes)

Skip the Navigation Links | Home Page | All Pages | Latest Revisions | Authors |

Showing changes from revision #4 to #5: Added | Removed | Changed

Contents

Definition

An imploid is a preordered set (X,≤)(X,\le) equipped with a binary operation ⊸\multimap (called “implication”) which is contravariant in its first argument and covariant in its second argument:

(1)a 2≤a 1b 1≤b 2 a 1⊸b 1≤a 2⊸b 2 \array{ \arrayopts{\rowlines{solid}} a_2 \le a_1 \quad b_1 \le b_2 \\ a_1\multimap b_1 \le a_2\multimap b_2 }

and which satisfies the composition law:

(2)b⊸c≤(a⊸b)⊸(a imp ⊸c) b \multimap c \le (a \multimap b) \multimap (a \imp \multimap c)

for all a,b,c∈Xa,b,c \in X. An imploid is said to be unital if it moreover contains an element II (“unit”) satisfying identity and unit laws:

(3)I≤a⊸a I \le a \multimap a
(4)I⊸a≤a I \multimap a \le a

for all a∈Xa \in X.

Special properties

In every unital imploid (P,≤,⊸,I)(P,\le,\multimap,I) we have that a≤ba \le b implies I≤a⊸bI \le a \multimap b; we say that PP is normalized if the converse is also true.

We say that an imploid is commutative if it validates the double-negation introduction law:

(5)a≤(a⊸b)⊸b a \le (a \multimap b) \multimap b
Proposition

If (P,≤,⊸)(P,\le,\multimap) is a commutative imploid then it validates the following laws:

  1. (sequential composition): a⊸b≤(b⊸c)⊸(a⊸c)a \multimap b \le (b \multimap c) \multimap (a \multimap c)
  2. (exchange): a⊸(b⊸c)≤b⊸(a⊸c)a \multimap (b \multimap c) \le b \multimap (a \multimap c)

Examples

From a group

Any group G=(G,⋅,I,(−) −1)G = (G,\cdot,I,(-)^{-1}) can be seen as a unital, normalized imploid, by taking the preorder to be the equality relation and defining a⊸b:=b⋅a −1a \multimap b \mathbin{:=} b\cdot a^{-1}. In this case, the composition law (2) holds because

b⊸c=cb −1=ca −1ab −1=(a⊸b)⊸(a⊸c) b \multimap c = c b^{-1} = c a^{-1} a b^{-1} = (a \multimap b) \multimap (a \multimap c)

while the identity and unit laws (3) and (4) likewise follow immediately from the group axioms.

Relating imploids and dmonoids

(See article dmonoid for the definition.)

Via existence of left/right adjoints

It is well-known that if CC has the structure of a monoidal category and for every object a∈Ca \in C, the tensor functor −⊗a:C→C-\otimes a : C \to C has a right adjoint −⊗a⊣[a,−]-\otimes a\dashv [a,-], then CC can also be given the structure of a closed category. But what about the converse? In other words, if CC is a closed category and every functor [a,−][a,-] has a left adjoint, is CC also a monoidal category? It turns out that the answer is no, because in general the associator maps

α a,b,c:(a⊗b)⊗c→a⊗(b⊗c)\alpha_{a,b,c} : (a \otimes b)\otimes c \to a \otimes (b\otimes c)

are not necessarily invertible, i.e., they only establish associativity up to natural transformation, and not up to natural isomorphism.

Proposition

(cf. Street 2013): If M=(M,≤,⋅,I)M = (M,\le,\cdot,I) is a dmonoid for which each operation −⋅a:M→M-\cdot a : M \to M (a∈Ma \in M) has a right adjoint operation a⊸−:M→Ma \multimap - : M \to M, then MM is also a unital imploid. Conversely, if P=(P,≤,⊸,I)P = (P,\le,\multimap,I) is a unital imploid for which each operation a⊸−:P→Pa \multimap - : P \to P has a left adjoint operation −⋅a:P→P-\cdot a : P \to P, then PP is also a dmonoid.

Dual yoneda embeddings

Proposition

Any dmonoid M=(M,≤,⋅,I)M = (M,\le,\cdot,I) induces a unital imploid M ↓M^\downarrow whose elements are the downsets of MM ordered by inclusion, and where the implication and unit are defined by:

A⊸B:={m∣∀a.a∈A⇒m⋅a∈B} A \multimap B \mathbin{:=} \{\, m \mid \forall a.\, a\in A \Rightarrow m\cdot a \in B\,\}
I ↓:={m∣m≤I} I^\downarrow \mathbin{:=} \{\, m \mid m \le I \,\}
Proposition

Any unital imploid P=(P,≤,⊸,I)P = (P,\le,\multimap,I) induces a dmonoid P ↑P^\uparrow whose elements are the upsets of PP ordered by reverse inclusion, and where the multiplication and unit are defined by:

A⋅B:={p∣∃b.b⊸p∈A∧b∈B} A \cdot B \mathbin{:=} \{\, p \mid \exists b.\, b\multimap p \in A \wedge b\in B\,\}
I ↑:={p∣I≤p} I^\uparrow \mathbin{:=} \{\, p \mid I \le p\,\}

References

  • B. J. Day and M. L. Laplaza, On Embedding Closed Categories, Bull. Austral. Math. Soc. 18 (1978), 357-371.

  • Ross Street. Skew-closed categories. Journal of Pure and Applied Algebra 217(6) (June 2013), arXiv:1205.6522

  • Kornel Szlachanyi. Skew-monoidal categories and bialgebroids. arXiv:1201.4981

Last revised on June 27, 2017 at 11:55:30. See the history of this page for a list of all contributions to it.

EditDiscussPrevious revisionHide changesHistory (4 revisions) Print Source