[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
#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
More information about the FOM
mailing list