FOM: 99:Boolean Relation Theory IV
Harvey Friedman
friedman at math.ohio-state.edu
Thu Mar 8 18:08:10 EST 2001
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
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.
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/G,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 f,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 A,B,C containedin Z containing E 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 A_1,A_2,A_3 containedin Z containing E 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 99th 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
More information about the FOM
mailing list