[FOM] Aaronson's Summary of Incompleteness

[Harvey Friedman]

Scott Aaronson has a new survey paper on P=NP,
http://www.scottaaronson.com/papers/pnp.pdf which is also being
discussed in his blog at http://www.scottaaronson.com/blog/?p=3095

His paper has a brief summary of the situation regarding "independence
from set theory" which I reproduce here for your convenience. He still
wants to include this brief summary even though his view is that the
independence of P = NP from set theory is "far fetched". So his
section on independence of set theory is not really relevant to what
he says about P = NP.

His brief summary is reasonably well done for a non expert.
Nevertheless, it is worth my commenting on this because, as would be
expected, it misses some important aspects. Of course, I agree with
Aronson that there is no reason as of now to consider independence of
P = NP from set theory to be a realistic possibility, at least based
on what we know now.

The relevant part of his currently circulated draft
http://www.scottaaronson.com/papers/pnp.pdf is on page 25. In this
current draft, he writes that known independence from set theory falls
into the following 4 categories:

(1)  Independence of statements that are themselves about formal
systems: for example, that assert their own unprovability in a given
system, or the system’s consistency. This is the class produced by G
̈odel’s incompleteness theorems.

(2)  Independence of statements in transfinite set theory, such as CH
and AC. Unlike “ordinary” mathematical statements—P ̸= NP, the Riemann
hypothesis, etc.—the set-theoretic ones can’t be rephrased in the
language of elementary arithmetic; only questions about their
provability from various axiom systems are arithmetical. For that
reason, one can question whether CH, AC, and so on need to have
definite truth-values at all, independent of the axiom system. In any
case, the independence of set-theoretic principles seems different in
kind, and less “threatening,” than the independence of arithmetical
statements.19

(3) Independence from “weak” systems, which don’t encompass all
accepted mathematical reasoning. Goodstein’s Theorem [101], and the
non-losability of the Kirby-Paris hydra game [142], are two examples
of interesting arithmetical statements that can be proved using small
amounts of set theory (or ordinal induction), but not within Peano
arithmetic.

(4) Independence from ZF set theory of strange combinatorial
statements, which (alas) would never have been studied if not for
their independence. Harvey Friedman [93] has produced striking
examples of such statements.

Before presenting my revised version of 1-4 below, let me first turn
to two fuller discussions of the range of Incompleteness:

1. https://u.osu.edu/friedman.8/foundational-adventures/boolean-relation-theory-book/
and in particular in the Introduction, 237 pages, directly at
http://u.osu.edu/friedman.8/files/2014/01/0.Intro061311-17n3hse.pdf
2. In the paper for Templeton's Goedel volume for the 1986 meeting,
published as the book Horizons of Truth,at
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/,
#57, directly at
http://u.osu.edu/friedman.8/files/2014/01/Fortyyears111909-1taw9j8.pdf
See the section Incompleteness in the Future.

In 1, we have this outline (I include the relevant sections of the
Introduction):

0.1. General Incompleteness.
0.2. Some Basic Completeness.
0.3. Abstract and Concrete Mathematical Incompleteness.
0.4. Reverse Mathematics.
0.5. Incompleteness in Exponential Function Arithmetic.
0.6. Incompleteness in Primitive Recursive Arithmetic, Single
Quantifier Arithmetic, RCA0, and WKL0.
0.7. Incompleteness in Nested Multiply Recursive Arithmetic, and Two
Quantifier Arithmetic.
0.8. Incompleteness in Peano Arithmetic and ACA0.
0.9. Incompleteness in Predicative Analysis and ATR0.
0.10. Incompleteness in Iterated Inductive Definitions and Π11-CA0.
0.11. Incompleteness in Second Order Arithmetic and ZFC\P. 0.12.
Incompleteness in Russell Type Theory and Zermelo Set Theory.
0.13. Incompleteness in ZFC using Borel Functions.
0.14. Incompleteness in ZFC using Discrete Structures.

In 2, Incompleteness of the Future, we have this outline:

i. First Incompleteness.
ii. Second Incompleteness.
iii. Consistency of the AxC. Consistency of the most basic, and once
controversial, early candidate for a new axiom of set theory.
iv. Consistency of the CH.
v. ∈_0 consistency proof.
vi. Functional recursion consistency proof.
vii. Independence of AxC.
viii. Open set theoretic problems in core areas shown independent.
ix. Large cardinals necessarily used to prove independent set
theoretic statements.
x. Large cardinals necessarily used to prove the consistency of set
theoretic statements.
xi. Uncountably many iterations of the power set operation necessarily
used to prove statements in and around Borel mathematics.
xii. Large cardinals necessarily used to prove statements around Borel
mathematics.
xiii. Independence of finite statements in or around existing
combinatorics from PA and subsystems of second order arithmetic.
xiv. Large cardinals necessarily used to prove sentences in discrete
mathematics, as part of a wider theory (Boolean Relation Theory).
xv. Large cardinals necessarily used to prove explicitly Π01
sentences. See section 11 above for the current state of the art.

Here is my revision/amplification of Aaronson's 1-4 above.

(1)  Independence of statements that are themselves about formal
systems: for example, that assert their own unprovability in a given
system, or the system’s consistency. This is the class produced by G
̈odel’s incompleteness theorems. (Keeping Aaronson's language).

(2)  Independence of statements in transfinite set theory, such as CH
and AC. Unlike “ordinary” mathematical statements—P ̸= NP, the Riemann
hypothesis, etc.—the set-theoretic ones can’t be rephrased in the
language of elementary arithmetic; only questions about their
provability from various axiom systems are arithmetical. For that
reason, one can question whether CH, AC, and so on need to have
definite truth-values at all, independent of the axiom system. In any
case, the independence of set-theoretic principles seems different in
kind, and less “threatening,” than the independence in (3) - (7)
below, which includes arithmetical statements. (Keeping almost all of
Aaronson's language).

(3) Independence of statements involving only subsets of complete
separable metric spaces that are projective (and associated
functions). There are only continuumly many such sets( functions), and
the sets come from taking complements and projections starting with
multidimensional open sets. The projection operator here is
surprisingly powerful. Independent statements previously encountered
by descriptive set theorists arise already with the use of one
projection (after first taking a complement). A phenomena appears in
the known examples that does not appear in (2). Namely, the
independent statements in this category are shown to be consistent by
actually proving them using large cardinal hypotheses. This is more
threatening than (2).

(4) Independence of statements involving only subsets of complete
metric spaces that are Borel measurable (and associated functions).
These come from taking countable unions and complements starting with
open sets. This is much more restrictive than a single projection of a
closed set in Baire space (the complete separable metric space N^N).
The clearest examples are proved in ZFC but only by using uncountably
many iterations of the power set operation (far more than ZC = ZFC
without the Replacement axiom). The first example of this involved a
celebrated problem from infinite game theory called Borel Determinacy.
This is much more threatening than (3).

(5) Independence of statements involving only countable sets,
requiring reasoning with the uncountable. The most well known examples
in this category are proved in ZFC without the power set axiom
(countable set theory), which is far weaker than the ZFC fragments
used in (4), but far stronger than PA = Peano Arithmetic or finite set
theory. In this category are various countably infinite combinatorial
theorems such as Kruskal's Tree Theorem and the Graph Minor Theorem in
what is called wqo (well quasi order) theory. The use of the
uncountable is known to be necessary. In most of the cases, there are
natural finite forms which have the same logical status. These natural
finite forms are AE statements, with known explosively huge associated
growth rates. This is much more threatening than (4) in content, but
much less threatening in terms of the level of independence.

(6) Independence of statements involving only countable sets, with
associated finite forms, requiring reasoning beyond finite set theory.
This category includes results such as Goldstein's Theorem,
non-losability of the Kirby-Paris hydra game, Paris/Harrington Ramsey
Theorem, Adjacent Ramsey Theorems, and Regressive Value Theorems.
These statements are just beyond the PA or finite set theory level.
The first two are in AE form,
and the last three involve countable sets, with natural associated
finite forms also in AE form, with explosive growth rates. This is
generally not as threatening as (5), with the initial results
predating (5).

(7) Independence of statements involving only countable sets, with
associated finite forms, requiring reasoning far beyond ZFC. These are
proved only by using large cardinal hypotheses. The associated finite
forms are provably equivalent to the infinite forms, and are in A
form. The A form is much more threatening than the AE forms in (5),
(6). The results have been announced recently in Large Cardinals and
Emulations/1-29. Although these independent statements were not
previously considered by mathematicians, Friedman claims that they are
sufficiently simple and compelling as to be inevitable. It is too
early to evaluate Friedman's claim. Potentially this category is very
threatening. However, at the moment, the relevance of the statements
to computational complexity theory is remote.

Harvey Friedman