[FOM] 570: Philosophy of Incompleteness 1

[Harvey Friedman]

Before getting into the Philosophy of Incompleteness, I want to make a
slight change in terminology for the last posting #569
http://www.cs.nyu.edu/pipermail/fom/2015-January/018489.html. I wrote

PROPOSITION 1. Let n > k >= 1 and V be a set of k linear inequalities
in k variables with coefficients from {-k,...,k}. There exists three
sets A containedin B containedin C between {0,(8k)!^0,...,(8k)!^n} and
{0,...,(8k)!^(n+1)}, such that
i. Any k-sum from A lies in B if and only if it has no V decomposition from B.
ii. Any k-sum from B lies in C if and only if it has no V
decomposition from C.

I now prefer to write the same thing this way:

PROPOSITION 1. Let n > k >= 1 and V be a set of k linear inequalities
in k variables with coefficients from {-k,...,k}. There exists three
sets A containedin B containedin C between {0,(8k)!^0,...,(8k)!^n} and
{0,...,(8k)!^(n+1)}, such that
i. Any k-sum from A lies in B if and only if it is not a proper V sum from B.
ii. Any k-sum from B lies in C if and only if it is not a proper V sum from C.

Here a V sum is a sum where the terms obey V. A proper V sum is a V
sum where there are at least two nonzero terms.

If we just use A containedin B and clause i, then the Proposition is
provable in EFA. I.e.,

THEOREM. Let n > k >= 1 and V be a set of k linear inequalities
in k variables with coefficients from {-k,...,k}. There exists two
sets A containedin B between {0,(8k)!^0,...,(8k)!^n} and
{0,...,(8k)!^(n+1)}, such that any k-sum from A lies in B if and only
if it is not a proper V sum from B.

************************************

By far, the most well known, the most generally understandable, and
the most highly respected, outcome of what is generally considered to
be mathematical logic, is the work in Incompleteness, and secondarily,
the work in Algorithmic Unsolvability. In fact, the two are often
confused by non experts. Initial encounters with Incompleteness often
have a profound impact on mathematicians and some theoretical
scientists, as it causes them to reassess their fundamental attitudes
toward objective truth in mathematics. Generally speaking, this almost
magical effect of Incompleteness rapidly wears off. The reasons for
this disengagement are usually not consciously formulated. But they
surround a general realization that there are crucial qualitative
differences between the examples of Incompleteness and the mathematics
involved in their teaching and research.

There are other foundationally important outcomes of mathematical
logic, such as the Completeness Theorem and fundamental decision
procedures (especially for elementary algebra and geometry), but these
are much less well known. In particular, they do not have anything
like the at least fleeting magical effect of Incompleteness.

Incompleteness, in its modern sense, is generally credited to Kurt
Goedel. But every great idea has roots that often go back to ancient
times. Incompleteness is no exception. Perhaps the ancient root of
Incompleteness appears in the famous equation

x^2 = 2.

In modern terms,

(therexists x)(x^2 = 2)

is neither provable nor refutable with the ordered field axioms. A
more elaborate but related Incompleteness surrounds the fifth degree
equation and ordered field axioms augmented with n-th roots
(radicals). Another famous example of Incompleteness involves the
parallel postulate in geometry.

There is, however, a radical new element in Goedel Incompleteness. The
examples of Incompleteness are sentences that are neither provable nor
refutable in the usual axiomatizations for ALL of mathematics.

Actually, Goedel originally used only a fragment of the usual
axiomatization for all of mathematics, but the work easily generalizes
(Goedel knew this). Even if only Peano Arithmetic is used,
corresponding to Finite Mathematics, or Finite Set Theory, the system
is obviously general purpose in a way that ordered fields and
geometries are not.

I was a student at MIT during 1964-1967, and I became immersed in
Goedel Incompleteness. I saw Goedel Incompleteness in these major
forms:

1. Goedel's First and Second Incompleteness Theorems.
2. AxC not refutable in ZF (Goedel).
3. CH not refutable in ZFC (Goedel).
4. AxC not provable in ZF (Cohen).
5. CH not provable in ZFC (Cohen).

All of these results created brief sensations in the mathematics
community. Yet, in the mathematics community, the great excitement
quickly died down to mere normal respect for high achievement. Over
time, less than even that in some significant circles. As far as
mathematics is concerned, a colleague of mine here conducted an
informal survey among Princeton Mathematics Professors, as to where
Kurt Goedel would rank as a mathematician of the 20th century. The
colleague reported to me that the consensus among the Princeton
Mathematics Department faculty was that Kurt Goedel would be on the
border of 100th. To be fair to the Princeton Mathematics Professors,
they may have answered differently if the category was not
"mathematician" but instead "mathematical thinker". But this modified
informal survey was not conducted (by my colleague).

Sitting here in 2015, I think I can formulate some factors that help
explain why the magic quickly wears off.

a. For the vast majority of mathematicians, there has been no
discernible path of Incompleteness examples pointing in the direction
of the mathematics that they are concerned with, in teaching or
research. Whereas there has been a path of further Incompleteness, the
path has clearly pointed elsewhere.

b. The above results do not interact with actual computation. Nor do
subsequent results point in that direction. This is obvious in the
case of 2-5. The Pi01 forms in 1 are not sufficient, partly due to
subject matter, and partly due to sharp contrasts with standard
computational situations.

c. Mathematicians may have heard of some long term concerted effort by
some eccentric logician in the middle of nowhere working on his own -
to do something radically different with Incompleteness for many
decades. But the last time they looked at anything coming out of this,
it looked ad hoc and artificial. Also the math logic community had
lost interest in the effort decades ago. Besides, the idea is that
anybody who tries that long to do something that ambitious,
particularly in mathematics, is almost certainly going to fail. So
there is no point in following this effort. In addition,
mathematician's generally are not looking for trouble (foundational
difficulties), and are rather more comfortable with the idea that this
eccentric logician in the middle of nowhere working on his own is
failing to do anything interesting or relevant.

Whereas the attitude that Incompleteness is not pointing to a
particular mathematician's concerns can be seriously questioned as
hopelessly narrow minded and egocentric, one cannot similarly dismiss
the disconnection of Incompleteness with actual computation. The
disconnect between Incompleteness and actual computation is in fact a
thoroughly fatal gap. Given the obvious computational path being
followed by mathematics and science generally, continuing failure to
deal with this gap threatens to make Incompleteness a mere historical
relic.

Another way of looking at the special significance of Concrete
Mathematical Incompleteness at the computational level is this. In
physical science, there is a special focus on theory that has direct
observational consequences that are capable of refuting the theory. In
mathematics, this basically forces us into the computational.

NOTE: Perhaps this does not entirely force us into the computational.
I am thinking of soap bubble experiments - for minimal surface theory.
Running a soap bubble experiment by dipping a shaped wire into a
solution and seeing what results, does not appear to be analogous to
the operation of a computer. Yet it is arguably a form of
incontrovertible observation. So it appears that minimal surfaces/soap
bubbles could be a rich topic for foundations of mathematics.

An important issue here is to analyze just how mathematical reasoning
that lies beyond the directly computational can be tested to make
substantive predictions about the actual computational. This is an
important foundational matter independent of Incompleteness.

OBSERVATIONAL CONSEQUENCES OF HIGHER MATHEMATICS

My favorite example of this isn't very "high". It is just above the
actual computational. I haven't thought about this systematically, and
I certainly don't want to now jump all the way to my recent work that
does give - or promises to give - observational consequences of the
most extremely high mathematics, and is intimately connected with
Incompleteness.

So let's start the discussion of this with the ever so slightly "high".

THEOREM. The five most common suit distributions of 13 card bridge
hands are the following:
4432   22.5512%
5332   15.5168%
5431   12.9307%
5422   10.5797%
4333   10.5361%

good to the last decimal place shown.

Now I am surmising that the above was proved rigorously first using
elementary combinatorics to derive exact percentages, and then
rounding off with a calculator. My source is

Official Encyclopedia of Bridge, ACBL, fifth edition, Mathematical
Tables, page 277.

Incidentally I noticed this reference on Wikipedia, with Emile Borel involved:

Émile, Borel; André, Chéron (1940). Théorie Mathématique du Bridge.
Gauthier-Villars. Second French edition by the authors in 1954.
Translated and edited into English by Alec Traub as The Mathematical
Theory of Bridge; printed in 1974 in Taiwan through the assistance of
C.C. Wei.

Now obviously one cannot fully verify the above Theorem by computer.
However, one can easily run trials using practical random number
generators observing the relative frequencies in the expected way.

So it is clear that there is some deep directly observable
consequences of the above Theorem. These directly observable
consequences can also be viewed as physically meaningful statements.
I.e., the computer as a physical device. Of course, in some sense,
there is only a core interaction with physics (hardware behavior),
with an outer shell of something more general than physics (math). But
nevertheless, here we have a place where

Mathematics Meets Physical Reality

where the Theory is that of abstract mathematics - elementary
combinatorics, with its inductions, recursions, bijections, etcetera.
And also, elementary statistics is very much in play here as well, and
also adds greatly to the deep foundational mix here.

This entire situation is very rich foundationally, involving
Ultrafinitism and foundational issues in probability and statistics.

But what about other Really Good Observational Consequences of Higher
Mathematics? E.g., ones that are disentangled from probability and
statistics?

We would like to stay within a space of roughly 52! elements. E.g.,
the positive integers <= 52!. This number counts the permutations of a
52 card deck, and these permutations are very real world familiar.

If we want to take out the probability/statistics, then we come to
universal statements quantifying over {1,...,52!} or variants such as
the set of permutations of {1,...,52}. These can be viewed as
predicting the positive outcome resulting from any appropriate input.

Higher Mathematics proves that a^3 + b^3 = c^3 has no solution for 1
<= a,b,c <= 52!. Here Higher Mathematics again meets physical reality.
Instances can be confirmed easily using computing devices that add and
multiply the relevant numbers, which don't have that many digits.

This does also suggest a very basic place where Higher Mathematics
meets physical reality. Namely, in the addition and multiplication
algorithms for exact arithmetic with not very many digits.

But how do we verify that the addition and multiplication devices are
correct? We can look for consistencies. This amounts to bringing in
the commutative, associative, and distributive laws for numbers with
not too many digits. This is also a low form of High mathematics.

It would be interesting to analyze a substantial inventory of
fundamental Higher Mathematics applied to {1,2,...,52!} or equivalent,
that meets physical reality in various senses.

I'll close here with the following intriguing example: every even
element of {1,...,52!} is the sum of two primes. To have this meet
physical reality, one has to examine actual primality testing. There
are fast testers using Monte Carlo, and there are slower testers that
don't. Both use Higher Mathematics. I don't know where the slower
testers break down at the practical level - below 52! or below 100! or
where? Experts surely can answer this for us. And we still have to
tell whether a given even number in the relevant range is in fact the
sum of two primes. So exactly how well Higher Mathematics meets
physical reality in the case of Goldbach's Conjecture needs some
careful discussion.

I'll really close here with the mentioning of another deep situation
with rich foundational overtones. That is, examples of statements from
the usual chess. Not only do we have counting theorems, but also there
is the game theory of usual chess. I won't go into this 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 570th 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-527 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2014-August/018092.html

528: More Perfect Pi01  8/16/14  5:19AM
529: Yet more Perfect Pi01 8/18/14  5:50AM
530: Friendlier Perfect Pi01
531: General Theory/Perfect Pi01  8/22/14  5:16PM
532: More General Theory/Perfect Pi01  8/23/14  7:32AM
533: Progress - General Theory/Perfect Pi01 8/25/14  1:17AM
534: Perfect Explicitly Pi01  8/27/14  10:40AM
535: Updated Perfect Explicitly Pi01  8/30/14  2:39PM
536: Pi01 Progress  9/1/14 11:31AM
537: Pi01/Flat Pics/Testing  9/6/14  12:49AM
538: Progress Pi01 9/6/14  11:31PM
539: Absolute Perfect Naturalness 9/7/14  9:00PM
540: SRM/Comparability  9/8/14  12:03AM
541: Master Templates  9/9/14  12:41AM
542: Templates/LC shadow  9/10/14  12:44AM
543: New Explicitly Pi01  9/10/14  11:17PM
544: Initial Maximality/HUGE  9/12/14  8:07PM
545: Set Theoretic Consistency/SRM/SRP  9/14/14  10:06PM
546: New Pi01/solving CH  9/26/14  12:05AM
547: Conservative Growth - Triples  9/29/14  11:34PM
548: New Explicitly Pi01  10/4/14  8:45PM
549: Conservative Growth - beyond triples  10/6/14  1:31AM
550: Foundational Methodology 1/Maximality  10/17/14  5:43AM
551: Foundational Methodology 2/Maximality  10/19/14 3:06AM
552: Foundational Methodology 3/Maximality  10/21/14 9:59AM
553: Foundational Methodology 4/Maximality  10/21/14 11:57AM
554: Foundational Methodology 5/Maximality  10/26/14 3:17AM
555: Foundational Methodology 6/Maximality  10/29/14 12:32PM
556: Flat Foundations 1  10/29/14  4:07PM
557: New Pi01  10/30/14  2:05PM
558: New Pi01/more  10/31/14 10:01PM
559: Foundational Methodology 7/Maximality  11/214  10:35PM
560: New Pi01/better  11/314  7:45PM
561: New Pi01/HUGE  11/5/14  3:34PM
562: Perfectly Natural Review #1  11/19/14  7:40PM
563: Perfectly Natural Review #2  11/22/14  4:56PM
564: Perfectly Natural Review #3  11/24/14  1:19AM
565: Perfectly Natural Review #4  12/25/14  6:29PM
566: Bridge/Chess/Ultrafinitism 12/25/14  10:46AM
567: Counting Equivalence Classes  1/2/15  10:38AM
568: Counting Equivalence Classes #2  1/5/15  5:06AM
569: Finite Integer Sums and Incompleteness  1/515  8:04PM

Harvey Friedman