Re: deductive databases
From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Thu, 26 May 2005 19:55:19 GMT
Message-ID: <HQple.102181$h25.6097958_at_phobos.telenet-ops.be>
>
> Given a set S of sentences using p and q, consider the set S'
> obtained by adding to S (using new constants a and b) the sentences
> q(a,b), ~p(a,b), ~Ex(p(a,x)&p(x,b)), ~ExEy(p(a,x)&p(x,y)&p(y,b)), and
> so on. Assuming that for every interpretation <D,P,Q> satisfying S, Q
> is included in the transitive closure of P, it follows that S' has no
> model. But then some finite subset of S' has no model, so there are
> interpretations <D,P,Q> where Q is the transitive closure of P even
> though <D,P,Q> does not satisfy S.
Date: Thu, 26 May 2005 19:55:19 GMT
Message-ID: <HQple.102181$h25.6097958_at_phobos.telenet-ops.be>
Torkel Franzen wrote:
> Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be> writes:
>
>>What I still not understand is how compactness shows in this case (or >>even in the normal case) proves that you cannot express the transitive >>closure.
>
> Given a set S of sentences using p and q, consider the set S'
> obtained by adding to S (using new constants a and b) the sentences
> q(a,b), ~p(a,b), ~Ex(p(a,x)&p(x,b)), ~ExEy(p(a,x)&p(x,y)&p(y,b)), and
> so on. Assuming that for every interpretation <D,P,Q> satisfying S, Q
> is included in the transitive closure of P, it follows that S' has no
> model. But then some finite subset of S' has no model, so there are
> interpretations <D,P,Q> where Q is the transitive closure of P even
> though <D,P,Q> does not satisfy S.
Nice! I'll continue the thread in VC's reply, but thank you very much for this proof and sticking with me.
- Jan Hidders