FOM: 57':Restatement

[Harvey Friedman]

The part of posting 57:Fixpoints/Summation/Large Cardinals  9/10/99  3:47AM
concerning Fixpoints (not Summation) is incorrect as stated. We add a
condition called cofiniteness, and simplify the definition of approximate
fixed point. Here is a self contained restatement of the entire posting.
**********

We present two closely related new kinds of discrete independence results.
They are closely related technically to the previous numbered postings 29,
31, 39, and 45. The abstract is self contained.

We postpone discussion of finite forms.

***LARGE CARDINALS, FIXED POINTS, AND SUMMATION***
by
Harvey M. Friedman
Department of Mathematics
Ohio State University
September 11, 1999

We present new necessary uses of large cardinals in discrete mathematics.
The first approach involves fixed points given by the usual contraction
mapping theorem on the Cantor space P(N) of sets of natural numbers. The
second approach involves the action of restricted integer summation as an
operator from P(Z) into P(Z). The approaches are closely related.

1. APPROXIMATE FIXED POINTS - OVERVIEW

The usual contraction mapping theorem in this context says that every
contraction phi:P(N) into P(N) has a unique fixed point.

We then define an approximate fixed point of a cofinite contraction as a
chain of elements of P(N) under inclusion, where each set in the chain is
close to its image under the operator in a sense that is measured by the
preceding element
in the chain.

Of course, we can just take each term to be the unique fixed point, and
then the terms are actual fixed points. But we then throw a wild card into
the mix by demanding that the first set in the approximate fixed point
consist of infinitely many even integers. This requirement cannot be met with
actual fixed points. However this requirement can be met with approximate
fixed points of finite length - if the contraction is cofinite and decreasing,
and we use large cardinals. This use of large cardinals is demonstrably
necessary.

Another wild card with the same effect is this. Ask for approximate fixed
points which start with the same infinite set.

In this posting, we consider only the infinitary discrete mathematical
context. We do not address finitary considerations. However, we do know
that the statements involved are provably equivalent to 1-consistency.

The issue of finite forms will be taken up in later postings.

2. APPROXIMATE FIXED POINTS

We use N for the set of all nonnegative integers. Let A,B,C containedin N.
We say that A = B on C if and only if A intersect C = B intersect C. For k
>= 1 we write Sk(A) for the set of all length k sums of elements of A,
where repetitions are allowed.

Let P(N) be the Cantor space of all subsets of N. We are interested in
mappings phi:P(N) into P(N).

We say that phi:P(N) into P(N) is a contraction if and only if
for all n >= 0 and A,B in P(N), if A,B agree on [0,n) then phi(A),phi(B)
agree on [0,n]. Throughout this paper, all contractions will map P(N) into
P(N).

Note that a contraction is determined by its values at finite sets. In this
sense, we are in the realm of discrete mathematics.

In this context, the classical contraction mapping theorem says the
following.

THEOREM 1. Every contraction has a unique fixed point.

This fixed point may be finite. A cofinite contraction is a contraction
which maps finite sets to cofinite sets.

THEROEM 2. The unique fixed point of every cofinite contraction is infinite.

Let phi be a contraction and n,k >= 1. An approximate fixed point of phi of
type (n,k) is a chain of sets A1 containedin ... containedin An containedin
N such that

*for all 1 <= i <= n-1, phi(Ai+1) = Ai+1 on Sk(Ai union {0,1}).*

We also allow n and/or k to be infinite, where k = infinity indicates that
we take all finite length sums.

An infinite approximate fixed point is an approximate fixed point whose
first set is infinite.

THEOREM 3. Let A be the unique fixed point of the contraction phi. Then the
infinite sequence of A's is an approximate fixed
point of phi of type (infinity,infinity).

A decreasing contraction is a contraction phi:P(N) into P(N) such that A
containedin B implies phi(B) containedin phi(A).

PROPOSITION 4. Every decreasing cofinite contraction has infinite
approximate fixed points of
every finite type whose first set consists of even integers.

THEOREM 5. Proposition 4 is provably equivalent to the 1-consistency of MAH
= ZFC + {there exists a k-Mahlo cardinal}_k. In particular, it is
independent of ZFC.

Theorem 5 also holds for the following weakening of Proposition 5.

PROPOSITION 6. Every decreasing cofinite contraction has infinite
approximate fixed
points of every finite type (3,k) whose first set consists of even
integers. Every decreasing cofinite contraction has infinite approximate
fixed points of every finite type (n,2) whose first set consists of even
integers.

We can enlarge the class of contractions considered. For n
in N, we can look at increasing chains of subsets of N, and ask how many
times the truth value of the statement "n lies in the value of the
contraction" changes as we pass through the sets in the chain in order. If
there is a uniform bound r not depending on n then we call this an
admissible contraction. Then the results above hold for admissible cofinite
contractions. Note that every decreasing contraction is an admissible
contraction, where the uniform bound is taken to be 1.

What's special about the even integers here? Nothing. We can require that
the first set be a subset of any given infinite subset of N, and the
statement is still provable from large cardinals. In fact, the mere
existence of a subset of N so that you can always insist on the appearance
of some element from that subset is already provably equivalent to the
1-consistency of Mahlo cardinals of finite order. On a related note, we get
the necessary use of Mahlo cardinals of finite order for this:

PROPOSITION 7. Let n,k >= 1. Any two decreasing (or admissible)
cofinite contractions have infinite approximate fixed points of type (n,k)
with the same first set.

In the definition of apporoximate fixed points, we can use other functions
instead of or in addition to summation. We can use finitely many functions
of several variables on N that are strictly increasing in each argument.
More generally, we can use finitely many functions of several variables
that are increasing in each argument and dominating.

Can we use minus instead of or in addition to + and get the same results?
Yes, provided we put an additional condition on the contractions: there exists
c > 1 such that for all n >= 0 and A,B in P(N), if A = B on [0,n) then
phi(A) = phi(B) on [0,cn]. This amounts to a higher order Lipschitz
condition on phi.

3. RESTRICTED SUMMATION

Let A,B,C be three sets. We say that A,B partitions C if and only if

i) A intersect B intersect C = emptyset;
ii) C containedin A union B.

We say that A,B disjointly partitions C if and only if

i) A intersect B = emptyset;
ii) C containedin A union B.

Let Z be the set of all integers, Z+ be the set of all positive integers.
For A containedin Z, let Sigma(A) be the set of all sums x1 + ... + xn, n
>= 1, such that x1,...,xn in A. We call Sigma:P(Z) into P(Z) the summation
function.

Let Z* be the set of all nonempty finite sequences of integers. We view Z
as a subset of Z*. We say that U containedin Z* is finite dimensional if
and only if there is a finite upper bound to the lengths of the elements of
U.

Each U containedin Z* defines the restricted summation function
Sigma_U:P(Z) into P(Z) given by SigmaU(A) = {x1 + ... + xn: n >= 1,
x1,...,xn in A, and (x1,...,xn) in U}. Note that if U = Z* then Sigma_U =
Sigma.

THEOREM 1. Let U containedin Z*\Z. There is a unique A containedin Z+ such
that A,SigmaU(A) partitions Z+.

PROPOSITION 2. Let U,V be finite dimensional subsets of Z*\Z. There exists
infinite sets A containedin B containedin C containedin Z+ such that
B,SigmaU(B) partitions SigmaV(A), and C\A,SigmaU(C)\A partitions SigmaV(B).

Obviously if we delete the two occurrences of \A, then Proposition 2 would
be a trivial consequence of Theorem 1.

We can strengthen Proposition 2 considerably in many ways. Here is an example.

PROPOSITION 3. Let U,V be finite dimensional subsets of Z*\Z, and n >= 1.
There exists infinite sets A1 properlycontainedin ... properlycontainedin
An properlycontainedin Z+ such that for all 1 <= i <= n-1,
Ai+1\A1,SigmaU(Ai+1)\A1 disjointly partitions SigmaV(Ai).

Again, if we delete \A1, then Proposition 3 would be a trivial consequence
of Theorem 1.

THEOREM 4. Propositions 2 and 3 are provably equivalent, over RCA_0, to the
1-consistency of MAH = ZFC + {there exists an n-Mahlo cardinal}n. In
particular, they are independent of ZFC.