[FOM] 192:Order Invariant Statement

[Harvey Friedman]

ORDER INVARIANT STATEMENT
October 25, 2003
Harvey M. Friedman

Let N be the set of all nonnegative integers. We say that R containedin N^2k
is strictly dominating if and only if for all x,y in Nk, R(x,y) implies
max(x) < max(y).

We write R[A] for {y in Nk: therexists x in A such that R(x,y)}.

We write A U. B for A U B provided A,B are disjoint; undefined otherwise.

The following is yet another variant of what I have called the
complementation theorem. I prefer the new name.

UNIQUE PARTITION THEOREM. Let k >= 1 and R containedin N^2k be strictly
dominating. There exists A containedin Nk such that A,R[A] partitions Nk.
I.e., A U. R[A] = Nk. Furthermore, A is unique.

FINITE UNIQUE PARTITION THEOREM. Let k,p >= 1 and R containedin [0,p]k be
strictly dominating. There exists A containedin [0,p]k such that A,R[A]
partitions [0,p]k. I.e., A U. R[A] = [0,p]k. Furthermore, A is unique.

Since A is unique, we have no control over A. If we want even modest control
over A, we need to weaken the equation A U. R[A] = [0,p]k.

We now give such a Proposition, which exerts a little bit of control over A,
at the cost of weakening the equation. We will simply say that a particular
number is missing from the coordinates of all elements of A. The equation is
replaced by an assertion that

A U. R[A] is large.

To accomplish this in an explicit fashion, we bring in the well known notion
of order invariance.

We say that x,y in Nk have the same order type if and only if for all i,j in
[1,k], xi < xj if and only if yi < yj.

We say that R containedin [1,t]k is order invariant if and only if for all
x,y in [1,t]k, if x,y have the same order type then x in R if and only if y
in R. 

The order invariant images of A are the images R[A], where for some d, R
containedin Nd+k is order invariant.

PROPOSITION 1. Let k,p >= 1 and R containedin [1,2^p]^2k be strictly
dominating and order invariant. There exists nonempty A containedin
[1,2^p]k, without 2^2^2^8k - 1, such that A U. R[A] meets every nonempty
order invariant image of Ak x {(1,2,4,...,2^p)} contained in [1,2^p]k.

The number 2^2^2^8k is crude, and will be examined at a later time.

Proposition 1 is provably equivalent to the consistency of ZFC + {there
exists a k-Mahlo cardinal}_k. Note that Proposition 2 is explicitly Pi01.

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

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 192nd 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
191:Boolean Roots 10/7/03  11:03 AM

Harvey Friedman