[FOM] 643: Constrained Subsets of N, #1

[Harvey Friedman]

THIS POSTING IS SELF CONTAINED
this is added to the Progress in Pi01 Incompleteness 1-4 series, for
the second book on Concrete Mathematical Incompleteness.

In http://www.cs.nyu.edu/pipermail/fom/2015-October/019327.html I wrote

"I am in some preliminary discussions with an expert in mathematical
physics concerning some Concrete Incompleteness in (N,<,+). We are at
the point where the statements are being absorbed, and there is some
back and forth about ways of modifying them to resonate more from the
point of view of mathematical physics. At this point, it is not at all
clear how far this will go."

Most of the interaction has been in the context of multiple upgrades
of infinite bit sequences, where 1 is treated as "better than 0". This
was via my routine translation from statements using subsets of N, via
characteristic functions.

However, there is something that I need to do to get to large
cardinals that has not so far resonated well from the Applied
Analysis perspective. This non resonating feature - at least non
resonating at the moment - is very natural from a general mathematical point of
view. It is simply the use of addition to proscribe locations for
assering optimality. See Definition 2.1.

So it makes sense for me to spin off this Constrained Subsets of N
development as a separate subject, regardless of whether it fully
resonates with Applied Analysts. But the experience thus far suggests
that it should *partially* resonate with a significant part of the
mathematical community.

You will see below that finite sequences of subsets of N play an
essential role. This "multiple pass" idea does resonate well with
the Applied Analysis expert. I did not expect that.

It seems that "multiple passes" is natural in the context
of evolving physical systems. Multiple passes, or sequences of sets,
is something I have been avoiding in the four part Progress Series.
But as I work with subsets of N, it is very natural to use multiple passes.

An unexpected feature has emerged after finishing the four part
Progress series. I thought that when moving to subsets of N, I was
going to have to use semi linear in the hypothesis. This is the case
if I want something explicitly finite. However, if
you look at section 1 below, you will see that I don't use
semi linear, or even order invariant. The statement is still
implicitly Pi02 (not implicitly Pi01). Also the statement below is
related to  Boolean Relation Theory, with some differences
and simplifications. It is explicitly Pi12, like BRT.

CONSTRAINED SUBSETS OF N
by
Harvey M. Friedman
November 3, 2015

1. Constraints and Optimization
2. Summation Based Improvements
3. Semi Linear Constraints

1. LIBERAL CONSTRAINTS, UPGRADES, OPTIMIZATION

DEFINITION 1.1. N is the set of all nonnegative integers. A liberal k-constraint
is a nonempty family C of <=k element subsets of N, where
i. Any subset of an element of C is an element of C.
ii. If x in C has <k elements, then for all but finitely many n, x
union {n} in C.
We let C* be the set of all subsets of N all of whose <=k element subsets
lie in C.

C will always denote a liberal k-constraint. x,y,z,w will denote subsets
of N, unless indicated otherwise.

THEOREM 1.1. Every infinite x containedin N has an infinite y
containedin x lying in C*.

DEFINITION 1.2. x is optimal for C if and only if x lies in C*, and no
(x intersect {0,...,n}) disjoint union {n} lies in C*.

THEOREM 1.2. Every C has a unique optimal x. The optimal x is infinite.

2. SUMMATION BASED IMPROVEMENTS

Optimality gains its strength - its uniqueness - by using all n in
Definition 1.2. We want to approximate this requirement, by using only
some n for Definition 1.2.

In particular, we want to consider finite series of possibly non
optimal x that keep "improving" in the direction of being optimal.

DEFINITION 2.1. y additively improves x for C if and only if
i. y is a proper superset of x lying in C*.
ii. No (y intersect {0,...,n}) disjoint union {n}, n in x+x, lies in C*.

Of course, i alone would be the most obvious notion of improvement,
but we have added the summation based clause ii as a gesture toward
optimality. This weak form of optimality depends monotonically on x.
Here x+x = {i+j: i,j in x}.

Obviously, if x is the optimal element of C* then (x,x,...) is at
least close to being an infinite series of additive improvements. But
in i), we require proper inclusion. We can fix this without much
difficulty.

THEOREM 2.1. For all C, some infinite x containedin N starts an
infinite series of additive improvements.

However, we cannot place reasonable conditions on x in Theorem 2.1.
Here is a nice illustration. Recall Theorem 1.1, where we immediate
see that there are infinite x containedin 2N lying in C*.

THEOREM 2.2. There exists C such that no infinite x containedin 2N
starts an infinite series of additive improvements.

What about length r series in Theorem 2.3?

PROPOSITION 2.3. For all C,r, some infinite x containedin 2N starts a
length r series of additive improvements.

PROPOSITION 2.4. For all C,r, every infinite x containedin N has an
infinite y containedin x that starts a length r series of additive
improvements.

PROPOSITION 2.5. Let C_1,C_2.r be given. Some infinite x
containedin N starts a length r series of additive improvements for C1
and starts a length r series of additive improvements for C2.

THEOREM 2.6. Propositions 2.3 - 2.5 are provably equivalent to
1-Con(SMAH) over ACA'. For each fixed r, Propositions 2.3 - 2.5 are
provable in ACA'. These results hold even if we relativize the
Propositions to the arithmetic sets.It is refutable in RCA_0 that we
can always find a single infinite element of C* which starts
arbitrarily long finite series of additive
 mprovements.

SMAH = ZFC + {there exists a strongly k-Mahlo cardinal}_k. ACA' is
ACA_0 + "for all x,n, the n-th Turing jump of x exists".

3. SEMI LINEAR CONSTRAINTS

It is convenient to start from the beginning with a somewhat different
but closely related setup for semi linear constraints.

DEFINITION 3.1. A semi linear constraint is a condition on x
containedin N of the form

(for all n_1,...,n_k in x)(phi)

where phi is a semi linear k-ary relation. I.e., phi is a proportional
combination of linear inequalities in variables n_1,...,n_k with
integer coefficients.

DEFINITION 3.2. A semi linear constraint has the extension property if
and only if every finite set obeying the constraint is a proper subset
of a finite set obeying the constraint.

THEOREM 3.1. The set of semi linear constraints with the extension
property is algorithmically decidable. Every semi linear constraint
with the extension property is obeyed by all sets whose min and ratios
are sufficiently large.

In this section, we use K for semi linear constraints with the
extension property.

DEFINITION 3.3. x is optimal for K if and only if
i. x obeys K.
ii. No (x intersect {0,...,n}) disjoint union {n} obeys K.

THEOREM 3.2. K has a unique optimal x.

Nothing in general can be said about the optimal x for the K, as they
exhibit complete computational complexity properties.

DEFINITION 3.4. y additively improves x for K if and only if
i. y is a proper superset of x obeying K.
ii. No (y intersect {0,...,n}) disjoint union {n}, n in x+x, obeys K.

PROPOSITION 3.3.  For all K,r, some infinite geometric progression
starts a length r series of additive improvements.

PROPOSITION 3.4. For all K,r, every geometric progression (set) with a
sufficiently large min and ratio(s) starts a length r series of
additive improvements.

PROPOSITION 3.5. For all K,r, every finite geometric progression
(finite set) with sufficiently large min and ratio(s) starts a length
r series of additive improvements.

DEFINITION 3.5. The complexity of K, #(K), is the sum of the number of
variables and the magnitudes of the coefficients.

PROPOSITION 3.6. For all K,r, every finite geometric progression
(finite set) with min and ratio(s) > (8#(K))! starts a length r series
of additive improvements.

Clearly Proposition 3.5 is explicitly Pi03 and Proposition 3.6 is
explicitly Pi01 - as the series of additive improvements are trivially
controlled by the starting set.

THEOREM 3.7. Propositions 3.3 - 3.6 are provably equivalent to
Con(SMAH) over ACA'. For each fixed r, Propositions 3.3 - 3.6 are
provable in RCA_0 (EFA for 3.5, 3.6).

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

Harvey Friedman