[FOM] Proving PD?/2

[Harvey Friedman]

We continue from http://www.cs.nyu.edu/pipermail/fom/2016-April/019769.html

We have been applying Borel Transfer to "refute" the continuum
hypothesis. We now want to apply the Borel Transfer approach to
"prove" PD.

Here K is the usual Cantor space.We look at statements of the form

A) (for all Borel S containedin K^2)(there exists continuous f:K into
K()(for all x in K)(phi) or (for all x in K)(psi))

Here phi,psi are quantifier free formulas in (K,S,f) with the variable x.

Many years ago I investigated what amounts to

1) (for all Borel S containedin K^2)(there exists continuous f:K into
K)((for all x in K)(S(x,f(x)) or (for all x in K)(not S(f(x),x)))

in the more readily understandable equivalent form

2) Let S containedin K^2 be Borel. There is a continuous function from
K into K which is either contained in S or disjoint from the converse
of S).

3) Every symmetric Borel S containedin K^2 contains or is disjoint
from the graph of a continuous f:K into K.

I proved the equivalence of 2),3) (and hence 1) also) and related
statements with Borel Determinacy. And passing through Turing degree
determinacy, I proved that the corresponding statements for the
projective sets is equivalent to PD.

BOREL/PROJECTIVE TRANSFER. Every true sentence in class A) above
remains true with Broel replaced by projective.

CONJECTURE. The above Transfer is equivalent to PD over ZFC.

We can also transfer to all S containedin K^2, and 1)-3) become
equivalent to AD (again passing through Turing determinacy).

Let's start modestly with phi(S,f,x), psi(S,f,x) which are literals
with no nesting and no equality. E.g., S(x,fx)), not S(fy,y), etc.

There are 4 atomic formulas, and therefore 8 literals. There are 64 disjunctions

(for all x)(phi) or (for all x)(psi)

to consider..

Let us call this fragment: A) with unnested literals and no equality.

THEOREM 1. The instance of A) with literals and no nesting and no
equality, is true if and only if it is among
{S(x,x), not S(fx,fx)}
{not S(x,x), S(fx,fx)}
{S(x,fx), not S(fx,x)}
{S(fx,x), not S(x,fx)}
The first two cases give a statement trivially provable in ATR_0, that
lifts to a statement trivially provable in Z.
The second two cases give a statement provably equivalent to Borel
determinacy over ATR_0, and lifts to a statement provably equivalent
to PD in ZC.

Here is a sketch. First of all, these universal statements have
trivial equivalents:

(there exists continuous f:K into K)(for all x in K)(S(x,x)). S is reflexive.
(there exists continuous f:K into K)(for all x in K)(not S(x,x)). S is
irreflexive.
(there exists continuous f:K into K)(for all x in K)(S(fx,fx)). S is
not irreflexive.
(there exists continuous f:K into K)(for all x in K)(not S(fx,fx)). S
is not reflexive.

The other four are nontrivial. If we stay in the trivial, then the
obvious criteria is of course that we have one from the first two and
another from the second two.

Now suppose one of them is nontrivial. I.e., from

(there exists continuous f:K into K)(for all x in K)(S(x,fx))
(there exists continuous f:K into K)(for all x in K)(not S(x,fx))
(there exists continuous f:K into K)(for all x in K)(S(fx,x))
(there exists continuous f:K into K)(for all x in K)(not S(fx,x))

These are all symmetric in the obvious sense of using S, competent of
S, converse of S, complement of converse of S.

So let us assume that we are using the first of these nontrivial four.
The other cannot be reflexivity since S can be the graph of a
discontinuous Borel function that moves everything. The other cannot
be irreflexivity since S can be the graph of a discontinuous Borel
function that moves something. So the other must be among the
nontrivial four. This argument works for any of these nontrivial four.

So we need to consider the four disjunctions

(there exists continuous f:K into K)(for all x in K)(S(x,x))

or

there exists continuous f:K into K)(for all x in K)(S(x,fx)). No. S = emptyset.
(there exists continuous f:K into K)(for all x in K)(not S(x,fx)). No.
S is the graph of a discontinuous Borel function on {x in K: x(0) =
0}, and the compliment of the graph of a discontinuous Borel function
on {x in K: x(0) = 1}.
(there exists continuous f:K into K)(for all x in K)(S(fx,x)). No. S = emptyset.
(there exists continuous f:K into K)(for all x in K)(not S(fx,x)).
Yes. By Borel determinacy.

THEOREM 2. Theorem 1 adapts to the expanded B):

B) (for all Borel S containedin K^2)(there exists continuous f:K into
K()(for all x in K)(phi_1) or ... or (for all x in K)(phi_n))

Here phi_i are phi,psi are literals in (K,S,f) with the variable x, no
nesting, and equality allowed.

Harvey Friedman