[FOM] What does Peano arithmetic have to offer?
Vaughan Pratt
pratt at cs.stanford.edu
Mon May 3 13:38:08 EDT 2010
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.
More information about the FOM
mailing list