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