Re: Relational symmetric difference is well defined

On May 31, 9:28 am, Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote:
> 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.

Excellent. I'm right away attracted to the idea of join, union, and set equality join.

> > 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.

Wonderful! That made me smile. It also makes it clear that parallels with fields are probably not going to be fruitful: absorbtion
is a requirement for set semantics, so there can't be inverse elements for join in an algebra of relations.

Is set equality join the inverse of join? If not, what is an inverse of join? (What are the choices? :-)

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

See other thread.

Marshall Received on Fri Jun 01 2007 - 00:55:15 CEST