[FOM] 486:Naturalness Issues
Harvey Friedman
friedman at math.ohio-state.edu
Wed Mar 14 10:50:57 EDT 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
*****************************************
FEEDBACK FROM FOM SUBSCRIBERS IS REQUESTED
*****************************************
I have now presented the main Pi01 independent statements at the
Harvard math dept (March 1, 2012), and at the 90th birthday
celebration of Patrick Suppes (March 10, 2012) at Stanford. Notes for
the two talks can be found at http://www.math.osu.edu/~friedman.8/manuscripts.html
, Lecture Notes 57, 58.
I have now obtained a certain amount of feedback from core
mathematicians and other noted non logicians, as well as from some
noted logicians, concerning
PROPOSITION 1. EVERY ORDER INVARIANT SUBSET OF Q[0,16]^32 HAS A
COMPLETELY Z+UP INVARIANT MAXIMAL SQUARE.
Here I want to discuss issues concerning the naturalness or
appropriateness of Proposition 1, with the hope that this will
generate interesting feedback from FOM subscribers.
The key issue I want to address is the use of the special function Z
+up:Q* into Q*.
Let's start with the self contained background for the discussion. We
start with
EVERY SET OF ORDERED PAIRS HAS A MAXIMAL SQUARE.
This abstract set theoretic statement is immediate from Zorn's Lemma,
and is in fact equivalent to Zorn's Lemma. But the following has a
very explicit greedy construction proof:
EVERY COUNTABLE SET OF ORDERED PAIRS HAS A MAXIMAL SQUARE.
We are moving towards
EVERY INVARIANT SET OF ORDERED PAIRS HAS AN INVARIANT' MAXIMAL SQUARE.
My general setup for the invariance conditions involves using the
master space Q* of all finite subsequences of Q.
Let S be a subset of an ambient space K.
Let R be any binary relation. We say that S is R invariant if and only
if for all x,y in K with R(x,y), we have x in S implies y in S.
We say that S is completely R invariant if and only if for all x,y in
K with R(x,y), we have x in S iff y in S.
We use two important special cases: R is an equivalence relation, and
R is a function.
Let Q be the set of all rationals, and Q* be the set of all finite
sequences of rationals.
We use the order equivalence relation on Q*, and the function Z+up:Q*
into Q*.
x,y in Q* are order equivalent if and only if they have the same
length, and for all 1 <= i,j <= lth(x), x_i < x_j iff y_i < y_j.
Z+up(x) results from adding 1 to all coordinates greater than all
coordinates outside Z+.
Nobody has questioned the naturalness of order equivalence on Q*.
Some have questioned the naturalness of Z+up on Q*. We will address
this concern below.
We use Q[0,n] as an ambient space, where Q[0,n] is the set of all
rationals in [0,n].
PROPOSITION 2. EVERY ORDER INVARIANT SUBSET OF Q[0,n]^2k HAS A
COMPLETELY Z+UP INVARIANT MAXIMAL SQUARE.
Note that Proposition 1 is the special case where n = 16 and k = 32.
THEOREM 3. Proposition 2 is provably equivalent to Con(SRP) over ACA'.
In particular, it is provable in SRP+ but not in ZFC (assuming ZFC is
consistent).
A proof of Theorem 3 has been submitted for publication.
THEOREM 4. Proposition 1 is provable in SRP+ but not in ZFC (assuming
ZFC is consistent).
SRP+ = ZFC + (for all k)(there is an ordinal with the k-SRP). SRP =
ZFC + {there is an ordinal with the k-SRP)_k. The k-SRP asserts that
every partition of the unordered k-tuples from lambda into two pieces
has a homogenous set stationary in lambda.
**********************************************
I would like to declare VICTORY on the basis of Theorems 3,4, together
with the observation that Propositions 1,2 can be seen to be
"concrete" in various senses. E.g., they are constructively equivalent
to the satisfiability of sentences in predicate calculus, and also
constructively equivalent to asserting that obvious associated
algorithms can be carried out for any given number of finite steps.
QUESTION: Exactly how should the VICTORY claim be stated?
As usual, I have been in contact with various kinds of scholars
concerning Propositions 1,2.
Generally speaking, discussion focuses on the function Z+up:Q* into
Q*. Here are some reactions.
1. Outright acceptance of Z+up:Q* into Q* as entirely natural and
appropriate, both intrinsically, and for use in complete invariance.
This includes at least one multiple prize winning icon in core
mathematics - possibly more than one.
2. Another prominent core mathematician said that Propositions 1,2 are
"artificially created", meant as a criticism, and seems to base this
feeling on Z+up:Q* into Q*. My own view is that they are of course
artificially created (by me) - but, after the fact, we recognize that
they are entirely natural and inevitable. They are now part of a new,
fully credible, and deep mathematical theory. In this sense, I
succeeded in greatly speeding up history. Pat Suppes views this work
as providing counterexamples to statements like "any intelligible
transparent concrete mathematical question can be answered in ZFC". My
own view is that Suppes is right, and the work goes further. Since
proofs are given using well studied extensions of ZFC, the
"counterexamples" also provide important new mathematical theories.
3. Noted logicians agreeing that the statement is transparent, but
expressing doubts that the mathematicians will accept Propositions 1,2
as natural, because of Z+up:Q* into Q*.
I have decided to focus on the Z+up:Q* into Q* issue in the following
way. I have isolated some simple and desirable abstract properties of Z
+up. I prove that any T:Q* into Q* obeying these properties can be
used in Propositions 1,2 - but using large cardinals in a necessary way.
*UNIFORM TRANSFORMATIONS*
THere are a few "fundamental" equivalence relations on Q*. We expect
to have a theory of "fundamental" equivalence relations on Q*, but
here we just present and use one of them.
For x,y in Q*, we define x ~ y if and only if
i. x,y are order equivalent.
ii. if x_i is in Z+ then y_i is in Z+.
iii. if x_i is not in Z+ then x_i = y_i.
We say that T:Q* into Q* is a UNIFORM TRANSFORMATION (with respect to
~) if and only if for all x in Q*, (x,Tx) ~ (Tx,TTx).
Note that Z+up:Q* into Q* is a uniform transformation. We can show
that all uniform transformations are very much like Z+up.
PROPOSITION 5. LET T:Q* into Q* BE A UNIFORM TRANSFORMATION. EVERY
ORDER INVARIANT SUBSET OF Q[0,n]^2k HAS A COMPLETELY T INVARIANT
MAXIMAL SQUARE.
PROPOSITION 6. LET T:Q* into Q* BE A UNIFORM TRANSFORMATION. EVERY
ORDER INVARIANT SUBSET OF Q[0,16]^32 HAS A COMPLETELY T INVARIANT
MAXIMAL SQUARE.
THEOREM 7. Proposition 5 is provably equivalent to Con(SRP) over ACA'.
In particular, it is provable in SRP+ but not in ZFC (assuming ZFC is
consistent). Proposition 6 is provable in SRP+ but not in ZFC
(assuming ZFC is consistent).
QUESTION. Are reservations about Propositions 1,2 with Z+up:Q* into Q*
reasonable? How far do Propositions 5,6 go to defuse reservations
about Propositions 1,2 with Z+up:Q* into Q*?
KEY PHRASE: Invariant Maximality.
********************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 486th 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-449 can be found
in the FOM archives at http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html
450: Maximal Sets and Large Cardinals II 12/6/10 12:48PM
451: Rational Graphs and Large Cardinals I 12/18/10 10:56PM
452: Rational Graphs and Large Cardinals II 1/9/11 1:36AM
453: Rational Graphs and Large Cardinals III 1/20/11 2:33AM
454: Three Milestones in Incompleteness 2/7/11 12:05AM
455: The Quantifier "most" 2/22/11 4:47PM
456: The Quantifiers "majority/minority" 2/23/11 9:51AM
457: Maximal Cliques and Large Cardinals 5/3/11 3:40AM
458: Sequential Constructions for Large Cardinals 5/5/11 10:37AM
459: Greedy CLique Constructions in the Integers 5/8/11 1:18PM
460: Greedy Clique Constructions Simplified 5/8/11 7:39PM
461: Reflections on Vienna Meeting 5/12/11 10:41AM
462: Improvements/Pi01 Independence 5/14/11 11:53AM
463: Pi01 independence/comprehensive 5/21/11 11:31PM
464: Order Invariant Split Theorem 5/30/11 11:43AM
465: Patterns in Order Invariant Graphs 6/4/11 5:51PM
466: RETURN TO 463/Dominators 6/13/11 12:15AM
467: Comment on Minimal Dominators 6/14/11 11:58AM
468: Maximal Cliques/Incompleteness 7/26/11 4:11PM
469: Invariant Maximality/Incompleteness 11/13/11 11:47AM
470: Invariant Maximal Square Theorem 11/17/11 6:58PM
471: Shift Invariant Maximal Squares/Incompleteness 11/23/11 11:37PM
472. Shift Invariant Maximal Squares/Incompleteness 11/29/11 9:15PM
473: Invariant Maximal Powers/Incompleteness 1 12/7/11 5:13AMs
474: Invariant Maximal Squares 01/12/12 9:46AM
475: Invariant Functions and Incompleteness 1/16/12 5:57PM
476: Maximality, CHoice, and Incompleteness 1/23/12 11:52AM
477: TYPO 1/23/12 4:36PM
478: Maximality, Choice, and Incompleteness 2/2/12 5:45AM
479: Explicitly Pi01 Incompleteness 2/12/12 9:16AM
480: Order Equivalence and Incompleteness
481: Complementation and Incompleteness 2/15/12 8:40AM
482: Maximality, Choice, and Incompleteness 2 2/19/12 7:43AM
483: Invariance in Q[0,n]^k 2/19/12 7:34AM
484: Finite Choice and Incompleteness 2/20/12 6:37AM__
485: Large Large Cardinals 2/26/12 5:55AM
Harvey Friedman
More information about the FOM
mailing list