FOM: 62:Approximate fixed points revisited

[Harvey Friedman]

This is the 62nd in a series of self contained postings to FOM covering a
wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.
3:Simplicity  11/14/97 10:10AM.
4:Simplicity  11/14/97  4:25PM
5:Constructions  11/15/97  5:24PM
6:Undefinability/Nonstandard Models   11/16/97  12:04AM
7.Undefinability/Nonstandard Models   11/17/97  12:31AM
8.Schemes 11/17/97    12:30AM
9:Nonstandard Arithmetic 11/18/97  11:53AM
10:Pathology   12/8/97   12:37AM
11:F.O.M. & Math Logic  12/14/97 5:47AM
12:Finite trees/large cardinals  3/11/98  11:36AM
13:Min recursion/Provably recursive functions  3/20/98  4:45AM
14:New characterizations of the provable ordinals  4/8/98  2:09AM
14':Errata  4/8/98  9:48AM
15:Structural Independence results and provable ordinals  4/16/98
10:53PM
16:Logical Equations, etc.  4/17/98  1:25PM
16':Errata  4/28/98  10:28AM
17:Very Strong Borel statements  4/26/98  8:06PM
18:Binary Functions and Large Cardinals  4/30/98  12:03PM
19:Long Sequences  7/31/98  9:42AM
20:Proof Theoretic Degrees  8/2/98  9:37PM
21:Long Sequences/Update  10/13/98  3:18AM
22:Finite Trees/Impredicativity  10/20/98  10:13AM
23:Q-Systems and Proof Theoretic Ordinals  11/6/98  3:01AM
24:Predicatively Unfeasible Integers  11/10/98  10:44PM
25:Long Walks  11/16/98  7:05AM
26:Optimized functions/Large Cardinals  1/13/99  12:53PM
27:Finite Trees/Impredicativity:Sketches  1/13/99  12:54PM
28:Optimized Functions/Large Cardinals:more  1/27/99  4:37AM
28':Restatement  1/28/99  5:49AM
29:Large Cardinals/where are we? I  2/22/99  6:11AM
30:Large Cardinals/where are we? II  2/23/99  6:15AM
31:First Free Sets/Large Cardinals  2/27/99  1:43AM
32:Greedy Constructions/Large Cardinals  3/2/99  11:21PM
33:A Variant  3/4/99  1:52PM
34:Walks in N^k  3/7/99  1:43PM
35:Special AE Sentences  3/18/99  4:56AM
35':Restatement  3/21/99  2:20PM
36:Adjacent Ramsey Theory  3/23/99  1:00AM
37:Adjacent Ramsey Theory/more  5:45AM  3/25/99
38:Existential Properties of Numerical Functions  3/26/99  2:21PM
39:Large Cardinals/synthesis  4/7/99  11:43AM
40:Enormous Integers in Algebraic Geometry  5/17/99 11:07AM
41:Strong Philosophical Indiscernibles
42:Mythical Trees  5/25/99  5:11PM
43:More Enormous Integers/AlgGeom  5/25/99  6:00PM
44:Indiscernible Primes  5/27/99  12:53 PM
45:Result #1/Program A  7/14/99  11:07AM
46:Tamism  7/14/99  11:25AM
47:Subalgebras/Reverse Math  7/14/99  11:36AM
48:Continuous Embeddings/Reverse Mathematics  7/15/99  12:24PM
49:Ulm Theory/Reverse Mathematics  7/17/99  3:21PM
50:Enormous Integers/Number Theory  7/17/99  11:39PN
51:Enormous Integers/Plane Geometry  7/18/99  3:16PM
52:Cardinals and Cones  7/18/99  3:33PM
53:Free Sets/Reverse Math  7/19/99  2:11PM
54:Recursion Theory/Dynamics 7/22/99 9:28PM
55:Term Rewriting/Proof Theory 8/27/99 3:00PM
56:Consistency of Algebra/Geometry  8/27/99  3:01PM
57:Fixpoints/Summation/Large Cardinals  9/10/99  3:47AM
57':Restatement  9/11/99  7:06AM
58:Program A/Conjectures  9/12/99  1:03AM
59:Restricted summation:Pi-0-1 sentences  9/17/99  10:41AM
60:Program A/Results  9/17/99  1:32PM
61:Finitist proofs of conservation  9/29/99  11:52AM

This is the first in a series of three postings that corrects, restates,
and extends all of the postings #57-#60.

In this posting, we restate the results about approximate fixed points in
#57. We add some new results and correct a problem with the decreasing
condition used in #57. We now use a kind of continuity condition.

By way of orientation, two different lines of development have emerged
since the November 1998 Annals of Mathematics paper. The first one is
1-dimensional and has a considerable amount of technical overlap with that
paper, but does not directly rely on that paper. The second one is
multi-dimensional and directly builds on top of the Annals paper. This
posting concerns the 1-dimensional approach.

APPROXIMATE FIXED POINTS AND LARGE CARDINALS
by
Harvey M. Friedman
October 9, 1999

1. APPROXIMATE FIXED POINTS ON P(N)

We use Z for the set of all integers and N for the set of all nonnegative
integers. Let A,B,C containedin Z. We say that A,B agree on C if and only
if A intersect C = B intersect C.

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+1).

This is the usual definition of contraction under the usual metric on P(N).

Note that a contraction is determined by its values at finite sets. In
this sense, we are in the realm of discrete - rather than continuous or set
theoretic - mathematics.

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

THEOREM 1.1. Every contraction on P(N) has a unique fixed point.

We would like to have some control over fixed points of contractions.
However, fixed points are unique and can be arbitrary.

We therefore work with "approximate" fixed points.

Let n,k >= 1. Informally, an approximate fixed point of phi of type (n,k)
is a chain of sets A_1 containedin ... containedin A_n containedin N such
that

*for all 1 <= i <= n-1, phi(A_i+1) and A_i+1 agree on lots of integers
asociated with A_i.*

The formal requirement is that

*for all 1 <= i <= n-1, phi(A_i+1) and A_i+1 agree on all sums and products
of length k from A_i union {0,1}.*

An infinite approximate fixed point of type (n,k) is an approximate fixed
point of type (n,k) whose terms are infinite.

THEOREM 1.2. Let phi:P(N) into P(N) have fixed point A. Then any finite
sequence consisting of A is an approximate fixed point of phi.

We have two related goals. Firstly, we would like to find approximate fixed
points whose first set is "large." Secondly, we would like a common
approximate fixed point theorem to the effect that any finite set of
contractions have approximate fixed points with the same first set.

We can achieve both goals using a stronger notion of contraction.

We say that phi is a decreasing contraction on P(N) if and only if phi is a
contraction satisfying

A containedin B implies phi(A) contains phi(B).

We need a strengthening of this concept. We say that phi is a uniformly
decreasing contraction on P(N) if and only if phi is a decreasing
contraction on P(N) for which there exists r >= 0 such that

*the value of phi at any set is equaled to the value of phi at some subset
of cardinality <= r.*

We can redefine a uniformly decreasing contraction on P(N) by the following
single sensible condition. There exists r >= 0 such that for all A and n,
if n notin phi(A) then there exists B containedin A intersect [0,n) with at
most r elements such that

*if B containedin C containedin N then n notin phi(C).*

We now present our first independent statement.

PROPOSITION 1.3. Let V be any countable set of infinte subsets of N. Any
uniformly decreasing contraction on P(N) mapping finite sets to cofinite
sets has approximate fixed points of every type whose first set meets every
element of V.

The condition "mapping finite sets to cofinite sets" is needed to rule out,
e.g., phi that are constantly a fixed finite set.

Here is an important consequence of Proposition 1.3.

PROPOSITION 1.4. Let E be an infinte subset of N. Any uniformly decreasing
contraction on P(N) mapping finite sets to cofinite sets has approximate
fixed points of every type whose first set is an infinite subset of E.

A particularly weak special case of Proposition 1.4 is the following.

PROPOSITION 1.5. Any uniformly decreasing contraction on P(N) mapping
finite sets to cofinite sets has infinite approximate fixed points of every
type where an odd integer appears.

We can obtain the following by iterating Proposition 1.4 any finite number
of times.

PROPOSITION 1.6. Let t be a type. Any finite set of uniformly decreasing
contractions on P(N) mapping finite sets to cofinite sets have respective
infinite approximate fixed points of type t with the same first set.

The following can be obtained by iterating Proposition 1.4 infinitely many
times.

PROPOSITION 1.7. Let t be a type. Any countable set of uniformly decreasing
contractions on P(N) mapping finite sets to cofinite sets have respective
infinite approximate fixed points of type t with almost equal first sets.

THEOREM 1.8. Propositions 1.3 - 1.7 are provably equivalent to the
1-consistency of MAH = ZFC + {there exists a k-Mahlo cardinal}_k over ACA.
The forward direction can be proved in RCA_0. In particular, they are
independent of ZFC.

Theorem 1.8 holds even if we weaken the Propositions 1.3, 1.4, 1.6, 1.7
substantially. Here are some simultaneous weakenings:

i) restrict to types of the form (3,k) and (n,2);
ii) restrict 1.6 to two uniformly decreasing contractions;
iii) replace "all sums and products of length k from A_i union {0,1}" in
the definition of approximate fixed points with "A_i + A_i."

In Proposition 1.5, we can use weakenings i), ii), and

iii') replace "all sums and products of length k from A_i union {0,1}" in
the definition of approximate fixed points with "(A_i + A_i) union {1}."

In Proposition 1.5, we can also use weakenings 1) - iii) and replace "odd"
by "infinitely many odd" or "infinitely many even".

Propositions 1,3 - 1.7 are provable for types (2,k) and (n,1).

2. APPROXIMATE FIXED POINTS IN P(Z)

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

We say that phi:P(Z) into P(Z) is a contraction if and only if for all n >=
0 and A,B in P(N), if A,B agree on (-n,n) then phi(A),phi(B) agree on
(-n-1,n+1).

THEOREM 2.1. Every contraction on P(Z) has a unique fixed point.

Let n,k >= 1. An approximate fixed point of phi of type (n,k) is a chain of
sets A_1 containedin ... containedin A_n containedin Z such that

*for all 1 <= i <= n-1, phi(A_i+1) and A_i+1 agree on all sums and products
of length k from A_i union {0,+-1}.*

Note the use of +-1, taking advantage of the ring operations on Z.

An infinite approximate fixed point of type (n,k) is an approximate fixed
point of type (n,k) whose terms are infinite.

A bi-infinite approximate fixed point of type (n,k) is an approximate fixed
point of type (n,k) whose terms are bi-infinite; i.e., contain infinitely
many positive and infinitely many negative elements.

We would like to obtain a bi-infinite approximate fixed points.

We say that phi:P(Z) into P(Z) is a compression on P(Z) if and only if
there exists r >= 0 and t > 1 such that

*if A,B agree on (-n,n) then phi(A),phi(B) agree on (-tn-1,tn+1).*

We say that phi is a decreasing compression on P(Z) if and only if phi is a
compression on P(Z) satisfying

*A containedin B implies phi(A) contains phi(B).*

We say that phi is a uniformly decreasing compression on P(Z) if and only
if phi is a decreasing compression on P(Z) for which there exists r >= 0
such that

*the value of phi at any set is equaled to the value of phi at some subset
of cardinality <= r.*

We can redefine a uniformly decreasing compression on P(N) by the following
single sensible condition. There exists r >= 0 and t > 1 such that for all
A and n, if n notin phi(A) then there exists B containedin A intersect
(-n/t,n/t) with at most r elements such that

*if B containedin C containedin Z then n notin phi(C).*

The primary reason for moving over to P(Z) from P(N) is the following
bi-infinite approximate fixed point Proposition.

PROPOSITION 2.2. Every uniformly decreasing compression on P(Z) mapping
finite sets to cofinite sets has bi-infinite approximate fixed points of
every type.

Here is a weak special case of Proposition 2.2.

PROPOSITION 2.3. Every uniformly decreasing compression on P(Z) mapping
finite sets to cofinite sets has an infinite approxiamte fixed point of
every type with a positive element.

A secondary reasons for using P(Z) is to support all of the ring operations
in the definition of approximate fixed point. However, we must use t > 1.
If we use t = 1 then Proposition 2.2 and all subsequent Propositions are
false.

The results about P(N) carry over to P(Z). Proposition 2.2 follows easily
from the following.

PROPOSITION 2.4. Let V be any countable set of infinte subsets of Z. Any
uniformly decreasing contraction on P(Z) mapping finite sets to cofinite
sets has approximate fixed points of every type whose first set meets every
element of V.

We can obtain the following from Proposition 2.4.

PROPOSITION 2.5. Let t be a type. Any finite set of uniformly decreasing
compressions on P(Z) mapping finite sets to cofinite sets have respective
infinite approximate fixed points of type t with the same first set.
Moreover, we can replace "infinite" by  "bi-infinite."

PROPOSITION 2.6. Let t be a type. Any countable set of uniformly decreasing
compressions on P(N) mapping finite sets to cofinite sets have respective
infinite approximate fixed points of type t with almost equal first sets.
Moreover, we can replace "infinite" by "bi-infinite."

THEOREM 2.7. Propositions 2.2 - 2.6 (all forms) are provably equivalent to
the 1-consistency of MAH = ZFC + {there exists a k-Mahlo cardinal}_k over
ACA. The forward direction can be proved in RCA_0. In particular, they are
independent of ZFC.

Theorem 2.7 holds even if we weaken the Propositions substantially. Here
are some simultaneous weakenings:

i) restrict to types of the form (3,k) and (n,2);
ii) restrict 2.5 to two uniformly decreasing compressions on P(Z).

Propositions 2.2 - 2.6 are provable for types (2,k) and (n,1).