[FOM] 250:Extreme Cardinals/Pi01

[Harvey Friedman]

EXTREME CARDINALS
by
Harvey M. Friedman
July 30, 2005

I2 (e.g., in Kanamori's Chart) asserts that

there exists an elementary embedding from V into a transitive class M such
that V(lambda) containedin M, where lambda is the first fixed point of j
above its critical point.

The above is stated over NBG. It is well known that there is a sentence of
set theory that is provably equivalent to I2 over NBG.

See Kanamori's 1994 book "The Higher Infinite".

1. INEXPLICITLY Pi01.

Let Q be the set of all rational numbers. For A containedin Q, we define
An<= = {x in An: x1 <= ... <= xn}.

Let F:An into A, A containedin Q. For x1,...,xn in Q, 1 <= r <= n, we write
F(x1,...,xr) for F(x1,...,xr,xr,...,xr).

Let E containedin Qn. We say that E is order invariant if and only if any
element of Qn that is of the same order type as an element of E, is itself
an element of E.

Let h:Qn into Q be partial. We say that h is order invariant if and only if
the graph of h is an order invariant subset of Qn+1.

We follow the convention that min(emptyset) = 0.

PROPOSITION 1.1. For all n >= 1 and order invariant partial h:Q2n+1 into Q,
there exists F:An into A, {0,...,n} in A containedin Q, such that for all x
in An<= and integers k > max(x),

F(x) = min{h(x,y,F(y)): y <lex x} < k.

PROPOSITION 1.2. For all n >= 2 and order invariant partial h:Q2n+1 into Q,
there exists F:An into A, 0 in A containedin Q, such that for all x in An<=
and integers k in (max(x),n],

F(x) = min{h(x,y,F(y)): y <lex x} < max(1,F(F(k,x1),...,F(k,xn))) < k.

Note that by the completeness theorem for ordinary predicate calculus with
equality, Propositions 1.1, 1.2 are provably equivalent to Pi01 sentences
over WKL0.

THEOREM 1.3. Proposition 1.1 is provable in third order arithmetic but not
in second order arithmetic. In WKL0, Proposition 1.1 implies the consistency
of second order arithmetic and follows from the consistency of third order
arithmetic. 

THEOREM 1.4. Proposition 1.2 is provable in VB + AxC + I2 but not in ZFC +
"there are arbitrarily large ranks which are nontrivially elementarily self
embeddable", assuming the latter is consistent.

THEOREM 1.5. In WKL0, Proposition 1.2 implies the consistency of ZFC +
"there are arbitrarily large ranks which are nontrivially elementarily self
embeddable". In WKL0, Proposition 1 follows from the consistency of VB + AxC
+ I2. 

The above results hold for some fixed n >= 2. Certainly n can be taken to be
quite small. Just how small will be taken up later.

2. EXPLICITLY Pi01.

Let F:Qn into Q be partial and a1,...,am be rationals, m >= 0. Define
GEN(r,F,a1,...,am) by induction on r as follows. GEN(0,F,a1,...,am) =
{a1,...,am}. GEN(i+1,F,a1,...,am) = GEN(i,F,a1,...,am) union
F[GEN(i,F,a1,...,am)n]. Here GEN stands for "generate".

PROPOSITION 2.1. For all n >= 1 and order invariant partial h:Q2n+1 into Q,
there exists finite F:An into Q, A containedin Q, such that for all x in
GEN(n,F,0,...,n)n<= and integers k > max(x),

F(x) = min{h(x,y,F(y)): y <lex x} < k.

PROPOSITION 2.2. For all n >= 2 and order invariant partial h:Q2n+1 into Q,
there exists finite F:An into Q, A containedin Q, such that for all x in
GEN(n,F,0,...,n)n<= and integers k in (max(x),n],

F(x) = min{h(x,y,F(y)): y <lex x} < max(1,F(F(k,x1),...,F(k,xn))) < k.

For Propositions 2.1, 2.2, there are obvious double exponential bounds on
the size of the required F. Since the statements are order invariant
relative to 0,...,n, we obtain a double exponential bound on the numerators
and denominators involved in some F. This gives us explicitly Pi01
sentences. 

We say that E uses numerators and denominators of magnitude at most t if and
only if E is a set of rationals whose numerators denominators in standard
reduced form are of magnitude at most the integer t.

For instance, we can state the following explicitly Pi01 forms.

PROPOSITION 2.1'.  For all n >= 1 and order invariant partial h:Q2n+1 into
Q, there exists F:An into Q, where A union rng(F) uses numerators and
denominators of magnitude at most (8n)!!, such that for all x in
GEN(n,F,0,...,n)n<= and integers k > max(x),

F(x) = min{h(x,y,F(y)): y <lex x} < k.

PROPOSITION 2.2'. For all n >= 2 and order invariant partial h:Q2n+1 into Q,
there exists F:An into Q, where A union rng(F) uses numerators and
denominators of magnitude at most (8n)!!, such that for all x in
GEN(n,F,0,...,n)n<= and integers k in (max(x),n],

F(x) = min{h(x,y,F(y)): y <lex x} < max(1,F(F(k,x1),...,F(k,xn))) < k.

THEOREM 2.3. Propositions 2.1 and 2.1' are provably equivalent in EFA
(exponential function arithmetic). Propositions 2.2 and 2.2' are provably
equivalent in EFA.

THEOREM 2.4. Proposition 2.1 are provable in third order arithmetic but not
in second order arithmetic. In EFA (exponential function arithmetic),
Proposition 2.1 implies the consistency of second order arithmetic and
follows from the consistency of third order arithmetic.

THEOREM 2.5. Proposition 2.2 is provable in VB + AxC + axiom I2 (e.g., see
Kanamori's chart) but not in ZFC + "there are arbitrarily large ranks which
are nontrivially elementarily self embeddable", assuming the latter is
consistent.

THEOREM 2.6. In EFA, Proposition 2.2 implies the consistency of ZFC + "there
are arbitrarily large ranks which are nontrivially elementarily self
embeddable". In EFA, Proposition 2.1 follows from the consistency of VB +
AxC + axiom I2. 

*************************************

I use www.math.ohio-state.edu/~friedman/ for downloadable manuscripts.
This is the 250th in a series of self contained numbered postings to
FOM covering a wide range of topics in f.o.m. The list of previous
numbered postings #1-149 can be found at
http://www.cs.nyu.edu/pipermail/fom/2005-June/008999.html in the FOM
archives, 6/15/05, 9:18PM.