[FOM] 353: Function Generation 1
Harvey Friedman
friedman at math.ohio-state.edu
Sat Aug 8 18:29:52 EDT 2009
It turns out that I need to insert an extra cube in http://www.cs.nyu.edu/pipermail/fom/2009-August/013907.html
(see below).
Because of this, and upon reflecting on the nice advantages of not
having the second parameter p at all, I am compelled to have my cake
and eat it, too.
Because of this, I have now moved to FUNCTION GENERATION.
{FOR THE RECORD. It turns out that (in dimension pk+k) we need to
invert from a subcube of A to a subcube of the p dimensional expression
rather than just
invert from a subcube of A to the p dimensional expression.
Compare this with http://www.cs.nyu.edu/pipermail/fom/2009-August/013906.html
where (in dimension 2k), where we
map from a subcube of A to a cube that is mapped to a subcube of the
one dimensional expression.
So both of these versions have their respective advantages. Note the
interesting tradeoff.}
FUNCTION GENERATION 1
by
Harvey M. Friedman
August 8, 2009
0. Terminology.
1. Background.
2. Strongly Mahlo Cardinals.
3. Subtle Cardinals.
N is the set of all nonnegative integers. For k >= 1, N^k is the set
of all k tuples from N. For k <= 0, N^k is the empty set.
For A contained in N^k, we write fld(A) for the set of all coordinates
of elements of A. We write cube(A) = fld(A)^k for the cube generated
by A.
Define A# = {x in A: min(x) > min(fld(A))}.
Let R contained in N^k x N^k. For A contained in N^k, we define R<[B]
= {y in N^k: (there exists x in A)(R(x,y) and max(x) < max(y))}.
The presence of R<[A] indicates that A containedin N^k.
We write M(R,A) for the minimal choice function for R. M(R,A):N^k into
N^k is defined by
M(R,A)(x) is the lexicographically least y in A such that R(x,y); 0 if
there is no y with R(x,y).
The presence of M(R,A) indicates that A containedin N^k.
NOTE: Many other orderings on N^k can be used other than the
lexicographic order. E.g., first order by max, then lexicographically;
or first put in descending order, and then order lexicographically.
Let F:N^k into N^k and A contained in N^k. We can use F,A to generate
elements of N^k as follows.
GEN(F,A,0) = A.
GEN(F,A,r+1) = cube(GEN(F,A,r) union F[GEN(F,A,r)]).
A regressive value of F on A is a y in N^k such that for some x in A,
max(F(x)) < min(x).
THe presence of GEN(F,A,r) indicates that A containedin N^k.
Delta is "symmetric difference".
For B contained in N, we write B! = {n!: n in B}.
Define !(n) as n!...!, where there are n !'s.
For A contained in N^k and n in Z, define A+n = {x+n: n in A}. Here x
+n is the result of adding n to each coordinate of x.
SMAH+ = ZFC + "for all k there is a strongly k-Mahlo cardinal". SMAH =
ZFC + {there exists a strongly k-Mahlo cardinal}_k
SUB+ = ZFC + "for all k there is a k-subtle cardinal". SUB = ZFC +
{there exists a k-subtle cardinal}_k.
1. BACKGROUND.
We start with one of many versions of the Complementation Theorem.
COMPLEMENTATION THEOREM. For all R contained in N^k x N^k, there
exists A
contained in N^k such that A delta R<[A] = N^k. Furthermore, A is
unique and contains the origin.
Other ways of writing A delta R<[A] = N^k are
R<[A] = N^k\A
A = N^k\R<[A]
A U. R<[A] = N^k
Here U. is "disjoint union".
We would like to get a "large" A. However, the unique A may be as
small as {0}.
We have better luck with A-1 delta R<[A].
THEOREM 1.1. For all R contained in N^k x N^k, there exists infinite A
contained in N^k such that A-1 delta R<[A] = N^k.
However, we cannot always obtain A which is large in the sense of
containing an infinite cube.
We will see that we can require that A have an infinite subcube if we
weaken the largeness condition on A-1 delta R<[A].
I.e., we can find A with an infinite subcube where A-1 delta R<[A] is
"large".
There is a regressive values theorem discussed in my Annals of Math
paper, 1998. There, we introduced and worked with counts on the
regressive values of functions. Here are versions that live on the
suitable large cardinals.
THEOREM 1.2. Let lambda is a (roughly) k-subtle cardinal. Every
f:lambda^k into lambda^k has finitely many regressive values over some
infinite cube in lambda^k. Furthermore, the converse (roughly) holds.
THEOREM 1.3. Let lambda be a (roughly) k-subtle cardinal. Every
f:lambda^k into lambda^k has at most (8k)! regressive values over some
length p cube in lambda^k. Furthermore, the converse (roughly) holds.
2. STRONGLY MAHLO CARDINALS.
Strongly Mahlo cardinals and Mahlo cardinals are equivalent for our
discrete math purposes, by Goedel's L relativization (well known
conservative extension).
PROPOSITION 2.1. For all R contained in N^k x N^k, some A with an
infinite subcube E has GEN(M(R,A),E,k) contained in A-1 delta R<[A].
PROPOSITION 2.2. For all (unit coefficient) piecewise linear R
contained in N^k x N^k, some A with an infinite subube E has
GEN(M(R,A),E,k) contained in A-1 delta R<[A]. Furthermore, A and its
aforementioned infinite subcube can be taken to be piecewise (base 2)
exponential.
PROPOSITION 2.3. For all unit coefficient piecewise linear R contained
in [0,t!]^k x [0,t!]^k, some A containing [8k,t]!^k has GEN(M(R,A),
[0,t]!^k,k) contained in A-1 delta R<[A].
THEOREM 2.4. Propositions 2.1-2.3 are provable in SMAH+ but not in any
consistent fragment of SMAH. They are all provably equivalent, over
ACA, to Con(SMAH). The same holds even if the last k under GEN is
fixed to be 3.
Note that Proposition 2.2 is arithmetical, using piecewise
exponential. Using the decision procedure for base 2 exponential
Presburger, Proposition 2.2 becomes Pi02. A double exponential bound
can be given on the exponential representation. Using this,
Propositions 2.2 becomes Pi01.
Note that Proposition 2.3 is explicitly Pi01.
Rudimentary piecewise linear R can also be used, with the same
results. These are given by Boolean combinations of unit coefficient
linear inequalities, where at most two variables appear in each linear
inequality.
3. SUBTLE CARDINALS.
PROPOSITION 3.1. For all R contained in N^k x N^k, some
GEN(M(R,A),E,k) and GEN(M(R,A),E#,k) are two infinite subsets of A-1
delta R<[A] with the same elements from [0,min(fld(E))^k.
PROPOSITION 3.2. For all R contained in [0,!(8pk)]^k x [0,!(8pk)]^k,
some GEN(M(R,A),E,k) and GEN(M(R,A),E#,k) are two >= p element subsets
of A-1 delta R<[A] with the same elements from [0,min(fld(E))^k.
Note that Propositions 3.3, 3.4 are explicitly Pi01.
THEOREM 3.5. Propositions 3.1-3.4 are provable in SUB+ but not in any
consistent fragment of SUB. Propositions 3.1-3.4 are provably
equivalent,
over ACA, to Con(SUB). The same holds even if the last k under GEN is
fixed to be 3.
**********************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 351st 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-249 can be found at
http://www.cs.nyu.edu/pipermail/fom/2005-June/008999.html in the FOM
archives, 6/15/05, 9:18PM. NOTE: The title of #269 has been corrected
from the original.
250. Extreme Cardinals/Pi01 7/31/05 8:34PM
251. Embedding Axioms 8/1/05 10:40AM
252. Pi01 Revisited 10/25/05 10:35PM
253. Pi01 Progress 10/26/05 6:32AM
254. Pi01 Progress/more 11/10/05 4:37AM
255. Controlling Pi01 11/12 5:10PM
256. NAME:finite inclusion theory 11/21/05 2:34AM
257. FIT/more 11/22/05 5:34AM
258. Pi01/Simplification/Restatement 11/27/05 2:12AM
259. Pi01 pointer 11/30/05 10:36AM
260. Pi01/simplification 12/3/05 3:11PM
261. Pi01/nicer 12/5/05 2:26AM
262. Correction/Restatement 12/9/05 10:13AM
263. Pi01/digraphs 1 1/13/06 1:11AM
264. Pi01/digraphs 2 1/27/06 11:34AM
265. Pi01/digraphs 2/more 1/28/06 2:46PM
266. Pi01/digraphs/unifying 2/4/06 5:27AM
267. Pi01/digraphs/progress 2/8/06 2:44AM
268. Finite to Infinite 1 2/22/06 9:01AM
269. Pi01,Pi00/digraphs 2/25/06 3:09AM
270. Finite to Infinite/Restatement 2/25/06 8:25PM
271. Clarification of Smith Article 3/22/06 5:58PM
272. Sigma01/optimal 3/24/06 1:45PM
273: Sigma01/optimal/size 3/28/06 12:57PM
274: Subcubic Graph Numbers 4/1/06 11:23AM
275: Kruskal Theorem/Impredicativity 4/2/06 12:16PM
276: Higman/Kruskal/impredicativity 4/4/06 6:31AM
277: Strict Predicativity 4/5/06 1:58PM
278: Ultra/Strict/Predicativity/Higman 4/8/06 1:33AM
279: Subcubic graph numbers/restated 4/8/06 3:14AN
280: Generating large caridnals/self embedding axioms 5/2/06 4:55AM
281: Linear Self Embedding Axioms 5/5/06 2:32AM
282: Adventures in Pi01 Independence 5/7/06
283: A theory of indiscernibles 5/7/06 6:42PM
284: Godel's Second 5/9/06 10:02AM
285: Godel's Second/more 5/10/06 5:55PM
286: Godel's Second/still more 5/11/06 2:05PM
287: More Pi01 adventures 5/18/06 9:19AM
288: Discrete ordered rings and large cardinals 6/1/06 11:28AM
289: Integer Thresholds in FFF 6/6/06 10:23PM
290: Independently Free Minds/Collectively Random Agents 6/12/06
11:01AM
291: Independently Free Minds/Collectively Random Agents (more) 6/13/06
5:01PM
292: Concept Calculus 1 6/17/06 5:26PM
293: Concept Calculus 2 6/20/06 6:27PM
294: Concept Calculus 3 6/25/06 5:15PM
295: Concept Calculus 4 7/3/06 2:34AM
296: Order Calculus 7/7/06 12:13PM
297: Order Calculus/restatement 7/11/06 12:16PM
298: Concept Calculus 5 7/14/06 5:40AM
299: Order Calculus/simplification 7/23/06 7:38PM
300: Exotic Prefix Theory 9/14/06 7:11AM
301: Exotic Prefix Theory (correction) 9/14/06 6:09PM
302: PA Completeness 10/29/06 2:38AM
303: PA Completeness (restatement) 10/30/06 11:53AM
304: PA Completeness/strategy 11/4/06 10:57AM
305: Proofs of Godel's Second 12/21/06 11:31AM
306: Godel's Second/more 12/23/06 7:39PM
307: Formalized Consistency Problem Solved 1/14/07 6:24PM
308: Large Large Cardinals 7/05/07 5:01AM
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
312: Pi01 Incompleteness 11/13/07 3:11PM
313: Pi01 Incompleteness 12/19/07 8:00AM
314: Pi01 Incompleteness/Digraphs 12/22/07 4:12AM
315: Pi01 Incompleteness/Digraphs/#2 1/16/08 7:32AM
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
319: Pi01 Incompleteness/Digraphs/#3 2/12/08 9:21PM
320: Pi01 Incompleteness/#4 2/13/08 5:32PM
321: Pi01 Incompleteness/forward imaging 2/19/08 5:09PM
322: Pi01 Incompleteness/forward imaging 2 3/10/08 11:09PM
323: Pi01 Incompleteness/point deletion 3/17/08 2:18PM
324: Existential Comprehension 4/10/08 10:16PM
325: Single Quantifier Comprehension 4/14/08 11:07AM
326: Progress in Pi01 Incompleteness 1 10/22/08 11:58PM
327: Finite Independence/update 1/16/09 7:39PM
328: Polynomial Independence 1 1/16/09 7:39PM
329: Finite Decidability/Templating 1/16/09 7:01PM
330: Templating Pi01/Polynomial 1/17/09 7:25PM
331: Corrected Pi01/Templating 1/20/09 8:50PM
332: Preferred Model 1/22/09 7:28PM
333: Single Quantifier Comprehension/more 1/26/09 4:32PM
334: Progress in Pi01 Incompleteness 2 4/3/09 11:26PM
335: Undecidability/Euclidean geometry 4/27/09 1:12PM
336: Undecidability/Euclidean geometry/2 4/29/09 1:43PM
337: Undecidability/Euclidean geometry/3 5/3/09 6:54PM
338: Undecidability/Euclidean geometry/4 5/5/09 6:38PM
339: Undecidability/Euclidean geometry/5 5/7/09 2:25PM
340: Thematic Pi01 Incompleteness 1 5/13/09 5:56PM
341: Thematic Pi01 Incompleteness 2 5/21/09 7:25PM
342: Thematic Pi01 Incompleteness 3 5/23/09 7:48PM
343: Goedel's Second Revisited 1 5/27/09 6:07AM
344: Goedel's Second Revisited 2 6/1/09 9:21PM
345: Thematic Pi01 Incompleteness 4 6/15/09 1:15PM
appears misnumbered as 344.
346: Goedel's Second Revisited 3 6/16/09 11:04PM
347: Goedel's Second Revisited 4 6/20/09 1:25AM
348: Goedel's Second Revisited 5 6/22/09 11:00AM
349: Pi01 Incompleteness/set series 7/20/09 11:21PM
350: one dimensional set series 7/23/09 12:11AM
351: Mapping Theorems/Mahlo/Subtle 8/6/09 10:59PM
352: Mapping Theorems/simpler 8/7/09 10:06PM
Harvey Friedman
More information about the FOM
mailing list