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

As an Amazon Associate I earn from qualifying purchases.

In this chapter the term join-semilattice means join-semilattice with least element ?.

Deﬁnition 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]

Deﬁnition 2 . It is said that a function f from a poset A to a poset B preserves ﬁnite joins, when

for every ﬁnite 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 ﬁnite joins iﬀ it preserves binary joins

(f(x t y) = fx t fy) and nullary joins (f (?

A

) = ?

B

).

Deﬁnition 4. A ﬁxed point of a function F is such x that F (x) = x. We will denote Fix(F ) the

set of all ﬁxed 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

Deﬁnition 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 deﬁnition of join.

Corollary 9.

F

Fix(F )

S is deﬁned 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 deﬁnition of meet.

Corollary 11.

d

Fix(F )

S is deﬁned 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 ﬁxed 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:

Deﬁnition 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 iﬀ there is a antitone map s: Up(A) ! A such that

[TODO: deﬁne 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 deﬁnition 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), deﬁned 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 ' deﬁned 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 deﬁned by the formula

(1). Then take F

0

= '

¡1

(1) and deﬁne '

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 deﬁned by the formula (2). Then take '

0

(a) =

1 if a 2 F

0 if a 2/ F

as deﬁned by the formula

(1) and deﬁne 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 iﬀ

d

: Up(A)!A preserves ﬁnite 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 ﬁnite 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 ﬁnite 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 ﬁnite joins, F preserves ﬁnite 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 ﬁxed point (i.e. if D = "

d

D ), then D clearly

belongs to h"i

∗

A; and conversely "a is always a ﬁxed point of F = " ◦

d

since F ("a) = "

d

"a ="a.

Deﬁnition 21. If A, B are two join-semilattices, then Join(A; B) is the (ordered pointwise) set

of ﬁnite 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

.

Deﬁnition 23. Let h: Q ! R be a ﬁnite joins preserving map. Then by deﬁnition 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 deﬁned Join(P ; h) is a ﬁnite 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 ﬁnite 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 ﬁnite 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 satisﬁes 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 ) satisﬁes the second

co-nucleus axiom.

By an other lemma, we have that Join(P ; F ) preserves ﬁnite joins, given that F preserves ﬁnite

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.

Deﬁnition 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)) iﬀ f 2 Join(Q; R)

P

iﬀ f 2 fg 2 R

Q

j g preserves ﬁnite joinsg

P

iﬀ f 2 (R

Q

)

P

and every g = f(x) (for x 2 P ) preserving ﬁnite joins. This is bijectively equivalent (f 7! f

0

) to

f

0

2 (R

P

)

Q

preserving ﬁnite joins.

f

0

2 Join(Q; Pos(P ; R)) iﬀ f

0

preserves ﬁnite joins and f

0

2 Pos(P ; R)

Q

iﬀ f

0

preserves ﬁnite joins

and f

0

2 fg 2 (R

P

)

Q

j g(x) is monotoneg iﬀ f

0

preserves ﬁnite 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.

Deﬁnition 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 ﬁxed 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

ﬁnite join preserving maps P A ! F(B).

Remark 34. The last theorem was proved without using axiom of choice.

6