<h1 style="color: rgb(0, 0, 0);"><font size="2">FOM: Set theory vs category theory: Representability of categories</font></h1>

    <font style="color: rgb(0, 0, 0);" size="2"><b>Vaughan Pratt</b> 

    <a href="mailto:fom%40cs.nyu.edu?Subject=FOM%3A%20Set%20theory%20vs%20category%20theory%3A%20Representability%20of%20categories&In-Reply-To=199801271058.LAA14876%40brics.dk" title="FOM: Set theory vs category theory: Representability of categories">

pratt at cs.Stanford.EDU

       </a><br>

<i>Tue Jan 27 13:37:42 EST 1998<br>

<br>

<a href="http://cs.nyu.edu/pipermail/fom/1998-January/001021.html">http://cs.nyu.edu/pipermail/fom/1998-January/001021.html</a><br>

</i></font>

<pre id="line36"><br><font size="4"><br>A number of representation theorems were found by Czech algebraists and<br>category theorists during the latter half of the 1960's, representing<br>arbitrary small categories as categories of familiar concrete structures

<br>and their homomorphisms.  Two notable representations are in terms<br>of semigroups, and of directed graphs.  In each case the theorem is<br>that every small category is representable as a category of semigroups<br>(directed graphs, etc.) and their homomorphisms (of the standard kind

<br>in each case).<br><br>The criteria used here for representability of objects  a  and morphisms<br>f:a-&<span class="entity">gt;</span>b of a category C by respectively structures F(a) and homomorphisms<br>F(f): F(a)->

<span class="entity"></span>F(b) of the concrete representing category D are as follows.<br><br>(i) F:C-><span class="entity"></span>D is a *functor*, that is, a graph homomorphism (viewing the<br>morphisms of C and D as edges of their respective underlying graphs)

<br>that preserves composition and identities (a condition exactly analogous<br>to those of monoid homomorphism and group homomorphism).<br><br>(ii) F is *faithful*, i.e. for any pair a,b of objects of C, distinct<br>morphisms f:a-&

<span class="entity">gt;b of C are represented by distinct homomorphisms F(f):F(a)-><span class="entity">F(b) of D. (iii) F is *full*, i.e. every homomorphism from F(a) to F(b) in D is the representation under F of some morphism from a to b in C.

<br><br>The intuitive meaning of full and faithful is that the representing<br>object is just as stiff as the object it represents when you wiggle both.<br>Fullness means it is at least as stiff (D offers no new transformations),

<br>while faithfulness means it is at most as stiff (no transformations are<br>lost by identification).<br><br>Unfortunately the project of embedding arbitrary categories fully and<br>faithfully in familiar concrete categories has turned out not to have

<br>the impact of its counterparts in group theory (permutations), Boolean<br>algebras (fields of sets), distributive lattices (rings of sets), etc.<br>These results have in consequence not been widely publicized in the<br>

introductory categorical literature.<br><br>The most objectionable feature of these embeddings in my view (and I<br>am aware of no other serious objection) is their lack of respect for<br>concreteness itself.  If one takes for C a small *concrete* category,

<br>such as all quotient groups of the additive group of natural numbers<br>and their group homomorphisms, the above-mentioned embedding represents<br>the finite group Z_2 as an infinite semigroup!  And if &<span class="entity">

quot;</span>natural numbers&<span class="entity">quot;</span></font>

</pre>

<pre id="line95"><font size="4">is replaced by "<span class="entity"></span>reals"<span class="entity"></span>, the corresponding embedding represents Z_2 as an<br>uncountable semigroup.  Such a lack of respect for concreteness would

<br>seem to undermine the very point of representing abstract objects as<br>concrete structures.<br><br>In contrast a finite group of order n is representable by permutations of<br>n things, a finite Boolean algebra as a field of subsets of a finite set,

and so on.  In these better-known representation theorems, cardinality is respected, typically to within at most two exponentials (which in the infinite case means to within two beth numbers) and often much better.

This unsatisfactory situation with the concrete representation of objects of arbitrary categories prompts the speculation that the notion of category is too broad to admit of any improvement in the situation.

<br>After all, any random graph G is made a category by adding to its<br>edges all paths in G, with composition defined as path concatenation<br>(the free category generated by G).  How could there possibly be a<br>cardinality-respecting representation of the vertices of a random graph

<br>in terms of the objects of a familiar concrete category?  When one can<br>do any violence one wishes to the structure by adding an edge at random<br>between any two vertices, it would seem that any concrete representation

<br>of each object would inevitably have a cardinality on the order of the<br>whole category.<br><br>But in fact there *is* a representation that does the job.  Let us make<br>two easily understood modifications to the usual notion of topological

<br>space.<br><br>First, drop the requirement that the open sets be closed under arbitrary<br>union and finite intersection.  (The role of this traditional restriction<br>is in effect to limit the &<span class="entity">

quot;</span>signature&<span class="entity">quot;</span> of a topological space to just that<br>needed to express the notion of limit, or even less with the more discrete<br>spaces; dropping it greatly broadens the range of possible signatures.)

Second, in place of the customary two degrees of membership in the open sets (ordinary sets), permit a set K of possible degrees of membership, call such open sets fuzzy (Zadeh's fuzzy sets are the case K the reals).

<br><br>Define continuity as usual for functions between topological spaces,<br>wording the definition in such a way however that its extension to<br>fuzzy sets is made clear.  Specifically, f:X-&<span class="entity">

gt;</span>Y is continuous when for<br>every open set g:Y-&<span class="entity">gt;</span>K (here expressed as a characteristic function),<br>the composite<br><br>                 f      g<br>           X ---><span class="entity"></span>

 Y ---><span class="entity"></span> K<br><br>is an open set of X.  When K = {0,1} it is easily verified that this is<br>the standard notion of continuity.<br><br>Call such generalized topological spaces Chu spaces over K.  An even more

<br>general notion was first studied in detail by Peter Chu in the 1970's,<br>a master's student of Michael Barr.  The more elementary version above<br>was first studied by Lafont and Streicher in 1991 (LICS) under the rubric

<br>of games but the term &<span class="entity">quot;</span>Chu construction&<span class="entity">quot;</span> was already in the computer<br>science air in the late 1980's making it too late to change the name.<br>

<br>Definitions.<br><br>1.  A concrete category is a pair (C,U) where C is a category and U:C-&<span class="entity">gt;</span>Set<br>is a faithful functor, the "<span class="entity"></span>forgetful" functor giving the *underlying

<br>set* of each object along with the realization of each morphism of C as<br>a function (a morphism of Set).<br><br>2.  A concrete functor F:(C,U)-><span class="entity"></span>(D,V) between two concrete categories<br>

is one satisfying VF = U.  That is, the underlying set VF(a) of the<br>representation F(a) of a is the same as the underlying set U(a) of<br>a itself.<br><br>Remark.  The elements of all the representing sets of a small concrete

<br>category (C,U) themselves form a single set, namely the disjoint or<br>marked union of all the sets in the category.  Call this set Elt(C,U),<br>the set of elements of (C,U).<br><br>A very minor technicality requires the notion of an *honest* concrete

<br>category, namely one having, for all objects a and b, a morphism from<br>a to b if U(a) is empty (necessarily at most one, by concreteness).<br>Dishonest concrete categories cannot be represented as below because<br>the empty topological space has nowhere to store the information as to

<br>which other spaces it does or does not have functions to.  (Thanks to<br>Peter Freyd for pointing out the lacuna in my proof that necessitated<br>this condition.)<br><br>Theorem.  Every small honest concrete category (C,U) embeds fully,

<br>faithfully, and concretely in the category of Chu spaces over Elt(C,U).<br><br>(This theorem enjoys all the advantages of the previous embeddings, but<br>in addition satisfies the strongest possible concreteness requirement:

<br>the representing object has the *same* underlying set as the object it<br>represents, and the representing morphisms viewed concretely are exactly<br>the same functions.)<br><br>Proof.  Let b be an object of C with underlying set X = U(b).  Represent

<br>b by a generalized topological space X, having one open set Y_h for<br>each morphism h:b-&<span class="entity">gt;</span>c in C for some c.  Form Y_h by taking the degree of<br>membership of each point x in Y_h to be U(h)(x), 

i.e. the element of U(c)<br>which is the image of x under the underlying function U(h) of h.<br><br>It is then straightforward to show that this representation is faithful,<br>full, and concrete.<br><br>Obviously the burden of the obstacle that we have overcome has merely

<br>been shifted to the open sets, the number of which must now be on the<br>order of the cardinality of the category.  But since when has the number<br>of open sets been an obstacle to topology?  The points of a space are

<br>clearly visible, but our embedding has left these untouched.  Who has<br>ever seen an open set or cares about how many there are?<br><br>For more information on Chu spaces consult<br><br>     <<span class="start-tag">A

</span><span class="attribute-name"> HREF</span>=<span class="attribute-value">"<a href="http://boole.stanford.edu/chuguide.html">http://boole.stanford.edu/chuguide.html</a>"</span>><a href="http://boole.stanford.edu/chuguide.html">

http://boole.stanford.edu/chuguide.html</a></<span class="end-tag">A</span>><br></font></pre>

<pre id="line206"><font size="4">My original interest in Chu spaces was as a model of concurrent<br>behavior.  More recently I have become interested in them as a primarily<br>set-theoretic foundation for mathematics that more directly emulates

<br>what category theory has to offer than the extant litany of single-sorted<br>and and multisorted relational structures and algebras with and without<br>(ordinary) topology and their standard homomorphisms, all of which are

<br>fully, faithfully, and concretely representable by Chu spaces.<br><br>---<br>Name: Vaughan Pratt<br>Position: Professor of Computer Science<br>Institution: Stanford University<br>Research interests: Foundations of computation and mathematics

</font><br>For more information: <<span class="start-tag">A</span><span class="attribute-name"> HREF</span>=<span class="attribute-value">"<a href="http://boole.stanford.edu">http://boole.stanford.edu</a>"</span>

><a href="http://boole.stanford.edu">http://boole.stanford.edu</a></<span class="end-tag">A</span>></pre>