[FOM] Concerning Con(PA)

[Harvey Friedman]

On Mon, May 25, 2015 at 6:17 PM, Timothy Y. Chow <tchow at alum.mit.edu> wrote:
> The late Edward Nelson regarded the consistency of PA as being an "open
> problem."  I have been trying to understand exactly what he meant by this
> claim.  Unfortunately, of course, Nelson is no longer with us.  However,
> since there are others (perhaps even some readers of FOM) who seem to agree
> with Nelson on this point, maybe they can address some of the points I make
> below, if not on Nelson's behalf then from their own point of view.
>  I will use "Nelson" hereafter to refer synecdochially to those whose
> beliefs are sufficiently similar to Nelson's (or what I think are Nelson's).

1. ABOUT Con(PA).
2. REGARDING Impossible Counting.

1. ABOUT CON(PA).

Chow uses Con(PA) throughout his discussion .This is not a direct
reply to Chow.. Instead, it is a brief discussion of aspects of
Con(PA) that I find highly productive.

Concerning ultrafinitism, feasibility, and the like, a particularly
vivid place to bring these concepts to life is in the mathematics of
bridge and chess. See
http://www.cs.nyu.edu/pipermail/fom/2014-December/018472.html

Earlier, I made some postings concerning Con(PA), particularly in
connection with Voevodsky starring in a video discussing Con(PA) as an
open problem.

I had mentioned the Bolzano Weierstrass theorem in this connection.
There are some variants that we want to deal with, and here is a
sample of two of them. L

BWQ. Every bounded infinite sequence from Q has an infinite Cauchy subsequence.
BWQ'. Every strictly increasing infinite sequence from Q[0,1] has an
infinite 1/n Cauchy subsequence.

The following is well known (I think I am usually cited for this or
this kind of thing):

BWQ and BWQ' are provably equivalent to ACA_0 over RCA_0.

COROLLARY. PA is interpretable in RCA_0 + BWQ and RCA_0 + BWQ'..

So the idea is that BWQ, BWQ' is an essential component of mathematics
that is readily accepted and used or conceptually used by all of the
Nelsons, Voevodskys, etcetera of this world. Hence Con(PA) is not an
issue.

The obvious weakness in this line of argument is the use of RCA_0.

Enter STRICT REVERSE MATHEMATICS. SRM was my original conception of RM
= Reverse Mathematics, and at the time it was entire premature, and
unwieldy. So I focused on a strategic choice of base theory, namely
the by now famous RCA_0. See
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#1 for the original 1975 documents on early conceptions of SRM - where
my ideas actually go back to 1969.

I have written about SRM later this in various venues, but only
started to systematically gather my thoughts for publication in:

The Inevitability of Logical Strength: strict reverse mathematics,
Logic Colloquium ’06, ASL, ed. Cooper, Geuvers, Pillay, Vaananen,
2009, 373 pages, Cambrdige University Press, pp. 135-183.

The idea is to not have any base theory whatsoever, but only small
collections of actual essential mathematical statements in everyday
use. In particular, any kind of schemes are totally banned.

I am writing an overdue paper on SRM refining and developing it
further. One aim of this paper is to give an impeccable version of the
Corollary in SRM. I.e., show that BWQ or BWQ' together with a small
collection of essential everyday mathematical statements of a
particularly elementary kind, form a formal system in which PA can be
interpreted.

2. REGARDING IMPOSSIBLE COUNTING
http://www.cs.nyu.edu/pipermail/fom/2015-May/018742.html

In the paper on my website,

https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#88. Impossible Counting, May 26, 2015, 9 pages, draft.

I also considered algorithmic unsolvability. I mention one of a number
theoretic nature, and this one:

Theta(k) is the number of binary operations up to k-similarity. Two
bops are k-similar if and only if they have the same restrictions to k
element sets up to isomorphism.

(NOTE: We can restrict to countable bops and Theta(k) will remain the
same. Also we can restrict to bops with domain Z. Theta(k) would
change, but the results would be the same).

Theta(k) is not recursive. There  go on to talk about Theta(12), which
is the high point of what I am trying to say.

I want to mention a related algorithmic unsolvability result.

Lambda(k) is the number of finite binary operations up to k-similarity.

This is also not recursive.

Harvey Friedman