# Re: More on lists and sets

From: Mikito Harakiri <mikharakiri_nospaum_at_yahoo.com>

Date: 28 Mar 2006 10:42:20 -0800

Message-ID: <1143571340.303966.286980_at_j33g2000cwa.googlegroups.com>

Date: 28 Mar 2006 10:42:20 -0800

Message-ID: <1143571340.303966.286980_at_j33g2000cwa.googlegroups.com>

Jan Hidders wrote:

*> Mikito Harakiri wrote:
**> > Less chatty version:
**> > http://arxiv.org/ftp/cs/papers/0603/0603044.pdf
**>
*

> Mikito, do you know if Vadim's axiomatization is complete? I mean, are

*> two queries equivalent iff the algebraic identities allow me to rewrite
**> one to the other? Or might there still be algebraic identities missing?
*

Axiomatization of relational algebra -- that was the question you asked on c.d.t back in 2001?

Relational lattice theory is not complete. Many parts still remain informal -- Spight distributivity criteria among them. It could be written formally, but this expression

doesn't look like a satisfying axiom.

If we just write all what is known so far there would be too many axioms.

- 8 Lattice axioms. This set can be reduced -- see any standard source on lattice theory (even wikipedia would do).
- Decomposition: A = (00 /\ A) \/ (11 \/ A)
- Homomorphisms into boolean algebras: X -> X /\ 00 X -> X \/ 00 X -> X /\ 11 X -> X \/ 11 This informal condition can be rewritten into a set of formal axioms, e.g. restrictive cases of distributivity A/\11 /\ ( (B/\11) \/ (C/\11) ) == (A /\ B /\ 11) \/ (A /\ C /\ 11)
- More restrictive cases of distributivty, that doesn't seem to follow from the above 00 /\ (A \/ B) = (00 /\ A) \/ (00 /\ B) 11 \/ (A /\ B) = (11 \/ A) /\ (11 \/ B)