Transitive Graph Closure - FOL - Interpretation and Counterexample

• Aug 8th 2011, 05:30 PM
suzanne
Transitive Graph Closure - FOL - Interpretation and Counterexample
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?

Suzanne
• Aug 9th 2011, 02:15 AM
Traveller
Re: Transitive Graph Closure - FOL - Interpretation and Counterexample
What are the edges in your directed graph?
• Aug 9th 2011, 09:25 AM
emakarov
Re: Transitive Graph Closure - FOL - Interpretation and Counterexample
Quote:

Originally Posted by suzanne
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)$

If I understand correctly, $\displaystyle \equiv$ is a biconditional. Note that this is not a definition of a predicate T; this is a formula that contains T.

Quote:

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.

Quote:

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.
• Aug 10th 2011, 06:35 PM
suzanne
Re: Transitive Graph Closure - FOL - Interpretation and Counterexample
There is only one edge (b,b), so G is {b,b}.
• Aug 10th 2011, 06:52 PM
suzanne
Re: Transitive Graph Closure - FOL - Interpretation and Counterexample
Quote:

Originally Posted by emakarov
If I understand correctly, $\displaystyle \equiv$ 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.

.

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??
• Aug 12th 2011, 01:02 AM
emakarov
Re: Transitive Graph Closure - FOL - Interpretation and Counterexample
Quote:

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,

$\displaystyle \forall x\,(T(x,y)\leftrightarrow G(x,y)\lor\exists z\,(G(x,z)\land G(z,y)))$

is a formula that can be considered a definition of T (informally, it represents $\displaystyle G\cup G^2$). 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 $\displaystyle E_1(x) = E_2(x)$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.

Quote:

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.