[FOM] 603: Removing Deep Pathology 3

[Joe Shipman]

Here's a good "pathology" topic for you--the lack of well-defined "functional square roots" of exponentials (functions defined on a real interval such that f(f(x))=e^x of f(f(x))=2^x) or the very closely related lack of a well-defined and non-arbitrary extension of the tower function to non-integral arguments.

-- JS 

Sent from my iPhone

> On Aug 25, 2015, at 10:24 AM, Harvey Friedman <hmflogic at gmail.com> wrote:
> 
> 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
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom