[FOM] 558: New Pi01/more
Harvey Friedman
hmflogic at gmail.com
Fri Oct 31 22:01:01 EDT 2014
Here we improve on
http://www.cs.nyu.edu/pipermail/fom/2014-October/018349.html in some
important ways.
In this posting, we will work entirely in N and not use order invariance at all.
In http://www.cs.nyu.edu/pipermail/fom/2014-October/018349.html we had
+1 built into the notion of reduction. We now use reduction in its
purest form without building in +1.
DEFINITION 1. Let R be contained in N^2k = N^k x N^k. x reduces to y
if and only if x R y and max(x) > max(y). S is irreducible in R if and
only if S containedin N^k and no element of S reduces to any element
of S.
DEFINITION 2. Let R containedin N^2k. A_1 red ... red A_r for S if and only if
i. A_1,...,A_r are subsets of N.
ii. S is a subset of N^k.
iii. Every element of (A_i )^k\S reduces to an element of A_i+1 intersect S.
ZFC is insufficient to handle matters even for r = 4. So we will
concentrate on r = 4 at this point.
PROPOSITION 1. Every R containedin N^2k has an irreducible set for
which some infinite A red B red C red D has B+1 containedin C\A.
NOTE: Officially, we take "infinite" here to apply to A,B,C,D.
However, we can take "infinite" to apply to just A and obtain the same
results.
THEOREM 2. Proposition 1 is provably equivalent to Con(SMAH) over ACA.
We haven't yet seriously tried to reduce the base theory ACA. Here
SMAH is the strongly Mahlo cardinal hierarchy.
TEMPLATE A. Every R containedin N^2k has an irreducible set for which
some infinite A red B red C red D has a given Boolean equation in
A,B,C,D,A+1,B+1,C+1,D+1.
Of course, we want to handle Boolean equations in infinite A_1,...,A_n.
What about explicitly finite versions? Here we use order invariance.
The first step is to simply move to order invariant R.
PROPOSITION 3. Every order invariant R containedin N^2k has an
irreducible set for which some infinite A red B red C red D has B+1
containedin C\A.
Order invariance allows us to be specific about A. We write E! = {n!: n in E}.
PROPOSITION 4. Every order invariant R containedin N^2k has an
irreducible set for which some infinite (8kN)! red B red C red D has
B+1 containedin C\(8kN)!.
Then we can move to the finite rather smoothly.We write [r] = {0,...,r}.
PROPOSITION 5. Every order invariant R containedin N^2k has a finite
irreducible set for which some finite (8k[r])! red B red C red D has
B+1 containedin C\(8k[r])!. We can require the irreducible set and
B,C,D to live <= (8kr)!+1.
THEOREM 7. Propositions 3-5 are provably equivalent to Con(SMAH) over ACA.
************************************************************
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 558th 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-527 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2014-August/018092.html
528: More Perfect Pi01 8/16/14 5:19AM
529: Yet more Perfect Pi01 8/18/14 5:50AM
530: Friendlier Perfect Pi01
531: General Theory/Perfect Pi01 8/22/14 5:16PM
532: More General Theory/Perfect Pi01 8/23/14 7:32AM
533: Progress - General Theory/Perfect Pi01 8/25/14 1:17AM
534: Perfect Explicitly Pi01 8/27/14 10:40AM
535: Updated Perfect Explicitly Pi01 8/30/14 2:39PM
536: Pi01 Progress 9/1/14 11:31AM
537: Pi01/Flat Pics/Testing 9/6/14 12:49AM
538: Progress Pi01 9/6/14 11:31PM
539: Absolute Perfect Naturalness 9/7/14 9:00PM
540: SRM/Comparability 9/8/14 12:03AM
541: Master Templates 9/9/14 12:41AM
542: Templates/LC shadow 9/10/14 12:44AM
543: New Explicitly Pi01 9/10/14 11:17PM
544: Initial Maximality/HUGE 9/12/14 8:07PM
545: Set Theoretic Consistency/SRM/SRP 9/14/14 10:06PM
546: New Pi01/solving CH 9/26/14 12:05AM
547: Conservative Growth - Triples 9/29/14 11:34PM
548: New Explicitly Pi01 10/4/14 8:45PM
549: Conservative Growth - beyond triples 10/6/14 1:31AM
550: Foundational Methodology 1/Maximality 10/17/14 5:43AM
551: Foundational Methodology 2/Maximality 10/19/14 3:06AM
552: Foundational Methodology 3/Maximality 10/21/14 9:59AM
553: Foundational Methodology 4/Maximality 10/21/14 11:57AM
554: Foundational Methodology 5/Maximality 10/26/14 3:17AM
555: Foundational Methodology 6/Maximality 10/29/14 12:32PM
556: Flat Foundations 1 10/29/14 4:07PM
557: New Pi01 10/30/14 2:05PM
Harvey Friedman
More information about the FOM
mailing list