[FOM] Bi-interpretability vs mutual interpretability - and Woodin

[Ali Enayat]

Thomas Forster's recent posting asks:

>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!

My response: The particular language for P(N) here is none other than
the language of "analysis", which is often formulated in a two-sorted
FIRST ORDER LANGUAGE, a sort for "natural numbers", a sort for "sets
of natural numbers" (aka "real numbers" sometimes). There is also a
relation symbol for expressing the membership relation between natural
numbers and sets of natural numbers, as well as arithmetical operation
symbols {plus and times}, sometimes augmented by other arithmetical
operation and relation symbols.

Nowadays the above language is often called the language of "second
order arithmetic", which can be misleading, since the theory is
handled by first order, not second order logic.

The language for HC, on the other hand, is the usual (one-sorted)
language of set theory {epsilon}.

There is a "natural" interpretation of second order arithmetic plus
the choice scheme in the theory ZF\{Power set} plus "every set if at
most countable".  "Numbers" are interpreted as finite von Neumann
ordinals, and "sets of numbers" are interpreted in the obvious way.

As it turns out, the interpretation I can be inverted by an
interpretation J of ZF\{Power set} plus "every set is at most
countable" in second order arithmetic plus the choice scheme. Note
that the choice scheme of second order arithmetic translates to the
replacement scheme of set theory via J.

J is usually defined in terms of trees on natural numbers, but one can
also define J by using *pointed* well-founded extensional relations R
on natural numbers, where "pointed" means that R has a "top" element.
This device is quite versatile: it can be used to "simulate" a
Zermelian structure within Quine's NF (as well as Quine-Jensen's NFU),
as noted by Hinnion, and later but independently by Holmes. More
recently, the same device was used by Koepke to interpret ZFC in the
second order theory of ordinals.


Finally, regarding the last question posed by Forster:

>And how important is it for W's programme that the theories should be mutually interpretable (in whatever sense is in play)?

Ever since Descartes' discovery of the two-way street between Geometry
and Algebra, mathematicians have added the following meta-strategy to
their toolbox: when faced with a difficult problem P pertaining to
some domain D, look for an "equivalent" domain D' and try solving the
corresponding problem P' instead of P; and if successful, translate
the solution S' of P' back to obtain the solution S of P.

In our discussion, the "equivalence" is the bi-interpretaion
relationship between theories, which, as emphasized in my previous
posting, is much stronger than mutual interpretability, since it
provides a *canonical correspondence* between models of a theory T and
models of another theory T' bi-interpretable with T.

Best regards,

Ali