931: Tangible Indiscernibles/2

[Harvey Friedman]

See 930: Tangible Indiscernibles/1
https://cs.nyu.edu/pipermail/fom/2022-May/023256.html for background.

SECTIONAL INDISCERNIBLES provides the strong connection between basic
features of some core mathematical objects and our Tangible Incompleteness.
The polished presentation of Tangible Incompleteness should now go
smoothly. We use the connection to confidently pick a certain
preferred form of the independent statement.

I will therefore put aside various important additional issues until this
is completed. Additional issues include incompleteness in low dimensions,
use of attractive weakened forms of the Sectional Indiscernibles still
yielding strength, moving from multidimensional sets to multidimensional
functions, and various additional adventures.

There are really TWO major parts of our Tangible Incompleteness. The first
is the one I was referring to just now, that has the direct connection with
core mathematics through SECTIONAL INDISCERNIBLES. The statement is
implicitly Pi01. As indicated above, we will have only two versions: one
with sets/emulators and one with order invariant sets/squares. These two
versions are easily proved to be equivalent. Both have their advantages and
disadvantages with somewhat different audiences. For the professional math
community the order invariant sets/maximal squares are preferred.

The second major part of Tangible Incompleteness develops nondeterministic
algorithms processing finite objects. The Intangible Incompletenss asserts
that these algorithms can be executed for any given finite number of steps.
This is explicitly Pi01.

The nondeterministic algorithms are in the style of standard greedy
algorithms but where the greed is relaxed in favor of demanding invariance
or symmetry conditions on the output. These algorithms are much simpler
than what normally arises in computer science.

This explicitly Pi01 algorithmic approach is what is best suited for
explicitly Pi01 and also for achieving the much greater strength of the
higher large cardinals such as the HUGE cardinal hierarchy and even higher.

********************************************

Here we discuss Indiscernibles and Sectional Indiscernibles in some core
mathematical objects. This is preliminary to us working with Indiscernibles
and Sectional Indiscernibles in MAXIMAL objects, which throws us outside of
what ZFC can really handle.

1. ORDER EQUIVALENCE

Let (X,<) be a linear ordering and x,y in X^k. x,y are order equivalent if
and only if for all 1 <= i,j <= k, x_i < x_j iff y_i < y_j.

Throughout this development, we use X = (X,<) for a linearly ordered set X.
Most often, X is N, Z, Q, R.

2. INTUITIVE IMPORTANCE OF ORDER EQUIVALENCE

Let X be an arbitrary set of arbitrary objects, which are totally general.
We know nothing. So any two elements of X "cannot be distinguished".

Which elements of X^2 can be "distinguished"? Well (x,y) might have x = y
and (z,w) might have z < w. We have just "distinguished them". It is clear
that we can "distinguish" (x,y) and (z,w) if they are not order equivalent.
But conversely, what if (x,y) and (z,w) are order equivalent?
Intuitively we will NOT be able to distinguish them "knowing nothing" about
(X,<). Thus, intuitively, u,v in X^2 are "indistinguishable" if and only if
u,v are order equivalent.

These remarks scale upwards to any dimension k >= 1.

Order equivalence is the weakest "reasonable" equivalence relation on X^k,
"knowing nothing about X". There are various ways to rigorize this
principle using mathematical logic. We will not go further with this here.

3. INDISCERNIBLES

Let S be a subset of X^k. E is a set of indiscernibles for S if and only if
for all order equivalent x,y in E^k, x in S iff y in S.

The idea here is that "from the point of view of mere membership in S, we
cannot tell anything about the k-tuples from E except the obvious". Hence
the word "indiscernible". However, this may not be the case if we use S in
ways beyond mere membership. For instance, even in dimension 1, one of the
indiscernibles might be a limit point of S whereas other indiscernibles are
not.

4. FUNDAMENTAL RAMSEY THEOREMS
Ramsey, F.P. (1929). *Proc. London Math. Soc*. *30*: 264–286. doi
<https://en.wikipedia.org/wiki/Doi_(identifier)>:10.1112/plms/s2-30.1.264
<https://doi.org/10.1112%2Fplms%2Fs2-30.1.264>.

THEOREM 4.1.. Let S be a subset of X^k, X infinite. Then S has an infinite
SOI. The infinite SOI can be taken to be a subset of any infinite subset of
X given in advance.

THEOREM 4.2. For all k,n >= 1 there exists r >= 1 such that the following
holds. Assume X has at least r elements. Every subset S of X^k has a SOI of
cardinality n.

There are many further results along these lines, falling under the name
Ramsey Theory. See. e.g., Graham, Rothshild, Spencer..
https://www.amazon.com/Ramsey-Theory-2nd-Ronald-Graham/dp/0471500461 Absurd
price, however.

INDISCERNIBLES IN MATHEMATICS

Let S be a piecewise linear subset of R^k.  I.e., S is a Boolean
combination of linear inequalities. We have already seen from Theorem 1
that S has an infinite SOI. But can we find an uncountable SOI for S?

In one dimension, obviously S contains or is disjoint from an uncountable
and even cardinality c set. So there is an SOI of cardinality c in one
dimension.This is of course works for any S containedin R, not using that S
is piecewise linear.

Now look at 3 dimensions. Set S = {(x,y,z): |x-y| < |y - z|}. Let E
containedin R be uncountable. Let x < y be two limit points of E. Let
|x-x'| and |y-y'| < |x-y|/4. Then (x,x',y) and (x',x,y) lie in S and
(x,y,y'), (x,y',y) lie outside of S. So in 3 dimensions we don't get an
uncountable SOI.

What about 2 dimensions? It is easy to see that for every piecewise linear
S containedin R, some nonempty open interval is an SOI.

Also, the above applies to the wider class of semi algebraic subsets of R^k
(Boolean combinations of polynomial inequalities), and the smaller class of
rational piecewise linear subsets of R^k over Q.

5. UNIVERSAL INDISCERNIBLES IN MATHEMATICS

Let W be a family of subsets of X^k. E is a universal SOI for W if and only
if E is an SOI for all S in W,

All universal SOI for the family of piecewise linear subsets of R^k have at
most one element. For if x < y lie in the universal SOI, then use
{(x,...,x)} and {(y,...,y)}.

Moreover, all universal SOI for the family of rational piecewise linear
subsets of R^k have at most one element. For if x < y lie in the universal
SOI, then use {(u,...,u): p < u}, where x < p < y, p rational.

On the other hand, the following is easy to obtain from Theorem 4.1.

THEOREM 5.1.  Let S be a finite family of subsets of X^k. Then S has an
infinite universal SOI. The infinite universal SOI can be taken to be a
subset of any infinite subset of X given in advance.

6. ALMOST UNIVERSAL INDISCERNIBLES IN MATHEMATICS

Let W be a family of subsets of X. E is an almost universal SOI for W if
and only if E is infinite and for all S in W, we can remove finitely many
elements of E and obtain an SOI for S.

THEOREM 6.1. Let W be a countable family of subsets of X^k. There is an
almost universal countable SOI E for W. We can take E to be a subset of any
countably infinite subset of X given in advance.

THEOREM 6.2. The family of all piecewise linear subsets of R^k has an
almost universal SOI. In fact, the range of any sequence of positive real
numbers whose xn+1/xn goes to infinity is an almost universal SOI.

THEOREM 6.3. The family of all semi algebraic subsets of R^k has an almost
universal SOI. In fact, the range of any sequence of positive real numbers
whose log(xn+1)/log(xn) goes to infinity is an almost universal SOI.

QUESTIONS. How can we characterize exactly the almost universal SOIs for
the family of all piecewise linear subsets of R^k and the family of all
semialgebraic subsets of R^k? What about uncountable (closed) almost
universal SOIs?

##########################################

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 931st 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-899 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

900: Ultra Convergence/2  10/3/21 12:35AM
901: Remarks on Reverse Mathematics/6  10/4/21 5:55AM
902: Mathematical L and OD/RM  10/7/21  5:13AM
903: Foundations of Large Cardinals/1  10/12/21 12:58AM
904: Foundations of Large Cardinals/2  10/13/21 3:17PM
905: Foundations of Large Cardinals/3  10/13/21 3:17PM
906: Foundations of Large Cardinals/4  10/13/21  3:17PM
907: Base Theory Proposals for Third Order RM/1  10/13/21 10:22PM
908: Base Theory Proposals for Third Order RM/2  10/17/21 3:15PM
909: Base Theory Proposals for Third Order RM/3  10/17/21 3:25PM
910: Base Theory Proposals for Third Order RM/4  10/17/21 3:36PM
911: Ultra Convergence/3  1017/21  4:33PM
912: Base Theory Proposals for Third Order RM/5  10/18/21 7:22PM
913: Base Theory Proposals for Third Order RM/6  10/18/21 7:23PM
914: Base Theory Proposals for Third Order RM/7  10/20/21 12:39PM
915: Base Theory Proposals for Third Order RM/8  10/20/21 7:48PM
916: Tangible Incompleteness and Clique Construction/1  12/8/21   7:25PM
917: Proof Theory of Arithmetic/1  12/8/21  7:43PM
918: Tangible Incompleteness and Clique Construction/1  12/11/21  10:15PM
919: Proof Theory of Arithmetic/2  12/11/21  10:17PM
920: Polynomials and PA  1/7/22  4:35PM
921: Polynomials and PA/2  1/9/22  6:57 PM
922: WQO Games  1/10/22 5:32AM
923: Polynomials and PA/3  1/11/22  10:30 PM
924: Polynomials and PA/4  1/13/22  2:02 AM
925: Polynomials and PA/5  2/1/22  9::04PM
926: Polynomials and PA/6  2/1/22 11:20AM
927: Order Invariant Games/1  03/04/22  9:11AM
928: Order Invariant Games/2  03/7/22  4:22AM
929: Physical Infinity/randomness  *3/21/22 02:14AM *
930: Tangible Indiscernibles/1  *5/7/22 7:46PM *

Harvey Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20220514/680f8c44/attachment-0001.html>