[FOM] A question on disjunction and numerical existence properties for extensions of HA

[Harvey Friedman]

On 11/18/05 12:01 PM, "Wojtek Moczydlowski" <wojtek at cs.cornell.edu> wrote:

>  In the article "The Disjunction Property Implies the
> Numerical Existence Property"
> (PNAS, August 1, 1975, vol. 72, no. 8, 2877-2878)
> Friedman proves the any r.e. extension of HA which satisfies the Disjunction
> Property satisfies also Numerical Existence Property. The r.e. assumption is
> essential, as there is a \Delta^0_2 theory, obtained by extending HA
> with false sentence \phi, which satisfied DP but not NEP.
> 
> Is the falseness of \phi essential to construct a counterexample?
> In other words, is there a true extension of HA satisfying DP and
> not satisfying NEP?
> 

The answer is yes. Here is a sketch.

It is well known that there is a recursive sequence A1,A2,... of Pi01
sentences which are independent over PA, in the sense that no nontrivial
Boolean combination of the Ai's is provable in PA. This condition is the
same as: every +-A1,+-A2,... is consistent with PA. It follows immediately
that these Ai are true.

The most straightforward way to prove this is to first prove

LEMMA 1. Let S1,...,Sk be sentences of PA, where each PA + Si is consistent.
Then there is a Pi01 sentence R such that each PA + Si  does not decide A.

Proof: Take A to say "every proof of A from some Si has a proof with smaller
index of notA from some Si". QED

LEMMA 2. There exists a recursive sequence A1,A2,... of Pi01 sentences such
that every +-A1,+-A2,... is consistent with PA.

We will only need to use a weak form of Lemma 2.

There seems to be a generalization of Lemma 1 of some independent interest.
I haven't  seen this stated anywhere. Have you?
 
THEOREM. Let Aij be a recursive doubly indexed set of sentences of PA.
Assume that for all i, {Ai1,Ai2,...} is consistent and proves a tiny amount
of arithmetic. Then there exists a Pi01 sentence which, for all i, is
neither provable nor refutable from {Ai1,Ai2,...}.

Now let B = (therexists n)(An), where the A1,A2,... are given by Lemma 2.

We introduce a property # of finite sequences T1,...,Tk, k >= 1, of
sentences of PA:

there are infinitely many i such that HA + Ai proves T1,...,Tk.

LEMMA 3. B has property #.

The following is well known. E.g., look at

H. Friedman, Some Applications of Kleene's Methods for Intuitionistic
Systems, Lecture Notes in Mathematics, Vol. 337, Springer-Verlag, (1973),
pp. 113-170. 

for a lot of information.

LEMMA 4. Let E be a Pi01 sentence. Then HA + E has the disjunction property.

LEMMA 5. Suppose T1,...,Tk has property #, and assume that HA + {T1,...,Tk}
proves a sentence (C or D). Then T1,...,Tk,C has property # or T1,...,Tk,D
has property #.    

THEOREM 6. There is a true extension of PA which has the disjunction
property (for sentences) but not the numerical existence property (for
sentences). 

Harvey Friedman