[FOM] 803: Perfectly Natural/7

[Harvey Friedman]

There was an ERROR in the explicitly Pi01 statements discussed in

https://cs.nyu.edu/pipermail/fom/2018-April/020906.html #800
https://cs.nyu.edu/pipermail/fom/2018-March/020900.html #798

and also in

https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#102, 103 Explicitly Pi01 Status 4/9/18

These #102, 103 have been replaced by the new #102:

https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#102, April 9, 2018.

The usual complementation A' that I was using inside N behaves rather
badly, as it is too large, and so I must use a different
complementation - and that destroys enough of the implicitly of the
statements, that I reconsidered the entire situation.

In fact, what I came up with now I like better than what I was doing before!

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

ABSTRACT. We begin with the upper image equation A È. R<[A] = Nk. In
the infinite case, we have known relation R ÍNk´Nkand unknown set A
ÍNk. In the finite case, we have known R Í[t]2kand unknown A Í[t]k.
This equation (and obvious variants) is easily seen to have a unique
solution by the Contraction Mapping Theorem (or by direct
combinatorial construction). We focus on order invariant R where these
unique A - called the Complementation of R - raise various
computational complexity and algorithmic solvability issues. We define
the Weak Complementations of R as those A for which A È. R<[A]
contains Bk, where B is the set of all numbers "generated" by R,A
through a simple process which starts with 1,2,4,8,... . Weak
Complementations are generally not unique. We initiate an
investigation into the structure of Weak Complementations, proving
that every order invariant R has a Weak Complementation with a wide
range of simple properties. Many of these results can only be proved
by going well beyond the usual ZFC axioms, using large cardinal
hypotheses. In the infinite case (on Nk), the statements are
implicitly P01. In the finite case (on [t]k), the statements are
explicitly P01. The logical strengths of the resulting statements are
expected to correspond exactly to a large variety of systems ranging
from, e.g., PA and its standard fragments to Z2 and 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) Mahlo cardinals to weakly
compact cardinals to (higher order) subtle, ineffable and SRP
cardinals. Some expectations that have already been realized are
discussed.

1. Definitions.
2. Complementations.
3. Weak Complementations.
4. Omissions.
5. Remarks.

************************************************************************
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 803rd 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

Harvey Friedman