Re: deductive databases

From: Torkel Franzen <torkel_at_sm.luth.se>
Date: 21 May 2005 01:53:37 +0200
Message-ID: <vcbk6lto3ni.fsf@beta19.sm.ltu.se>

Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be> writes:

> The structure also contains a domain over which R and S are relations.
> This condition means we only consider structures where this domain is
> restricted to the natural numbers.

This restriction is equivalent to requiring the domain to be countable. We can then observe that there is no first order formula involving two two-place predicates p(x,y) and q(x,y) which is true in a countable structure <D,R,S> if and only if S is the transitive closure of R. Received on Fri May 20 2005 - 18:53:37 CDT