FOM: 18:Binary Functions and Large Cardinals

[Harvey Friedman]

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

A complete archiving of fom, message by message, is available at
http://www.math.psu.edu/simpson/fom/
Also, my series of positive postings (only) is archived at
http://www.math.ohio-state.edu/foundations/manuscripts.html

*Note the omission of the word "positive," in light of the fact that the
fom list has cooled down for the time being.

I first want to make two corrections to 17:Very Strong Borel statements.

1. A_x = {y in S^k-1: (x,y) in X} should be A_x = {y in X^k-1: (x,y) in A}.
2. "It is necessary and sufficient to use uncountably many Woodin cardinals
in order to prove Proposition B" should be "It is necessary and sufficient
to use infinitely many Woodin cardinals in order to prove Proposition B,"
in the sense that I stated later.

Let F:Q^2 into Q, where Q is the rationals. An F-Boolean relation is a
relation of several variables on Q which is defined by a quantifier free
formula in the structure (Q,<,F), with parameters allowed.

A cross section of F is a function F_x:Q into Q given by F_x(y) = F(x,y). A
semi cross section of F is a function G:Q into Q where for all x in Q there
exists y in Q such that G and F_y agree strictly below x.

Let R be a k-ary relation on Q. We write fld(R) for the set of all
coordinates of elements of R. We say that R is unbounded if and only if
fld(R) has arbitrarily large elements. An embedding of R is a one-one h:Q
into Q such that

	i) for all x_1,...,x_n in fld(R), R(x_1,...,x_n) iff
R(h(x_1),...,h(x_n));
	ii) for all x notin fld(R), h(x) = 0.

Let f:Q into Q. Following terminology from set theory, we say that x is a
critical point of f if and only if f is the identity below x and f(x) > x.
We say that x is a sharp critical point of f if and only if x is a critical
point of f and the iterates of f at x go to infinity.

PROPOSITION A. There exists F:Q^2 into Q such that every F-Boolean relation
has a semi cross sectional embedding with a sharp critical point.

THEOREM. Proposition A is provably equivalent to the consistency of ZFC +
{there exists a k-huge cardinal}_k, within RCA_0 + WKL.

We can strengthen Proposition A so that it goes beyond even ZF + j:V into V.

PROPOSITION B. There exists F:Q^2 into Q such that for all F-Boolean
relations have two semi cross sectional embeddings g,h, where the sharp
critical point of g is a fixed point of h that is greater than the critical
point of h.

THEOREM. Proposition B implies the consistency of ZF + there exists an
elementary embedding from V into V, within RCA_0. In fact, it is provably
equivalent to the consistency of ZF + an appropriate technical large
cardinal hypothesis believed to be consistent.