[FOM] 403: Set Equation Tower Theory 1
Harvey Friedman
friedman at math.ohio-state.edu
Mon Mar 22 00:51:41 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.
***********************************
TYPOS IN http://www.cs.nyu.edu/pipermail/fom/2010-March/014468.html
In the table of contents, I used "single relation" and "two
relations", but in the actual titles of the sections, I used "binary"
and "ternary". The latter are the correct titles.
Sorry about any confusion.
********************
Conceptual breakthroughs will be evident upon reading this abstract.
MOTIVATING THEME: Do certain set equations emanating out of an
important area in graph theory going back to von Neumann (game theory)
have nontrivially self embeddable solutions? And if so, what are the
first integers moved by the self embeddings?
IMAGE EQUATION TOWER THEORY 1
by
Harvey M. Friedman
March 22, 2010
1. SET EQUATIONS AND TOWERS.
2. SET EQUATION TOWER THEOREMS - infinite.
3. SET EQUATION TOWER THEOREMS - finite.
1. SET EQUATIONS AND TOWERS.
We use N for the set of nonnegative integers, and N^+ for the set of
positive integers.
Let R be a binary relation on N^k. I.e., R is a subset of N^k x N^k.
Let A be a subset of N^k. We have the usual forward image construction
R[A] = {y: there exists x in A such that R(x,y)}.
We will need the following upper image construction
R<[A] = {y: there exists x in A such that max(x) < max(y) and R(x,y)}.
The following theorem is a version of the classical theorem in graph
theory of the existence and uniqueness of dominators (kernels) in
digraphs with a "no finite path" condition, that essentially goes back
to von Neumann in his book with Morgenstern on game theory:
THEOREM 1.1. For all R contained in N^k x N^k, the equation A = N^k
\R<[A] has a unique solution.
It is natural to think of A = N^k\R<[A] as a fixed point equation,
asserting that A is a fixed point of the operator that maps any A to
N^k\R<[A]. The space of all subsets of N^k is a Cantor space, and this
operator is a very continuous function. This is highly suggestive, and
we are not nearly done exploiting this point of view properly.
We are interested in embeddings between solutions. Let A,B be
contained in N^k. Wr write fld(A) for the set of integers that appear
as coordinates in A.
We say that h is an embedding of A into B if and only if h is an
injection from fld(A) into fld(B) such that
i. For all n,m in fld(A), n < m iff h(n) < h(m).
ii. For all n_1,...,n_k in fld(A), (n_1,...,n_k) in A iff
(h(n_1),...,h(n_k)) in B.
Any function is said to be nontrivial if and only if it is not the
identity on its domain. We say that h is a self embedding of A if and
only if h is an embedding from A into A.
THEOREM 1.2. The following is false. For all R contained in N^k x N^k,
the equation A = N^k\R<[A] has a solution with a nontrivial self
embedding. This is false even for k = 1.
There is an obvious reason behind this. We cannot even guarantee that
A be infinite. E.g., let R = N x N.
To ensure that there are infinite solutions, it is natural to assume
that R is contained in N^+k x N^+k.
THEOREM 1.3. The following is false. For all R contained in N^+k x N^
+k, the equation A = N^k\R<[A] has a solution with a nontrivial self
embedding.
The difficulty here is that too many infinite A can be the unique
solution for some R contained in N^+k x N^+k.
THEOREM 1.4. Let A contained in N^k. The following are equivalent.
i. A contains all x in N^k\N^+k.
ii. For some R contained in N^+k x N^+k, A = N^k\R<[A].
We need to weaken the equation. The most obvious weakening is as
follows.
Let A# = fld(A)^k. We can view A# to be the least subspace of N^k
containing A - where the subspaces of N^k are taken to be the E^k, E
contained in N.
We now consider the weaker equation
A = A#\R<[A].
Again, A is an unknown subset of N^k, and R is a particular subset of
N^k x N^k.
Obviously, if A = N^k\R<[A] then A = A#\R<[A].
Here the solution spaces behave quite differently.
THEOREM 1.5. For all R contained in N^+k x N^+k, there are continuumly
many solutions to A = A#\R<[A].
However, there is an interesting finite object that we can associate
to each integer k >= 1, up to isomorphism.
THEOREM 1.6. For all k >= 1, there is a finite set W_k of infinite
subsets of N^k such that the following holds.
i. For all R contained in N^+k x N^+k, A = A#\R<[A] has a solution
isomorphic to an element of W_k.
ii. The above is false for any proper subset of W_k.
Furthermore, W_k is unique up to isomorphism.
We call W_k the basis for the formal equation A = A#\R<[A], R
contained in N^+k x N^+k. It is uniquely defined up to isomorphism.
It can be shown that each W_k can be presented as a finite set of very
computable infinite subsets of N^k. However, there are fundamental
barriers to "understanding" these W_k, and it appears that even for
modest k >= 1 - perhaps k = 6 or less - one cannot count the number of
elements of W_k, in the sense that there is no number for which it can
be proved in ZFC that that number is the correct count. Furthermore,
this negative result doesn't depend on ZFC, and holds for any
consistent set theory that is not too complicated. E.g., all of the
proposed extensions of ZFC are sufficiently simple. So this is NOT a
situation where we can do something with large cardinals that we
cannot do in ZFC.
Back to self embeddability.
THEOREM 1.7. The following is false. For all R contained in N^+k x N^
+k, the equation A = A#\R<[A] has an infinite solution with a
nontrivial self embedding.
So now what? We weaken the equation further by introducing a second
set variable. We consider
A = A#\R<[B] contained in B
Here A,B are unknown subsets of N^k, and R is a particular subset of
N^k x N^k.
The notion of embedding can be easily lifted to sequences of subsets
of N^k. We say that h is an embedding of A_1,...,A_p into B_1,...,B_p
if and only if for all 1 <= i <= p, h|fld(B_i) is an embedding from
A_i into B_i.
The critical point of any partial function from N into N is the least
integer which is moved by the function. Obviously nontrivial
embeddings have critical points.
Now we can get our nontrivial self embeddings, and even control the
critical point.
THEOREM 1.8. For all R contained in N^+k x N^+k,
A = A#\R<[B] contained in B
has an infinite solution with a self embedding with critical point
min(fld(A)).
2. SET EQUATION TOWER THEOREMS - infinite.
We think of A = A#\R<[B] as an approximation to A = A#\R<[B], and we
have seen that this behaves differently: compare Theorems 1.7 and 1.8.
An even better approximation to A = A#\R<[A] is the system of equations
A = A#\R<[B] contained in
B = B#\R<[C] contained in C.
PROPOSITION 2.1. For all R contained in N^+k x N^+k, the system
A = A#\R<[B] contained in
B = B#\R<[C] contained in C.
has an infinite solution with a self embedding with critical point
min(fld(A)).
The only proof we have of Proposition 2.1 uses a bit more than SRP
(e.g., SRP+). We don't know if it is provable in ZFC.
PROPOSITION 2.2. For all R contained in N^+k x N^+k, the system
A = A#\R<[B] contained in
B = B#\R<[C] contained in
C = C#\R<[D] contained in D.
has an infinite solution with a self embedding with critical point
min(fld(A)).
PROPOSITION 2.3. For all k,p >= 1, every R contained in N^+k x N^+k,
the system
A_1 = A_1#\R<[A_2] contained in
A_2 = A_2#\R<[A_3] contained in
...
A_p = A_p#\R<[A_p+1] contained in A_p+1
has an infinite solution with a self embedding with critical point
min(fld(A)).
THEOREM 2.4. Propositions 2.2, 2.3 are provable in SRP+, but not from
any consequence of SRP consistent with RCA_0. Propositions 2.2, 2.3
are provably equivalent to Con(SRP) over ACA'.
Here SRP+ = ZFC + "for all k there exists a limit ordinal with the k-
SRP". SRP = ZFC + {there exists a limit ordinal with the k-SRP}_k. We
say that lambda has the k-SRP if and only if lambda is a limit
ordinal, where every partition of the unordered k tuples from lambda
into two pieces has a homogenous set which is a stationary subset of
lambda. ACA' is ACA_0 + "for all n and x contained in omega, the n-th
Turing jump of x exists".
3. SET EQUATION TOWER THEOREMS - finite
We use |A| for the cardinality of A. We work with R contained in
{1,...,t}^k x {1,...,t}^k. Here solutions are required to be subsets
of {0,...,t}^k.
Since we are working with finite sets, we must relax the notion of
embedding. An embedding from A_1,...,A_p into B_1,...,B_p maps
fld(A_p) intersect into fld(B_p) intersect [0,b], where a is the
second largest element of fld(A_1) and b is the second largest element
of fld(B_1).
PROPOSITION 3.1. Let t >> k,r >= 1. For all R contained in {1,...,t}^k
x {1,...,t}^k, the system
A = A#\R<[B] contained in
B = B#\R<[C] contained in
C = C#\R<[D] contained in D
has a solution with |A| > r, and a self embedding with critical point
min(fld(A)). Furthermore, it suffices to assume that t is greater than
an exponential stack of 8kr 2's.
PROPOSITION 3.2. Let t >> k,r,p >= 1. For all R contained in
{1,...,t}^k x {1,...,t}^k, the system
A_1 = A_1#\R<[A_2] contained in
A_2 = A_2#\R<[A_3] contained in
...
A_p = A_p#\R<[A_p+1] contained in A_p+1
has a solution with |A| > r, and a self embedding with critical point
min(fld(A_1)). Furthermore, it suffices to assume that t is greater
than an exponential stack of 8krp 2's.
THEOREM 3.3. Propositions 3.1, 3.2 are each provable in SRP+, but not
from any consequence of SRP consistent with SEFA. Propositions 3.1,
3.2 are each provably equivalent to Con(SRP) over SEFA.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 402nd 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-349 can be found at http://www.cs.nyu.edu/pipermail/fom/2009-August/014004.html
in the FOM archives.
350: one dimensional set series 7/23/09 12:11AM
351: Mapping Theorems/Mahlo/Subtle 8/6/09 10:59PM
352: Mapping Theorems/simpler 8/7/09 10:06PM
353: Function Generation 1 8/9/09 12:09PM
354: Mahlo Cardinals in HIGH SCHOOL 1 8/9/09 6:37PM
355: Mahlo Cardinals in HIGH SCHOOL 2 8/10/09 6:18PM
356: Simplified HIGH SCHOOL and Mapping Theorem 8/14/09 9:31AM
357: HIGH SCHOOL Games/Update 8/20/09 10:42AM
358: clearer statements of HIGH SCHOOL Games 8/23/09 2:42AM
359: finite two person HIGH SCHOOL games 8/24/09 1:28PM
360: Finite Linear/Limited Memory Games 8/31/09 5:43PM
361: Finite Promise Games 9/2/09 7:04AM
362: Simplest Order Invariant Game 9/7/09 11:08AM
363: Greedy Function Games/Largest Cardinals 1
364: Anticipation Function Games/Largest Cardinals/Simplified 9/7/09
11:18AM
365: Free Reductions and Large Cardinals 1 9/24/09 1:06PM
366: Free Reductions and Large Cardinals/polished 9/28/09 2:19PM
367: Upper Shift Fixed Points and Large Cardinals 10/4/09 2:44PM
368: Upper Shift Fixed Point and Large Cardinals/correction 10/6/09
8:15PM
369. Fixed Points and Large Cardinals/restatement 10/29/09 2:23PM
370: Upper Shift Fixed Points, Sequences, Games, and Large Cardinals
11/19/09 12:14PM
371: Vector Reduction and Large Cardinals 11/21/09 1:34AM
372: Maximal Lower Chains, Vector Reduction, and Large Cardinals
11/26/09 5:05AM
373: Upper Shifts, Greedy Chains, Vector Reduction, and Large
Cardinals 12/7/09 9:17AM
374: Upper Shift Greedy Chain Games 12/12/09 5:56AM
375: Upper Shift Clique Games and Large Cardinals 1
376: The Upper Shift Greedy Clique Theorem, and Large Cardinals
12/24/09 2:23PM
377: The Polynomial Shift Theorem 12/25/09 2:39PM
378: Upper Shift Clique Sequences and Large Cardinals 12/25/09 2:41PM
379: Greedy Sets and Huge Cardinals 1
380: More Polynomial Shift Theorems 12/28/09 7:06AM
381: Trigonometric Shift Theorem 12/29/09 11:25AM
382: Upper Shift Greedy Cliques and Large Cardinals 12/30/09 2:51AM
383: Upper Shift Greedy Clique Sequences and Large Cardinals 1
12/30/09 3:25PM
384: THe Polynomial Shift Translation Theorem/CORRECTION 12/31/09
7:51PM
385: Shifts and Extreme Greedy Clique Sequences 1/1/10 7:35PM
386: Terrifically and Extremely Long Finite Sequences 1/1/10 7:35PM
387: Better Polynomial Shift Translation/typos 1/6/10 10:41PM
388: Goedel's Second Again/definitive? 1/7/10 11:06AM
389: Finite Games, Vector Reduction, and Large Cardinals 1 2/9/10
3:32PM
390: Finite Games, Vector Reduction, and Large Cardinals 2 2/14/09
10:27PM
391: Finite Games, Vector Reduction, and Large Cardinals 3 2/21/10
5:54AM
392: Finite Games, Vector Reduction, and Large Cardinals 4 2/22/10
9:15AM
393: Finite Games, Vector Reduction, and Large Cardinals 5 2/22/10
3:50AM
394: Free Reduction Theory 1 3/2/10 7:30PM
395: Free Reduction Theory 2 3/7/10 5:41PM
396: Free Reduction Theory 3 3/7/10 11:30PMs
397: Free Reduction Theory 4 3/8/10 9:05AM
398: New Free Reduction Theory 1 3/10/10 5:26AM
399: New Free Reduction Theory 2 3/12/10 9:36AM
400: New Free Reduction Theory 3 3/14/10 11:55AM
401: New Free Reduction Theory 4 3/15/10 4:12PM
402: New Free Reduction Theory 5 3/19/10 12:59PM
Harvey Friedman
More information about the FOM
mailing list