FOM: 114:Borel Functions on HC

[Harvey Friedman]

Borel Functions on HC
by
Harvey M. Friedman
January 1, 2002

It is unexpectedly simple to give necessary uses of large large cardinals
in the hereditarily countable sets. The consequences are Pi-1-3. In order
to prove that they hold in the constructible universe, it is still
necessary to use large large cardinals.

Let HC be the set of all hereditarily countable sets - i.e., sets whose
transitive closure is countable. There is a standard notion of code for an
element of HC, and the set of codes is a Pi-1-1 subset of Baire space. We
say that F:HC into HC is a Borel function if and only if there is a Borel
function h from Baire space into itself such that if x is a code for A in
HC then h(x) is a code for F(A).

Two sets A,B are said to be isomorphic if and only if there is a one-one
function h from A onto B such that for all x,y in A, x in y if and only if
hx in hy.

Below, "includes" means "includes under inclusion", and "contains" means
"contains as an element".

PROPOSITION 1. For every rank preserving Borel function F:HC into HC, some
A in HC includes a proper subset of F(A) isomorphic to F(A).

PROPOSITION 2. For every rank preserving Borel function F:HC into HC, some
A in HC of successor rank includes a proper subset F(A) isomorphic to F(A).

PROPOSITION 3. For every rank preserving Borel function F:HC into HC, some
A in HC of rank some alpha + 2 includes a proper subset F(A) isomorphic to
F(A).

PROPOSITION 4. For every rank preserving Borel function F:HC into HC, some
A in HC of rank some alpha + alpha includes a proper subset F(A) isomorphic
to F(A).

PROPOSITIONS 1',2',3',4'. Replace "contains a ..." with "includes F(A) and
a ...".

PROPOSITION 5. For every rank preserving Borel function F:HC into HC, some
A in HC includes a proper subset B of F(A) isomorphic to F(A)  and a proper
subset C of F(B) isormorphic to F(B).

PROPOSITION 5'. For every rank preserving Borel function F:HC into HC, some
A in HC includes F(A), a proper subset B of F(A) isomorphic to F(A), and a
proper subset C of F(B) isomorphic to F(B).

PROPOSITION 6. For every rank preserving Borel function F:HC into HC, some
A in HC of successor rank contains proper isomorphic subsets of each
element of F(A) of rank rk(A)-1.

THEOREM 7. Proposition 1 is provable in ZF + "there is a nontrivial
elementary embedding from a rank into itself". Proposition 1 implies the
existence of a countable transitive model of ZF + "there exists alpha such
that for all n, alpha is the critical point of an elementary embedding from
a rank into another rank whose n-th iterate at alpha exists" and somewhat
more, over ZF\P. Using Woodin's work on getting models with choice from
models without choice in the context of large cardinals, we obtain:
Proposition 1 implies the existence of a countable transitive model of ZFC
+ "there exists alpha such that for all n, alpha is n-huge".

THEOREM 8. Proposition 2 is provable in ZF + "there is a nontrivial
elementary embedding from some V(alpha + 1) into V(alpha + 1)". Proposition
2 proves the existence of a countable transitive model of ZF + "there is a
nontrivial elementary embedding from some V(alpha) into V(alpha)" over
ZF\P.

THEOREM 9. Proposition 3 is provable in ZF + "there is a nontrivial
elementary embedding from some V(alpha + 2) into V(alpha + 2)". Proposition
3 proves the existence of a countable transitive model of ZF + "there is a
nontrivial elementary embedding from some V(alpha +1) into V(alpha +1)"
over ZF\P.

THEOREM 10. Proposition 4 is provable in ZF + "there is a nontrivial
elementary embedding from some V(alpha + alpha) into V(alpha + alpha)" over
ZF\P. Proposition 4 proves the existence of a countable transitive model of
"there exists alpha such that for all beta < alpha, there is a nontrivial
elementary embedding from V(alpha + beta) into V(alpha + beta)" over ZF\P.

THEOREM 11. Proposition 5 is provable in ZF + "there is a nontrivial
elementary embedding j from some V(alpha) into V(alpha) and a nontrivial
elementary embedding j' from (V(alpha),j) into (V(alphaa),j)" over ZF\P.
Proposition 5 proves the existence of a countable transitive model of VB +
"there exists a nontrivial elementary embedding from V into V" over ZF\P.

THEOREM 12. Proposition 6 is provable in ZF + "there exists a strongly
inaccessible rank V(alpha) such that every transitive set of rank alpha has
a nontrivial elementary embedding into itself". Proposition 6 proves the
existence of a countable transitive model of VB + "every transitive proper
class has a nontrivial elementary embedding into itself" over ZF\P.

THEOREM 13. Propositions 1,2,3,4,5 are equivalent to Propositions
1',2',3',4',5' over ZF\P.

THEOREM 14. All Propositions here are Pi-1-3. The results hold even if the
Propositions are relativized to the constructible universe.

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

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.

This is the 114th in a series of self contained postings to FOM covering
a wide range of topics in f.o.m. Previous ones counting from #100 are:

100:Boolean Relation Theory IV corrected  3/21/01  11:29AM
101:Turing Degrees/1  4/2/01  3:32AM
102: Turing Degrees/2  4/8/01  5:20PM
103:Hilbert's Program for Consistency Proofs/1 4/11/01  11:10AM
104:Turing Degrees/3   4/12/01  3:19PM
105:Turing Degrees/4   4/26/01  7:44PM
106.Degenerative Cloning  5/4/01  10:57AM
107:Automated Proof Checking  5/25/01  4:32AM
108:Finite Boolean Relation Theory   9/18/01  12:20PM
109:Natural Nonrecursive Sets  9/26/01  4:41PM
110:Communicating Minds I  12/19/01  1:27PM
111:Communicating Minds II  12/22/01  8:28AM
112:Communicating MInds III   12/23/01  8:11PM
113:Coloring Integers