[FOM] Re: Flexible Predicates

[Ali Enayat]

This is a note on Shavrukov's comment on Spector's positive reply to the
following query of Taranovsky (May 31, 2004):

> Is there an arithmetical formula phi with one free variable such that
> for every Pi-0-1 formula psi with one free variable it is consistent
> with Peano Arithmetic that
> Forall n (phi(n) <--> psi(n)).
> Can phi be a Pi-0-1 formula?

Spector pointed out that the answer is positive, using the recursion
theorem, and Shavrukov cited Kripke's following article as an original
source.

S.A.Kripke. "Flexible" predicates of formal number theory. Proc.AMS
13(1962)647-650.

I am writing to add:

(1) Another independent original source is A. Mostowski's paper "A
generalization of the completeness theorem", Fund. Math., Volume XLIX
(1961), 205-232.  [It is curious to note that Mostowski's paper was
received by the editors on April 30, 1960, and Kripke's was received on
March 11, 1960].

(2) What the work of Mostowski and Kripke shows is that there is a fixed
r.e. set W_e, such that given *any* subset X of natural numbers, the theory

PA + {" n is in W_e" : n in X} union {"n is not in W_e": n not in X} is
consistent.

(3)A modern exposition of flexible predicates can be found in Hajek and
Pudlak's excellent mononograph "Metamathematics of First Order Arithmetic"
(see Theorem 2.15).

(4) Flexible predicates can be used to establish the following surprising
result (I first heard of this result from Hugh Woodin in 1991, who had
proved it from scratch; later I saw how it follows from the
Mostowski-Krikpke classical work, coupled with Bernay's arithmetized
completeness theorem).

Theorem. There is an r.e. set W_e such that:

(a) PA + Con(PA) proves "W_e is empty", and

(b) If M is any model of PA, and S is a subset of M that is finite in the
sense of M (i.e., M can be coded by an element of M via base 2 coding),
there is an end extenion N of M satisfying PA such that W_e, as computed in
N, is precisely S.

Regards,

 Ali Enayat