Todd Trimble
topogeny

Contents

Introduction

These are notes that were made in response to a reading of Victor Porton’s online work titled Algebraic General Topology. This work is a study of general notions of “space” (proximity spaces, pretopological spaces, and the like) from Porton’s idiosyncratic point of view, centering on the concepts that he calls “funcoid” and “reloid”.

Despite the poor reception of this work (some of it justifiable, as Porton employs a heavy symbolism, and some key results are deeply buried), there is some real structural content to his work. In particular, the central concept of “funcoid” is in fact connected with such varied notions as Chu spaces, coherence spaces, syntopogenous spaces, flat profunctors, interchange of finite limits and filtered colimits, … The purpose of these notes is to bring out some of these connections in a concise way, so that some points of his work might be better appreciated, especially by members of the categorical community who deal in abstract topology.

I have titled this page “topogeny”, both as a proposed catch-all term for doing topology from a point of view that takes nearness relations as primitive, and also as a euphonious and grammatically versatile term that can cover various senses of “funcoid” as they recur in various cryptomorphically equivalent ways.

Preliminary observations

In this section we collect various facts about the set of filters Filt(X)Filt(X) on a set XX, which are needed in the sequel.

Proposition

The poset of filters on a set XX (i.e., in the Boolean algebra PXP X), ordered by inclusion, is a frame, in fact isomorphic to the frame of open sets of βX\beta X.

Proof

The topology of βX\beta X is the Zariski topology of the Boolean ring PXP X, with ideals/filters corresponding to closed sets; we thus have a Galois correspondence between filters and closed sets in βX\beta X, so that the poset of filters under inclusion is isomorphic to the poset of open sets of βX\beta X under inclusion.

Remark

Proposition 1 can also be proven in a “point-free” way, removing all reference to ultrafilters = points of βX\beta X. In fact, for any distributive lattice LL, the poset of filters in LL ordered by inclusion, isomorphic to Lex(L,2)Lex(L, \mathbf{2}), is itself a distributive lattice in which there is also interchange between finite limits and filtered colimits, so that finite meets distribute over arbitrary joins and Lex(L,2)Lex(L, \mathbf{2}) is a frame. The proof is constructive and may be internalized in any topos; see Corollary 1 below.

In the next proposition, \vee denotes the join in the lattice Filt(X)Filt(X), and \top denotes the top element (the improper filter PXP X).

Proposition

The map Φ X:Filt(X)P(Filt(X))\Phi_X: Filt(X) \to P(Filt(X)) mapping F{G:FG}F \mapsto \{G: F \vee G \neq \top\} is injective.

Proof

We have that F=(β(X)Φ X(F))F = \bigcap (\beta(X) \cap \Phi_X(F)), because every filter is the intersection of the ultrafilters that contain it. More elementarily (without using AC): we have (A:PX)AFprin(¬A)Φ X(F)(\forall A: P X)\; A \in F \Leftrightarrow prin(\neg A) \notin \Phi_X(F).

The last proposition suggests a Chu space (see also Pratt) with carrier Filt(X)Filt(X), given by a triple

Ch(X)(Filt(X),Filt(X),Filt(X)×Filt(X)R X2)Ch(X) \coloneqq (Filt(X), Filt(X), Filt(X) \times Filt(X) \stackrel{R_X}{\to} \mathbf{2})

where R X(F,G)R_X(F, G) is the truth value of FGF \vee G \neq \top. The previous proposition says that Ch(X)Ch(X) is a separable Chu space (Pratt, p. 4). It is also clearly a self-dual Chu space, since RR is a symmetric relation.

Lemma

R X(FF,G)=R X(F,G)R X(F,G)R_X(F \wedge F', G) = R_X(F, G) \vee R_X(F', G).

Proof

By distributivity in the frame Filt(X)Filt(X), we have (FF)G=(FG)(FG)\top \leq (F \wedge F') \vee G = (F \vee G) \wedge (F' \vee G) iff both FG\top \leq F \vee G and FG\top \leq F' \vee G. Taking negations on both sides of the “iff” gives the result.

Lemma

Given diagram ϕ:DFilt(X)\phi: D \to Filt(X), with DD filtered, R X(colim dDϕ(d),G)= dDR X(ϕ(d),G)R_X(colim_{d\in D}\; \phi(d), G) = \forall_{d \in D} R_X(\phi(d), G).

Proof

Since DD is inhabited, we have (colim dϕ(d))G=colim d(ϕ(d)G)(colim_d\; \phi(d)) \vee G = colim_d\; (\phi(d) \vee G). As βX\beta X is compact, the frame Filt(X)=𝒪(β(X))Filt(X) = \mathcal{O}(\beta(X)) is compact in the sense that hom(,):Filt(X)2\hom(\top, -): Filt(X) \to \mathbf{2} preserves filtered colimits, i.e.,

colim d(ϕ(d)G)iff( d)ϕ(d)G.\top \leq colim_d\; (\phi(d) \vee G) \;\;\; iff \;\;\; (\exists_d) \top \leq \phi(d) \vee G.

Taking negations on both sides of this “iff” shows that R X(colim dDϕ(d),G)R_X(colim_{d\in D}\; \phi(d), G) holds iff ( dD)R X(ϕ(d),G)(\forall_{d\in D})\; R_X(\phi(d), G) holds.

Porton’s definition of funcoid

Definition

Let X,YX, Y be sets. A funcoid from XX to YY is a Chu space morphism Ch(X)Ch(Y)Ch(X) \to Ch(Y).

This is not how Porton phrases it, but it’s the same as his notion. In more detail: a funcoid ff from XX to YY consists of a pair of functions α:Filt(X)Filt(Y)\alpha: Filt(X) \to Filt(Y) and β:Filt(Y)Filt(X)\beta: Filt(Y) \to Filt(X) such that for all FFilt(X),GFilt(Y)F \in Filt(X), G \in Filt(Y) the following condition is satisfied:

Gα(F)iffFβ(G).G \vee \alpha(F) \neq \top \;\;\;\; iff \;\;\;\; F \vee \beta(G) \neq \top.

In other words, R Y(α(F),G)=R X(F,β(G))R_Y(\alpha(F), G) = R_X(F, \beta(G)).

Evidently there is a category of sets and funcoids between them. Because each Chu space Ch(X)Ch(X) is self-dual, this actually gives a \dagger-category.

Basic results

The modes of argument that Porton employs to establish some basic results may be cast in a form familiar to those who have worked a little with Chu spaces. A key fact is separability (see Proposition 2 and the remark that follows on the Chu space Ch(X)Ch(X)).

For f=(α,β)f = (\alpha, \beta) a funcoid XYX \to Y, we follow Porton’s notation and let [f][f] be the relation R Y(α(),)=R X(,β())R_Y(\alpha(-), -) = R_X(-, \beta(-)).

Lemma

Each component α,β\alpha, \beta of a funcoid ff determines the other. Either is determined uniquely from [f][f].

Proof

Suppose (α,β)(\alpha, \beta) and (α,β)(\alpha, \beta') are funcoids. Then for all GFilt(Y)G \in Filt(Y) we have R X(,β(G))=R X(,β(G))R_X(-, \beta(G)) = R_X(-, \beta'(G)) since both sides equal R Y(α(),G)R_Y(\alpha(-), G). Hence β(G)=β(G)\beta(G) = \beta'(G) by separability, for all GG; i.e., β=β\beta = \beta'. Similarly, if (α,β)(\alpha, \beta) and (α,β)(\alpha', \beta) are funcoids, then α=α\alpha = \alpha'. The same argument shows both the functions α\alpha and β\beta are uniquely determined from the relation [f][f].

Lemma

For a funcoid f=(α,β)f = (\alpha, \beta) from XX to YY, we have that α:Filt(X)Filt(Y)\alpha: Filt(X) \to Filt(Y) preserves finite meets.

Proof

(Compare Porton, Proposition 6.13.) With the help of Lemma 1, we have

R Y(α(FF),G) = R X(FF,β(G)) = R X(F,β(G))R X(F,β(G) = R Y(α(F),G)R Y(α(F),G) = R Y(α(F)α(F),G)\array{ R_Y(\alpha(F \wedge F'), G) & = & R_X(F \wedge F', \beta(G)) \\ & = & R_X(F, \beta(G)) \vee R_X(F', \beta(G) \\ & = & R_Y(\alpha(F), G) \vee R_Y(\alpha(F'), G) \\ & = & R_Y(\alpha(F) \wedge \alpha(F'), G) }

whence α(FF)=α(F)α(F)\alpha(F \wedge F') = \alpha(F) \wedge \alpha(F') by separability. A similar argument shows that α()=\alpha(\top) = \top.

Lemma

For a funcoid f=(α,β)f = (\alpha, \beta) from XX to YY, we have that α:Filt(X)Filt(Y)\alpha: Filt(X) \to Filt(Y) preserves filtered colimits.

Proof

(Compare Porton, Theorem 6.25.) For a filtered diagram ϕ:DFilt(X)\phi: D \to Filt(X), we have with the help of Lemma 2 the following calculation:

R Y(α(colim dϕ(d)),G) = R X(colim dϕ(d),β(G)) = ( d)R X(ϕ(d),β(G)) = ( d)R Y(α(ϕ(d)),G) = R Y(colim dα(ϕ(d)),G)\array{ R_Y(\alpha(colim_d\; \phi(d)), G) & = & R_X(colim_d\; \phi(d), \beta(G)) \\ & = & (\forall_d)\; R_X(\phi(d), \beta(G)) \\ & = & (\forall_d)\; R_Y(\alpha(\phi(d)), G) \\ & = & R_Y(colim_d\; \alpha(\phi(d)), G) }

whence α(colim dϕ(d))=colim dα(ϕ(d))\alpha(colim_d\; \phi(d)) = colim_d\; \alpha(\phi(d)) by separability.

We state now a key theorem which gives a cryptomorphically equivalent notion of funcoid.

Theorem

A map α:Filt(X)Filt(Y)\alpha: Filt(X) \to Filt(Y) preserves finite limits and filtered colimits if and only if α\alpha is the component of a funcoid from XX to YY.

We prove this in the next section. Since just one component α\alpha uniquely determines a funcoid (α,β)(\alpha, \beta), the theorem says we may equivalently define a funcoid from XX to YY as a map Filt(X)Filt(Y)Filt(X) \to Filt(Y) that preserves finite limits and filtered colimits.

Remark

This formulation is vaguely reminiscent of the notion of stable function between coherence spaces, due to Girard. I’m not sure how much to make of this however.

Topogenies

Let XX, YY be sets. The following definition is adapted from syntopogenous space.

Definition

A topogeny from XX to YY is a relation ξ:PX×PY2\xi: P X \times P Y \to \mathbf{2} that preserves coproducts in each separate argument. More concretely:

  1. ξ(A,)\xi(A, \emptyset) and ξ(,B)\xi(\emptyset, B) are false, for all APX,BPYA \in P X, B \in P Y;

  2. ξ(A,CD)\xi(A, C \cup D) if and only if (ξ(A,C)\xi(A, C) or ξ(A,D)\xi(A, D)), and ξ(AB,C)\xi(A \cup B, C) if and only if (ξ(A,C)\xi(A, C) or ξ(B,C)\xi(B, C)).

Note that if CDC \subseteq D, then ξ(A,C)\xi(A, C) implies ξ(A,D)\xi(A, D) since D=CDD = C \cup D; similarly, if ABA \subseteq B, then ξ(A,C)\xi(A, C) implies ξ(B,C)\xi(B, C). Thus the “if” clauses of condition 2. in the definition of topogeny are equivalent to the monotonicity of ξ:PX×PY2\xi: P X \times P Y \to \mathbf{2}.

For a basic and instructive example of a topogeny, consider a metric space (X,d)(X, d), and define a “nearness” relation ξ\xi where two subsets A,BA, B are near (or ξ(A,B)\xi(A, B)) if the distance between them is zero, viz. inf{d(x,y):xA,yB}=0\inf\; \{d(x, y): x \in A, y \in B\} = 0.

Proposition

There is a natural bijection between topogenies from XX to YY and maps α:Filt(X)Filt(Y)\alpha: Filt(X) \to Filt(Y) that preserve finite limits and filtered colimits.

This gives another cryptomorphically equivalent view on funcoids (for Porton, perhaps the most important one, as various general notions of space can be viewed as special types of topogenous relations on sets).

Proof

Filt(X)Filt(X) is the filtered colimit completion (in the 22-category of preorders or 2\mathbf{2}-enriched categories) of (PX) op(P X)^{op}; otherwise put, Filt(X)Lex(PX,2)Filt(X) \cong Lex(P X, \mathbf{2}). The “Yoneda embedding” prin:(PX) opLex(PX,2)prin: (P X)^{op} \to Lex(P X, \mathbf{2}), which is the universal map from (PX) op(P X)^{op} to filtered-cocomplete posets, preserves finite limits. Thus, for any α:Filt(X)Filt(Y)\alpha: Filt(X) \to Filt(Y) that preserves finite limits and filtered colimits, the restriction

αprin:(PX) opFilt(Y)\alpha \circ prin: (P X)^{op} \to Filt(Y)

preserves finite limits.

In the other direction, because finite limits commute with filtered colimits in Filt(Y)=Lex(PY,2)Filt(Y) = Lex(P Y, \mathbf{2}), the filtered-cocontinuous extension of any left exact (PX) opFilt(Y)(P X)^{op} \to Filt(Y) is also left exact. Thus we have a natural bijection

(PX) opLex(PY,2)lexFilt(X)Filt(Y)lex,filtered-cocontinuous\frac{(P X)^{op} \to Lex(P Y, \mathbf{2}) \;\;\; lex}{Filt(X) \to Filt(Y) \;\;\; lex, \; \text{filtered-cocontinuous}}

We also have an isomorphism Lex(PY,2)Rex(PY,2) opLex(P Y, \mathbf{2}) \cong Rex(P Y, \mathbf{2})^{op} that takes ϕ:PY2\phi: P Y \to \mathbf{2} to (λB:PY)(¬ϕ(¬B))(\lambda B: P Y)(\neg\phi(\neg B)). Left exact maps (PX) opLex(PY,2)(P X)^{op} \to Lex(P Y, \mathbf{2}) are thus in bijection with right exact maps PXRex(PY,2)P X \to Rex(P Y, \mathbf{2}), i.e., with maps PX×PY2P X \times P Y \to \mathbf{2} that preserve finite colimits in each variable, which are topogenies.

This proposition enables one to define a category of sets and topogenies between them, simply by associating identity and composite topogenies with the corresponding maps Filt(X)Filt(Y)Filt(X) \to Filt(Y). In detail, the identity topogeny on XX is derived from a map PXRex(PX,2)P X \to Rex(P X, \mathbf{2}), mapping

A{B:¬Bprin(A)},A \mapsto \{B: \neg B \notin prin(A)\},

where the condition on BB says A¬BA \subseteq \neg B is false, or ABA \cap B \neq \emptyset. Thus the identity topogeny is the relation consisting of pairs (A,B)PX×PX(A, B) \in P X \times P X such that ABA \cap B is inhabited.

While it is true that topogenies are closed under relational composition, this isn’t the composition that corresponds to composing maps Filt(X)Filt(Y)Filt(X) \to Filt(Y) (noting in particular that the identity topogeny doesn’t behave as an identity under relational composition). To get the “correct” composition, we use the fact that topogenies ξ:PX×PY2\xi: P X \times P Y \to \mathbf{2} correspond to “flat profunctors” ϕ:PX op×PY2\phi: P X^{op} \times P Y \to \mathbf{2} (where ϕ\phi takes coproducts AAA \cup A' in the argument PXP X to products and products BBB \cap B' in the argument PYP Y to products) under the correspondence ϕ(A,B)=¬ξ(A,¬B)\phi(A, B) = \neg \xi(A, \neg B). The composition of flat profunctors is relational composition; working through the correspondence, one arrives at the following definition.

Definition

If ν:XY\nu: X \to Y and ξ:YZ\xi: Y \to Z are topogenies, then their topogenic composite ξν:XZ\xi \circ \nu: X \to Z is defined by the rule

(ξν)(A,C)¬(B:PY)¬ν(A,¬B)¬ξ(B,C).(\xi \circ \nu)(A, C) \coloneqq \neg (\exists B: P Y) \neg \nu(A, \neg B) \wedge \neg \xi(B, C).

Proposition 3, together with the symmetry of the notion of topogeny (i.e., the fact that each topogeny from XX to YY is tantamount to a topogeny from YY to XX), enables us to associate to each lex filtered-cocontinuous α:Filt(X)Filt(Y)\alpha: Filt(X) \to Filt(Y) a lex filtered-cocontinuous β:Filt(Y)Filt(X)\beta: Filt(Y) \to Filt(X). Tracing through the correspondences above, and using the fact that a filter GFilt(Y)G \in Filt(Y) is a filtered colimit of principal filters, here is the formula:

β(G)= BG{A:¬Bα(prin(¬A))}\beta(G) = \bigvee_{B \in G} \{A: \; \neg B \in \alpha(prin(\neg A))\}
Proposition

Given a lex filtered-cocontinuous map α:Filt(X)Filt(Y)\alpha: Filt(X) \to Filt(Y), and with β\beta as given above, we have α(F)G\top \leq \alpha(F) \vee G if and only if Fβ(G)\top \leq F \vee \beta(G). In other words, the pair (α,β)(\alpha, \beta) is a funcoid from XX to YY.

Proof

We have α(F)G\top \leq \alpha(F) \vee G precisely when there is Bα(F)B \in \alpha(F) and BGB' \in G such that BB=B \cap B' = \emptyset. We may write FF as a filtered colimit of principal filters prin(A)prin(A) with AFA \in F; since α\alpha preserves filtered colimits, the condition may be rewritten

(B:PY)(B:PY)(A:PX)(AF)(Bα(prin(A)))(BG)(BB=).(\exists B: P Y)(\exists B': P Y)(\exists A: P X)\; (A \in F) \wedge (B \in \alpha(prin(A))) \wedge (B' \in G) \wedge (B \cap B' = \emptyset).

For such B,BB, B' we have B¬BB' \subseteq \neg B, so by upward closure of GG the condition may be condensed to the equivalent

(1)(B:PY)(A:PX)(AF)(Bα(prin(A)))(¬BG).(\exists B: P Y)(\exists A: P X)\; (A \in F) \wedge (B \in \alpha(prin(A))) \wedge (\neg B \in G).

Coming from the other direction: we have Fβ(G)\top \leq F \vee \beta(G) precisely when there is AFA \in F and Aβ(G)A' \in \beta(G) such that AA=A \cap A' = \emptyset. Spelling this out, this may be rewritten as

(A:PX)(A:PX)(B:PY)(AF)(¬Bα(prin(¬A)))(BG)(AA=).(\exists A: P X)(\exists A': P X)(\exists B: P Y)\; (A \in F) \wedge (\neg B \in \alpha(prin(\neg A'))) \wedge (B \in G) \wedge (A \cap A' = \emptyset).

For such A,AA, A' we have A¬AA \subseteq \neg A', so the last condition may be condensed down to

(A:PX)(A:PX)(B:PY)(AF)(¬Bα(prin(A)))(BG)(\exists A: P X)(\exists A': P X)(\exists B: P Y)\; (A \in F) \wedge (\neg B \in \alpha(prin(A))) \wedge (B \in G)

which matches (1) since we can swap BB and ¬B\neg B, and we are done.

We now have all we need to establish Theorem 1:

Proof

(Theorem 1) Combine Proposition 4 with Lemmas 4 and 5.

Remark

We now have at least four ways in which to view “funcoids”:

  • As Chu space morphisms Ch(X)Ch(Y)Ch(X) \to Ch(Y),

  • As left exact Scott-continuous maps Filt(X)Filt(Y)Filt(X) \to Filt(Y),

  • As flat or meet-preserving profunctors of type PX opPYP X^{op} \to P Y,

  • As topogenies or separately join-preserving maps PX×PY2P X \times P Y \to \mathbf{2}.

Compare Porton, Theorem 6.28. So we have plenty of formulations to choose from, some more convenient than others for a given purpose.

As an example, let us prove the following lemma (compare Porton, Theorem 6.86). In fact we give two proofs; the second proof does not use the axiom of choice, settling a query of Porton.

Lemma

The poset of funcoids from a set XX to a set YY is a frame.

Proof

(This proof is a reformulation of Porton’s proof, and uses the axiom of choice, specifically the fact that every proper filter is contained in an ultrafilter, which is slightly weaker than AC.) As in the proof of Proposition 3, the poset of funcoids is isomorphic to the poset Lex((PX) op,Filt(Y))Lex((P X)^{op}, Filt(Y)), or equivalently Lex(PX,Filt(Y))Lex(P X, Filt(Y)) since negation provides an isomorphism (PX) opPX(P X)^{op} \cong P X. Now Filt(Y)=𝒪(βY)Filt(Y) = \mathcal{O}(\beta Y) (cf. Proposition 1) is a sober spatial frame, so that (abbreviating 𝒪(βY)\mathcal{O}(\beta Y) to 𝒪\mathcal{O}) there is a frame embedding

j:Filt(Y)2 pt(𝒪)j: Filt(Y) \hookrightarrow \mathbf{2}^{pt(\mathcal{O})}

and this induces an embedding

Lex(PX,Filt(Y))Lex(PX,2 pt(𝒪))Lex(PX,2) pt(𝒪)Lex(P X, Filt(Y)) \hookrightarrow Lex(P X, \mathbf{2}^{pt(\mathcal{O})}) \cong Lex(P X, \mathbf{2})^{pt(\mathcal{O})}

that preserves finite meets and arbitrary joins (note this embedding is a left adjoint because we have an adjunction jj *j \dashv j_\ast of left exact maps, and Lex(PX,)Lex(P X, -) will preserve that adjunction). The codomain is a power of the frame Lex(PX,2)Filt(X)Lex(P X, \mathbf{2}) \cong Filt(X) and is thus a frame itself; the domain Lex(PX,Filt(Y))Lex(P X, Filt(Y)), being closed under finite meets and arbitrary joins, is a subframe, as was to be shown.

Second proof

We prove a more general fact: that if LL is any frame, then Lex((PX) op,L)Lex((P X)^{op}, L) is also a frame. Then apply this to L=Filt(Y)L = Filt(Y).

Indeed, a frame LL is precisely a lex-total poset, i.e., a poset with the property that the Yoneda-Dedekind embedding y:L[L op,2]y: L \to [L^{op}, \mathbf{2}] has a left exact left adjoint σ:[L op,2]L\sigma: [L^{op}, \mathbf{2}] \to L. Applying the functor Lex((PX) op,)Lex((P X)^{op}, -) to this adjunction σy\sigma \dashv y (both left exact maps), we get an induced adjunction with right adjoint

Lex((PX) op,L) Lex((PX) op,y) Lex((PX) op,[L op,2]) [L op,Lex((PX) op,2)] [L op,Filt(X)].\array{ Lex((P X)^{op}, L) & \stackrel{Lex((P X)^{op}, y)}{\to} & Lex((P X)^{op}, [L^{op}, \mathbf{2}]) \\ & \cong & [L^{op}, Lex((P X)^{op}, \mathbf{2})] \\ & \cong & [L^{op}, Filt(X)]. }

Since Filt(X)Filt(X) is a frame, so is [L op,Filt(X)][L^{op}, Filt(X)]. We thus have realized Lex((PX) op,L)Lex((P X)^{op}, L) as the category of algebras (or poset of fixed points) of a left exact monad (aka a nucleus) on a frame [L op,Filt(X)][L^{op}, Filt(X)]. By a well-known result in locale theory (see for example Mac Lane-Moerdijk, section IX.4, Proposition 3), this implies Lex((PX) op,L)Lex((P X)^{op}, L) is a frame, as was to be shown.

Remark

Slightly more generally, if DD is a distributive lattice and LL is a frame, then Lex(D,L)Lex(D, L) is a frame. The same method of proof applies, by exhibiting Lex(D,L)Lex(D, L) as the lattice of fixed points of a nucleus on the frame [L op,Filt(D)][L^{op}, Filt(D)], where Filt(D)Lex(D,2)Filt(D) \cong Lex(D, \mathbf{2}) is a frame by Corollary 1, given in an appendix below.

As a second example, we consider a generalization of Lemma 6, involving something Porton calls a “staroid” which generalizes the notion of topogeny.

Definition

(Porton) For a finite cardinal nn, given sets X 1,,X nX_1, \ldots, X_n, an (nn-)staroid on these sets is a function ϕ:PX 1××PX n2\phi: P X_1 \times \ldots \times P X_n \to \mathbf{2} which preserves finite joins in separate arguments.

Porton also has a notion of nn-staroid for infinite nn, one which is apparently stronger than the obvious generalization of the previous definition.

Theorem

The poset of nn-staroids under the pointwise order is a co-frame. More generally, if L 1,,L nL_1, \ldots, L_n are distributive lattices, then the poset of maps ϕ:L 1××L n2\phi: L_1 \times \ldots \times L_n \to \mathbf{2} which preserve joins in separate arguments is a co-frame.

Proof

(See also this MO discussion.) This poset is isomorphic to the poset of join-preserving maps ψ:LL 1L n2\psi: L \coloneqq L_1 \otimes \ldots \otimes L_n \to \mathbf{2}. This tensor product LL is a distributive lattice by Proposition 8. The poset of such ψ\psi is dual to the poset of ideals in LL, or to the poset of filters in L opL^{op}, where L opL^{op} is also a distributive lattice. Then apply Corollary 1.

The description of staroids can be considerably sharpened in fact:

Proposition

If X 1,,X nX_1, \ldots, X_n are sets, then the poset of staroids ψ:PX 1××PX n2\psi: P X_1 \times \ldots \times P X_n \to \mathbf{2} is isomorphic to the co-frame of closed subsets of βX 1××βX n\beta X_1 \times \ldots \times \beta X_n.

Proof

This poset is dual to the frame of ideals of the distributive lattice PX 1PX nP X_1 \otimes \ldots \otimes P X_n which, by Proposition 9, is the coproduct iPX i\sum_i P X_i in the category of Boolean algebras. By Stone duality, the poset of ideals in the Boolean algebra iPX i\sum_i P X_i is isomorphic to the topology of its spectrum βX 1××βX n\beta X_1 \times \ldots \times \beta X_n.

This gives yet another view on funcoids or topogenies from XX to YY (cf. Remark 3): they are tantamount to

From this point of view, a topogeny from XX to YY is precisely a relation from βX\beta X to βY\beta Y in the pretopos of compact Hausdorff spaces. Composition of funcoids or topogenies corresponds to ordinary relational composition within this pretopos (to be checked carefully).

Reflexive topogenies

At this point I am going to switch over to using the word ‘topogeny’, which I much prefer (aesthetically) to ‘funcoid’. At the same time, the most useful point of view on topogenies between sets X,YX, Y is that they are equivalent to closed subsets CβX×βYC \hookrightarrow \beta X \times \beta Y: this allows us to bring the considerable literature on ultrafilter theory to bear on problems.

Apparently Porton is interested in the category whose objects are sets XX that come equipped with an endotopogeny CβX×βXC \hookrightarrow \beta X \times \beta X, i.e., a topogeny from XX to itself. The morphisms are continuous maps:

Definition

Let (X,C X)(X, C_X) and (Y,C Y)(Y, C_Y) be sets equipped with topogenies. A continuous map between them is a function f:XYf: X \to Y such that for ultrafilters F,GβXF, G \in \beta X, we have C X(F,G)C_X(F, G) implies C Y(β(f)(F),β(f)(G))C_Y(\beta(f)(F), \beta(f)(G)).

For various reasons, we will be particularly interested in the full subcategory whose objects are sets XX with reflexive topogenies, i.e., endotopogenies on XX that contain the diagonal of βX×βX\beta X \times \beta X. We will call such topogenic spaces. Clearly, the lattices of endotopogenies and of reflexive topogenies are complete lattices (where meets are given by set-theoretic intersections of closed sets, and joins are closures of set-theoretic unions).

Proposition

The category of endotopogenies and the category of topogenic spaces, taken with their obvious forgetful functors to SetSet, are topological over SetSet.

Proof

If f:XYf: X \to Y is a function and CC is an endotopogeny on YY, then there is an induced endotopogeny f *C(β(f)×β(f)) 1(C)βX×βXf^\ast C \coloneqq (\beta(f) \times \beta(f))^{-1}(C) \subseteq \beta X \times \beta X by pulling back. This f *Cf^\ast C is the largest endotopogeny on XX that renders ff continuous, and is the initial structure that lifts f:XYf: X \to Y seen as a source diagram.

More generally, given a source diagram f i:XX if_i: X \to X_i of sets where X iX_i have given endotopogenies C iC_i, the initial lift is the meet of the endotopogenies f i *C if_i^\ast C_i on XX. This shows that the forgetful functor is topological. The case for topogenic spaces is wholly similar.

Similarly, if CC is an endotopogeny on XX and f:XYf: X \to Y, then the direct image f *C(β(f)×β(f))(C)βY×βYf_\ast C \coloneqq (\beta(f) \times \beta(f))(C) \subseteq \beta Y \times \beta Y is the smallest endotopogeny on YY that renders ff continuous. This is the final structure that lifts f:XYf: X \to Y seen as a sink diagram. Final lifts of sink diagrams f i:Y iYf_i: Y_i \to Y are obtained by taking joins of the endotopogenies (f i) *C i(f_i)_\ast C_i.

Corollary

The category of endotopogenies and the category of topogenic spaces is complete and cocomplete. In fact, each of those categories is both total and cototal.

Appendix

Here we collect some order-theoretic and topological results that were used in the account above.

Filters in distributive lattices

Here we prove that the poset of filters Filt(L)Lex(L,2)Filt(L) \cong Lex(L, \mathbf{2}) in a distributive lattice LL is a frame.

Lemma

Let LL be a distributive lattice. Then Lex(L,2)Lex(L, \mathbf{2}) is also a distributive lattice.

Proof

If F,FLF, F' \subseteq L are two filters, then their meet may be calculated as

FF={xy:xF,yF}F \wedge F' = \{x \vee y: x \in F, y \in F'\}

and their join as

FF={z:(xF,yF)xyz}.F \vee F' = \{z: (\exists x \in F, y \in F')\; x \wedge y \leq z\}.

The inclusion (FG)(FH)F(GH)(F \wedge G) \vee (F \wedge H) \leq F \wedge (G \vee H) holds in any lattice, and we have

zF(GH) (aF,bG,cH,dL)z=adandbcd (aF,bG,cH)a(bc)z (aF,bG,cH)(ab)(ac)z z(FG)(FH)\array{ z \in F \wedge (G \vee H) & \vdash & (\exists a \in F, b \in G, c \in H, d \in L) \; z = a \vee d \; and \; b \wedge c \leq d \\ & \vdash & (\exists a \in F, b \in G, c \in H)\; a \vee (b \wedge c) \leq z \\ & \vdash & (\exists a \in F, b \in G, c \in H)\; (a \vee b) \wedge (a \vee c) \leq z \\ & \vdash & z \in (F \wedge G) \vee (F \wedge H) }

which completes the proof.

Lemma

For any poset LL, finite meets distribute over filtered joins in Lex(L,2)Lex(L, 2).

Proof

Certainly finite meets distribute over arbitrary joins in [L,2][L, \mathbf{2}]. Since the inclusion Lex(L,2)[L,2]Lex(L, \mathbf{2}) \hookrightarrow [L, \mathbf{2}] is closed under finite meets and filtered joins, the result follows.

Corollary

If LL is a distributive lattice, then Lex(L,2)Lex(L, \mathbf{2}) is a frame.

Proof

The preceding lemmas show that FF \wedge - preserves finite joins and filtered joins, and therefore arbitrary joins.

Tensor products of distributive lattices

Proposition

Let P,QP, Q be join-semilattices, considered as commutative monoids. Then the commutative monoid PQP \otimes Q is idempotent.

Proof

Certainly each element aba \otimes b is idempotent, since ab=(a+a)b=ab+aba \otimes b = (a + a) \otimes b = a \otimes b + a \otimes b.

For an idempotent commutative monoid PP, we define \leq so as to make PP a join-semilattice, viz. pqp \leq q iff p+q=qp + q = q. Thus PQP \otimes Q in the previous proposition is endowed with a partial order, making it a join-semilattice. In this way the category of join-semilattices inherits a symmetric monoidal structure from the symmetric monoidal category of commutative monoids containing it.

Lemma

For a commutative monoid PP in the symmetric monoidal category of join-semilattices, the monoid multiplication coincides with conjunction iff the unit is the top element and multiplication is idempotent.

Proof

Note that if bcb \leq c, then abaca b \leq a c since ac=a(b+c)=ab+aca c = a(b + c) = a b + a c. If the unit 11 is maximal, it follows that aba1=aa b \leq a 1 = a and similarly abba b \leq b. On the other hand, if xax \leq a and xbx \leq b, then x=xxabx = x x \leq a b. This shows aba b is the meet of aa and bb.

Proposition

Let P,QP, Q be distributive lattices, considered as commutative rigs with addition given by join and multiplication given by meet. Then the commutative rig PQP \otimes Q, under the order \leq when considered as a join-semilattice, is also a distributive lattice.

Proof

Certainly PQP \otimes Q is a commutative monoid in the symmetric monoidal category of join-semilattices. By the lemma it suffices to show that the unit P Q{\top_P} \otimes {\top_Q} is maximal and that multiplication is idempotent.

First we show P Q\top_P \otimes \top_Q is the maximal element of PQP \otimes Q. Indeed,

abab+ Pb=(a+ P)b= Pba \otimes b \leq a \otimes b + \top_P \otimes b = (a + \top_P) \otimes b = \top_P \otimes b

and similarly Pb P Q\top_P \otimes b \leq \top_P \otimes \top_Q, so ab P Qa \otimes b \leq \top_P \otimes \top_Q. Since any element of PQP \otimes Q is a join ia ib i\sum_i a_i \otimes b_i of elements a ib ia_i \otimes b_i which all have P Q\top_P \otimes \top_Q as upper bound, any element has P Q\top_P \otimes \top_Q as upper bound.

Second we show multiplication is idempotent. Clearly aba \otimes b is idempotent for any aPa \in P and bQb \in Q, by idempotency of aa and bb. More generally

( ia ib i)( ja jb j)= i,ja ia jb ib j(\sum_i a_i \otimes b_i) \cdot (\sum_j a_j \otimes b_j) = \sum_{i, j} a_i a_j \otimes b_i b_j

which is bounded above by ia ib i\sum_i a_i \otimes b_i since a ia ja ia_i a_j \leq a_i and b ib jb ib_i b_j \leq b_i, but is also bounded below by ia ia ib ib i= ia ib i\sum_i a_i a_i \otimes b_i b_i = \sum_i a_i \otimes b_i. This completes the proof.

By the preceding proposition, distributive lattices form a full subcategory of the category of commutative rigs that is closed under coproducts (which is the tensor product of commutative rigs).

Proposition

The category of Boolean algebras, as a full subcategory of the category of distributive lattices, is closed under coproducts.

Proof

We must show that if P,QP, Q are Boolean algebras, then every element in the distributive lattice PQP \otimes Q has a complement (necessarily unique by distributivity). For aPa \in P and bQb \in Q, let ¬a\neg a and ¬b\neg b denote their complements in PP and QQ. Then an easy calculation shows that the complement of aba \otimes b in PQP \otimes Q is ¬ab+a¬b+¬a¬b\neg a \otimes b + a \otimes \neg b + \neg a \otimes \neg b. Moreover, any element in PQP \otimes Q is a finite join of elements of the form a ib ia_i \otimes b_i, so we just need the auxiliary lemma that the join x+yx + y of two complemented elements in a distributive lattice is also complemented. Indeed, ¬x¬y\neg x \cdot \neg y is that complement (for instance, 1x+y+(¬x)(¬y)1 \leq x + y + (\neg x)(\neg y) since 1=(x+¬x)(y+¬y)=xy+x(¬y)+(¬x)y+(¬x)(¬y)1 = (x + \neg x)(y + \neg y) = x y + x(\neg y) + (\neg x)y + (\neg x)(\neg y) and xy+x(¬y)+(¬x)y=x+(¬x)yx+yx y + x(\neg y) + (\neg x)y = x + (\neg x)y \leq x + y).

Properties of the ultrafilter monad

Recall that the space of ultrafilters βX\beta X on a set XX may be regarded as the free compact Hausdorff space generated by XX, so that we have a monad β:SetSet\beta: Set \to Set. It is well-known that the category of compact Hausdorff spaces is equivalent to the category of β\beta-algebras, and that the category of topological spaces is equivalent to the category of so-called “relational β\beta-modules”. Here we collect a few more results on β\beta.

Lemma

If f:XYf: X \to Y is a function, then β(f):β(X)β(Y)\beta(f): \beta(X) \to \beta(Y) is an open map.

Proof

For a subset AXA \subseteq X, let [A][A] denote the corresponding basic clopen of β(X)\beta(X):

[A]{Uβ(X):AU}.[A] \coloneqq \{U \in \beta(X): A \in U\}.

It suffices to show that the image β(f)([A])\beta(f)([A]) is open in β(Y)\beta(Y); in fact we will show β(f)([A])=[f(A)]\beta(f)([A]) = [f(A)]. For Uβ(X)U \in \beta(X) we have

β(f)(U)={BY:f 1(B)U}\beta(f)(U) = \{B \subseteq Y: f^{-1}(B) \in U\}

and

β(f)([A])={Vβ(Y):(Uβ(X))AU(BV)f 1(B)U}\beta(f)([A]) = \{V \in \beta(Y): (\exists U \in \beta(X))\; A \in U \wedge (\forall B \in V) f^{-1}(B) \in U\}

so a necessary condition for Vβ(f)([A])V \in \beta(f)([A]) is Af 1(B)A \cap f^{-1}(B) \neq \emptyset for all BVB \in V. Note that Af 1(B)A \cap f^{-1}(B) \neq \emptyset iff f(Af 1(B))f(A \cap f^{-1}(B)) \neq \emptyset; using Frobenius reciprocity, this is the same as saying f(A)Bf(A) \cap B \neq \emptyset. But f(A)Bf(A) \cap B \neq \emptyset for all BVB \in V if and only if f(A)Vf(A) \in V (the “if” is clear, and moreover either f(A)Vf(A) \in V or ¬f(A)V\neg f(A) \in V, where the latter clearly negates f(A)Bf(A) \cap B \neq \emptyset for all BVB \in V, and so the “only if” must hold as well).

We have thus shown that Vβ(f)([A])V \in \beta(f)([A]) implies V[f(A)]V \in [f(A)]. In the other direction, if V[f(A)]V \in [f(A)], then f(A)Bf(A) \cap B \neq \emptyset for all BVB \in V, which as we saw is equivalent to Af 1(B)A \cap f^{-1}(B) \neq \emptyset for all BVB \in V. Hence the sets Af 1(B)A \cap f^{-1}(B) generate a filter on XX, which may be extended to an ultrafilter UU on XX, for which U[A]U \in [A] and Vβ(f)(U)V \subseteq \beta(f)(U) by construction, whence V=β(f)(U)V = \beta(f)(U) by maximality of ultrafilters. Thus V[f(A)]V \in [f(A)] implies Vβ(f)([A])V \in \beta(f)([A]).

Proposition

The ultrafilter monad β:SetSet\beta: Set \to Set preserves weak pullbacks, i.e., satisfies the Beck-Chevalley condition.

A proof may be found here.

Proposition

Let X jX_j be a family of sets. Then the disjoint sum jβ(X j)\sqcup_j \beta(X_j) (the coproduct in TopTop) is open and dense in jβ(X j)=β( jX j)\sum_j \beta(X_j) = \beta(\sum_j X_j) (the coproduct in CompHausCompHaus).

Proof

Put X= jX jX = \sum_j X_j in SetSet. Each inclusion β(X j)β(X)\beta(X_j) \hookrightarrow \beta(X) induced by the inclusion i j:X jXi_j: X_j \to X is open, by Lemma 10, and hence their union is open. The subspace topology on the union is the same as the disjoint sum topology. In the category TychTych of Tychonoff spaces, where coproducts are formed the same as they are in TopTop, an inclusion i:XYi: X \to Y is dense if and only if it is epic. But it is obvious that jβ(X j) jβ(X j)\sqcup_j \beta(X_j) \to \sum_j \beta(X_j) is epic in TychTych: if ZZ is Tychonoff and i:ZZ¯i: Z \to \bar{Z} its Stone-Cech compactification, then a map f:XZf: X \to Z is uniquely determined by a map if:XZ¯i f: X \to \bar{Z} in CompHausCompHaus, which in turn is uniquely determined by the family of their restrictions to the summands β(X j)\beta(X_j), or by the restriction along the inclusion of the disjoint sum. This completes the proof.

References

Revised on January 7, 2015 05:19:48 by Todd Trimble