Finite Model Theory/FO Localities

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 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 reflexive
  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
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 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 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