An isomorphism
between two structures constructed with relations (e.g. trees,
orderings, etc.)
(A, R_{A})
and (B, R_{B})
is a bijection, f:A→B
, such that
∀ a_{1},a_{2}∈A a_{1}R_{A}a_{2} ⇔ f(a_{1})R_{B}f(a_{2})
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 a_{i}∈A
and
for all relations r
,
and all functions f
, and all constants c
:
g(c^{A})=c^{B}
g(f^{A}(a_{1},...,a_{n}))
= f^{B}(g(a_{1}),...,g(a_{n}))
r^{A}(a_{1},...,a_{n})
⇔ r^{B}(g(a_{1}),...,g(a_{n}))
where c^{A}
is the interpretation for c
in
A
,
f^{A}
is the interpretation for f
in
A
, and
r^{A}
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⊨φ
Doets, Kees. From Logic to Logic Programming. MIT Press, 1994.
Copyright © 2014 Barry Watson. All rights reserved.