Re: deductive databases

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Sat, 21 May 2005 18:17:47 GMT
Message-ID: <fXKje.97604$rd1.5444651@phobos.telenet-ops.be>

Torkel Franzen wrote:
> Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be> writes:

>> 
>>By now I think you have enough information to know what the exact 
>>problem is. So for the sake of clarity: the structure consists of D, R, 
>>S, 0 and succ, and nothing else.

>
> Well, it's still not the case that there is any set M of sentences
> in the corresponding first-order language such that for every
> countable structure I of the kind indicated, I satisfies the sentences
> in M if and only if R is the transitive closure of S.

You meant *finite* M, right?

My reasoning was something like the following. A path will consist of a sequence of pairs of numbers and can therefore be encoded in a single number p such that there is a formula F(x,y,p) that is true iff the pair (x,y) is in the path p. If you also have formulas B(x,p) and E(x,p) that are true iff x is the begin (respectively, end) node of p then you can build a formula that says that for each pair u and v such that R(u,v) there is a number p such that B(u,p) and E(v,p) and for each pair (x,y) such that F(x,y,p) it holds that R(x,y).

Jan Hidders

Received on Sat May 21 2005 - 13:17:47 CDT