[FOM] Bi-interpretability vs mutual interpretability

[Ali Enayat]

Thomas Forster has asked me to elaborate on my previous posting in
relation to interpretability, hence the change of the subject line to
the present one.

Before I start, let me provide the URL of the Friedman article on
interpretations that I mentioned in my last posting:

http://www.math.ohio-state.edu/~friedman/pdf/Tarski1,052407.pdf

The notions of interpretability and bi-interpretability between two
theories S and T are purely syntactic, but thanks to the completeness
theorem, they can be recast in model-theoretic terms as follows.

S is interpretable in T, via some interpretation I, if there is a
uniform way - via appropriate first order formulas, that's where the I
comes in by specifying exactly which formulas - of defining a model
I(M) of S for every model M of T.  The equality relation on I(M) is
allowed to be an equivalence (congruence) relation by the way.

S is said to be *bi-interpretable* with T if there is an
interpretation I of S in T, and an interpretation J of T in S, such
that S and T "invert" each other in the following sense:

(1) There is a uniform [definable] isomorphism between any model M of
T, and the model J(I(M)).
(2) There is a uniform [definable] isomorphism between any model M of
S, and the model I(J(M)).


ZF and ZFC are mutually interpretable [for the nontrivial direction
one can use either L [the constructible universe] or HOD [hereditarily
ordinal definable sets]. To see that ZF and ZFC are, in contrast, not
bi-interpretable, one can proceed as follows [there are other ways of
proving this].

(A) If S and T are bi-interpretable, then the automorphism groups
arising as Aut(M) for some model M of S must coincide with the
automorphism groups arising as Aut(M) for some model M of T.

(B) No model of ZFC has an automorphism f of order 2 since an
automorphism of finite order must fix the ordinals of the model, and
in the presence of AC, each set X of the model must also be fixed by f
since X is constructible from a subset of S ordinals in the sense of
the model [the latter result is well-known but not entirely trivial].

(C) By a theorem of Cohen, there is a model of ZF that has an
automorphism of order 2. Note that such a model cannot be well-founded
since well-founded models of the extensionality axiom are rigid.
Cohen's result is established by forcing over a nonstandard model of
ZF. The forcing machinery, contrary to the impression given by popular
expositions, can be recast as an entirely syntactic construction that
works for all models of set theory, even the nonstandard ones. This
was already very clear to Cohen, who remarked in his famous book on
the subject that independence results obtained by forcing, such as
"Con(ZF) implies Con(ZF+ not AC)", can be verified in PRA [primitive
recursive arithmetic], let alone PA.

Best regards,

Ali