Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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. –  Yuval Filmus Jul 13 '11 at 22:17

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

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

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