[FOM] ZF[n] and (n+2)-order arithmetic

[Ali Enayat]

This is a reply to the recent query of Colin McLarty (Sep 7) regarding
the relationship between n-th order arithmetic and set theory.

1. There are at least two natural notions of "relationship" one can
explore here, namely mutual interpretability  and bi-interpretability.

2. In an earlier FOM posting (Jan 19, 2010), available at the link
below, I explained the distinction between mutual interpretability and
bi-interpretability, and pointed out the system of set theory that is
bi-interpretable with second order arithmetic.
http://cs.nyu.edu/pipermail/fom/2010-January/014318.html
My posting above includes a mention of Mostowski's work, and a
reference to Simpson's refinement of it in his SOSOA monograph (the
Mostowski reference is a 1961-paper of his; see ref [193] in Simpson's
book).

3. I am not aware of any published reference for the interpretability
relationship between n-th order arithmetic and appropriate set
theories. My feeling is that it is "common knowledge" that the
technique for finding the "set-theoretic equivalent" of second order
arithmetic lends itself to  a natural generalization for larger values
of n.

4. On the other hand, for 0-th order PA, i.e., PA itself, ever since
Ackermann's 1940-paper we know how to interpret ZF\{Infinity} in PA,
and of course von Neumann taught us there is an interpretation of PA
in ZF\{Infinity}.  However,

(A) ZF\{Infinity} is NOT bi-interpretable with PA, but rather
(B) ZF\{Infinity" + "every set has a transitive closure" is
bi-interpretable with PA.

Of course ZF\{Infinity} is MUTUALLY interpretable with PA, but (A) is
a rather recent result, it appears in the following paper:

A. Enayat, J. Schmerl, and A. Visser, omega-models of finite set
theory, in the soon-to-appear volume Set theory, Arithmetic, and
Foundations of Mathematics: Theorems, Philosophies (edited by J.
Kennedy and R. Kossak), Cambridge University Press, 2011.

(B) has a more complicated history. This result was established first
by Mycielski in 1964, and published in Russian in :

 Mycielski, Jan. The definition of arithmetic operations in the
Ackermann model, Algebra i Logika Seminar (1964) , 3:64–65.

However, Mycielski's result did not reach a wide audience and lay
hidden from for non-Russian readers until it was re-discovered by
Richard Kaye and Tin Lok Wong in the following paper:

On interpretations of arithmetic and set theory, Notre Dame Journal of
Formal Logic Volume 48, Number 4 (2007), 497-510.

Regards,

Ali Enayat









Message: 2
Date: Wed, 7 Sep 2011 10:32:46 -0400
From: Colin McLarty <colin.mclarty at case.edu>
To: Foundations of Mathematics <fom at cs.nyu.edu>
Subject: [FOM] ZF[n] and (n+2)-order arithmetic
Message-ID:
       <CAOzx82qCSu+9dZgCJYg2Yc82_U-jFYKzAeNp7E1HTgtPxFOZeQ at mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1

Several people have given good advice on the relation between higher
order arithmetic, and ZF with power set restricted.  And there is
well-published material on restricting power set in proofs of
determinacy, following Harvey.  But so far no one has known a citation
for the connection with higher order arithmetic.   It may never have
been published.  Since I want to cite it elsewhere, I venture a
proof-sketch.  The relation of orders is one off from what I suggested
in my earlier query and the most natural version will omit choice for
3rd and higher order.

The theory ZF[n] is the ZF axioms except power set, and positing that
the set N of natural numbers has n iterated power sets.

STATEMENT ZF[n] is inter-interpretable with (n+2)-order arithmetic.

Sketch:  The nonobvious direction is to interpret ZF[n] in (n+2)-order
arithmetic.  Ackermann interpreted all of ZF except infinity in PA.
He interprets any number n as the 'ZF-set' of all m such that the m-th
place in the binary expansion of n is a 1.  In other words the
remainder of n on division by 2^(m+1) is at least 2^m.

This codes the hereditarily finite sets as binary numbers, and in fact
it has a definable global choice function.

Extend this to second order arithmetic by interpeting a ZF-set as a
set (in the sense of second order arithmetic) which is either a
singleton {n} or unbounded.  Interpret any singleton {n} the way
Ackermann interprets n as a hereditarily finite ZF-set,  And interpret
{n} as a ZF-element of an unbounded set P iff n is an element of P in
the second order sense.  So the singletons correspond to hereditarily
finite sets.  The unbounded sets correspond to all ZF sets of rank
omega.   This interpetation  still has a definable global choice
function.

In third order arithmetic interpret a ZF-set as any class C of sets of
numbers such that for every set P in C, P counts as a ZF-set in the
2nd-order interpretation.  This includes a ZF-powerset for the ZF-set
of all natural numbers, but no powerset for that powerset.  This
interpretation does not provably satisfy choice for ZF sets.

The step used for third order works as well for all higher orders.

So two questions:

Is this sketch correct?

Is there an existing reference to cite in writing about this matter?