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_at_phobos.telenet-ops.be>
>
> 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.
Date: Sat, 21 May 2005 18:17:47 GMT
Message-ID: <fXKje.97604$rd1.5444651_at_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.
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