Re: deductive databases

Mikito Harakiri wrote:
>
> 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.

Let's say I felt it bubbling below the surface, but wasn't really sure. :-)

> 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)

I haven't really thought this through yet but I suspect that if your domain consists only of numbers, then, yes, you can probably express transitive closure. It is, after all, Turing complete. But if your domain is not the same as the domain of the arithmetic then that becomes a whole different story. Note that in your last line you are mixing relations and numbers in your arithmatic, and FOL with PA cannot do that.

But why do you want to know if a problem which we know how to effectively compute can be expressed in a formalism with wich no effective computational procedure can be associated?

• Jan Hidders