[FOM] 603: Removing Deep Pathology 3

[Harvey Friedman]

PROBLEM. Let T be a nice set and let K be a nice family of nice
subsets of T. Can T be written as a union of elements of K? When is
there a GOOD way, when is there a way but NO good way, when is there
no way?

T = Z (the set of all integers). Seems reasonable to take K to be the
set of all translates of a given list of sets. Probably should start
thinking about the sets K of translates of a finite list of finite
sets. This latter should have a very nice combinatorial/number
theoretic answer. Another idea: take K to be not just the translates
of a given list of sets, but their affine images.

T = Q (the set of all rationals). Same considerations. Only here there
is more opportunity to look at very interesting and varied infinite
sets to be put in K.

T = R (the set of all reals). Here is presumably where deep pathology
kicks in. What is the simplest K for which we have deep pathology
here?

T = R^2. Here is where K can be made up of geometrically interesting
elements where presumably this gets interesting.

T = R^3. Very special cases discussed here, and I would like to see it
systematically discussed here. The thread got confusing and it doesn't
look systematic at all. Big variety of K's to look at made up of very
pleasing elements.

SHIPMAN WROTE

Harvey, what is the strongest form of the axiom of choice you are
familiar with such that the kind of "deep pathology" that you talk
about eliminating cannot be proven in ZF to follow from it?

ANSWER: DC.

MARTIN DAVIS WROTE

It is certainly worthwhile to study mathematical entities whose
existence can be proved but for which it can be proved that explicit
examples (using acceptable mathematical language) can not be given.
But I don't like using a pejorative term like "pathology" to describe
them. We don't know what role such things will play in future
developments, and calling them pathological simply validates what may
turn out to be simply prejudice of our day.

ANSWER:

1. I see no justification for "certainly worthwhile". What
justification? Even justifying "worthwhile" is not that easy.  By the
very nature of the deeply pathological objects we are talking about
that break the language barrier, we must be talking about studying
some explicitly nameable *category of such objects*.

2. In order to have a productive discussion, and get to the bottom of
any disagreements, we need to distinguish several senses of
"worthwhile". Here is an attempt.

3. That those particular objects or those nameable categories are of
intrinsic interest in and of their own right, just as much as lines
and circles in the Euclidian plane, finite groups, complex analytic
functions, real algebraic numbers, and so forth. Almost Every
mathematician I know, including myself, disagrees sharply with this
view

4. That those particular objects are used in an essential way to prove
theorems about the standardly nameable objects of mathematics. For the
deeply pathological objects under discussion, there are theorems going
back to Goedel to the effect that this cannot be the case. (The ones
under discussion arise from standard ZFC arguments using the axiom of
choice in an essential way). That there is a general machine which
tells us how to eliminate such objects.

5. HOWEVER, there is an interesting point about 4. Firstly, yes, we
can eliminate the axiom of choice and eliminate such objects
systematically for proving theorems about "nice objects" = the
standardly nameable objects of mathematics, but we still have some
explicit constructions of a sort that would still make almost all
mathematicians rather uncomfortable. So it is of considerable interest
to me to i) compile a list of situations where mathematicians have
been using deep pathology in the present sense to prove theorems about
"nice" objects ii) find more delicate tools to eliminate the deep
pathology.

6. I have been talking to my coauthor, an analyst with very broad
interests, about this, and he came up with some examples. Actually, I
knew about some and vaguely knew about others in the category of
examples he has found. I will take a look. I think that there is a
very effective "elimination by countable approximation" in this
category of situations. If my memory serves me right, this was in the
folklore a way back among some logicians, but the method of countable
approximation does not really get below Pi12-CA0 or so, and hence
didn't really get seriously developed.

7. I am talking about the Glazer idempotent ultrafilter on N method
originally developed to prove Hindman's theorem. And then used and
elaborated on by Furstenburg and associates in ergodic theory, which
also is used by them to prove more countably infinite combinatorial
theorems. Heinemann's theorem, and probably most, maybe not all, of
Furstenburg people applications, have seemingly totally different
alternative proofs that do not come anywhere near any deep pathology.

NEIL TENNANT WROTE:

What about pathologies of *proof*, in addition to pathologies in the
properties of certain mathematical objects?
One could take the view that fallacies of irrelevance are
proof-pathologies. They are not needed for mathematical reasoning;
they should be expunged.

ANSWER: There is only one successful attempt I know of to make an
interesting robust distinction at the LOGICAL REASONING LEVEL (not the
nature of the objects, or the proper axioms used) in actual
mathematical reasoning. That is the distinction between the
constructive (in and about banning the law of excluded middle) and the
nonconstructive (in and about allowing the law of excluded middle). I
know of no other for actual mathematical reasoning, and would be
extremely interested to see and investigate such.

What needs to be done is this. Come up with, say, one example from
undergrad number theory, and one example from undergrad set theory,
with the following features.

1. The usual proof has certain features that can be viewed as dubious
or undesirable from some arguably coherent viewpoint.
2. Display an actual reworking of the proof that eliminates these
dubious or undesirable features.
3. Or instead prove that no such elimination is possible.
4. Determine to what extent mathematicians have avoided or not avoided
giving proofs with such features.
5. In the case of constructively, we have delicious theorems which
provide obviously important information automatically from the fact
that we have given a constructive proof. E.g., algorithms and
continuity, automatically.
6. If possible, show here that one has some sort of similar gain of
information if one avoids the alleged dubious or undesirable features.
7. In general, it is important to go beyond toy examples as much as is
feasible.

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

I have a new name for what I am mostly doing in this series:

*Removing Deep Pathology through Borelian Mathematics*

Continuing from 602: Removing Deep Pathology 2

2.1. Brief replies to responses.
2.2. Robustness of Borel.

3.1. Standard Borel Spaces
3.2. Borel and Borelian Structures
3.3. Some Miscellaneous Borelian Results

3.1. STANDARD BOREL SPACES

There is an incredible amount of robustness of Borel, and what I said
in 2.2 is not the full story.

DEFINITION. A Borel space is a pair (X,S), where X is a sigma algebra
of subsets of X. I.e., S is a nonempty family of subsets of X closed
under complements, countable unions, and countable intersections. A
set G of generators of (X,S) is a set of elements of S such that S is
the least sigma algebra of subsets of X containing G.

DEFINITION. A family of subsets of X is called separating if and only
if for all distinct x,y in X, some subset in the family contains the
point x but not the point y.

DEFINITION. A standard Borel space is a Borel space (X,S) with a
countable set of generators that is separating.

The standard Borel spaces notion is very robust.

THEOREM. Let (X,S) be a Borel space. The cardinality of X is
1,2,...,omega,c, all of which are possible. The cardinality of S is
2,4,8,16,...,c, all of which are possible. If X is countable then S is
the power set of X.If X is uncountable then S is not the power set of
X.

THEOREM. Let (X,S) be a standard Borel space and A in S. Then (A,S
intersect POW(A)) is a standard Borel space. If X is uncountable then
X can be partitioned into c many elements of S, each of cardinality c.

DEFINITION. An isomorphism between two Borel spaces (X,S), (X',S'), is
a bijection f:X onto X' which sends elements of S to elements of S'
and elements of S' back into elements of S.

THEOREM. Any two standard Borel spaces with same cardinality of points
are isomorphic. Furthermore, the functions f0g^-1 for isomorphisms f,g
from the first to the second, are exactly the isomorphisms from the
first to the first.

THEOREM. Let (X,S) be a Borel space. The following are equivalent.
i. (X,S) is a standard Borel space.
ii. X can be made into a Polish space such that S is the family of all
Borel sets in the Polish space in the usual sense.
iii. (X,S) is isomorphic to some (X',S'), where X' is a Polish space
and S' is the family of all Borel sets in X'.

This robustness robustly propagates into higher dimensions, including
countable dimension. First, there are some robust developments staying
in one dimension.

>From now on X = (X,S) and X' - (X',S') always denote standard Borel spaces.

DEFINITION. A Borel set in X is simply an element of S. We say that a
partial function f:X into X' is Borel if and only if the inverse image
of every Borel set in X' is a Borel set in X.

THEOREM. Let f:X into X' be a one-one partial Borel functions. The
domain, range, and inverse of f are Borel.

THEOREM. If A,B are Borel sets in X with the same cardinality, then
there exists a bijection from A onto B which is Borel.

This strong robustness robustly propagates to higher dimensions,
including dimension omega (but not further). Note that (X,S) is not
determined by X alone. It is only determined up to isomorphism. But
(X,S) does determine the appropriate Borel space (X^2,S<2>), where
S<2> is to be determined. What fundamental relationship do we want
between (X,S) and (X^2,S<2>)? ANSWER: That there be a good isomorphism
between them, or maybe that all isomorphisms between them are good.

DEFINITION. Let f:X into X'^2. The inverses of f are f_1,f_2, where
f(x) = (f_1(x),f_2(x)).

THEOREM. Let A be Borel in X and B be Borel in X', both with the same
cardinality. There exists a bijection f:A onto B^2 with Borel
inverses.

DEFINITION. A Borel space (X^2,S<2>) is standard over (X,S) if and
only if it (X,S) is isomorphic to (X^2,S<2>) by some bijection f:X
onto X^2 with Borel inverses.

THEOREM. There is exactly one Borel space (X^2,S<2>) standard over (X,S).

This robustness lifts perfectly with much more generality. E.g., we
can start with n uncountable standard Borel spaces, and a single
standard Borel space on the side. We use bijections from the side
space onto the Cartesian product of the n spaces,  to robustly define
the standard Borel space on the Cartesian product over the given n
spaces. Once again, we arrive at the same higher dimensional standard
Borel space no matter what bijection with Borel inverses that we use.

Also, this works just fine if we are given an infinite sequence of
standard Borel spaces. There is a bijection from any given standard
Borel space onto the infinite product set, whose infinitely many
inverses are Borel, and it again doesn't make any difference which one
we use to define the standard Borel space on the infinite Cartesian
product over the infinitely many given Borel spaces. We also remove
the requirement that the given standard Borel spaces be uncountable.

3.2. BOREL AND BORELIAN STRUCTURES

First, we need a suitably general concept of

*countably based many sorted structure"

sufficient for most purposes in analysis. This is more general than
what is normally used in logic.

DEFINITION. M is a CBS (countably based system) if and only if M =
(D_1,...,c_1,...,R_1,...,F_1,...), where

i. All four lists are of length at most omega, where the list of D's
is required to be nonempty.
ii. The D's are nonempty sets called the domains, which are required
to be pairwise disjoint.
ii. The c's are constants, where each constant is an element of some
D_i, where the index i is designated.
iii. Each R is a subset of a Cartesian product of at most omega of the
D's, such Cartesian product designated using indices of the D's.
iv. Each F is a partial function from some Cartesian product of at
most omega of the D's into some Cartesian product of at most omega of
the D's, where both Cartesian products are designated using indies of
the D's.

Thus we allow countably infinite dimensions, with partial functions
from infinite dimensional vectors into infinite dimensional vectors.
Of course, in many cases, there will be only finitely many D's, c's,
R's, F's, the F's are everywhere defined, only finite Cartesian
products are used, and the F's are point valued.

DEFINITION. A Borel structure is an (S,M)  where
i. M is a CBS.
ii. S is a standard Borel space whose set of points is the union of
the domains of M.
iii. The R's in M are Borel sets in the relevant Cartesian products
according to the product Borel space construction in section 3.1.
iv. The F's in M are partial Borel functions from the relevant
Cartesian products into the relevant Cartesian products according to
the product Borel space construction in section 3.1.
M is called the structural part of (S,M).

DEFINITION. A Borelian structure is a CBS which is the structural part
of a Borel structure. A uniquely Borelian structure is a CBS which is
the structural part of a unique Borel structure.

THEOREM. A Borelian structure is uniquely Borelian if and only if
there exists a countable subset A of the union of its domains such
that every automorphism of the CBS which is the identity on A is the
identity.

The proof of the above is not obvious and needs to be discussed.

Which commonplace mathematical structures are Borelian and which are
uniquely Borelian?

1. Equivalence Relations. The Borelian equivalence relations are of
course the usual Borel equivalence relations. There is already a vast
area, and growing.

The study of Borel equivalence relations historically has been
centered around the notion of Borel reducibility of Borel equivalence
relations (generally credited to me): (S,EQR_1) is Borel reducible to
(T,EQR_2) if and only if there exists a Borel function f:S into T such
that for all x,y in S,

x EQR_1 y iff f(x) EQR_2 f(y)

where S,T are Polish spaces. The idea is that (S,EQR_1)  can be
SIMULATED in (T,EQR_2). At the lowest level is of course the identity
relation on R. See http://www.math.ucla.edu/~greg/223b.1.06s/borel.ps
and http://www.ams.org/publications/authors/books/postpub/ulect-44

The only uniquely Borelian equivalence relation are the ones with a
single point (zero points generally not allowed).

2. Linear Orderings. There is a certain amount of literature on Borel
linear orderings, and Borel quasi orderings, which should become vast.

CONJECTURE. A Borel linear ordering is uniquely Borel if and only if
it is separable.

There is probably enough known about Borel linear orderings to readily
affirm this Conjecture. This area of Borel linear and Borel quasi
orderings should become vast.

3. Groups. There is a limited amount of literature on Borel groups,
which should become vast. The group of reals under + is Borelian but
not uniquely Borelian.

CONJECTURE. There are uncountable (commutative) Borel groups which are
uniquely Borelian.

4. Rings, Fields. Not much literature on this, but should become vast.
The field of reals is uniquely Borel. All Archimedean ordered fields
are uniquely Borel. There exists an ordered field which is Borelian
but not uniquely Borelian.

5. Real Vector Spaces. Countable dimensional real vector spaces are
uniquely Borelian. Those with dimension c are Borelian but not
uniquely Borelian. All others are not Borelian.

6. Metric Spaces. There is a little literature on this, which should
become vast. Use R as the second domain, with its ordered group
structure. All Borelian separable metric spaces are uniquely Borelian.

What about non separable Borelian metric spaces? Some are uniquely
Borelian and some are not uniquely Borelian. Adding completeness
doesn't change the situation.

7. Normed Real Vector Spaces. Use R as the second domain, with its
ordered group structure.

8. Banach Spaces. Again use R as the second domain, with its ordered
group structure. Every separable Banach space is uniquely Borelian.
Some non separable Banach spaces are non Borelian, are Borelian but
not uniquely Borelian, and are uniquely Borelian.

THEOREM. ell_inifnity and L_infinity are uniquely Borel.

The above is not obvious, and the proof needs to be discussed.

3.3. SOME MISCELLANEOUS BOREL RESULTS

In the course of Removing Deep Pathology through Borelian Mathematics,
some miscellaneous Borel results have come up.

(Jack Silver) Every Borel equivalence relation with uncountably many
equivalence classes has a perfect set of mutually inequivalent
elements. (Even true for coanalytic equivalence relations).

Nobody reads Jack's proof anymore, which uses uncountably many
iterations of the power set. Instead Harrington's proof is all the
rage, and works in Pi11-CA0. Ramez Sami proved that it is equivalent
to Pi11-CA0 over RCA_0, with Borel or even coanalytic.

Harrington uses his method of forcing with Sigma-1-1 lightfaced sets
of reals. I got interested in this, and recently duplicated this using
Harrington's method:

(Harrington) In every non separable Borel metric space, there exists
epsilon > 0 such that some perfect set of points lie at least epsilon
apart.

I did find a little new twist on this:

(Me) In every pseudo Borel metric space with an uncountable set of
points lying at least epsilon apart, there is a perfect set of points
lying at least epsilon/2 apart. This is, in the appropriate sense,
best possible.

(Blass) Every reflexive symmetric Borel subset of R^2 contains or is
disjoint from a square whose side is perfect.

(Me) The following statements are false. Every Borel subset of R^2
that contains an uncountable square contains a square whose side is
perfect. Every Borel subset of R^2 that contains the product of two
uncountable sets contains the product of two perfect sets.

************************************************************
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 603rd 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?
602: Removing Deep Pathology 2

Harvey Friedman