FOM: 150:Finite obstruction/statistics
friedman@math.ohio-state.edu
friedman at math.ohio-state.edu
Sat Jun 1 08:55:03 EDT 2002
THIS POSTING IS SELF CONTAINED.
Recall the following statement:
PROPOSITION 1. For all multivariate functions f,g from N into N of expansive
linear growth, there exists infinite A,B,C containedin N such that
A U. fA containedin C U. gB
A U. fB containedin C U. gC.
{Recall that U. is disjoint union, which is ordinary union together with the
assertion of disjointness. Recall that hX is the set of all values of h at
arguments drawn from X. The above is a particularly elegant focused corner of
Boolean Relation Theory}.
##################################
Recall that the climax of the work thus far (on demonstrably necessary uses of
transcendental set theoretic methods in elementary discrete mathematics) is a
complete classification of the 3^8 = 6561 statements obtained by replacing the
eight occurrences of the letters from {A,B,C} in Proposition 1 with any choice
of eight letters from {A,B,C}. This classification is carried out without
resorting to any set theoretic methods (in fact within RCA_0) except for a
single case up to symmetry (actually 12 cases if we use ordered pairs, and 6
cases if we use unordered pairs). In this one case (up to symmetry) where we
resort to set theoretic methods, we know that this is necessary in that the
statement is provable in ZFC + "Mahlo cardinals of all finite orders exist"
but not in ZFC.
We have considered the same classification problem with "infinite" replaced by
"nonempty finite" and "arbitrarily large finite". We have carried out the
classifications in these three cases without resorting to any set theoretic
methods (in fact within RCA_0). With "nonempty finite" and "arbitrarily large
finite" there is no singular case.
Remarkably, all three classifications, with "infinite", "nonempty finite", and
"arbitrarily large finite", are identical. However, to establish this
identity,
we need large cardinals in that the statement that the three classifications
are identical is itself provable in ZFC + "Mahlo cardinals of all finite
orders
exist" but not in ZFC. Note that the statement of identity between the three
classifications does not refer to any one case.
We now interpret one aspect of this identity between classifications. If we
fail to find infinite sets A,B,C with some given pair of inclusions, then we
cannot even find nonempty finite sets A,B,C with that given pair of
inclusions.
Hence there must be what we call a "finite obstruction". As we indicate three
paragraphs below, this finite obstruction statement itself cannot be proved
within ZFC.
Breaking this down, first of all the identity between the classifications with
"nonempty finite" and "arbitrarily large finite" is established without
resorting to set theoretic methods (in fact within RCA_0), since each
classification is so carried out, and they are just compared.
The implication from any statement with "infinite" to the corresponding
statement with "arbitrarily large finite" can be proved without resorting to
set theoretic methods (in fact within RCA_0).
The implication from any statement with "nonempty finite" to the corresponding
statement with "infinite" can also be proved without resorting to set
theoretic
methods (in fact within RCA_0) except in the one singular case (up to
symmetry). In that one singular case (up to symmetry) that implication
requires
large cardinals in the sense that that implication is provable in ZFC + "Mahlo
cardinals of all finite orders exist" but not in ZFC.
We now mention another classification that we have carried out. We have
classified all 3^8 = 6561 statements obtained from Proposition 1 with "of
expansive linear growth" removed. This classification substantially differs
from the above discussed classifications as expected. We have carried out this
classification without resorting to set theoretic methods (in fact within
RCA_0).
We now present some statistics. We first present them in terms of ordered
pairs
of statements with a sample space of 3^8 = 6561 as used in the above
discussion.
In the three classifications with "infinite", "nonempty finite", and
"arbitrarily large finite", of the 6561 statements, 414 are provable in RCA_0,
6135 are refutable in RCA_0, and 12 are provably equivalent to the 1-
consistency of ZFC + "Mahlo cardinals of finite order". These percentages are
approximately 6.31%, 93.51%, and .18%, respectively.
If we use unordered pairs, then the sample space consists of C(81,2) = 3240
statements. This is a little less than half of 6561 since unordered pairs do
not include the singletons. Of these statements, 189 are provable in RCA_0,
3045 are refutable in RCA_0, and 6 are provably equivalent to the 1-
consistency
of ZFC + "Mahlo cardinals of finite order". These percentages are
approximately
5.83%, 93.98%, .19%, respectively.
In each of these three sample spaces above based on ordered pairs and
unordered
pairs, with "infinite", we can consider the 2 Propositions that state the
number of true cases. I.e.,
PROPOSITION A. Proposition 1 holds with exactly (at least) 426 ordered pairs
of such inclusion relations.
PROPOSITION B. Proposition 1 holds with exactly (at least) 195 unordered pairs
of such inclusion relations.
Each of these Propositions requires large cardinals in that they are provable
in ZFC + "Mahlo cardinals of all finite orders exist" but not in ZFC.
Every statement that we assert above to be provable in ZFC + "Mahlo cardinals
of all finite orders exist" but not in ZFC is in fact provably equivalent to
the 1-consistency of ZFC + {there exists a Mahlo cardinal of order n}_n,
within
ACA.
*********************************************
I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 150th in a series of self contained postings to FOM covering
a wide range of topics in f.o.m. Previous ones counting from #100 are:
100:Boolean Relation Theory IV corrected 3/21/01 11:29AM
101:Turing Degrees/1 4/2/01 3:32AM
102: Turing Degrees/2 4/8/01 5:20PM
103:Hilbert's Program for Consistency Proofs/1 4/11/01 11:10AM
104:Turing Degrees/3 4/12/01 3:19PM
105:Turing Degrees/4 4/26/01 7:44PM
106.Degenerative Cloning 5/4/01 10:57AM
107:Automated Proof Checking 5/25/01 4:32AM
108:Finite Boolean Relation Theory 9/18/01 12:20PM
109:Natural Nonrecursive Sets 9/26/01 4:41PM
110:Communicating Minds I 12/19/01 1:27PM
111:Communicating Minds II 12/22/01 8:28AM
112:Communicating MInds III 12/23/01 8:11PM
113:Coloring Integers 12/31/01 12:42PM
114:Borel Functions on HC 1/1/02 1:38PM
115:Aspects of Coloring Integers 1/3/02 10:02PM
116:Communicating Minds IV 1/4/02 2:02AM
117:Discrepancy Theory 1/6/02 12:53AM
118:Discrepancy Theory/2 1/20/02 1:31PM
119:Discrepancy Theory/3 1/22.02 5:27PM
120:Discrepancy Theory/4 1/26/02 1:33PM
121:Discrepancy Theory/4-revised 1/31/02 11:34AM
122:Communicating Minds IV-revised 1/31/02 2:48PM
123:Divisibility 2/2/02 10:57PM
124:Disjoint Unions 2/18/02 7:51AM
125:Disjoint Unions/First Classifications 3/1/02 6:19AM
126:Correction 3/9/02 2:10AM
127:Combinatorial conditions/BRT 3/11/02 3:34AM
128:Finite BRT/Collapsing Triples 3/11/02 3:34AM
129:Finite BRT/Improvements 3/20/02 12:48AM
130:Finite BRT/More 3/21/02 4:32AM
131:Finite BRT/More/Correction 3/21/02 5:39PM
132: Finite BRT/cleaner 3/25/02 12:08AM
133:BRT/polynomials/affine maps 3/25/02 12:08AM
134:BRT/summation/polynomials 3/26/02 7:26PM
135:BRT/A Delta fA/A U. fA 3/27/02 5:45PM
136:BRT/A Delta fA/A U. fA/nicer 3/28/02 1:47AM
137:BRT/A Delta fA/A U. fA/beautification 3/28/02 4:30PM
138:BRT/A Delta fA/A U. fA/more beautification 3/28/02 5:35PM
139:BRT/A Delta fA/A U. fA/better 3/28/02 10:07PM
140:BRT/A Delta fA/A U. fA/yet better 3/29/02 10:12PM
141:BRT/A Delta fA/A U. fA/grammatical improvement 3/29/02 10:43PM
142:BRT/A Delta fA/A U. fA/progress 3/30/02 8:47PM
143:BRT/A Delta fA/A U. fA/major overhaul 5/2/02 2:22PM
144: BRT/A Delta fA/A U. fA/finesse 4/3/02 4:29AM
145:BRT/A U. B U. TB/simplification/new chapter 4/4/02 4:01AM
146:Large large cardinals 4/18/02 4:30AM
147:Another Way 7:21AM 4/22/02
148:Finite forms by relativization 2:55AM 5/15/02
149:Bad Typo
More information about the FOM
mailing list