[FOM] 646: Philosophy of Incompleteness 1
Harvey Friedman
hmflogic at gmail.com
Tue Nov 24 17:19:46 EST 2015
First we correct two typos in
http://www.cs.nyu.edu/pipermail/fom/2015-November/019358.html There
are two occurrences of k-+5, These should be k+.5.
#############################
I want to present an overview of what has and what has not been
achieved in Incompleteness, and its role in the foundations of
mathematics generally.
The standard foundations of mathematics we generally accept today emerged
after
1. Frege's work on what we now call first order predicate calculus
with equality.
2. Zermelo's work on what we now call Zermelo set theory.
3. Frankel's additional axiom, resulting in what we now call Zermelo
Frankel set theory with the axiom of choice, or ZFC.
Since I am going to be focusing on Incompleteness, I am not going to
talk about a number of important issues surrounding 1-3, here.
However, just to put matters in some context, let me mention some
important matters connected with 1-3 that I do intend to talk about
elsewhere - but not here:
a. There is crucial intervening work as 1-3 emerged, including,
Bolzano, Weierstrass, Cauchy and others with epsilon/delta, and Cantor
with set theory.
b. There are alternative foundational schemes being offered, such as
constructivity, nonstandard analysis, category theory, and new forms
of category theory. All four of these can be developed, and often are
developed, totally within the standard ZFC framework. However, some
offer them up as alternative self contained foundations.
c. There are important fragments of ZFC that are responsive to the
"portions" of ZFC that are actually used in various mathematical
contexts - e.g., Reverse Mathematics, and Strict Reverse Mathematics.
d. Other important issues.
Not too long after the roughly 1920 emergence of ZFC, Completeness and
Incompleteness became the centerpiece of the great era in the
foundations of mathematics, led by Kurt Goedel.
4. The Completeness of first order predicate calculus with equality
(1930)
.
5. The First and Second Incompleteness Theorems
(1931)
. This is
currently formulated as Concrete General Incompleteness, even though
Goedel did not explicitly propose formulations involving general
formal systems.
6. The Relative Consistency of ZFC + GCH
(1938)
. This is the beginning
of Set Theoretic Mathematical Incompleteness.
7. Considerably later, the 1962 Relative Consistency of ZFC + not CH, by
Cohen.
1-6 propelled the foundations of mathematics, or f.o.m., into a
subject of singular general intellectual interest. In terms of g.i.i.,
it arguably transcended other developments in mathematics and
philosophy in the first half of the 20th century. This perhaps
controversial assessment has been shared by others. Notably, Morris
Kline, in his monumental Mathematics from Ancient to Modern Times,
OUP, 1972, wrote in his last chapter, number 51, titled The
Foundations of Mathematics,
"By far the most profound activity of twentieth-century mathematics
has been the research on the foundations." - page 1182.
After 1-6, there was a decline from this Golden Age of f.o.m.,
naturally coinciding with the aging of Kurt Goedel (who did, however,
continue with important work on Functional Interpretations and General
Relativity).
With 7, there was a revitalization of f.o.m., with the work of Cohen.
Set Theoretic Mathematical Incompleteness was now off the ground and
running fast with Cohen's forcing technique.
Also, by this time, there had developed a pretty clear conception of
what we call mathematical logic, which should be distinguished from
foundations of mathematics.
Mathematical logic emerged as a branch of mathematics that studies the
basic mathematical structures that grew out of developments in f.o.m.
These structures are studied in mathematical logic for their own sake,
independently of any foundational issues or aims. The four main
divisions are model theory, proof theory, recursion theory, and set
theory.
I was a student at MIT from 9/1964 through 8/1967. I graduated with a
PhD and took an Assistant Professorship in Philosophy at Stanford. in
9/1967.
During that period, there were two problems that were being generally
discussed as the biggest in mathematical logic and f.o.m.
A. Hilbert's Tenth Problem. It had been known for some time that the
solvability in integers of exponential Diophantine equations (integer
coefficients) is algorithmically unsolvable (Davis, Putnam). Whether
this is the case for (polynomial) Diophantine equations (integer
coefficients) was unknown. Also solvability of (polynomial)
Diophantine equations (integer coefficients) over the rationals.
B. Is there a sentence in number theory or finite mathematics that is
independent of ZFC?
With regard to A, Algorithmic Unsolvability had a development that is
in some ways parallel to that of Incompleteness. The setup is credited
to Alan Turing, with his Turing machine model for algorithms. The
original Algorithmic Undecidability of the Halting Problem roughly
corresponds conceptually to General Concrete Incompleteness, although
much more is going on with Second Incompleteness. Mathematical
Algorithmic Undecidability got off the ground in finitely presented
groups and homeormorphisms of manifolds. See, e.g.,
http://www-math.mit.edu/~poonen/slides/cantrell3.pdf By 1970, Number
Theoretic Algorithmic Undecidability got off the ground with a long
series of developments, Davis, Putnam, J. Robinson, Matiyasevich, by
1970. When I was a student discussing A with people, David and Putnam
had shown Algorithmic Undecidability for exponential Diophantine
equations over the integers.
With regard to B, I remember that people did realize that there was no
obvious candidate for such Incompleteness. This was in sharp contrast
to the situation in Set Theoretic Mathematical Incompleteness, with
obvious candidates in light of Goedel's 1938 work.
When I graduated in 1967. Set Theoretic Mathematical Incompleteness
was already highly developed, led by Robert Solovay.
Yet it was clear to all at the time that the hugely successful methods
driving Set Theoretic Mathematical Incompleteness were not going to be
adaptable to B.
It was also clear that during the 1960's after Cohen's 1962
breakthrough, that the special g.i.i. status of mathematical logic and
f.o.m. had at least partly recovered. This partial recovery of g.i.i.
was driven by the work on Incompleteness.
By the time I graduated from MIT in 1967, I made a commitment to what
I now call Concrete Mathematical Incompleteness as the natural
continuation of Incompleteness from the g.i.i. perspective. I had this
perspective even though there was an important missing element
compared to Set Theoretic Mathematical Incompleteness. Namely, the
utter lack of a promising example to work on. I.e., the obvious
examples suggested by Goedel's work on the axiom of choice and the
continuum hypothesis. I will be referring to this as "no compelling
targets".
This sets the stage for a discussion of a number of topics, including these:
i. How does one go about developing Concrete Mathematical
Incompleteness without compelling targets? What criteria for success
makes sense for Concrete Mathematical Incompleteness?
ii. What has been achieved with Concrete Mathematical Incompleteness?
iii. What prospects are there for future Concrete Mathematical
Incompleteness?
iv. What in mathematical logic and f.o.m. has, besides Incompleteness,
had significant g.i.i? What future developments would have significant
g.i.i,?
v. Elaboration on the g.i.i. = general intellectual interest concept,
and how it can be used to drive research.
But to limit the scope of the discussion in this series, I will try to
mostly stay focused on Incompleteness.
**********************************************************
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 645th 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-599 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2015-August/018887.html
600: Removing Deep Pathology 1 8/15/15 10:37PM
601: Finite Emulation Theory 1/perfect? 8/22/15 1:17AM
602: Removing Deep Pathology 2 8/23/15 6:35PM
603: Removing Deep Pathology 3 8/25/15 10:24AM
604: Finite Emulation Theory 2 8/26/15 2:54PM
605: Integer and Real Functions 8/27/15 1:50PM
606: Simple Theory of Types 8/29/15 6:30PM
607: Hindman's Theorem 8/30/15 3:58PM
608: Integer and Real Functions 2 9/1/15 6:40AM
609. Finite Continuation Theory 17 9/315 1:17PM
610: Function Continuation Theory 1 9/4/15 3:40PM
611: Function Emulation/Continuation Theory 2 9/8/15 12:58AM
612: Binary Operation Emulation and Continuation 1 9/7/15 4:35PM
613: Optimal Function Theory 1 9/13/15 11:30AM
614: Adventures in Formalization 1 9/14/15 1:43PM
615: Adventures in Formalization 2 9/14/15 1:44PM
616: Adventures in Formalization 3 9/14/15 1:45PM
617: Removing Connectives 1 9/115/15 7:47AM
618: Adventures in Formalization 4 9/15/15 3:07PM
619: Nonstandardism 1 9/17/15 9:57AM
620: Nonstandardism 2 9/18/15 2:12AM
621: Adventures in Formalization 5 9/18/15 12:54PM
622: Adventures in Formalization 6 9/29/15 3:33AM
623: Optimal Function Theory 2 9/22/15 12:02AM
624: Optimal Function Theory 3 9/22/15 11:18AM
625: Optimal Function Theory 4 9/23/15 10:16PM
626: Optimal Function Theory 5 9/2515 10:26PM
627: Optimal Function Theory 6 9/29/15 2:21AM
628: Optimal Function Theory 7 10/2/15 6:23PM
629: Boolean Algebra/Simplicity 10/3/15 9:41AM
630: Optimal Function Theory 8 10/3/15 6PM
631: Order Theoretic Optimization 1 10/1215 12:16AM
632: Rigorous Formalization of Mathematics 1 10/13/15 8:12PM
633: Constrained Function Theory 1 10/18/15 1AM
634: Fixed Point Minimization 1 10/20/15 11:47PM
635: Fixed Point Minimization 2 10/21/15 11:52PM
636: Fixed Point Minimization 3 10/22/15 5:49PM
637: Progress in Pi01 Incompleteness 1 10/25/15 8:45PM
638: Rigorous Formalization of Mathematics 2 10/25/15 10:47PM
639: Progress in Pi01 Incompleteness 2 10/27/15 10:38PM
640: Progress in Pi01 Incompleteness 3 10/30/15 2:30PM
641: Progress in Pi01 Incompleteness 4 10/31/15 8:12PM
642: Rigorous Formalization of Mathematics 3
643: Constrained Subsets of N, #1 11/3/15 11:57PM
644: Fixed Point Selectors 1 11/16/15 8:38AM
645: Fixed Point Minimizers #1 11/22/15 7:46PM
Harvey Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20151124/ec16d38e/attachment-0001.html>
More information about the FOM
mailing list