[FOM] 191:Boolean Roots

[Harvey Friedman]

First a clarification concerning #190.

In connection with the interpretation of diagrams consisting of rectangles,
I said the following.

"It is understood that the
rectangles are open rectangles, so that adjacent rectangles are disjoint."

This is not a good way to interpret such diagrams as the one displayed in
#190.

Instead, one should treat the rectangles as closed sets, and define the
inclusion relation between finite intersections and finite unions as:

the finite intersection is included in the finite union except for a finite
union of line segments and points.

Disjointness of course should be interpreted as

the finite intersection is a finite union of line segments and points.

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

Boolean Roots is a particularly convenient way of expressing a certain form
of BRT. 

Let N be the set of all nonnegative integers. Let f:N^k into N, k >= 1. Let
B be a subset of N.

A Boolean f-root of B is a subset A of B such that

A+A containedin B Delta fB.

Here Delta is symmetric difference, and fB is my usual {f(x1,...,xk):
x1,...,xk in B}. 

THEOREM 1. Let f:N^k into N be strictly dominating (i.e., every f(x1,...,xk)
> x1,...,xk). Then some infinite set of integers is a Boolean f-root of
itself.

THEOREM 2. Let f:N^k into N be strictly dominating (i.e., every f(x1,...,xk)
> x1,...,xk). Then some infinite set of odd integers is a Boolean f-root of
a Boolean f-root of a set.

THEOREM 3. Let f:N^k into N be piecewise linear with integer coefficients,
and r,p be sufficiently large. Then {1,r,r^2,...,r^p} is a Boolean f-root of
a Boolean f-root of some subset of {1,...,r^p+1}.

Theorem 1 is provable in a weak fragment of ZFC such as RCA0.

Theorem 2 is provably equivalent to the 1-consistency of Mahlo cardinals of
finite order. Theorem 2 is equivalent to the consistency of Mahlo cardinals
of finite order. Triple exponential bounds will work in Theorem 3.

We can also obtain the analogous results for Boolean f-roots of Boolean
f-roots of Boolean f-roots ... of Boolean f-roots, with finite iteration.

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

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
190:Diagrammatic BRT 10/6/03  8:36PM

Harvey Friedman