World's most popular travel blog for travel bloggers.

# [Answers] First Order interpretation of arbitrary structures as a graph

, ,
Problem Detail:

I am currently trying to get some intuition on the concept of First Order reductions, and have come across this exercise question by Immerman, dubbed "Everything is a Graph".

Given some arbitrary relational structure $S$ of some vocabulary $\sigma$, show that there are first-order queries $I$ and $I^{-1}$, such that $G:=I(S)$ is a directed graph, and $I^{-1}(G)$ is isomorphic to $S$.

I would be grateful for some hints and proof ideas, as I struggle a bit with seeing how the encoding would work.

#### Answered By : David Richerby

The following is, as requested, a hint rather than a full answer. I'll hint at one way of doing the coding; I'll not touch on how to define the queries but those formulas will always be horrible and you'd probably end up describing them in words anyway. We'll code a structure $\cal{A}$ that has universe $A$ as a graph $G_\cal{A}$. The will contain one vertex for each element of $A$, plus a whole bunch of other vertices that encode the relations and so on.

1. You can assume a purely relational vocabulary by using standard codings of constants and functions as relations.

2. Coding is done by adding "gadgets": small graphs that you can recognize. Remember that, for every graph $H$ on $k$ vertices, there is a formula $\varphi_H(x_1, \dots, x_k)$ such that $(G, v_1, \dots, v_k)\vDash \varphi_H$ iff the subgraph of $G$ induced by $v_1, \dots, v_k$ is $H$.

3. You probably need a way to say "This vertex is an element of $A$." Come up with a gadget, make a copy of the gadget for each element of $A$ and add an edge between the gadget and the vertex coding that element. (You might not need to do this but it's normally easier to just do it than to prove that it's unnecessary.)

4. You definitely need a way to say "This tuple $a_1\dots a_r$ is in the $r$-ary relation $R$." Come up with a gadget for each relation and a way to attach each tuple in $R$ to its own copy of the gadget. Remember that the tuple $a_1a_2a_3$ is different from $a_2a_3a_1$ so your coding needs to make those different.

If you don't understand what I mean about gadgets, mouse-over the following for a concrete example. However, the example gives away a lot of the answer, so try not to look at it.

You could mark a vertex $v\in G_\cal{A}$ as coding an element of $A$ by adding a $k$-clique to your graph, along with an edge from one vertex of the clique to $v$. So, being adjacent to a $k$-clique means a vertex codes an element of $A$. Make $k$ big enough so there are no other $k$-cliques in $G_\cal{A}$.