[FOM] 712: PA Incompleteness/1
Harvey Friedman
hmflogic at gmail.com
Fri Sep 23 01:20:50 EDT 2016
THIS POSTING IS SELF CONTAINED
The most well known Incompleteness at the level of PA are Goodstein's
Theorem and the Paris Harrington Theorem.
Both have tangible features that make them to some degree abnormal
mathematically. Goodstein's Theorem has a recreational flavor quite
different from normal mathematics. The Pairs Harrington Theorem does
not have a recreational flavor, and is close to the spirit of Ramsey
theory. However the use of an integer both as a size and an element is
a tangible abnormal feature.
To put this into context, citing abnormal features should not be
viewed as some sort of negative assessment that something is not
interesting. On the contrary - it simply calls for new research to
address the assessment.
Obviously, one can iterate this process of removing tangible
abnormalities, over and over again. I have discussed the idea of
"perfect naturalness", and have claimed to have met this for some
statements in Continuation/Emulation Theory. Continuation/Emulation
theory is not at the level of PA Incompleteness, but is expected to be
nicely weakened to be at that level.
There is also a major future beyond "perfect naturalness". I have
written about this in, e.g.,
http://www.cs.nyu.edu/pipermail/fom/2016-July/019966.html
So in the realm of PA Incompleteness, we can expect a long future
series of examples and tangible abnormalities, where the process is
certainly not going to end in the near future.
I have posted about PA Incompleteness here:
38: Existential Properties of Numerical Functions 3/26/99 2:21PM
44: Indiscernible Primes 5/27/99 12:53 PM
50: Enormous Integers/Number Theory 7/17/99 11:39PN
51: Enormous Integers/Plane Geometry 7/18/99 3:16PM
66: PA/an approach 10/21/99 8:02PM —— no.
81: Finite Distribution 3/13/00
91: Counting Theorems 6/24/00 8:22PM
106: Degenerative Cloning 5/4/01 10:57AM
123: Divisibility 2/2/02 10:57PM
152: sin 10:35PM 6/8/02
169: New PA Independence 5:11PM 8:35PM
178: Diophantine Shift Sequences 6/14/03 6:34PM
179: Polynomial Shift Sequences/Correction 6/15/03 2:24PM
180: Provable Functions of PA 6/16/03 12:42AM
197: PL and primes 11/12/03 7:46AM
199: Radical Polynomial Behavior Theorems
204: Finite Extrapolation 1/18/04 8:18AM
309: Thematic PA Incompleteness 10/22/07 10:56AM
310: Thematic PA Incompleteness 2 11/6/07 5:31AM
311: Thematic PA Incompleteness 3 11/8/07 8:35AM
316: Shift Theorems 1/24/08 12:36PM
317: Polynomials and PA 1/29/08 10:29PM
318: Polynomials and PA #2 2/4/08 12:07AM
328: Polynomial Independence 1 1/16/09 7:39PM
377: The Polynomial Shift Theorem 12/25/09 2:39PM
380: More Polynomial Shift Theorems 12/28/09 7:06AM
381: Trigonometric Shift Theorem 12/29/09 11:25AM
384: THe Polynomial Shift Translation Theorem/CORRECTION 12/31/09
7:51PM
387: Better Polynomial Shift Translation/typos 1/6/10 10:41PM
448: Naturalness/PA Independence 12/3/10 12:19AM
454: Three Milestones in Incompleteness 2/7/11 12:05AM
518: Polynomial Independence 8/7/13 6:04AM
And see
https://u.osu.edu/friedman.8/foundational-adventures/boolean-relation-theory-book/
Introduction
https://cage.ugent.be/~pelupessy/ARPH.pdf
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
Adjacent Ramsey Theory, #65.
http://arxiv.org/abs/math/9811187
section 1
*********************
PA INCOMPLETENESS
1. GENERAL FUNCTIONS
1.1. SPECIAL VALUE
1.2. REGRESSIVE COUNTING
1.3. UPWARD SHIFTING
1.4. UNAVOIDABLE INEQUALITIES
1.5. UNAVOIDABLE FUNCTIONS
2. POLYNOMIALS
for next posting
The general significance of PA Incompleteness can be viewed as
follows. We have statements about finite objects that can be proved
using infinite mathematics, but cannot be proved using finite
mathematics.
We use N,Z+ for the set of all nonnegative and positive integers,
respectively. k,n,m,r,s,t range over the positive integers unless
otherwise indicated.
For most of the statements, we have limited the number of parameters
in the interests of immediate readability. In a complete manuscript,
we would include versions with all relevant parameters.
ACA' is ACA_0 + "for all x and n the n-th Turing jump of x exists".
1.1. SPECIAL VALUE
Let f:N^k into N or f:[t] into N. A special value of f over E is a
value f(x) <= min(E), where x in E^k and x_1 < ... < x_k.
THEOREM 1.1.1. Every f:N^k into N has at most one special value over
some infinite set of positive integers.
THEOREM 1.1.2. For all k,r there exists t such that the following
holds. Every f:[t]^k into N has at most one special value over some r
element subset of [t]\{0}.
THEOREM 1.1.3. For all k,r there exists t such that the following
holds. Every f:[r]^k into [r] has at most one special value over some
t element subset of [t]\{0}.
THEOREM 1.1.4. Theorem 1.1.1 is provably equivalent to ACA' over
RCA_0. Theorems 1.1.2, 1.1.3 are provably equivalent to 1-Con(PA) over
EFA, with growth rates corresponding to the < epsilon_0 recursive
hierarchy.
1.2. REGRESSIVE COUNTING
Let f:N^k into N^k or f:[t]^k into N^r. A regressive value of f is a
value f(x), where max(f(x)) <= min(x).
A value of f over E is a value f(x), x in E^k. A regressive value of f
over E is a value f(x), x in E^k, where max(f(x)) <= min(x).
f is regressive if and only if for all x in dom(f), max(f(x)) <= min(x).
THEOREM 1.2.1. Every f:N^k into N^k has at most (k^k)r regressive
values over some r element subset of N.
THEOREM 1.2.2. For all k,r there exists t such that the following
bolds. Every f:[t]^k into N^k has at most (k^k)r regressive values
over some r element subset of [t].
THEOREM 1.2.3. For all k,r there exists t such that the following
bolds. Every f:[t]^k into [t]^k has at most (k^k)r regressive values
over some r element subset of [t].
Here are the corresponding statements for regressive f.
THEOREM 1.2.4. Every regressive f:N^k into N^k has at most (k^k)r
values over some r element subset of N.
THEOREM 1.2.5. For all k,r there exists t such that the following
bolds. Every regressive f:[t]^k into N^r has at most (k^k)r values
over some r element subset of [t].
THEOREM 1.2.6. For all k,r there exists t such that the following
bolds. Every regressive f:[t]^k into [t]^r has at most (k^k)r values
over some r element subset of [t].
THEOREM 1.2.7. Theorems 1.2.1, 1.2.4 are provably equivalent to
"epsilon_0 is well ordered" over RCA_0. Theorems 1.2.2, 1.2.3, 1.2.5,
1.2.6 are provably equivalent to 1-Con(PA) over EFA, with growth rates
corresponding to the < epsilon_0 recursive hierarchy..
See http://arxiv.org/abs/math/9811187
section 1
1.3. UPWARD SHIFTING
For x,y in N^k, x <=* y if and only if for all 1 <= i <= k, x_i <= y_i.
THEOREM 1.3.1. For all f:N^k into N^k there exists n_1 < n_2 < n_3 <
... such that f(n_1,...,n_k) <=* f(n_2,...,n_k+1) <=* f(n_3,...,n_k+2)
<=* ... .
THEOREM 1.3.2. For all f:N^k into N^k there exists n_1 < ... < n_k+1
such that f(n_1,...,n_k) <=* f(n_2,...,n_k+1).
THEOREM 1.3.3. For all f:N^k into N there exists n_1 < ... < n_k+2
such that f(n_1,...,n_k) <= f(n_2,...,n_k+1). <= f(n_3,...,n_k+2).
THEOREM 1.3.4. For all f:N^k into N there exists n_1 < ... < n_k such
that f(n_2,...,n_k) - f(n_1,...,n_k) is in 2N.
We say that f:[t]^k into [t]^k is limited if and only if for all x in
[t]^k, max(f(x)) <= max(x).
THEOREM 1.3.5. For all k there exists t such that the following holds.
For all limited f:[t]^k into N^k there exists n_1 < ... < n_k+1 such
that f(n_1,...,n_k) <=* f(n_2,...,n_k+1).
THEOREM 1.3.6. For all k there exists t such that the following holds.
For all limited f:[t]^k into N there exists n_1 < ... < n_k+2 such
that f(n_1,...,n_k) <= f(n_2,...,n_k+1) <= f(n_3,...,n_k+2).
THEOREM 1.3.7. For all k there exists t such that the following holds.
For all limited f:[t]^k into N there exists n_1 < ... < n_k+1 such
that f(n_2,...,n_k+1) - f(n_1,...,n_k) is in 2N.
THEOREM 1.3.8. Theorem 1.3.1 is provably equivalent to ACA' over
RCA_0.Theorems 1.3.2, 1.3.3, 1.3.4 are provably equivalent to
"epsilon_0 is well ordered" over RCA_0. Theorems 1.3.5, 1.3.6, 1.3.7
are provably equivalent to 1-Con(PA) over EFA, with growth rates
corresponding to the < epsilon_0 recursive hierarchy..
See https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
Adjacent Ramsey Theory, #65.
1.4. UNAVOIDABLE INEQUALITIES
The (k,n)-inequalities take the form f(x_1,...,x_k) <= f(y_1,...,y_k),
where x_1,...,x_k,y_1,...,y_k are among the k variables v_1,...,v_n.
We will use flat inequalities in the context where f:N^k into N and
the variables v_1,...,v_n are assigned n strictly increasing
nonnegative integers.
A flat inequality is regular if and only if
i. The subscripts of x_1,...,x_k are order equivalent to the
subscripts of y_1,...,y_k.
ii. There exists v_i such that, for all j, if the subscript of x_j is
smaller than i then the subscripts of x_j and y_j are the same; and if
the subscript of x_j is at least i then the subscript of x_j is less
than the subscript of y_j.
THEOREM 1.4.1. Let f:N^k into N be arbitrary (recursive, primitive
recursive, poly time computable). There exist v_1 < ... < v_n such
that all of the regular (k,n)-inequalities hold. This is false if we
replace the set of all of the regular (k,n)-inequalities by any single
non regular (k,n)-inequality.
THEOREM 1.4.2. Theorem 1.4.1 for arbitrary f is provably equivalent to
"epsilon_0 is well ordered" over RCA_0. Theorem 1.4.1 for recursive f
is provably equivalent to 2-Con(PA) over EFA. Theorem 1.4.2 for
primitive recursive and for poly time computable is provably
equivalent to 1-Con(PA) over EFA, with growth rates corresponding to
the < epsilon_0 recursive hierarchy..
Use some of https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
Adjacent Ramsey Theory, #65.
1.5. UNAVOIDABLE COPIES
We say that f is (k,n)-fine if and only if
i. f:A^k into N for some n element A containedin N.
ii. f(a_1,...,a_k) <= f(b_1,...,b_k) iff f(c_1,...,c_k) <=
f(d_1,...,d_k) provided (a_1,...,a_k,b_1,...,b_k) and
(c_1,...,c_k,d_1,...,d_k) are order equivalent and lie in A^2k.
iii. f(a_1,...,a_k) <= f(b_1,...,b_k) provided (a_1,...,a_k),
(b_1,...,b_k) are order equivalent elements of A^k and there exists 0
<= t <= n such that for all a_i < t, a_i = b_i, and for all a_i >= t,
a_i < b_i.
Let f:A^k into N and g:B^k into N. We say that f,g are similar if and
only if for the unique increasing bijection h:A into B, we have
f(a_1,...,a_k) <= f(b_1,...,b_k) if and only if f(h(a_1),...,h(a_k))
<= f(h(b_1),...,h(b_k)).
THEOREM 1.5.1 Let S be a set of functions f:[n]^k into [(n+1)^k]. The
following are equivalent.
i. Every arbitrary (recursive, primitive recursive, poly time
computable) f:N^k into N has a restriction that is similar to an
element of S.
ii. Every (k,n)-fine function is similar to an element of S.
THEOREM 1.5.2. Theorem 1.5.1 for arbitrary f is provably equivalent to
"epsilon_0 is well ordered" over RCA_0. Theorem 1.5.1 for recursive f
is provably equivalent to 2-Con(PA) over EFA. Theorem 1.5.1 for
primitive recursive and for poly time computable f is provably
equivalent to 1-Con(PA) over EFA, with growth rates corresponding to
the < epsilon_0 recursive hierarchy.,
Use some of https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
Adjacent Ramsey Theory, #65.
***********************************************
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 712th 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-699 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/
700: Large Cardinals and Continuations/14 8/1/16 11:01AM
701: Extending Functions/1 8/10/16 10:02AM
702: Large Cardinals and Continuations/15 8/22/16 9:22PM
703: Large Cardinals and Continuations/16 8/26/16 12:03AM
704: Large Cardinals and Continuations/17 8/31/16 12:55AM
705: Large Cardinals and Continuations/18 8/31/16 11:47PM
706: Second Incompleteness/1 7/5/16 2:03AM
707: Second Incompleteness/2 9/8/16 3:37PM
708: Second Incompleteness/3 9/11/16 10:33PM
709: Large Cardinals and Continuations/19 9/13/16 4:17AM
710: Large Cardinals and Continuations/20 9/14/16 1:27AM
711: Large Cardinals and Continuations/21 9/18/16 10:42AM
Harvey Friedman
More information about the FOM
mailing list