What are the edges in your directed graph?
Hi
The following is a representation of transitive graph closure in FOL (which is not correct)
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
If I understand correctly, is a biconditional. Note that this is not a definition of a predicate T; this is a formula that contains T.
Or if we had G(a,b), then the formula above would be true for x = a and y = b, since we also have T(b,b). As it is, the formula is false for these values of x and y. And, again, strictly speaking, the formula is not a definition of T.My question:
What about T(a,b)? according to the above definition, we should have [G(?,a) and T(a,b)], right?
Well, it is a known fact that it is not possible to write a FOL formula that represents the transitive closure, and in this interpretation T is not the transitive closure of G.How is this interpretaion a model for the FOL definition of transtive graph closure?
A definition must have the defined object in the left-hand side only. For example,
is a formula that can be considered a definition of T (informally, it represents ). The formula in the OP contains T both in the left- and right-hand sides, so it is a constraint on T, not a definition of T. It is true that if that formula is true in some interpretation, then T is the transitive closure of G in that interpretation, but to interpret the formula, T must be given in advance.
This is quite similar to equations on numbers. An equation x = E where E in an expression consisting of numbers and (everywhere defined) operations is always a definition of x. However, an equation can serve as a definition, but it may also have multiple solutions for x or none at all.
There are extensions of FOL, called inductive logics or calculi, where certain biconditionals having a new predicate in both sides are considered definitions of this predicate, but one has to define how exactly such definitions are used, what their semantics is, etc.
Which interpretation? As I said, the original formula is false for x = a, y = b in the interpretation where G is {(b,b)} and T is {(a,b),(b,b)}. In general, biconditional is interpreted as a conjunction of two implications.How is the interpretation a model of this formula??