Re: Relational lattice completeness

From: vc <boston103_at_hotmail.com>
Date: 9 Apr 2006 19:32:32 -0700
Message-ID: <1144636352.195425.47630@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 Sun Apr 09 2006 - 21:32:32 CDT