Re: deductive databases

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. Received on Thu May 26 2005 - 02:41:09 CEST