Knowledge in Action (Reiter) - example 2.1.1

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. Any help greatly appreciated.

I'd like to make sure I understand this point fully before I move on, as it seems crucial to Reiter's argument for second-order logic.

-- Neil
.

Relevant Pages

  • Re: Knowledge in Action (Reiter) - example 2.1.1
    ... closure of a graph, G, and says that the following "naive" definition is ... single directed edge G. ... 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)