Home -> Usenet -> comp.databases.theory -> Re: Relational lattice completeness

Re: Relational lattice completeness

From: vc <boston103_at_hotmail.com>
Date: 9 Apr 2006 19:32:32 -0700
Message-ID: <1144636352.195425.47630_at_v46g2000cwv.googlegroups.com> 






Jan Hidders wrote:


> vc wrote:

> > Jan Hidders wrote:

> > > vc wrote:

> > > >


> > > > What's confusing,  to me at least,  is that in another thread you said

> > > > that the question was about complete theories,  that is about

> > > > completeness in the context of the first incompleteness theorem.

> > >

> > > It is. Because we talking about a system where we have a semantical

> > > notion of truth for algebraic identities and a syntactical one

> > > (derivation from the set of given algebraic identies by applying them

> > > to each other) and the question is if these two are the same.

> >

> > They would be the same for a complete (in the sense of the first

> > incompletenes theorem) system  so finding out whether this is the case

> > would amount to showing if the system in question is complete or not.

>




> Not necessarily because the syntactical notion of truth is not the


> usual one. It's related but not the same.




I let it slip the first time because I thought you'd used the
expression metaphorically,  but now I am curious as to what exactly you

meant.  The 1st incompleteness theorem talks about provability, not
truth. The notion of truth is not used in either the formulation or
proof.





Let's assume that by 'syntactical notion of truth; you've meant in fact
derivation.  If so, what did you mean by " because the syntactical
notion of truth is not the usual one. It's related but not the same" ?


>


> > However,  I am not sure why that may be practically important.




> > Arithmetic incompleteness does not prevent anyone from balancing one's

> > checkbook.

>




> Having a full and simple axiomatization makes it possible to write


> query optimizers that do a more thorough search of the "optimization

> space", and if you know you are complete then you are sure that you

> need not look further for any other rules.




If you have a bunch of axioms/derivation rules,  you can transform an
expression to your heart content regardless of whether the theory is
complete or not.  It's highly unlikely that you will all of a sudden
come up with a formula which turns out to be unprovable in your
hypothetical incomplete theory -- such formula is underivable from the
theory axioms (unless the formula somehow magically appears in your
mind).  So I am puzzled by your thinking that a theory completeness in
the sense of the 1st incompletness theorem may have any practical
implications for the query language.



> 

> -- Jan Hidders


Received on Mon Apr 10 2006 - 04:32:32 CEST












Original text of this message