FOM: 96:Comments on BRT
Harvey Friedman
friedman at math.ohio-state.edu
Wed Dec 20 09:20:13 EST 2000
THE FOM E-MAIL LIST NOW HAS EXACTLY 500 SUBSCRIBERS!!!
I make a practice of not putting (extended) informal remarks on my numbered
series of postings. This numbered posting is an exception because the
matter is so important and relevant to Boolean Relation Theory. Also, the
main line of argument here is one which I have used in a public lecture at
a Logic Meeting (the recent Midwest Philosophy of Mathematics Workshop held
at CMU), and I intend to use it in the future.
See disclaimer in the last paragraph at the end.
1. NATURALNESS OF BRT SETUP AND INDEPENDENT INSTANCES.
We refer to posting #95, which is the state of the art extended abstract on
BRT. It should be clear from that abstract that BRT provides a very wide
range of very natural finite families of mathematical problems, where very
interesting special cases are highly nontrivial. These finite families of
mathematical problems have a permanent place in the mathematical
literature.
Moreover, it is clear that at least in the one case intensively studied -
that of integral multivariate functions of expansive linear growth (and
related classes of functions), and the bi-infinite subsets of Z - there are
particular instances that are tied up with large cardinals which are also
very natural.
Posting #95 contains new material related to presenting these particular
instances tied up with large cardinals in the most natural way. In
particular, there is new motivation that leads up to the crucial - and
natural - notion of a disjoint cover tower.
Disjoint covers are introduced as a way of restating the extremely natural
complementation theorem, which is a fundamental fixed point theorem:
"Let f be a strictly dominating integral multivariate function. There
exists an infinite A containedin Z such that fA = A'. There is a unique A
containedin Z such that fA = A'."
This becomes
"Let f be a strictly dominating integral multivariate function. There
exists an infinite A containedin Z such that Z is disjointly covered by
A,fA. There is a unique A containedin Z such that Z is disjointly covered
by fA = A'."
This is an infinite disjoint cover theorem. One asks for a bi-infinite
disjoint cover theorem. After a succession of attempts with
counterexamples, one is inexorably led to the theorem
"Let f,g be strictly dominating integral multivariate functions. There
exists bi-infinite A containedin B containedin Z such that fA is disjointly
covered by B,gB, and fB is disjointly covered by C,gC."
This is restated as:
"Every pair of strictly dominating integral multivariate functions has a
bi-infinite disjoint cover tower of length 2."
This leads inexorably to
"Every pair of integral multivariate functions of expansive linear growth
has a bi-infinite disjoint cover tower of length 3."
"Every pair of integral multivariate functions of expansive linear growth
has a bi-infinite disjoint cover tower of every finite length."
Both of these are equivalent to the 1-consistency of Mahlo cardinals of
finite order over ACA.
2. IT IS NOT ESSENTIAL THAT THERE ARE SPECIFIC NATURAL INSTANCES TIED UP
WITH LARGE CARDINALS.
The ultimate success of BRT in causing a sea change in f.o.m. is not
dependent on their being natural specific instances of these finite sets of
problems that are tied up with large cardinals. As indicated above, there
are, indeed, natural such instances in the case of (expansive linear
growth,bi-infinite). However, there may well be many other interesting BRT
settings (V,K) where there are instances tied up with large cardinals, but
where no really natural instances are.
There are many reasons why it is enough that these very natural finite sets
of problems merely have some instance that is tied up with large cardinals.
Above and beyond this, there is the reality and expectations of very
natural SINGLE SENTENCES associated with the classfication that do not
depend in any way on natural single instances. These state the so called
finiteness property (a transfer principle from finite to, e.g.,
bi-infinite). See e) below.
a. There is the complete expectation that ALL problems in such natural
classes of problems can be proved or refuted using large cardinals. This
would establish the necessary and sufficient need for large cardinals (or
equivalents) in order to develop a certain natural mathematical theory.
I.e., necessary and sufficient to carry out various classifications. There
are two related reasons for this expectation.
b. One is that at least in the apparently critical cases of two functions
and three sets - and probably higher up - there is the informed feeling of
experts that one simply cannot get any coding apparatus started in any way
in order to diagonalize and/or create artificial examples of anything. So
the intuition is that the finite set of statements must amount to something
coherent as a totality. And that something must be measured by a level in
the large cardinal hierarchy. At least this is what would appear to be
almost certainly the case to any expert in set theory and related matters.
c. The second is that one has significant partial results already which
vindicate b in some particularly satisfying ways. In particular, I have
classified all statements in disjoint cover theory (a weakened but totally
natural form of Boolean relation theory) on (expansive linear
growth,bi-infinite) with two functions and three sets and two disjoint
cover conditions (rather than any number). There are nearly one million of
these pairs, and I had to seriously look at about 800 of them. I found that
every statement is provable or refutable in RCA_0, or provably equivalent
to the 1-consistency of Mahlo cardinals of finite order over ACA.
d. In addition, the aforementioned classification had a striking property
which we call finiteness. That if it is true in (expansive linear
growth,nonempty finite) then it is true in the case at hand, (expansive
linear growth,bi-infinite). It is also clear that the classification can be
carefully examined and presented in an intelligible way. I gave a table
with about 800 entries, with auxiliary theorems indicating how the table
classifies all of the nearly one million pairs. But this sort of pruning
can be continued much further. And of course such pruning must be done in
order to handle the vastly larger classes. E.g., what about disjoint cover
theory in (expansive linear growth,bi-infinite) with two functions and
three sets and three disjoint cover conditions, let alone full disjoint
cover theory in (expansive linear growth,bi-infinite) in two functions and
three sets? Yet does anyone doubt large cardinals are necesssary and
sufficient to handle three disjoint cover conditions here, or even full
disjoint cover theory here? Incidentally, full disjoint cover theory for
(expansive linear growth,bi-infinite) with two functions and two sets has
been completely classified, and every statement is provable or refutable in
RCA_0.
e. So in any case, we can consider the finiteness property for
classficiations, as well as other related properties. Then we have the
SINGLE SENTENCE
"if a statement in this class holds with nonempty finite sets, then it
holds as intended."
And this single sentence will be equivalent to the 1-consistency of large
cardinals. As a special case, we know that
"if a statement in disjoint cover theory with two functions, three sets,
two disjoint cover conditsions, holds on (expansive linear growth,nonempty
finite), then it holds on (expansive linear growth,bi-infinite)"
is provably equivalent to the 1-consistency of Mahlo cardinals of finite
order over ACA.
And we can do all of this without having to address any question of natural
instances that are tied up with large cardinals (even though there are
such)!
f. In particular, we conjecture the SINGLE SENTENCE
"if a statement in Boolean relation theory with two functions and three
sets holds on (expansive linear growth,nonempty finite) then it holds on
(expansive linear growth,bi-infinite)"
is provably equvialent to the 1-consistency of Mahlo cardinals of finite
order over ACA. It certainly implies it. And if this conjecture proves to
be erroneous, then no doubt it can be watered down so that it holds. E.g.,
maybe it needs to be watered down to disjoint cover theory only.
3. NEVERTHELESS, THERE ARE ALWAYS NATURAL INSTANCES TIED UP WITH LARGE
CARDINALS.
I conjecture that in any natural BRT setting (V,K) with n functions and m
sets, where n,m are very small, and where there is an instance that is tied
up with large cardinals, and where there is no such instance with n-1
functions and m sets, then there is a natural instance that is tied up with
large cardinals.
4. SHOCK OVER THE UNEXPECTEDLY tiny AMOUNT OF KNOWN MATHEMATICS.
The Earth has been in existence for billions of years. There are perhaps
trillions of stars and planets elsewhere. Yet we have access to only about
a few hundred years worth of intensive mathematical production. Since there
has been a huge increase in production rates, one can argue that we have
access to only, say, at most 100 years worth of mathematical production
under current conditions.
100 years is very small compared to billions of years, or even the roughly
1 million years of man. http://china-window.com/wenwu/Pal/3e.htm And this
does not take into account the rest of the incredibly vast physical
universe.
So one would normally expect to have access to a much greater number of
years worth of mathematical production under current prodution rates. Even
if we include the rather unexpected recent ascent of humans, a more normal
minimal expectation would be something on the order of, say, 25,000 years
worth of mathematical production under current conditions.
Taking a much more global, or universal, view, it is reasonable to expect
access to, say, 100 million years worth of mathematical production under
current conditions. Contrast this with the 100 years worth of mathematical
production under current conditions that is a liberal upper bound on
reality.
Now how would you compare 100 years worth with 100 million years worth?
>From this point of view, it is clear that all of the mathematics we know
today is but some completely trivial initial segment of the virtually
unimaginable development that awaits us.
So to reject the role of Boolean relation theory in the coming sea change
in f.o.m. on the basis of its not having been thought of by mathematicians
BY NOW can only be based on an absurdly naive misunderstanding of the
development of mathematics.
The issue is rather of the inevitability of the acceptance of BRT as a
permanent force in the mathematical culture of the future. And that is
quite easily argued.
But first let me drive home the point made above about expectations and bad
luck made above in another way.
5. SHOCK AND BAD LUCK OVER THE UNEXPECTEDLY tiny AMOUNT OF KNOWN MEDICAL
SCIENCE.
It is shocking but true that we are today among the last living humans that
will have to completely die. This is very unexpected bad luck. Had we been
born somewhat later - not too much later - then we would not have this
annoying problem.
This time the bad luck is really sad. Just perhaps another 1000 years,
which is a very short period of time. Nothing needed like, say, 1 million
years. Optimists say even 100 years might be enough. And lots of people
think that even 50 years will push the life span of newborns to, say, 200
years. Would even a pessimist doubt that in 1 million years, the life
expectancy of newborns would be virtually unlimited (with brain backup if
all physical parts need to be replaced)? And that is also a very short
period of time given the age of the Earth. Too bad, so sad.
6. INEVITABILITY OF BOOLEAN RELATION THEORY.
I tend to believe that there are no concrete mathematical problems in the
literature RIGHT NOW that are independent of the axioms of ZFC.
But I am even more convinced that this state of affairs is only temporary,
and a consequence of the unexpectedly tiny amount of known mathematics (see
4 above). I.e., the very opposite is the normal and expected state of
affairs.
Of course, I am intervening into this situation by introducing Boolean
Relation Theory into the literature, PREMATURELY, and getting all sorts of
mathematicians from various fields to prove theorems and publish in and
hold meetings on Boolean Relation Theory.
And why should I wait till, say, the year 7512 when Boolean relation theory
for (expansive linear growth,bi-infinite) is classified using only RCA_0
for 2 functions and 2 sets (not yet known, but well on its way), and
certain simple hard instances crop up for 2 functions and 3 sets? So then I
can come in and settle them with necessary uses of large cardinals?
I won't wait until 7512 because I can't afford to.
Actually, BRT looks more like something before 2100 to me, without my
intervention. But 2100, 7512, who cares? This is still just around the
corner compared to geological and universal time.
Now let's talk about the inevitability of Boolean relation theory and
attempts to classify all statements in Boolean relation theory under
various contexts and restrictions.
First of all, the idea of identifying important logical forms for
mathematical statements that are significant because of the expressive
power and the fact that something can be proved about such statements
generally is now well ingrained in the mathematical culture, especially in
the culture of mathematical logic.
The most well known and accessible examples of this are
a) All first order sentences in the ordered group of integers (Presburger
arithmetic). Here there is an intelligible complete set of axioms, and a
kind of classification beyond recursive solvability in terms of quantifier
elimination. And various more refined results concerning fragments.
b) All first order sentences in the ordered field of real numbers (Tarski's
work on real closed fields). Same situation.
c) All first order sentences in the field of complex numbers. Same situation.
d) All first order sentences in Euclidean and other geometries. Same situation.
There are many other more modern instances, and this is not the place to
conduct a survey. Suffice it to say that the modern history involves being
more delicate about the choice of mathematical objects and the choice of
logical forms to be analyzed; witness, e.g., monadic second order theories.
Of course, it has been tacitly assumed that one must go for classifying
infinite families of statements. That it would not be interesting to
classify finite families of statements. The thought has been, say, that any
finite set is recursively solvable, and so what do you get by classifying?
But it has already been known for some time that one should be suspicious
of rejecting the finite this way in light of the development of theoretical
and applied computer science. Without much loss of generality, vast
developments there can be assumed to be about strictly finite families of
objects. E.g., strings of only reasonable length.
At the same time, we have the Ramsey theory community striving to make
their subject look even more elegant, simple, compelling, and connected
with other areas of mathematics. Of course, that is a part of a more
general effort of combinatorists generally, including algebraic
combinatorists, of trying to make their subject connect up with other areas
of mathematics, and be immediately accessible and impressive to
mathematicians generally.
So when the Ramsey theorists heard about the Thin Set Theorem:
"every integral multivariate function omits a value on some infinite set"
they perked up and demanded to see the proof of it, and some explicitly
said that they were surprised to see something that elementary that
requires (apparently) Ramsey theory, and wished that they thought of it.
And then, just as expected, I showed the Thin Set Theorem to many fancy
mathematicians way outside combinatorics, who don't particularly like
combinatorics, and they related to it very well, sometimes demanding to see
a proof of it, and trying to prove it on the spot without success.
Then I point out that this is a Boolean conclusion (actually a Boolean
inequality), and then Boolean relation theory is off and running.
In particular, using more functions and more sets is verified in discussion
to be part of the standard development of mathematics in virtually all
contexts - akin to related moves like going to higher dimensions, etcetera.
And placing growth conditions like expansive linear growth or quadratic
growth, etcetera, is completely standard throughout mathematics. Etcetera.
So through the forces of
a) identifying logical forms and making classifications (championed by
logicians, mainly); and
b) looking for elementary but deep and accessible mathematical nuggets;
c) specific efforts of combinatorists along the lines of b);
d) natural moves including more objects and growth conditions, etcetera.
one sees the inevitability of Boolean relation theory, at least over time.
And maybe even fairly soon without my intervention.
7. SPEEDING UP AN OBVIOUSLY INEVITABLE PROCESS.
So I view myself as speeding up an inevitable process. I cannot afford to
wait since I certainly do not expect to live even to the middle of the
(coming) Century.
In light of the examples of the Thin Set Theorem and the Complementation
Theorem, we see that Boolean relation theory and disjoint cover theory have
a permanent place in the history of mathematics.
Substantial classifications can be carried out using normal mathematical
methods, but when pushed a bit more require uses of large cardinals.
Beautiful classfication results can only be obtained using large cardinals.
Moreover, we have a very natural situation in terms of specific instances.
In light of the Complementation Theorem and related considerations, the
notion of disjoint cover tower is entirely fundamental enough to have a
permanent place in the history of mathematics.
With disjoint over towers, one has the magic key to necessary uses of set
theory, including large cardinal theory.
All of this assumes, of course, that there are no problems with the
delicate reversals. The crucial opus 1 paper is being prepared now from
drafts that already exist, and I expect things will become very solid in
the next few months.
****************************
This is the 96th in a series of self contained postings to FOM covering
a wide range of topics in f.o.m. Previous ones are:
1:Foundational Completeness 11/3/97, 10:13AM, 10:26AM.
2:Axioms 11/6/97.
3:Simplicity 11/14/97 10:10AM.
4:Simplicity 11/14/97 4:25PM
5:Constructions 11/15/97 5:24PM
6:Undefinability/Nonstandard Models 11/16/97 12:04AM
7.Undefinability/Nonstandard Models 11/17/97 12:31AM
8.Schemes 11/17/97 12:30AM
9:Nonstandard Arithmetic 11/18/97 11:53AM
10:Pathology 12/8/97 12:37AM
11:F.O.M. & Math Logic 12/14/97 5:47AM
12:Finite trees/large cardinals 3/11/98 11:36AM
13:Min recursion/Provably recursive functions 3/20/98 4:45AM
14:New characterizations of the provable ordinals 4/8/98 2:09AM
14':Errata 4/8/98 9:48AM
15:Structural Independence results and provable ordinals 4/16/98
10:53PM
16:Logical Equations, etc. 4/17/98 1:25PM
16':Errata 4/28/98 10:28AM
17:Very Strong Borel statements 4/26/98 8:06PM
18:Binary Functions and Large Cardinals 4/30/98 12:03PM
19:Long Sequences 7/31/98 9:42AM
20:Proof Theoretic Degrees 8/2/98 9:37PM
21:Long Sequences/Update 10/13/98 3:18AM
22:Finite Trees/Impredicativity 10/20/98 10:13AM
23:Q-Systems and Proof Theoretic Ordinals 11/6/98 3:01AM
24:Predicatively Unfeasible Integers 11/10/98 10:44PM
25:Long Walks 11/16/98 7:05AM
26:Optimized functions/Large Cardinals 1/13/99 12:53PM
27:Finite Trees/Impredicativity:Sketches 1/13/99 12:54PM
28:Optimized Functions/Large Cardinals:more 1/27/99 4:37AM
28':Restatement 1/28/99 5:49AM
29:Large Cardinals/where are we? I 2/22/99 6:11AM
30:Large Cardinals/where are we? II 2/23/99 6:15AM
31:First Free Sets/Large Cardinals 2/27/99 1:43AM
32:Greedy Constructions/Large Cardinals 3/2/99 11:21PM
33:A Variant 3/4/99 1:52PM
34:Walks in N^k 3/7/99 1:43PM
35:Special AE Sentences 3/18/99 4:56AM
35':Restatement 3/21/99 2:20PM
36:Adjacent Ramsey Theory 3/23/99 1:00AM
37:Adjacent Ramsey Theory/more 5:45AM 3/25/99
38:Existential Properties of Numerical Functions 3/26/99 2:21PM
39:Large Cardinals/synthesis 4/7/99 11:43AM
40:Enormous Integers in Algebraic Geometry 5/17/99 11:07AM
41:Strong Philosophical Indiscernibles
42:Mythical Trees 5/25/99 5:11PM
43:More Enormous Integers/AlgGeom 5/25/99 6:00PM
44:Indiscernible Primes 5/27/99 12:53 PM
45:Result #1/Program A 7/14/99 11:07AM
46:Tamism 7/14/99 11:25AM
47:Subalgebras/Reverse Math 7/14/99 11:36AM
48:Continuous Embeddings/Reverse Mathematics 7/15/99 12:24PM
49:Ulm Theory/Reverse Mathematics 7/17/99 3:21PM
50:Enormous Integers/Number Theory 7/17/99 11:39PN
51:Enormous Integers/Plane Geometry 7/18/99 3:16PM
52:Cardinals and Cones 7/18/99 3:33PM
53:Free Sets/Reverse Math 7/19/99 2:11PM
54:Recursion Theory/Dynamics 7/22/99 9:28PM
55:Term Rewriting/Proof Theory 8/27/99 3:00PM
56:Consistency of Algebra/Geometry 8/27/99 3:01PM
57:Fixpoints/Summation/Large Cardinals 9/10/99 3:47AM
57':Restatement 9/11/99 7:06AM
58:Program A/Conjectures 9/12/99 1:03AM
59:Restricted summation:Pi-0-1 sentences 9/17/99 10:41AM
60:Program A/Results 9/17/99 1:32PM
61:Finitist proofs of conservation 9/29/99 11:52AM
62:Approximate fixed points revisited 10/11/99 1:35AM
63:Disjoint Covers/Large Cardinals 10/11/99 1:36AM
64:Finite Posets/Large Cardinals 10/11/99 1:37AM
65:Simplicity of Axioms/Conjectures 10/19/99 9:54AM
66:PA/an approach 10/21/99 8:02PM
67:Nested Min Recursion/Large Cardinals 10/25/99 8:00AM
68:Bad to Worse/Conjectures 10/28/99 10:00PM
69:Baby Real Analysis 11/1/99 6:59AM
70:Efficient Formulas and Schemes 11/1/99 1:46PM
71:Ackerman/Algebraic Geometry/1 12/10/99 1:52PM
72:New finite forms/large cardinals 12/12/99 6:11AM
73:Hilbert's program wide open? 12/20/99 8:28PM
74:Reverse arithmetic beginnings 12/22/99 8:33AM
75:Finite Reverse Mathematics 12/28/99 1:21PM
76: Finite set theories 12/28/99 1:28PM
77:Missing axiom/atonement 1/4/00 3:51PM
78:Qadratic Axioms/Literature Conjectures 1/7/00 11:51AM
79:Axioms for geometry 1/10/00 12:08PM
80.Boolean Relation Theory 3/10/00 9:41AM
81:Finite Distribution 3/13/00 1:44AM
82:Simplified Boolean Relation Theory 3/15/00 9:23AM
83:Tame Boolean Relation Theory 3/20/00 2:19AM
84:BRT/First Major Classification 3/27/00 4:04AM
85:General Framework/BRT 3/29/00 12:58AM
86:Invariant Subspace Problem/fA not= U 3/29/00 9:37AM
87:Programs in Naturalism 5/15/00 2:57AM
88:Boolean Relation Theory 6/8/00 10:40AM
89:Model Theoretic Interpretations of Set Theory 6/14/00 10:28AM
90:Two Universes 6/23/00 1:34PM
91:Counting Theorems 6/24/00 8:22PM
92:Thin Set Theorem 6/25/00 5:42AM
93:Orderings on Formulas 9/18/00 3:46AM
94:Relative Completeness 9/19/00 4:20AM
95:Boolean Relation Theory III 12/19/00 7:29PM
More information about the FOM
mailing list