FOM: Arithmetic: how much? Reply to Tennant

[Joe Shipman]

Neil, I have no argument with most of what you say.  But I would ask you
this: if the universe were actually finite, or (even if infinite) it
imposes some absolute constraints on the calculations we can perform or
the theorems we can derive, how might one ever talk about such
constraints formally and rigorously?  A system of "bounded arithmetic"
or "feasible arithmetic", *without in any way attempting to displace
Peano-Dedekind arithmetic as "the" theory of integers considered
abstractly*, might still be valuable for describing or talking about the
universe we actually live in.

Example.  Let x be the length of Friedman's number n(3) when expressed
in binary notation.  I expect "x is even" is a statement no one will
ever know the truth value of, despite its obvious decidability.  It
would be nice to have a formal system which somehow represented this
fact directly by having neither "x is even" nor "x is odd" be formally
derivable.  Of course here we are only requiring a system whose
derivable sentences are a subset of the derivable sentences of PA; but
one can go further and ask for a system in which a statement like "n(3)
exists" is actually "false", where "false" is interpreted as "there is
no feasible integer with the property defining n(3)".

But let's forget about feasibilist and finitist versions of arithmetic
for now -- Sazonov and others who would like to further explicate the
above may step in if they like.  Consider the following sequence of
theories:

1) Presburger Arithmetic
2) Exponential Function Arithmetic
3) Primitive Recursive Arithmetic
4) Peano Arithmetic
5) Predicative Arithmetic
6) Sentences of Arithmetic provable in ZF
7) Th(N): The set of true sentences of Arithmetic

All but the last are incomplete.  All can be obtained (though the sense
of the word "obtained" weakens from "decidably" to "enumerably" to
"definably" as you move down the list) by the epistemological process
i) observe regularities in the empirical behavior of "objects" and
"counting"
ii) create a formal system that represents these regularities
iii) extend the formal system in a logical (or "logicist") way based on
a priori intuitions, mathematical elegance, simplificatory rounding out,
or any other considerations you like.

When you refer to "Peano/Dedekind Arithmetic", do you mean 4) or 7)?  If
you mean 4), then are you claiming that this (incomplete) theory has a
privileged epistemological status compared with the ones before and
after it on the list? If so, why? If you mean 7), then Sazonov and
Mayberry say "but what do you mean by this, what is this standard model
'{1,2,...},S,+,*' ?".

I'm trying here to shift the discussion from *alternatives* to Peano
arithmetic to *weakenings and strengthenings* of it, in order to
continue comparing arithmetic and geometry.  If you dump the parallel
postulate you get an *incomplete* theory of geometry which *as far as it
goes* seems to describe the physical world.  Similarly, with Peano
arithmetic (or any of the other theories except the last on my list) you
get an *incomplete* theory of arithmetic (Presburger arithmetic is
complete only for sentences which don't have the multiplication symbol)
which *as far as it goes* seems to describe the physical world.  There
are multiple incompatible extensions of "geometry without the parallel
postulate" which cannot all describe the physical world; while in the
case of arithmetic the theories listed above are compatible (actually
more than that, I believe they're ordered by inclusion), and there are
no *natural* examples of multiple incompatible extensions.  Or are
there?

I would guess this last point is the critical one for you.  Because I
can propose the theories PA + MCC ("a measurable cardinal is
consistent") and PA + NMCC ("a measurable cardinal is inconsistent").
What's the difference between viewing these two theories as alternative
extensions of PA, and viewing Euclidean and non-Euclidean geometry as
alternative extensions of "geometry without the parallel postulate"?
You can say "only one of MCC and NMCC is in Th(N), and I can reply "but
only one of PP and NPP is in Th(R^n)", where PP is the parallel
postulate and NPP is its negation, using a standard method of reducing
sentences in elementary geometry to sentences about real numbers.  Since
you admit that both Th(N) and Th(R^n) are a priori, to insist on an
epistemological difference between arithmetic and geometry you might say
"the applicability of Th(R^n) to the external world is arbitrary in a
way that  the applicability of Th(N) is not", but then you will be asked
"which Th(N)?  What do you mean?  Which of MCC and NMCC is in there?".

Let EG- be "Euclidean geometry without the parallel postulate".  The
relevant analogies here are between PA and EG- or between Th(N) and
Th(R^n), not between PA and Th(R^n) or between Th(N) and EG-.   Maybe
EG-+PP  doesn't describe physical reality, but maybe PA+MCC doesn't
either.   Is there an epistemological difference *of kind* between
arithmetic and geometry (apart from arithmetic not having a decision
procedure), or just one of degree?

If you're careful not to slip between Th(N) and PA while thinking about
this you may find what I've written easier to follow. -- JS