[FOM] 672: Refuting the Continuum Hypothesis?/1

[Harvey Friedman]

THIS MOVES THE REFUTING CH 1-7 SERIES OVER TO OUR NUMBERED POSTINGS.
IT HAS MATURED ENOUGH TO DO THAT. WE START FROM THE BEGINNING

1. We have a particularly simple sentence $ that refutes the continuum
hypothesis. It appears that no remotely simple sentence of roughly
this kind proves the continuum hypothesis.
2. Because of the fundamental nature of the properties of $, this
asymmetry between not CH and CH is offered up as a possible refutation
of the continuum hypothesis, and more generally, as a strategic
principle that could be used to arguably solve the large list of set
theoretic problems left open by ZFC.
3. In fact, a closely related development of this kind has been
presented here on the FOM in order to "prove" PD.

1. LIFTING EXISTENTIAL PROPERTIES OF BOREL FUNCTIONS TO ALL FUNCTIONS

We start with the following theorem about all Borel functions which is
easy to prove using Fubini's theorem It provides a particularly simple
existential property of all Borel functions f:R into R.

THEOREM 1.1. (ATR_0) For all Borel f:R into R there exists x,y in R
such that for no integer n do we have x = f(y+n) or y = f(x+n).

Proof: For all n, {{x,y}: x = f(y+n} and {(x,y): y = f(x+n)} have
measure 0 by a very special case of Fubini's theorem since both sets
are graphs or converse graphs of Borel functions Hence for all n,
{{x,y}: x = f(y+n) or y = f(x+n)} has measure 0. By countable
additivity, {(x,y): for some n, y = f(x+n) or x = f(y+n)} has measure
0. Hence its complement is nonempty. We can analogously use Baire
category. QED

We now lift the Theorem to all functions f:R into R.

PROPOSITION $. For all f:R into R there exists x,y in R such that for
no integer n do we have x = f(y+n) or y = f(x+n).

The Theorem represents a very simple existential property of Borel
functions. The Lifting process to all functions is what is being
investigated as a systematic way of solving set theoretic problems
like the continuum hypothesis.

THEOREM 1.2. $ is provably equivalent to the negation of the continuum
hypothesis over Z = Zermelo set theory.

So we are investigating the following EXISTENTIAL BOREL LIFTING PRINCIPAL.

a. Start with a simple existential property of Borel f:R into R, proved in ZFC.
b. Take its lifting to all f:R into R.
c. We know of simple cases where the lifting is refutable in ZC. See
section 5 below.
d. Postulate that if the lifting is consistent with ZFC then the
lifting is true.
e. Theorem 1 and $ is the initial example of the lifting process, and
it "refutes" the continuum hypothesis.

One issue immediately arises. If this lifting process is to become a
principled way of solving set theoretic problems like the continuum
hypothesis, we need to be assured that the same lifting process isn't
also capable of solving some of the same set theoretic problems but in
the opposite way. I.e., is the strategy *coherent*?

At this early stage, we have only some preliminary results and ideas
about establishing such coherence.

This Lifting strategy has also been applied to "prove" PD. I want to
keep these parallel developments separate at this very early stage.
See http://www.cs.nyu.edu/pipermail/fom/2016-April/019769.html
http://www.cs.nyu.edu/pipermail/fom/2016-April/019775.html

2. CLEAR VALUE OF PHONE CONVERSATIONS WITH OTHER MINDS

I often use the telephone for feedback from other thinkers. I have
experienced a wide variety of availabilities. Some are reliably
available, all the way to others who have essentially refused to
engage in conversation.

In 99% of cases, when there is a phone conversation, something
intellectually valuable comes out of it, even if the person is only
giving an immediate reaction to something they barely understand.

So I take this opportunity to thank all who have, over the years,
participated in such immediate feedback. You will be hearing from me
again. For the others, you will also be hearing from me again.

This section is oriented toward what came out of a conversation with
Ovidiu Costin, an analyst with very broad interests.

Costin expressed immediate interest in Theorem 1 and Proposition $. He
asked, in essence, whether $ produces a set of reals of intermediate
cardinality. He said that this ought to be true. I said that I doubt
that.

I later realized that Costin was right.

DEFINITION 2.1. A $ operator is an operator that maps any given f:R
into R to a pair x,y according to Proposition $.

QUESTION A. (Costin) Is there an explicitly definable way of passing
from a $ operator to a set of real numbers of intermediate
cardinality?

THEOREM 2.1. The answer to Question A is Yes. In fact, there is an
explicitly definable way of passing from a $ operator to a well
ordering of the reals.

QUESTION B. Now suppose we merely assume $ is true, and have no access
to a $ operator. Can we explicitly define a set of reals of
intermediate cardinality? Can we explicitly define set of reals of
cardinality omega_2?

THEOREM 2.2. The answer to question B is that we cannot find such an
explicit definition that provably works in ZFC. This is well known.
Add omega_2 Cohen reals over L.

DEFINITION 2.2. A $ counter function is an f:R into R such that for
all x,y, in R, x is some f(y+n) or y is some f(x+n).

QUESTION C. Is there a definable way of passing from a $ counter
function to a well ordering of R of length omega_1?

THEOREM 2.3. The answer to question B is that we cannot find an
explicit definition of such an operator that provably works in ZFC.
First add omega_1 Cohen reals to L and then add a generic subset of
omega_1 using countable conditions.

3. IS THE METHOD OF EXISTENTIAL BOREL LIFTING COHERENT? part 1

Here we see how close we can to "proving" CH in the same way that we
have "proved" not CH.

We will use T for the Baire space N^N. This is homeomorphic to the
irrational real numbers as a subspace of R.

THEOREM 3.1. The following is well known. Every second order sentence
over countable domains is provably equivalent, over ZC, to a sentence
of the form  (for all f:T into T)(there exists x in T)(for all n in
N)(S(n,x|<=n,f(x)|<=n)), where S is a ternary recursive predicate of
nonnegative integers, finite sequence numbers, and finite sequence
numbers. In fact, this hold of third order sentences over countable
domains where all third order quantifiers are in front and are
universal.

THEOREM 3.2. The following is well known. There is a second order
sentence over countable domains, consistent with ZFC, which proves the
continuum hypothesis. Most notably, the one that naturally expresses
"every real is constructible".

Note that $ is of the form

1) (for all f:R into R)(there exists x,y in R)(for all n in Z)(phi)

where phi is in a weak fragment of the propositional combinations of
formulas that compare the x,y,n,x+n,y+n,f(x),f(y),f(n),f(x+n),f(y+n).
Actually we only need comparisons not=, conjunction, and
x,y,f(x+n),f(y+n).

The pertinent question for us is whether we can put "every real is
constructible" in anything even remotely close to the form above that
$ takes.

I have never seen any simpler formulation of "every real is
constructible" than that of general second order sentences over
countable domains, and so we appear to be stuck with trying to reduce
the complexity involved in the general

2) (for all f:T into T)(there exists x in T)(for all n in
N)(S(n,x|<=n,f(x)|<=n)),

By Theorem 3.1, we can put any sentence of form 1) into form 2). To
put any sentence of form 2) anywhere near the form 1), we are going to
have to replace T with R, and replace general recursive (or
computationally efficient) ternary predicates S acting on nonnegative
integers and two sequence numbers by something in the vicinity of the
phi used in 1). Granted, 1) allows us two existential second order
quantifiers, x,y, but that hardly seems much help.

So there appears to be a complex probably quite open ended subject
here of what I call REFINED NORMAL FORM THEORY. 1) is an example of a
Fine Normal Form, whereas 2) is an example only of a Crude Normal
Form.

Actually the phi allowed in 1), although quite pertinent to the issues
at hand, is rather specialized. The appropriate form to consider for
Refined Normal Form Theory is probably this:

3)  (for all f_1,...,f_k:R into R)(there exists x_1,...,x_n in R)(phi)

where phi is a proportional combination of atomic formulas s < t, t in
Z, where s,t are terms built from the f's, x's, addition, subtraction,
and multiplication.

MAYBE 3) is universal for second order sentences over countable
domains, and can be used to imply CH via "all reals are
constructible", and then probably there is no problem making sure that
it is true of all Borel f's. BUT two points:

a. This may or may not be the case.
b. This is still a far cry away from various natural more refined
normal forms that are closer to 1).
c. In any case, it would seem that the phi coming from "all reals are
constructible' are going to be absolutely gigantic compared to the
tiny tiny size of our instance of 1) given by $.

So the attack on COHERENCE via "all reals are constructible" is very
weak and rather dubious on multiple levels.

4. IS THE METHOD OF EXISTENTIAL BOREL LIFTING COHERENT? part 2

The plan is to analyze

1) (for all f:R into R)(there exists x,y in R)(for all n in Z)(phi)

where phi is from some very restrictive languages that include the phi
used in $. Recall that $ uses

phi = "x not= f(y+n) and y not= f(x+n)".

Here are some baby classes that need to be examined.

i. phi is a conjunction of equations and inequations between
x,y,x+n,y+n,fx,fy,f(x+n),f(y+n). Also allow <.

ii. Same as i except allow f...f instead of just f.

iii. Same as i except allow any terms involving f's, x's, n's, with
the restriction that every subterm of the form s+t must have s or t be
the variable "n".

iv. Now starting allowing multiple f's, more than two real variables,
multiple integer variables, and arbitrary propositional combinations.

v. Dance very carefully with the big deal of allowing any terms
involving f;s, x;s, n's and unrestricted addition and subtraction.

What to expect?

a. A meaningful characterization of which statements are true of all
Borel functions. That they are provable or refutable in ATR_0.
b. For at least the most restrictive languages, the instances that are
true of all Borel functions have the property that their lifting to
all functions is provable from not CH - and hence they are consistent
with ZFC and do not imply CH.
c. Perhaps for say v in full glory, we only have that the instances
that are true of all Borel functions have the property that their
lifting to all functions is either refutable in ZFC, or do not imply
CH. Perhaps moreover, that they follow from not CH, or at least follow
from 2^omega > omega_omega. See section 5.

I haven't really got into this yet.

5. IS THE METHOD OF EXISTENTIAL BOREL LIFTING COHERENT? part 3

We give a simple existential  property of all Borel functions f:R into
R, provable
in ATR_0, which, when lifted to all functions f:R into R, results in a
statement refutable in ZC.

THEOREM 5.1. (ATR_0) Let f:R into R be Borel. There exists x in R and n
in Z such that |f(x) - f(x + e^n)| < 1.

PROPOSITION 5.2. Let f:R into R. There exists x in R and n in Z such
that |f(x) - f(x + e^n))| < 1.

THEOREM 5.3. Proposition 2 is refutable in ZC. It is provable in ZC +
"every set of reals has the property of Baire".

***********************************************
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 672nd 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
643: Constrained Subsets of N, #1  11/3/15  11:57PM
644: Fixed Point Selectors 1  11/16/15  8:38AM
645: Fixed Point Minimizers #1  11/22/15  7:46PM
646: Philosophy of Incompleteness 1  Nov 24 17:19:46 EST 2015
647: General Incompleteness almost everywhere 1  11/30/15  6:52PM
648: Necessary Irrelevance 1  12/21/15  4:01AM
649: Necessary Irrelevance 2  12/21/15  8:53PM
650: Necessary Irrelevance 3  12/24/15  2:42AM
651: Pi01 Incompleteness Update  2/2/16  7:58AM
652: Pi01 Incompleteness Update/2  2/7/16  10:06PM
653: Pi01 Incompleteness/SRP,HUGE  2/8/16  3:20PM
654: Theory Inspired by Automated Proving 1  2/11/16  2:55AM
655: Pi01 Incompleteness/SRP,HUGE/2  2/12/16  11:40PM
656: Pi01 Incompleteness/SRP,HUGE/3  2/13/16  1:21PM
657: Definitional Complexity Theory 1  2/15/16  12:39AM
658: Definitional Complexity Theory 2  2/15/16  5:28AM
659: Pi01 Incompleteness/SRP,HUGE/4  2/22/16  4:26PM
660: Pi01 Incompleteness/SRP,HUGE/5  2/22/16  11:57PM
661: Pi01 Incompleteness/SRP,HUGE/6  2/24/16  1:12PM
662: Pi01 Incompleteness/SRP,HUGE/7  2/25/16  1:04AM
663: Pi01 Incompleteness/SRP,HUGE/8  2/25/16  3:59PM
664: Unsolvability in Number Theory  3/1/16  8:04AM
665: Pi01 Incompleteness/SRP,HUGE/9  3/1/16  9:07PM
666: Pi01 Incompleteness/SRP,HUGE/10  13/18/16  10:43AM
667: Pi01 Incompleteness/SRP,HUGE/11  3/24/16  9:56PM
668: Pi01 Incompleteness/SRP,HUGE/12  4/7/16  6:33PM
669: Pi01 Incompleteness/SRP,HUGE/13  4/17/16  2:51PM
670: Pi01 Incompleteness/SRP,HUGE/14  4/28/16  1:40AM
671: Pi01 Incompleteness/SRP,HUGE/15  4/30/16  12:03AM

Harvey Friedman