Isomorphism

An isomorphism between two structures constructed with relations (e.g. trees, orderings, etc.) (A, RA) and (B, RB) is a bijection, f:A→B, such that

	
∀ a1,a2∈A a1RAa2 ⇔ f(a1)RBf(a2)
	
      

In such a case the structures are said to be isomorphic.

An isomorphism between two first-order models A and B which have universes of discourse A and B respectively, is a bijection g:A→B such that ai∈A and for all relations r, and all functions f, and all constants c:

• g(cA)=cB
• g(fA(a1,...,an)) = fB(g(a1),...,g(an))
• rA(a1,...,an) ⇔ rB(g(a1),...,g(an))

where cA is the interpretation for c in A, fA is the interpretation for f in A, and rA is the interpretation for r in A. Likewise for B.

We write A≅B if models A and B are isomorphic. Isomorphic models are first-order indistinguishable, so if A≅B then A⊨φ⇔B⊨φ

References

Doets, Kees. From Logic to Logic Programming. MIT Press, 1994.