[FOM] 281:Linear Self Embedding Axioms

Fri May 5 02:32:30 EDT 2006

Here we continue to refine the self embedding axiom discussed in
http://www.cs.nyu.edu/pipermail/fom/2006-May/010492.html

The results here grew out of the results claimed in

[1] `Combinatorial set theoretic statements of great logical strength',
1995, 4 pages, abstract.

at http://www.math.ohio-state.edu/%7Efriedman/ paper 2 under downloadable
manuscripts.

LSEA (linear self embedding axiom) is a candidate for the mathematically
cleanest statement corresponding to the extreme end of the large cardinal
hypotheses over ZFC. It is naturally formulated over ZC.

###########################

Over NBGC = NBG plus global choice, we state

ORDINAL SELF EMBEDDING AXIOM (class). Every binary relation with field On
has a self embeddable initial segment.

Over ZFC, we state

ORDINAL SELF EMBEDDING AXIOM (set). Every binary relation whose field is a
sufficiently large ordinal, has a self embeddable initial segment.

Before continuing, we clarify any ambiguities in these two statements.

In class theory, a binary relation is a class of ordered pairs. In set
theory, a binary relation is a set of ordered pairs. The field of a binary
relation is the class of all coordinates of its elements.

Let R be a binary relation whose field is a class, which is also given a
linear ordering. This includes the case where the field is On or an ordinal.
An initial segment of R is the restriction of R to some subclass A of its
domain which is downward closed. Thus initial segments of R are also binary
relations whose field is a set with a linear ordering.

Note that intiial segments may or may not be proper.

Let R be a binary relation. A self embedding of R is a one-one function
h:fld(R) into fld(R) such that

R(x,y) implies R(hx,hy).

A stronger notion is that

R(x,y) iff R(hx,hy), and
x < y iff hx < hy.

We say that R is self embeddable if and only if R has a self embedding that
is not the identity. A stronger notion is that R has a self embedding whose
range is a proper subclass of fld(R).

The three statements above use the weakest versions of the relevant notions.
We can give sharpened versions as follows.

ORDINAL SELF EMBEDDING AXIOM' (class). Every binary relation with field On
has a self embeddable proper initial segment. (The self embedding uses iff
with < as above, and its range is a proper subset of the field).

ORDINAL SELF EMBEDDING AXIOM' (set). Every binary relation whose field is a
sufficiently large ordinal, has a self embeddable proper initial segment.
(The self embedding uses iff with < as above, and its range is a proper
subset of the field).

Here is essentially the results from [1], going back to 1995.

LCA1. There is a nontrivial elementary embedding of
V ® M such that V(a) Í M, where a is the first
fixed point above the critical point.

LCA2. There is a nontrivial elementary embedding of some V(kappa) into
itself.

Yet stronger than LCA1 is

LCA3. There is a nontrivial elementary embedding of some V(kappa + 1) into
itself.

THEOREM 1. In NBGC, OSEA (class), OSEA' (class) follow from LCA1 and imply
LCA2. In ZFC, ODEA (set), OSEA' (set) follow from LCA1 and imply LCA2.

In order to make the axioms more mathematically natural, it is best to use a
linear ordering rather than the ordinals.

The idea of stating axioms in the form:

there exists a linear ordering obeying a natural combinatorial property

was already well exploited in my paper

[2] Subtle Cardinals and Linear Orderings, Annals of Pure and Applied
Logic 107 (2001), 1-34.

There is much more to do along these lines.

Over ZC (Zermelo set theory with choice) we state

LINEAR SELF EMBEDDING AXIOM (lsea). There is a linear ordering (X,<) such
that every f:X^2 into X has a self embeddable initial segment.

Here an initial segment of f:X^2 into X is a restriction f:Y^2 into Y, where
Y is a subset of X that is downward closed. We say that h is a self
embedding of f:Y^2 into Y if and only if h is a one-one map from Y into Y,
where

f(x,y) = z implies f(hx,hy) = hz.

A stronger notion is obtained by requiring that

x < y iff hx < hy.

We say that f:Y into Y is self embeddable if and only if f has a self
embedding that is not the identity.

A stronger notion is obtained by requiring that the range of f is a proper
subset of Y.

We can sharpen this as follows.

LINEAR SELF EMBEDDING AXIOM' (lsea). There is a linear ordering (X,<) such
that every f:X^2 into X has a self embeddable proper initial segment. (The
self embedding uses iff with < as above, and its range is a proper subset of
its field).

THEOREM 2. In ZFC, LSEA, LSEA' follow from LCA1 and imply LCA2. ZC + LSEA,
ZC + LSEA interpret LCA2 and are interpretable in LCA1. The interpretations
are "set theoretically good".

Of course, we can also use binary functions for OSEA (set), OSEA' (set),
OSEA (class), OSEA' (class), with the same results.

The proofs show that the least cardinality of such a linear ordering is much
greater than the least kappa with an elementary embedding from V(kappa) into
V(kappa), and much smaller than any critical point of a j according to LCA1.

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

I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 281st 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-249 can be found at
http://www.cs.nyu.edu/pipermail/fom/2005-June/008999.html in the FOM
archives, 6/15/05, 9:18PM. NOTE: The title of #269 has been corrected from
the original.

250. Extreme Cardinals/Pi01  7/31/05  8:34PM
251. Embedding Axioms  8/1/05  10:40AM
252. Pi01 Revisited  10/25/05  10:35PM
253. Pi01 Progress  10/26/05  6:32AM
254. Pi01 Progress/more  11/10/05  4:37AM
255. Controlling Pi01  11/12  5:10PM
256. NAME:finite inclusion theory  11/21/05  2:34AM
257. FIT/more  11/22/05  5:34AM
258. Pi01/Simplification/Restatement  11/27/05  2:12AM
259. Pi01 pointer  11/30/05  10:36AM
260. Pi01/simplification  12/3/05  3:11PM
261. Pi01/nicer  12/5/05  2:26AM
262. Correction/Restatement  12/9/05  10:13AM
263. Pi01/digraphs 1  1/13/06  1:11AM
264. Pi01/digraphs 2  1/27/06  11:34AM
265. Pi01/digraphs 2/more  1/28/06  2:46PM
266. Pi01/digraphs/unifying 2/4/06  5:27AM
267. Pi01/digraphs/progress  2/8/06  2:44AM
268. Finite to Infinite 1  2/22/06  9:01AM
269. Pi01,Pi00/digraphs  2/25/06  3:09AM
270. Finite to Infinite/Restatement  2/25/06  8:25PM
271. Clarification of Smith Article  3/22/06  5:58PM
272. Sigma01/optimal  3/24/06  1:45PM
273: Sigma01/optimal/size  3/28/06  12:57PM
274: Subcubic Graph Numbers  4/1/06  11:23AM
275: Kruskal Theorem/Impredicativity  4/2/06  12:16PM
276: Higman/Kruskal/impredicativity  4/4/06  6:31AM
277: Strict Predicativity  4/5/06  1:58PM
278: Ultra/Strict/Predicativity/Higman  4/8/06  1:33AM
279: Subcubic graph numbers/restated  4/8/06  3:14AN
280: Generating large caridnals/self embedding axioms  5/2/06  4:55AM

Harvey Friedman