In this chapter the term join-semilattice means join-semilattice with least element ?.
Definition 1 . A co-frame is the same as a complete co-brouwerian lattice. [TODO: move it above
in the book and use it when appropriate]
Definition 2 . It is said that a function f from a poset A to a poset B preserves finite joins, when
for every finite set S 2 P A such that
F
A
S exists we have
F
B
hf i
∗
S = f
F
A
S.
Obvious 3. A function between join-semilattices preserves finite joins iff it preserves binary joins
(f(x t y) = fx t fy) and nullary joins (f (?
A
) = ?
B
).
Definition 4. A fixed point of a function F is such x that F (x) = x. We will denote Fix(F ) the
set of all fixed points of a function F .
Remark 5. This is based on a Todd Trimble's proof. A shorter but less elementary proof (also
by Todd Trimble) is available at http://ncatlab.org/toddtrimble/published/topogeny
Definition 6. Let A be a join-semilattice. A co-nucleus is a function F : A ! A such that for every
p; q 2 A we have:
1. F (p) v p;
2. F (F (p)) = F (p);
3. F (p t q) = F (p) t F (q).
Proposition 7. Every co-nucleus is a monotone function.
Proof. It follows from F (p t q) = F (p) t F (q).
Lemma 8.
F
Fix(F )
S =
F
S for every S 2 P Fix(F ) for every co-nucleus F .
Proof. Obviously
F
S w x for every x 2 S.
Suppose z w x for every x 2 S for a z 2 Fix(F ). Then z w
F
S.
F (
F
S) w F (x) for every x 2 S. Thus F (
F
S) w
F
x2S
F (x) =
F
S. But F (
F
S) v
F
S. Thus
F (
F
S) =
F
S that is
F
S 2 Fix(F ).
So
F
Fix(F )
S =
F
S by the definition of join.
Corollary 9.
F
Fix(F )
S is defined for every x; y 2 Fix(F ).
Lemma 10 .
d
Fix(F )
S = F (
d
S) for every S 2 P Fix(F ) for every co-nucleus F .
Proof. Obviously F (
d
S) v x for every x 2 S.
Suppose z v x for every x 2 S for a z 2 Fix(F ). Then z v
d
S and thus z v F (
d
S).
So
d
Fix(F )
S = F (
d
S) by the definition of meet.
Corollary 11.
d
Fix(F )
S is defined for every x; y 2 Fix(F ).
1
Obvious 12. Fix(F ) with induced order is a complete lattice.
Lemma 13. If F is a co-nucleus on a co-frame A, then the poset Fix(F ) of fixed points of F , with
order inherited from A, is also a co-frame.
Proof. Let b 2 Fix(F ), S 2 P Fix(F ). Then
b t
Fix(F )
l
Fix(F )
S =
b t
Fix(F )
F
¡
l
S
=
F (b) t F
¡
l
S
=
F
¡
b t
l
S
=
F
¡
l
hb t i
∗
S
=
l
Fix(F )
hb t i
∗
S =
l
Fix(F )
b t
Fix(F )
∗
S:
Definition 14. Upper set is a set X on a poset A such that x 2 X ^ y w x) y 2 X for every y 2 A.
Denote Up(A) the set of upper sets on A ordered reverse to set theoretic inclusion. [TODO: move
it above in the book]
Lemma 15 . The set Up(A) is closed under arbitrary meets and joins.
Proof. Let S 2 P Up(A).
Let X 2
S
S and Y w X for an Y 2 A. Then there is P 2 S such that X 2 P and thus Y 2 P and
so Y 2
S
S. So
S
S 2 Up(A).
Let now X 2
T
S and Y w X for an Y 2 A. Then 8T 2 S: X 2 T and so 8T 2 S: Y 2 T , thus Y 2
T
S.
So
T
S 2 Up(A).
Theorem 16. A poset A is a complete lattice iff there is a antitone map s: Up(A) ! A such that
[TODO: define antitone.]
1. s("p) = p for every p 2 A;
2. D ⊆ "s(D) for every D 2 Up(A).
Moreover, in this case s(D) =
d
D for every D 2 Up(A).
Proof.
). Take s(D) =
d
D.
(. 8x 2 D: x w s(D) from the second formula.
Let 8x 2 D: y v x. Then x 2 "y, D ⊆ "y; because s is an antitone map, thus follows
s(D) w s("y) = y. So 8x 2 D: y v s(D).
That s is the meet follows from the definition of meets.
It remains to prove that A is a complete lattice.
2
Take any subset S of A. Let D be the smallest upper set containing S. (It exists because
Up(A) is closed under arbitrary joins.) This is
D = fx 2 A j 9s 2 S: x w sg:
Any lower bound of D is clearly an upper bound of S since D ⊇ S. Conversely any lower
bound of S is a lower bound of D. Thus S and D have the same set of lower bounds, hence
have the same greatest lower bound.
Proposition 17. [TODO: Move it above in the book.] For any poset A the following are mutually
reverse order isomorphisms between upper sets F (ordered reverse to set-theoretic inclusion) on A
and order homomorphisms ': A
op
! 2 (here 2 is the partially ordered set of two elements: 0 and 1
where 0 v 1), defined by the formulas
1. '(a) =
1 if a 2 F
0 if a 2/ F
for every a 2 A;
2. F = '
¡1
(1).
Proof. Let X 2 '
¡1
(1) and Y w X. Then '(X) = 1 and thus '(Y ) = 1. Thus '
¡1
(1) is a upper set.
It is easy to show that ' defined by the formula (1) is an order homomorphism A
op
! 2 whenever
F is a upper set.
Finally we need to prove that they are mutually inverse. Really: Let ' be defined by the formula
(1). Then take F
0
= '
¡1
(1) and define '
0
(a) by the formula (1). We have
'
0
(a) =
(
1 if a 2 '
¡1
(1)
0 if a 2/ '
¡1
(1)
=
1 if '(a) = 1
0 if '(a) =/ 1
= '(a):
Let now F be defined by the formula (2). Then take '
0
(a) =
1 if a 2 F
0 if a 2/ F
as defined by the formula
(1) and define F
0
= '
0¡1
(1). Then
F
0
= '
0¡1
(1) = F :
Lemma 18 . For a complete lattice A, the map
d
: Up(A) ! A preserves arbitrary meets.
Proof. Let S 2 P Up(A) . We have
d
S 2 Up(A).
d d
S =
d d
X 2S
X =
d
X 2S
d
X is what we needed to prove.
Lemma 19 . A complete lattice A is a co-frame iff
d
: Up(A)!A preserves finite joins.
Proof.
). Let A be a co-frame. Let D; D
0
2 Up(A). Obviously
d
(D t D
0
) w
d
D and
d
(D t D
0
) w
d
D
0
, so
d
(D t D
0
) w
d
D t
d
D
0
.
Also
d
D t
d
D
0
=
S
D t
S
D
0
= (because A is a co-frame)=
S
fd t d
0
j d 2 D; d
0
2 D
0
g.
Obviously d t d
0
2 D \ D
0
, thus
d
D t
d
D
0
⊆
S
(D \ D
0
) =
d
(D \ D
0
) that is
d
D t
d
D
0
w
d
(D \ D
0
). So
d
(D t D
0
) =
d
D t
d
D
0
that is
d
: Up(A)!A preserves
binary joins.
It preserves nullary joins since
d
Up(A)
?
Up(A)
=
d
Up(A)
A = ?
A
.
3
(. Suppose
d
: Up(A)!A preserves finite joins. Let b 2 A, S 2 P A. Let D be the smallest
upper set containing S (so D =
S
h"i
∗
S). We have
d
D =
S
S. So
b t
l
S =
l
"b t
[l
h"i
∗
S =
l
"b t
l [
h"i
∗
S = (since
l
preserves finite joins)
l
¡
"b t
[
h"i
∗
S
=
[
¡
"b \
[
h"i
∗
S
=
l [
a2S
("b \ "a) =
l [
a2S
"(b t a) = (since
l
preserves all meets)
[
a2S
l
"(b t a) =
[
a2S
(b t a) =
l
a2S
(b t a):
Corollary 20. If A is a co-frame, then the composition F = " ◦
d
: Up( A) ! Up(A) is a co-nucleus.
The embedding ": A ! Up(A) is an isomorphism of A onto the co-frame Fix(F ).
Proof. D w F (D) follows from theorem 16.
We have F (F (D)) = F (D) for all D 2 Up(A) since F (F (D)) = "
d
"
d
D = (because
d
"s = s for
any s)="
d
D = F (D).
And since both
d
: Up(A)!A and " preserve finite joins, F preserves finite joins. Thus F is a co-
nucleus.
Finally, we have a w a
0
if and only if "a ⊆ "a
0
, so that ":A ! Up(A) maps A isomorphically onto its
image h"i
∗
A. This image is Fix( F ) because if D is any fixed point (i.e. if D = "
d
D ), then D clearly
belongs to h"i
∗
A; and conversely "a is always a fixed point of F = " ◦
d
since F ("a) = "
d
"a ="a.
Definition 21. If A, B are two join-semilattices, then Join(A; B) is the (ordered pointwise) set
of finite joins preserving maps A ! B.
Obvious 22. Join(A; B) is a join-semilattice, where f t g is given by the formula (f t g)(p) =
f(p) t g(p), ?
Join(A;B)
is given by the formula ?
Join(A;B)
(p) = ?
B
.
Definition 23. Let h: Q ! R be a finite joins preserving map. Then by definition Join(P ; h):
Join(P ; Q) ! Join(P ; R) takes f 2 Join(P ; Q) into the composition h ◦ f 2 Join(P ; R).
Lemma 24 . Above defined Join(P ; h) is a finite joins preserving map.
Proof. (h ◦ (f t f
0
))x = h(f t f
0
)x = h(f x t f
0
x) = h fx t hf
0
x = (h ◦ f )x t (h ◦ f
0
)x =
((h ◦ f) t (h ◦ f
0
))x. Thus h ◦ (f t f
0
) = (h ◦ f ) t (h ◦ f
0
).
¡
h ◦ ?
Join(A;B)
x = h?
Join(A;B)
x = h?
B
= ?
A
.
Proposition 25. If h; h
0
: Q ! R are finite join preserving maps and h w h
0
, then Join(P ;
h) w Join(P ; h
0
).
4
Proof. Join(P ; h)(f)(x) = (h ◦ f )(x) = hfx w h
0
fx = (h
0
◦ f)(x) = Join(P ; h
0
)(f )(x).
Lemma 26. If g: Q ! R and h: R ! S are finite joins preserving, then the composition Join(P ;
h) ◦ Join(P ; g) is equal to Join(P ; h ◦ g). Also Join(P ; id
Q
) for identity map id
Q
on Q is the identity
map id
Join(P ; Q)
on Join(P ; Q).
Proof. Join(P ; h) Join(P ; g) f = Join(P ; h)(g ◦ f ) = h ◦ g ◦ f = Join(P ; h ◦ g)f.
Join(P ; id
Q
) f = id
Q
◦ f = f .
Corollary 27. If Q is a join-semilattice and F : Q! Q is a co-nucleus, then for any join-semilattice
P we have that Join(P ; F ): Join(P ; Q) ! Join(P ; Q) is also a co-nucleus.
Proof. From id
Q
w F (co-nucleus axiom 1) we have Join(P ; id
Q
) w Join(P ; F ) and since by the last
lemma the left side is the identity on Join(P ; Q), we see that Join (P ; F ) also satisfies co-nucleus
axiom 1.
Join(P ; F ) ◦ Join(P ; F )= Join(P ; F ◦ F ) by the same lemma and thus Join (P ; F ) ◦ Join(P ;
F ) = Join(P ; F ) by the second co-nucleus axiom for F , showing that Join(P ; F ) satisfies the second
co-nucleus axiom.
By an other lemma, we have that Join(P ; F ) preserves finite joins, given that F preserves finite
joins, which is the third co-nucleus axiom.
Lemma 28. Fix(Join(P ; F )) = Join(P ; Fix(F )) for every join-semilattices P , Q and a join
preserving function F : Q ! Q.
Proof. a 2 Fix(Join(P ; F )) , a 2 F
P
^ F ◦ a = a , a 2 F
P
^ 8x 2 P : F (a(x)) = a(x) .
a 2 Join(P ; Fix(F )) , a 2 Fix(F )
P
, a 2 F
P
^ 8x 2 P : F (a(x)) = a(x) .
Thus Fix(Join(P ; F )) = Join(P ; Fix(F )). That the order of the left and right sides of the equality
agrees is obvious.
Definition 29. Pos(A; B) is the pointwise ordered poset of monotone maps from a poset A to a
poset B.
Lemma 30. If Q, R are join-semilattices and P is a poset, then Pos(P ; R) is a join-semilattice and
Pos(P ; Join(Q; R )) is isomorphic to Join(Q; Pos(P ; R)). If R is a co-frame, then also Pos(P ; R)
is a co-frame.
Proof. Let f ; g 2 Pos(P; R). Then λx 2 P : (fx t gx) is obviously monotone and then it is evident
that f t
Pos(P ;R)
g = λx 2 P : (fx t gx). λx 2 P : ?
R
is also obviously monotone and it is evident
that ?
Pos(P ;R)
= λx 2 P : ?
R
.
Obviously both Pos(P ; Join(Q; R)) and Join(Q; Pos(P ; R)) are sets of order preserving maps.
Let f be a monotone map.
f 2 Pos(P ; Join(Q; R)) iff f 2 Join(Q; R)
P
iff f 2 fg 2 R
Q
j g preserves finite joinsg
P
iff f 2 (R
Q
)
P
and every g = f(x) (for x 2 P ) preserving finite joins. This is bijectively equivalent (f 7! f
0
) to
f
0
2 (R
P
)
Q
preserving finite joins.
f
0
2 Join(Q; Pos(P ; R)) iff f
0
preserves finite joins and f
0
2 Pos(P ; R)
Q
iff f
0
preserves finite joins
and f
0
2 fg 2 (R
P
)
Q
j g(x) is monotoneg iff f
0
preserves finite joins and f
0
2 (R
P
)
Q
.
So we have proved that f 7! f
0
is a bijection between Pos(P ; Join (Q; R)) and Join(Q; Pos(P; R)).
That it preserves order is obvious.
5
It remains to prove that if R is a co-frame, then also Pos(P ; R) is a co-frame.
First, we need to prove that Pos(P ; R) is a complete lattice. But it is easy to prove that for every
set S 2 P Pos(P ; R) we have λx 2 P :
F
f 2S
f(x) and λx 2 P :
d
f 2S
f(x) are monotone and thus
are the joins and meets on Pos(P ; R).
Next we need to prove that b t
Pos(P ;R)
d
Pos(P ;R)
S =
d
Pos(P ;R)
b t
Pos(P ;R)
∗
S. Really (for every
x 2 P ),
b t
Pos(P ;R)
d
Pos(P ;R)
S
x = b(x) t
d
Pos(P ;R)
S
x = b(x) t
d
f 2S
f(x) =
d
f 2S
(b(x) t f (x)) =
d
f 2S
¡
b t
Pos(P ;R)
f
x =
d
f 2S
Pos(P ;R)
¡
b t
Pos(P ;R)
f
x.
Thus b t
Pos(P ;R)
d
Pos(P ;R)
S =
d
f 2S
Pos(P ;R)
¡
b t
Pos(P ;R)
f
=
d
Pos(P ;R)
b t
Pos(P ;R)
∗
S.
Definition 31. P
=
∼
Q means that posets P and Q are isomorphic.
Theorem 32. If A is a co-frame and L is a distributive lattice with greatest element, then
Join(L; A) is also a co-frame.
Proof. Let F = " ◦
d
: Up(A) ! Up(A); F is a co-nucleus by above.
Since Up(A)
=
∼
Pos(A; 2) by proposition 17, we may regard F as a co-nucleus on Pos(A; 2).
Join(L; A)
=
∼
Join(L; Fix(F )) by corollary 20.
Join(L; Fix(F ))
=
∼
Fix(Join(L; F )) by lemma 28.
By corollary 27 the function Join(L; F ) is a co-nucleus on Join(L; Pos(A; 2)).
Join(L; Pos(A; 2))
=
∼
(by lemma 30)
Pos(A; Join(L; 2))
=
∼
Pos(A; F(X)):
But Pos(A; F( X)) is a co-frame by lemma 30.
Thus Join(L; A) is isomorphic to a poset of fixed points of a co-nucleus on the co-frame Pos(A;
F(X)) . By lemma 13 Join(L; A) is also a co-frame.
Theorem 33. The set of funcoids from a set A to a set B is a co-frame. [TODO: Generalize for
pointfree funcoids.]
Proof. Take A = F (B) in the previous theorem and use the fact that FCD(A; B) is isomorphic to
finite join preserving maps P A ! F(B).
Remark 34. The last theorem was proved without using axiom of choice.
6
