Abstract

Spatio-temporal logic is a variant of branching temporal logic where one of the so-called causal relations on spacetime plays the role of a time flow. Allowing only rational numbers as space and time co-ordinates, we prove that a first-order spatio-temporal theory over this flow is recursively enumerable if and only if the dimension of spacetime does not exceed 2. The situation is somewhat different compared to the case of real co-ordinates, because we establish that even dimension 2 does not permit recursive enumerability in this case. The proof of the result on rational spacetime involves a more deeper portion of spacetime geometry than the corresponding, more evident result for the real co-ordinates