Re: Relational symmetric difference is well defined

On May 30, 8:52 pm, Marshall <marshall.spi..._at_gmail.com> wrote:
> Can you clarify the difference between set containment join and set
> equality join? The inverse of join is much on my mind these days.

Set equality join

A(x,y)/=B(y,z) is {(x,z)| {y|A(x,y)}={y|A(y,z)} }

Set containment join

A(x,y)/=B(y,z) is {(x,z)| {y|A(x,y)}>{y|A(y,z)} }

where the ">" is "subset of".

> I suspect it might be possible to eliminate the inverse of union as
> a primitive. As I mentioned, I also suspect that it might be possible
> to eliminate relational equality as a primitive. (Although not scalar
> equality.) We can build the lattice order on top of equality, and
> logical implication is just the lattice order. So we could perhaps get
> down to just join, union, and division, and *nothing else.* Seems
> desirable if we want to pursue axiomatization down the line.

Yes, antijoin can be written via join, union, and division. Similarly, division can be represented as a combination of join, union, and antijoin.

> Inverses are tricky. At least we would like A op B op-1 B = A.
> Boolean algebra is more concerned with complements, but
> abstract algebra is more concerned with additive/multiplicative
> inverse elements. The RL seems about halfway between the two.

You can't have additive inverses in idempotent semiring. Likewise, you can't have join and meet inverses in the lattice. Here is a 2 line proof:

A /\ 01 = A, therefore 01 is neutral element for join. If there exists [-A] that is join inverse of A, then

01 = A /\ [-A] = A /\ A /\ [-A] = A /\ 01 = A

which asserts that the lattice reduces to trivial one element lattice.

I'm puzzled by boolean algebra complement operation which acts as surrogate inverse for both conjunction and disjunction.

> I've wondered if it might be possible to give it a kick and get
> it somewhere more traditional. Better distributivity would
> make a boolean algebra. OTOH, the two lattice operations
> each form a commutative monoid over relations. (R, /\)
> is a comm. monoid and (R, \/) is a comm. monoid.

Well, D&D algebra has 2 commutative monoids as well. In relational lattcice case thes monoids are "glued together" with absorption property. In D&D case they are glued together with distributivity.

<Have to read about Grothendieck groups in order to comment the rest> Received on Fri Jun 01 2007 - 05:11:48 CEST