Re: More on lists and sets

Mikito Harakiri wrote:
> Jan Hidders wrote:
> > Mikito Harakiri wrote:
> > > Jan Hidders wrote:
> > > >
> > > > Understood, but let's start first with a simpeler question. Is the
> > > > axiomatization complete if we only consider /\ and \/? (So no 00, 01,
> > > > 10 and 11.)
> > >
> > > Then I don't understand your question. If we remove constant symbols
> > > (00 and 11 being the most important ones), then what is left are the
> > > lattice axioms. Lattices however are more general than relation
> > > algebras.
> >
> > Indeed, but the lattice axioms might still be complete. There are
> > several ways in which such a set of axioms can be complete, so let me
> > attempt to explain my question more clearly.
> >
> > We are considering expressions that are made up of relation variables
> > and the /\ and \/ operators, e.g., R \/ S and (T /\ R) \/ S. Such
> > expressions define a query over a database D where D may be defined
> > here as a function that maps the mentioned relation variables to a
> > relation. Let e(D) be the result of applying e to D then we can call
> > two expressions e1 and e2 query-equivalent if for every database DB it
> > holds that e1(DB) = e2(DB).
> >
> > Next to the query-equivalence we can also define lattice-equivalence:
> > two expressions e1 and e2 are called lattice-equivalent if e1 can be
> > rewritten to e2 using the lattice axioms.
> >
> > So my question is if lattice-equivalence and query-equivalence
> > coincide. It clearly holds that lattice-equivalence implies
> > query-equivalence, but whether query-equivalence implies
> > lattice-equivalence (or not) is unclear to me. And as far as I can tell
> > the N_5 lattice doesn't really provide a counterexample, but I might be
> > missing something here.
> >
> > Anyway, is my question clear now? Or why such a type of completeness is
> > important in the context of database theory?

>

I'm asking the question for a specific model, not in general as you did. For example, boolean algebra for boolean value *is* complete.

> You are welcome to
> steer discussion there, as I'm not really skillful in model theory.

Yet it is your model. :-) Pity. Such a result would lift your work on this from "cute" to "really interesting".

• Jan Hidders