[FOM] 505: Function Transfer Theory
Harvey Friedman
hmflogic at gmail.com
Sun Oct 21 02:14:33 EDT 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
*****************************************
FUNCTION TRANSFER THEORY 1
by
Harvey M. Friedman
October 21, 2012
FUNCTION TRANSFER THEORY.
1. M(R,S), SM(R,S), P(R,S), SP(R,S).
Let R,S be binary relations on respective sets A,B. We write M(R,S)
for the statement
every f:A into B maps some R related arguments to S related values.
We write SM(R,S) for the statement
every surjective f:A into B maps some R related arguments to S related values.
In Function Transfer Theory (FTT), we investigate M(R,S), SM(R,S), for
a variety of relations R,S. In FTT, we also restrict the class of
functions and surjection functions used in various ways.
In this preliminary report, we only consider relations R,S on the
various N^k, where N is the set of all nonnegative integers. This
immediately suggests various restrictions on the functions between the
N^k.
In this abstract, we consider the restriction to polynomials between
the various N^k. Thus we write P(R,S) for the statement
every polynomial f:N^k into N^r maps some R related arguments to S
related values.
We write SP(R,S) for the statement
every surjective polynomial f:N^k into N^r maps some R related
arguments to S related values.
CONJECTURE. There is a (simple, informative) algorithm for determining
the truth values of M(R,S), SM(R,S), P(R,S), SP(R,S), for any given
order invariant relations R,S on the various N^k.
We shall see that for the particular order invariant R,S considered
here, the SP(R,S) give rise to new particularly simple statements
independent of PA = Peano Arithmetic.
2. <=*[N^k], adj[N^k].
In this abstract, we use only the following two relations on the various N^k.
x <=*[N^k] y if and only if x,y ∈ N^k, and for all 1 <= i <= k, x_i <= y_i.
x adj[N^k] y if and only if x,y are each strictly increasing elements
of N^k, and for all 1 <= i < k, y_i = x_i+1.
adj is read "adjacent". E.g., (2,3,5,11) adj[N^4] (3,5,11,25).
Note that <=*[N^k] and adj[N^k] are order invariant relations on N^k.
These two order invariant relations are sufficient to generate
remarkable metamathematical phenomena.
3. M(R,S) for <=*[N^k], adj[N^k].
THEOREM 3.1. For all k,r >= 1, M(<=*[N^k],<=*[N^r]).
THEOREM 3.2. For k,r >= 1, M(adj[N^k],adj[N^r]) if and only if r = 1.
THEOREM 3.3. For all k,r >= 1, M(<=*[N^k],adj[N^r]) if and only if r = 1.
THEOREM 3.4. For all k,r >= 1, M(adj[N^k],<=*[N^r]).
THEOREM 3.5. Theorems 3.1 - 3.3 are provable in RCA_0. Theorem 3.4 is
provably equivalent to "epsilon_0 is well ordered" over RCA_0.
4. SM(R,S) for <=*[N^k], adj[N^k].
THEOREM 4.1. For all k,r >= 1, SM(<=*[N^k],<=*[N^r]).
THEOREM 4.2. For all k,r >= 1, SM(adj[N^k],adj[N^r]) if and only if k
= 1 or r = 1.
THEOREM 4.3. For all k,r >= 1, SM(<=*[N^k],adj[N^r]).
THEOREM 4.4. For all k,r >= 1, SM(adj[N^k],<=*[N^r]).
THEOREM 4.5. Theorems 4.1, 4.2 are provable in RCA_0. Theorems 4.3,
4.4 are each provably equivalent to "epsilon_0 is well ordered" over
RCA_0.
5. P(R,S) for <=*[N^k], adj[N^k].
THEOREM 5.1. For all k,r >= 1, P(<=*[N^k],<=*[N^r]).
THEOREM 5.2. For k,r >= 1, P(adj[N^k],adj[N^r]) if and only if r = 1.
THEOREM 5.3. For all k,r >= 1, P(<=*[N^k],adj[N^r]) if and only if r = 1.
THEOREM 5.4. For all k,r >= 1, P(adj[N^k],<=*[N^r]).
THEOREM 5.5. Theorems 5.1 - 5.4 are provable in EFA.
Here EFA is exponential function arithmetic, or ISigma_0(exp).
6. SP(R,S) for <=*[N^k], adj[N^k].
THEOREM 6.1. For all k,r >= 1, SP(<=*[N^k],<=*[N^r]).
THEOREM 6.2. For all k,r >= 1, SP(adj[N^k],adj[N^r]) if and only if k < r.
THEOREM 6.3. For all k,r >= 1, SP(<=*[N^k],adj[N^r]).
THEOREM 6.4. For all k,r >= 1, SP(adj[N^k],<=*[N^r]).
THEOREM 6.5. Theorems 6.1, 6.2, 6.4 are provable in EFA. Theorem 6.3
is provably equivalent to 2-Con(PA) over EFA.
Here 2-Con(PA) asserts that every Sigma-0-2 sentence provable in PA is true.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 505th 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-449 can be found
in the FOM archives at
http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html
450: Maximal Sets and Large Cardinals II 12/6/10 12:48PM
451: Rational Graphs and Large Cardinals I 12/18/10 10:56PM
452: Rational Graphs and Large Cardinals II 1/9/11 1:36AM
453: Rational Graphs and Large Cardinals III 1/20/11 2:33AM
454: Three Milestones in Incompleteness 2/7/11 12:05AM
455: The Quantifier "most" 2/22/11 4:47PM
456: The Quantifiers "majority/minority" 2/23/11 9:51AM
457: Maximal Cliques and Large Cardinals 5/3/11 3:40AM
458: Sequential Constructions for Large Cardinals 5/5/11 10:37AM
459: Greedy CLique Constructions in the Integers 5/8/11 1:18PM
460: Greedy Clique Constructions Simplified 5/8/11 7:39PM
461: Reflections on Vienna Meeting 5/12/11 10:41AM
462: Improvements/Pi01 Independence 5/14/11 11:53AM
463: Pi01 independence/comprehensive 5/21/11 11:31PM
464: Order Invariant Split Theorem 5/30/11 11:43AM
465: Patterns in Order Invariant Graphs 6/4/11 5:51PM
466: RETURN TO 463/Dominators 6/13/11 12:15AM
467: Comment on Minimal Dominators 6/14/11 11:58AM
468: Maximal Cliques/Incompleteness 7/26/11 4:11PM
469: Invariant Maximality/Incompleteness 11/13/11 11:47AM
470: Invariant Maximal Square Theorem 11/17/11 6:58PM
471: Shift Invariant Maximal Squares/Incompleteness 11/23/11 11:37PM
472. Shift Invariant Maximal Squares/Incompleteness 11/29/11 9:15PM
473: Invariant Maximal Powers/Incompleteness 1 12/7/11 5:13AMs
474: Invariant Maximal Squares 01/12/12 9:46AM
475: Invariant Functions and Incompleteness 1/16/12 5:57PM
476: Maximality, CHoice, and Incompleteness 1/23/12 11:52AM
477: TYPO 1/23/12 4:36PM
478: Maximality, Choice, and Incompleteness 2/2/12 5:45AM
479: Explicitly Pi01 Incompleteness 2/12/12 9:16AM
480: Order Equivalence and Incompleteness
481: Complementation and Incompleteness 2/15/12 8:40AM
482: Maximality, Choice, and Incompleteness 2 2/19/12 7:43AM
483: Invariance in Q[0,n]^k 2/19/12 7:34AM
484: Finite Choice and Incompleteness 2/20/12 6:37AM__
485: Large Large Cardinals 2/26/12 5:55AM
486: Naturalness Issues 3/14/12 2:07PM
487: Invariant Maximality/Naturalness 3/21/12 1:43AM
488: Invariant Maximality Program 3/24/12 12:28AM
489: Invariant Maximality Programs 3/24/12 2:31PM
490: Invariant Maximality Program 2 3/24/12 3:19PM
491: Formal Simplicity 3/25/12 11:50PM
492: Invariant Maximality/conjectures 3/31/12 7:31PM
493: Invariant Maximality/conjectures 2 3/31/12 7:32PM
494: Inv Max Templates/Z+up, upper Z+ equiv 4/5/12 4:17PM
495: Invariant Finite Choice 4/5/12 4:18PM
496: Invariant Finite Choice/restatement 4/8/12 2:18AM
497: Invariant Maximality Restated 5/2/12 2:49AM
498: Embedded Maximal Cliques 1 9/18/12 12:43AM
499. Embedded Maximal Cliques 2 9/19/12 2:50AM
500: Embedded Maximal Cliques 3 9/20/12 10:15PM
501: Embedded Maximal Cliques 4 9/23/12 2:16AM
502: Embedded Maximal Cliques 5 9/26/12 1:21AM
503: Proper Classes of Graphs 10/13/12 12:17PM
504. Embedded Maximal Cliques 6 10/14/12 12:49PM
Harvey Friedman
More information about the FOM
mailing list