906: Foundations of Large Cardinals/4

[Harvey Friedman]

1. Conceptual Remarks concerning 903 - in #2
2. Second Thoughts about Elementary Extensions versus Elementary
Equivalence - #2
3. Two Universe Elementary Extension - #2
4. Two Extended Universe Restricted Elementary Extension - #3
5. Double Completion Elementary Extension - foundations of ZF - here
6. Multiple Universes Elementary Extension - next posting - #5
7. Two Universe Elementary Extension/complex - #6

5. DOUBLE COMPLETION ELEMENTARY EXTENSION - foundations of ZF

For foundations of ZF, we cannot just throw around strongly
inaccessible ranks as we did in sections 3,4,5.

Let's warm up with a comparatively easy development here before
getting into more delicate and more compelling formulations. We use
ranks V(alpha) and V(beta) which are not assumed to be strongly
inaccessible.

PROPOSITION 5.1. Some V(beta) is a proper elementary extension of some
V(alpha). As a scheme on n, it reads "some V(beta) is a proper n
quantifier elementary extension of some V(alpha)".

THEOREM 5.1. (Known) ZF proves Proposition 5.1 as a scheme. ZF with
replacement only for n quantifier formulas is provable in KP +
Proposition 5.1  as a scheme. ZF and Proposition 5.1 as a scheme are
mutually interpretable. Proposition 5.1 as a statement over KP, proves
the existence of a rank satisfying ZF. KP + there exists a strongly
inaccessible cardinal proves Proposition 5.1.

Proof: Left to the reader. QED

We now want to be minimalistic. We want to dispense with the idea of a
rank and go much more fundamental. This was the approach in 902.

Here are the obvious relevant natural conditions when one binary
relation is exploding into a bigger one.

DEFINITION 5.1. A relation is a binary relation R, where we write x R y.
fld(S) is {x: (therexists y)(x R y or y R x)). A  completion of R is a
relation S containing R, where every subset of fld(R) is the set of S
predecessors of some element of fld(S).

DEFINITION 5.2. S is an end completion of R if and only if S is a
completion of R in which every predecessor in S of an element of
fld(R) is an element of fld(R).

DEFINITION 5.3. S is an elementary completion of R if and only if S is
a completion of the relation R that is also an elementary extension of
R. S is an elementary end completion of R if and only  if S is an end
completion of the relation R that is also an elementary extension of
R.

Extensionality is also a relevant notion for us, simplifying reversals.

We view relations R as relational structures (fld(R),R). We think of x
R y as the epsilon relation in (fld(R),R).

In our first version of this, we will assume extensionality and
elementary end completion. We aim to reduce these assumptions.

DEFINITION 5.4. An ordinal is an epsilon connected transitive set
where every subset has an epsilon least element. A natural number is
an ordinal where every nonempty subset has an epsilon greatest
element.

LEMMA 5.2. (KP) Suppose R is an extensional relation with the
elementary end completion S.
i. R,S satisfy extensionality.
ii. R,S satisfy (first order) separation.
iii. R,S satisfy pairing.
iv. R,S satisfy union.
v. R,S satisfy replacement.
vi. In R,S, every element of an ordinal in is an ordinal; the ordinals
are epsilon connected. If x is an ordinal then x union {x} is an
ordinal; the union of any set of ordinals is an ordinal. Emptyset is a
natural number, every element of a natural number is a natural number,
if x is a natural number then x union {x} is a natural number.
vii. Let x in fld(S) be a natural number according to S. Then x in
fld(R) is a natural number according to R.
viii. R,S satisfy Infinity.
ix. R,S satisfy ZF\POW.

Proof: Let R be extensional with an elementary end completion S. i is
immediate since R is extensional.

For ii, let A in fld(R) and let phi be a formula with parameters
x1,...,xk in fld(R). We show that R satisfies (therexists z)(forall
y)(y in A iff phi(x1,...,xk).

We apply completion to the set {y R A: phi(x1,...,xk) holds in R}. Let
z in fld(S) be such that (forall y)(y S z iff y R A and phi(x1,...,xk)
holds in R). Then (forall y)(y S z iff y S A and phi(x1,...,xk) holds
in S) by elementary end extension.Therefore (forall y)(y in z iff y in
A and phi(x1,...,xk))  holds in S. Hence (there exists z)(forall y)(y
in z iff y in A and phi(x1,...,xk))  holds in S. By elementary
extension, (there exists z)(forall y)(y in z iff y in A and
phi(x1,...,xk))  holds in R, establishing that R satisfies separation.
By elementary extension, S satisfies separation.

For pairing, let x,y in fld(R). By completion, let z = {x,y} hold in
S. Then (therexists z)(z = {x,y}) holds in S. By elementary extension,
 (therexists z)(z = {x,y}) holds in R. Hence pairing holds in R. By
elementary extension, pairing holds in S.

For union, let A in fld(R). Apply completion to the set of all R
predecessors of R predecessors of A. We obtain z whose S predecessors
are exactly the R predecessors of R predecessors of A. By end
extension, the S predecessors of z are exactly the S predecessors of S
predecessors of A. Hence in S, there is the union of A. By elementary
extension, in R, there is the union of A. Hence R satisfies union. By
elementary extension, S satisfies union.

Suppose (forall x in A)(therexists unique y)(phi(x,y,z1,...,zk)) holds
in R with parameters z1,...,zk in fld(R). By elementary end extension,
this holds in S, with the same x in A, and the same unique y's. By
completion we can form the set of all these unique y's, all of which
lie in fld(R), into z in fld(S). By elementary extension, there exists
z' in fld(R) which also consists of these unique y's. Hence R
satisfies replacement. By elementary extension, S satisfies
replacement.

For vi, all of this is completely standard in R or in S using i-iv,
and does not involve any interaction between R and S.

For vii, let x in fld(S) be a natural number according to S. If x is
greater (contains as an element) all of the natural numbers according
to S, then using completion for the set of all natural numbers
according to S, we get a nonempty subset of x in the sense of S with
no S greatest element. This is a contradiction, and so x cannot be
greater than all of the natural numbers according to S. Hence x is a
natural number according to S, using end extension and vi.

For Infinity, apply completion to the set of all natural numbers in
the sense of R. This will give us the set of all natural numbers in
the sense of S as a point in fld(S), and therefore Infinity in S.
Hence also Infinity in R.

R,S satisfy ZF\POW by 1-viii. QED

But we have fallen short because we couldn't handle power set.
However, let us see what happens when we do TWO COMPLETIONS!

THEOREM 5.2. (KP) Suppose R is an extensional relation with the
elementary end completion S, and S with the elementary end completion
T. Then R,S,T satisfy ZF.

Proof: By Lemma 5.1, R,S,T satisfy ZF\POW. It suffices to show that R
satisfies power set. Let x in fld(R). Let A be the set of all y in
fld(S) such that y is a subset of x in the sense of S. Apply
completion to A to obtain z in fld(T) whose T predecessors are exactly
the y in fld(S) that is a subset of x in the sense of S. Since the
subsets of x in the sense of S are the same as the subsets of x in the
sense of T, it is clear that T satisfies that the power set of x
exists. By elementary extension, R satisfies that the power set of x
exists. Hence R satisfies power set. QED

We cannot use just two, R,S, in Theorem 5.2, because of the following.
Let HC be the hereditarily countable sets, and let A be a transitive
element of HC that is an elementary substructure of HC. Then HC is an
elementary end completion of A.

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

My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 905th 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-899 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

900: Ultra Convergence/2  10/3/21 12:35AM
901: Remarks on Reverse Mathematics/6  10/4/21 5:55AM
902: Mathematical L and OD/RM  10/7/21  5:13AM
903: Foundations of Large Cardinals/1
904: Foundations of Large Cardinals/2
905: Foundations of Large Cardinals/3

Harvey Friedman