Hi

The following is a representation of transitive graph closure in FOL (which is not correct)

$\displaystyle T(x,y) \equiv G(x,y) \or (\exists z).G(x,z) \and T(z,y)$

G(x,y) means x and y are connected by an edge in the graph.

T(x,y) is the transitive closure

Counterexample: consider a directed graph with two vertices a, b. An interpretation assigns {(b,b)} to G and {(a,b),(b,b)} to T.

T(x,y) is true if G(x,y) : since we have G(b,b) so T(b,b) is true. Ok

My question:

What about T(a,b)? according to the above definition, we should have [G(?,a) and T(a,b)], right? But we only have G(b,b).

How is this interpretaion a model for the FOL definition of transtive graph closure?

Thank you in advance.

Suzanne