How to describe Deterministic Transitive Closure in FOL?

Question

In "Finite Model Theory and Its Applications", page 152, it is said that Deterministic Transitive Closure, on ordered finite structures, captures LOGSPACE.

Hence, taking into account that FOL captures LOGSPACE, the following should be possible:

• Given a functional relation R(X,Y) (e.g. "motherOf(X,Y)")
• Define, in FOL, a predicate T(X,Y) that captures its transitive closure (e.g. "femaleAncestor(X, Y)").

I would like to know how to define such predicate. This would be quite easy in Datalog, using recursion, but it should be possible to define it without recursion, which is the question that puzzles me.

Answer 1

Hence, taking into account that FOL captures LOGSPACE, it should be possible to:

• Given a functional relation R(X,Y) (e.g. "motherOf(X,Y)")
• It should be possible to define, in FOL, a predicate T(X,Y) that captures its transitive closure (e.g. "femaleAncestor(X, Y)")

Actually this is not correct: first-order logic does not capture logspace. As you said earlier in your question, FOL plus deterministic transitive closure captures logspace, that is $$ \text{FO(DTC)} = \text{L} $$ but $$ \text{FO} \ne \text{FO(DTC)}, $$

i.e. deterministic transitive closure is not definable in first-order logic.

More generally, FOL is quite limited. FOL captures a class called uniform $\text{AC0}$ (see the complexity zoo and Immerman's diagram); it is the class of queries computable in "constant parallel time". And transitive closure, even deterministic transitive closure, cannot be done in $\text{AC0}$ (with a circuit of constant depth). Even something very simple, calculating the parity of the number of input bits, can't be done in $\text{AC0}$.

How to describe Deterministic Transitive Closure in FOL?

To reiterate: it is impossible.