[FOM] Bi-interpretability vs mutual interpretability - and Woodin
T.Forster at dpmms.cam.ac.uk
Thu Jan 21 02:49:16 EST 2010
while we have your ear...
Can you say something about the nature of the interpretability between the
theory of HC and the theory of P(N)? It's not entirely clear from Woodin's
article what language these theories are to be expressed in, and that
clearly matters! And how important is it for W's programme that the
theories should be mutually interpretable (in whatever sense is in play)?
On Jan 21 2010, Ali Enayat wrote:
>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:
>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
>(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.
>FOM mailing list
>FOM at cs.nyu.edu
More information about the FOM