[FOM] 520: Incompleteness - 4 abstracts
Harvey Friedman
hmflogic at gmail.com
Mon Jun 23 22:15:30 EDT 2014
FOUR LINKS:
http://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
77. Invariant Maximality and Incompleteness, 37 pages, April 30, 2014, to
appear. Supersedes January 8, 2014 version. CMI051114w
78. Order Theoretic Equations, Maximality, and Incompleteness, 17 pages,
June 7, 2014. Extended abstract. Largely supersedes 77, but some content in
77 is not incorporated here, and so we are keeping 77. OrdTheEq060714
79. Order Invariant Graphs and Finite Incompleteness, 4 pages, June 22,
2014. Extended abstract. FIiniteSeqInc062214a
http://u.osu.edu/friedman.8/foundational-adventures/downloadable-lecture-notes-2/
63. Foundational Investigations in Mathematics and Philosophy, May 8, 2014,
Public Lecture, Princeton Philosophy Department, 10 pages. PrincTalk060614
***FOUR ABSTRACTS****
INVARIANT MAXIMALITY AND INCOMPLETENESS
Harvey M. Friedman*
Distinguished University Professor of Mathematics, Philosophy, and Computer
Science, Emeritus
Ohio State University
Columbus, Ohio 43235
April 30, 2014
*This research was partially supported by an Ohio State University
Presidential Research Grant and by the John Templeton Foundation grant ID
#36297. The opinions expressed here are those of the author and do not
necessarily reflect the views of the John Templeton Foundation.
Abstract. We present new examples of discrete mathematical statements that
can be proved from large cardinal hypotheses but not within the usual ZFC
axioms for mathematics (assuming ZFC is consistent). These new statements
are provably equivalent to Pi01 sentences (purely universal statements,
logically analogous to Fermat's Last Theorem) - in particular provably
equivalent to the consistency of strong set theories, including one that is
in explicitly Pi01 form. The examples live in the rational numbers, with
only order, where the nonnegative integers are distinguished elements. The
statements take the general form: every order invariant W containedin Q^2k
has a maximal subset S^2, with an invariance condition. Certain statements
of this form are shown to be provably equivalent to the widely believed
Con(SRP), and hence unprovable in ZFC (assuming ZFC is consistent).
Modifications are made, involving a simple cross section condition, which
propels the statement beyond the huge cardinal hierarchy, to attain
equivalence with Con(HUGE). We also present some nondeterministic
constructions of infinite and finite length with some of the same
metamathematical properties. These lead to practical computer
investigations designed to provide arguable confirmation of Con(ZFC) and
more.
1. Introduction
2. Preliminaries.
2.1. Invariance.
2.2. Order invariance.
2.3. N/order invariance.
2.4. Restricted shifts.
2.5. (Q,N,+,<).
2.6. Graphs.
3. Invariant maximal roots and cliques.
3.1. Maximal roots and cliques in Q^k.
3.2. Maximal roots and cliques in J^k.
3.3. Step maximal roots and cliques in Q^k.
3.4. Inductively maximal cliques in Q^k.
4. N tail equivalence is maximum.
5. Finite sequential cliques.
6. Inductively maximal cliques in Q^<=k.
7. Order Theoretic Invariance Program.
8. Computer investigations.
8.1. Infinite and finite length constructions.
8.2. Computational aspects.
9. Proofs of invariant maximality.
9.1. The stationary Ramsey property.
9.2. Invariant Step Maximal Roots (Nteq).
10. Appendix - formal systems used.
11. References.
ORDER THEORETIC EQUATIONS, MAXIMALITY, AND INCOMPLETENESS
by
Harvey M. Friedman*
Distinguished University Professor of Mathematics, Philosophy, and Computer
Science Emeritus
Ohio State University
June 7, 2014
*This research was partially supported by an Ohio State University
Presidential Research Grant and by the John Templeton Foundation grant ID
#36297. The opinions expressed here are those of the author and do not
necessarily reflect the views of the John Templeton Foundation.
ABSTRACT. We work with binary relations R on an ambient space X. We first
consider the set equations R[A] = A and R[A] = A^c, with known R and
unknown A, for arbitrary R containedin X2. We give a necessary and
sufficient condition for solvability of the first equation (requiring A
nonempty) and sufficient conditions for solvability of the second. We then
focus on X = Q[0,1]^k, where Q[0,1] = Q intersect [0,1], with very concrete
R. In particular, we assume R containedin Q[0,1]^2k is order theoretic. We
seek to determine the order theoretic R,S such that the set equations R[A]
= A, S[A] = A^c have a common solution. By Gödel's completeness theorem,
each such common solvability statement is provably equivalent to a
universal arithmetic sentence, representing the lowest level of complexity
of a mathematical statement involving infinitely many objects. We show that
there are specific order theoretic R,S such that ZFC is insufficient to
decide whether the equations R[A] = A, S[A] = Ac have a common solution. We
conjecture that all such common solvability statements can be decided using
some well studied standard large cardinal hypotheses. In fact, we use
specific natural order theoretic equivalence relations EQR_k containedin
Q[0,1]^2k for these independence results. In particular, we show that "R[A]
= A, S[A] = A^c have a common solution if R = EQR_k and S is a purely order
theoretic graph" can be proved using standard large cardinal hypotheses but
not in ZFC (Theorem 7.6). We convert these results to maximal independent
sets and maximal cliques as "in every purely order theoretic graph on
Q[0,1]k, some union of cosets of EQRk is maximally independent (is a
maximal clique)" (Propositions 8.1,8.2). We also convert these results to
maximal squares as "in every purely order theoretic subset of Q[0,1]^2k,
some union of cosets of EQR_2k is a maximal square" (Proposition 8.3).
Again, these are provable in SRP but not in ZFC (assuming ZFC is
consistent). In this way, significant information about the common
solvability of equations R[A] = A, S[A] = A^c for order theoretic R,S,
maximal independent sets cliques in purely order theoretic graphs, and
maximal squares in purely order theoretic sets can be obtained using
standard large cardinal hypotheses but not in ZFC alone.
1. R[A] = A.
2. R[A] = A^c.
3. (Purely) order theoretic sets.
4. R[A] = A, R order theoretic.
5. R[A] = A^c, R order theoretic.
6. Order theoretic conjectures.
7. Order theoretic conjectures and set theory.
8. Maximal cliques and maximal squares.
9. J replacing Q[0,1].
10. Proofs.
ORDER INVARIANT GRAPHS AND FINITE INCOMPLETENESS
by
Harvey M. Friedman*
Distinguished University Professor of Mathematics, Philosophy, and Computer
Science Emeritus
Ohio State University
June 22a, 2014
EXTENDED ABSTRACT
*This research was partially supported by the John Templeton Foundation
grant ID #36297. The opinions expressed here are those of the author and do
not necessarily reflect the views of the John Templeton Foundation.
ABSTRACT. Every order invariant graph on [Q]^infinity has a free E
containing ush(E) reducing [UE U N]<infinity. Every order invariant graph
on [Q]^<=k has a free {x_1,...,x_r,ush(x_1),...,ush(x_r)}, each
{x_1,...x_(8kni)!} reducing [x_1 U ... U x_i U {0,...,n}]^<=k. The second
statement finitely approximates the first. The proofs with ush removed are
unremarkable. The proofs of the full statements use standard large cardinal
hypotheses, and we show that there is no proof in ZFC (assuming ZFC is
consistent). The second statement is explicitly Pi02. The complexity of the
free set can be exponentially bounded, resulting in an explicitly Pi01 form.
FOUNDATIONAL INVESTIGATIONS IN MATHEMATICS AND PHILOSOPHY
Harvey M. Friedman*
Council of the Humanities
Department of Philosophy
Princeton University
May 8, 2014
edited June 6, 2014
NOTE: This is the text for the public lecture delivered on May 8, 2014 in
connection with my appointment as Research Scholar of the Council of the
Humanities and the Department of Philosophy at Princeton University, March
24 - May 2, 2014. It has been lightly edited until the Russell Paradox
section, which corrects a misstatement and with some improved material.
*This research was partially supported by an Ohio State University
Presidential Research Grant and by the John Templeton Foundation grant ID
#36297. The opinions expressed here are those of the author and do not
necessarily reflect the views of the John Templeton Foundation.
I want to express my thanks to the Council of the Humanities and the
Philosophy Department for hosting my 6 week visit from March 24 to May 2,
2014. It has been a great pleasure.
I want to especially thank Gideon Rosen, John Burgess, and Hans Halvorson
for making this possible.
I greatly enjoyed the interaction with graduate students at the recent
Princeton/Rutgers conference, and the Burgess/Halvorson informal seminar in
philosophy of mathematics and physics.
I have been holed up for more than 45 years trying to show that Gödel’s
Incompleteness Phenomena is not FAKE. I have recently succeeded in
establishing this in a clear sense that we will be discussing. I now call
this MATHEMATICALLY PERFECT INCOMPLETENESS.
So if you never heard of me before, this is largely what I have been doing
for about 100,000 hours.
I retired in 2012 from Ohio State University, in order to start over and
rethink everything. (Actually, my pension maxed out).
Thanks to this visit, I am coming out of my shell, and thinking about some
wider issues.
****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 519th 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 5/21/13 1:31PM
517: New Concrete Mathematical Incompleteness 8/2/13 9:57PM
518: Polynomial Independence 8/7/13 6:04AM
519: New Invariant Maximality 1/8/14 10:59PM
Harvey M. Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20140623/6aa3e804/attachment-0001.html>
More information about the FOM
mailing list