3
$\begingroup$

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 (source)

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"?

$\endgroup$
26
  • $\begingroup$ 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. $\endgroup$ Jun 9, 2011 at 17:44
  • $\begingroup$ 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. $\endgroup$ Jun 9, 2011 at 17:50
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 9, 2011 at 18:03
  • $\begingroup$ Yes, otherwise you'd need a parameter. Emil, why not post as an answer? $\endgroup$ Jun 9, 2011 at 18:08
  • $\begingroup$ 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. $\endgroup$ Jun 9, 2011 at 18:17

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.