Thread: Transitive Graph Closure - FOL - Interpretation and Counterexample

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

What are the edges in your directed graph?

Originally Posted by suzanne

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

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.

My question:

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

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.

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

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.

There is only one edge (b,b), so G is {b,b}.

Originally Posted by emakarov

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.

.

Thanks for the reply.

I am not clear about something you had mentioned. What is the difference between a formula (with logical equivalence ) and a definition?

Another thing is that, suppose this is a formula. How is the interpretation a model of this formula??

Originally Posted by suzanne

What is the difference between a formula (with logical equivalence ) and a definition?

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.

How is the interpretation a model of this formula??

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.