Finite Model Theory/FO Localities

3 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 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 alt=Gaifman graph example|thumb|320x320px|Gaifman graph of a structure with relations Blue and GreenWe 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 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 G is reflexive the orientation of the edges in Ri doesn't matter in G Examples If S is a graph, G is basically the same plus reflexivity If S is a digraph, G is basically the same plus reflexivity, plus symmetry (i.e. edges lose orientation) If S has only the relations R1 and R2, G is their union plus reflexivity, plus symmetry 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 alt=Graph|thumb|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 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 Example elms: shorter path, infinite, zero Example sets: path, zero? Neighbourhood alt=Graph|thumb|320x320px|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 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 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 the universe B(S, r; a) each relation from S, restricted to B the elements of a as additional constants a1, ..., a_n Remarks examples of 'locally look the same' Isomorphism: ai -> bi - overlap? => equi classes decompose with increasing radius - no swap of class? Gaifman Locality Neighbourhoods & Queries alt=Graph Example|thumb|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 Hanf Locality Bijection among Structures Definition Special Case: Gaifman