[FOM] 190:Diagrammatic BRT

Mon Oct 6 20:36:25 EDT 2003

WARNING: There is a diagram below which must be viewed in a *fixed width
font*. Most mail programs allow for changing the viewing font.

#################################

Instead of writing down Boolean relations between A,B,C,fA,fB,fC,gA,gB,gC,
as in BRT = Boolean relation theory, we can convey the relevant information
in diagrams. One of the several BRT statements in BRT involving
A,B,C,fA,fB,fC,gA,gB,gC lends itself particularly well to a digrammatic
representation.

This particular BRT statement involves a Boolean equation involving only

A,B,C,fA,fB,gB,gC

which of course makes the diagram simpler.

[Recall from BRT that f,g are functions whose domain is a finite dimensional
Cartesian power of N and whose range is a subset of N. Here N is the set of
all nonnegative integers. Also, for subsets E of N, fE is a convenient
notation for the set of all values of f at arguments drawn from E].

There is a particular diagrammatic representation of a Boolean equation
between any sets A1,...,Ak that is useful here.

Specifically, k regions of the plane are given, E1,...,Ek. Consider all
conditions of the forms

E_i_1 intersection ... intersection E_i_n = emptyset.

E_i_1 intersection ... intersection E_i_n containedin E_j_1 union ... union
E_j_m.

Here n,m >= 1, and no i is equaled to any j.

We have excluded the case where the left side is the universal set (n = 0)
- this case will not interest us.

What the diagram "says" is that every one of these conditions that is true
of the E's is also true of the A's.

The idea is that if the regions E1,...,Ek can be chosen to be simple enough,
then all conditions of the above form on the E's will be "visually evident",
without any algebraic notation. Hence the BRT statement itself - i.e., the
Boolean relation on the A1,...,Ak - will has a "visually evident" meaning.

Note that such diagram of E's may contain information of a different
character - i.e., proper inclusions - that are not intended to be imposed on
the A's. Such information may well be true in the particular context about
the A's under consideration, but the information is not given by the diagram
itself, in the sense of this posting.

Of course, such stronger interpretations of diagrams of E's is also very
useful and interesting. But it is not being considered here in connection
with equational BRT, at least not at present.

Here is the diagram that we use. It is made up of rectangles, whose sides
are parallel to the axes, and are labeled A,B,C,fA,fB,gB,gC. The labeling of
rectangles is by labeling the four corners. It is understood that the
rectangles are open rectangles, so that adjacent rectangles are disjoint.

Various visual schemes, including color and shading, can undoubtedly enhance
the "geometric" information.

For instance, each of the seven labels could appear with a different color.
Thus we might have four blacks, four blues, four reds, four greens, four
browns, four purples, four oranges.

Also, an interactive computer system supporting various modes of viewing
would be helpful. E.g., click on a label, and the rectangle with that label
is filled in. 

_____________________________________________
|C     |fB          C|gC           fB|     gC|
|      |             |               |       |
|      |             |               |       |
|_____ |_____________|_______________|_______|
|B     |      |fA   B|gB   fA|       |     gB|
|      |      |      |       |       |       |
|      |      |      |       |       |       |
|_____ |fB____|fA____|gBgC_fA|_____fB|___gBgC|
|A                  A|
|                    |
|                    |
|ABC______________ABC|

Note that this diagram "asserts" that

1. A containedin B containedin C.
2. fA containedin fB.
3. gB containedin gC.
4. C,gC are disjoint.
5. A,fB are disjoint.
6. fA containedin B union gB.
7. fB containedin C union gC.

The main BRT statement is a little different, and algebraically simpler:

PROPOSITION 1. For all f,g of expansive linear growth, there exist infinite
A,B,C containedin N such that
i) A disjoint union fA containedin C disjoint union fB;
ii) A disjoint union fB containedin C disjoint union fC.

The relevant BRT results here are the following.

PROPOSITION 2. For all f,g of expansive linear growth, there exist infinite
A,B,C containedin N such that
i) A disjoint union fA containedin B disjoint union fB;
ii) A disjoint union fB containedin C disjoint union fC.

PROPOSITION 3. For all f,g of expansive linear growth, there exist infinite
A containedin B containedin C containedin N such that
i) A disjoint union fA containedin B disjoint union fB;
ii) A disjoint union fB containedin C disjoint union fC.

Proposition 1 requires large cardinals.

Proposition 2 does not require large cardinals. (Provable in RCA0).

Proposition 3 requires large cardinals.

Proposition 3 is stated as follows, using the diagram:

PROPOSITION 3'. For all f,g of expansive linear growth, the above diagram
can be realized with infinite A,B,C containedin N.

This opens up the expectation of a classification of the
truth/falsity/strength of equational BRT statements that are given by simple
diagrams of this kind.

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

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 188th in a series of self contained numbered postings to
FOM covering a wide range of topics in f.o.m. The list of previous
numbered postings #1-149 can be found at
http://www.cs.nyu.edu/pipermail/fom/2003-May/006563.html  in the FOM
archives, 5/8/03 8:46AM. Previous ones counting from #150 are:

150:Finite obstruction/statistics  8:55AM  6/1/02
151:Finite forms by bounding  4:35AM  6/5/02
152:sin  10:35PM  6/8/02
153:Large cardinals as general algebra  1:21PM  6/17/02
154:Orderings on theories  5:28AM  6/25/02
155:A way out  8/13/02  6:56PM
156:Societies  8/13/02  6:56PM
157:Finite Societies  8/13/02  6:56PM
158:Sentential Reflection  3/31/03  12:17AM
159.Elemental Sentential Reflection  3/31/03  12:17AM
160.Similar Subclasses  3/31/03  12:17AM
161:Restrictions and Extensions  3/31/03  12:18AM
162:Two Quantifier Blocks  3/31/03  12:28PM
163:Ouch!  4/20/03  3:08AM
164:Foundations with (almost) no axioms, 4/22/0  5:31PM
165:Incompleteness Reformulated  4/29/03  1:42PM
166:Clean Godel Incompleteness  5/6/03  11:06AM
167:Incompleteness Reformulated/More  5/6/03  11:57AM
168:Incompleteness Reformulated/Again 5/8/03  12:30PM
169:New PA Independence  5:11PM  8:35PM
170:New Borel Independence  5/18/03  11:53PM
171:Coordinate Free Borel Statements  5/22/03  2:27PM
172:Ordered Fields/Countable DST/PD/Large Cardinals  5/34/03  1:55AM
173:Borel/DST/PD  5/25/03  2:11AM
174:Directly Honest Second Incompleteness  6/3/03  1:39PM
175:Maximal Principle/Hilbert's Program  6/8/03  11:59PM
176:Count Arithmetic  6/10/03  8:54AM
177:Strict Reverse Mathematics 1  6/10/03  8:27PM
178:Diophantine Shift Sequences  6/14/03  6:34PM
179:Polynomial Shift Sequences/Correction  6/15/03  2:24PM
180:Provable Functions of PA  6/16/03  12:42AM
181:Strict Reverse Mathematics 2:06/19/03  2:06AM
182:Ideas in Proof Checking 1  6/21/03 10:50PM
183:Ideas in Proof Checking 2  6/22/03  5:48PM
184:Ideas in Proof Checking 3  6/23/03  5:58PM
185:Ideas in Proof Checking 4  6/25/03  3:25AM
186:Grand Unification 1  7/2/03  10:39AM
187:Grand Unification 2 - saving human lives 7/2/03 10:39AM
188:Applications of Hilbert's 10-th 7/6/03  4:43AM
189:Some Model theoretic Pi-0-1 statements  9/25/03  11:04AM

Harvey Friedman