Re: Knowledge in Action (Reiter) - example 2.1.1

On Sun, 11 Mar 2007 17:40:38 GMT, Neil Madden <nem@xxxxxxxxxxxxx> said:
Hi all,

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.

T(a,b) is simply true by stipulation in the new structure. The problem
is that the new structure satisfies the naive definition. The naive
definition is supposed to pick out, for any graph <V,E>, its (unique)
transitive closure. What Reiter's example shows is that the naive
definition lets in too much. In particular, the TC of the directed
graph <{a,b},{<b,b>}> is just itself. However, the graph
<{a,b},{<a,b>,<b,b>}> also satisfies the naive definition. (I do find
his argument for this above a little unclear -- he uses "G" both as a
name for a graph and as a binary predicate.) Hence, the naive
definition has "unintended" models, which Reiter goes on to argue can
only be ruled out in second-order logic.

.

Relevant Pages

  • 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)
  • 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: 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)
  • Plot a dotted graph using 3 vectors.
    ... I want to plot a 2D graph where I could input 3 vectors each specifying one of the coordinates. ... The first two vectors would be the x/y position of the data point and the third vactor would specify the color or size of the point. ...
    (comp.soft-sys.matlab)