Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

• Forgot your password?
• Apply for membership

1. • CommentRowNumber1.
   • CommentAuthorDavid Tanzer
   • CommentTimeFeb 13th 2013
   • PermaLink
   Author: David Tanzer
   Format: TextLet R be a binary relation on a set S. Let us picture R as a finite, square, Boolean matrix, with one row/column for each member of S. Now let's view these matrices as members of a Boolean vector space 2^S. So R has a determinant, which is either 0 or 1. Let's call the relation even if its determinant is 0, and 1 if it's determinant. We also have a "funny composition" of binary relations, given by mod-2 matrix multiplication. The composition of two even relations is even, etc. Can anyone give a concrete interpretation of the _meaning_ of this composition? Can anyone give a concrete interpretation of the _meaning_ of the determinant of a relation? If the world of binary relations on a set is neatly divided into two groups, I feel like this must have some meaning, that can be explained in simple terms.

   Let R be a binary relation on a set S. Let us picture R as a finite, square, Boolean matrix, with one row/column for each member of S.
   
   Now let's view these matrices as members of a Boolean vector space 2^S.
   
   So R has a determinant, which is either 0 or 1. Let's call the relation even if its determinant is 0, and 1 if it's determinant.
   
   We also have a "funny composition" of binary relations, given by mod-2 matrix multiplication.
   
   The composition of two even relations is even, etc.
   
   Can anyone give a concrete interpretation of the _meaning_ of this composition?
   
   Can anyone give a concrete interpretation of the _meaning_ of the determinant of a relation? If the world of binary relations on a set is neatly divided into two groups, I feel like this must have some meaning, that can be explained in simple terms.
2. • CommentRowNumber2.
   • CommentAuthorTodd_Trimble
   • CommentTimeFeb 13th 2013
   • (edited Feb 13th 2013)
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexDavid: as you probably know, if we use not the ring structure on $\{0, 1\}$ where $+$ is symmetric difference (exclusive 'or'), but the [[rig]] structure on $\{0, 1\}$ where $+$ is the usual join (inclusive 'or'), then matrix composition is the same as relational composition: $$(R \circ S)(x, z) = \sum_y R(x, y) \cdot S(y, z) = \exists_y R(x, y) \wedge S(y, z)$$ (notice that infinite sums make sense in this context; they do not for the ring structure). I see you are assuming that your set $S$ is finite. Anyway, the meaning of matrix multiplication for the Boolean ring case is weird, but similar: for $R$, $R'$ two binary relations on $S$, we have $(R' \circ R)(x, z) = 1$ iff there exist an odd number of $y$ such that $R'(x, y) = 1$ and $R(y, z) = 1$. I'd like to think further about the meaning of the determinant.

   David: as you probably know, if we use not the ring structure on $\{0, 1\}$ where $+$ is symmetric difference (exclusive ’or’), but the rig structure on $\{0, 1\}$ where $+$ is the usual join (inclusive ’or’), then matrix composition is the same as relational composition:

   $$(R \circ S)(x, z) = \sum_y R(x, y) \cdot S(y, z) = \exists_y R(x, y) \wedge S(y, z)$$

   (notice that infinite sums make sense in this context; they do not for the ring structure). I see you are assuming that your set $S$ is finite.

   Anyway, the meaning of matrix multiplication for the Boolean ring case is weird, but similar: for $R$, $R'$ two binary relations on $S$, we have $(R' \circ R)(x, z) = 1$ iff there exist an odd number of $y$ such that $R'(x, y) = 1$ and $R(y, z) = 1$.

   I’d like to think further about the meaning of the determinant.

3. • CommentRowNumber3.
   • CommentAuthorRodMcGuire
   • CommentTimeFeb 13th 2013
   • PermaLink
   Author: RodMcGuire
   Format: MarkdownItexSome terminology: All binary relations on set $S$ form the Boolean lattice $Rel(S) = 2^{S\times S}$. $Rel(S)$ also is a monoid where the monoid operation is relation composition. Together these mean that $Rel(S)$ is a [[quantale]], in particular a *-quantale, where the *-operation is relational opposite.

   Some terminology:

   All binary relations on set $S$ form the Boolean lattice $Rel(S) = 2^{S\times S}$. $Rel(S)$ also is a monoid where the monoid operation is relation composition. Together these mean that $Rel(S)$ is a quantale, in particular a *-quantale, where the *-operation is relational opposite.

4. • CommentRowNumber4.
   • CommentAuthorDavid Tanzer
   • CommentTimeFeb 13th 2013
   • (edited Feb 13th 2013)
   • PermaLink
   Author: David Tanzer
   Format: TextTodd: Yes, I meant to say that S is finite. Thanks for the clarification on my first question. To paraphrase, using the rig, the composite relation says whether there exists a path from one endpoint to the other, and using the ring, the composite specifies the parity of the number of paths from one endpoint to another. After talking this through, I see that the determinant does have a set-theoretic meaning: it is the parity of the number of subrelations that are permutations. For instance, the identity relation has only one subrelation which is a permutation -- which is itself. That is because each term of the determinant corresponds to a permutation of the set. I wonder if these concepts have any further applications within mathematics, or if they have the status of curious exhibits.

   Todd: Yes, I meant to say that S is finite.
   
   Thanks for the clarification on my first question. To paraphrase, using the rig, the composite relation says whether there exists a path from one endpoint to the other, and using the ring, the composite specifies the parity of the number of paths from one endpoint to another.
   
   After talking this through, I see that the determinant does have a set-theoretic meaning: it is the parity of the number of subrelations that are permutations. For instance, the identity relation has only one subrelation which is a permutation -- which is itself. That is because each term of the determinant corresponds to a permutation of the set.
   
   I wonder if these concepts have any further applications within mathematics, or if they have the status of curious exhibits.
5. • CommentRowNumber5.
   • CommentAuthorDavid Tanzer
   • CommentTimeFeb 13th 2013
   • (edited Feb 13th 2013)
   • PermaLink
   Author: David Tanzer
   Format: TextSo the determinant law det(AB) = det(A) * det(B) does say something about these funny structures: when two relations are parity-composed, the parity of the number of permutations contained in the composite is equal to the product of the parities of the number of permutations contained in each of the factors. I have a hunch that there is more to this story, but I have no idea what it is!

   So the determinant law det(AB) = det(A) * det(B) does say something about these funny structures: when two relations are parity-composed, the parity of the number of permutations contained in the composite is equal to the product of the parities of the number of permutations contained in each of the factors.
   
   I have a hunch that there is more to this story, but I have no idea what it is!
6. • CommentRowNumber6.
   • CommentAuthorDavid Tanzer
   • CommentTimeFeb 13th 2013
   • (edited Feb 13th 2013)
   • PermaLink
   Author: David Tanzer
   Format: TextThis is an example where linear algebra has something to say about the structure of finite sets and relations, when viewed through the lens of counting the parity of sets. So I wonder what else it has to say.

   This is an example where linear algebra has something to say about the structure of finite sets and relations, when viewed through the lens of counting the parity of sets.
   
   So I wonder what else it has to say.
7. • CommentRowNumber7.
   • CommentAuthorTodd_Trimble
   • CommentTimeFeb 13th 2013
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItex> it is the parity of the number of subrelations that are permutations So it is! But I don't see the deeper meaning of this yet myself.

   it is the parity of the number of subrelations that are permutations

   So it is! But I don’t see the deeper meaning of this yet myself.

8. • CommentRowNumber8.
   • CommentAuthorDavid Tanzer
   • CommentTimeFeb 13th 2013
   • PermaLink
   Author: David Tanzer
   Format: TextI would say that either it has a deeper meaning, or else it is some kind of joke that is built into mathematics. Here are a few more aspects of this linear-algebraic view of sets. 1. The powerset 2^S is an inner product space, where the inner product of two sets is the parity of their intersection. 2. Therefore, for a set s, the dual of s is the linear functional that operates by first intersecting with s, and then computing the parity. 3. For sets s,t, the tensor product of dual(s) and dual(t) is the function which maps a binary relation R on S to the parity of the intersection of R with the cartesian product s x t.

   I would say that either it has a deeper meaning, or else it is some kind of joke that is built into mathematics.
   
   Here are a few more aspects of this linear-algebraic view of sets.
   
   1. The powerset 2^S is an inner product space, where the inner product of two sets is the parity of their intersection.
   
   2. Therefore, for a set s, the dual of s is the linear functional that operates by first intersecting with s, and then computing the parity.
   
   3. For sets s,t, the tensor product of dual(s) and dual(t) is the function which maps a binary relation R on S to the parity of the intersection of R with the cartesian product s x t.
9. • CommentRowNumber9.
   • CommentAuthorTodd_Trimble
   • CommentTimeFeb 13th 2013
   • (edited Feb 13th 2013)
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItex> This is an example where linear algebra has something to say about the structure of finite sets and relations, when viewed through the lens of counting the parity of sets. Yes, this is something I don't think about much. This may be off-topic or distracting, but it reminds me of one cute result though, that the number of fixed points of an involution on a finite set $S$ has the same parity as $S$. This is the basis of Zagier's proof of the sum-of-two-squares theorem, that I once ranted about a little [here](http://topologicalmusings.wordpress.com/2008/05/04/a-proof-from-the-book/). The group $GL(n, 2)$ (invertible $n \times n$ matrices over the field $\mathbb{Z}/2$) can be interesting. For $n = 2$, we get the symmetric group $S_3$. For $n = 3$, we get a group of order 168, also known as $PSL_2(\mathbb{Z}/7)$, which John Baez could tell you about until the cows come home.

   This is an example where linear algebra has something to say about the structure of finite sets and relations, when viewed through the lens of counting the parity of sets.

   Yes, this is something I don’t think about much. This may be off-topic or distracting, but it reminds me of one cute result though, that the number of fixed points of an involution on a finite set $S$ has the same parity as $S$. This is the basis of Zagier’s proof of the sum-of-two-squares theorem, that I once ranted about a little here.

   The group $GL(n, 2)$ (invertible $n \times n$ matrices over the field $\mathbb{Z}/2$) can be interesting. For $n = 2$, we get the symmetric group $S_3$. For $n = 3$, we get a group of order 168, also known as $PSL_2(\mathbb{Z}/7)$, which John Baez could tell you about until the cows come home.

10. • CommentRowNumber10.
    • CommentAuthorDavid Tanzer
    • CommentTimeFeb 13th 2013
    • (edited Feb 13th 2013)
    • PermaLink
    Author: David Tanzer
    Format: MarkdownHere are some further thoughts on the matter. We began with a set of truth-values V, call them 0 and 1, along with an algebra on them. The two candidates we have been discussing are the ring 2, and the rig 2 which uses disjunction instead of mod-2 addition. Then we can represent sets and relations as V-valued functions. Then linear algebra gives us a toolbox of constructs, which we can then apply to define intersection, union, overlapping of sets, composition of relations, ... By changing the "ground rig" of truth values, we obtain different perspectives on sets and relations. The disjunctive rig 2 is what we are most familiar with. But the ring 2 can also be used, and in the view of the world that it entails, two sets will "overlap" if the parity of their intersection is even. So this is multi-valued logic, cast within the framework of matrix algebra. An interesting case to consider is when the truth-values are themselves relations, and the algebra V is an algebra of relations. Here is a motivating case. In the standard case, a relation R(a,b) gives a truth-value saying whether a and b stand in the relation R. But consider an application where the elements a,b, etc. stand for components in a system. A Boolean-valued relation can answer the simple question as to whether or not a and b are connected in the system. But a richer question is: _how_ are a and b connected? If you consider that a consists of parts a1,...,ak, and b consists of b1,...,bn, then the actual connection between a and b is a relation, of one lower degree, between these constituent parts. So we can have multi-level relations -- even potentially ones that can have an infinite number of levels. Then we are multiplying matrices whose elements are themselves matrices. One fly in the ointment: I don't think that determinant is defined if the rig is not a ring, because it needs the sign of the permutation. But nevermind -- a lot of the structure does generalize. Can you guys give me any pointers to where work in these directions is being carried out? What are some good categorical ways to look at: * Relativizing set and relation theory over a ground rig of truth values * Multi-level relational algebra, possibly with an infinite number of levels of increasing detail

    Here are some further thoughts on the matter.

    We began with a set of truth-values V, call them 0 and 1, along with an algebra on them. The two candidates we have been discussing are the ring 2, and the rig 2 which uses disjunction instead of mod-2 addition.

    Then we can represent sets and relations as V-valued functions. Then linear algebra gives us a toolbox of constructs, which we can then apply to define intersection, union, overlapping of sets, composition of relations, ...

    By changing the "ground rig" of truth values, we obtain different perspectives on sets and relations. The disjunctive rig 2 is what we are most familiar with. But the ring 2 can also be used, and in the view of the world that it entails, two sets will "overlap" if the parity of their intersection is even.

    So this is multi-valued logic, cast within the framework of matrix algebra.

    An interesting case to consider is when the truth-values are themselves relations, and the algebra V is an algebra of relations.

    Here is a motivating case. In the standard case, a relation R(a,b) gives a truth-value saying whether a and b stand in the relation R. But consider an application where the elements a,b, etc. stand for components in a system. A Boolean-valued relation can answer the simple question as to whether or not a and b are connected in the system. But a richer question is: how are a and b connected? If you consider that a consists of parts a1,...,ak, and b consists of b1,...,bn, then the actual connection between a and b is a relation, of one lower degree, between these constituent parts. So we can have multi-level relations -- even potentially ones that can have an infinite number of levels.

    Then we are multiplying matrices whose elements are themselves matrices.

    One fly in the ointment: I don't think that determinant is defined if the rig is not a ring, because it needs the sign of the permutation.

    But nevermind -- a lot of the structure does generalize.

    Can you guys give me any pointers to where work in these directions is being carried out?

    What are some good categorical ways to look at:

    • Relativizing set and relation theory over a ground rig of truth values

    • Multi-level relational algebra, possibly with an infinite number of levels of increasing detail

11. • CommentRowNumber11.
    • CommentAuthorTobyBartels
    • CommentTimeFeb 13th 2013
    • PermaLink
    Author: TobyBartels
    Format: MarkdownItex>I don't think that determinant is defined if the rig is not a ring, because it needs the sign of the permutation. I believe that semiring theorists speak of separate positive and negative determinants in this case. Then instead of ${|A B|} = {|A|} {|B|}$, we have $$ {|A B|^+} + {|A|^+} {|B|^-} + {|A|^-} {|B|^+} = {|A B|^-} + {|A|^+} {|B|^+} + {|A|^-} {|B|^-} .$$ But in fact something stronger holds: $$ {|A B|^+} = {|A|^+} {|B|^+} + {|A|^-} {|B|^-},\qquad {|A B|^-} = {|A|^+} {|B|^-} + {|A|^-} {|B|^+} .$$ This all works nicely if you think of the determinant as taking values in the ring of formal differences of elements of the original rig.

    I don’t think that determinant is defined if the rig is not a ring, because it needs the sign of the permutation.

    I believe that semiring theorists speak of separate positive and negative determinants in this case. Then instead of ${|A B|} = {|A|} {|B|}$, we have

    $${|A B|^+} + {|A|^+} {|B|^-} + {|A|^-} {|B|^+} = {|A B|^-} + {|A|^+} {|B|^+} + {|A|^-} {|B|^-} .$$

    But in fact something stronger holds:

    $${|A B|^+} = {|A|^+} {|B|^+} + {|A|^-} {|B|^-},\qquad {|A B|^-} = {|A|^+} {|B|^-} + {|A|^-} {|B|^+} .$$

    This all works nicely if you think of the determinant as taking values in the ring of formal differences of elements of the original rig.

12. • CommentRowNumber12.
    • CommentAuthorTodd_Trimble
    • CommentTimeFeb 14th 2013
    • PermaLink
    Author: Todd_Trimble
    Format: MarkdownItex> (What are some good categorical ways to look at:) Relativizing set and relation theory over a ground rig of truth values Embarrassing riches here. There is for starters the theory of $H$-valued sets ($H$ a complete Heyting algebra) which has important connections with sheaf theory and forcing. Replacing $H$ with a [[quantale]] $Q$, one may consider $Q$-valued relations and functions; Lawvere's theory of metric spaces is an important example of that. The theory of buildings can also be developed in such a context. But one can generalize far beyond such cases; the theory of $V$-enriched profunctors is one such generalization. What is motivating your interest expressed in #1?

    (What are some good categorical ways to look at:) Relativizing set and relation theory over a ground rig of truth values

    Embarrassing riches here. There is for starters the theory of $H$-valued sets ($H$ a complete Heyting algebra) which has important connections with sheaf theory and forcing. Replacing $H$ with a quantale $Q$, one may consider $Q$-valued relations and functions; Lawvere’s theory of metric spaces is an important example of that. The theory of buildings can also be developed in such a context. But one can generalize far beyond such cases; the theory of $V$-enriched profunctors is one such generalization.

    What is motivating your interest expressed in #1?

13. • CommentRowNumber13.
    • CommentAuthorDavid Tanzer
    • CommentTimeFeb 16th 2013
    • PermaLink
    Author: David Tanzer
    Format: MarkdownTodd, thanks for all this good information. That should keep me busy for the next few years :) My queries have been motivated by problems in knowledge representation. How, for example, would we model _international relations_? A set of tuples just isn't up for the job. These real relations appear to have much more texture, perhaps even to an unlimited level of detail. This led me to think of relation-valued relations, and to wonder about what kind of "textures" would be achieved in a limiting case. Which lead me to think about multi-valued logics and categories for them. I'm really glad to have found this forum, and your very informative wiki. Working in isolation was okay for a time, but that time is over. By the way, I am getting some mileage out of this paper: David I. Spivak, [Simplicial Databases](http://math.mit.edu/~dspivak/informatics/SD.pdf). With Best Regards, Dave Tanzer

    Todd, thanks for all this good information. That should keep me busy for the next few years :)

    My queries have been motivated by problems in knowledge representation. How, for example, would we model international relations? A set of tuples just isn't up for the job. These real relations appear to have much more texture, perhaps even to an unlimited level of detail. This led me to think of relation-valued relations, and to wonder about what kind of "textures" would be achieved in a limiting case. Which lead me to think about multi-valued logics and categories for them.

    I'm really glad to have found this forum, and your very informative wiki. Working in isolation was okay for a time, but that time is over.

    By the way, I am getting some mileage out of this paper:

    David I. Spivak, Simplicial Databases.

    With Best Regards, Dave Tanzer

14. • CommentRowNumber14.
    • CommentAuthorTim_Porter
    • CommentTimeFeb 16th 2013
    • PermaLink
    Author: Tim_Porter
    Format: MarkdownItexDave, you should probably also look at ideas of building simplicial complexes from relations. Any relation between sets defines two simplicial complexes: see [[Dowker's theorem]] (in case this goes wrong as a link (see another thread) it is to Dowker's theorem). Also check up on work by Pascal Hitzler, and Guo-Qiang Zhang, for instance: A categorical view on algebraic lattices in formal concept analysis. Pascal Hitzler, Markus Krötzsch and Guo-Qiang Zhang Fundamenta Informaticae 74 (2-3), 301-328, 2006. Generally formal concept analysis has some interesting insights and methods, and may be worth your while exploring a bit.

    Dave, you should probably also look at ideas of building simplicial complexes from relations. Any relation between sets defines two simplicial complexes: see Dowker’s theorem (in case this goes wrong as a link (see another thread) it is to Dowker’s theorem). Also check up on work by Pascal Hitzler, and Guo-Qiang Zhang, for instance:

    A categorical view on algebraic lattices in formal concept analysis. Pascal Hitzler, Markus Krötzsch and Guo-Qiang Zhang Fundamenta Informaticae 74 (2-3), 301-328, 2006.

    Generally formal concept analysis has some interesting insights and methods, and may be worth your while exploring a bit.