[FOM] 779: End of Year Claims
Harvey Friedman
hmflogic at gmail.com
Sun Dec 31 20:03:08 EST 2017
I have been operating under a new policy that generally speaking, new claims
are being backed up right away on my website
http://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
However, there has been a lot of major developments in my efforts
during December, 2017, and I would like to end my 2017 with an
ambitious to do list for 2018 - which of course includes the
completion of the book Concrete Mathematical Incompleteness which,
presently, is planned to have these three PARTS:
CONCRETE MATHEMATICAL INCOMPLETENESS
PART ONE. BOOLEAN RELATION THEORY (done)
PART TWO. EMULATION FUNCTION THEORY
PART THREE. INDUCTIVE EQUATION THEORY
1. New Emulation Function Theory/infinite/SRP.
2. New Inductive Equation Theory/infinite/SRP.
3. New Inductive Equation Theory/infinite/HUGE.
4. New One Dimensional Combinatorial Incompleteness
5. New/Old Polynomial Incompleteness.
6. More.
1. NEW EMULATION FUNCTION THEORY/INFINITE/SRP
There has been some recent drama in Emulation Theory. However, in
no way, shape, or form, are we going to amend the Putnam Volume paper,
to appear:
http://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#92
Here is what happened. We always planned to eventually consider and
develop Emulation Theory for functions instead of sets. We tried this
briefly some time ago, and nothing all that dramatic came out of it,
so it was put at a non high priority.
But I recently took another look, and it has become dramatic. In January, we
plan to put a proof of the new statement(s) in WKL_0 + Con(SRP), and
also a proof that the new statement(s) imply the old statement from
the above #92 in WKL_0, on my website.
For very strong motivation, we start with a very familiar property
from combinatorial large cardinal theory. f:lambda^n into lambda^m is
regressive if and only if min(x) > 0 implies min(x) > max(f(x)).
LARGE CARDINAL PROPERTY. Every regressive f:lambda^k into lambda has
some alpha_1 < ... < alpha_k+1 with f(alpha_1,...,alpha_k) =
f(alpha_2,...,alpha_k+1).
PARAMETERIZED LARGE CARDINAL PROPERTY. Every regressive f:lambda^2k
into lambda^2k has some 0 < alpha_1 < ... < alpha_k+1 with max(x) <
alpha_1 implies f(x,alpha_1,...,alpha_k) = f(x,alpha_2,...,alpha_k+1).
Look how CLOSELY RELATED our breakthrough Emulation Function Theory
statements are now:
EMULATION SHIFT THEOREM. EST. Every regressive f:Q[0,k+1]^k into
Q[0,k+1] with finite support has an optimal emulation with g(1,...,k)
= g(2,...,k+1).
PARAMETERIZED EMULATION SHIFT THEOREM. PEST. Every regressive
f:Q[0,k+1]^2k into Q[0,k+1]^2k with finite support has an optimal
emulation with max(x) < 1 implies g(x,1,...,k) = g(x,2,...,k+1).
*supporting definitions*
REGRESSIVE. For f:Q[0,n]^m into Q[0,n]^r, f is regressive if and only
if min(x) > 0 implies min(x) > max(f(x)).
SUPPORT. For f:Q[0,n}^m into Q[0,n]^r, supp(f) = {x: max(f(x)) > 0}.
EMULATION. g is an emulation of f if and only if every (x,gx,y,gy) is
order equivalent to some (z,fz,w,fw). I.e., every element of g^2 is
order equivalent to an element of f^2 in terms of graphs of f,g.
OPTIMAL EMULATION. g is an optimal emulation of f if and only if g is
an emulation of f, where if we change the value of g at any argument
not in supp(g) so that x is in supp(g), then g is no longer an
emulation of f.
Note the simple no nonsense shift equation conclusion(s) for EST and
PEST!!! And, as we shall see from the definitions, this EST is very
*strategic*. We start with a rather impoverished f, due to its finite
support. We then struggle to optimally enlarge its support while still
remaining an emulation. You can struggle as best you can (optimally)
in such a way that the shift equation holds.
THEOREM 1.1. EST and PEST are provably equivalent to Con(SRP) over WKL_0.
2. NEW INDUCTiVE EQUATION THEORY/INFINITE/SRP
using set equations
In Inductive Equation Theory we proceed differently, with an obviously
inductive character.
UPPER SHIFT EQUATION THEOREM. USET. For order invariant R containedin
Q^k x Q^k, the equation S = (E U {0})^k\R<[S] has a solution where S
containedin Q^k contains its upper shift.
*supporting definitions*
ORDER INVARIANT. V containedin Q^n is order invariant if and only if
for all order equivalent x,y in Q^n, x in V iff y in V.
UPPER IMAGE. R<[A] = {y: (there exists x R y with max(x) < max(y).
UPPER SHIFT. ush(A) the result of adding 1 to all nonnegative
coordinates of elements of A.
THEOREM 2.1. USET is provably equivalent to Con(SRP) over WKL_0.
3. NEW INDUCTIVE EQUATION THEORY/INFINITE/HUGE
using set equations
STRONG UPPER SHIFT EQUATION THEOREM. SUSET. For order invariant R
containedin Q^k x Q^k, the equation S^< = (E U {0})^k<\R<[S] has a
solution where the upper shift truncations of S containedin Q^k are
conjunctive subsets of S.
*supporting definitions*
V^< is the set of all increasing tuples in V.
UPPER SHIFT TRUNCATIONS. The upper shift truncations of V containedin
Q^k are the sets ush(V) intersect Q(-infinity,p]^k, p in Q.
CONJUNCTIVE SUBSETS. The conjunctive subsets of V containedin Q^k are
the subsets of V that are defined by a finite system of atomic
formulas over (Q,<,V), with parameters allowed..
THEOREM 3.1. SUSET is provably equivalent to Con(HUGE) over WKL_0.
4. NEW ONE DIMENSIONAL COMBINATORIAL INCOMPLETENESS
THEOREM 4.1. Every f:N into {0,1} is constant on the ratios of some
integer with some n distinct primes.
THEOREM 4.2. Every f:N into N with finite range is constant on the
ratios of some integer with some n distinct primes.
THEOREM 4.3. Every f:N into N is increasing (<=) on the ratios of some
integer with some n distinct primes.
Theorem 4.3 is provable in ACA but not in ACA_0. Theorem 4.3 is
provably equivalent to "epsilon_0 is well ordered" over RCA_0.
We now give finite forms.
THEOREM 4.4. Every f:{0,...,r} into {0,1}, r >> n, is constant on the
ratios of some integer with some n distinct primes.
THEOREM 4.5. Every f:{0,...,r} into {0,...,s}, r >> s,n, is constant
on the ratios of some integer with some n distinct primes.
THEOREM 4.6. Every limited f:{0,...,r} into {0,...,r}, r >> n, is
constant on the ratios of some integer with some n distinct primes.
Here f:{0,...,r} into {0,...,r} is limited if and only if each
max(f(x)) <= max(x).
In Theorems 4.4, 4.5, the >> is iterated exponential, and cannot be
replaced by a fixed exponential length stack.
Theorem 4.6. is independent of PA. It is provably equivalent to
1-Con(PA) over EFA.
5. NEW/OLD POLYNOMIAL INCOMPLETENESS
We say that x,y in Z^k are adjacent if and only if y not= x is
obtained from x by removing the first term of x and adding a new last
term.
THEOREM 5.1. Every f:N^k into N^k has some x adj y with f(x) <=c f(y).
THEOREM 5.2. Every surjective f:N^k into N^k has some x <=c y with
f(x) adj f(y).
Theorem 5,1 is from our
http://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#65 Also see http://www.ams.org/journals/proc/2016-144-02/S0002-9939-2015-12759-1/
Theorem 5.2 follows from Theorem 5.1, Both are provably equivalent to
epsilon_0 is well ordered over EFA.
I applied this to polynomials in
https://cs.nyu.edu/pipermail/fom/2017-February/020268.html
THEOREM 5.3. Every polynomial P:N^k into N^k has some adjacent x,y
with f(x) <=c f(y).
THEOREM 5.4. Every surjective polynomial P:N^k into N^k has some x <=c
y with adjacent f(x),f(y).
The first is easy to prove in EFA. However, the second is independent
of PA, and in fact is provably equivalent to 2-Con(PA) over EFA.
2-Con(PA) comes in because of the following result which may be due to
me (or maybe not):
THEOREM 5.5. EFA proves the equivalence of 2-Con(PA) = "every
Sigma_0-2 sentence provable in PA is true", and "there is no recursive
descending sequence through epsilon_0".
We can look at these developments through the lens of comparing the
inverse image of P:Z^k into Z^k at two points x,y, which we write as
P^-1(x) and P^-1(y). When we do this properly, we no longer need the
hypothesis of surjectivity.
THEOREM 5.6. Every polynomial P:Z^k into Z^k has some adjacent x,y
where every preimage of x is <=c some preimage of y.
THEOREM 5.7. Every polynomial P:Z^k into Z^k has some adjacent x,y
where x is assumed no more times than y.
THEOREM 5.8. Every polynomial P:Z^k into Z^k has some adjacent x,y,z
where x is assumed no more times than y is assumed no more times than
z.
THEOREM 5.9. For polynomials P,Q:Z^k into Z^k, some adjacent x,y has x
assumed by P (Q) no more times than y is assumed by P (Q).
THEOREM 5.10. Theorem 5.7 is provable in ISigma_1. Theorems
5.6,5.8,5.9 are provably equivalent to 2-Con(PA) over EFA.
6. MORE
We are working up a number of further advances which we are not quite
ready to announce, but should be ready to announce in early 2018.
HAPPY NEW YEAR!
************************************************************************
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 779th 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
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
712: PA Incompleteness/1 9/23/16 1:20AM
713: Foundations of Geometry/1 9/24/16 2:09PM
714: Foundations of Geometry/2 9/25/16 10:26PM
715: Foundations of Geometry/3 9/27/16 1:08AM
716: Foundations of Geometry/4 9/27/16 10:25PM
717: Foundations of Geometry/5 9/30/16 12:16AM
718: Foundations of Geometry/6 101/16 12:19PM
719: Large Cardinals and Emulations/22
720: Foundations of Geometry/7 10/2/16 1:59PM
721: Large Cardinals and Emulations//23 10/4/16 2:35AM
722: Large Cardinals and Emulations/24 10/616 1:59AM
723: Philosophical Geometry/8 10/816 1:47AM
724: Philosophical Geometry/9 10/10/16 9:36AM
725: Philosophical Geometry/10 10/14/16 10:16PM
726: Philosophical Geometry/11 Oct 17 16:04:26 EDT 2016
727: Large Cardinals and Emulations/25 10/20/16 1:37PM
728: Philosophical Geometry/12 10/24/16 3:35PM
729: Consistency of Mathematics/1 10/25/16 1:25PM
730: Consistency of Mathematics/2 11/17/16 9:50PM
731: Large Cardinals and Emulations/26 11/21/16 5:40PM
732: Large Cardinals and Emulations/27 11/28/16 1:31AM
733: Large Cardinals and Emulations/28 12/6/16 1AM
734: Large Cardinals and Emulations/29 12/8/16 2:53PM
735: Philosophical Geometry/13 12/19/16 4:24PM
736: Philosophical Geometry/14 12/20/16 12:43PM
737: Philosophical Geometry/15 12/22/16 3:24PM
738: Philosophical Geometry/16 12/27/16 6:54PM
739: Philosophical Geometry/17 1/2/17 11:50PM
740: Philosophy of Incompleteness/2 1/7/16 8:33AM
741: Philosophy of Incompleteness/3 1/7/16 1:18PM
742: Philosophy of Incompleteness/4 1/8/16 3:45AM
743: Philosophy of Incompleteness/5 1/9/16 2:32PM
744: Philosophy of Incompleteness/6 1/10/16 1/10/16 12:15AM
745: Philosophy of Incompleteness/7 1/11/16 12:40AM
746: Philosophy of Incompleteness/8 1/12/17 3:54PM
747: PA Incompleteness/2 2/3/17 12:07PM
748: Large Cardinals and Emulations/30 2/15/17 2:19AM
749: Large Cardinals and Emulations/31 2/15/17 2:19AM
750: Large Cardinals and Emulations/32 2/15/17 2:20AM
751: Large Cardinals and Emulations/33 2/17/17 12:52AM
752: Emulation Theory for Pure Math/1 3/14/17 12:57AM
753: Emulation Theory for Math Logic 3/10/17 2:17AM
754: Large Cardinals and Emulations/34 3/12/17 12:34AM
755: Large Cardinals and Emulations/35 3/12/17 12:33AM
756: Large Cardinals and Emulations/36 3/24/17 8:03AM
757: Large Cardinals and Emulations/37 3/27/17 2:39AM
758: Large Cardinals and Emulations/38 4/10/17 1:11AM
759: Large Cardinals and Emulations/39 4/10/17 1:11AM
760: Large Cardinals and Emulations/40 4/13/17 11:53PM
761: Large Cardinals and Emulations/41 4/15/17 4:54PM
762: Baby Emulation Theory/Expositional 4/17/17 1:23AM
763: Large Cardinals and Emulations/42 5/817 2:18AM
764: Large Cardinals and Emulations/43 5/11/17 12:26AM
765: Large Cardinals and Emulations/44 5/14/17 6:03PM
766: Large Cardinals and Emulations/45 7/2/17 1:22PM
767: Impossible Counting 1 9/2/17 8:28AM
768: Theory Completions 9/4/17 9:13PM
769: Complexity of Integers 1 9/7/17 12:30AM
770: Algorithmic Unsolvability 1 10/13/17 1:55PM
771: Algorithmic Unsolvability 2 10/18/17 10/15/17 10:14PM
772: Algorithmic Unsolvability 3 Oct 19 02:41:32 EDT 2017
773: Goedel's Second: Proofs/1 Dec 18 20:31:25 EST 2017
774: Goedel's Second: Proofs/2 Dec 18 20:36:04 EST 2017
775: Goedel's Second: Proofs/3 Dec 19 00:48:45 EST 2017
776: Logically Natural Examples 1 12/21 01:00:40 EST 2017
777: Goedel's Second: Proofs/4 12/28/17 8:02PM
778: Goedel's Second: Proofs/5 12/30/17 2:40AM
Harvey Friedman
More information about the FOM
mailing list