[FOM] ACA0, PA, PA'

[Harvey Friedman]

>
>Perhaps I didn't understand the concept of "interpretation".  I
>understand it as a kind of translation.  If I assent to a proposition
>expressed in one language, then I assent to exactly the same
>proposition expressed in another language.

No, that is not the idea of a translation. A translation can be from 
what is viewed to be a false set of axioms into what is accepted to 
be a true set of axioms. Or it can be from what is viewed to be as a 
meaningless set of axioms (i.e., using concepts that are viewed as 
meaningless), into what is viewed to be a true set of axioms. And 
also, from what is viewed to be a true set of axioms into what is 
viewed to be as a meaningleess set of axioms, etcetera.

Translations have nothing to do with truth, falisty, or 
meaninglessness. Translations have nothing to do with meaning.

Here is a toy example. Let us make the simplifying assumption that 
all apples are red, all strawberries are red, and the sky is blue.

Friedman says:

All apples are blue.
All strawberries are blue.
The sky is red.

Buckner says (correctly):

All apples are red.
All strawberries are red.
The sky is blue.

How do we make these into axioms?

We have two unary predicate symbols, A(x) for "x is an apple", S(x) 
for "x is a strawberry". We also have the constant symbol W for "the 
sky". Also we have the unary predicate symbols R(x) for "x is red", 
and B(x) for "x is blue".

Friedman says:

(forall x)(A(x) implies B(x))
(forall x)(S(x) implies B(x))
R(S).

Buckner says:

(forall x)(A(x) implies R(x))
(forall x)(S(x) implies R(x))
B(S).

Here is a translation from Friedman's axioms into Buckner's axioms.

 From the POINT OF VIEW of Friedman:

1. Buckner's universe of objects is the full universe of objects. 
This means that "forall x" and "therexists x" are unchanged under 
translation.
2. Buckner's "being an apple" is translated as "being an apple".
3. Buckner's "being a strawberry" is translated as "being a strawberry".
4. Buckner's "sky" is translated to "sky".
5. Buckner's "being red" is translated as "being blue".
6. Buckner's "being blue" is translated as "being red".

Then the translation of every Buckner axiomis a theorem of the 
Friedmnan axioms. Actually, in this very trivial example, even more 
is true: the translation of every Buckner axiom is a Friedman axiom.

In a translation, you are not allowed to mess with the connectives, 
and, or, not, implies, iff.

In a more sophisticated example,

i) you expect that the translations of the first set of axioms are 
NOT all among the second set of axioms, but are theorems of the 
second set of axioms;
ii) you expect that the universe of objects for the first set of 
axioms to become, under the translation, only a portion of the 
universe of objects for the second set of axioms.

As I said before, there is a translation of ACA0 into PA'. You might 
expect that under this translation, the natural numbers of ACA0 
become natural numbers of PA', but this cannot be the case. Also, 
ACA0 proves that there are plenty of infinite sets of natural 
numbers. Under the translation, these become natural numbers of 
PA'!!!! Why???? Because the only objects of PA' are natural 
numbers.   

>
>You (Friedman) write:
>>  We have three systems: PA, PA', ACA0. You have accepted PA and even
>>  PA' as directly meaningful. We agree that you do not agree that ACA0
>>  is directly meaningful.
>
>Not at all.  I agree that ACA0 is meaningful.  Even "directly" meaningful!
>Of course it means or says something.  I just don't agree with what it says,
>that's all.

I can proceed with this very unusual point of view. But this move is 
almost never made. It is very difficult, perhaps not impossible, to 
make any kind of sense of the position that "sure the concept of 
infinite sets of natural numbers makes perfectly good sense, and 
there are plenty of finite sets of natural numbers. But there are no 
infinite sets of natural numbers." Or perhaps, you would rather say:

"sure the concept of infinite and finite sets of natural numbers 
makes perfectly good sense. But there are no infinite sets of natural 
numbers, and also there are no finite sets of natural numbers."

The reason I can wodk with this unusual point of view is that a 
translation can be made from a perfectly meaningful set of axioms 
that are viewed to be false, into a perfectly meaningful set of 
axioms that are viewed to be true.
>
>Who said I accepted PA'?  If it really is possible to interpret certain
>existential statements in ACA0 in PA', and if I don't agree with those
>statements, then I won't agree with their interpretation either.  Obviously.

You have already accepted PA' because of the following. Remember you 
said that you had no problem with introducing a predicate for "x is a 
prime number." When you said this, you emphasized that the predicate 
is NOT to be used as an object. It rather is used as a definition.

If you don't allow such definitions in even elementary number theory, 
then you have no chance whatsoever of doing elementary number theory. 
Everything would have to be spelled out in full notation, and ...

In PA', one also introduces predicates more complicated than "being a 
prime number". And these predicates are NOT used as objects.

If you don't grant the distinction between using a predicate as a 
definition and using a predicate as an object, then probably nothing 
you have said on the FOM list makes any sense to me.

>
>I wrote
>>  >There need be no term in NL [i.e. natural language system]
>>  >that corresponds to "{x in N: x is not in f(x)}".
>
>and you replied
>>  That's the whole point. In PA or even in PA' we cannot even state
>>  this set existence principle, let alone prove it.
>
>I'm totally confused by that.  If this set existence principle is a theorem
>of ACA0, then can't it also be interepreted as a theorem of PA'?  That's
>what I thought you were saying.  And, whatever that theorem is, I don't
>agree with it.

The translation is a theorem of PA'. The translation is something you 
accept, since it follows logically from the axioms of PA'. The 
translation may be just fine for you, but the thing it is the 
translation of may be false or meaningless.

>
>You wrote in a previous posting
>>PA' ... has no axiom of infinity. However, some predicates on the
>>natural numbers are introduced by definition as I indicated. But
>>these predicates are NOT used as objects.
>
>They are predicates, so they are objects!

Again, if you don't make a distinction between the introduction of a 
predicate as a definition and the introduction of a predicate as an 
object - with quantification over predicates - then we are nowhere. 
You can't do even the most elementary of mathematics without 
introduction of predicates by definition.

Of course, you have the option of insisting that I use the word 
"definition" instead of "predicate" and not change anything I said. 
That would work. Unusual, but that would work.

>Obviously you can't escape the
>force of Cantor's Theorem by turning sets into predicates or some analogue
>of that.

Ah! I see your problem.

Although PA' has predicates, they are NOT USED to interpret objects 
in ACA0. Only natural numbers are used to interpret objects in ACA0. 
Predicates cannot be used to interpret objects in ACA0 in the sense 
that a set in ACA0 becomes a predicate. That is illegal. Sets of 
natural numbers in ACA0 become certain natural numbers in PA'.

This whole matter is rather deep and subtle, and totally unexpected 
to the nonprofessional logician. But it works perfectly. 

>  My problem, which seems to puzzle you, is based precisely on an
>objection to predicates, in particular the idea that we can rewrite "grass
>is green" in any of the following ways
>
>     grass satisfies the predicate "is green"
>     grass falls under the concept <is green>
>
>or anything similar like that.  Indeed, your presentation of PA' as
>containing the following definitions
>
>R(0) if and only if A.
>R(n+1) if and only if B(n,R|<=n).
>
>suggests that we are sneakily introducing nasty objects by the back door.
>What entity is referred to by the noun phrase "R|<=n"?

There are no objects in that definition of R. B(n,R|<=n) is an 
abbreviation that must be taken as a whole. R|<=n is NOT an object.

I should have known better than to use this kind of abbreviation. 
It's my fault for not anticipating your objection - which does not 
apply as you shall see.

Before I restate this more fully, I did notice that I have made a 
serious mistake in logic here. I should have written

R(0,m) if and only if A(m).
R(n+1,m) if and only if B(n,m,R|<=n,_)

where the blank is important.

However, I am now going to make this clearer so that you can see that 
the only objects are natural numbers.

For all m, R(0,m) if and only if A(m).
For all n,m, R(n+1,m) if and only if 
(Qx1|<=n)(Qy1)(Qx2|<=n)(Qy2)...(Qxr|<=n)(Qyr)(B(n,m,x1,...,xr,y1,...,yr)

where B(n,m,x1,...,xr,y1,...,yr) is a quantifier free formula in the 
language of PA with the letter R appended as a new binary relation 
symbol, and all subformulas of the form B(alpha,beta) have alpha 
among the variables x1,...,xr. Here the variables 
n,m,x1,...,xr,y1,...,yr are distinct, and (Qyi|<=n) is the well known 
abbreviation for quantification restricted to natural numbers <= n.

I think that a little care shows that we need introduce exactly one 
such definition - i.e., use only one R - and in this definition, we 
can get away with r = 1, although B will be somewhat long and ugly. 
Or we can introduce one such R with r = 1 and a reasonable number of 
digestable little ones with only one quantifier (smaller than r = 1) 
and B is quantifier free and strictly within the language of PA.

In other words, informally, the definition of R(n+1,m) must involve R 
applied only to numbers <= n and arbitrary m. The restriction to 
numbers <= n here in the first argument of R is to avoid the obvious 
circularity.

This is called definition by induction, or definition by recursion.

It is perhaps somewhat surprising that we do not need to expand 
induction in PA to cover any formulas that mention the R's, in order 
to accomplish the translation of ACA0 into PA'.

>
>Your idea that I accept PA' is based on the fact I accept some sort of
>induction.  Does it follow that we cannot accept induction unless we accept
>predicates/concept/sets?  I'm very sceptical of that.


A very principal point is that one can certainly accept induction 
without accepting or thinking about any sets of natural numbers, 
infinite or finite. That is what PA is about. Also PA'.

Now here is some more relevant information.

There is a system RCA0 - also in Simpson's book - which is weaker 
than ACA0, but still strong enough to do a lot of real analysis. 
There is also a somewhat stronger system WKL0 than RCA0, but still 
substantially weaker than ACA0, which does even more real analysis, 
naturally and directly. Of course, all three of these systems talk 
directly about infinite sets of natural numbers.

THEOREM. RCA0 and WKL0 are interpretable (translatable) into PA.

I.e., we don't need PA' for this. Just PA. In fact, we don't need all 
of PA. We need just a weak fragment of PA.