MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm afraid this question might be too localized, but I have no better place to ask it:

In the section Classes which interpret any structure of his Model Theory Hodges shows how each $L$-structure $B$ can be converted into a graph $A = \Delta(B)$, $L$ a first order language with finite signature.

He associates every element of $B$ with a so-called 5-tagged element $a$ of $A$. Likewise he associates the i-th symbol of the signature $S_i$ with a (i+6)-tagged element of $A$. For further details see Hodges, p. 228 ff.

alt text

The only question I have at this point is: Why isn't it enough to associate all the relation symbols with different 6-tagged (and 6-tagged only) elements of $A$? Why is it necessary - for his argument's sake - to distinguish them further by their "tag count"?

share|cite|improve this question
I haven’t got the book handy, but I suppose you need to be able to distinguish the relation symbols from each other by a (parameter-free) formula. If they were all $6$-tagged, they would be isomorphic, hence indistinguishable. – Emil Jeřábek Jun 9 '11 at 17:44
Perhaps one consideration is that by doing this you seem to make a graph with exactly the same automorphism group as the original structure. Otherwise, as Emil says, you might introduce automorphisms of the graph that do not correspond to any automorphism of the original structure, simply by moving the (nodes corresponding to the) relations rather than the nodes corresponding to the elements. – Joel David Hamkins Jun 9 '11 at 17:50
I think the goal is not the automorphism group, but interpretation of $B$ in $A$: for any sentence $\phi$, we have a $\phi^*$ such that $B\models\phi$ iff $A\models\phi^*$. But the point is the same: if $B\models\forall x\,P(x)\land\neg\forall x\,Q(x)$, we’d better make sure that the gadgets which are used in $A$ to read off the values of $P$ and $Q$ cannot be swapped by an automorphism, as otherwise we couldn’t interpret $\forall x\,P(x)$ and $\forall x\,Q(x)$ by a different formula. – Emil Jeřábek Jun 9 '11 at 18:03
Yes, otherwise you'd need a parameter. Emil, why not post as an answer? – Joel David Hamkins Jun 9 '11 at 18:08
My question then is: Why is the distinguishability of the relations so important? I would find it consistent when the relations were treated on an equal footing as the elements. – Hans Stricker Jun 9 '11 at 18:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.