FOM: 57:Fixpoints/Summation/Large Cardinals

[Harvey Friedman]

This is the 57th 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

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 10, 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. It is inconvenient
that this fixed point is not always an infinite set. This is an issue
because we will be considering P(N) as a partial ordering under inclusion.
This situation is remedied by a simple condition called normality, which
asserts that finite sets are mapped to cofinite sets.

We then define an approximate fixed point of a normal contraction as a
chain of infinite elements of P(N) under inclusion which progressively get
closer and closer to being a fixed point. I.e., each set in the chain is
close to its image under the operator as 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 entirely of 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 normal contraction obeys a
monotonicity condition (decreasing) and we use large cardinals. This use of
large cardinals is demonstrably necessary.

Another wild card with the same effect: ask for approximate fixed points of
two normal contractions which start with the same term.

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 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]. 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. However we can get an infinite "fixed
point" in the following sense. We say that B is an initial segment of A if
and only if B = A intersect [0,n), where 0 <= n <= infinity. Note that A is
an initial segment of A.

THEROEM 2. Let phi be a contraction. There is an infinite A such that
phi(A) is an initial segment of A. The value phi(A) is unique, and in fact
is the unique fixed point of phi.

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

*for all 1 <= i <= n-1, phi(Ai+1) agrees with some initial segment of Ai+1
on the set of all k length sums from 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.

Condition ii) is needed in order to handle, e.g., the constant contractions.

THEOREM 3. Let A be the unique fixed point of the contraction phi. If A is
infinite then the infinite sequence of A's is an approximate fixed
point of phi of type (infinity,infinity). If A is finite then the infinite
sequence consisting of A union (max(A),infinity) is an approximate fixed
point of phi of type (infinity,infinity), where max(emptyset) = -1.

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 contraction has approximate fixed points of
every finite type whose first set consists of even integers.

THEOREM 5. Proposition 3 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 contraction has approximate fixed
points of every finite type (3,k) whose first set consists of even
integers. Every decreasing contraction has 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
operator" 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
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. You 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)
contractions have 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. A
weak contraction is a phi:P(N) into P(N) such that for some constant c > 1,
we have that 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,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,Sigma(U) 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).

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

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.