[FOM] 599: Invariant Sequential Choice

Sat Aug 15 16:22:41 EDT 2015

This coming week I plan to put a paper RESOLUTION AND LARGE CARDINALS,
on my website. This has complete proofs, and represents a major
revisiting of much of my work over the years on BOREL Incompleteness.
At the end of the paper, there are some formulations in terms of what
I call INVARIANT SEQUENTIAL CHOICE. These are probably the best
formulations in the paper from the point of view of an analyst. From
the DST point of view, probably not.

Here is a version of the part on Invariant Sequential Choice which is
a little abridged and uses more English - making it more readable as a
posting.

5. INVARIANT SEQUENTIAL CHOICE

In Sequential Choice, we start with Polish spaces T_1,T_2. Given a
Borel R containedin (T_1)^omega x (T_2)^omega, we seek a Borel choice
function F for R. I.e., a Borel F:(T_1)^omega x (T_2)^omega, where
R(x,y) implies R(x,F(x)).

In Invariant Sequential Choice, we place the additional range
invariance condition

rng(x) = rng(y) implies rng(F(x)) = rng(F(y)).

We also consider the following more elemental setup, which is already
of interest. Given a Borel R containedin (T_1)^omega x (T_2)^omega, we
seek a Borel F:(T_1)^omega x (T_2)^omega, where R(x,y) implies
R(x,F(x)). We also seek the additional range invariance condition

rng(x) = rng(y) implies F(x)) = F(y).

We often find that while there is a Borel choice function, there is no
range invariant Borel choice function. However, unexpectedly deep
logical issues arise in connection with such negative results.

The setting can be expanded in many ways. E.g., we can use more
general T_1,T_2, and also go well beyond Borel.

5.1. FOR INCLUSION

K is the usual Cantor space of infinite sequences from {0,1}.

The original diagonalization arguments are credited to Georg Cantor.
Here is a corresponding Sequential Choice statement.

THEOREM 5.1.1. There is a Borel way of passing from any infinite
sequence of elements of K to a y in K off the sequence.

THEOREM 5.1.2. There is a Borel way of passing from any infinite
sequence of elements of K to an infinite sequence of elements of K
with some new term.

THEROEM 5.1.3. There is no range invariant Borel way of passing from
any infinite sequence of elements of K to a y in K off the sequence.

THEOREM 5.1.4. There is no range invariant Borel way of passing from
any infinite sequence of elements of K to an infinite sequence of
elements of K with some new term.

Theorems 5.1.3, 5.1.4 are not provable in separable mathematics -
e.g., not in ZFC\P.

5.2. FOR RESOLUTION

DEFINITION 5.2.1. The converse of E containedin K^2 is the set
resulting from interchanging the coordinates of the elements of E. E
is symmetric if and only if E is the same as its converse.

THEOREM 5.2.1. The converse of the complement of E containedin K^2 is
the complement of the converse of E.

THEOREM 5.2.2. There is a Borel way of passing from any infinite
sequence of continuous functions from K into K to an infinite sequence
of elements of K^2 which meets each x_i and the complement of its
converse.

THEOREM 5.2.3. There is a Borel way of passing from any infinite
sequence of continuous functions from K into K to a symmetric infinite
sequence of elements of K^2 which meets each x_i and its complement.

PROPOSITION A. There is no invariant Borel way of passing from any
infinite sequence of continuous functions from K into K to an infinite
sequence of elements of K^2 which meets each x_i and the complement of
its converse.

PROPOSITION B. There is no invariant Borel way of passing from any
infinite sequence of continuous functions from K into K to a symmetric
infinite sequence of elements of K^2 which meets each x_i and its
complement.

Note that Propositions A,B are Pi12.

THEOREM. Propositions A,B  are provable in ZFC + "there exists a
Woodin cardinal" but not in ZFC + "there exists a strong cardinal",
assuming the latter is consistent.

************************************************************
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 599th 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-527 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2014-August/018092.html

528: More Perfect Pi01  8/16/14  5:19AM
529: Yet more Perfect Pi01 8/18/14  5:50AM
530: Friendlier Perfect Pi01
531: General Theory/Perfect Pi01  8/22/14  5:16PM
532: More General Theory/Perfect Pi01  8/23/14  7:32AM
533: Progress - General Theory/Perfect Pi01 8/25/14  1:17AM
534: Perfect Explicitly Pi01  8/27/14  10:40AM
535: Updated Perfect Explicitly Pi01  8/30/14  2:39PM
536: Pi01 Progress  9/1/14 11:31AM
537: Pi01/Flat Pics/Testing  9/6/14  12:49AM
538: Progress Pi01 9/6/14  11:31PM
539: Absolute Perfect Naturalness 9/7/14  9:00PM
540: SRM/Comparability  9/8/14  12:03AM
541: Master Templates  9/9/14  12:41AM
542: Templates/LC shadow  9/10/14  12:44AM
543: New Explicitly Pi01  9/10/14  11:17PM
544: Initial Maximality/HUGE  9/12/14  8:07PM
545: Set Theoretic Consistency/SRM/SRP  9/14/14  10:06PM
546: New Pi01/solving CH  9/26/14  12:05AM
547: Conservative Growth - Triples  9/29/14  11:34PM
548: New Explicitly Pi01  10/4/14  8:45PM
549: Conservative Growth - beyond triples  10/6/14  1:31AM
550: Foundational Methodology 1/Maximality  10/17/14  5:43AM
551: Foundational Methodology 2/Maximality  10/19/14 3:06AM
552: Foundational Methodology 3/Maximality  10/21/14 9:59AM
553: Foundational Methodology 4/Maximality  10/21/14 11:57AM
554: Foundational Methodology 5/Maximality  10/26/14 3:17AM
555: Foundational Methodology 6/Maximality  10/29/14 12:32PM
556: Flat Foundations 1  10/29/14  4:07PM
557: New Pi01  10/30/14  2:05PM
558: New Pi01/more  10/31/14 10:01PM
559: Foundational Methodology 7/Maximality  11/214  10:35PM
560: New Pi01/better  11/314  7:45PM
561: New Pi01/HUGE  11/5/14  3:34PM
562: Perfectly Natural Review #1  11/19/14  7:40PM
563: Perfectly Natural Review #2  11/22/14  4:56PM
564: Perfectly Natural Review #3  11/24/14  1:19AM
565: Perfectly Natural Review #4  12/25/14  6:29PM
566: Bridge/Chess/Ultrafinitism 12/25/14  10:46AM
567: Counting Equivalence Classes  1/2/15  10:38AM
568: Counting Equivalence Classes #2  1/5/15  5:06AM
569: Finite Integer Sums and Incompleteness  1/515  8:04PM
570: Philosophy of Incompleteness 1  1/8/15 2:58AM
571: Philosophy of Incompleteness 2  1/8/15  11:30AM
572: Philosophy of Incompleteness 3  1/12/15  6:29PM
573: Philosophy of Incompleteness 4  1/17/15  1:44PM
574: Characterization Theory 1  1/17/15  1:44AM
575: Finite Games and Incompleteness  1/23/15  10:42AM
576: Game Correction/Simplicity Theory  1/27/15  10:39 AM
577: New Pi01 Incompleteness  3/7/15  2:54PM
578: Provably Falsifiable Propositions  3/7/15  2:54PM
579: Impossible Counting  5/26/15  8:58PM
580: Goedel's Second Revisited  5/29/15  5:52 AM
581: Impossible Counting/more  6/2/15  5:55AM
582: Link+Continuation Theory  1  6/21/15  5:38PM
583: Continuation Theory 2  6/23/15  12:01PM
584: Finite Continuation Theory 3   6/26/15  7:51PM
585: Finite Continuation Theory 4  6/29/15  11:23PM
586: Finite Continuation Theory 5  6/20/15  1:32PM
587: Finite Continuation Theory 6  7/1/15  11:39PM
588: Finite Continuation Theory 7  7/2/15  2:44PM
589: Finite Continuation Theory 8  7/4/15  6:51PM
590: Finite Continuation Theory 9  7/6/15  5:20PM
591: Finite Continuation Theory 10  7/12/15  3:38PM
592: Finite Continuation Theory 11/perfect?  7/29/15  4:30PM
593: Finite Continuation Theory 12/perfect?  8/23/15  9:47PM
594: Finite Continuation Theory 13/perfect?  8/4/15  1:44PM
595: Finite Continuation Theory 14/perfect?  8/5/15  8:23PM
596: Finite Continuation Theory 15/perfect?  8/8/15 12:35AM
597: Finite Continuation Theory 16/perfect?  8/10/15  10:22PM
598: Finite Axiomatizations  8/10/15  5:05AM

Harvey Friedman