FOM: 64:Finite Posets/Large Cardinals
Harvey Friedman
friedman at math.ohio-state.edu
Mon Oct 11 01:37:02 EDT 1999
This is the 64th 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
62:Approximate fixed points revisited 10/11/99 1:35AM
63:Disjoint Covers/Large Cardinals 10/11/99 1:36AM
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.
Postings #62 and #63 concern the first line of development. This posting
concerns the second of these two lines of development, and represents the
state of the art on this second line of development.
The first line of developemnt is 1-dimensional and has a considerable
amount of technical overlap with the Annals paper, but does not directly
rely on that paper. The second line of development is multi-dimensional and
directly builds on top of the Annals paper.
The previous state of the art in this second line of development is
discussed in posting #26, #28, #28', #30, #32.
In this posting, the new advance is to use a notion of optimization based
on a natural assignment of positive real numbers to posets in Z^+k. We look
at such posets whose assigned real number is largest as compared to other
such posets with the same field. We obtain results about the structure of
such optimized posets using large cardinals in an essential way.
NOTE: There are a number of new technical ideas needed to prove these
results, and I am at the outer limit of what I can safely claim without a
detailed manuscript. These results now look stable enough for publication.
**********
POSET OPTIMIZATION AND THE NECESSARY USE OF LARGE CARDINALS
by
Harvey M. Friedman
October 1, 1999
1. POSET PRELIMINARIES
We begin by fixing standard terminology and notation regarding posets.
A poset is a reflexive, transitive, and antisymmetric relation <=. I.e., <=
is a set of ordered pairs such that
i) if x <= y then x <= x and y <= y;
ii) if x <= y and y <= z then x <= z;
iii) if x <= y and y <= x then x = y.
The field of <=, fld(<=), is {x: x <= x}. We write x < y if and only if x
<= y and x not= y.
We say that x is a predecessor of y in <= if and only if x < y. We say that
x is an immediate predecessor of y in <= if and only if
i) x < y;
ii) there is no z such that x < z < y.
A maximal point of <= is a field element x which is not a predecessor.
We write <=_x for <= intersection {y: y <= x}^2.
The height of a poset <= is the length of the longest finite sequence x_1 <
x_2 ... < x_n. If there is no longest length, then the height is considered
to be infinity.
2. OPTIMIZED POSETS IN N^k
We use N for the set of all nonnegative integers. We write PO(k) for the
set of all posets <= such that
i) fld(<=) containedin N^k;
ii) x < y implies max(x) < max(y).
Here max(x) is the maximum of the coordinates of x, and the second < in ii)
is numerical.
We write FPO(k) for the set of all elements of PO(k,r) whose field is finite.
We write PO(k,r) and FPO(k,r) for the set of all elements of PO(k) and
FPO(k), respectively, such that every field element has at most r immediate
predecessors.
Let F:FPO(k,r) into R. We define F*:PO(k,r) into R union {+-infinity} by
F*(<=) = Sum over x in fld(<=)\{0} of F(<=_x)/max(x). Here R is the set of
all real numbers. F* is taken to be undefined if this sum does not converge
to an extended real number.
WARNING: F* may not extend F.
We say that <= is F*-optimal if and only if F*(<=) is defined, and there is
no <=' in PO(k,r) with the same field such that F*(<=') > F*(<=).
THEOREM 2.1. Let k,r >= 1 and F:FPO(k,r) into R have finite range. There
exists an F*-optimal poset whose field contains an infinite Cartesian
power. If F is also nonnegative, then there exist F*-optimal posets whose
field is any prescribed subset of N^k.
Finite range means that the range is a finite set.
PROPOSITION 2.2. Let k,r >= 1 and F:FPO(k,r) into R have finite range.
There exists an F*-optimal poset of finite height whose field contains an
infinite Cartesian power.
I.e., whose field contains E^k for some infinite E containedin N.
THEOREM 2.3. Proposition 2.2 is provably equivalent to the 1-consistency of
MAH = ZFC + {there exists an n-Mahlo cardinal}_n over ACA. The forward
direction is provable in RCA_0.
3. LARGER CARDINALS
We say that x in Z^+k is strictly increasing if and only if each coordinate
is strictly less than the next.
For x,y in N^k, we say that x is entirely lower than y if and only if
every coordinate of x is strictly less than every coordinate of y.
PROPOSITION 3.1. Let k,r >= 1 and F:FPO(k,r) into Z have finite range.
There exists an F*-optimal poset whose maximal points comprise the strictly
increasing k tuples from an infinite set, all of which have the same
entirely lower predecessors.
And here is a sharper form.
PROPOSITION 3.2. Let k,r >= 1 and F:FPO(k,r) into Z have finite range.
There exists an F*-optimal poset whose maximal points comprise the strictly
increasing k tuples from an infinite set, all of which have the same
entirely lower predecessors and the same number of predecessors.
THEOREM 3.3. Propositions 3.1 and 3.2 are provably equivalent to the
1-consistency of SUB = ZFC + {there exists an n-subtle cardinal}_n over
ACA. The forward direction is provable in RCA_0.
4. FINITE FORMS
First we begin with two semifinite forms. The hypotheses are infinite but
the conclusion is finite.
Here we will not need the parameter r. For F:FPO(k) into R, we define F* as
before. Also <= is an F*-optimal poset if and only if F*(<=) is defined,
and for no <=' in PO(k) with the same field, is F*(<=') > F*(<=).
PROPOSITION 4.1. Let k,p >= 1 and F:FPO(k) into Z have finite range. There
exists a finite F*-optimal poset whose maximal points comprise the strictly
increasing k tuples from a p element set, all of which have the same
entirely lower predecessors.
And here is a sharper form.
PROPOSITION 4.2. Let k,p >= 1 and F:FPO(k) into Z have finite range. There
exists a finite F*-optimal poset whose maximal points comprise the strictly
increasing k tuples from a p element set, all of which have the same
entirely lower predecessors and the same number of predecessors.
We now give the obvious finite forms. Let PO(k:t) be the set of all
elements of PO(k) whose field is contained in {0,...,t}^k. Let F:PO(k:t)
into R. We define F* as before. Also <= is an F*-optimal poset if and only
if <= in PO(k:t) and for no <=' in PO(k:t) with the same field, is F*(<=')
> F*(<=).
PROPOSITION 4.3. Let t >> k,r,p >= 1 and F:FPO(k:t) into {-r,...,r}. There
exists an F*-optimal poset whose maximal points comprise the strictly
increasing k tuples from a p element set, all of which have the same
entirely lower predecessors.
And here is a sharper form.
PROPOSITION 4.4. Let t >> k,r,p >= 1 and F:FPO(k:t) into {-r,...,r}. There
exists an F*-optimal poset whose maximal points comprise the strictly
increasing k tuples from a p element set, all of which have the same
entirely lower predecessors and the same number of predecessors.
THEOREM 4.5. Propositions 4.1 - 4.4 are provably equivalent to the
1-consistency of SUB = ZFC + {there exists an n-subtle cardinal}_n over
RCA_0. In the case of Propositions 4.3 and 4.4 we can use EFA*, with EFA
for the forward direction.
More information about the FOM
mailing list