FOM: 124:Disjoint Unions

[Harvey Friedman]

Here is my currently favorite Boolean Relation Theory statement, which has
a special elegance due to the use of the standard disjoint union notation.

We write

A U. B

for the disjoint union of A and B. This is just the union of A and B, but
the appearance of this implies that A,B are disjoint.

Thus the meaning of an expression involving one or more occurrences of U.
is the same as its meaning with U instead of U., together with the
assertion that for all appearences of s U. t , we have s,t disjoint.

This is entirely standard notation.

We can take splendid advantage of this notation for the purposes of Boolean
Relation Theory.

Why does this help so much? The answer is that this notation was invented
by mathematicians in order to more elegantly express a number of
mathematical statements. We are following the same process.

PROPOSITION 1. For all multivariate f,g from N into N of quadratic
growth, there exist infinite sets A,B,C containedin N obeying

A U. fA containedin C U. gB
A U. fB containedin C U. gC.

Here are some more general forms.

PROPOSITION 2. For all m >= 1 and multivariate f,g from N into N of quadratic
growth, there exist infinite sets A1,...,Am containedin N obeying the m-1
inclusions

A1 U. fAi containedin Am U. gAi+1.

PROPOSITION 3. For all n,m >= 1 and multivariate f1,...,fn from N into N of
quadratic
growth, there exist infinite sets A1,...,Am containedin N obeying the
n(m-1) inclusions

A1 U. fiAj containedin Am U. fnAj+1.

THEOREM 4. Propositions 1-3 are ach provably equivalent to the
1-consistency of ZFC + {there exists an n-Mahlo cardinal}n over ACA.

Note that Propoisiton 1 is clearly part of the original Boolean relation
theory (for two functions and three sets). It does not need a tower
A1 containedin A2 containedin A3, and it does not need a notion of
largeness. Further, we are
considering only inclusions of the form

X U. gY containedin V U. hW

which has nice symmetry.

As usual we can use other notions of growth such as expansive linear
growth, or expansive linearly trapped.

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

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.

This is the 123rd 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