Re: Relation subset operators --> negation

On Jun 6, 2:19 pm, vadim..._at_gmail.com wrote:
> The dual version of this operation also makes sence. Let's call it
> "inversion" and use the back quote "`" symbol in postfix notation to
> write down the defining axioms:
>
> x` ^ x = x ^ R11.
> x` v x = x v R00.
>
...
>
> Informally, inversion complements relation header, and it could be
> demonstrated that the best it can do about the relation content is
> producing either the cartesian product of the full domains, or the
> empty relation. Not surprisingly, it is weaker than complement. Double
> inversion doesn't hold, only
>
> x```=x`.
>
> The other interesting theorems:
>
> x` v y` = (x + y)`.
> x` + y` = (x v y)`.
> x'`v y'`= (x ^ y )'`.
>
> Complement and inversion can be viewed as "halves" of genuine boolean
> negation operator, because in relational lattice it is impossible to
> have a genuine negation.

To clarify this a little more, the fundamental decomposition identity

x = (x ^ R00) v (x ^ R11).

generalizes to

x = (x ^ y') v (x ^ y`).

which the double complement law y = y'' makes it equivalent to

x = (x ^ y) v (x ^ y`').

Compare it to boolean algebra identity

x = (x ^ y) v (x ^ (-y)).

To repeat, one can't have a genuine negation -x in relational, lattice. The composition of inversion and complement gets us as close as it can. In order to have genuine negation one would have to complement not only relation's content, but relation header as well, and it is impossible to do it satisfactory. Received on Sun Jun 07 2009 - 00:36:03 CEST