[FOM] What does Peano arithmetic have to offer?

[Vaughan Pratt]

On 5/2/2010 7:56 PM, Monroe Eskew wrote:
> On Fri, Apr 30, 2010 at 9:21 PM, Vaughan Pratt<pratt at cs.stanford.edu>  wrote:
>> [...]  The
>> homomorphisms, quotients, products, tensor products, function spaces,
>> etc. of abstract algebra fall well outside the scope of first order
>> logic.
>
> I don't understand; abstract algebra can be done within set theory
> which is a first order theory.

Sorry, I should have been more specific: by "first order logic" I had in 
mind first order number theory in the sense of quantifying over numbers. 
  An algebraic number theorist might indeed use a first order theory 
quantifying over say rings and their homomorphisms, which would look 
like second order logic to a number theorist accustomed to quantifying 
over numbers.

What I don't see is whether Harvey's theorems 4 and 5 are sufficiently 
robust as to carry over to algebraic number theory in any form a number 
theorist would understand.  If not then they would seem to be the sort 
of theorems that would appeal only to logicians and those number 
theorists still working inside PA.  Algebraic number theorists consider 
that they're doing number theory, which raises the question, what can 
logicians tell number theorists they can't do?

A related phenomenon arises with transitive closure.  A first order 
theory whose language has binary relation R and S can't assert that S is 
the transitive closure of R in a way that makes it true in every model 
of the theory.  In an algebraic theory of binary relations such as 
Tarski's RA however, where the domain is (abstract) binary relations 
themselves rather than the domain of the relations, reflexive transitive 
closure can be defined precisely, and even purely equationally.  I 
applied this in [1] (downloadable from my website as 
http://boole.stanford.edu/pub/jelia.pdf ) to expand Kleene's regular 
expressions with two implications which allow the expanded language to 
be finitely axiomatized purely equationally to define a variety ACT in 
which x* is precisely the reflexive transitive closure of x in every 
model of ACT (the abstract spells this out).  Conway had shown earlier 
in his 1971 book *Regular Algebra and Finite Machines* that the 
equational theory of regular expressions had a four-element model in 
which x* was not the reflexive transitive closure of x; that fact 
together with the ineffability of transitive closure in first order 
theories might lead one to believe that no equational theory could force 
x* to be precisely the reflexive transitive closure of x, refuted by ACT.

It seems to me that examples of this kind illustrate the non-robustness 
of theorems of logic when brought to bear on mathematical subjects that 
can be usefully treated in incomparable logical frameworks.  Each 
framework will have its limitations, but why should they carry over to 
other frameworks?

The situation is very much like that of quantum mechanics, which imposes 
no limits of its own on the accuracy with which either position or 
momentum in a given direction can be measured separately, but which does 
not allow both to be measured precisely at the same time.  Switching 
between PA and algebraic number theory, or between a theory with 
relations in its language and one with relations in its domain, is like 
switching between observing position and observing momentum.  A momentum 
observer who naively takes arbitrary precision of position for granted 
on the ground that momentum is *defined* in terms of position (namely 
its time derivative v times the mass m) will find that momentum is 
annoyingly hard to observe, and vice versa.  This limitation of the 
observability of momentum is not intrinsic to physics per se because it 
can be overcome by giving up some precision in position.  By the same 
token limitations imposed by first order logic on the theory of numbers 
may disappear when switching to the theory of rings; in both frameworks 
one is still doing number theory, just as when trading off precision in 
momentum and position one is still doing physics.

Vaughan

[1] V.R. Pratt, Action Logic and Pure Induction, Logics in AI: European 
Workshop JELIA '90 (ed. J. van Eijck), LNCS 478, 97--120, 
Springer-Verlag, 1990.