[FOM] How much of math is logic?

[Richard Heck]

joeshipman at aol.com wrote:
> Chow:
>   
>> My suggestion is that, in order to avoid arguments about contentious topics that are tangential to your (first) main question, you rephrase your question as follows:
>>
>> For suitable "X", one can say that ZFC = logic + AxInf + X.  Just how weak can "X" be made to be?
>>     
> I do want to avoid tangential discussions, and I like this suggestion. To clarify, it is also the case that one can say PA = logic + Y; and we also want to know how weak Y can be; what I was really driving at is, for the weakest such Y, how close logic + AxInf +Y comes to ZFC.
>   
If logic is (full) second-order logic, then Y is a weak axiom of
infinity, i.e., a statement of the form: There are not Dedekind finitely
many objects. Russell showed how to interpret PA in this theory, and the
PA you get is full second-order PA. It's obvious that PA entails such a
weak axiom of infinity. The logic here can be weakened to \Pi^1_1
second-order logic, in which case you only get \Pi^1_1 PA. Since there's
no set theory here, it's not clear what to make of the distinction
between this sort of weak axiom of infinity and a stronger one. Note
that, for this result, we don't need any non-logical vocabulary.

Here's the neat things about Russell's treatment: His axiom of infinity
just says that there are not (non-Dedekind) finitely many individuals.
Russell then shows that this entails that there are Dedekind infinitely
many classes at level 2---if \kappa is infinite, then 2^2^\kappa is
Dedekind infinite---and so we get PA at level 2. Getting full PA here
requires reducibility, which (as Ramsey pointed out) just collapses
ramified, predicative higher-order logic into simple, impredicative
higher-order logic. The expert on this kind of issue is Allen Hazen.

If you approach this via set theory, then, with the logic again being
(either full or \Pi^1_1) second-order logic, the weak axiom of infinity
can take the form of null set, adjunction, and extensionality, as has
already been mentioned. Adding a strong axiom of infinity to this set of
axioms doesn't give a very strong set theory, even in full second-order
logic, since you don't have power set. It's probably known what the
strength of this theory is. It wouldn't terribly surprise me if it were
no stronger than PA, since you really won't get many infinite sets.
Indeed, it looks to me as if the infinite sets you get will just be
isomorphic to the finite ones you get, with the infinite set whose
existence AxInf posits playing the role of the null set.

There is a lot of recent work on what you can do in predicative systems
in a more Fregean setting. (See John Burgess's /Fixing Frege/, chapter
two, for an overview.) For example, consider Frege's axiom V:
    ^xFx = ^xGx <--> (x)(Fx <--> Gx)
This is of course inconsistent in full (even \Pi^1_1) second-order
logic, but it is consistent in ramified predicative second-order logic
(and, as Ferreira and Wehmeier showed, even with \Delta_1^1 second-order
logic). It is now known that I\Delta_0 + exp is interpretable in this
system (Heck, without exp; Burgess and Hazen, with). Recent work of
Albert Visser's has precisely determined the strength of such theories:
It's below I\Delta_0 + superexp. (This is really gorgeous work. I highly
recommend it. The paper is on the Amsterdam logic group's preprints
site.) It is a nice question whether there are any natural axioms one
could add to this system to get stronger extensions, and it's not
currently known what the strength of the \Delta^1_1 system is.

A similar thread has studied predicative systems with HP
    Nx:Fx = Nx:Gx iff F is equinumerous with G
as the base axiom. Again, you get I\Delta_0 + exp, and I am morally
certain that there is a natural axiom that strengthens the theory to
something like ACA_0, but I haven't yet been able to prove that you
don't get any more than that.

Richard

-- 
==================================================================
Richard G Heck, Jr
Professor of Philosophy
Brown University
http://bobjweil.com/heck/
==================================================================
Get my public key from http://sks.keyserver.penguin.de
Hash: 0x1DE91F1E66FFBDEC
Learn how to sign your email using Thunderbird and GnuPG at:
http://dudu.dyn.2-h.org/nist/gpg-enigmail-howto