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:

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 AB if models A and B are isomorphic. Isomorphic models are first-order indistinguishable, so if AB then A⊨φ⇔B⊨φ


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