FOM: 82:Simplified Boolean Relation Theory
Harvey Friedman
friedman at math.ohio-state.edu
Wed Mar 15 09:23:10 EST 2000
This is a progress report on Boolean relation theory. Boolean Relation
Theory is abbreviated BRT.
We have found a promising new way to simplify Boolean relation theory in
order to obtain a suitably
strong classification result (substantially better than the one announced
in posting #80), given that the main classification conjecture is going to
take some extended time to prove.
In the search for such a suitably strong classification result, we have
come across some
thematic simplifications in Boolean relation theory that make the
classifications more manageable.
1. EQUATIONAL BOOLEAN RELATION THEORY (EBRT).
This is from posting 80:Boolean Relation Theory, Fri, 10 Mar 2000 09:41.
Let (V,K) be given, where V is a set of multivariate functions and K is a
family of sets. Let n,m >= 1 and E be a Boolean equation in (1+n)m
set variables. Determine whether the following
statement holds:
alpha) For all f_1,...,f_n in V there exist A_1,...,A_m in K such that E holds
of the A's and their images under the f's.
I.e.,
beta) For all f_1,...,f_n in V there exist A_1,...,A_m in K such that E
holds of the (1+n)m sets A_1,...,A_m,f_1A_1,...,f_1A_m,f_nA_1,...,f_nA_m.
If we say "Boolean Relation Theory" then we allow more general kinds of
Boolean relations among the (1+n)m sets than just Boolean equations. This
leads to an incomparably richer theory, but BRT is already too vast for the
moment. See the discussion in section 2 of posting #80, of generalized
Boolean equation statements.
2. SIMPLIFIED BOOLEAN RELATION THEORY (SBRT).
SBRT is a thematic simplification of Boolean relation theory, where general
Boolean equations are removed in favor of only coverings and exclusions,
which are respectively of the forms
A containedin B_1 union ... union B_k
A intersection B = emptyset
applied to sets and their images. For example, in A,B,C,fA,fB,fC,gA,gB,gC,
a typical covering is
fA containedin C union gA
and a typical exclusion is
C intersect fC = emptyset.
We formally present simplified Boolean relation theory.
Let (V,K) be given, where V is a set of multivariate functions and K is a
family of sets. Let n,m >= 1 and E be a list of coverings and exclusions
in (1+n)m set variables. Determine
whether the following statement holds:
alpha) For all f_1,...,f_n in V there exist A_1,...,A_m in K such that E holds
of the A's and their images under the f's.
I.e.,
beta) For all f_1,...,f_n in V there exist A_1,...,A_m in K such that E holds
of the (1+n)m sets A_1,...,A_m,f_1A_1,...,f_1A_m,f_nA_1,...,f_nA_m.
3. VERY SIMPLIFIED BOOLEAN RELATION THEORY (VSBRT).
Simplified boolean relation theory is still too much for this very early
stage of Boolean relation theory.
We define a forward covering in sets A_1,...,A_m,f_1A_1,...,f_1A_m as a
covering where the subscript on the left side is strictly smaller than all
subscripts on the right side.
We now present very simplified Boolean relation theory.
Let (V,K) be given, where V is a set of multivariate functions and K is a
family of sets. Let n,m >= 1 and E be a list of forward coverings and
exclusions in (1+n)m set variables. Determine whether the following
statement holds:
alpha) For all f_1,...,f_n in V there exists m sets A_1 containedin ...
containedin A_m from K such that E holds of the A's and their images under
the f's.
I.e.,
beta) For all f_1,...,f_n in V there exists m sets A_1 containedin ...
containedin A_m from K such that E holds of the (1+n)m sets
A_1,...,A_m,f_1A_1,...,f_1A_m,f_nA_1,...,f_nA_m.
4. INSTANCES REQUIRING LARGE CARDINALS.
Fix V to be the set of all multivariate functions from N into N of
expansive linear growth as in posting #80, section 5. Let K be the family
of all infinite subsets of N.
THEOREM 4.1. There is an instance of VSBRT with two functions from V
and three sets from K and two forward coverings and two exclusions using
seven sets (out of
nine) for which it is necessary and sufficient to use large cardinals.
PROMISE: When the dust settles a little more, I will display and discuss
these particular simple instances.
Theorem 4.1 is quite robust. In partciular, we can use other growth
conditions for V. E.g, for each real number r > 1 we can take V = V(r) to
be the set of
all multivariate functions from N into N such that there exists real
constants c,d > 0 where the inequality
c|x|^r <= f(x) <= d|x|^r
holds with finitely many exceptions, and |x| denotes any l_p norm, 0 < p <=
infinity. Also we can take K to be the family of all "thin" infinite
subsets of N. In particular, we can take K to be the family K' of infinite
subsets of N of density zero. Under all of these choices of (V,K), these
same instances represent necessary and sufficient use of large cardinals.
5. WORK IN PROGRESS.
We are finishing up work on VSBRT for (V,K) with two functions and three
sets.
We have had enough experience with VSBRT to see that it leads to a barely
manageable
number of cases that require serious investigation - under a thousand. The
proliferation of cases that require investigation - into the millions and
even much higher - is the main barrier to obtaining really strong
classification results at this early stage of Boolean relation theory,
where powerful theory is lacking.
A large number of simple statements about the classification are being
obtained (test questions), for which it is necessary and sufficient to use
large cardinals.
6. STATUS REPORT
We have written up a sketch of the proof from large cardinals (Mahlo
cardinals of finite order) of the particular instances mentioned in Theorem
4.1, and lectured on them in a seminar.
As soon as the VSBRT classification is completed, and test questions
analyzed, and results announced, we will write up a sketch of the crucial
proof that the particular instances mentioned necessarily use large
cardinals.
**********
This is the 82nd 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
More information about the FOM
mailing list