933: Provable Functions of Set Theories/1

[Harvey Friedman]

We characterize the provable functions (provably recursive functions)  of
various set theories, including those with large cardinals. The approach
also is a uniform characterization of the provable ordinals of all theories
including the weak systems that fall under the current state of the art of
classical ordinal notations.

FUN(k,k)

FUN(k,k) is the set of all functions f:A^k into A^k, where A containedin Q
is unbounded above, where -1/1,-1/2,-1/3,... are the first omega elements
of A. and 1,2,3,... are elements of A.

THE ORDER FUNCTION

The order function of f in FUN(k,k) if the function h:Z+ into Z+ defined as
follows. h(n) is the number of times f has to be applied starting at
(-1/n,-1/n,...,-1/n) in order to repeat. There may be no order function
because for some n, h(n) does not exist.

The stable order function of a subset of FUN(k,k) is the unique order
function of its elements. A subset of FUN(k,k) may or may not have a stable
order function.

TWO SPECIAL SUBSETS OF FUN[k,k]

Let R is an order invariant subset of Q^2k viewed as a relation on Q^k. R
gives rise to the important subset of FUN[k,k] defined as
follows.Gamma(R,k) is the set of all f in FUN[k,k] such that the following
holds:

1. For all x in A^k, f(x) is some y = f(y) R x with y <lex x, if such y
exists; x otherwise.
2. {1,2,...} is a gap section SOI for f consisting of limit points, in the
sense of posting #932.

Theta(R,k) is the set of all f in FUN[k,k] such that the following holds:

1. For all x in A^k, f(x) is some y = f(y) R x with y <lex x, if such y
exists; x otherwise.
2. {1,2,...} s a section SOI for f in the sense of posting #932.

STABLE ORDER FUNCTIONS

THEOREM 1. The stable order functions of the various Gamma(R,k) that have
one are provably recursive functions of MAH cofinal in the provably
recursive functions of MAH. The provably recursive functions of MAH are
exactly the functions elementary recursive in the stable order functions of
the various Gamma(R,k) that have one.

THEOREM 2. The stable order functions of the various Theta(R,k) that have
one are provably recursive functions of SRP cofinal in the provably
recursive functions of SRP. The provably recursive functions of SRP are
exactly the functions elementary recursive in the stable order functions of
the various Theta(R,k) that have one.

FLEXIBILITY

The SOI conditions can be adjusted so that we likewise obtain corresponding
results for a large range of standard fragments of SRP.

TANGIBLE INCOMPLETENESS

We also have another route to Tangible Incompleteness, even without the
constants:

For all order invariant R containedin Q^2k there exists f:A^k into A^k, A
containedin Q, with condition 1 above, and section SOIs of any finite size.

We have chosen other lead independent statements based on maximality, but
do consider this approach as important and an integral part of our Tangible
Incompleteness. We want to make the first line of Tangible Incompleteness
as concise as reasonable, without a lot of alternative options at first.

##########################################

My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 933rd 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-899 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

900: Ultra Convergence/2  10/3/21 12:35AM
901: Remarks on Reverse Mathematics/6  10/4/21 5:55AM
902: Mathematical L and OD/RM  10/7/21  5:13AM
903: Foundations of Large Cardinals/1  10/12/21 12:58AM
904: Foundations of Large Cardinals/2  10/13/21 3:17PM
905: Foundations of Large Cardinals/3  10/13/21 3:17PM
906: Foundations of Large Cardinals/4  10/13/21  3:17PM
907: Base Theory Proposals for Third Order RM/1  10/13/21 10:22PM
908: Base Theory Proposals for Third Order RM/2  10/17/21 3:15PM
909: Base Theory Proposals for Third Order RM/3  10/17/21 3:25PM
910: Base Theory Proposals for Third Order RM/4  10/17/21 3:36PM
911: Ultra Convergence/3  1017/21  4:33PM
912: Base Theory Proposals for Third Order RM/5  10/18/21 7:22PM
913: Base Theory Proposals for Third Order RM/6  10/18/21 7:23PM
914: Base Theory Proposals for Third Order RM/7  10/20/21 12:39PM
915: Base Theory Proposals for Third Order RM/8  10/20/21 7:48PM
916: Tangible Incompleteness and Clique Construction/1  12/8/21   7:25PM
917: Proof Theory of Arithmetic/1  12/8/21  7:43PM
918: Tangible Incompleteness and Clique Construction/1  12/11/21  10:15PM
919: Proof Theory of Arithmetic/2  12/11/21  10:17PM
920: Polynomials and PA  1/7/22  4:35PM
921: Polynomials and PA/2  1/9/22  6:57 PM
922: WQO Games  1/10/22 5:32AM
923: Polynomials and PA/3  1/11/22  10:30 PM
924: Polynomials and PA/4  1/13/22  2:02 AM
925: Polynomials and PA/5  2/1/22  9::04PM
926: Polynomials and PA/6  2/1/22 11:20AM
927: Order Invariant Games/1  03/04/22  9:11AM
928: Order Invariant Games/2  03/7/22  4:22AM
929: Physical Infinity/randomness  *3/21/22 02:14AM *
930: Tangible Indiscernibles/1 05/07/22  7:46PM
931: Tangible Indiscernibles/2  *5/14/22  1:34PM :*
932: Tangible Indiscernibles/3  *5/14/22  1:34PM *

Harvey Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20220516/cf8d6ff4/attachment-0001.html>