[FOM] 804: Beyond Perfectly Natural/8

[Harvey Friedman]

There has been a substantial Thematic Improvement in the explicitly
Pi01 statements corresponding to SRP. We have placed a new manuscript
at

https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
103.  Explicitly Pi01 Status – 4/14/18. 5 pages. Presents favorite
explicitly Pi01 statements requiring large cardinals as of 4/12/18.
Improves 102 but does not obsolete it.

EXPLICITLY P01STATUS 4/12/18
by
Harvey M. Friedman
University Professor of Mathematics, Philosophy, Computer Science Emeritus
Ohio State University
Columbus, Ohio
April 12, 2018

ABSTRACT. We begin with the upper image equation A È. R<[A] = N^k,
where R containedin N^k x N^k is the known and A containedin N^k is
the unknown. In the finite case, R containedin [t]^k x [t]^k is the
known and A containedin [t]^k is the unknown. This equation (and
obvious variants) is easily seen to have a unique solution by the
Contraction Mapping Theorem (or by direct combinatorial construction).
Even for very explicit R (order invariant), these unique A are
computationally complete - and are called the Complementations of R.
We define Approximate Complementations (Complementations/r) where it
is only required that the upper image equation holds for tuples that
are generated by a natural r-fold process starting from 1,2,4,8,... .
We lose uniqueness but we show that we gain solutions with very
desirable properties. In particular, we show that we can always find a
Complementation/r that is self embedded by the function n if n < s; 2n
if n >= s, provided s >> k,r. However, to obtain such
Complementations/r, it is necessary and sufficient to go well beyond
the usual ZFC axioms for mathematics. This is required even in the
finite case over [t], where the statements are explicitly Pi01. The
logical strengths of these statements and variants are expected to
correspond exactly to a large variety of formal systems ranging from,
e.g., PA and its standard fragments to Z2and its standard fragments to
weak ZC and its standard fragments (including higher order
arithmetics) to various strong fragments of ZFC to ZFC to various
large cardinal extensions of ZFC including (higher order) inaccessible
cardinals to (higher order) strongly Mahlo cardinals to weakly compact
cardinals to (higher order) subtle, ineffable and SRP cardinals. Some
expectations that have already been realized are discussed here.

1. Definitions.
2. Complementations.
3. Approximate Complementations.
4. Embeddings.
5. Remark.

************************************************************************
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 804th 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

Harvey Friedman