Results 1 to 6 of 6

Math Help - Transitive Graph Closure - FOL - Interpretation and Counterexample

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    9

    Transitive Graph Closure - FOL - Interpretation and Counterexample

    Hi

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

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162

    Re: Transitive Graph Closure - FOL - Interpretation and Counterexample

    What are the edges in your directed graph?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Transitive Graph Closure - FOL - Interpretation and Counterexample

    Quote Originally Posted by suzanne View Post
    The following is a representation of transitive graph closure in FOL (which is not correct)

    T(x,y) \equiv G(x,y) \or (\exists z).G(x,z) \and T(z,y)
    If I understand correctly, \equiv 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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2011
    Posts
    9

    Re: Transitive Graph Closure - FOL - Interpretation and Counterexample

    There is only one edge (b,b), so G is {b,b}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2011
    Posts
    9

    Re: Transitive Graph Closure - FOL - Interpretation and Counterexample

    Quote Originally Posted by emakarov View Post
    If I understand correctly, \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.

    .
    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??
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Transitive Graph Closure - FOL - Interpretation and Counterexample

    Quote Originally Posted by suzanne View Post
    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,

    \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 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 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.

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof concerning a transitive closure
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2011, 12:26 PM
  2. Transitive Closure
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 27th 2010, 06:33 AM
  3. transitive closure, cardinality
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 24th 2010, 04:13 PM
  4. Transitive Closure in FOL and Prolog
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 22nd 2009, 02:06 AM
  5. Transitive closure
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 14th 2008, 11:06 PM

Search Tags


/mathhelpforum @mathhelpforum