[FOM] 517: New Concrete Mathematical Incompleteness
Harvey Friedman
hmflogic at gmail.com
Fri Aug 2 21:57:52 EDT 2013
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
*****************************************
In posting 516:Embedded Maximal Cliques/restatement
http://www.cs.nyu.edu/pipermail/fom/2013-May/017291.html
I reported on an extended abstract on my website
http://www.math.osu.edu/~friedman.8/manuscripts.html :
76. Embedded Maximal Cliques and Incompleteness. Extended Abstract.
18 pages. May 20, 2013. Reesults supersede 71. Largely supersedes 72,
November 6, 2012, but some matters from 72 are not addressed in this
new version, and so we are keeping 72.
This has now been upgraded with a new extended abstract on
http://www.math.osu.edu/~friedman.8/manuscripts.html :
77. Sum Base Towers, Invariant Maximal Continuations, and Concrete
Incompleteness. Extended abstract. 48 pages. August 2, 2013. 76 is
incorporated as a small part. Some matters in 76 not covered here, so
we are keeping 76. Look for dated updates. I will normally remove
earlier versions, with an indication as to what's new.
Given the scope of 77, expect that there will be periodic revisions,
and I normally will not keep earlier versions unless the revision is
major - like this one. However, with significant revisions, I will
make a numbered FOM posting discussing the latest change. I will be
careful to date everything.
FROM THE MANUSCRIPT:
Abstract. In this extended abstract, we present an account
of new examples of concrete mathematical statements that
can be proved from large cardinal hypotheses but not in the
usual ZFC axioms for mathematics (assuming ZFC is
consistent). Many of the statements are provably equivalent
to Pi01 sentences (purely universal statements, logically
like FLT) - in particular the consistency (not the 1-
consistency) of strong set theories. Some are in explicitly
Pi01 form. The examples are thematic, and fall into two major
groups. The first is sum base towers, which are of finite
length, made up of sets of positive integers (both finite
and infinite sets are treated). These basic objects are
motivated through an analogy with elements in physical
science. They are related to towers in Boolean Relation
Theory, but are more concrete and combinatorial, and
involve only the ordering of Z+ and addition on Z+. We
present a substantial theory of sum base towers for both
arbitrary R containedin Z+k and tame R containedin Z+k. Tameness here is taken
to mean integral piecewise linear relations or the more
extensive Presburger relations. These substantial theories
cannot be carried out in ZFC, but can be carried out using
certain large cardinal hypotheses, represented by the SRP
axiom system. If unrestricted R containedin Z+k are used then the
results are mostly equivalent to 1-Con(SRP), and often have
simple Pi02 or Pi03 forms. If tame R containedin Z+k are used then the
results are mostly equivalent to Con(SRP), and often have
simple Pi01 forms. The second major group of examples lives
in the rationals, with only order. The basic shape of the
results assert that any finite set of negative rational
vectors has a "maximal continuation" which is invariant
under certain shift operators (they add 1 to only some
coordinates, leaving others fixed). These and many other
statements are shown to be provably equivalent to the
widely believed Con(SRP), and hence unprovable in ZFC
(assuming ZFC is consistent). Modifications are made to
"maximal continuations" which allow for stronger invariance
properties. One version is particularly strong, and a
simple cross sectional condition is added which propels the
statement beyond the huge cardinal hierarchy to be
equivalent to Con(HUGE). Another kind of weakening of
maximality which we call source maximality, supports a
series of finite source maximal continuations of a negative
set of rational vectors. These are explicitly Π02 and become
explicitly Π01 because a relevant and easy exponential type
bound. This also applies to statements corresponding to
Con(HUGE). We also present some nondeterministic
constructions of infinite and finite length with the same
metamathematical properties. These lead to practical
computer investigations designed to provide arguable
confirmation of Con(ZFC) and more.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 516th 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-449 can be found
in the FOM archives at
http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html
450: Maximal Sets and Large Cardinals II 12/6/10 12:48PM
451: Rational Graphs and Large Cardinals I 12/18/10 10:56PM
452: Rational Graphs and Large Cardinals II 1/9/11 1:36AM
453: Rational Graphs and Large Cardinals III 1/20/11 2:33AM
454: Three Milestones in Incompleteness 2/7/11 12:05AM
455: The Quantifier "most" 2/22/11 4:47PM
456: The Quantifiers "majority/minority" 2/23/11 9:51AM
457: Maximal Cliques and Large Cardinals 5/3/11 3:40AM
458: Sequential Constructions for Large Cardinals 5/5/11 10:37AM
459: Greedy CLique Constructions in the Integers 5/8/11 1:18PM
460: Greedy Clique Constructions Simplified 5/8/11 7:39PM
461: Reflections on Vienna Meeting 5/12/11 10:41AM
462: Improvements/Pi01 Independence 5/14/11 11:53AM
463: Pi01 independence/comprehensive 5/21/11 11:31PM
464: Order Invariant Split Theorem 5/30/11 11:43AM
465: Patterns in Order Invariant Graphs 6/4/11 5:51PM
466: RETURN TO 463/Dominators 6/13/11 12:15AM
467: Comment on Minimal Dominators 6/14/11 11:58AM
468: Maximal Cliques/Incompleteness 7/26/11 4:11PM
469: Invariant Maximality/Incompleteness 11/13/11 11:47AM
470: Invariant Maximal Square Theorem 11/17/11 6:58PM
471: Shift Invariant Maximal Squares/Incompleteness 11/23/11 11:37PM
472. Shift Invariant Maximal Squares/Incompleteness 11/29/11 9:15PM
473: Invariant Maximal Powers/Incompleteness 1 12/7/11 5:13AMs
474: Invariant Maximal Squares 01/12/12 9:46AM
475: Invariant Functions and Incompleteness 1/16/12 5:57PM
476: Maximality, CHoice, and Incompleteness 1/23/12 11:52AM
477: TYPO 1/23/12 4:36PM
478: Maximality, Choice, and Incompleteness 2/2/12 5:45AM
479: Explicitly Pi01 Incompleteness 2/12/12 9:16AM
480: Order Equivalence and Incompleteness
481: Complementation and Incompleteness 2/15/12 8:40AM
482: Maximality, Choice, and Incompleteness 2 2/19/12 7:43AM
483: Invariance in Q[0,n]^k 2/19/12 7:34AM
484: Finite Choice and Incompleteness 2/20/12 6:37AM__
485: Large Large Cardinals 2/26/12 5:55AM
486: Naturalness Issues 3/14/12 2:07PM
487: Invariant Maximality/Naturalness 3/21/12 1:43AM
488: Invariant Maximality Program 3/24/12 12:28AM
489: Invariant Maximality Programs 3/24/12 2:31PM
490: Invariant Maximality Program 2 3/24/12 3:19PM
491: Formal Simplicity 3/25/12 11:50PM
492: Invariant Maximality/conjectures 3/31/12 7:31PM
493: Invariant Maximality/conjectures 2 3/31/12 7:32PM
494: Inv Max Templates/Z+up, upper Z+ equiv 4/5/12 4:17PM
495: Invariant Finite Choice 4/5/12 4:18PM
496: Invariant Finite Choice/restatement 4/8/12 2:18AM
497: Invariant Maximality Restated 5/2/12 2:49AM
498: Embedded Maximal Cliques 1 9/18/12 12:43AM
499. Embedded Maximal Cliques 2 9/19/12 2:50AM
500: Embedded Maximal Cliques 3 9/20/12 10:15PM
501: Embedded Maximal Cliques 4 9/23/12 2:16AM
502: Embedded Maximal Cliques 5 9/26/12 1:21AM
503: Proper Classes of Graphs 10/13/12 12:17PM
504. Embedded Maximal Cliques 6 10/14/12 12:49PM
505: Function Transfer Theory 10/21/12 2:15AM
506: Finite Embedded Weakly Maximal Cliques 10/23/12 12:53AM
507: Finite Embedded Dominators 11/6/12 6:40AM
508: Unique Undefinable Elements 12/22/12 8:08PM
509: A Divine Consistency Proof for Mathematics 12/26/12 2:15AM
510: Unique Undefinable Elements Again 1/9/13 5:07PM
511: A Supernatural Consistency Proof for Mathematics 1/10/13 9:19PM
512: Countable Elementary Extensions 1/11/13 7:31PM
513: Five Supernatural Consistency Proofs for Mathematics 1/14/13 1:13AM
514: Countable Elementary Extensions/again 1/14/13 2:19AM
515: Eight Supernatural Consistency Proofs For Mathematics 1/19/13 2:40PM
516: Embedded Maximal Cliques/restatement
Harvey M. Friedman
More information about the FOM
mailing list