[FOM] 189:Some Model theoretic Pi-0-1 statements

[Harvey Friedman]

SOME MODEL THEORETIC Pi-0-1 STATEMENTS
by
Harvey M. Friedman
September 21, 2003

We give some statements of a simple model theoretic nature, which assert the
existence of a relational structure satisfying certain conditions. The
conditions can easily be seen to be in the form of a first order theory.
Hence these sentences are provably equivalent to Pi-0-1 sentences. In fact,
they are provably equivalent to the consistency of very strong set theories.

Let R be a binary relation on a set A. A cross section of R is a set of the
form {y: R(x,y)}, for some x in A. A unique cross section of R is a set of
is of the form  {y: R(x,y)}, for some unique x in A.

PROPOSITION 1. There is a relational structure (A,R,j), where j is an
elementary embedding from (A,R) into (A,R), such that every (A,R,j)
definable set of fixed points of j is a unique cross section of R.

PROPOSITION 2. There is a relational structure (A,R,j,k), where j is an
elementary embedding from (A,R) into (A,R), k is an elementary embedding
from (A,R,j) into (A,R,j), and every (A,R,j,k) definable set of fixed points
of k is a unique cross section of R.

PROPOSITION 3. There is a relational structure (A,R,j,k), where j is an
elementary embedding from (A,R) into (A,R) whose fixed points form an
elementary substructure of (A,R), k is an elementary embedding from (A,R,j)
into (A,R,j), and every (A,R,j,k) definable set of fixed points of k is a
unique cross section of R.

THEOREM 4. Proposition 1 is provably equivalent, over ACA, to the
consistency of ZF + {there exists an elementary embedding j:V(alpha) into
V(beta) with critical point kappa such that j^n(kappa) < alpha}_n. By work
of Woodin, we can replace ZF with ZFC.

THEOREM 5. Proposition 2 implies, over ACA, the consistency of ZF + there
exists a nontrivial elementary embedding from some V(alpha) into V(alpha),
where alpha is an inaccessible cardinal (and more). By work of Woodin, the
latter implies the consistency of ZFC + there exists a nontrivial elementary
embedding from some V(alpha) into V(alpha).

THEOREM 6. Proposition 3 implies, over ACA, ZF + there exists a nontrivial
elementary embedding from some V(alpha) into V(alpha), where V(critical
point) is an elementary substructure of V(alpha). By work of Woodin, the
latter implies the consistency of MKC + there exists a nontrivial elementary
embedding from some L(V(alpha+1)) into L(V(alpha+1)).

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

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 188th 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/2003-May/006563.html  in the FOM
archives, 5/8/03 8:46AM. Previous ones counting from #150 are:

150:Finite obstruction/statistics  8:55AM  6/1/02
151:Finite forms by bounding  4:35AM  6/5/02
152:sin  10:35PM  6/8/02
153:Large cardinals as general algebra  1:21PM  6/17/02
154:Orderings on theories  5:28AM  6/25/02
155:A way out  8/13/02  6:56PM
156:Societies  8/13/02  6:56PM
157:Finite Societies  8/13/02  6:56PM
158:Sentential Reflection  3/31/03  12:17AM
159.Elemental Sentential Reflection  3/31/03  12:17AM
160.Similar Subclasses  3/31/03  12:17AM
161:Restrictions and Extensions  3/31/03  12:18AM
162:Two Quantifier Blocks  3/31/03  12:28PM
163:Ouch!  4/20/03  3:08AM
164:Foundations with (almost) no axioms, 4/22/0  5:31PM
165:Incompleteness Reformulated  4/29/03  1:42PM
166:Clean Godel Incompleteness  5/6/03  11:06AM
167:Incompleteness Reformulated/More  5/6/03  11:57AM
168:Incompleteness Reformulated/Again 5/8/03  12:30PM
169:New PA Independence  5:11PM  8:35PM
170:New Borel Independence  5/18/03  11:53PM
171:Coordinate Free Borel Statements  5/22/03  2:27PM
172:Ordered Fields/Countable DST/PD/Large Cardinals  5/34/03  1:55AM
173:Borel/DST/PD  5/25/03  2:11AM
174:Directly Honest Second Incompleteness  6/3/03  1:39PM
175:Maximal Principle/Hilbert's Program  6/8/03  11:59PM
176:Count Arithmetic  6/10/03  8:54AM
177:Strict Reverse Mathematics 1  6/10/03  8:27PM
178:Diophantine Shift Sequences  6/14/03  6:34PM
179:Polynomial Shift Sequences/Correction  6/15/03  2:24PM
180:Provable Functions of PA  6/16/03  12:42AM
181:Strict Reverse Mathematics 2:06/19/03  2:06AM
182:Ideas in Proof Checking 1  6/21/03 10:50PM
183:Ideas in Proof Checking 2  6/22/03  5:48PM
184:Ideas in Proof Checking 3  6/23/03  5:58PM
185:Ideas in Proof Checking 4  6/25/03  3:25AM
186:Grand Unification 1  7/2/03  10:39AM
187:Grand Unification 2 - saving human lives 7/2/03 10:39AM
188:Applications of Hilbert's 10-th 7/6/03  4:43AM