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.
Note that Mikito was asking about the case where you also had PA in your
logic, so the structure also includes the constant 0 and the succesor
function.
Received on Sat May 21 2005 - 03:01:18 CDT
