Initial segments of Rudin-Frolík order

Masahiko Murakami

                        muramasa@ms.u-tokyo.ac.jp

Department of Mathematics, Hosei University

Abstract

The Rudin-Frolík order is originally defined on β (ω) [3, 7]. We defined Rudin-Frolík order on the ultrafilters of the complete Boolean algebras [5]. It is well-known that an initial segment of Rudin-Frolík order on β (ω) is totally ordered. The main theorem is Theorem 1.1. When the complete Boolean algebra satisfies countably chain condition (ccc), an initial segment of Rudin-Frolík order is totally ordered.

1 Rudin-Frolík order

Definition 1.1 (Rudin-Frolík order). Let p be an ultrafilter of a complete Boolean algebra 𝒜 and let q be an ultrafilter of a complete Boolean algebra ℬ. The Rudin-Frolík order ⊑ is the binary relation, which is given by p ⊑ q, if there are a ∈ p, b ∈ q, a complete homomorphism h: 𝒜 → ℬ↾b and a homomorphism f: ℬ → 𝒜↾a such that f ∘ h(x) = x for all x ∈ 𝒜↾a and f^{−1}“ p = q.

Precisely saying, Rudin-Frolík order is preorder, which dose not satisfy anti-symmetric law. We consider the equivalence class, the equivalence relation is defined by p ⊑ q ∧ q ⊑ p, implicitly.

Theorem 1.1. Let q be an ultrafilter of a complete Boolean algebra ℬ with countably chain condition (ccc). Let p_{1} be an ultrafilter of a complete Boolean algebra 𝒜_{1} and let p_{2} be an ultrafilter of a complete Boolean algebra 𝒜_{2}. If p_{1} ⊑ q and p_{2} ⊑ q, then p_{1} ⊑ p_{2} or p_{2} ⊑ p_{1}.

2 Nonstandard universes

Given a set X, we define the iterated power set V_{n}(X) over X recursively by V_{0}(X) = X and V_{n+1}(X) = V_{n}(X) ∪ 𝒫(V_{n}(X)). The superstructure V (X) is the union ⋃_{n<ω} V_{n}(X). The set X is said to be a base set if ∅ ∉ X and each element of X is disjoint from V (X). From now on, we reserve the letter X for infinite base set. In a substructure W of a superstructure V (X), the elements of W \ X are called sets relative to W. We denote the model ⟨V (X), ∈⟩ for the language ℒ_{∈} = {∈} of set theory by the same symbol V (X). A Δ_{0}-formula of ℒ_{∈} is a formula obtained from atomic formulae using connectives and bounded quantifiers such as ∀x ∈ y and ∃x ∈ y. Let 𝔐 = ⟨M, ϵ_{M}⟩ and 𝔑 = ⟨N, ϵ_{N}⟩ be models for ℒ_{∈}. We say that 𝔐 is a bounded elementary submodel of 𝔑 if 𝔐 is a submodel of 𝔑 and for any Δ_{0}-formula φ(x_{1}, …, x_{n}) of ℒ_{∈} and for any a_{1}, …, a_{n} ∈ M, 𝔐 ⊧ φ(a_{1}, …, a_{n}) if and only if 𝔑 ⊧ φ(a_{1}, …, a_{n}). A map e: M → N is said to be a bounded elementary embedding of 𝔐 into 𝔑 if e is an isomorphic embedding of 𝔑 onto a bounded elementary submodel of 𝔐.

A nonstandard universe is a triple ⟨V (X), V (Y), ⋆⟩ such that:

(1) X and Y are infinite base sets.

(2) (Transfer Principle) The map ⋆ is a bounded elementary embedding of V (X) into V (Y).

(3) ^{⋆}X = Y.

(4) For every infinite subset of A of X, {^{⋆}a | a ∈ A} is a proper subset of ^{⋆}A.

Ignoring the condition (4), we call the triple a pre-nonstandard universe. By the condition (3), we can denote by ⟨V (X), V (^{⋆}X), ⋆⟩ a pre-nonstandard universe.

We call an element a ∈ V (^{⋆}X) standard if there is an x ∈ V (X) such that a = ^{⋆}x. We call an element a ∈ V (^{⋆}X) internal if there is an x ∈ V (X) such that a ∈ ^{⋆}x. We denote by V (X)^{⋆} the set of all internal elements in V (^{⋆}X). The model V (X)^{⋆} is a transitive submodel of V (^{⋆}X). Then, we can simply denote by single V (X)^{⋆} pre-nonstandard universe. The norm (of standardness) nos(a) of an internal element a is a cardinal defined by

nos(a) = min {|x| | a ∈ ^{⋆}x}.

The radius of V (X)^{⋆} is a cardinal defined by

rad( V (X)^{⋆}) = min {κ | ∀y ∈ V (X)^{⋆} nos(y) < κ}.

We call an element of V (^{⋆}X) external if it is not internal. For the general theory of nonstandard universes, we refer to [1].

Definition 2.1 (Standardizable bounded elementary embedding). Let ⋆V (X) and ^{▲ ▼}V (X) be pre-nonstandard universes. A bounded elementary embedding e: ^{⋆}V (X) → ^{▲ ▼}V (X) is standardizable if e^{−1}“ y ∈ ^{⋆}V (X) for any set y relative to ^{▲ ▼}V (X). We call e^{−1}“ y the standardization of y by e if e^{−1}“ y ∈ ^{⋆}V (X).

Definition 2.2 (End extension). Let ⟨N, <⟩ be a structure inside V (X) which is isomorphic to ⟨ω, <⟩. A bounded elementary embedding e: ^{⋆}V (X) → ^{▲ ▼}V (X) is an end extension if {e(x) | x < ν} = {y | y < e(ν)} for any ν ∈ ^{⋆}N.

Lemma 2.1. A standardizable bounded elementary embedding of pre-nonstandard universe is an end extension.

Proof. Easy.

3 Boolean valued superstructures

Definition 3.1 (Bounded Boolean ultrapower). Let 𝒜 be a complete Boolean algebra. We denote

V̂(X)^{⟨𝒜⟩} = \{ u: V (X) → 𝒜 | \begin{matrix}u(x) ∧ u(y) = 0 for x ≠ y, \\ ⋁ u“ V_{n}(X) = 1 for some n < ω \end{matrix} \} .

Let p be an ultrafilter of 𝒜. The bounded Boolean ultrapower V̂(X)^{⟨𝒜⟩} /p modulo p of 𝒜 is the set of equivalence class by p with the membership relation.

We can regard a bounded Boolean ultrapower as a pre-nonstandard universe by Mostowski collapsing. The bounded elementary embedding of V (X) into V̂(X)^{⟨𝒜⟩} /p is given by x̌/p where x̌ = V (X) × {1_{𝒜} }.

Definition 3.2 (Bounded ultrasheaf). Let 𝒜 be a complete Boolean algebra. We denote

V_{0}(X)^{(𝒜)} = {u: ⋃ X → 𝒜 | ⋁_{x∈X}(⋁ u“ x ∧ ¬ ⋀ u“ (⋃ X \ x)) = 1},
V_{n+1}(X)^{(𝒜)} = { u | dom u ⊆ V_{n}(X), rng u ⊆ 𝒜 } ,
V̂(X)^{(𝒜)} = ⋃_{n<ω} V_{n}(X)^{(𝒜)} .

Then V̂(X)^{(𝒜)} is equipped with 𝒜-valued membership relation. Let p be an ultrafilter of 𝒜. The bounded Boolean ultrasheaf V̂(X)^{(𝒜)} /p modulo p of 𝒜 is the set of equivalence class by p with the membership relation.

We can regard a bounded ultrasheaf as a pre-nonstandard universe by Mostowski collapsing. Then we can regard the bounded Boolean ultrapower V̂(X)^{⟨𝒜⟩} /p is a substructure of the bounded ultrasheaf V̂(X)^{(𝒜)} /p. For the general theory of bounded ultrasheaves, we refer to [6].

Bounded Boolean ultrapower is constructed by equivalence relation “=”. As the Boolean valued universe V^{(ℬ)} of set theory, bounded ultrasheaf is constructed by membership relation “∈”. Membership relation “∈” is stronger than equivalence relation “=”.

Definition 3.3 (Standardizable bounded elementary embedding of ultrasheaves). Let V̂(X)^{(𝒜)} /p and V̂(X)^{(ℬ)} /q be ultrasheaves. A bounded elementary embedding e: V̂(X)^{(𝒜)} /p → V̂(X)^{(ℬ)} /q is standardizable if e^{−1}“ y ∈ V̂(X)^{(𝒜)} /p for any set y relative to V̂(X)^{(ℬ)} /q. We call e^{−1}“ y the standardization of y by e if e^{−1}“ y ∈ V̂(X)^{(𝒜)} /p.

Theorem 3.1 (Characterization theorem of the Rudin-Frolík order [5]). Let p be an ultrafilter of a complete Boolean algebra 𝒜 and let q be an ultrafilter of a complete Boolean algebra ℬ. Suppose 𝒜, ℬ ∈ V (X) \ X. Then, p ⊑ q if and only if there is a standardizable bounded elementary embedding e: V̂(X)^{(𝒜)} /p → V̂(X)^{(ℬ)} /q of ultrasheaves.

Proof. See [5, Theorem 5.3].

Lemma 3.2. Let e: V̂(X)^{(𝒜)} /p → V̂(X)^{(ℬ)} /q be a standardizable bounded elementary embedding. Then e↾V̂(X)^{⟨𝒜⟩} /p is an end extension.

Proof. As easy as that of Lemma 2.1.

Theorem 3.3. Let e_{0} : V̂(X)^{⟨𝒜⟩} /p → V̂(X)^{⟨ℬ⟩} /q be a bounded elementary embedding. Suppose |𝒜|, |ℬ| < |V (X)| = ℶ_{ω}(|X|), then e_{0} can be extended to a unique bounded elementary embedding e: V̂(X)^{(𝒜)} /p → V̂(X)^{(ℬ)} /q of ultrasheaves.

I am sorry to omit the proof of the theorem above, because it is not enough space to state it — it costs at least 12 pages. The theorem seems to be deep, which suggests that every pre-nonstandard universe has the generic extension a priori. If you are interested in the theorem, please email me.

4 Proof of Theorem 1.1

Lemma 4.1. Let ℬ be a complete Boolean algebra with ccc. Let p be an ultrafilter of a complete Boolean algebra 𝒜 and let q be an ultrafilter of ℬ. Suppose p ⊑ q. Then there is a ∈ p such that 𝒜↾a satisfies ccc.

Proof. Choose a ∈ p, b ∈ q, a complete homomorphism h: 𝒜 → ℬ↾b and an epimorphism f: ℬ → 𝒜↾a satisfying that f ∘ h(x) = x for all x ∈ 𝒜↾a and f^{−1}“ p = q. Let P be a partition of unity of 𝒜↾a. Since h“ P is a partition of unity of ℬ, we have |P | ≤ ℵ_{0}.

Lemma 4.2. Let 𝒜 be a complete Boolean algebra with ccc and let p be an ultrafilter of 𝒜. Then the radius of the bounded Boolean ultrapower is at most ℵ_{1}.

Proof. For u/p ∈ V̂(X)^{⟨𝒜⟩} , put I = {x ∈ V (X) | u(x) ≠ 0_{𝒜} }, then I is a set relative to V (X). Since u“ I is a partition of unity of 𝒜, |I| is at most countable. Then [[u ∈ Ǐ]] = 1_{𝒜} ∈ p. Thus u/p is an element of Ǐ/p where |I| is at most countable.

Lemma 4.3. Let ^{⋆^{1}}V (X) and ^{⋆^{2}}V (X) be pre-nonstandard universes with the radii at most ℵ_{1}. Let e_{1} : ^{⋆^{1}}V (X) → ^{▲ ▼}V (X) and e_{2} : ^{⋆^{2}}V (X) → ^{▲ ▼}V (X) be end extensions. Then either rng e_{1} ⊆ rng e_{2} or rng e_{2} ⊆ rng e_{1}. When rng e_{1} ⊆ rng e_{2}, there is a bounded elementary embedding e_{0} : ^{⋆^{1}}V (X) → ^{⋆^{2}}V (X) such that e_{1} = e_{2} ∘ e_{0}. When rng e_{2} ⊆ rng e_{1}, there is a bounded elementary embedding e_{0} : ^{⋆^{2}}V (X) → ⋆^{1}V (X) such that e_{2} = e_{1} ∘ e_{0}.

\begin{matrix}▲ \\ ▼ \end{matrix}V (X)^{⋆_{1}}V (X)_{e_{1}}  _{e_{0}} or  ^{⋆_{1}}V (X)_{e_{2}}_{e_{0}}  .

Proof. Let ⟨N, <⟩ be a structure inside V (X) which is isomorphic to ⟨ω, <⟩. Since e_{1} and e_{2} are end extensions, we have either e_{1}“^{⋆^{1}}N ⊆ e_{2}“^{⋆^{2}}N or e_{2}“^{⋆^{2}}N ⊆ e_{1}“^{⋆^{1}}N. Suppose e_{1}“^{⋆^{1}}N ⊆ e_{2}“^{⋆^{2}}N. We shall show rng e_{1} ⊆ rng e_{2}. Let a ∈ ^{⋆^{1}}V (X). Since the radius of ^{⋆^{1}}V (X) is at most ℵ_{1}, there is a countable set I relative to V (X) such that a ∈ ^{⋆^{1}}I. Let ã: N → I be a bijection. Note that ã ∈ V (X) and that ⋆^{1}ã: ^{⋆^{1}}N → ^{⋆^{1}}I is a bijection. Then there are ν_{1} ∈ ^{⋆^{1}}N and ν_{2} ∈ ^{⋆^{2}}N such that a = (^{⋆^{1}}ã)(ν_{1}) and e_{1}(ν_{1}) = e_{2}(ν_{2}). We obtain that e_{1}(a) = e_{2}((^{⋆^{2}}ã)(ν_{2})). In fact, since e_{1}(^{⋆^{1}}ã) = e_{2}(^{⋆^{2}}ã) and e_{1}(ν_{1}) = e_{2}(ν_{2}), we have

(e_{1}(^{⋆^{1}}ã))(e_{1}(ν_{1})) = (e_{2}(^{⋆^{2}}ã))(e_{2}(ν_{2})),
e_{1}(a) = e_{1}((^{⋆^{1}}ã)(ν_{1})) = e_{2}((^{⋆^{2}}ã)(ν_{2})).

Thus we have obtained that rng e_{1} ⊆ rng e_{2}. Now we can define the map e_{0} : ^{⋆^{1}}V (X) → ^{⋆^{2}}V (X) such that e_{1} = e_{2} ∘ e_{0}. Let φ(x_{1}, …, x_{n}) be a Δ_{0}-formula of ℒ_{∈}, and let a_{1}, …, a_{n} ∈ ^{⋆^{1}}V (X). Since both e_{1} and e_{2} are bounded elementary embeddings, we get

▲ ▼V (X) ⊧ φ(e_{1}(a_{1}), …, e_{1}(a_{n})) ⟺ ^{▲ ▼}V (X) ⊧ φ(e_{2}(e_{0}(a_{1})), …, e_{2}(e_{0}(a_{n}))),
⋆^{1}V (X) ⊧ φ(a_{1}, …, a_{n}) ⟺ ^{⋆^{2}}V (X) ⊧ φ(e_{0}(a_{1}), …, e_{0}(a_{n})).

Thus we e_{0} is a bounded elementary embedding. Exchanging ⋆_{1} for ⋆_{2}, we have the proof in case e_{2}“^{⋆^{2}}N ⊆ e_{1}“^{⋆^{1}}N.

Proof of Theorem 1.1. From Lemma 4.1, we can assume both 𝒜_{1} and 𝒜_{2} satisfy ccc. Choose a base set X such that 𝒜_{1}, 𝒜_{2}, ℬ ∈ V (X) \ X. By the characterization theorem of the Rudin-Frolík order, there are standardizable bounded elementary embeddings of ultrasheaves e_{1} : V̂(X)^{(𝒜_{1})} /p_{1} → V̂(X)^{(ℬ)} /q and e_{2} : V̂(X)^{(𝒜_{2})} /p_{2} → V̂(X)^{(ℬ)} /q. Then, from Lemma 3.2, both e_{1}↾V̂(X)^{⟨𝒜_{1}⟩} /p_{1} and e_{2}↾V̂(X)^{⟨𝒜_{2}⟩} /p_{2} are end extensions.

V̂(X)^{(ℬ)} /q V̂(X)^{(𝒜_{1})} /p_{1}_{e_{1}}  V̂(X)^{(𝒜_{2})} /p_{2}_{e_{2}}  ⟶^{restriction}  V̂(X)^{⟨ℬ⟩} /q V̂(X)^{⟨𝒜_{1}⟩} /p_{1}  _{e_{0}} or V̂(X)^{⟨𝒜_{2}⟩} /p_{2}_{e_{0}}  .

Since both 𝒜_{1} and 𝒜_{2} satisfy ccc, the radii of the bounded Boolean ultrapowers V̂(X)^{⟨𝒜_{1}⟩} /p_{1} and V̂(X)^{⟨𝒜_{2}⟩} /p_{2} are at most ℵ_{1} by Lemma 4.2. Then, from Lemma 4.3, there is a bounded elementary embedding e_{0} : V̂(X)^{⟨𝒜_{1}⟩} /p_{1} → V̂(X)^{⟨𝒜_{2}⟩} /p_{2} or e_{0} : V̂(X)^{⟨𝒜_{2}⟩} /p_{2} → V̂(X)^{⟨𝒜_{1}⟩} /p_{1} that makes the diagram above commute. Suppose that there is e_{0} : V̂(X)^{⟨𝒜_{1}⟩} /p_{1} → V̂(X)^{⟨𝒜_{2}⟩} /p_{2} such that e_{1} = e_{2} ∘ e_{0}. From Theorem 3.3, let e: V̂(X)^{(𝒜_{1})} /p_{1} → V̂(X)^{(𝒜_{2})} /p_{2} be a unique extension of e_{0}. Since e_{2} ∘ e is a bounded elementary embedding of ultrasheaves, e_{2} ∘ e must coincide with e_{1}.

V̂(X)^{⟨ℬ⟩} /q V̂(X)^{⟨𝒜_{1}⟩} /p_{1} _{e_{0}} V̂(X)^{⟨𝒜_{2}⟩} /p_{2} ⟶^{extension}  V̂(X)^{(ℬ)} /q V̂(X)^{(𝒜_{1})} /p_{1}_{e_{1}}  _{e}  V̂(X)^{(𝒜_{2})} /p_{2}_{e_{2}}  .

Then e is standardizable. In fact, let y be a set relative to V̂(X)^{(𝒜_{2})} /p_{2} and let s ∈ V̂(X)^{(𝒜_{1})} /p_{1} be the standardization of e_{2}(y) by e_{1}. We have that, for any x ∈ V̂(X)^{(𝒜_{1})} /p_{1},

e(x) ∈ y ⟺ e_{1}(x) = e_{2}(e(x)) ∈ e_{2}(y),
x ∈ e^{−1}“ y ⟺ x ∈ e_{1}^{−1}“ e_{2}(y) = s.

Thus s is the standardization of y by e. We have shown e is standardizable. Again by the characterization theorem of the Rudin-Frolík order, we have p_{1} ⊑ p_{2}. In case there is e_{0} : V̂(X)^{⟨𝒜_{2}⟩} /p_{2} → V̂(X)^{⟨𝒜_{1}⟩} /p_{1}, we conclude p_{2} ⊑ p_{1} similarly.

5 Conjectures

We have proved that the initial segments of Rudin-Frolík order of the ultrafilters of the complete Boolean algebras with ccc are totally ordered. Now we consider eliminating conditions completeness or ccc.

Against completeness, we have to consider the general nonstandard universes and extend the definition of Rudin-Frolík order. This means the order completion of Rudin-Frolík order. I think that eliminating the condition completeness must be possible.

Against ccc, I state a conjecture here.

Conjecture 5.1. Under the first measurable cardinal, the initial segments Rudin-Frolík order are totally ordered.

In the conjecture above, the first measurable cardinal is derived from that every σ-complete homomorphism of Boolean algebras of sets is complete.

References

[1] C. Chang and J. Keisler, Model Theory, 3rd ed, North-Holland, Amsterdam, (1990).

[2] W. W. Comfort and S. Negrepontis, The theory of ultrafilters, Springer, Berlin, (1974).

[3] Z. Frolík, Sum of ultrafilters, Bull. Amer. Math. Soc., 73 (1967) 87–91.

[4] R. Mansfield, The theory of Boolean ultrapowers, Ann. Math. Logic, 2 (1971) 297–323.

[5] M. Murakami, Standardization principle of Nonstandard universes, Journal of Symbolic Logic, 64, 4(1999), 1645–1655.

[6] M. Ozawa, Forcing in nonstandard analysis, Annals of Pure and Applied Logic, 68 (1994), 263–297.

[7] M. Rudin, Partial orders on the type in β N, Trans. Amer. Math. Soc., 155 No.2 (1971) 353–362.