Noam Zeilberger imploid (Rev #4, changes)

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

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

Contents

Definition

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

  1. 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)⊸(aimpc) b \multimap c \le (a \multimap b) \multimap (a \imp c)

    for all a,b,c∈Xa,b,c \in X; and

  2. an element I∈XI \in X (called 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.

(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 }

An and imploid which is satisfies said the to beundirectedcomposition law if the underlying preorder is symmetric, so that (2)-(4) also hold in the converse direction. On the other hand, the imploid is said to be commutative if it additionally satisfies an exchange law:

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

for all a,b,c∈Xa,b,c \in X . Finally, An in any imploid we is have said that to bea≤ba \le bunital implies if it moreover contains an elementI≤a⊸b I \le a \multimap b ; we (“unit”) say satisfying that the imploid isnormalizedidentity if and the converse is also true.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 an a undirected unital, (normalized) normalized imploid, by taking the preorder to be the equality relation and defininga⊸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 an a unital imploid. Conversely, ifP=(P,≤,⊸,I)P = (P,\le,\multimap,I) is an a unital imploid for which each operationa⊸−: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 an a unital imploidM ↓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 imploidP=(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

Revision on June 26, 2017 at 21:03:56 by Noam Zeilberger?. See the history of this page for a list of all contributions to it.

DiscussNext revision (to current)Previous revision (3 more)Current version of pageHide changesHistory (4 revisions)Rollback Source