Can somebody explain to me how we define an isomorphism between structures?

Question

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?

Answer 1

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.