FOM: 100:Boolean Relation Theory IV corrected

Harvey Friedman friedman at math.ohio-state.edu
Wed Mar 21 11:29:43 EST 2001


 In posting #99, there were a critical mass of typos and also, on some
 computers, some ... came out as S. Given the length of #99, we thought it
 best to post a full, corrected version.

 ************************************************

 This is a self contained restatement of present highlights of Boolean
 relation theory. It obsoletes the previous statement, posting #95.

 NOTE: This is intended to be the last comprehensive statement before the
 major papers on BRT are finished and made available. I am at the outer
 limit of what I can safely claim before these major papers are finished.

 BOOLEAN RELATION THEORY
 by
 Harvey M. Friedman
 friedman at math.ohio-state.edu
 www.math.ohio-state.edu/~friedman/
 Extended Abstract
 March 8, 2001
 corrected March 21, 2001

 Boolean relation theory concerns the relationship between sets and their
 images under multivariate and multidimensional functions. We give detailed
 formulations of Boolean relation theory and its specializations.

 Boolean relation theory quickly leads to particularly simple discrete
 mathematical statements that are not only independent of ZFC (Zermelo
 Frnakel set theory with the axiom of choice), but also statements that can
 be proved with and only with certain large cardinal axioms extending ZFC.
 This holds even if rather concrete functions and sets are u sed, resulting
 in statements readily formalizable in arithmetic with the same
 metamathematical properties.

 1. MULTIVARIATE AND MULTIDIMENSIONAL FUNCTIONS.

 We say that f is a multivariate function if and only if f is a pair (g,k),
 where k >= 1 (the arity of f) and g is a function whose domain is a set of
 ordered k-tuples.

 We write dom(f) for dom(g), and define f(x_1,...,x_k) = g(<x_1,...,x_k>).

 We pair with k in order to avoid any ambiguity regarding the arity. In
 practice, the intended arity is obvious and we omit the k.

 BRT is based on the following notion of forward image of a multivariate
 function on a set. Let f be a multivariate function and A be a set. We
 define fA = {f(x_1,...,x_k): k is the arity of f and x_1,...,x_k in A}.

 We could have written f[A^k], but it is convenient to suppress the arity
 and write fA. In this way, f defines a special kind of operator from sets
 to sets.

 We say that f is a multivariate function from A into B if and only if f is
 a multivariate function with dom(f) = A^k and rng(f) containedin B, where f
 has arity k.

 More generally, we say that f is a multidimensional function if and only if
 f is a triple (g,k,r), where k,r >= 1 and g is a function whose domain is a
 set of ordered k-tuples and whose range is a set of ordered r-tuples. The
 arity of f is (k,r).

 We write dom(f) for dom(g), and define f(x_1,...,x_k) = g(<x_1,...,x_k>).

 We say that f is a multidimensional function from A into B if and only if f
 is a multidimensional function with dom(f) = A^k and rng(f) containedin
 B^r, where f has arity (k,r).

 We define fA = {f(x_1,...,x_k): k is the arity of f and x_1,...,x_k in A}.

 2. EQUATIONAL, INEQUATIONAL, PROPOSITIONAL, BOOLEAN RELATION THEORY.

 The set variables consist of A_1,A_2,... . The function variables consist
 of f_1,f_2,... .

 The Boolean expressions are inductively defined as follows:

 i) emptyset, U, and each set variable are Boolean expressions;
 ii) if s,t are Boolean expression then (s union t), (s intersection t), and
 s' are Boolean expressions.

 Here s' denotes the complement of s, and U denotes the universal set.

 A Boolean equation is an equation s = t, where s,t are Boolean expressions.

 A Boolean inequation is an inequation s not= t, where s,t are Boolean
 expressions.

 The propositional combinations of Boolean equations are obtained from the
 Boolean equations through use of the usual propositional connectives.

 Let V be a set of multidimensional functions and K be a set of sets. Let
 n,m >= 1.

 Equational (inequational, propositional) BRT on (V,K) of type (n,m) is the
 study of all statements of the form

 for all f_1,...,f_n in V there exists A_1,...,A_m in K such that a given
 Boolean equation (Boolean inequation, propositional combination of Boolean
 equations) holds in the m(n+1) sets

 A_1,...,A_m
 f_1A_1,...,f_1A_m
 ...
 f_nA_1,...,f_nA_m.

 Here we interpret the universal set U to be the union of K, and
 complementation is taken relative to U.

 The case n = m = 1 is the most elemental type, where we have a single
 function and a single set. Here even equational BRT on (V,K) of type (1,1)
 can be highly nontrivial.

 The goal of equational (inequational, propositional) BRT on (V,K) of type
 (n,m) is to determine the truth or falsity of all of its members. For a
 given n,m >= 1, there are 2^2^m(n+1) elements of equational (inequational)
 BRT on (V,K) of type (n,m), up to Boolean equivalence. There are
 2^2^2^2^m(n+1) elements of propositional BRT on (V,K) of type (n,m) up to
 Boolean/logical equivalence.

 Note that equational BRT is quite robust. I.e., any finite conjunction of
 Boolean equations is equivalent to a single Boolean equation (formally, in
 Boolean algebra), and inclusions between Boolean terms are equivalent to
 single Boolean equations (again formally, in Boolean algebra).

 3. EXTENDED EQUATIONAL, INEQUATIONAL, PROPOSITIONAL, BOOLEAN RELATION THEORY.

 The extended Boolean expressions are defined inductively as follows:

 i) emptyset, U, and each set variable are extended Boolean expressions;
 ii) if s,t are extended Boolean expressions then so are (s union t), (s
 intersect t), and s';
 iii) if s is an extended Boolean expression and f is a function variable
 then f(s) is an extended
 Boolean expression.

 An extended Boolean equation is an equation s = t, where s,t are extended
 Boolean expressions.

 An extended Boolean inequation is an inequation s not= t, where s,t are
 extended Boolean expressions.

 The propositional combinations of extended Boolean equations are obtained
 from the extended Boolean equations through use of the usual propositional
 connectives.

 Let V be a set of multidimensional functions and K be a set of sets. Let
 n,m >= 1.

 Extended equational (inequational, propositional) BRT on (V,K) of type
 (n,m) is the study of all statements of the form

 for all f_1,...,f_n in V there exists A_1,...,A_m in K such that a given
 extended Boolean equation (Boolean inequation, propositional combination of
 Boolean equations) holds in the functions f_1,...,f_n and the sets
 A_1,...,A_m.

 Extended equational (inequational, propositional) BRT on (V,K) is the union
 over n,m >= 1 of extended equational (inequational, propositional) BRT of
 type (n,m).

 Note that there are infinitely many statements even in extended equational
 BRT on (V,K) of type (1,1). However, we can introduce a new parameter for
 the number of occurrences of functions (or function variables) in an
 extended Boolean expression. We then have finitely many statements in the
 extended theory of type (n,m).

 4. THE THIN SET THEOREM.

 We use Z for the set of all integers. An integral multivariate function is
 a multivariate function from Z into Z. An integral multidimensional
 function is a multidimensional function from Z into Z. We write MF(Z) for
 the set of all integral multivariate functions. We write MDF(Z) for the set
 of all integral multidimensional functions.

 Boolean relation theory begins with the thin set theorem. It is the most
 basic interesting theorem in inequational Boolean relation theory. In fact,
 it is a statement in inequational Boolean relation theory on (V_1,K_1) of
 type (1,1).

 THIN SET THEOREM. For all f in MF(Z) there exists infinite A containedin Z
 such that fA not= Z.

 THIN SET THEOREM restated. Every integral multivariate function omits a
 value over some infinite set.

 The thin set theorem (TST) can be easily proved from the classical infinite
 Ramsey theorem within RCA_0. In fact, TST for any specific exponent is
 provable in ACA_0.

 We have shown that TST can be proved in ACA but not in ACA_0. See the joint
 paper with Steve Simpson in the Proceedings of the Boulder Conference (an
 AMS Summer Research Conference).

 We also showed that TST for binary functions is not provable in WKL_0. See
 the joint paper of Cholak et al, to appear in the Simpson volume on Reverse
 Mathematics.

 However the status of TST in Reverse Mathematics is unclear at this time.
 One possibility is that TST is provably equivalent to the classical Ramsey
 theorem for all finite exponents over RCA_0 (which is in turn equivalent to
 "for all x,n, the n-th Turing jump of x exists"). Another possibility is
 that TST does not even prove the existence of 0'. One can go further. Maybe
 TST does not even prove that every infinite recursive 0,1-tree has an
 infinite path.

 The same remarks apply if we extend TST to multidimensional functions;
 i.e., to MDF(Z). The same remarks also apply if we use multivariate
 functions where the domains are the strictly increasing k tuples instead of
 all k tuples.

 We have also looked at the weak form using rectangles and strictly
 increasing tuples:

 THEOREM 4.1. Let k >= 1 and f:Z^k< into Z. There exists infinite sets
 A_1,...,A_k containedin Z such that f[A_1 x ... x A_k] not= Z.

 The same remarks apply to this weak form of TST. (Here Z^k< is the set of
 all strictly increasing k-tuples from Z).

 5. THE COMPLEMENTATION THEOREM.

 For x in Z^k, we write |x| for the sup norm of x, which is the maximum of
 the absolute values of the coordinates of x. We say that an integral
 multivariate f is strictly dominating if and only if for all x in dom(f),
 |f(x)| > |x|.

 We write SD(Z) for the set of all strictly dominating integral multivariate
 functions.

 The complementation theorem is the most basic interesting theorem in
 equational Boolean relation theory. It is provable in RCA_0, but is, in a
 sense, complete for bounded recursion.

 COMPLEMENTATION THEOREM. For all f in SD(Z) there exists infinite A
 containedin Z such that fA = Z\A. For all f in SD(Z) there exists a unique
 A containedin Z such that fA = Z\A.

 The structure of this unique fixpoint A is rather complex even for strictly
 dominating affine transformations from Z into Z (even one-dimensional!).
 One can also work entirely within N. Here N is the set of all nonnegative
 integers.

 We can extend the complementation theorem to multidimensional functions. A
 multidimensional function is strictly dominating if and only if each of its
 coordinate functions is strictly dominating.

 We write SD*(Z) for the set of all strictly dominating integral
 multidimensional functions.

 COMPLEMENTATION THEOREM. For all f in SD*(Z) there exists infinite A
 containedin Z such that fA = Z\A. For all f in SD(Z) there exists a unique
 A containedin Z such that fA = Z\A.

 6. BABY BOOLEAN RELATION THEORY.

 By baby BRT I generally mean equational and inequational BRT on (V,K) of
 type (1,1) for some basic V,K. We refer to this as unary equational and
 inequational BRT on (V,K). In each case, there are only 16 statements
 involved.

 INF(Z) is the set of all infinite subsets of Z. BINF(Z) is the set of all
 bi-infinite subsets of Z; i.e., where there are infinitely many positive
 and infinitely many negative elements.

 ASD(Z) is the set of all asymptotically strictly dominating elements of
 MF(Z). Here we demand that the inequality hold only for sufficiently large
 |x|.

 ET(Z) is the set of all expansively trapped elements of MF(Z). This class
 turns out to play an important role in the theory. The condition is that
 there are constants p,q > 1 such that p|x| < |f(x)| < q|x| for all x in
 dom(f).

 AET(Z) is the set of all asymptotically expansively trapped elements of
 MF(Z). Here we demand that the inequality hold only for sufficiently large
 |x|.

 We have completely classified unary equational and inequational BRT on the
 ten pairs (V,K), where V = MF(Z),SD(Z),ASD(Z),ET(Z),AET(Z), and K =
 INF(Z),BINF(Z).

 The only interesting statements that appear are

 a) the thin set theorem together with a straightforward refinement;
 b) the complementation theorem.

 The refinement of TST has the stronger conclusion: fA union A not= Z.

 7. EXTENSIONS OF THE COMPLEMENTATION THEOREM.

 We consider some natural extensions of the complementation theorem
 involving bi-infinite sets. These extensions lie squarely within equational
 Boolean relation theory.

 We say that A is covered by B,C if and only if A containedin B union C. We
 say that A is disjointly covered by B,C if and only if A is covered by B,C,
 and B,C are disjoint.

 It is convenient to write A is disjointly covered by B,C by

 A/B,C.

 We can restate the complementation theorem as follows.

 THEOREM 7.1. For all f in SD(Z) there exists infinite A containedin Z such
 that Z/A,fA. There is a unique A containedin Z such that Z/A,fA.

 We now strive for a bi-infinite disjoint cover theorem.

 PROPOSITION 7.2. For all f in SD(Z) there exists bi-infinite A containedin
 Z such that Z/A,fA.

 Unfortunately this is refutable in RCA_0. Here is a fix.

 PROPOSITION 7.3. For all f,g in SD(Z) there exists bi-infinite A
 containedin Z such that fA/A,gA.

 Note that here we have replaced f by g and we do not insist that Z/A,gA,
 but only that fA/A,gA. Unfortunately this, also, is refutable in RCA_0.

 To fix this, we consider two sets A,B.

 THEOREM 7.4. For all f,g in SD(Z) there exist bi-infinite A,B containedin Z
 such that fA/B,gB.

 This is fine. It is provable in RCA_0. We now move to three sets.

 THEOREM 7.5. For all f,g in SD(Z) there exist bi-infinite A,B,C containedin
 Z such that fA/B,gB and fB/C,gC.

 This is also provable in RCA_0. We can also prove the following variant in
 RCA_0.

 THEOREM 7.6. For all f,g in SD(Z) there exist bi-infinite A,B,C containedin
 Z such that fA/B,gC and fB/C,gC.

 We now consider another variant.

 PROPOSITION 7.7. For all f,g in SD(Z) there exist bi-infinite A,B,C
 containedin Z such that fA/C,gB and fB/C,gC.

 We also consider the following sharper statement which immediately implies
 7.4 - 7.7.

 PROPOSITION 7.8. For all f,g in SD(Z) there exist bi-infinite A_1,A_2,A_3
 containedin Z such that for all 1 <= i < j,k <= 3, fA_i/ A_j,gA_k.

 Some profound difficulties emerge here. It turns out that Proposition 7.7
 already is refutable in RCA_0.

 We can fix this by using ET(Z).

 PROPOSITION 7.9. For all f,g in ET(Z) there exist bi-infinite A,B,C
 containedin Z such that fA/C,gB and fB/C,gC.

 PROPOSITION 7.10. For all f,g in ET(Z) there exist bi-infinite A_1,A_2,A_3
 containedin Z such that for all 1 <= i < j,k <= 3, fA_i/A_j,gA_k.

 These Propositions can be proved, but only with small large cardinals. Let
 MAH = ZFC + {there exists an n-Mahlo cardinal}_n.

 THEOREM 7.11. Propositions 7.9 and 7.10 are provably equivalent, in ACA, to
 the 1-consistency of MAH.

 We can extend to any finite number of bi-infinite sets.

 PROPOSITION 7.12. For all r >= 1 and f,g in ET(Z) there exist bi-infinite
 A_1,...,A_r containedin Z such that for all 1 <= i < j.k <= r,
 fA_i/A_j,gA_k.

 In fact, we can consider the following substantially sharper statement.

 PROPOSITION 7.13. For all r >= 1 and f,g in ET(Z) there exists bi-infinite
 A_1 containedin ... containedin A_k containedin Z such that for all 1 <=
 i < j,k <= r, fA_i/A_j,gA_k and A_1,fA_r are disjoint.

 Once we bring in towers under inclusion, we can revisit Theorem 7.5:

 PROPOSITION 7.14. For all f,g in ET(Z) there exist bi-infinite A
 containedin B containedin C containedin Z such that fA/B,gB and fB/C,gC.

 THEOREM 7.15.  Propositions 7.12 - 7.14 are provably equivalent, in ACA, to
 the 1-consistency of MAH.

 All of the results here hold if we use asymptotically expansively trapped
 integral multivariate functions. These are the integral multivariate
 functions for which there exist constants p,q > 1 such that

 p|x| < |f(x)| < q|x|

 holds for all sufficiently large |x|.

 The same results hold if we use ASD(Z) in Theorems 7.4 - 7.6, and AET(Z) in
 Propositions 7.9,7.10,7.12 - 7.14..

 8. EQUATIONAL BOOLEAN RELATION THEORY OF TYPE (2,3)..

 Note that Propositions 7.9,7.10,7.12 - 7.14 are statements in equational
 BRT on (ET(Z),BINF(Z)) of type (2,3).

 We conjecture that we can "classify" equational BRT on (ET(Z),BINF(Z)) of
 type (2,3). Let MAH be ZFC + "for all n there exists an n-Mahlo cardinal".

 CONJECTURE 8.1. Every instance of equational BRT on (ET(Z),BINF(Z)) of type
 (2,3) is provable or refutable in MAH+.

 By Theorem 7.11, we see that this conjecture is false with MAH+ replaced by
 MAH, assuming MAH is consistent. We encapsulate this conjecture by saying
 that it is necessary and sufficient to use Mahlo cardinals of finite order
 in order to classify equational BRT on (ET(Z),BINF(Z)) of type (2,3).

 We now consider INF(Z). It is easy to see that Propositions
 7.9,7.10,7.12,7.14 are provable in RCA_0 with BINF(Z) replaced by INF(Z).
 This is not the case with Proposition 7.13. In fact, consider the following.

 PROPOSITION 8.2. For all f,g in ET(Z) there exist infinite A,B,C
 containedin Z such that fA/C,gB, fB/C,gC, and A,fC are disjoint.

 THEOREM 8.3. Propositions 7.13 and 8.2 are provably equivalent to
 1-Con(MAH) over ACA.

 CONJECTURE 8.4. Every instance of equational BRT on (ET(Z),INF(Z)) of type
 (2,3) is provable or refutable in MAH+.

 By the above we see that this conjecture is false with MAH+ replaced by
 MAH, assuming MAH is consistent. We encapsulate this conjecture by saying
 that it is necessary and sufficient to use Mahlo cardinals of finite order
 in order to classify equational BRT on (ET(Z),INF(Z)) of type (2,3).

 We also make a conjecture about type (2,2).

 CONJECTURE 8.5. Every statement of equational BRT on (ET(Z),BINF(Z)) of
 type (2,2) is provable or refutable in ACA. Every statement of equational
 BRT on (ET(Z),INF(Z)) of type (2,2) is provable or refutable in ACA.

 The same results hold and conjectures made using AET(Z) in place of ET(Z).

 9. DISJOINT COVER THEORY.

 Boolean relation theory is very difficult (for us) to handle, even of type
 (2,2), and even more so of type (2,3).

 Note that Proposition 7.9 involves only two disjoint cover conditions. Thus
 we define disjoint cover theory, a simplification of Boolean relation
 theory, as follows.

 Disjoint cover theory (DCT) on (V,K) of type (n,m) is the study of all
 statements of the form

 for all f_1,...,f_n in V there exists A_1,...,A_m in K such that  a given set
 of disjoint cover conditions holds among the m(n+1) sets

 A_1,...,A_m
 f_1A_1,...,f_1A_m
 ...
 f_nA_1,...,f_nA_m.

 We have been able to classify DCT on (ELG(Z),BINF(Z)) of type (2,2).

 THEOREM 9.1. Every statement of DCT on (ELG(Z),BINF(Z)) of type (2,2) is
 either provable or refutable in RCA_0.

 We have not been able to classify DCT on (ELG(Z),BINF(Z)) of type (2,3). We
 do have the following partial result.

 Before we discovered Propositions 7.9,7.10,7.12, our simplest independence
 result involved towers under inclusion, and was Proposiiton 7.14
 (originally stated just for AET(Z)).

 At that time, we formulated DCT to include the condition A_1 containedin
 ... containedin A_m containedin Z. Let us call this DCT with inclusion. We
 then obtained the following result by a lengthy exhaustive analysis.

 THEOREM 9.2. Every statement of DCT with inclusion on (AET(Z),BINF(Z)) of
 type (2,3) with at most two disjoint cover conditions is either provable or
 refutable in RCA_0 or provably equivalent, over ACA, to the 1-consistency
 of MAH.

 With the discovery of Propositions 7.9,7.10.7.12, it is imperative to
 obtain an analogous classification result for DCT of type (2,3) with at
 most two disjoint cover conditions. We fully expect to be able to carry
 this out.

 10. FINITENESS.

 There is a striking fact that we have observed in all of our
 classifications to date. Let NFIN(Z) be the set of all nonempty finite
 subsets of Z.

 In our classifications, any statement classified as true on (V,NFIN(Z)) is
 classified as true on (V,BINF(Z)). We call this finiteness. We conjecture
 that finiteness also holds for the various conjectured classifications.

 In the particular case of the classification in Theorem 9.2, finiteness is
 provably equivalent, over ACA, to the 1-consistency of MAH.

 11. INTEGRAL PIECEWISE POLYNOMIALS.

 An integral polynomial is a multivariate polynomial from Z into Z.

 An integral piecewise polynomial is an integral multivariate function which
 is defined by possibly different integral polynomials in each of finitely
 many cases, where each case is given by a finite set of integral polynomial
 inequalities.

 An integral multivariate function f is expansive if and only if for some
 constant p > 1, |f(x)| > p|x| holds for all x in dom(f). An integral
 multivariate function f is asymptotically expansive if and only if for some
 constant p > 1, |f(x)| > p|x| holds for all sufficiently large |x|.

 We write EPP(Z) for the set of all expansive integral piecewise
 polynomials, and AEPP(Z) for the set of all asymptotically expansive
 integral piecewise polynomials. We also use ETPP(Z) for the set of all
 expansively trapped integral piecewise polynomials, and AETPP(Z) for the
 set of all asymptotically expansively trapped integral piecewise
 polynomials.

 THEOREM 11.1. The status of Propositions 7.9,7.10,7.12 - 7.14 remain the
 same when stated for EPP(Z), AEPP(Z), ETPP(Z), and AETPP(Z).

 In fact, when Propositions 7.9,7.10,7.12 - 7.14 are stated for EPP(Z),
 AEPP(Z),ETPP(Z),AETPP(Z), we can require that the nine sets
 A,B,C,fA,fB,fC,gA,gB,gC be exponential Presburger. By exponential
 Presburger, we mean definable in the structure (Z,<,+,-,2^|x|), which is
 well known to have quantifier elimination. This results in a Pi-0-2
 sentence which is provably equivalent, over ACA, to the 1-consistency of
 MAH.

 We can be more explicit about the form of A,B,C. We can take A,B,C to be
 images of integral piecewise polynomials on the set of double factorials,
 or alternatively, on the set of triple exponentials to base 2.

 12. INTEGRAL POLYNOMIALS ON UPPER HALFSPACE.

 For all k >= 1, we define the upper halfspace of Z^k as the set of all
 points whose final coordinate is nonnegative.

 We let POLY*(Z,k) be the set of all integral polynomials P from the upper
 halfspace of Z^k into Z^k such that each coordinate function of P is
 expansive on its domain. Let POLY*(Z) be the union over k, of POLY*(Z,k).

 THEOREM 12.1. The status of Propositions 7.9,7.10,7.12 - 7.14 remain the
 same when stated for POLY*(Z).

 In fact, when Propositions 7.9,7.10,7.12 - 7.14 are stated for POLY*(Z), we
 can require that the nine sets A,B,C,fA,fB,fC,gA,gB,gC are exponential
 Presburger. Using quantifier elimination for exponential Presburger, this
 results in a Pi-0-2  sentence which is provably equivalent, over ACA, to
 the 1-consistency of MAH.

 13. FINITE SETS.

 PROPOSITION 13.1. Let f,g in EPP(Z) and E be a finite subset of N\{0,1}
 where the logarithms of successive elements have sufficiently large ratios.
 There exist finite A,B,C containedin Z containing E such that fA/C,gB and
 fB/C,gC.

 PROPOSITION 13.2. Let f,g in EPP(Z) and E be a finite subset of N\{0,1}
 where the logarithms of successive elements have sufficiently large ratios.
 There exist finite sets E containedin A_1,A_2,A_3 containedin Z such that
 for all 1 <= i < j,k <= 3, fA_i/A_j,gA_k.

 PROPOSITION 13.3. Let r >= 1, f,g in EPP(Z), and E be a finite subset of
 N\{0,1} where the logarithms of successive elements have sufficiently large
 ratios. There exist finite sets E containedin A_1 containedin ...
 containedin A_r containedin Z such that for all 1 <= i < j,k <= r,
 fA_i/A_j,gA_k.

 THEOREM 13.4. Propositions 13.1 - 13.3 are provably equivalent, in ACA, to
 1-Con(MAH). The same holds for AEPP(Z),ETPP(Z),AETPP(Z),POLY*(Z).

 Propositions 13.1 - 13.3 are naturally in Pi-0-3 form.

 14. REAL PIECEWISE POLYNOMIALS.

 A real polynomial is a multivariate polynomial from R into R.

 A real piecewise polynomial is a real multivariate function which is
 defined by possibly different real polynomials in each of finitely many
 cases, where each case is given by a finite set of real polynomial
 inequalities.

 We write EPP(R) for the set of all expansive real piecewise polynomials. We
 write EPP(R,Z) for the set of all expansive real piecewise polynomials with
 integer coefficients, where the polynomial inequalities also involve only
 integer coefficients.

 We let POLY*(R,Z,k) be the set of all real polynomials P from the upper
 halfspace of R^k into R^k, with integer coefficients, such that each
 coordinate function of P is expansive on its domain. Let POLY*(R,Z) be the
 union over k, of POLY*(R,Z,k).

 PROPOSITION 14.1. Let f,g in EPP(R,Z) and E be a finite subset of N\{0,1}
 where the logarithms of successive elements have sufficiently large ratios.
 There exist finite sets E containedin A,B,C containedin R such that fA/C,gB
 and fB/C,gC.

 PROPOSITION 14.2. Let f,g in EPP(R,Z) and E be a finite subset of N\{0,1}
 where the logarithms of successive elements have sufficiently large ratios.
 There exist finite sets E containedin A_1,A_2,A_3 containedin R such that
 for all 1 <= i < j,k <= 3, fA_i/A_j,gA_k.

 PROPOSITION 14.3. Let r >= 1, f,g in EPP(R,Z), and E be a finite subset of
 N\{0,1} where the logarithms of successive elements have sufficiently large
 ratios. There exist finite sets E containedin A_1 containedin ...
 containedin A_r containedin R such that for all 1 <= i < j,k <= r,
 fA_i/A_j,gA_k.

 THEOREM 14.4. Propositions 14.1 - 14.3 are provably equivalent, in ACA, to
 Con(MAH). The same holds for AEPP(R,Z),ETPP(R,Z),AETPP(R,Z),POLY*(R,Z).

 In each case we can use the elimination of quantifiers for the real field
 and double exponential bounds on how large the ratios of the logarithms
 need to be, together with bounds on the sizes of A,B,C, in order to put
 these Propositions in Pi-0-1 form. We can of course quantify over algebraic
 real numbers with a bound on their presentations to make everything
 explicitly Pi-0-1.

 Instead of quantifying over algebraic real numbers, we can instead quantify
 over rationals, and use the notion of approximate disjoint cover. Write
 A/_epsilon B,C to mean that B,C are disjoint and every element of A is
 within epilson of some element of B union C. We can modify these
 Propositions to state that for each epsilon > 0, there exist finite sets of
 rationals containing E such that the disjoint cover conditions hold with
 /_epsilon. We can bound everything involved double exponentially, and get
 explicitly Pi-0-1 sentences equivalent to Con(MAH) this way.

 15. INTEGRAL PIECEWISE LINEAR FUNCTIONS.

 An integral piecewise linear function is an integral multivariate function
 which is defined by possibly different integral affine functions in each of
 finitely many cases, where each case is given by a finite set of integral
 linear inequalities.

 We write EPL(Z) for the set of all expansive integral piecewise linear
 functions, and AEPL(Z) for the set of all asymptotically expansive integral
 piecewise linear functions. We also use ETPL(Z) for the set of all
 expansively trapped integral piecewise linear functions, and AETPL(Z) for
 the set of all asymptotically expansively trapped integral piecewise linear
 functions.

 THEOREM 15.1. The status of Propositions 7.9,7.10,7.12 - 7.14, remain the
 same when stated for EPL(Z), AEPL(Z), ETPL(Z), and AETPL(Z), except that we
 get equivalence with Con(MAH).

 We can take A,B,C to be images of integral piecewise linear functions on
 infinite geometric progressions, or on just the powers of 2. The
 representation can be bounded double exponentially in the data.

 PROPOSITION 15.2. Let f,g in EPL(Z) and E be a finite subset of N\{0} where
 the ratios of successive elements are sufficiently large. There exist
 finite sets E containedin A,B,C containedin Z such that fA/C,gB and fB/C,gC.

 PROPOSITION 15.3. Let f,g in EPL(Z) and E be a finite subset of N\{0} where
 the ratios of successive elements are sufficiently large. There exist
 finite sets E containedin A_1,A_2,A_3 containedin Z such that for all 1 <= i <
 j,k <= 3, fA_i/A_j,gA_k.

 PROPOSITION 15.4. Let r >= 1, f,g in EPL(Z), and E be a finite subset of
 N\{0} where the ratios of successive elements are sufficiently large. There
 exist finite sets E containedin A_1 containedin ... containedin A_r
 containedin Z such that for all 1 <= i < j,k <= r, fA_i/A_j,gA_k.

 THEOREM 15.5. Propositions 15.2 - 15.4 are provably equivalent, in ACA, to
 Con(MAH). The same holds for AEPL(Z),ETPL(Z),AETPL(Z). We can give a double
 exponential bound on "sufficiently large".

 16. INTEGRAL AFFINE FUNCTIONS.

 We let LIN*(Z,k) be the set of all integral affine functions T from a
 finite intersection of integral halfplanes in Z^k into Z^k such that each
 coordinate function of T is expansive on its domain. Let LIN*(Z) be the
 union over k, of LIN*(Z,k).

 The results of section 15 also hold for LIN*(Z).

 17. BOUNDED ARITY.

 All independent statements thus far considered use multivariate functions
 without bounding the arity.

 In each case other than those involving piecewise polynomials, polynomials,
 piecewise linear functions, and affine functions, the arity can be fixed to
 be a small number - perhaps even 2 - and one obtains the same results. Here
 one takes advantage of the constant(s) in the definition of expansive or
 expansively trapped. In the other cases, the arity can also be fixed, but
 it is not clear how small the fixed number can be.

 18. FORMAL PARTITION THEORY.

 We say that A is partitioned by B,C if and only if A is covered by B,C and
 A intersect B intersect C = emptyset. This is weaker than A is disjointly
 covered by B,C. Nevertheless, we can replace "disjointly covered" by
 "partitioned" in the independent statements that include the inclusions A
 containedin B containedin C or  A_1 containedin A_2 containedin A_3 or  A_1
 containedin ... containedin A_r, and get the same results. We have not
 redone the classification results using partitions. We expect that they
 will go through and have the same properties.

 If we use "partitioned" instead of "disjoint covered" then the general
 theory is called "formal partition theory" instead of "disjoint cover
 theory".

 19. SOME ILLUSTRATIVE EXAMPLES.

 To give some indication of the scope of Boolean relation theory, we give
 these examples.

 a. For all f in V there exists A in K such that fA containedin A.

 b. For all f In V there exists A in K such that fA not= U.

 In b, U is the universal set, which is always taken to be the union of the
 elements of K.

 In a, if we take V to be the set of all bounded linear operators on Hilbert
 space and K to be the set of all nontrivial closed subspaces of Hilbert
 space, then we have a restatement of the invariant subspace problem for
 Hilbert space.

 In b, if we take V to be the multivariate functions from omega_1 into
 omega_1, and K to be the set of all subsets of omega_1 of cardinality
 omega_1, then we have a restatement of the negation of a theorem of
 Todorcevic (even for just binary functions).

 In b, if we take V to be the continuous functions from R into R and K to be
 the set of all dense open subsets of R, then we get a true theorem in
 elementary real analysis.

 In b, if we take V to be the binary continuous functions from R into R and
 K to be the set of all dense open subsets of R, then we get a false theorem
 in elementary real analysis.

 It is natural to use the set of all continuous functions from a topological
 space into itself, or the multivariate continuous functions from a
 topological space into itself, and K to be the open sets, or some variety
 of open sets. E.g., the nonempty open sets, the dense open sets, the open
 sets of the same cardinality as the space, the open sets that can be
 continuously mapped onto the space, etcetera. We call this topological
 Boolean relation theory.

 The thin set theorem and the examples discussed above for b are obviously
 in topological Boolean relation theory, using, respectively, the discrete
 topology on Z, the discrete topology on omega_1, and the usual topology on
 R.

 One can consider algebraic Boolean relation theory. Here one takes V to be
 the polynomials over a ring, or some variety of polynomials over a ring, in
 genearal of several variables. Or take V to be the rational functions over
 a field, or some variety of rational functions over a field (the
 singularities cause no problems in the definition of forward image), in
 general of several variables. Or one might have an ordered ring or ordered
 field, and use the order to define natural varieties of polynomials or
 rational functions, in general of several variables. The sets in K could be
 taken to be the zero sets, or infinite sets, or sets having some property
 involving the order, etcetera.

 One can also consider geometric Boolean relation theory, where smoothness
 conditions are placed on the functions, in general of several variables. Or
 analytic Boolean relation theory where analyticity conditions are placed on
 the functions, in general of several variables.

 Or linear Boolean relation theory, where V is the set of all linear or
 affine functions on a vector space, or a topological vector space, subject
 to boundedness or continuity conditions, in general of several variables.

 For the purest, there is finite combinatorial Boolean relation theory,
 where, in its purest form, one takes V to be the set of all (multivariate)
 functions from a finite set into itself, and takes K to be the set of all
 subsets of the finite set. It is natural to also consider cardinality
 conditions on the elements of K.

 ******************************

 This is the 100th 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
 96:Comments on BRT  12/20/00  9:20AM
 97.Classification of Set Theories  12/22/00  7:55AM
 98:Model Theoretic Interpretation of Large Cardinals  3/5/01  3:08PM
 99:Boolean Relation Theory IV  3/8/01  6:08PM






More information about the FOM mailing list