Re: deductive databases

Jan Hidders wrote:
> mikharakiri_nospaum_at_yahoo.com wrote:
> > Chris Menzel wrote:
> >>On 18 May 2005 12:23:53 -0700, Mikito Harakiri
<mikharakiri_nospaum_at_yahoo.com> said:
> >>>Chris Menzel wrote:
> >>>
> >>>>I'm confused by the talk of computation here, but, in the model
> >>>>theoretic sense of "expressive power", the TC of a graph is not
> >>>>expressible in first-order logic with or without function
symbols.
> >>>
> >>>TC is surely expressible in arithmetics (or less slopily Peano
> >>>Arithmetics), right?
> >>
> >>Second-order PA, yes (presumably in conjunction with some basic
graph
> >>theoretic apparatus), first-order, no.
> >
> > Is there a list of problems that are solvable in first order PA?
Can I
> > solve [systems of] linear equations, for example?
>
> No. You can *express* them, but you cannot *solve* them in the sense
> that can "solve" first order queries on a given database by executing

> them as SQL (I assume that is how you meant it). In this logic you
can
> actually formulate undecidable queries.

Perhaps, you already guessed that my question was somewhat related to "Solving equations in the realitional algebra" that you have already discussed here at c.d.t some time ago.

To clarify my original question.

Can we prove

x+5 = 6 ==> x=1

in the first order PA? If we can, and if we can to extend this proof to arbitrary system of linear equations, then I fail to see why transitive closure can't be expressed in the first order PA.

To convert TC problem into a problem in terms of linear algebra use a standard adjacency matrix for a graph. Transitive closure of matrix A is just

I+A+A^2+...=(I-A)^(-1) Received on Thu May 19 2005 - 03:39:19 CEST