[FOM] 740: Philosophy of Incompleteness/2
Harvey Friedman
hmflogic at gmail.com
Sat Jan 7 08:33:06 EST 2017
NOTE: I MISNUMBERED THIS POSTING AS 739 AND TO AVOID CONFUSION, THIS
IS A RESUBMISSION UNDER THE CORRECT NUMBER 740. SORRY FOR THE
CONFUSION.
Some time ago, I authored the posting 646: Philosophy of Incompleteness 1,
http://www.cs.nyu.edu/pipermail/fom/2015-November/019360.html
I didn't follow through on an anticipated thread where I was planning
to discuss issues about Incompleteness, especially where we are, where
we are going, and where we could be going in the future. I didn't
follow through on this thread.
But Aaronson's Summary of Incompleteness
http://www.cs.nyu.edu/pipermail/fom/2017-January/020215.html can be
viewed as being in the category of some sort of followup. I wanted to
amplify on some points there, and this made me think of reactivating
the thread.
Aaronson has already revised his Summary in the direction I proposed
(not entirely). Here is his revised public version,
http://www.scottaaronson.com/papers/pnp.pdf and my suggestions for
further revisions as I just wrote to him:
(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.
FINE
(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 state- ments can’t be phrased 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.
FINE
(3) Independence from ZF set theory of various statements involving
metric spaces and measure theory—many of which can nevertheless be
proven if one assumes the existence of a suitable large cardinal. (In
other cases, such as the so-called Borel determinacy theorem [173],
the statement can be proven in ZF, but one really does need close to
the full power of ZF [94].) These statements, while different from
those in class (2), are open to the same objection: namely, that
they’re about uncountable sets, so their independence seems less
“threatening” than that of purely arithmetical statements.
CHANGE ZF THRICE TO ZFC. SCOTT - the ones that can be proven with
large cardinals and independent of ZFC involve the so called
projective hierarchy. So here is a rewrite:
(3) Independence from ZFC set theory of various statements involving
metric spaces, measure theory, and projective sets. The statements
about projective sets can nevertheless be proven if one assumes the
existence of a suitable large cardinal. (In other cases, SAME.
(4) Independence from “weak” systems, which don’t encompass all
accepted mathematical rea- soning. Goodstein’s Theorem [105], and the
non-losability of the Kirby-Paris hydra game [147], 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. The cele- brated Robertson-Seymour Graph Minor Theorem
(see [83]), while not strictly arithmetical (since it quantifies over
infinite lists of graphs), is another example of an important result
that can be proven using ordinal induction, but that provably can’t be
proven using axioms of similar strength to Peano arithmetic. For more
see Friedman, Robertson, and Seymour [95].
FINE
(5) Independence from ZF set theory of strange combinatorial
statements. Harvey Friedman [96] has produced striking examples of
such statements, which he claims are “natural” (i.e., they might
eventually have been studied even if not for their independence from
set theory), but there’s no consensus on that question. In any case,
the relevance of Friedman’s statements to computational complexity is
remote at present.
REWRITE:
(5) Independence from ZFC set theory of unusual combinatorial
statements. Harvey Friedman [96] has produced striking examples of
such statements, which he claims are "perfectly natural". In
particular, that they would appear in the expected future development
of normal mathematics without Friedman. There is no consensus on such
claims yet. In any case, the relevance of Friedman’s statements to
computational complexity is remote at present.
Scott - perfectly natural implies that they would appear in the ....,
but not vice versa. Perfect Naturalness, according to me, has its own
meaning and logic, independently of what humans actually do. Also
"strange" is too pejorative in this context, and "unusual" is much
nicer.
In http://www.cs.nyu.edu/pipermail/fom/2017-January/020215.html we
have already pointed two main discussions of mine on the status of
Incompleteness - one from the Introduction to the BRT book, and one
from my paper in the Templeton Goedel Volume Horizons of Truth.
Another source is the posting PA Incompleteness/1
http://www.cs.nyu.edu/pipermail/fom/2016-September/020083.html Another
thread that I anticipated and have yet to follow through with.
I now want to focus on crucial strategic issues. There is a kind of
Incompleteness that is so dramatically compelling, that it virtually
overwhelms any discussion of its merits.
A. An existing mathematical question that is widely known and of wide
interest, is shown to be neither provable nor refutable in ZFC.
The best approximate to A that we have, probably by a wide margin, is
CH = continuum hypothesis. There are other examples that may be more
directly connected with mathematical practice, but how well known, how
wide the interest, drops significantly from CH.
Even CH can be argued not to meet the high standard of A. Although
widely known, it can be argued that CH is not of wide interest. Bear
in mind that I am speaking about today. It would appear that the
interest in CH was probably wider say, in the period 1900-1950. But
nowadays the interest in CH is rather limited. It is generally viewed
as in some sort of intangible realm where pathology and lack of
tangible mathematical structure dominate.
It also appears that the fact that CH is neither provable nor
refutable from ZFC actually lowers the interest in CH. In fact, many
set theorists are of the opinion that once a statement is shown to be
neither provable nor refutable in ZFC, the interest in it wanes
considerably.
My own view is that the mere independence from ZFC is not nearly
sufficient to lower the interest. Rather, it is really a reinforcing
factor among other factors that leads to a sharp decline of interest
in a statement. In the case of CH, and just about all intensely "set
theoretic" statements, the independence from ZFC reinforces the view
mentioned above, that it lives in some sort of intangible realm where
pathology and lack of tangible mathematical structure dominate.
Nevertheless the idea that mathematical questions that are widely
known can be independent of ZFC is definitely of substantial interest
to a wide variety of mathematicians and thinkers with mathematical
interests. For most (pure) mathematicians, the idea that the rules of
the game are engraved in stone and don't need to be revisited, so that
mathematics is a matter of purely skillful deep quantifiable effort,
not social engineering or political machinations, immune to devious
tampering and backroom deals, is deeply ingrained in the very reason
that they chose (pure) mathematics in the first place. So
Incompleteness as in A above, is potentially deeply disturbing for
such people.
Now A as stated has not really been achieved by CH nor anything else,
at least not yet. I view the prospects for A as rather poor say before
2100, after which I will not be actively involved. For instance, I
confess as spending absolutely no time whatsoever trying to prove the
independence from ZFC of RH or that e+pi is irrational or Twin Prime
or Goldbach, and the like. And a nonzero but very limited amount of
time for proving independence of computational complexity questions.
So what else is there to do, other than A?
Before getting into this, I want to digress and talk about an effort
to completely stamp out independence from ZFC.
There is a method for completely stamping out independence from ZFC
that has been conjectured to work perfectly for the entire literature
of statements stated by core mathematicians which live in the first
omega+omega levels of the cumulative hierarchy. Almost all of these
statements live there anyway, and even for ones that don't live there,
this applies to almost all of those. The only exceptions are
statements that at least in effect state the existence of a strong
inaccessible or weak inaccessible cardinality, say in Grothendieck
Universes.
This method is of course to use the hypothesis V = L. That all sets
are constructible. That all sets are built up by some particular
explicit transfinite process.
Now before we get into the merits and demerits of this method, let's
discuss the following question. V = L is rather uncomfortably
complicated taken as a mathematical statement, even if its strategic
idea is rather transparent (explicit transfinite processes).
THIS POSTING IS LONG ENOUGH, so I will stop here.
************************************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 740th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-699 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/
700: Large Cardinals and Continuations/14 8/1/16 11:01AM
701: Extending Functions/1 8/10/16 10:02AM
702: Large Cardinals and Continuations/15 8/22/16 9:22PM
703: Large Cardinals and Continuations/16 8/26/16 12:03AM
704: Large Cardinals and Continuations/17 8/31/16 12:55AM
705: Large Cardinals and Continuations/18 8/31/16 11:47PM
706: Second Incompleteness/1 7/5/16 2:03AM
707: Second Incompleteness/2 9/8/16 3:37PM
708: Second Incompleteness/3 9/11/16 10:33PM
709: Large Cardinals and Continuations/19 9/13/16 4:17AM
710: Large Cardinals and Continuations/20 9/14/16 1:27AM
700: Large Cardinals and Continuations/14 8/1/16 11:01AM
701: Extending Functions/1 8/10/16 10:02AM
702: Large Cardinals and Continuations/15 8/22/16 9:22PM
703: Large Cardinals and Continuations/16 8/26/16 12:03AM
704: Large Cardinals and Continuations/17 8/31/16 12:55AM
705: Large Cardinals and Continuations/18 8/31/16 11:47PM
706: Second Incompleteness/1 7/5/16 2:03AM
707: Second Incompleteness/2 9/8/16 3:37PM
708: Second Incompleteness/3 9/11/16 10:33PM
709: Large Cardinals and Continuations/19 9/13/16 4:17AM
710: Large Cardinals and Continuations/20 9/14/16 1:27AM
711: Large Cardinals and Continuations/21 9/18/16 10:42AM
712: PA Incompleteness/1 9/2316 1:20AM
713: Foundations of Geometry/1 9/24/16 2:09PM
714: Foundations of Geometry/2 9/25/16 10:26PM
715: Foundations of Geometry/3 9/27/16 1:08AM
716: Foundations of Geometry/4 9/27/16 10:25PM
717: Foundations of Geometry/5 9/30/16 12:16AM
718: Foundations of Geometry/6 101/16 12:19PM
719: Large Cardinals and Emulations/22
720: Foundations of Geometry/7 10/2/16 1:59PM
721: Large Cardinals and Emulations//23 10/4/16 2:35AM
722: Large Cardinals and Emulations/24 10/616 1:59AM
723: Philosophical Geometry/8 10/816 1:47AM
724: Philosophical Geometry/9 10/10/16 9:36AM
725: Philosophical Geometry/10 10/14/16 10:16PM
726: Philosophical Geometry/11 Oct 17 16:04:26 EDT 2016
727: Large Cardinals and Emulations/25 10/20/16 1:37PM
728: Philosophical Geometry/12 10/24/16 3:35PM
729: Consistency of Mathematics/1 10/25/16 1:25PM
730: Consistency of Mathematics/2 11/17/16 9:50PM
731: Large Cardinals and Emulations/26 11/21/16 5:40PM
732: Large Cardinals and Emulations/27 11/28/16 1:31AM
733: Large Cardinals and Emulations/28 12/6/16 1AM
734: Large Cardinals and Emulations/29 12/8/16 2:53PM
735: Philosophical Geometry/13 12/19/16 4:24PM
736: Philosophical Geometry/14 12/20/16 12:43PM
737: Philosophical Geometry/15 12/22/16 3:24PM
738: Philosophical Geometry/16 12/27/16 6:54PM
739: Philosophical Geometry/17 1/2/17 11:50PM
Harvey Friedman
More information about the FOM
mailing list