Re: Knowledge in Action (Reiter) - example 2.1.1

Neil Madden says...

I have just started reading Raymond Reiter's "Knowledge in Action:
Logical Foundations for Specifying and Implementing Dynamical Systems",
and am finding it hard to understand an early example. The author is
explaining why first-order logic is insufficient to define transitive
closure of a graph, G, and says that the following "naive" definition is
incorrect:

T(x, y) <=> G(x, y) \/ (Ez).(G(x, z) /\ T(z, y)).

(Hopefully that is readable: E is existential quantification here).

The author then describes a counter-example (example 2.1.1):

"Consider the directed graph with two vertices a and b, and with a
single directed edge G(b, b). Consider a structure with universe {a, b}
that interprets G as {(b, b)} and T as {(a, b), (b, b)}. In other
words, the structure represents the graph G (by declaring that there is
an edge from b to b, and no other edges), and it assigns true to T(a, b)
and T(b, b). It is easy to check that this structure is a model of the
above naive definition for transitive closure. ..."

I must be missing something in the semantics, because I don't see how a
model of T given the above definition can allow T(a, b) to be true, as
there is no edge in G that involves a at all. Any help greatly appreciated.

I think you're right. I believe that it is typo. What the author
probably meant was T = {(b,a), (b,b)}. For this graph, the definition
of T(x,y) tells us that

T(b,a) = G(b,a) \/ Ez (G(b,z) /\ T(z,a))

which for the case of two nodes a and b becomes

T(b,a) = G(b,a) \/ (G(b,b) /\ T(b,a)) \/ (G(b,a) /\ T(a,a))

Since G(b,a) is false and G(b,b) is true, this reduces to

T(b,a) = false \/ (true /\ T(b,a)) \/ (false /\ T(a,a))
= T(b,a)

So the definition gives no information about T(b,a). It could
be true, or it could be false. Either way is consistent.

--
Daryl McCullough
Ithaca, NY

.

Relevant Pages

  • Knowledge in Action (Reiter) - example 2.1.1
    ... "Consider the directed graph with two vertices a and b, and with a single directed edge G. ... It is easy to check that this structure is a model of the above naive definition for transitive closure. ...
    (sci.logic)
  • Re: Can this be done in SQL? Find the transitive relation
    ... I am strugling get the following done in SQL. ... http://www.bookpool.com/sm/0977671542, section on transitive closure ... There are several key graph concepts that would guide your intuition ... Figure 6.5: Reachability as an equivalence relation: graph from fig. ...
    (comp.databases.oracle.server)
  • Re: Help needed: Is Quick-Union-Find the right solution to this problem ?
    ... That's a solved problem (checking for cycles in a directed graph using ... > What you want is a "transitive closure" of the graph. ... I did a bit of research and studied two approaches to Warshall ... which is pretty easy to accomplish or I might have an array of strings ...
    (comp.programming)
  • Re: Knowledge in Action (Reiter) - example 2.1.1
    ... Logical Foundations for Specifying and Implementing Dynamical ... transitive closure of a graph, G, and says that the following "naive" ... model of the above naive definition for transitive closure. ...
    (sci.logic)
  • Re: Transitive Order of a Relation
    ... The transitive closure of R is well defined and is ... A of a graph G of a relation R is squared, new paths of length two may ... we may normalize any power of an adjacency matrix ... The transitive order of a transitive relation is 1. ...
    (sci.math)