Finite Model Theory/FO Localities

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Basic idea: bringing neighbourhoods in relational structures together with queries written in certain languages. Like an area of land and a watchtower with a visual range, a neighbourhood has a sort of sprawl that it covers, and queries may have a sort of operating distance over which they can relate elements.

Such queries are said to have the locality property. This concept now can be expanded to whole languages. For example, for FO it can be shown that all FO-queries have the locality property.

Neighbourhood[edit]

universe with 1 relation: distance-1-neighbour

expand a: distance-2-neighbour

expand b: 2 relations with d-1-neighb

expand a+b: ...

Gaifman graph[edit]

Gaifman graph example
Gaifman graph of a structure with relations Blue and Green

We define a Gaifman graph as a sort of overlay of all relations of a structure S, and then make use of it for measuring a distance between elements of S, i.o.w. how far it is to walk from one element to the other, on a path paved by the relations of S.

Definition Gaifman Graph[edit]

Let S be a relational structure with a universe U and relations Ri. A graph G (N, E) is said to be the Gaifman Graph of S iff N = U, for all e exists a r in some Ri or e = (u, u).

Remarks[edit]
  1. G is reflexiv
  2. the orientation of the edges in Ri doesn't matter in G
Examples[edit]
  1. If S is a graph, G is basically the same plus reflexivity
  2. If S is a digraph, G is basically the same plus reflexivity, plus symmetry (i.e. edges lose orientation)
  3. If S has only the relations R1 and R2, G is their union plus reflexivity, plus symmetry
  4. In the example image a Gaifman graph (a) is derived from the 2 relations (digraphs) Blue (b) and Green (c) by 'overlaying' the edges, 'forgetting' orientation and adding loops.
Definition Distance between elements[edit]
Graph
Disatnces in Graphs btw elements and sets.

Let S be a structure with universe U with elements u1, u2 and Gaifman graph G. The length of a shortest path between u1 and u2 in G with ... is said to be the distance of u1 and u2 (in S).

Definition Distance between sets[edit]

Let S be a structure with universe U with subsets U1, U2 and Gaifman graph G. Then the minimal distance btw elms of U1 and U2 is said to be the distance btw U1 and U2 (in S).

Remarks[edit]
  1. Example elms: shorter path, infinite, zero
  2. Example sets: path, zero?

Neighbourhood[edit]

Graph
Graph with 1-neighbourhood with Relations Blue and Green

First, a ball is defined as a subset of elements of a structure S. Next, a neighbourhood is defined as a partial structure of S, based on a ball.

Definition Ball[edit]

Let S be a relational structures with a universe U, a be a sequence, r a natural. A set of elements of U is said to be a ball of radius r around a, B(S, r; a), iff

B(S, r; a) = { u | d(a, u) le r }

Definition Neighbourhood[edit]

Let B(S, r; a) be a Ball around a. Then a structure N(Sn, r; a) is said to be the r-neighbourhood of a in Sn, with Sn having

  1. the universe B(S, r; a)
  2. each relation from S, restricted to B
  3. the elements of a as additional constants a1, ..., a_n
Remarks[edit]
  1. examples of 'locally look the same'
  2. Isomorphism: ai -> bi - overlap?
  3. => equi classes decompose with increasing radius - no swap of class?

Gaifman Locality[edit]

Neighbourhoods & Queries[edit]

Graph Example
Graph G

1-Neighbourhood: {1, 6,7}, {2, 3,5},{4}, {8, 9}

2-Neighbourhood: {1, 6}, {7}, {2}, {3}, {5}, {4}, {8, 9}

Definition[edit]

Hanf Locality[edit]

Bijection among Structures[edit]

Definition[edit]

Special Case: Gaifman[edit]