[FOM] 191:Boolean Roots

Harvey Friedman friedman at math.ohio-state.edu
Tue Oct 7 11:03:05 EDT 2003

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

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

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

More information about the FOM mailing list