# [FOM] 448: Naturalness/PA Independence

Harvey Friedman friedman at math.ohio-state.edu
Thu Dec 2 03:30:29 EST 2010

```THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

I recently discussed the following three theorems with a famous
combinatorialist in terms of mathematical naturalness. It would be

THEOREM 1. Let n >> k,r,p >= 1. Every r coloring of the unordered k-
tuples from {1,...,n} has an at least p element monochromatic set with
at least as many elements as its min.

THEOREM 2. Let n >> k >= 1. For every x_1,...,x_n from {1,...,k},
there exists 1 <= i < j <= n/2 such that x_i,...,x_2i is a subsequence
of x_j,...,x_2j.

THEOREM 3. Let n >> k >= 1. For every f:{1,...,n}^k into {1,...,n}^k
obeying max(f(x)) <= max(x), there exist distinct x_1,...,x_k+1 such
that f(x_1,...,x_k) <= f(x_2,...,x_k+1) coordinatewise.

Theorems 1,3 are equivalent to 1-Con(PA), and Theorem 2 is equivalent
to 1-Con(PA_2). PA_2 is 2 quantifier induction.

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

manuscripts. This is the 448th 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-349 can be found athttp://www.cs.nyu.edu/pipermail/fom/2009-August/014004.html
in the FOM archives.

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
353: Function Generation 1  8/9/09  12:09PM
354: Mahlo Cardinals in HIGH SCHOOL 1  8/9/09  6:37PM
355: Mahlo Cardinals in HIGH SCHOOL 2  8/10/09  6:18PM
356: Simplified HIGH SCHOOL and Mapping Theorem  8/14/09  9:31AM
357: HIGH SCHOOL Games/Update  8/20/09  10:42AM
358: clearer statements of HIGH SCHOOL Games  8/23/09  2:42AM
359: finite two person HIGH SCHOOL games  8/24/09  1:28PM
360: Finite Linear/Limited Memory Games  8/31/09  5:43PM
361: Finite Promise Games  9/2/09  7:04AM
362: Simplest Order Invariant Game  9/7/09  11:08AM
363: Greedy Function Games/Largest Cardinals 1
364: Anticipation Function Games/Largest Cardinals/Simplified 9/7/09
11:18AM
365: Free Reductions and Large Cardinals 1  9/24/09  1:06PM
366: Free Reductions and Large Cardinals/polished  9/28/09 2:19PM
367: Upper Shift Fixed Points and Large Cardinals  10/4/09 2:44PM
368: Upper Shift Fixed Point and Large Cardinals/correction 10/6/09
8:15PM
369. Fixed Points and Large Cardinals/restatement  10/29/09 2:23PM
370: Upper Shift Fixed Points, Sequences, Games, and Large Cardinals
11/19/09  12:14PM
371: Vector Reduction and Large Cardinals  11/21/09  1:34AM
372: Maximal Lower Chains, Vector Reduction, and Large Cardinals
11/26/09  5:05AM
373: Upper Shifts, Greedy Chains, Vector Reduction, and Large
Cardinals  12/7/09  9:17AM
374: Upper Shift Greedy Chain Games  12/12/09  5:56AM
375: Upper Shift Clique Games and Large Cardinals 1graham
376: The Upper Shift Greedy Clique Theorem, and Large Cardinals
12/24/09  2:23PM
377: The Polynomial Shift Theorem  12/25/09  2:39PM
378: Upper Shift Clique Sequences and Large Cardinals  12/25/09 2:41PM
379: Greedy Sets and Huge Cardinals 1
380: More Polynomial Shift Theorems  12/28/09  7:06AM
381: Trigonometric Shift Theorem  12/29/09  11:25AM
382: Upper Shift Greedy Cliques and Large Cardinals  12/30/09 2:51AM
383: Upper Shift Greedy Clique Sequences and Large Cardinals 1
12/30/09  3:25PM
384: THe Polynomial Shift Translation Theorem/CORRECTION 12/31/09
7:51PM
385: Shifts and Extreme Greedy Clique Sequences  1/1/10  7:35PM
386: Terrifically and Extremely Long Finite Sequences  1/1/10 7:35PM
387: Better Polynomial Shift Translation/typos  1/6/10  10:41PM
388: Goedel's Second Again/definitive?  1/7/10  11:06AM
389: Finite Games, Vector Reduction, and Large Cardinals 1 2/9/10
3:32PM
390: Finite Games, Vector Reduction, and Large Cardinals 2 2/14/09
10:27PM
391: Finite Games, Vector Reduction, and Large Cardinals 3 2/21/10
5:54AM
392: Finite Games, Vector Reduction, and Large Cardinals 4 2/22/10
9:15AM
393: Finite Games, Vector Reduction, and Large Cardinals 5 2/22/10
3:50AM
394: Free Reduction Theory 1  3/2/10  7:30PM
395: Free Reduction Theory 2  3/7/10  5:41PM
396: Free Reduction Theory 3  3/7/10  11:30PM
397: Free Reduction Theory 4  3/8/10  9:05AM
398: New Free Reduction Theory 1  3/10/10  5:26AM
399: New Free Reduction Theory 2  3/12/10  9:36AM
400: New Free Reduction Theory 3  3/14/10  11:55AM
401: New Free Reduction Theory 4  3/15/10  4:12PM
402: New Free Reduction Theory 5  3/19/10  12:59PM
403: Set Equation Tower Theory 1  3/22/10  2:45PM
404: Set Equation Tower Theory 2  3/24/10  11:18PM
405: Some Countable Model Theory 1  3/24/10  11:20PM
406: Set Equation Tower Theory 3  3/25/10  6:24PM
407: Kernel Tower Theory 1  3/31/10  12:02PM
408: Kernel tower Theory 2  4/1/10  6:46PM
409: Kernel Tower Theory 3  4/5/10  4:04PM
410: Kernel Function Theory 1  4/8/10  7:39PM
411: Free Generation Theory 1  4/13/10  2:55PM
412: Local Basis Construction Theory 1  4/17/10  11:23PM
413: Local Basis Construction Theory 2  4/20/10  1:51PM
414: Integer Decomposition Theory  4/23/10  12:45PM
415: Integer Decomposition Theory 2  4/24/10  3:49PM
416: Integer Decomposition Theory 3  4/26/10  7:04PM
417: Integer Decomposition Theory 4  4/28/10  6:25PM
418: Integer Decomposition Theory 5  4/29/10  4:08PM
419: Integer Decomposition Theory 6  5/4/10   10:39PM
420: Reduction Function Theory 1  5/17/10   2:53AM
421: Reduction Function Theory 2  5/19/10   12:00PM
422: Well Behaved Reduction Functions 1  5/23/10  4:12PM
423: Well Behaved Reduction Functions 2  5/27/10  3:01PM
424: Well Behaved Reduction Functions 3  5/29/10  8:06PM
425: Well Behaved Reduction Functions 4  5/31/10  5:05PM
426: Well Behaved Reduction Functions 5  6/2/10  12:43PM
427: Finite Games and Incompleteness 1  6/10/10  4:08PM
428: Typo Correction in #427  6/11/10  12:11AM
429: Finite Games and Incompleteness 2  6/16/10  7:26PM
430: Finite Games and Incompleteness 3  6/18/10  6:14PM
431: Finite Incompleteness/Combinatorially Simplest  6/20/10  11:22PM
432: Finite Games and Incompleteness 4  6/26/10  8:39PM
433: Finite Games and Incompleteness 5  6/27/10  3:33PM
434: Digraph Kernel Structure Theory 1  7/4/10  3:17PM
435: Kernel Structure Theory 1  7/5/10  5:55PM
436: Kernel Structure Theory 2  7/9/10  5:21PM
437: Twin Prime Polynomial  7/15/10  2:01PM
438: Twin Prime Polynomial/error  9/17/10  1:22PM
439: Twin Prime Polynomial/corrected 9/19/10  2:16PM
440: Finite Phase Transitions  9/26/10  1:28PM
441: Equational Representations  9/27/10  4:59PM
442: Kernel Structure Theory Restated  10/11/10  9:01PM
443: Kernels and Large Cardinals 1  10/21/10  12:16AM
444: The Exploding Universe 1  11/1/10  1:46AMs
445: Kernels and Large Cardinals II  11/17/10  10:13PM
446: Kernels and Large Cardinals III  11/22/10  2:50PM
447: Kernels and Large Cardinals IV  11/23/10  3:51PM

Harvey Friedman

```