Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Arrows in the category $\bf Rel$ are binary (2-valued) relations between set objects.

Do ternary, 4-term, $n$-term and variadic (2-valued) relations form categories? (Or perhaps one category?).

It may be convenient to study categorically how binary relations relate to mutual relations, as this and this question, or to represent Helly type relations.

$n$-ary relations are mentioned in nlab, but no explicit category seems defined. Neither does the concept seem to be discussed in Freyd & Scedrov's Categories, Allegories. Did I miss it?

By analogy with graphs and hypergraphs, where the former are defined by edges between pairs of vertices, whereas the latter are defined by arbitrary subsets of vertices, it's not clear offhand how would arrows be defined even for a ternary relation $R \subset X \times Y \times Z$?

share|improve this question
1  
Do you want to know about categories where relations are objects or where they are morphisms? –  Hagen von Eitzen Jan 16 '13 at 6:29
    
@HagenvonEitzen, I don't have an opinion on that - but simply adopted the standard definition of $\bf Rel$ –  alancalvitti Jan 16 '13 at 6:41
    
Sure, but in Rel, relations $\subset A\times B$ are used as morphisms $A\to B$ as they nicely generelize functions (which are just special binary relations). As we only consider morphisms from one object to another in category theory, anything beyond binary does not fit in as a morphism as such. –  Hagen von Eitzen Jan 16 '13 at 7:02
    
Yes I know that's why I added the last paragraph in my Q, but thought maybe there's a potential way to represent $n$-ary relations via products, maybe by equalizing $A \times B \to C$, $B \times C \to A$, $C \times A \to B$ ? –  alancalvitti Jan 16 '13 at 7:07
    
Relations (not only binary relations) form a "category with star morphisms" (over $\mathbf{Rel}$) as I define them in my book: mathematics21.org/algebraic-general-topology.html - I suspect that I am the first person who explicitly defined categories with star morphisms, as they are important for my research of products of morphisms. –  porton Jun 2 at 19:04

2 Answers 2

I hope I understand your question correctly. If you are referring to 3-ary relations as subsets of $A\times B\times C$ and so on for $n$-ary relations in general then these are in fact already incorporated in the category $Rel$. The category $Rel$ has a monoidal structure given by the ordinary cartesian product of sets. Thus, a ternary relation $R \subseteq A\times B\times C$ can be seen as a relation $R\subseteq (A\times B)\times C$ and thus as an arrow in $Rel$ from $A\times B$ to $C$. Similarly any $n$-are relation can be interpreted as a binary relation.

Just like $Rel$ is a dagger category (that is it admits an involution) the monoidal structure on $Rel$ turns it into a cyclic operad. So, if I understand your question correctly, all of the relations you are interested in form the cyclic operad $Rel$, which is completely defined in terms of the category $Rel$ of binary relations + its monoidal structure. I hope this helps.

share|improve this answer
    
Thanks Ittay, I wasn't aware of the monoidal structure. How is the distinction between pairwise versus mutual relations on $A \times B \times C$? represented? –  alancalvitti Jan 16 '13 at 5:15
    
I'm not sure what you mean by pairwise vs. mutual. –  Ittay Weiss Jan 16 '13 at 5:16
    
For example, pairwise intersection of 3 sets doesn't imply that all 3 intersect. Similarly, pairwise independence of random variables doesn't imply mutual independence. (In both cases the converse implications are true) –  alancalvitti Jan 16 '13 at 5:18
    
I don't see how this issue is related to n-ary relations. –  Ittay Weiss Jan 16 '13 at 5:18
    
The ternary relations I just mentioned are special cases of $n$-ary relations, $n=3$, while binary relations are those with $n=2$ –  alancalvitti Jan 16 '13 at 5:19

You can define a multicategory of relations: Objects are sets, multimorphisms $(X_1,\dotsc,X_n) \to Y$ are subsets of $X_1 \times \dotsc \times X_n \times Y$. The identity $(Y) \to Y$ is the usual diagonal $\{(y,y) : y \in Y\}$. The composition $R \circ (S_1,\dotsc,S_n)$ of $R : (X_1,\dotsc,X_n) \to Y$ with $S_i : (X_{i1},\dotsc,X_{im_i}) \to X_i$ (for $i \in \{1,\dotsc,n\}$) is given by the set of tuples $\{(a_{11},\dotsc,a_{1m_1},a_{21},\dotsc,a_{n\,m_n},y)$ such that there is some $b \in \prod_{i=1}^{n} X_i$ with $(b,y) \in R$ and $(a_{i1},\dotsc,a_{im_i},b_i) \in S_i$ for all $i \in \{1,\dotsc,n\}$.

Actually, this is the multicategory associated to the usual monoidal category of relations (where the monoidal structure is given by products of sets).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.