Differences

This shows you the differences between two versions of the page.

--- sav08:graphs_as_interpretations [2008/03/19 16:16]
vkuncak
+++ sav08:graphs_as_interpretations [2008/03/25 16:07]
vkuncak
@@ Line 1: / Line 1: @@
 ====== Graphs as Interpretations ======
-Directed graph is is given by a set of vertices $V$ and a set of edges $E \subseteq V \times V$.  Graph is therefore specified by an [[First-Order Logic Semantics|interpretation]] $I = (V,\alpha)$ in languge ${\cal L} = \{edge\}$ with $\alpha(edge) = E$.
+Directed graph is given by a set of vertices $V$ and a set of edges $E \subseteq V \times V$.  Graph is therefore specified by an [[First-Order Logic Semantics|interpretation]] $I = (V,\alpha)$ in languge ${\cal L} = \{edge\}$ with $\alpha(edge) = E$.
 Example: $D = \{1,2,3,4\}$, $\alpha(edge) = \{ (1,2), (2,3), (1,3), (3,4) \}$.
@@ Line 19: / Line 19: @@
 **Tournament:**
 \[
-   \forall x, y.\ (edge(x,y) \lor edge(y,x)) \land \lnot (edge(x,y) \land edge(y,x))
+   (\forall x, y.\ x \neq y \rightarrow (edge(x,y) \lor edge(y,x)) \land \lnot (edge(x,y) \land edge(y,x))) \land (\forall x. \lnot edge(x,x))
 \]
-Note: there is no formula $F$ in this language ${\cal L} = \{edge\}$ that characterizes property "graph has no cycles".  All properties expressed in first-order logic on graphs are "local".
+Note: there is no formula $F$ in this language ${\cal L} = \{edge\}$ that characterizes property "graph has no cycles".  All properties expressed in first-order logic on graphs are "local". Intuitively, formula with $k$ universal quantifiers says that if we pick any set of $k$ vertices in the graph, then they (and their close neighbors) can induce only one of the finitely many specified subgraphs.
-Many more properties become expressible if we take as domain $D$ the set of all subsets of $V$ and allow set operations in our language.
   * [[http://citeseer.ist.psu.edu/benedikt95relational.html|Relational Expressive Power of Constraint Query Language]]
   * [[http://citeseer.ist.psu.edu/context/64580/0|H. Gaifman, On local and non-local properties, in Logic Colloquium '81, North Holland, 1982]]
+Many more properties become expressible if we take as domain $D$ the set of all subsets of $V$ and allow set operations in our language.