[FOM] 680: Large Cardinals and Continuations/1

[Harvey Friedman]

THIS POSTING IS ENTIRELY SELF CONTAINED

After making these connections, I hope to become inspired by the
growth of biological organisms as discussed in articles such as
https://en.wikipedia.org/wiki/Simulated_growth_of_plants and
references therein.

LARGE CARDINALS AND CONTINUATIONS 1
May 29, 2016

1. Symmetries in N
2. Symmetries in the Ordinals
3. Symmetries in Infinite Continuations
4. Symmetries in Finite Perpetuations
5. Seeds to Plants
6. Comments

1. SYMMETRIES IN N

DEFINITION 1.1. Q,N,Z are the set of all rationals, nonnegaitve
integers, and integers, respectively. p,q range over rationals and
n,m,r,s,t range over positive integers, with or without subscripts,
unless indicated otherwise.

DEFINITION 1.2. Let R containedin E^k. R is partially self embedded by
h if and only if h is a partial one-one function :from E into E, where
 for all x_1,...,x_k in dom(h), (x_1,...,x_k) in V iff
(f(x_1),...,f(x_k)) in V.

We think of partial self embeddings as representing a kind of symmetry.

DEFINITION 1.3. Let A containedin N. f_A is the increasing bijection
from A\{max(A)} onto A\{min(A)}.

Self embedding by f_A exhibits a special kind of symmetry.

P(N^k,n). Every R containedin N^k is partially self embedded by some
f_A, |A| = n.

P(N^k,omega). Every R containedin N^k is partially self embedded by
some f_A, A infinite.

THEOREM 1.1. P(N^k,n) holds in the strong sense that the A's can be
chosen below a number depending only on k,n. That number is an
iterated exponential in n of length roughly k, and this is best
possible.

Proof: See http://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/?preview_id=28&preview_nonce=ca9862f157&preview=true
23. Adjacent Ramsey Theory, October 2, 1999, 3 pages, draft.

THEOREM 1.2. P(N^k,omega) holds. The scheme over k is equivalent to
ACA_0 over RCA_0. The full statement is equivalent to "every iterated
Turing jump of every x exists" over RCA_0.

Proof: Use k = 3 to get jump. Let R(a,b,c) if and only if a < b < c,
and every i <= a has a witness <= b for lying in W if and only if it
has a witness <= c for lying in W. Let A = {a_1 < a_2 < ...} be given.
Let R(a_1,a_n,a_n+c). Then R(a_1+c,a_n+c,a_n+2c),
R(a_1+2c,a_n+2c,a_n+3c),... hold, and in particular R(a_1,a_n,a_n+c),
R(a_1,a_n+c,a_n+2c),... hold. Therefore every i <= a_1 has a witness
<= a_n for lying in W iff i is in W.

Now R(a_2,a_n+1,a_n+c+1). Repeat the above argument to show that every
i <= a_2 has a witness for lying in W iff i is in W.

So i in W iff i in W has a witness <= a_n+c+1, where i <= a_n. QED

We consider a stronger kind of symmetry.

DEFINITION 1.4. Let A containedin N. h_A is the increasing bijection
from A\{max(A)} union [0,min(A)) onto A\{min(A)} union [0,min(A)).

P'(N^k,n). Every R containedin N^k is partially self embedded by some
h_A, |A| = n.

P'(N^k,omega). Every R containedin N^k is partially self embedded by
some f_A, A infinite.

Unfortunately, these lead only to trivialities.

THEOREM 1.3. P'(N^k,n) if and only if k = 1 or n <= 1. P'(N^k,omega)
if and only if k = 1.

Proof: Use R(n,m) iff n = m+1. QED

Thus we see that we need limit points for this kind of symmetry.

2. SYMMETRIES IN THE ORDINALS

We now shift the setting to the ordinals. Recall that every ordinal is
the set of its strict predecessors.

DEFINITION 2.1. Let A containedin lambda, lambda a limit ordinal. h_A
is the increasing bijection from A\{max(A)} union min(A) onto
A\{min(A)} union min(A).

W(lambda^k,n). Every R containedin lambda^k is partially self embedded
by some h_A, |A| = n.

W(lambda^k,omega). Every R containedin N^k is partially self embedded
by some h_A, A of order type omega.

THEOREM 2.1. (ZFC) The following are equivalent.
i. There exists lambda such that W(lambda^2,2).
ii. There exists lambda such that W(lambda^2,omega).
iii. There exists a subtle cardinal.

Subtle cardinals are far higher than what one can see in ZFC, but
provably exist in SRP.

THEOREM 2.2. (ZFC) SRP is equivalent to the schemes "there exists
lambda such thatW'(lambda^k,k)", "there exists lambda such that
W(lambda^k,omega)" over k.

THEOREM 2.3. (ZFC) SRP+ is equivalent to
i. For all k there exists lambda such that W(lambda^k,k).
ii. There exists lambda such that for all k, W(Lambda^k,omega).

3. SYMMETRIES IN INFINITE CONTINUATIONS

We continue to use Definition 1.1.

DEFINITION 3.1. U. indicates disjoint union. Q^k|<p,
Q^k|<=p is the set of all k-tuples of rationals <p, <=p, respectively.

DEFINITION 3.2. A,B containedin Q^k are isomorphic if and only if
there is an increasing bijection h from the set of all coordinates of
elements of A, onto the set of all coordinates of elements of B, such
that for all x in dom(h)^k, x in A iff hx in B.

We will only need to use isomorphisms between A,B containedin Q^k of
cardinalities 2 and 3.

DEFINItiON 3.3. S is a continuation (perpetuation) of V containedin
Q^k if and only if V containedin S containedin Q^k|<=k, and every
subset of S of cardinality 2 (3) is isomorphic to some subset of V. S
is a maximal continuation (perpetuation) of V containedin Q^k if and
only if S is a continuation (perpetuation) of V containedin Q^k, where
no S U. {x} is a continuation (perpetuation) of V containedin Q^k.

THEOREM 3.1. Every finite subset of Q^k|<=k has a maximal continuation
(perpetuation).

EMBEDDED MAXIMAL CONTINUATIONS. EMC. For finite subsets of Q^k|<0,
some maximal continuation (perpetuation) is partially self embedded by
the function p if p < 0; p+1 if p = 0,...,k-1.

THEOREM 2.2. EMC (both forms) is implicitly Pi01 via the Goedel
Completeness Theorem.

THEOREM 2.3. EMC (both forms) is provably equivalent to Con(SRP) over WKL_0.

4. SYMMETRIES IN FINITE, PERPETUATIONS

The following notion of height is widely used in number theory.

DEFINITION 4.1. Let V containedin Q^k be finite. The height of V is
the least t such that every coordinate of every element of R can be
written as the ratio between two integers of magnitude at most t.

DEFINITION 4.2. S is a rich continuation (perpetuation) of finite V
containedin Q^k if and only if S is a continuation (perpetuation) of V
containedin Q^k, where no S U. {x} is a continuation (perpetuation) of
V containedin Q^k with {x} of height at most that of V.

THEOREM 4.1. Every finite subset of Q^k|<0 has a finite rich
continuation (perpetuation).

THEOREM 4.2. For finite subsets of Q^k|<0, some finite rich
perpetuation is partially self embedded by the function
p if p < 0; p+1 if p = 0,...,k-1.

FINITE EMBEDDED RICH PERPETUATIONS. FERP. For finite subsets of Q^k|<0,
some two successive finite rich perpetuations are partially self
embedded by the function p if p < 0; p+1 if p = 0,...,k-1.

FERP is explicitly Pi02. However, it is easy to give a priori bounds
on the heights of the S,T. This converts them into explicitly Pi01
forms.

THEOREM 4.3. FERP is provably equivalent to Con(SRP) over EFA.

5. SEEDS TO PLANTS

We can think of the subset of Q^k|<0 as a seed below ground that is
growing into the maximal continuation subject to the height
restriction k. During this plant growth, it is required that all
patterns in tiny pieces of the plants are already present in the
original seed below ground. The existence of the explicitly given
partial embedding is conceptually related to the striking symmetries present
in plants grown from seeds.

6. PLANS

In the full paper, we will also present these results in significantly
greater generality, still preserving these headline statements.

Also in the full paper, we will present the best of the earlier
results, as many are perfectly natural and still have some valuable
features and are not obsolete. In particular, statements involving
order invariant sets of tuples of rationals.

But we are convinced that this Continuation/Perpetuation approach has
the best promise of major interaction with mathematics and science,
generally.

***********************************************
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 680th 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-599 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2015-August/018887.html

600: Removing Deep Pathology 1  8/15/15  10:37PM
601: Finite Emulation Theory 1/perfect?  8/22/15  1:17AM
602: Removing Deep Pathology 2  8/23/15  6:35PM
603: Removing Deep Pathology 3  8/25/15  10:24AM
604: Finite Emulation Theory 2  8/26/15  2:54PM
605: Integer and Real Functions  8/27/15  1:50PM
606: Simple Theory of Types  8/29/15  6:30PM
607: Hindman's Theorem  8/30/15  3:58PM
608: Integer and Real Functions 2  9/1/15  6:40AM
609. Finite Continuation Theory 17  9/315  1:17PM
610: Function Continuation Theory 1  9/4/15  3:40PM
611: Function Emulation/Continuation Theory 2  9/8/15  12:58AM
612: Binary Operation Emulation and Continuation 1  9/7/15  4:35PM
613: Optimal Function Theory 1  9/13/15  11:30AM
614: Adventures in Formalization 1  9/14/15  1:43PM
615: Adventures in Formalization 2  9/14/15  1:44PM
616: Adventures in Formalization 3  9/14/15  1:45PM
617: Removing Connectives 1  9/115/15  7:47AM
618: Adventures in Formalization 4  9/15/15  3:07PM
619: Nonstandardism 1  9/17/15  9:57AM
620: Nonstandardism 2  9/18/15  2:12AM
621: Adventures in Formalization  5  9/18/15  12:54PM
622: Adventures in Formalization 6  9/29/15  3:33AM
623: Optimal Function Theory 2  9/22/15  12:02AM
624: Optimal Function Theory 3  9/22/15  11:18AM
625: Optimal Function Theory 4  9/23/15  10:16PM
626: Optimal Function Theory 5  9/2515  10:26PM
627: Optimal Function Theory 6  9/29/15  2:21AM
628: Optimal Function Theory 7  10/2/15  6:23PM
629: Boolean Algebra/Simplicity  10/3/15  9:41AM
630: Optimal Function Theory 8  10/3/15  6PM
631: Order Theoretic Optimization 1  10/1215  12:16AM
632: Rigorous Formalization of Mathematics 1  10/13/15  8:12PM
633: Constrained Function Theory 1  10/18/15 1AM
634: Fixed Point Minimization 1  10/20/15  11:47PM
635: Fixed Point Minimization 2  10/21/15  11:52PM
636: Fixed Point Minimization 3  10/22/15  5:49PM
637: Progress in Pi01 Incompleteness 1  10/25/15  8:45PM
638: Rigorous Formalization of Mathematics 2  10/25/15 10:47PM
639: Progress in Pi01 Incompleteness 2  10/27/15  10:38PM
640: Progress in Pi01 Incompleteness 3  10/30/15  2:30PM
641: Progress in Pi01 Incompleteness 4  10/31/15  8:12PM
642: Rigorous Formalization of Mathematics 3
643: Constrained Subsets of N, #1  11/3/15  11:57PM
644: Fixed Point Selectors 1  11/16/15  8:38AM
645: Fixed Point Minimizers #1  11/22/15  7:46PM
646: Philosophy of Incompleteness 1  Nov 24 17:19:46 EST 2015
647: General Incompleteness almost everywhere 1  11/30/15  6:52PM
648: Necessary Irrelevance 1  12/21/15  4:01AM
649: Necessary Irrelevance 2  12/21/15  8:53PM
650: Necessary Irrelevance 3  12/24/15  2:42AM
651: Pi01 Incompleteness Update  2/2/16  7:58AM
652: Pi01 Incompleteness Update/2  2/7/16  10:06PM
653: Pi01 Incompleteness/SRP,HUGE  2/8/16  3:20PM
654: Theory Inspired by Automated Proving 1  2/11/16  2:55AM
655: Pi01 Incompleteness/SRP,HUGE/2  2/12/16  11:40PM
656: Pi01 Incompleteness/SRP,HUGE/3  2/13/16  1:21PM
657: Definitional Complexity Theory 1  2/15/16  12:39AM
658: Definitional Complexity Theory 2  2/15/16  5:28AM
659: Pi01 Incompleteness/SRP,HUGE/4  2/22/16  4:26PM
660: Pi01 Incompleteness/SRP,HUGE/5  2/22/16  11:57PM
661: Pi01 Incompleteness/SRP,HUGE/6  2/24/16  1:12PM
662: Pi01 Incompleteness/SRP,HUGE/7  2/25/16  1:04AM
663: Pi01 Incompleteness/SRP,HUGE/8  2/25/16  3:59PM
664: Unsolvability in Number Theory  3/1/16  8:04AM
665: Pi01 Incompleteness/SRP,HUGE/9  3/1/16  9:07PM
666: Pi01 Incompleteness/SRP,HUGE/10  13/18/16  10:43AM
667: Pi01 Incompleteness/SRP,HUGE/11  3/24/16  9:56PM
668: Pi01 Incompleteness/SRP,HUGE/12  4/7/16  6:33PM
669: Pi01 Incompleteness/SRP,HUGE/13  4/17/16  2:51PM
670: Pi01 Incompleteness/SRP,HUGE/14  4/28/16  1:40AM
671: Pi01 Incompleteness/SRP,HUGE/15  4/30/16  12:03AM
672: Refuting the Continuum Hypothesis?  5/1/16  1:11AM
673: Pi01 Incompleteness/SRP,HUGE/16  5/1/16  11:27PM
674: Refuting the Continuum Hypothesis?/2  5/4/16  2:36AM
675: Embedded Maximality and Pi01 Incompleteness/1  5/7/16  12:45AM
676: Refuting the Continuum Hypothesis?/3  5/10/16  3:30AM
677: Embedded Maximality and Pi01 Incompleteness/2  5/17/16  7:50PM
678: Symmetric Optimality and Pi01 Incompleteness/1  5/19/16  1:22AM
679: Symmetric Maximality and Pi01 Incompleteness/1  5/23/16  9:21PM

Harvey Friedman