Algebraic General Topology. Vol 1: Paperback / E-book || Axiomatic Theory of Formulas: Paperback / E-book

As an Amazon Associate I earn from qualifying purchases. Orderings of ﬁl ters in terms of reloids
Extensions of Rudin-Keisler ordering
by Victor Porton
August 13, 2013
Abstract
Orderings of lters which extend Rudin-Keisler preorder of ultraﬁlters are described in terms
of reloids that (roughly speaking) is lters on sets of binary relations between some sets. Also
it is deﬁned isomorphism of lters which extends Rudin-Keisler equivalence of ultraﬁlters.
Keywords: Rudin-Keisler order, Rudin-Keisler preorder, Rudin-Keisler ordering, lters,
ultraﬁlters, reloids, isomorphism, isomorphic
A.M.S. subject classiﬁcation: 06F99, 06A99, 54D99
1 Draft status
It is a draft.
2 Preliminary deﬁ nitions
Whilist my other works use ﬁlters to resea rch funcoids and reloids , here it is discussed the
opposite thing, the theory of reloids is used to describe properties of ﬁlters.
See  for the deﬁnition of ﬁlter objects and  for the deﬁnition 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 ﬁlters
We will restrict to small sets that is members of some Grothendieck universe.
Deﬁnition 1. Two lter objects A and B (with possibly diﬀerent base sets) are equivalent (A B)
iﬀ 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 ﬁlter 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 ﬁlter objects is an equivalence relation.
Proof.
Reﬂexivity. 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.
Deﬁnition 4. The rebase A ÷ A for a f.o. A and a set A (base) such that X up A: X A is
deﬁned 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 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 deﬁned 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 ﬁlters
Below I will deﬁne some categories having ﬁlter objects (with possibly diﬀerent bases) as their
objects a nd some relations having two ﬁlter objects (with possibly diﬀerent bases) as arguments
induced by these c ategories (deﬁned as existence of a morphism between these two f.o.).
Theorem 9. card a = card U for every ultraﬁlter a on U if U is inﬁnite.
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 ultraﬁlters on a s et U is the same.
Proof. For inﬁnite U it follows from the theorem. For ﬁnite case it is obvious.
Deﬁnition 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 deﬁne some directed multigraphs. By an abuse of notation, I will denote these multi-
graphs the same as (below deﬁned) 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.
Deﬁnition 12. I will denote GreFunc
1
the multigraph whose objects are lter objects and whose
morphisms between objects A and B are Set-morphisms from Base(A) to Base(B) such that
up B f∗A.
Deﬁnition 13. I will denote GreFunc
2
the multigraph whose objects are lter objects and whose
morphisms between objects A and B are Set-morphisms from Base(A) to Base(B) such that
up B = f ∗A.
Deﬁnition 14. Let A is a f.o. on a set X and B is a f.o. on a set Y . A >
1
B iﬀ Mor
GreFunc
1
(A; B)
is not empty.
Deﬁnition 15. Let A is an f.o. on a set X and B is an f.o. on a set Y . A >
2
B iﬀ Mor
GreFunc
2
(A; B)
is not empty.
Proposition 16.
1. f Mor
GreFunc
1
(A; B) iﬀ 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) iﬀ 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).
Deﬁnition 17. The multigraph FuncBij is the multigraph got from GreFunc
2
by restricting to
only bijective morphisms.
Deﬁnition 18. A f.o. A is directly isomorphic to a f.o. B iﬀ 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 hf 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 iﬀ 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 iﬀ 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 = hgiB = 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 ultraﬁlters being directly isomorphic is the same as being Rudin-
Keisler equivalent.
Deﬁnition 32. A f.o. A is isomorphic to a f.o. B iﬀ 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 ﬁlter objects) is an equivalence relation.
Proof.
Reﬂexivity. 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 ﬁlter 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 ﬁlters 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 ﬁnd 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 ﬁnish 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 iﬀ A ÷ A >
2
B ÷ B.
2. For every A up A and B up B we have A >
1
B iﬀ A ÷ A >
1
B ÷ B.
Proof.
1. A >
2
B iﬀ 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 iﬀ 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 ultraﬁlters is cons idered in such a book as .
Proposition 38. For ultraﬁlters >
2
is the same as Rudin-Keisler ordering.
Proof. x >
2
y iﬀ 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 deﬁnition of Rudin-Keis le r ordering.
6 Section 3 Remark 39. The relation of being isomorphic for ultraﬁlters is traditionally called Rudin-Keisler
equivalence.
Obvious 40. (>
1
) (>
2
).
Deﬁnition 41. Let Q and R a re binary relations on the set of ﬁlter objects. I will denote
MonRld
Q,R
the directed multigraph with objects being ﬁlter 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 ﬁlter 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 testiﬁed 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 ﬁrst 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).
Deﬁnition 45. Let BijRld is the groupoid of all bijections of the category of reloid triples. Its
objects are ﬁlter 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 iﬀ 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|
PAup A
is a bijection PA up A PB up B.
So ﬁlter objects A and B are isomorphic.
Proposition 47. (>
1
) = () (>
2
) (when we limit to small f.o.).
Proof. A >
1
B iﬀ 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 ﬁlter 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 ﬁlter objects
3.1.1 The lemmas
The lemm as in this section were provided to me by Robert Martin Solovay in . These are based
on Wistar Comfort’s work.
In this section we will assume µ is an ultraﬁlter 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 deﬁne x y iﬀ 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 iﬀ 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 deﬁned by the relation .
Let α is a function A N deﬁned 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
n1
(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
n1
(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
ij
(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.
Deﬁne 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-deﬁned.
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 ﬁxed points of f. Thus the set of ﬁxed points of f belongs
to the ﬁlter µ.
3.1.2 The main theorem and its consequences
Theorem 59. For every atomic ﬁlter 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 ﬁlter objects (with p ossibly diﬀerent 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 diﬀerent 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 ﬁlter objects a and b (with possibly diﬀerent bases) are isomorphic iﬀ
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 ﬁlters 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 )=
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 .
Theorem 69. >
1
and >
2
are diﬀerent 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 ﬁlters, 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 ﬁlter 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 ﬁlter 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 inﬁnite set U there exist 2
2
cardU
equivalence classes of isomorphic ultraﬁlters.
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-
ﬁlters. But there are 2
2
card U
ultraﬁlters. So there are 2
2
card U
classes.
Remark 76. One of the above mentioned equivalence cla sses c ontains trivial ultraﬁlters.
Corollary 77. There exist non-isomorphic nontrivial ultraﬁlters on any inﬁnite set.
5 Consequen ces
Theorem 78. The reloid
A
{a} ×
RLD
F is isomorphic to the ﬁlter 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 suﬃces to prove that
RLD(Src f ;Dst f )
F
|
dom f
is atomic.
Let the function τ : dom F F is deﬁned 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 ﬁlter 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 ﬁlter 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  for a proof that
such ult raﬁlters 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 deﬁned by the formulas f (n; x)= (n; h
2n
x) and
g(n; x) = (n 1; h
2n1
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
2n1
| 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
 Andreas Blass. Kleene degrees of ultraﬁlters. 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.
 Anatoly Gryzlov. On the rudin-keisler order on ultraﬁlters. Topology and its Applications, 76(2):151–155, 1997.
 Victor Porton. Funcoids and reloids. At http://www.mathematics21.org/binaries/funcoids-reloids.pdf.
 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.
 R. M. Solovay. Maps preserving measures. At
http://math.berkeley.edu/~solovay/Preprints/Rudin_Keisler.pdf, 2011.
 Comfort W. W. and Negrepontis S. The theory of ultralters. Springer-Verlag, 1974.
14 Section 