Orderings of fil ters in terms of reloids
∗
Extensions of Rudin-Keisler ordering
by Victor Porton
August 13, 2013
Abstract
Orderings of filters which extend Rudin-Keisler preorder of ultrafilters are described in terms
of reloids that (roughly speaking) is filters on sets of binary relations between some sets. Also
it is defined isomorphism of filters which extends Rudin-Keisler equivalence of ultrafilters.
Keywords: Rudin-Keisler order, Rudin-Keisler preorder, Rudin-Keisler ordering, filters,
ultrafilters, reloids, isomorphism, isomorphic
A.M.S. subject classification: 06F99, 06A99, 54D99
1 Draft status
It is a draft.
2 Preliminary defi nitions
Whilist my other works use filters to resea rch funcoids and reloids [3], here it is discussed the
opposite thing, the theory of reloids is used to describe properties of filters.
See [4] for the definition of filter objects and [3] for the definition and properties of reloids a nd
funcoids.
I will call small sets members of some Grothendieck universe.
Recall that morphisms of the category Set (or “Set -morphisms” for short) are triples (F ; A; B)
of a function F and small sets A and B where dom F ⊆ A and im F ⊆ B.
For X ∈ PA we’ll denote h(F ; A; B)iX = hF i X.
Let f = (F ; A; B) is a Set-morphism. I will denote in this article
↑f =
↑
FCD(A;B)
F ; A; B
and ↑
RLD
f =
↑
RLD(A;B)
F ; A; B
.
2.1 Equivalent filters
We will restrict to small sets that is members of some Grothendieck universe.
Definition 1. Two filter objects A and B (with possibly different base sets) are equivalent (A∼ B)
iff there exists a set X such that X ∈ up A and X ∈ up B and PX ∩ up A = PX ∩ up B.
Proposition 2. If two filter objects with the same base are equivalent they are equal.
Proof. Let A and B are two f.o. and PX ∩ up A = PX ∩ up B for some set X such that X ∈ up A
and X ∈ up B, and Base(A) = Base(B). Then up A = (PX ∩ up A) ∪ {Y ∈ PBase(A) | Y ⊇ X } =
(PX ∩ up B) ∪ {Y ∈ P Base(B) | Y ⊇ X } = up B.
Proposition 3. ∼ restricted to small filter objects is an equivalence relation.
Proof.
Reflexivity. Obvious.
Symmetry. Obvious.
∗. This document has been written using the GNU T
E
X
MACS
text editor (see www.texmacs.org).
1
Transitivity. Let A ∼ B and B ∼ C for some small f.o. A, B, and C. Then exist a set X such
that X ∈ up A and X ∈ up B and PX ∩ up A = PX ∩ up B and a set Y such th at Y ∈ up B
and Y ∈ up C and PY ∩ up B = PY ∩ up C. So X ∩ Y ∈ up A because
PY ∩ PX ∩ up A = PY ∩ PX ∩ up B = P (X ∩ Y ) ∩ up B ⊇ {X ∩ Y } ∩ up B ∋ X ∩ Y .
Similarly we have X ∩ Y ∈ up C. Finally P (X ∩ Y ) ∩ up A = PY ∩ PX ∩ up A =
PY ∩ PX ∩ up B = PX ∩ PY ∩ up B = PX ∩ PY ∩ up C = P(X ∩ Y ) ∩ up C.
Definition 4. The rebase A ÷ A for a f.o. A and a set A (base) such that ∃X ∈ up A: X ⊆ A is
defined by the formula
A ÷ A = up
−1
{X ∈ PA | ∃Y ∈ up A: Y ⊆ X }
where “up” is taken for the set of f.o. on A.
Proposition 5. If ∃X ∈ up A: X ⊆ A then:
1. A ÷ A is a f.o.
2. A ÷ A ∼ A.
Proof.
1. We need to prove that { X ∈ PA | ∃Y ∈ up A: Y ⊆ X } is a fi lter on A. That it is
an upper set is obvious. It is non-empty because ∃Y ∈ up A: Y ⊆ A and thus A ∈
{X ∈ PA | ∃Y ∈ up A: Y ⊆ X }. Let P , Q ∈ {X ∈ PA | ∃Y ∈ up A: Y ⊆ X }. Then P , Q ⊆ A
and ∃P
′
∈ up A: P
′
⊆ P and ∃Q
′
∈ up A: Q
′
⊆ Q. So P ∩ Q ⊆ A and P
′
∩ Q
′
⊆ P ∩ Q. Thus
P ∩ Q ∈ {X ∈ PA | ∃Y ∈ up A: Y ⊆ X }.
2. P (A ∩ Base(A)) ∩ up A = up(A ÷ (A ∩ Base(A))) = {X ∈ P(A ∩ Base(A)) | ∃Y ∈ up A:
Y ⊆ X } = P(A ∩ Bas e (A)) ∩ up A = PA ∩ up A = {X ∈ PA | X ∈ up A} =
{X ∈ PA | ∃Y ∈ up A: Y ⊆ X , X ⊆ Base(A)} = P (A ∩ Bas e(A)) ∩ up(A ÷ A).
Thus A ÷ A ∼ A becau se A ∩ Base(A) ⊇ X ∈ u p A for some X ∈ up A and A ∩ Base(A) ⊇
X ∩ Base(A) ∈ {X ∈ PA | ∃Y ∈ up A: Y ⊆ X } = up(A ÷ A).
Proposition 6. A ∈ up A ⇒ up(A ÷ A) = PA ∩ up A.
Proof. Let A ∈ up A. Then up(A ÷ A)= {X ∈ PA | ∃Y ∈up A: Y ⊆ X }= {X ∈ PA | X ∈ upA} =
PA ∩ up A.
Lemma 7. If A ∼ B then ∃Y ∈ up A: Y ⊆ X ⇔ ∃Y ∈ up B: Y ⊆ X for every f.o. A, B, and a set X.
Proof. We will prove ∃Y ∈ up A: Y ⊆ X ⇒ ∃Y ∈ up B: Y ⊆ X (the other direc tion is si milar).
We have PK ∩ up A = PK ∩ up B for some set K such that K ∈ up A, K ∈ up B.
∃Y ∈up A: Y ⊆ X ⇒ ∃Y ∈PK ∩ up A:Y ⊆ X ⇒ ∃Y ∈ PK ∩ up B:Y ⊆ X ⇒ ∃Y ∈ up B: Y ⊆ X.
Proposition 8. If A ∼ B then B = A ÷ Base(B) for every f.o. A, B.
Proof. PY ∩ up A = PY ∩ up B for some set Y ∈ up A, Y ∈ up B. There exists a set X ∈ up A
such that X ∈ up B. Thus ∃X ∈ up A: X ⊆ Base(B) and so A ÷ Base(B) is a properly defined f.o.
X ∈ up(A ÷ Base(B)) ⇔ X ∈ PBas e(B) ∧ ∃Y ∈ up A: Y ⊆ X ⇔ X ∈ PBase(B) ∧ ∃Y ∈ up B :
Y ⊆ X ⇔ X ∈ up B (the lemma used).
3 Orde ring of filters
Below I will define some categories having filter objects (with possibly different bases) as their
objects a nd some relations having two filter objects (with possibly different bases) as arguments
induced by these c ategories (defined as existence of a morphism between these two f.o.).
Theorem 9. card a = card U for every ultrafilter a on U if U is infinite.
2 Section 3
Proof. Let f (X) = X if X ∈ a and f(X) =U \X if X
a. Obviously f is a surjection from U to a.
Every X ∈ a appears as a value of f exactly twice, as f (X) and f(U \ X). So card a = U /2 =
U.
Corollary 10. Cardinality of every two ultrafilters on a s et U is the same.
Proof. For infinite U it follows from the theorem. For finite case it is obvious.
Definition 11. f∗A = {C ∈ P (Dst f ) | hf
−1
iC ∈ up A} for every f .o. A and a Set-morphism f .
Below I’ll define some directed multigraphs. By an abuse of notation, I will denote these multi-
graphs the same as (below defined) categories based on some of these these directed multigraphs
with added composition of morphisms (of directed multigraphs edges). As such I will call vertices
of these multigraphs objects and edges morphisms.
Definition 12. I will denote GreFunc
1
the multigraph whose objects are filter objects and whose
morphisms between objects A and B are Set-morphisms from Base(A) to Base(B) such that
up B ⊇ f∗A.
Definition 13. I will denote GreFunc
2
the multigraph whose objects are filter objects and whose
morphisms between objects A and B are Set-morphisms from Base(A) to Base(B) such that
up B = f ∗A.
Definition 14. Let A is a f.o. on a set X and B is a f.o. on a set Y . A >
1
B iff Mor
GreFunc
1
(A; B)
is not empty.
Definition 15. Let A is an f.o. on a set X and B is an f.o. on a set Y . A >
2
B iff Mor
GreFunc
2
(A; B)
is not empty.
Proposition 16.
1. f ∈ Mor
GreFunc
1
(A; B) iff f is a Set-morphism from Base(A) to Base(B) such that
C ∈ up B ⇐ hf
−1
iC ∈ up A
for eve ry C ∈ P Base(B).
2. f ∈ Mor
GreFunc
2
(A; B) iff f is a Set-morphism from Base(A) to Base(B) such that
C ∈ up B ⇔ hf
−1
iC ∈ up A
for eve ry C ∈ P Base(B).
Proof.
1. f ∈ Mor
GreFunc
1
(A; B) ⇔ up B ⊇ f ∗A ⇔ ∀C ∈ f∗A: C ∈ up B ⇔ ∀C ∈ PBase(B):
(hf
−1
iC ∈ up A ⇒ C ∈ up B).
2. f ∈ Mor
GreFunc
2
(A; B) ⇔ up B = f∗A ⇔ ∀C: (C ∈ up B ⇔ C ∈ f ∗A) ⇔ ∀C ∈ P Base(B):
(C ∈ up B ⇔ C ∈ f∗ A) ⇔ ∀C ∈ PBase(B): (C ∈ up B ⇔ hf
−1
iC ∈ up A).
Definition 17. The multigraph FuncBij is the multigraph got from GreFunc
2
by restricting to
only bijective morphisms.
Definition 18. A f.o. A is directly isomorphic to a f.o. B iff there are a morphism f ∈
Mor
FuncBij
(A; B).
Proposition 19. f ∗A = up h↑f iA for every Set-morphism f: Base(A) → Base(B).
Proof. For every set C ∈ P Base(B) we have C ∈ f∗A ⇔ hf
−1
iC ∈ up A ⇒ ∃K ∈ up A:
hf
−1
iC = K ⇒ ∃K ∈ up A: hf ihf
−1
iC = hf iK ⇒ ∃K ∈ up A: C ⊇ hf iK ⇔ ∃K ∈ up A:
C ∈ up hf iK ⇔ C ∈ up
T
↑
Base(B )
hhf iiup A ⇔ C ∈ up h↑f iA.
So C ∈ f ∗A ⇒ C ∈ up h↑f i A.
Ordering of filters 3
Let now C ∈ up h↑f iA. Then ↑
Base(A)
hf
−1
iC ⊇ h↑f
−1
ih↑f iA ⊇ A and thus hf
−1
iC ∈ up A.
Corollary 20. f ∈ Mor
GreFunc
1
(A; B) ⇔ B ⊆ h↑f iA for every Set-m orphism f from Base(A) to
Base(B).
Corollary 21. f ∈ Mor
GreFunc
2
(A; B) ⇔ B = h↑f iA for every Set-morphism f from Base(A) to
Base(B).
Corollary 22. A >
2
B iff it exis ts a Set-morphism f: Base(A) → Base(B) such that B = h↑f iA.
Corollary 23. up B ⊇ f∗A ⇔ B ⊆ h↑f iA .
Corollary 24. A >
1
B iff it exis ts a Set-morphism f: Base(A) → Base(B) such that B ⊆ h↑f iA.
Proposition 25. For a bijective Set-morphism f :Base(A) →Base(B) the following are equivalent:
1. up B = f∗A.
2. ∀C ∈ B ase(B): (C ∈ up B ⇔ hf
−1
iC ∈ up A).
3. ∀C ∈ B ase(A): (hf iC ∈ up B ⇔ C ∈ up A).
4. hf i|
up A
is a bijection from up A to up B .
5. hf i|
up A
is a function onto up B.
6. B = h↑f iA.
7. f ∈ Mor
GreFunc
2
(A; B).
8. f ∈ Mor
FuncBij
(A; B).
Proof.
(1)⇔(2). up B = f∗A ⇔ up B = {C ∈ PBase(B) | hf
−1
iC ∈ up A} ⇔ ∀C ∈ Base(B):
(C ∈ up B ⇔ hf
−1
iC ∈ up A).
(2)⇔(3). Because f is a bijection.
(2)⇒(5). For every C ∈ up B we have hf
−1
iC ∈ up A and thus hf i|
up A
hf
−1
iC = hf i hf
−1
iC =
C. Thus hf i|
up A
is onto up B.
(4)⇒(5). Obvious.
(5)⇒(4). We need to prove only that hf i|
up A
is an injection. But this follows from the fact
that f is a biject ion.
(4)⇒(3). We have ∀C ∈ Base(A): ((hf i|
up A
)C ∈ up B ⇔ C ∈ up A ) and consequently
∀C ∈ Base(A): (hf iC ∈ up B ⇔ C ∈ up A).
(6)⇔(1). From the last corollary .
(1)⇔(7). Obvious.
(7)⇔(8). Obvious.
Corollary 26. The following are equivalent for every f.o. A and B:
1. A is directly isom orphic to a f.o. B.
2. There are a bijective Set-morphism f :Base(A)→ Base(B) such that for eve ry C ∈P B ase(B)
C ∈ up B ⇔ hf
−1
iC ∈ up A
3. There are a bijective Set-morphism f :Base(A)→ Base(B) such that for eve ry C ∈P B ase(B)
hf iC ∈ up B ⇔ C ∈ u p A.
4. There are a bijective Set-mo rphism f : Base(A) → Base(B) such that hf i|
up A
is a bijection
from up A to up B.
4 Section 3
5. There are a bijective Set-morphism f : Base(A) → Bas e(B) such that hf i|
up A
is a function
onto up B.
6. There are a bijective Set-morphism f: Base(A) → Base(B) such that B = h↑f iA.
7. There are a bijective morph ism f ∈ Mor
GreFunc
2
(A; B).
Proposition 27. GreFunc
1
and GreFunc
2
with function composition are categories.
Proof. Let f: A→ B and g: B → C are morphisms of GreFunc
1
. Then B ⊆ h↑f iA and C ⊆ h↑g iB.
So h↑(g ◦ f)iA = h↑gih↑f iA ⊇ h↑giB ⊇ C. Thus g ◦ f is a morphism of GreFunc
1
. Associativity
law is evident. Id
Base(A)
is the identity morphism of GreFunc
1
for eve ry f.o. A.
Let f : A → B and g: B → C are morphism s of GreFunc
2
. Then B = h↑f iA and C = h↑g iB. So
h↑(g ◦ f )iA = h↑gih↑f iA = h↑giB = C. Thus g ◦ f is a morphism of GreFunc
2
. Associativity law
is evident. Id
Base(A)
is the identity morphism of GreFunc
2
for eve ry f.o. A.
Corollary 28. 6
1
and 6
2
are preorders.
Theorem 29. FuncBij is a groupoid.
Proof. First let’s prove it is a category. Let f : A → B and g: B → C are morphisms of FuncBij.
Then f : Base(A) →Base(B) and g: Base(A)→ Base(C) are bijections and B = h↑f iA and C = h↑g iB.
Thus g ◦ f: Base(A) → Base(C) is a bijection and C = h↑(g ◦ f)iA. Thus g ◦ f is a morphism of
FuncBij. Id
Base(A)
is the identity morphism of FuncBij for every f.o. A. Thus it is a categ ory .
It re mains to prove only that every morphism f ∈ Mor
FuncBij
(A; B) has a reverse (for every f.o.
A, B). We have f is a bijection Base(A) → Base(B) such that for every C ∈ P Base(A)
hf iC ∈ up B ⇔ C ∈ u p A.
Then f
−1
: Base(B) → Base(A) is a bijection such that for eve ry C ∈ PBase(A)
hf
−1
iC ∈ up A ⇔ C ∈ up B.
Thus f
−1
∈ Mor
FuncBij
(B; A).
Corollary 30. Be ing directly isomorphic is an equivalence relation.
Obvious 31. For the case of ultrafilters being directly isomorphic is the same as being Rudin-
Keisler equivalent.
Definition 32. A f.o. A is isomorphic to a f.o. B iff the re exis t sets A ∈ up A and B ∈ up B such
that A ÷ A is directly isomorphic to B ÷ B.
Obvious 33. Equivalent f.o. are isomorphic.
Theorem 34. B eing isomorphic (for filter objects) is an equivalence relation.
Proof.
Reflexivity. Because every f.o. is direc tly iso morphic to itself.
Symmetry. If f.o. A is isom orphic t o B then there exist set s A ∈ up A and B ∈ up B such that
A ÷ A is directly isomorphic to B ÷ B and thus B ÷ B is directly isomorphic to A ÷ A, So
B is isomorphic to A.
Transitivity. Let A is isomorphic to B and B is isomorphic to C. Then exist A ∈ up A,
B
1
∈ up B, B
2
∈ up B, C ∈ up C such that the re are bije ctions f: A→ B
1
and g ∈ B
2
→ C such
that
∀X ∈ PA: (X ∈ up B ⇔ hf
−1
iX ∈ up A) and ∀X ∈ PB
2
: (X ∈ up A ⇔ hf iX ∈ up B).
Also ∀X ∈ PB
2
: (X ∈ up B ⇔ hgiX ∈ up C).
So g ◦ f is a bijection from hf
−1
i(B
1
∩ B
2
) ∈ up A to hg i(B
1
∩ B
2
) ∈ up C such that
X ∈ up A ⇔ hf iX ∈ up B ⇔ hg ihf iX ∈ up C ⇔ hg ◦ f iX ∈ up C.
Ordering of filters 5
Thus g ◦ f establishes a bijection which proves that A is isomorphic to C.
Lemma 35. Let card X = cardY , u is an atomic f.o. on X and v is an atomic f.o. on Y ; let A ∈up u
and B ∈ up v. Let u ÷ A and v ÷ B are directly isomorphic. Then if card(X \ A) = card(Y \ B) we
have u and v directly isomorphic.
Proof. Arbitrary extend the bijection witnessing being directly isomorphic to the sets X \ A and
Y \ B.
Theorem 36. If card X = card Y then being isomorphic and being directly isomorphic are the
same for atomic f.o. u on X and v on Y .
Proof. That if two filter objects are isomorphic then they are directly isomorphic is obvious.
Let atomic f.o. u and v are isomorphic that is there is a bijection f: A → B where A ∈ up u,
B ∈ up v witnessing isomorphism of u and v.
If one of the filters u or v is a trivial ato mic f.o. then the other is also a trivial atomic f.o. and as
it is easy to show they are directly isomo rphic. So we can assume u and v are not trivial atomic f.o.
If card(X \ A) = card(Y \ B) our statement f ollows from the last lemma.
Now assume without loss of generality card(X \ A) < card(Y \ B).
card B = card Y b ecause card(Y \ B) < card Y .
It is easy to show that thre exists B
′
⊃ B such that card(X \ A) = card(Y \ B
′
) and
card B
′
= card B.
We will find a bijection g from B to B
′
which witnesses direct isomorphism of v to v itself.
Then the composition g ◦ f witnesses a direct isomorphism of u ÷ A and v ÷ B
′
and by th e lemma
u and v are directly isomorphic.
Let D = B
′
\ B. We have D
up v.
There exists a set E ⊆ B such that card E > card D and E
up v.
We have card E = card(D ∪ E) and thus there exists a bijection h: E → D ∪ E.
Let
g(x) =
x if x ∈ B \ E;
h(x) if x ∈ E.
g|
B \E
and g|
E
are bijections.
im(g |
B \E
) = B \ E; im(g |
E
) = im h = D ∪ E;
(D ∪ E) ∩ (B \ E) = (D ∩ (B \ E)) ∪ (E ∩ (B \ E)) = ∅ ∪ ∅ = ∅.
Thus g is a bijection from B to (B \ E) ∪ (D ∪ E) = B ∪ D = B
′
.
To finish the proof it’s enough to show that hgiv = v. Indeed it follows from B \ E ∈ up v.
Proposition 37.
1. For every A ∈ up A and B ∈ up B we have A >
2
B iff A ÷ A >
2
B ÷ B.
2. For every A ∈ up A and B ∈ up B we have A >
1
B iff A ÷ A >
1
B ÷ B.
Proof.
1. A >
2
B iff there exist a bijective Set-mo rphism f such that B = h↑f iA. The equality is
obviously preserve d replacing A with A ÷ A and B with B ÷ B.
2. A >
1
B iff there exist a bijective Set-mo rphism f such that B ⊆ h↑f iA. The equality is
obviously preserve d replacing A with A ÷ A and B with B ÷ B.
Rudin-Keisler order of ultrafilters is cons idered in such a book as [6].
Proposition 38. For ultrafilters >
2
is the same as Rudin-Keisler ordering.
Proof. x >
2
y iff there exist sets A ∈ up x and B ∈ up y a bijective Set-morphism f : X → Y such
that up(y ÷B)={C ∈ PY | hf
−1
iC ∈up(x ÷ A)} that is when C ∈up(y ÷ B)⇔hf
−1
iC ∈up(x÷ A)
what is equivalent to C ∈ up y ⇔ hf
−1
iC ∈ up x what is the definition of Rudin-Keis le r ordering.
6 Section 3
Remark 39. The relation of being isomorphic for ultrafilters is traditionally called Rudin-Keisler
equivalence.
Obvious 40. (>
1
) ⊇ (>
2
).
Definition 41. Let Q and R a re binary relations on the set of filter objects. I will denote
MonRld
Q,R
the directed multigraph with objects being filter objects and mo rphisms such mono-
valued reloids f that (dom f) Q A and (im f) R B.
I will also denote CoMonRld
Q,R
the direc ted multigraph with objects being filter objects and
morphisms such injective reloids f that (im f ) QA and (dom f ) RB. T he se are ess e ntially the duals.
Some of these dire cted multigraphs are categories with reloid composition (see below). By abuse
of notation I will denote these categories the same as these directed multigraphs.
Theorem 42. For every f.o. A and B the following are equivalent:
1. A >
1
B.
2. Mor
MonRld
=,⊇
(A; B)
∅.
3. Mor
MonRld
⊆,⊇
(A; B)
∅.
4. Mor
MonRld
⊆,=
(A; B)
∅.
5. Mor
CoMonRld
=,⊇
(A; B)
∅.
6. Mor
CoMonRld
⊆,⊇
(A; B)
∅.
7. Mor
CoMonRld
⊆,=
(A; B)
∅.
Proof.
(1)⇒(2). There exists a Set-morphism f : Ba se(A) → Base(B) such that B ⊆ h↑f iA. We have
dom (↑
RLD
f)|
A
=A ∩ dom f = A
and
im (↑
RLD
f)|
A
=im (FCD)(↑
RLD
f)|
A
=im (↑f )|
A
=h↑f iA ⊇ B.
Thus (↑
RLD
f)|
A
is a monovalued reloid such that dom (↑
RLD
f)|
A
=A and im (↑
RLD
f)|
A
⊇B.
(2)⇒(3), (4)⇒(3), (5)⇒(6), (7)⇒(6). Obvious.
(3)⇒(1). We have B ⊆ h(FCD)f iA for a monovalue d reloid f ∈RLD(Base(A); Base(B)). Then
there exists a Set-morphism F : Base(A) → Base(B) such that B ⊆ h↑F i A that is A >
1
B.
(6)⇒(7). dom f |
B
=B and im f |
B
⊆A.
(2)⇔(5), (3)⇔(6), (4)⇔(7). By duality.
Theorem 43. For every f.o. A and B the following are equivalent:
1. A >
2
B.
2. Mor
MonRld
=,=
(A; B)
∅.
3. Mor
CoMonRld
=,=
(A; B)
∅.
Proof.
(1)⇒(2). Let A >
2
B that is B = h↑f iA for some Set-morphism f : Base(A) → Base(B).
Then dom (↑
RLD
f)|
A
=A and im (↑
RLD
f)|
A
=im (FCD)(↑
RLD
f)|
A
=im (↑f)|
A
=h↑f iA = B. So
(↑
RLD
f)|
A
is a sought for reloid.
(2)⇒(1). There exists a Set-morphism F : Base(A) → Base(B) such that f = (↑
RLD
F )|
A
. Thus
h↑F iA = im(↑F )|
A
=im (FCD)(↑
RLD
F )|
A
=im (FCD)f = im f = B. Thus A >
2
B is testified by
the morphism F .
(2)⇔(3). By duality.
Ordering of filters 7
Theorem 44. The following are categories (with reloid composition):
1. MonRld
⊆,⊇
;
2. MonRld
⊆,=
;
3. MonRld
=,=
.
4. CoMonRld
⊆,⊇
;
5. CoMonRld
⊆,=
;
6. CoMonRld
=,=
.
Proof. We will prove only the first three. The rest follow from duality. We need to prove only that
composition of morphisms is a morphism, because a ssociativ ity and existence of identity morphism
are evident. We have:
1. Let f ∈ Mor
MonRld
⊆,⊇
(A; B), g ∈ Mor
MonRld
⊆,⊇
(B; C). The n dom f ⊆ A, im f ⊇ B,
dom g ⊆ B, im g ⊇ C. So dom(g ◦ f) ⊆ A, im(g ◦ f) ⊇ C that is g ◦ f ∈ Mor
MonRld
⊆,⊇
(A; C).
2. Let f ∈ Mor
MonRld
⊆,=
(A; B), g ∈ Mor
MonRld
⊆,=
(B; C). The n dom f ⊆ A, im f = B,
dom g ⊆ B, im g = C. So dom(g ◦ f ) ⊆ A, im(g ◦ f ) = C that is g ◦ f ∈ Mor
MonRld
⊆,=
(A; C).
3. Let f ∈Mor
MonRld
=,=
(A; B), g ∈ Mor
MonRld
=,=
(B;C). Then dom f = A, im f =B, dom g =B,
im g = C. So dom(g ◦ f ) = A, im(g ◦ f ) = C that is g ◦ f ∈ Mor
MonRld
=,=
(A; C).
Definition 45. Let BijRld is the groupoid of all bijections of the category of reloid triples. Its
objects are filter objects and its morphisms from a f.o. A to f.o. B are monovalued injective reloids
f s uch that dom f = A and im f = B.
Theorem 46. Filter objects A and B are isomorphic iff Mor
BijRld
(A; B)
∅.
Proof.
⇒. Let A and B are isomorphic. Then there are sets A ∈ up A, B ∈ up B and a bijective Set-
morphism F : A → B such that hF i: PA ∩ up A → PB ∩ up B is a bijection.
Obviously f = (↑
RLD
F )|
A
is monovalued and injective.
im f =
T
{↑
B
im G | G ∈ up (↑
RLD
F )|
A
} =
T
{↑
B
im(H ∩ F |
X
) | H ∈ up (↑
RLD
F )|
A
,
X ∈ up A} =
T
{↑
B
im F |
P
| P ∈ up A} =
T
{↑
B
hF iP | P ∈ up A} =
T
{↑
B
hF iP | P ∈
PA ∩ up A} =
T
h↑
B
i(PB ∩ up B) =
T
h↑
B
iup B = B.
Thus dom f = A and im f = B.
⇐. Let f is a monovalued injective reloid such that dom f = A and im f = B. Then e xist a
function F
′
and an inj ective binary relation F
′′
such that F
′
, F
′′
∈ up f. Thus F = F
′
∩ F
′′
is a n in jection such that F ∈ up f . The func tio n F is a bijection from A = dom F to
B = im F . The function hF i is an inje ction on PA ∩ up A (and moreover on PA). It’s
simple to show that ∀X ∈ PA ∩ up A: hF iX ∈ PB ∩ up B and similarly ∀Y ∈ PB ∩ up B:
hF i
−1
Y = hF
−1
iY ∈ PA ∩ up A. Thus hF i|
PA∩up A
is a bijection PA ∩ up A→ PB ∩ up B.
So filter objects A and B are isomorphic.
Proposition 47. (>
1
) = (⊆) ◦ (>
2
) (when we limit to small f.o.).
Proof. A >
1
B iff exists a function f : Ba se(A) → Base(B) such that B ⊆ h↑f iA. But B ⊆ h↑f iA is
equivalent to ∃B
′
∈ F: (B ⊆ B
′
∧ B
′
= h↑f iA). So A >
1
B is equivalent to existence of B
′
∈ F s uch that
B ⊆ B
′
and existence of a function f: Base(A) → Base(B) such that B
′
= h↑f iA. That is equivalent
to A((⊆) ◦ (>
2
))B.
Proposition 48. If a and b is an atomic f.o. then b >
1
a ⇔ b >
2
a.
Proof. We need to prove only b >
1
a ⇒ b >
2
a. If b >
1
a then there exis ts a monovalued
reloid f: Base(b) → 1
F(Base(a))
such that dom f = b and im f ⊇ a. The n im f = im (FCD)f ∈
0
F(Base(a))
∪ atoms 1
F(Base(a))
because (FCD)f is a monova lued funco id. So im f = a (taken in
account a
0
F(Base(a))
) and thus b >
2
a.
8 Section 3
Corollary 49. For atomic filter objects >
1
is the same as >
2
.
Thus I will write simply > for atomic f.o.
3.1 Existence of no more than one monovalued injective reloid for a given
pair of filter objects
3.1.1 The lemmas
The lemm as in this section were provided to me by Robert Martin Solovay in [5]. These are based
on Wistar Comfort’s work.
In this section we will assume µ is an ultrafilter on a se t I and f : I → I has the property
X ∈ µ ⇔ hf
−1
iX ∈ µ.
Lemma 50. If X ∈ µ then X ∩ hf iX ∈ µ.
Proof. If hf iX
µ then X ⊆hf
−1
ihf iX
µ and so X
µ. Thus X ∈ µ ∧ hf iX ∈ µ and consequently
X ∩ hf iX ∈ µ.
We will say that x is periodic when f
n
(x) = x for som e positive integer x. The leas t such n is
called the period of x.
Let’s define x ∼ y iff there exist i, j ∈ N such that f
i
(x) = f
j
(y). Trivially it is an equiva lenc e
relation. If x and y are periodic, then x ∼ y iff exists n ∈ N such that f
n
(y) = x.
Let A = {x ∈ I | x is periodic with period>1}.
We will show that A
µ. Let’s assume A ∈ µ.
Let a set D ⊆ A contains (by the axiom of choice) exactly one element from each equiva le nce
class of A defined by the relation ∼.
Let α is a function A →N defined as follows. Let x ∈ A. Let y be the unique element of D such
that x ∼ y. Let α(x) be the least n ∈ N such that f
n
(y) = x.
Let B
0
= {x ∈ A | α(x) is even} and B
1
= { x ∈ A | α(x) is odd}.
Let B
2
= {x ∈ A | α(x) = 0}.
Lemma 51. B
0
∩ hf iB
0
⊆ B
2
.
Proof. If x ∈ B
0
∩ hf iB
0
then f
n
(y) = x for a minimal even n and x = f (x
′
) where f
m
(y
′
) = x
′
for a minimal even m. Thus f
n
(y) = f(x
′
) thus y and x
′
lay ing in the same equivalence class and
thus y = y
′
. So we have f
n
(y) = f
m+1
(y). Thus n 6 m + 1 by minimality.
x
′
lies on an orbit and thus x
′
= f
−1
(x) where by f
−1
I mean step backward on our orbit;
f
m
(y) = f
−1
(x) and thus x
′
= f
n−1
(y) thus n − 1 > m by minimality or n = 0.
Thus n = m + 1 what is impossible for even n and m. We have a contradiction what proves
B
0
∩ hf iB
0
⊆ ∅.
Remained the case n = 0, then x = f
0
(y) and thud α(x) = 0.
Lemma 52. B
1
∩ hf iB
1
= ∅.
Proof. Let x ∈ B
1
∩ hf iB
1
. Then f
n
(y) = x for an odd n and x = f (x
′
) where f
m
(y
′
) = x
′
for an
odd m. Thus f
n
(y) = f(x
′
) thus y and x
′
laying in the same equivalenc e class and thus y = y
′
. So
we have f
n
(y) = f
m+1
(y). Thus n 6 m + 1 by minimality.
x
′
lies on an orbit and thus x
′
= f
−1
(x) where by f
−1
I mean step backward on our orbit;
f
m
(y) = f
−1
(x) and thus x
′
= f
n−1
(y) t hus n −1 > m by minimality (n= 0 is impossible because
n is odd.
Thus n = m + 1 wha t is impossible for odd n and m. We have a contradiction what proves
B
0
∩ hf iB
0
= ∅.
Lemma 53. B
2
∩ hf iB
2
= ∅.
Proof. Let x ∈ B
2
∩ hf iB
2
. Then x = y and x
′
= y where x = f(x
′
). Thus x = f(x) and so x
A
what is impossible.
Ordering of filters 9
Lemma 54. A
µ.
Proof. Suppose A ∈ µ.
Since A ∈ µ we have B
0
∈ µ or B
1
∈ µ.
So either B
0
∩ hf iB
0
⊆ B
2
or B
1
∩ hf iB
1
⊆ B
2
. As such by the lemma 50 we have B
2
∈ µ. This
is incompatible with B
2
∩ hf iB
2
= ∅. So we got a contradiction.
Let C be the set of points x which are not periodic but f
n
(x) is period ic for some positive n.
Lemma 55. C
µ.
Proof. Let β be a function C → N such that β(x) is the least n ∈ N such that f
n
(x) is period ic.
Let C
0
= {x ∈ C | β(x) is even} and C
1
= {x ∈ C | β(x) is odd}.
Obviously C
j
∩ hf iC
j
= ∅ for j = 0, 1. Hence by the lemma 50 we have C
0
, C
1
µ and thus
C = C
0
∪ C
1
µ.
Let E be the set of x ∈ I such that for no n ∈ N we have f
n
(x) periodic.
Lemma 56. Let x, y ∈ E are such that f
i
(x) = f
j
(y) and f
i
′
(x) = f
j
′
(y) for some i, j, i
′
, j
′
∈ N.
Then i − j = i
′
− j
′
.
Proof. i
f
i
(x) is a bijection.
So y = f
i− j
(y) and y = f
i
′
−j
′
(y). Thus f
i−j
(y) = f
i
′
−j
′
(y) and so i − j = i
′
− j
′
.
Lemma 57. E
µ.
Proof. Let D
′
⊆ E be a subset of E with exactly one element from e ach equivalence class of the
relation ∼ on E.
Define the function γ: E → Z as follows. Let x ∈ E. Let y be the unique element of D
′
such that
x∼ y. Choose i, j ∈N such that f
i
(y) = f
j
(x). Let γ(x)= i − j. By the last lemma, γ is well-defined.
It is clear that if x ∈ E then f (x) ∈ E and moreover γ(f (x)) = γ(x) + 1.
Let E
0
= {x ∈ E | γ(x) is even} a nd E
1
= {x ∈ E | γ(x) is odd}.
We have E
0
∩ hf iE
0
= ∅
µ and hence E
0
µ.
Similarly E
1
µ.
Thus E = E
0
∪ E
1
µ.
Lemma 58. f is the identity function on a set in µ.
Proof. We have s hown A, C , E
µ. But the points w hich lie in none of these sets are exac tly
points periodic with period 1 that is fixed points of f. Thus the set of fixed points of f belongs
to the filter µ.
3.1.2 The main theorem and its consequences
Theorem 59. For every atomic filter object a the morphism ((=)|
a
; a; a) is the only
1. monovalued morphism of the c ategory of reloids from a to a ;
2. injective morphism of the category of reloids from a to a;
3. bijective morphism of the category of reloids from a to a.
Proof. We will prove only (1) because the rest follow from it.
Let f is a monovalued morphism from a to a. Then it exists a Set-morphism (F ; a; a) such that
F ∈ up f . Trivially h↑(F ; a; a)ia ⊇ a and thus hF iA ∈ up a for every A ∈ up a. Thus by the lemma
we have that F is the identity function on a set in up a and so obviously f is an identity.
Corollary 60. For every two atomic filter objects (with p ossibly different bases) A and B there
exists at most one bijective reloid from A to B.
10 Section 3
Proof. Suppose that f and g are two different bijective reloids from A to B. Then g
−1
◦ f is not
the identity reloid (otherwise g
−1
◦ f = I
dom f
RLD
and so f = g). But g
−1
◦ f is a bijective reloid (as a
composition of bijective reloids) from A to A wha t is impossible.
4 Rud in-Keisler equivalence and Rudin-Keisler o rder
Theorem 61. Atomic filter objects a and b (with possibly different bases) are isomorphic iff
a > b ∧ b > a .
Proof. Let a > b ∧ b > a. Then there are a monovalued reloids f and g such that dom f = a a nd
im f = b and dom g = b and im g = a. Thus g ◦ f is a monovalued morphism from a to a. By the
above we have g ◦ f = I
a
RLD
so g = f
−1
and f
−1
◦ f = I
a
RLD
so f is monovalued. Thus f is an injective
monovalued reloid from a to b and thus a and b are isomorphic.
The last the ore m cannot be generalize d from atomic f .o. to arbitrary f.o., as it’s shown by the
following two examples:
Example 62. A >
1
B ∧ B >
1
A but A is not isomorphic to B for some f.o. A and B.
Proof. Consider A = ↑
R
[0; 1] and B =
T
{↑
R
[0; 1 + ε) | ε > 0}. Then the function f = {(x;
x/2) | x ∈R} witnesses both inequalities A >
1
B and B >
1
A. But these filters cannot be isomor phic
because only one of them is principal.
Lemma 63. Let f
0
and f
1
are Set-morphisms. Let f(x; y) = (f
0
x; f
1
y) for a function f. Then
↑
FCD(Dst f
0
;Dst f
1
)
f
(A ×
RLD
B) = h↑f
0
iA ×
RLD
h↑f
1
iB.
Proof.
↑
FCD(Dst f
0
;Dst f
1
)
f
(A ×
RLD
B) =
↑
FCD(Dst f
0
;Dst f
1
)
f
T
{↑
Src f
0
×Src f
1
(A × B) | A ∈ up A,
B ∈ up B} =
T
{↑
Src f
0
×Src f
1
hf i(A × B) | A ∈ up A, B ∈ up B} =
T
{↑
Dst f
0
×Dst f
1
(hf
0
iA ×
hf
1
iB) | A ∈ up A, B ∈ up B} =
T
{↑
Dst f
0
hf
0
iA ×
RLD
↑
Dst f
1
hf
1
iB | A ∈ up A, B ∈ up B} =
(theorem 164?? in [3])=
T
{↑
Dst f
0
hf
0
iA | A ∈ up A} ×
RLD
T
{↑
Dst f
1
hf
1
iB | A ∈ up B} =
h↑f
0
iA ×
RLD
h↑f
1
iB.
Lemma 64. If an f.o. A is isomorphic to an f.o. B then if X is a set and ↑
Base(A)
X ∩ A is an
atomic f.o., then there exists a set Y such that ↑
Base(A)
X ∩ A is an atomic f.o. isomorphic to
↑
Base(A)
Y ∩ B.
[FIXME: See the book for a cor rected proof.]
Proof. Let A is isomorphic to B. Then there are sets A ∈up A, B ∈up B such that A ÷A is directly
isomorphic to B ÷ B. So there are a bijection f : PA ∩ up A → PB ∩ up B such that B = hf iA.
[FIXME: ?? equality is wrong.]
up
↑
Base(A)
X ∩ A
= up
↑
Base(A)
(X ∩ A) ∩ A
= ?? = hX ∩ A ∩ iup A = hX ∩ i(PA ∩ up A).
Thus hhf iiup
↑
Base(A)
X ∩ A
= hhf iihX ∩ i(PA ∩ up A) = hf (X) ∩ ihhf ii(PA ∩ up A) =
hf (X) ∩ i(PB ∩ up B) = hf(X) ∩ B ∩ iup B = hf (X) ∩ iup B = up
↑
Base(B )
(f (X)) ∩ B
.
So hf i
↑
Base(A)
X ∩ A
=
T
↑
Base(B )
hhf iiup
↑
Base(A)
X ∩ A
=
T
↑
Base(B)
up
↑
Base(B )
(f (X)) ∩ B
= ↑
Base(B )
(f (X)) ∩ B.
Finally we have ↑
Base(B )
(f (X)) ∩ B is isomorphic to ↑
Base(A)
X ∩ A from the last equality.
Theorem 65. Let f is a monovalued injective reloid. Then f is isomorphic to the f.o. dom f.
Proof. Let f is a monovalued injective reloid. There exists a bijection F ∈ up f . Consider the
bijective function p = {(x; Fx) | x ∈ dom F }.
hpidom F = F and consequently hpidom f =
T
↑
RLD(Dst f ;Src f )
hpidom K | K ∈ up f
=
T
↑
RLD(Dst f ;Src f )
hpidom(K ∩ F ) | K ∈ up f
=
T
↑
RLD(Dst f ;Src f )
(K ∩ F ) | K ∈ up f
=
T
↑
RLD(Dst f ;Src f )
K | K ∈ up f
= f . Thus p witnesses that f is isomorphic to the f.o. dom f .
Corollary 66. A monovalued injective reloid with atomic domain is atomic.
Rudin-Keisler equivalence and Rudin-Keisler order 11
Corollary 67. I
A
RLD
is isomorphic to A for every f.o. A.
Theorem 68. There are atomic f.o. incomparable by Rudin-Keisler order.
Proof. See [2].
Theorem 69. >
1
and >
2
are different relations.
Proof. Cons ider a is an arbitrary non-empty f.o. Then a >
1
0
F(Base(a))
but not a >
2
0
F(Base(a))
.
Proposition 70. If a >
2
b where a is an atomic f.o. then b is also an atomic f.o.
Proof. b = h↑f ia for some f : Base(a) → Base(b). So b is an atomic f.o. since f is monovalued.
Corollary 71. If a >
1
b where a is an atomic f.o. then b is also an atomic f.o. or 0
F(Base(a))
.
Proof. b ⊆ h↑f ia for some f: Base(a) → Base(b). Therefore b
′
= h↑f ia is an atomic f.o. From this
follows our statement.
Proposition 72. P rincipal filters, generated by sets of the same cardinality, are isomorphic.
Proof. Let A and B are sets of the same cardinality. Then there are a bijection f from A to B.
We have hf iA = B and thus A and B are isomorphic.
Proposition 73. If a filter object is isomorphic to a principal f.o., the n it is also a principal f.o.
induced by a set with the same cardinality.
Proof. Let A is a set and B is a f.o. isomorphic to A. Then there are sets X ∈ up A and Y ∈ up B
such that there are a bijection f:X → Y such that hf iA = B. Thus A is a set of the same cardinality
as B.
Proposition 74. A filter isom orphic to a non-trivial atomic f.o. is a non-trivial atomic f.o.
Proof. Let a is a non-trivial atomic f.o. and a is isomorphic to b. The n a >
2
b and thus b is an
atomic f.o. The f.o. b cannot be trivial because otherwise a would be also trivial.
Theorem 75. For an infinite set U there exist 2
2
cardU
equivalence classes of isomorphic ultrafilters.
Proof. The number of bijections between any two given subsets of U is no more than
(card U)
card U
= 2
card U
. The number of bijections between all pairs of subsets of U is no more
than 2
card U
· 2
card U
= 2
card U
. Therefore ea ch isomorphism c lass contains at most 2
card U
ultra-
filters. But there are 2
2
card U
ultrafilters. So there are 2
2
card U
classes.
Remark 76. One of the above mentioned equivalence cla sses c ontains trivial ultrafilters.
Corollary 77. There exist non-isomorphic nontrivial ultrafilters on any infinite set.
5 Consequen ces
Theorem 78. The reloid ↑
A
{a} ×
RLD
F is isomorphic to the filter object F for every s e t A and
a ∈ A.
Proof. Consider B ={a} ×Base(F) and f = {(x; (a;x)) | x ∈ Base(F)}. Then f is a bijection from
Base(F) to B.
If X ∈ up F then hf iX ⊆ B and hf iX = {a} × X ∈ up(↑
A
{a} ×
RLD
F).
For every Y ∈ up(↑
A
{a} ×
RLD
F) ∩ PB we have Y = {a} × X fo r some X ∈ up F a nd thus
Y = hf iX.
12 Section 5
So hf i|
up F ∩PBase(F)
=hf i|
up F
is a bijection from up F ∩ PB to up(↑
A
{a} ×
RLD
F) ∩ PB.
We have up F ∩ PBase(F) and up(↑
A
{a} ×
RLD
F) ∩ PB directly isomorphic and thus up F is
isomorphic to up(↑
A
{a} ×
RLD
F).
Theorem 79. A m onovalued reloid with ato mic domain is atomic.
Proof. Let f is a monovalued reloid with atomic domain. There e xists a function F ∈ up f .
We have f ⊆
↑
RLD(Src f ;Dst f )
F
|
dom f
. Thus it suffices to prove that
↑
RLD(Src f ;Dst f )
F
|
dom f
is atomic.
Let the function τ : dom F → F is defined by the formula τx = (x; Fx) (for every x ∈ dom F ).
That τ is an injection is obvious. That τ is a surjection is also obvious. Thus τ is a bijecti on.
Let T = hτ i|
up dom f ∩Pdom F
.
If X ∈ up dom f ∩ P dom F then
TX = {τx | x ∈ X } = {(x; Fx) | x ∈ X } = F |
X
.
Thus TX ⊆ F and ↑
RLD(Src f ;Dst f )
TX ⊇
↑
RLD(Src f ;Dst f )
F
|
dom f
. So
TX ∈ up
↑
RLD(Src f ;Dst f )
F
|
dom f
∩ PF .
So T : up dom f ∩ Pdom F → up
↑
RLD(Src f ;Dst f )
F
|
dom f
∩ PF .
Let X , Y ∈ up dom f ∩ Pdom F and X
Y . Then TX = hτ iX
hτ iY = TY because τ is a
bijection. So T is an injection.
Let Y ∈ up
↑
RLD(Src f ;Dst f )
F
|
dom f
∩ PF . Then Y ⊆ F and thus Y = F |
dom Y
. We have
dom Y ∈ up dom f ∩ P dom F and
T dom Y = {τx | x ∈ dom Y } = {(x; Fx) | x ∈ dom Y } = F |
dom Y
=Y .
Thus T is a surjection.
Thus T is a bijection and so up dom f ∩ Pdom F is directly is omorphic to
up
↑
RLD(Src f ;Dst f )
F
|
dom f
∩ PF . Consequently up dom f is isom orphic to
up
↑
RLD(Src f ;Dst f )
F
|
dom f
, and so
↑
RLD(Src f ;Dst f )
F
|
dom f
is an atomic filter object because
dom f is atomic by the assumption.
Theorem 80. If f , g are reloids, f ⊆ g and g is monovalued then g|
dom f
=f.
Proof. It’s simple to show t hat f =
S
f |
a
| a ∈ atoms 1
F(Src f )
(use the fact that every atomic
reloid k ⊆ f |
a
for some a ∈ atoms 1
F(Src f)
and the fact that RLD(Src f; Dst f ) is atomistic).
Suppose that g|
dom f
f. Then there exists a ∈ atoms dom f such that g |
a
f |
a
.
Obviously g|
a
⊇f |
a
.
If g|
a
⊃f |
a
then g|
a
is not atomic (because f |
a
0
RLD(Src f ;Dst f )
) what contradicts to a theorem
above. So g |
a
=f |
a
what is a contradiction and thus g |
dom f
=f .
Corollary 81. Every monova lued re loid is a restr ic ted discrete monovalued reloid.
Proof. Let f is a monovalued reloid. Then exists a function F ∈ up f. So we have
↑
RLD(Src f ;Dst f )
F
|
dom f
=f .
Corollary 82. Every monovalued inject ive reloid is a restricted injective monovalued discrete
reloid.
Proof. Let f is a monovalued injective reloid. There ex ists a function F such that f =
↑
RLD(Src f ;Dst f )
F
|
dom f
. Also there exists an injection G ∈ up f .
Thus f = f ∩
↑
RLD(Src f ;Dst f )
G
|
dom f
=
↑
RLD(Src f ;Dst f )
F
|
dom f
∩
↑
RLD(Src f ;Dst f )
G
|
dom f
=
↑
RLD(Src f ;Dst f )
(F ∩ G)
|
dom f
. Obviously F ∩ G is an injection.
Theorem 83. If a reloid f is monovalued and dom f is a principal f.o. then f is discrete.
Consequences 13
Proof. f is a discrete monovalued reloid. Thus f = F |
dom f
where F is a discrete monovalued
reloids. Thus f is discrete.
Example 84. There exist two atomic reloids whose composition is non-atomic and non-empty.
Proof. Let a is a non-trivial atomic filter object on N and x ∈ N. Then
(a ×
RLD
↑
N
{x}) ◦ (↑
N
{x} ×
RLD
a) =
\
↑
RLD(N;N)
((A × {x}) ◦ ({x} × A)) | A ∈ up a
=
\
↑
RLD(N;N)
(A × A) | A ∈ up a
= a ×
RLD
a
is non-atomic despite of a ×
RLD
↑
N
{x} and ↑
N
{x} ×
RLD
a are atomic.
Example 85. There exists non-monovalued atomic reloid.
Proof. From the previous example f ollows that the atomic reloid ↑
N
{x} ×
RLD
a is not mono-
valued.
Example 86. A >
2
B ∧ B >
2
A but A is not isomorphic to B for some f.o. A and B.
Proof. (proof idea by Andreas Blass, rewritten using reloids by me)
Let u
n
, h
n
with n ranging over the set Z are sequences of atomic f.o. on N and functions N →N
such that
↑
FCD(N;N)
h
n
u
n+1
= u
n
and u
n
are pairwise non-isomorphic. (See [1] for a proof that
such ult rafilters and functions exist.)
A =
def
S
{↑
Z
{n} ×
RLD
u
2n+1
| n ∈ Z}; B =
def
S
{↑
Z
{n} ×
RLD
u
2n
| n ∈ Z}.
Let the Set-morphisms f , g: Z ×N → Z ×N are defined by the formulas f (n; x)= (n; h
2n
x) and
g(n; x) = (n − 1; h
2n−1
x).
Using the fact that every function induces a complete funcoid and a lemma above we ge t:
hf iA =
S
hh↑f ii{↑
Z
{n} ×
RLD
u
2n+1
| n ∈ Z} =
S
{↑
Z
{n} ×
RLD
u
2n
| n ∈ Z} = B.
hg iB =
S
hh↑g ii{↑
Z
{n} ×
RLD
u
2n
| n ∈ Z} =
S
{↑
Z
{n − 1} ×
RLD
u
2n−1
| n ∈ Z} =
S
{↑
Z
{n} ×
RLD
u
2n+1
| n ∈ Z} = A.
It remains to show that A and B are not isomorphic.
Let X ∈ up(↑
Z
{n} ×
RLD
u
2n+1
) for some n ∈ Z . Then if ↑
Z×N
X ∩ A is an atomic f.o. we have
↑
Z×N
X ∩ A = ↑
Z
{n} ×
RLD
u
2n+1
and thus by the theorem 78 is isomorphic to u
2n+1
.
If X
up(↑
Z
{n} ×
RLD
u
2n+1
) for every n ∈ Z then (Z × N) \ X ∈ up(↑
Z
{n} ×
RLD
u
2n+1
) and
thus (Z × N) \ X ∈ up A and thus ↑
Z×N
X ∩ A = ∅.
We have also (↑
Z
{0} ×
RLD
N) ∩ B = (↑
Z
{0} ×
RLD
N) ∩
S
{↑
Z
{n} ×
RLD
u
2n
| n ∈ Z} =
S
{(↑
Z
{0} ×
RLD
N) ∩ ({n} ×
RLD
u
2n
) | n ∈ Z} = ↑
Z
{0} ×
RLD
u
0
(an atomic f.o.).
Thus every atomic f.o. generated as intersecting A with a principal f.o. ↑
Z×N
X is isomorphic
to some u
2n+1
and thus is not isomorphic to u
0
. By the lemma it follows that A and B are non-
isomorphic.
Bib liography
[1] Andreas Blass. Kleene degrees of ultrafilters. In Heinz-Dieter Ebbinghaus, Gert Müller, and Gerald Sacks,
editors, Recursion Theory Week, volume 1141 of Lecture Notes in Mathematics, pages 29–48. Springer Berlin /
Heidelberg, 1985. 10.1007/BFb0076213.
[2] Anatoly Gryzlov. On the rudin-keisler order on ultrafilters. Topology and its Applications, 76(2):151–155, 1997.
[3] Victor Porton. Funcoids and reloids. At http://www.mathematics21.org/binaries/funcoids-reloids.pdf.
[4] Victor Porton. Filters on posets and generalizations. International Journal of Pure and Applied Mathematics,
74(1):55–119, 2012. http://www.mathematics21.org/binaries/filters.pdf.
[5] R. M. Solovay. Maps preserving measures. At
http://math.berkeley.edu/~solovay/Preprints/Rudin_Keisler.pdf, 2011.
[6] Comfort W. W. and Negrepontis S. The theory of ultrafilters. Springer-Verlag, 1974.
14 Section
