Re: deductive databases
From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Sat, 21 May 2005 08:01:18 GMT
Message-ID: <iVBje.97015$8E4.5565485_at_phobos.telenet-ops.be>
>
> 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.
Date: Sat, 21 May 2005 08:01:18 GMT
Message-ID: <iVBje.97015$8E4.5565485_at_phobos.telenet-ops.be>
Torkel Franzen wrote:
> 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.
- Jan Hidders