[FOM] 330: Templating Pi01/Polynomial

Harvey Friedman friedman at math.ohio-state.edu
Sat Jan 17 17:04:23 EST 2009


TYPO in #328, http://www.cs.nyu.edu/pipermail/fom/2009-January/013287.html

We wrote there

> Let x,y in N^k. We write x <=* y if and only if for all 1 <= i <= n,
> x[i] <= y[i]. We write x <* y if and only if x <=* y and x not= y.
>
> We say that x,y in N^r are adjacent if and only if x,y are distinct
> and y begins with x[2],...,x[n].

The letter n is wrong in both places. This should be

Let x,y in N^k. We write x <=* y if and only if for all 1 <= i <= k,
x[i] <= y[i]. We write x <* y if and only if x <=* y and x not= y.

We say that x,y in N^r are adjacent if and only if x,y are distinct
and y begins with x[2],...,x[r].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Here we discuss Templating projects

1. for the Pi01 independence results that were presented in #326, http://www.cs.nyu.edu/pipermail/fom/2008-October/013161.html
2. for the polynomial independence results presented in #328. http://www.cs.nyu.edu/pipermail/fom/2009-January/013287.html

1. TEMPLATING THE Pi01 STATEMENT.

Recall the following from #326:

PROPOSITION 1.6. For all k,r >= 1 and upwards order invariant R  
containedin [0,r]^4k, some RRA is a subset of R(A') union A+2 with the  
same k dimensional powers of (8k)!.

This is equivalent to the consistency of ZFC with Mahlo cardinalities  
of every finite order.

We will take up a slight alternative mentioned at the end of #326.

PROPOSITION 1.6'. For all k,r >= 1 and upwards order invariant R  
containedin [1,r]^4k, some RRA is a subset of R(A') union A+1 with the  
same k dimensional powers of (8k)!.

For present purposes, we prefer to suppress the quantity (8k)!.  
Instead, we will use the following further variant of Proposition 1.6.

PROPOSITION 1.6*. For all r,p >> k and upwards order invariant R  
containedin [1,r]^4k, some RRA is a subset of R(A') union A+1 with the  
same k dimensional powers of p. The >> can be taken to represent a  
double exponential.

We now construct a first template. Write POW(p)^k for the set of all k  
dimensional powers of p. Here 1 is the first power of (8k)!.

TEMPLATE 1. For all r,p >> k and upwards order invariant R containedin  
[1,r]^4k, there exists A containedin [1,r] such that BOOL(A 
+1,R(A'),RRA,POW(p)^k).

In the above Template 1, BOOL(A+1,R(A'),RRA,POW(p)^k) represents any  
given Boolean relation between the four sets A+1,R(A'),RRA,POW(p)^k).

A Boolean relation between subsets A_1,...,A_n of E, is the equality  
between two expressions involving  
A_1,...,A_n,union,intersection,complement, where complementation is  
taken with respect to E. In Template 1, the E is [1,r]^k. THere are  
2^16 Boolean equations, up to formal equivalence, in four set variables.

I have made a decent start on solving Template 1. It appears to be  
difficult, but manageable. One gets an early reduction to 2^14 cases,  
still a big number.

Obviously, the list A+1,R(A'),RRA,POW(p)^k) looks ad hoc. More  
interesting, and hopefully still within reach of a sustained intense  
effort, would be. e.g.,

TEMPLATE 2. For all r,p >> k and upwards order invariant R containedin  
[1,r]^4k, there exists A containedin [1,r] such that BOOL(A,A 
+1,RA,RRA,R(A'),POW(p)^k).

Obviously, even more interesting would be

TEMPLATE 3. For all r,p >= k and upwards order invariant R containedin  
[1,r]^4k, there exists A containedin [1,r] such that BOOL(A,A+1,A 
+2,...;RA,RRA,RRRA,...;R(A'),RR(A'),RRR(A')...;POW(p)^k).

2. TEMPLATING THE POLYNOMIAL INDEPENDENCE RESULT.

Recall the following from #328:

THEOREM 5. For every surjective polynomial P:N^k into Z^r, there exist
x <* y such that P(x),P(y) are adjacent.

Here for x,y in N^k,

x <* y iff x not= y, and (forall i in [1,k])(x[i] <= y[i]).

For x,y in N^r,

x,y are adjacent iff x not= y, and y begins with x[2],...,x[r].

We view <* and adjacent, as having variable dimension. Thus, they are  
presented in a natural unifying way as follows:

x R y if and only if x,y are distinct vectors from N of the same  
length, such that

(forall i in [1,lth(x))), a given order invariant relation holds of  
x[i],x[i+1],y[i],y[i+1].

TEMPLATE 1. For every surjective polynomial P:N^k into Z^r, there  
exist x R y such that P(x) S P(y). Here R,S are binary relations on  
finite sequences from R, presented as above.

I believe that Template 1 is manageable.

There are obviously some easier Templates naturally arise. We can  
consider the relations of the forms:

(forall i in (1,lth(x)), a given order invariant relation holds of  
x[i],x[i+1],y[i].

The above doesn't cover the comparison of x[n],y[n], but it does cover  
all x[i],y[i], 1 <= i < n-1. So it doesn't quite incorporate x <* y -  
only a slightly weakened form.

Harvey Friedman

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 330th 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

Harvey Friedman






More information about the FOM mailing list