860: Unary Regressive Growth/1
Harvey Friedman
hmflogic at gmail.com
Sat Aug 1 21:50:21 EDT 2020
HEADS UP: https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#110, #111. #110 has been updated with the July 30,2020 version.
UNARY REGRESSIVE GROWTH
PRELIMINARIES
Let W be the set of all finite strictly regressive partial functions
f:Q into Q I.e., we require of the finite partial function f:Q into Q
that for all x in dom(f), f(x) < x. We view W as a set of ordered
pairs. Also dom(f) and rng(f) are important. Note that |rng(f)| <=
|dom(f)| = |f|.
Point expansion is performed as follows. Let f in W. Here are the
choices for expansion.
1. Adjoin some new f(p) = q, where q < p and p notin dom(f) U rng(f).
There is no restriction on q.
2. Delete some existing f(p) = q and adjoin f(p) = r and f(r) = q,
where q < r < p and r notin dom(f) U rng(f).
THEOREM 1. (EFA) Every point expansion of an element of W is an
element of W with exactly one more element.
f,g are isomorphic if and only if there is a bijection h:dom(f) U
rng(f) onto dom(g) U rng(g) such that for all x in dom(f), g(h(x)) =
h(f(x)).
GROWING SEQUENCES
A pure growing sequence is initialized with S_0 = {f}, f in W.. We
require that for all i >= 0, S_i+1 consists of one isomorphic copy of
all of the point extensions of elements of S_i. f is called the seed.
There are some simple facts about growing sequences.
THEOREM 1. (RCA0) Let (S_i), i >= 0, be a pure growing sequence with
seed of cardinality n >= 0.
i. Each S_i, i >= 0, is a finite set of elements of W of cardinality
i+n, no two of which are isomorphic.
ii. If n <=1 then each S_i consists of all elements of W of
cardinality i+n up to order isomorphism.
iii. If n >=2 then each S_i omits elements of W of cardinality n+i up
to isomorphism.
ACCELERATED GROWING SEQUENCES
We accelerate the growing process.
An accelerated growing sequence is initialized with S_0 = {f}, f in W.
We require that for all i >= 0, S_i+1 consists of one isomorphic copy
of all of the point extensions of elements of S_i, augmented, if
possible, with some g in W, |g| = i+1+n, which is not isomorphic to
any of these point extensions of elements of S_i we are using. If this
augmentation is impossible then we set S_i+1 = T.
There are some simple facts about accelerated growing sequences.
THEOREM 2. (RCA0) Let (S_i), i >= 0,be an accelerated growing sequence
with seed of cardinality n >= 0.
i. Each S_i, i >= 0, is a finite set of elements of W of cardinality
i+n, no two of which are isomorphic.
ii. If n <=1 then each S_i consists of all elements of W of
cardinality i+n up to order isomorphism.
iii. Let i be least such that all elements of W of cardinality i+n lie
in S_i up to isomorphism. (We are not asserting that i exists). Then
for all j > i, all elements of W of cardinality j+n lie in S_j up to
isomorphism, and augmentation for S_j is impossible. This i exists if
and only if all but finitely many elements of W are generated (in the
union of the S_k) up to isomorphism.
THEOREM 3. Every accelerated growing sequence generates all but
finitely many elements of W up to isomorphism. In every accelerated
growing sequence, with seed of cardinality n, some S_i contains all
elements of W of cardinality n+i up to isomorphism. For each seed of
cardinality n there exists i such that in every accelerated growing
sequence S_i contains all elements of W of cardinality n+i up to
isomorphism.
THEOREM 4. (EFA) Theorem 3 is equivalent to the 1-consistency of
arithmetic transfinite recursion up through any proper initial segment
of theta_Omega^omega at 0. The growth rate r = r(i) is just beyond the
provably recursive functions of this theory.
##########################################
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 860th 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-799 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/
800: Beyond Perfectly Natural/6 4/3/18 8:37PM
801: Big Foundational Issues/1 4/4/18 12:15AM
802: Systematic f.o.m./1 4/4/18 1:06AM
803: Perfectly Natural/7 4/11/18 1:02AM
804: Beyond Perfectly Natural/8 4/12/18 11:23PM
805: Beyond Perfectly Natural/9 4/20/18 10:47PM
806: Beyond Perfectly Natural/10 4/22/18 9:06PM
807: Beyond Perfectly Natural/11 4/29/18 9:19PM
808: Big Foundational Issues/2 5/1/18 12:24AM
809: Goedel's Second Reworked/1 5/20/18 3:47PM
810: Goedel's Second Reworked/2 5/23/18 10:59AM
811: Big Foundational Issues/3 5/23/18 10:06PM
812: Goedel's Second Reworked/3 5/24/18 9:57AM
813: Beyond Perfectly Natural/12 05/29/18 6:22AM
814: Beyond Perfectly Natural/13 6/3/18 2:05PM
815: Beyond Perfectly Natural/14 6/5/18 9:41PM
816: Beyond Perfectly Natural/15 6/8/18 1:20AM
817: Beyond Perfectly Natural/16 Jun 13 01:08:40
818: Beyond Perfectly Natural/17 6/13/18 4:16PM
819: Sugared ZFC Formalization/1 6/13/18 6:42PM
820: Sugared ZFC Formalization/2 6/14/18 6:45PM
821: Beyond Perfectly Natural/18 6/17/18 1:11AM
822: Tangible Incompleteness/1 7/14/18 10:56PM
823: Tangible Incompleteness/2 7/17/18 10:54PM
824: Tangible Incompleteness/3 7/18/18 11:13PM
825: Tangible Incompleteness/4 7/20/18 12:37AM
826: Tangible Incompleteness/5 7/26/18 11:37PM
827: Tangible Incompleteness Restarted/1 9/23/19 11:19PM
828: Tangible Incompleteness Restarted/2 9/23/19 11:19PM
829: Tangible Incompleteness Restarted/3 9/23/19 11:20PM
830: Tangible Incompleteness Restarted/4 9/26/19 1:17 PM
831: Tangible Incompleteness Restarted/5 9/29/19 2:54AM
832: Tangible Incompleteness Restarted/6 10/2/19 1:15PM
833: Tangible Incompleteness Restarted/7 10/5/19 2:34PM
834: Tangible Incompleteness Restarted/8 10/10/19 5:02PM
835: Tangible Incompleteness Restarted/9 10/13/19 4:50AM
836: Tangible Incompleteness Restarted/10 10/14/19 12:34PM
837: Tangible Incompleteness Restarted/11 10/18/20 02:58AM
838: New Tangible Incompleteness/1 1/11/20 1:04PM
839: New Tangible Incompleteness/2 1/13/20 1:10 PM
840: New Tangible Incompleteness/3 1/14/20 4:50PM
841: New Tangible Incompleteness/4 1/15/20 1:58PM
842: Gromov's "most powerful language" and set theory 2/8/20 2:53AM
843: Brand New Tangible Incompleteness/1 3/22/20 10:50PM
844: Brand New Tangible Incompleteness/2 3/24/20 12:37AM
845: Brand New Tangible Incompleteness/3 3/28/20 7:25AM
846: Brand New Tangible Incompleteness/4 4/1/20 12:32 AM
847: Brand New Tangible Incompleteness/5 4/9/20 1 34AM
848. Set Equation Theory/1 4/15 11:45PM
849. Set Equation Theory/2 4/16/20 4:50PM
850: Set Equation Theory/3 4/26/20 12:06AM
851: Product Inequality Theory/1 4/29/20 12:08AM
852: Order Theoretic Maximality/1 4/30/20 7:17PM
853: Embedded Maximality (revisited)/1 5/3/20 10:19PM
854: Lower R Invariant Maximal Sets/1: 5/14/20 11:32PM
855: Lower Equivalent and Stable Maximal Sets/1 5/17/20 4:25PM
856: Finite Increasing reducers/1 6/18/20 4 17PM :
857: Finite Increasing reducers/2 6/16/20 6:30PM
858: Mathematical Representations of Ordinals/1 6/18/20 3:30AM
859. Incompleteness by Effectivization/1 6/19/20 1132PM :
Harvey Friedman
More information about the FOM
mailing list