A Visual Presentation of Rank-Ordered Sets

Year: 1998 Authors: Mara Alagić

Core claim

Rank-ordered sets with rank-preserving and rank-increasing functions form a cartesian closed categorical framework useful for interpreting programming entities.

Topics

category theory, rank-ordered sets, partial equivalence relations, cartesian closed category

Domains

category theory, order theory, domain theory, scientific visualization

Methods

categorical abstraction, inverse-limit construction, diagrammatic proof, definition-driven exposition

Media

commutative diagrams, set-theoretic notation, category diagrams

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

BRIDGES

Mathematical Connections

in Art, Music, and Science

A Visual Presentation of Rank-Ordered Sets

Mara Alagić Department of Mathematics and Statistics Wichita State University, Wichita 67226 - 0033 e-mail: mara@math.twsu.edu

Abstract

We are exploring two cartesian closed categories, rich with structure: rank-ordered sets, and its subcategory kinds. Categorical language is used for a conceptual clarification and imagination of these structures.

Motivation

The paper originated in an attempt to get the mathematical and conceptual understanding of some programming entities ([5], [1], [2]). The main contribution of this paper is a self-contained view to a specific cartesian closed category - rank ordered sets and rank-preserving functions. The fact is that this category can be also considered as a subcategory of the category of bounded ultrametrics with nonexpansive maps (see [5],[3]). That fact describes its geometric structure.

In the first section we present rank-ordered sets with rank-preserving functions starting from a category of sets, Set. The collection of rank-preserving functions is a rank-ordered set. The same is true for naturally defined product of two rank-ordered sets. Therefore we have in our hands a cartesian closed category of rank-ordered sets with rank-preserving functions.

In the second section two categories $CPER$ and $CPE{R}^p$ of partial equivalence relations (per) defined on cpo’s (complete partial orders) are presented. Special collections of partial equivalence relations over certain domain $D_{\infty }$ are shown to be rank-ordered sets. Domain $D_{\infty }$ is introduced as a limit object of an inverse limit system $\{D_i,h_i\}$ in $CP{O}^p$ and each per in this collection is the limit of a sequence of pers of the approximating domains $D_i$. Family of commutative diagrams proving this illustrates precisely corresponding relationships ([3]).

Imposing conditions that guarantee closure under limits and therefore induced cpo structure, and requiring that each per can be seen as a limit of a certain sequence of pers gives so-called acceptable collection of per’s over $D_{\infty }$. The collection of rank-increasing functions has the same abstract structure as an acceptable collection of nice per’s ([4]).

The smallest subcategory of rank-ordered sets which contains a collection of acceptable pers and is closed under products and exponents is presented in Section 3. It is cartesian closed category, called category of kinds in order to suggest more complex structure than one of types.

238 Mara Alagic

1. Rank-ordered Sets and Rank-preserving Functions

In this section we have a close look at objects, rank-ordered sets and corresponding arrows, rank-preserving functions of a specific category.

We start with the category of sets and maps between sets, Set.

A set $K$ is rank-ordered if there is a collection of maps $(\cdot {)}_{[i]}:K\to K$, $i\ge 0$, $i\in \omega$ that assigns to each element $A$ from $K$ a sequence of elements $A_{[i]}$ (each from $K$) satisfying the following conditions:

(i) $(\cdot {)}_{[0]}:K\to K$ assigns to any $A\in K$ the same element, denoted by $Bo{t}_K$. Thus, $A_{[0]}=Bo{t}_K$ for all $A\in K$.

(ii) $(A_{[i]}{)}_{[j]}=(A_{[j]}{)}_{[i]}=A_{[\min \{i,j\}]}$ for all $A\in K$.

(iii) Let $K_{[i]}\stackrel{\text{def}}{=}\left\{A_{[i]}\mid A\in K\right\}$. If ${\left\{A_i\right\}}_{i\in \omega }$ is a sequence from $K$ with the property $A_i=(A_{i+1}{)}_{[i]}$ then there is a unique $A\in K$ such that for all $i$, $A_i=A_{[i]}$.

Let $A,B\in K$. If $A=A_{[i]}$ for some $i$, then the rank of $A$ is defined by $\text{rank}(A)=\min \left\{i\mid A=A_{[i]}\right\}$. If $A\ne A_{[i]}$ for all $i$ we say $\text{rank}(A)=\infty$. If $\text{rank}(A)$ is finite and $A=B_{[\text{rank}(A)]}$ we say that $A$ approximates $B$, denoted by $A◃B$.

In the next section we will see the construction of a specific rank-ordered set.

The arrows between rank-ordered sets are defined according to the following diagram (for all $A\in K$ and all $j\ge i$):

A function $f:K\to L$ is rank-preserving function if for all $j\ge i$ and all $A\in K$,

The collection of rank-preserving functions from $K$ to $L$, $[K\Rightarrow L]$, is a rank-ordered set. $K\times L\stackrel{\text{def}}{=}\{(k,l)\mid k\in K,l\in L\}$ and $(\cdot {)}_{[i]}:K\times L\to K\times L$ is defined by $(k,l{)}_{[i]}=(k_{[i]},l_{[i]})$. Note that $K\times L$ is a rank-ordered set.

Closure property of rank-preserving functions: If $F:K\times L\to M$ is rank-preserving function then

Thus, $F:K\times L\to M$ is rank-preserving iff it is rank-preserving in each of its arguments, separately.

> The category of rank-ordered sets with rank-preserving functions is a cartesian-closed category.

A Visual Presentation of Rank-Ordered Sets 239

1.1. Rank-increasing Functions.

The advantage of rank-increasing functions is that each endo-function has a unique fixed point. Also, the fixed point of a multivariable function that is rank-increasing in one argument retains its rank-related properties in other arguments.

A function $f:K\to L$ is rank-increasing function if for all $j\ge i-1$ and all $A\in K$,

The collection of rank-increasing functions from $K$ to $L$ is denoted by $[K\stackrel{i}{\to }L]$.

Properties of rank-increasing and rank-preserving functions:

1. Every rank-increasing function is also rank-preserving function.
2. The collection of rank-increasing functions from $K$ to $L$ is a rank-ordered set.
3. Composition of a rank-preserving and a rank-increasing (or vice versa) functions is a rank-increasing function.
4. If $F:K\times L\to M$ is rank-increasing function then

5. Let $G:K\to L$ and $F:L\to M$ be rank-preserving functions. If one of them is rank-increasing then the composition $F\circ G$ is also rank-increasing.
6. $F:K\times L\to M$ is rank-increasing (rank-preserving) iff it is rank-increasing (rank-preserving) in each of its arguments, separately.

Only rank-increasing subset of rank-preserving functions have unique fixed points. (The identity map from per’s to per’s is rank preserving but not rank-increasing function.) In addition, the fixed point of a multi-argument function that is rank-increasing in one argument retains its rank-related properties in other arguments.

2. Partial Equivalence Relations

The cartesian closed category of rank-ordered sets with rank-preserving functions provides an environment space for the construction of specific rank-ordered set - partial equivalence relations over a certain desired domain.

An $\omega -$ complete partial order $(cpo)(D,\le ,\perp )$ is a partial order (reflexive, antisymmetric, and transitive) with a least element $\perp$, and such that $\vee A\in D$ for every countable directed collection $A\in D$.

There are two classes of morphisms that can be introduced between $\omega -$ complete partial orders: continuous functions and embedding-projection pairs. Both of them give rise to a certain category.

240 Mara Alagić

A map $f:D\to D^{\prime }$ is continuous iff $f(\vee X)=\vee f(X)$ for all directed $X\subseteq D$ where $f(X)=\{f(x)\mid x\in X\}$ and $\vee f(X)$ is in $D^{\prime }$. Note also that continuous maps on cpo’s are always monotonic.

An embedding-projection pair between cpo’s $D$ and $D^{\prime }$ consists of maps $e:D\to D^{\prime }$ and $p:D^{\prime }\to D$ such that $pe=i{d}_D$ and $ep\le i{d}_{D^{\prime }}$. Each determines the other, assuming both exist, so it suffices to name the embedding or the projection.

Let $CPO$ denotes the category of $\omega -$ complete partial orders with continuous maps and let $CP{O}^p$ be the category of $\omega -$ complete partial orders with projections as maps between them.

Example 1 Let $N$ denotes a set of counting numbers together with usual ordering and 1 as the initial object. Therefore, $N$ and $N\times N$ (pointwise ordering) can be considered as $CPO$‘s. Given embedding $e:N\to N\times N$, $e(n)=(n,0)$ the corresponding projection is defined by $p:N\times N\to N$, where now $pe=i{d}_N$ and $ep\le i{d}_{N\times N}$.

Facts.

(i) The category CPO is a cartesian closed category: the singleton cpo is terminal object; $D\times D$ is ordered coordinate-wise, and for each $f:D\times D^{\prime }\to D^{\prime \prime }$ there exists a unique $f^{\ast }:D\to [D^{\prime }\to D^{\prime \prime }]$ satisfying the adjointness condition.

(ii) Every $f\in [D\to D]$ has a fixed point.

(iii) Inverse limits exist in $CPO$. For an inverse system $(D_i,f_i:D_{i+1}\to D_i)$, inverse limit, $\lim (D_i,f_i)$ is the poset $D_{\infty }=\{(x_0,x_1,\dots )\mid f(x_{i+1})=x_i\text{ for all }{x}_i\in D_i\}$ with coordinate-wise ordering, and with $\vee X=\vee \{x(i)\mid x\in X\}$.

A new categories $CPER$ and $CPE{R}^p$ may be defined in the following manner:

Let $(D,\le ,\perp )$ be a cpo. A relation $R\subset D\times D$ is a partial equivalence relation, per, if it is symmetric and transitive relation on $D$.

Example 2 On a set $D=\{♠,♣,\star \}$ (or $D=\{1,3,5\}$ or $D=\{\varnothing ,\{\varnothing \},\{\{\varnothing \},\varnothing \}\}$) there are $81=(3\times 3{)}^2$ binary relations, but only 14 pers:

A Visual Presentation of Rank-Ordered Sets 241

Objects of $CPER$ are pairs $(R,D)$ where $(D,\le ,\perp )$ is a cpo and $R\subset D\times D$ is a partial equivalence relation, per, (symmetric and transitive) which is closed under sup’s of $\omega$-chains.

Morphism $(f,g):(R,D)\to (R^{\prime },D^{\prime })$ in $CPER$ is given with continuous $f\times g:D\times D\to D^{\prime }\times D^{\prime }$ which respects the relation: $xRy\Rightarrow f(x)R^{\prime }g(y)$.

$CPE{R}^p$ is the subcategory of $CPER$ with the same objects and with arrows $(f,g):(R,D)\to (R^{\prime },D^{\prime })$ projection maps.

To construct a specific rank ordered set, we start with a continuous functor $H:CP{O}^p\to CP{O}^p$ and construct a cpo $(D_{\infty },\le ,\perp )$ as the inverse limit of the following $\omega$-diagram.

Let $\perp =\{\perp \}$ (the one element cpo) be the terminal object of $CP{O}^p$ and $t:H(\perp )\to \perp$ the unique projection from $H(\perp )$ to the terminal object.

A collection $\{H^i(t):H^{i+1}(\perp )\to H^i(\perp ),i\in \omega \}$ forms an inverse system:

Denote by $(D_{\infty },p_i:D_{\infty }\to H^i(\perp ))={\lim }_{\leftarrow }\left\{H^i(\perp ),H^i(t):H^{i+1}(\perp )\to H^i(\perp )\right\}.$

By this construction each $H^i(\perp )$ is isomorphic to some subdomain $D_i\subseteq D_{\infty }$, with projections ${\hat{p}}_i:D_{\infty }\to D_i$. For $d\in D_{\infty }$ let us denote ${\hat{p}}_i(d)$ by $d_{[i]}$ so that each $d\in D_{\infty }$ is the limit of the $\omega$-chain $\{d_{[i]}{\}}_{i\in \omega }$.

$H(D_{\infty })\cong H(\lim D_i)\cong \lim H(D_i)\cong D_{\infty }$. So, $D_{\infty }\cong H(D_{\infty })$ ($H$ continuous).

An example of such functor is $H(X)=A+L^X+X^X$ where $A$ is some cpo of atomic values, $L$ is countably infinite cpo and $+$ is coalesced sum.

A continuous functor $F:CPE{R}^p\to CPE{R}^p$ extends continuous functor $H:CP{O}^p\to CP{O}^p$ if the following conditions are satisfied:

$F(R,D)=(S,H(D))$, $S=F(R)$; $F(f,g)=(H(f),H(g))$;

so that we may write shortly

The following shows that each per is the limit of a sequence of pers of the approximating domains $H^i(\perp )$. A family of commutative diagrams used to prove this illustrates precisely corresponding relationships among $D_{\infty },H^i(\perp )$, and each per constructed over $D_{\infty }$.

Let $F:CPE{R}^p\to CPE{R}^p$ extends $H:CP{O}^p\to CP{O}^p$. Then the sequence $F^{(n)}(\perp )$ in $CPE{R}^p$ is a sequence of relations over $H^n(\perp )$ in $CP{O}^p$ and, furthermore

242 Mara Alagić

$(F_{\infty },q_n:F_{\infty }\to F^n(\perp ))={\lim }_{\leftarrow }\{F^n(\perp ),F^n(\perp ):F^{n+1}(\perp )\to F^n(\perp )\}$ is a relation over $D_{\infty }$.

Consider the following family $(n\in \omega )$ of commutative diagrams

“Fixed points” of each continuous F extending H are obtainable as limits of a diagram consisting of relations over $D_i$‘s. Note that if F extends H, the action of F on morphisms is completely determined by H. So, for fixed H, object maps on $CPE{R}^p$ are maps from per’s to per’s.

Approximations ($D_{\infty }$ is a rank ordered set.). A family of continuous mappings $(\cdot {)}_{[n]}:D_{\infty }\to D_{\infty }$ defined by $(\cdot {)}_{[n]}(d)=d_{[n]}$ for $d\in D_{\infty }$ satisfies the following properties:

1. Let $d\in D_{\infty }$. Then

if $n\le m$ then $d_{[n]}\le d_{[m]}$.

2. Let $f\in [D_{\infty }\to D_{\infty }]$ and $f_{[n]}={\hat{p}}_{n}f$ where ${\hat{p}}_n:D_{\infty }\to D_n$ is the $n$-th projection. Then

2.1. Acceptable collection of per’s over $D_{\infty }$

(Construction of a rank-ordered set of per’s.)

We now consider partial equivalence relations over $D_{\infty }$. Specifically, let us define an acceptable collection $\mathcal{R}$ of per’s over $D_{\infty }$ imposing the following conditions.

A collection $\mathcal{R}$ of per’s over $D_{\infty }$ is an acceptable collection subject to the following conditions:

(p1) For all $R\in \mathcal{R},(\perp ,\perp )\in R$.

(p2) If \{(d_i,d_i')\mid i > 0\} is an $\omega$-chain in $R\in \mathcal{R}$ with limit $(d,d^{\prime })$ then $(d,d^{\prime })\in R$.

(p3) $(d,d^{\prime })\in R$ iff $(d_{[i]},d_{[i]}^{\prime })\in R$ for all $i\in \omega$.

(a1) $\mathcal{R}$ contains the per $\{(\perp ,\perp )\}$.

A Visual Presentation of Rank-Ordered Sets 243

(a2) $\mathcal{R}$ is closed under function space, i.e. $P,Q\in \mathcal{R}$ implies $[P\to Q]\in \mathcal{R}$.

(a3) $\mathcal{R}$ is closed under F-bounded quantification.

(a4) If \{R_i \mid i < \omega\} \subseteq \mathcal{R} satisfies the property that for all $j\ge i$, $(R_j{)}_{[i]}=R_i$, (where $S_{[i]}$ denotes the restriction of $S$ to the subdomain ${\hat{D}}_i\subset D_{\infty }$) then there is a unique $R\in \mathcal{R}$ such that for all $i$, $R_{[i]}=R_i$.

Conditions (p1), (p2), and (p3) describe nice per. The first two conditions give closure under limits and the third is the requirement that each per can be seen as a certain limit of a sequence of pers.

The set $\mathcal{R}$ is not only closed under function space but it also contains unique sups of increasing chains of per’s.

Conditions (p1), (p2), and (p3) allow the definition of a cpo structure on $\mathcal{R}$.

A notion of rank on a per from $\mathcal{R}$ (even on a nice per) is given by the following definition.

For $R\in \mathcal{R}$ let $R_{[n]}=R\cap D_n\times D_n$. If $R=R_{[i]}$ for some $i$, $\text{rank}(R)\stackrel{\text{def}}{=}\min \{i\mid R=R_{[i]}\}$. If $R\ne R_{[i]}$ for all $i$, $\text{rank}(R)\stackrel{\text{def}}{=}\infty$. If $\text{rank}(R)$ is finite and $R=S_{[\text{rank}(R)]}$ for some $S\in \mathcal{R}$, we say $R$ approximates $S$, $R◃S$.

$R_{[n]}=\left\{(d_{[n]},e_{[n]})\mid (d,e)\in R\right\}$ and it satisfies the properties (p1), (p2), and (p3) of an acceptable collection.

A collection $\mathcal{R}$ of nice pers has a cpo structure.

It is enough to notice that the least upper bound of an $\omega$-chain $R_0◃R_1◃\dots$ with $\text{rank}(R_i)=i$ is the relation $R=\{(d,e)\mid d_{[i]}{R}_i{e}_{[i]},\text{all }i\}$. Therefore, each $R$ in $\mathcal{R}$ is the limit of the corresponding $R_{[i]}$‘s.

An acceptable collection of per’s, $\mathcal{R}$, is a rank-ordered set because

(i) $(R{)}_{[0]}=(\perp ,\perp )$

(ii) By construction of $R\in \mathcal{R}$ as a $\lim \leftarrow F^n(\perp )$ for some functor $F$ that extends $H$, we have $(R_{[i]}{)}_{[j]}=(R_{[j]}{)}_{[i]}=R_{[\min \{i,j\}]}$ for all $R\in \mathcal{R}$.

(iii) $R=\lim \leftarrow R_{[n]}={\bigvee }_n{R}_{[n]}$.

3. CCC of Kinds

The kind structure $\mathcal{K}$ generated from $\mathcal{R}$ is the smallest subcategory of the category of rank-ordered sets which contains $\mathcal{R}$ and is closed under products and exponents. A kind structure $\mathcal{K}$ is a cartesian closed category.

The elements of each kind may be ordered in two ways:

For types we consider the subtype ordering,

For $R,S\in \mathcal{R}$ let $R{\le }_{\mathcal{R}}S$ iff $R\subseteq S$.

For type functions we have the induced pointwise ordering:

Assuming ${\le }_K$ and ${\le }_L$ are defined for $K,L\in \mathcal{K}$, we define

$F{\le }_{[K\Rightarrow L]}G$ iff for all $A\in K$, $F(A){\le }_{L}G(A)$ where $F,G\in [K\Rightarrow L]$, and

Mara Alagic

$(A,B){\le }_{K\times L}(C,D)$ iff $A{\le }_{K}C$ and $B{\le }_{L}D$ where $(A,B)$, $(C,D)\in K\times L$.

For types we may also consider the rank ordering (induced by approximations of rank-ordered sets) defined as follows

For $R,S\in \mathcal{R},R◃S$ iff rank(R)<\infty and $R=S_{[rank(R)]}$.

The induced ordering for type functions is

$F{\le }_{[K\Rightarrow L]}G$ iff for all $R\in K,F(R)◃G(R)$ where $F,G\in [K\Rightarrow L]$.

4. Summary

In this paper we have described a cartesian closed category of rank-ordered sets and its two subcategories of partial equivalence relations defined on a very specific inverse limit object as its domain. Although rank-preserving functions are convenient arrows for rank-ordered sets, the advantage of rank-increasing functions is the existence of a unique fixed point in this case.

Categories $CPER$ and $CPE{R}^p$ of partial equivalence relations defined on cpo’s (complete partial orders) are an important step in this construction. Special collections of partial equivalence relations over certain domain $D_{\infty }$ are rank-ordered sets. Domain $D_{\infty }$ is a limit object of an inverse limit system $\{D_i,h_i\}$ in $CP{O}^p$ and each per in this collection is the limit of a sequence of pers of the approximating domains $D_i$. These partial equivalence relations obtained by the inverse-limit construction over suitable domain structure are used as models interpreting types by many authors (M.Coppo, Amadio, Cardelli, Abadi & Plotkin).

Elements of the domain $D_{\infty }$ can be viewed according to the limit construction of $D_{\infty }$ and therefore some very natural properties follow. These are also properties of approximations on cpo’s introduced in [4, Cardelli]. Imposing conditions that guarantee closure under limits and therefore induced cpo structure, and requiring that each per can be seen as a limit of a certain sequence of pers gives an acceptable collection of nice per’s ([3]).

The smallest subcategory of rank-ordered sets which contains a collection of acceptable pers and is closed under products and exponents is category of kinds. It suggests more complex structure then one of types - both of them convenient for interpreting certain programing entities. The elements of each kind may be ordered.

References

• [1] M.Alagić. Relations with I-structure in categories with pullbacks.

Publications de l’Institut Mathematique, Nouvelle serie, Belgrade 50(64), pp. 355–365. 1992.

• [2] S. Alagić and M. Alagić. Order-sorted model theory for temporal executable specifications. Theoretical Computer Science 179, pp.273–299, 1997.
• [3] K. Bruce and J. C. Mitchell. Per Model of Subtyping, Recursive Types and Higher–order Polymorphism. Proceedings of POPL-92, pp.316–327. 1992.
• [4] L. Cardelli. A Semantics of Multiple Inheritance. Information and Computation 76, pp 138–164, 1988.
• [5] M.Abadi and G.D.Plotkin. A per Model of Polymorphism and Recursive Types, Proc. IEEE Symp. on Logic in Computer Science, pp. 355–365, 1990.