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.


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}$.

If you still don't understand, leave a comment and I'll try to explain it better.

| cite | improve this answer | |
  • $\begingroup$ Thank for the rather detailed hint. I can see how a $G_A$ could look like so that $A$ is recoverable from it via a first-order query. (For instance, your suggested encoding of elements as adjacent to a large clique, and a tuple $(a_1,a_2,...,a_r)$ could be encoded by having a path of length $i$ from $a_i$ to the vertex representing the tuple.) However I don't see exactly how such a Graph is constructed from the structure via a first-order query. To build the gadgets I need additional vertices, where do they come from? $\endgroup$ – Syzygy Jul 9 '14 at 11:15
  • $\begingroup$ Good point -- constructing the graph via a first-order interpretation is probably the hardest part of the exercise and I didn't touch on it at all. The universe of the $G_{\cal A}$ will be $A^k$ for some appropriate $k$. You can use the equality type of a tuple in $A^k$ (the set of facts $a_i=a_j$ and $a_i\neq a_j$ that hold for the tuple) to give yourself identifiable sets of vertices to play with. $\endgroup$ – David Richerby Jul 9 '14 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.