FOM: 59:Restricted summation:Pi-0-1 sentences
Harvey Friedman
friedman at math.ohio-state.edu
Fri Sep 17 05:41:55 EDT 1999
This is the 59th in a series of self contained postings to fom covering a
wide range of topics in f.o.m. Previous ones are:
1:Foundational Completeness 11/3/97, 10:13AM, 10:26AM.
2:Axioms 11/6/97.
3:Simplicity 11/14/97 10:10AM.
4:Simplicity 11/14/97 4:25PM
5:Constructions 11/15/97 5:24PM
6:Undefinability/Nonstandard Models 11/16/97 12:04AM
7.Undefinability/Nonstandard Models 11/17/97 12:31AM
8.Schemes 11/17/97 12:30AM
9:Nonstandard Arithmetic 11/18/97 11:53AM
10:Pathology 12/8/97 12:37AM
11:F.O.M. & Math Logic 12/14/97 5:47AM
12:Finite trees/large cardinals 3/11/98 11:36AM
13:Min recursion/Provably recursive functions 3/20/98 4:45AM
14:New characterizations of the provable ordinals 4/8/98 2:09AM
14':Errata 4/8/98 9:48AM
15:Structural Independence results and provable ordinals 4/16/98
10:53PM
16:Logical Equations, etc. 4/17/98 1:25PM
16':Errata 4/28/98 10:28AM
17:Very Strong Borel statements 4/26/98 8:06PM
18:Binary Functions and Large Cardinals 4/30/98 12:03PM
19:Long Sequences 7/31/98 9:42AM
20:Proof Theoretic Degrees 8/2/98 9:37PM
21:Long Sequences/Update 10/13/98 3:18AM
22:Finite Trees/Impredicativity 10/20/98 10:13AM
23:Q-Systems and Proof Theoretic Ordinals 11/6/98 3:01AM
24:Predicatively Unfeasible Integers 11/10/98 10:44PM
25:Long Walks 11/16/98 7:05AM
26:Optimized functions/Large Cardinals 1/13/99 12:53PM
27:Finite Trees/Impredicativity:Sketches 1/13/99 12:54PM
28:Optimized Functions/Large Cardinals:more 1/27/99 4:37AM
28':Restatement 1/28/99 5:49AM
29:Large Cardinals/where are we? I 2/22/99 6:11AM
30:Large Cardinals/where are we? II 2/23/99 6:15AM
31:First Free Sets/Large Cardinals 2/27/99 1:43AM
32:Greedy Constructions/Large Cardinals 3/2/99 11:21PM
33:A Variant 3/4/99 1:52PM
34:Walks in N^k 3/7/99 1:43PM
35:Special AE Sentences 3/18/99 4:56AM
35':Restatement 3/21/99 2:20PM
36:Adjacent Ramsey Theory 3/23/99 1:00AM
37:Adjacent Ramsey Theory/more 5:45AM 3/25/99
38:Existential Properties of Numerical Functions 3/26/99 2:21PM
39:Large Cardinals/synthesis 4/7/99 11:43AM
40:Enormous Integers in Algebraic Geometry 5/17/99 11:07AM
41:Strong Philosophical Indiscernibles
42:Mythical Trees 5/25/99 5:11PM
43:More Enormous Integers/AlgGeom 5/25/99 6:00PM
44:Indiscernible Primes 5/27/99 12:53 PM
45:Result #1/Program A 7/14/99 11:07AM
46:Tamism 7/14/99 11:25AM
47:Subalgebras/Reverse Math 7/14/99 11:36AM
48:Continuous Embeddings/Reverse Mathematics 7/15/99 12:24PM
49:Ulm Theory/Reverse Mathematics 7/17/99 3:21PM
50:Enormous Integers/Number Theory 7/17/99 11:39PN
51:Enormous Integers/Plane Geometry 7/18/99 3:16PM
52:Cardinals and Cones 7/18/99 3:33PM
53:Free Sets/Reverse Math 7/19/99 2:11PM
54:Recursion Theory/Dynamics 7/22/99 9:28PM
55:Term Rewriting/Proof Theory 8/27/99 3:00PM
56:Consistency of Algebra/Geometry 8/27/99 3:01PM
57:Fixpoints/Summation/Large Cardinals 9/10/99 3:47AM
57':Restatement 9/11/99 7:06AM
58:Program A/Conjectures 9/12/99 1:03AM
We first make some minor corrections to posting #57'. I am grateful to
Andreas Blass for calling these to my attention.
1. I wrote
>Another wild card with the same effect is this. Ask for approximate fixed
>points which start with the same infinite set.
This should be
Another wild card with the same effect is this. Ask for approximate fixed
points for two decreasing cofinite contractions which start with the same
infinite set.
2. I wrote
>However, we do know
>that the statements involved are provably equivalent to 1-consistency.
This should be
>However, we do know that the statements involved are provably equivalent
>to the 1-consistency of Mahlo cardinals of finite order.
3. I wrote
>Theorem 5 also holds for the following weakening of Proposition 5.
This should be
>Theorem 5 also holds for either part of the following weakening of
>Proposition 4.
4. More substantively, I wrote
>In fact, the mere
>existence of a subset of N so that you can always insist on the appearance
>of some element from that subset is already provably equivalent to the
>1-consistency of Mahlo cardinals of finite order.
This should be
>In fact, the mere existence of a subset E of N with blocks of bounded
>lengths,
>so that you can always insist on the first set being a subset of E, is
>already
>provably equivalent to the 1-consistency of Mahlo cardinals of finite order.
**********
I now want to discuss the extraction of natural Pi-0-2 sentences from the
second half of #57'. There are a lot of details still to check, but these
appear to be a "right" way to do the extraction.
SLIGHT CHANGE OF TERMINOLOGY
I prefer the terminology "disjoint cover" from "partition" or "disjointly
partitions". So let me rephrase the relevant part of 57'.
Let A,B,C be three sets. We say that A,B is a disjoint cover of C if and
only if
i) A intersect B = emptyset;
ii) C containedin A union B.
Let Z be the set of all integers, Z^+ be the set of all positive integers.
For A containedin Z, let Sigma(A) be the set of all sums x_1 + ... + x_n, n
>= 1, such that x_1,...,x_n in A.
Let Z* be the set of all nonempty finite sequences of integers. We view Z
as a subset of Z*. We say that U containedin Z* is finite dimensional if
and only if there is a finite upper bound to the lengths of the elements of
U.
Each U containedin Z* defines the restricted summation function
Sigma_U:P(Z) into P(Z) given by Sigma_U(A) = {x_1 + ... + x_n: n >= 1,
x_1,...,x_n in A, and (x_1,...,x_n) in U}. Note that if U = Z* then Sigma_U =
Sigma.
THEOREM 1. Let U containedin Z*\Z. There is a unique A containedin Z^+ such
that A,Sigma_U(A) is a disjoint cover of Z^+.
PROPOSITION 2. Let U,V be finite dimensional subsets of Z*\Z. There exist
infinite sets A containedin B containedin C containedin Z^+ such that
B,Sigma_U(B) is a disjoint cover of Sigma_V(A), and C\A,Sigma_U(C)\A is a
disjoint cover of Sigma_V(B).
Here is a strengthened form.
PROPOSITION 3. Let U,V be finite dimensional subsets of Z*\Z, and n >= 1.
There exist infinite sets A_1 properlycontainedin ... properlycontainedin
A_n containedin Z^+ such that for all 1 <= i <= n-1,
A_i+1\A_1,Sigma_U(A_i+1)\A_1 is a disjoint cover of Sigma_V(A_i).
THEOREM 4. Propositions 2 and 3 are provably equivalent, over RCA_0, to the
1-consistency of MAH = ZFC + {there exists an n-Mahlo cardinal}n. In
particular, they are independent of ZFC.
Pi-0-1 SENTENCES
We say that U containedin Z* is semilinear if and only if for all k >= 1, U
intersect Z^k is a semilinear subset of Z^k (i.e., a Boolean combination of
halfplanes in Z^k). We will assume without loss of generality that the
coefficients used in the halfplanes are integers.
We need a measure of the "thiness" of A containedin Z^+. Thus we define
#(A) as the inf of the ratios A_n+1/A_n, where A_n is the n-th element of
A, counting from n = 1. If #(A) is "large" then A is "thin".
PROPOSITION A. Let U,V be finite dimensional semilinear subsets of Z*\Z and
A containedin Z^+, where #(A) is sufficiently large. Then there exist A
containedin B containedin C containedin Z^+ such that B,Sigma_U(B) is a
disjoint cover of Sigma_V(A), and C,Sigma_U(C) is a disjoint cover of
Sigma_V(B).
Proposition A is still infinitary since A may be finite. However, note that
we use C,Sigma_U(C) instead of C\A,Sigma_U(C)\A. We could also have used
the latter and get the same results, but the present form is simpler. Both
forms of Proposition A are provably equivalent to the consistency of MAH =
ZFC + {there exists an n-Mahlo cardinal}_n, rather than the 1-consistency,
over RCA_0.
PROPOSITION B. Let U,V be finite dimensional semilinear subsets of Z*\Z and
A be a finite subset of Z^+, where #(A) is sufficiently large. Then there
exist finite A containedin B containedin C containedin Z^+ such that
B,Sigma_U(B) is a disjoint cover of Sigma_V(A), and C,Sigma_U(C) is a
disjoint cover of Sigma_V(B).
Note that Proposition B is finitary: all infinite objects have been
removed. It can be shown to be equivalent to Con(MAH) over EFA (exponential
function arithmetic).
Also note that Proposition B, as written, is in Pi-0-2 form. However, it
can be put in Pi-0-1 form because double exponential upper bounds can be
given on how large #(A) need be, as well as where the set C lies, in terms
of the size of the presentations of U,V.
We give the corresponding results for the more general Theorem 4. The
results are the same.
PROPOSITION C. Let n >= 1 and U,V be finite dimensional semilinear subsets
of Z*\Z. Let A_1 containedin Z_+, where #(A) is sufficiently large. Then
there exist A_1 containedin ... containedin A_n containedin Z^+ such that
for all 1 <= i <= n-1, A_i+1,Sigma_U(A_i+1) is a disjoint cover of
Sigma_V(A_i).
PROPOSITION D. Let n >= 1 and U,V be finite dimensional semilinear subsets
of Z*\Z. Let A_1 be a finite subset of Z^+, where #(A) is sufficiently
large. Then there exist finite A_1 containedin ... containedin A_n
containedin Z^+ such that for all 1 <= i <= n-1, A_i+1,Sigma_U(A_i+1) is a
disjoint cover of Sigma_V(A_i).
More information about the FOM
mailing list