[FOM] 569: Finite Integer Sums and Incompleteness

[Harvey Friedman]

The implicitly Pi01 statements corresponding to SRP and to HUGE are in
perfect shape - of course we still strive to make then better than
merely being Perfectly Mathematically Natural.

However, the explicitly Pi01 statements are not in what I would call
perfect shape - although the ones for SRP are what I would call
natural.

So I have been mulling over just how to improve these explicitly Pi01
statements. This recycles some earlier ideas in an improved form.

It is now looking like the best implicitly Pi01/Pi02 sentences are on
a somewhat different path than the best explicitly Pi01 and Pi02
sentences.

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

DEFINITION 1. N is the set of all nonnegative integers. Let A,B,C
containedin N. A is between B and C if and only if B containedin A
containedin C. n is a k-sum from A if and only if n is the sum of k
elements of A, with repetitions allowed.

DEFINITION 2. Let V be a finite set of linear inequalities with
integer coefficients, in k variables. The V-decompositions of n >= 0
take the form

n = m_1 + ... + m_k

where 0 <= m_1,...,m_k < n, and all inequalities in V hold of m_1,...,m_k.

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.

THEOREM 2. Proposition 1 is provably equivalent to Con(SMAH) over EFA.

This looks pretty stable, and so I should think about both weakening
and strengthening it. For weakening, the idea is quite simple: require
that n be a simple function of k. This should support a full range of
logical strengths ranging between PA (and fragments), and SMAH,
passing through Z_2,Z_3,..., and Zermelo and ZFC, and even more. Thus
same natural explicitly Pi01 statement has numerically adjustable
parameters that give rise to a large variety of strengths.

************************************************************
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 569th 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

Harvey Friedman