3
$\begingroup$

I was reading this definition from journal article 'fixed-point logics with nondeterministic choice' by Anuj Dawar and David Richerby. On page 505 it says

'Classes of structures are assumed to be isomorphism-closed: if a structure is in a class, all images of that structure under isomorphisms are in the class. If $\mathcal{C}$ is a class of structures, a k-ary query on $\mathcal{C}$ maps each structure $\mathcal{U}\in\mathcal{C}$ to a k-ary relation on |$\mathcal{U}$| such that if $\rho$ : $\mathcal{U}\rightarrow\mathcal{B}$ is an isomorphism, $\mathcal{Q}(\mathcal{B})$ = $\rho(\mathcal{Q}(\mathcal{U}))$'.

I am trying to understand how we have an isomorphism between structures by some example? Also what exactly query is needed for? Why do we have need to map a structure to a k-ary relation on its universe?

$\endgroup$
  • 3
    $\begingroup$ It's defined just at it is defined for groups, rings etc. If you want a formal definition, look up any text on universal algebra. $\endgroup$ – Yuval Filmus Jul 13 '11 at 22:17
8
$\begingroup$

As Yuval Filmus says, it is exactly as in algebra. Two structures $\mathcal{A}$, $\mathcal{B}$ are isomorphic if there is a function $F\colon |\mathcal{A}| \to |\mathcal{B}|$ such that:

  • $F$ is a bijection
  • For every function symbol $g$ in the language, of some arity $n$, for all $a_1, \ldots, a_n \in |\mathcal{A}|$, $F(g^\mathcal{A}(a_1, \ldots, a_n)) = g^{\mathcal{B}}(F(a_1),\ldots, F(a_n))$. This also covers constant symbols as they are 0-ary functions.
  • For every relation symbol $R$ in the language, of some arity $n$, for $a_1, \ldots, a_n \in |\mathcal{A}|$, $A \vDash R(a_1, \ldots, a_n)$ if and only if $\mathcal{B} \vDash R(F(a_1),\ldots,F(a_n))$.

The term "query" is not part of the definition of an isomorphism. As defined in the paper, a query is a relation on the domain of each of a class of structures (so the query consists of one relation per structure) which has the property that the truth values are preserved by isomorphisms: if $a_1, \ldots, a_n \in |\mathcal{A}|$ and $\mathcal{A}$ is isomorphic to $\mathcal{B}$ via $F$ then $Q(a_1, \ldots, a_n)$ holds if and only if $Q(F(a_1),\ldots,F(a_n))$ holds. For example, if we take the class of structures to be the class of all graphs then we could let $Q(a,b)$ be the property that there is a path from $a$ to $b$, and this would have the necessary invariance under isomorphisms.

$\endgroup$

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.