What are the general rules for calculating the sub-object classifier of a topos? Or, for what class of toposes is there an algorithm for calculating the sub-object classifier of its members? Ellis D. Cooper [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
For sheaves on a finite site (which by a theorem of AGV in SGA4 vol 2 is the same as all presheaves on some smaller finite category C), take the category of all functors from C^op to bold 2. It is a finite poset, in fact, a Heyting algebra (indeed even bi-Heyting) belying the old misconception that one deviates from Boole only for infinite sets. If for each given A in C we do the same for C/A, we get the figures of shape A in the Omega of the topos. The adjoints to maps induced by A'->A give a concrete model of tense logic. By the same AGV (not only these C/A' ->C/A but) any functor between finite categories induces a geometric morphism that is even "essential". Actually, taking sheaves valued in the topos of finite sets would be interesting, providing a more objective version of number theorythan the abstract exponential rig traditionally called "natural". Topos theory is bristling with potential examples that we "generalists" have been slow to take up. Anyway, the above construction of Omega is manifestly exponential, hence an effort to find computable sub cases is clearly needed, as you suggest Ellis. Bill
Date: Wed, 23 Feb 2011 10:16:56 -0500 To: categories@mta.ca From: xtalv1@netropolis.net Subject: categories: Subobject Classifier Algorithm
What are the general rules for calculating the sub-object classifier of a topos? Or, for what class of toposes is there an algorithm for calculating the sub-object classifier of its members?
Ellis D. Cooper
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
When "Ellis D. Cooper" <xtalv1@netropolis.net> asks,
What are the general rules for calculating the sub-object classifier of a topos? Or, for what class of toposes is there an algorithm for calculating the sub-object classifier of its members?
I imagine the sort of response he hoped for is one like: In a presheaf topos, the suboject classifier Ω can be unraveled, from its universal property, by help of the Yoneda Lemma, as each of the various values Ω(X) that Ω must take at an object X "is" the set of natural transformations from hom(-, X) to Ω, which, in turn, "is" the set of subfunctors of the representable functor hom(-, X). I'll let others formulate similarly "algorhythmic" proposals for other sorts of topoi (comonadic ones, sheaves, etc.). Cheers, -- Fred [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Ellis Cooper asked,
What are the general rules for calculating the sub-object classifier of a topos? Or, for what class of toposes is there an algorithm for calculating the sub-object classifier of its members?
Thanks to Bill and Fred for describing the constructions. I would suggest, however, that it is rather stretching the meaning of the word "algorithm" to describe them as such. What kind of machine might be able to perform these operations? A propos of this question, it is well known both to new students of category theory and to those who like to use the subject to discuss Life, The Universe And Everything, that: (1) a topos is a cartesian closed category with (2) an internal Heyting algebra Omega, so ehat is the least that we have to add to these correct but incomplete statements to give a characterisation of a topos? Obviously I do not mean just reciting the definition of a subobject classifier. We should begin by strengthening these two statements: The term "cartesian closed" is ambigious in its usage. In computer science, it has come to require just products (and exponentials), whereas it seems to be implicit in older mathematical literature that all finite limits are needed, including EQUALISERS in particular. I therefore replace (1) by (1') a category with all finite limits and exponentials. Secondly, the Heyting algebra Omega is COMPLETE: there are morphisms some_X: PX = Omega^X --> Omega and PX = all_X: Omega^X --> X whose properties are easy to state. So (2) becomes (2') an object Omega with some_X and all_X for every object X. Let's try to prove some things from this: In order to avoid towers of exponentials, which are difficult enough in LaTeX but quite illegible in ASCII, I will write PX for Omega^X, but use the lambda calculus for exponentials. Since Omega is a Heyting algebra it also has an internal equality: equals_Omega : Omega x Omega --> Omega Using completeness, we can define an equality for all objects: equals_X : X x X --> Omega where equals_X (x, y) is all_PX (lambda phi:PX. equals_Omega(phi x, phi y) so that a morphism i:X-->Y is mono iff equals_Y (i x, i x') = equals_X (x, x'). Given such a mono we can also define I : PX --> PY by I phi == lambda y. some_X (lambda x. phi x /\ equals_Y (i x, y)) and I would like to show that I phi (i x) = i x. However, to do this we need another assumption, the Frobenius law for some_X, specifically some x'X. (phi x /\ x=x') == phi x /\ some x'.x=x' where I have replaced the earlier notation with a friendlier one. Instead of asserting the Frobenius law, I prefer a more general property of Omega itself that I call the EUCLIDEAN PRINCIPLE: (3) omega /\ F (omega) == omega /\ F (T) for all omega:Omega and F:Omega^Omega, which is to be interpreted in either the lambda calculus or using generalised elements, ie omega : X --> Omega and F : X x Omega --> Omega. We're not quite there. None of the operations that we have introduced so far yields elements of a general type X. So the final hypothesis is (4) every object X is SOBER by which I mean that the diagram X ->> PPX ==> PPPP X involving units of the monad (PP, eta, mu = P eta P) is an equaliser, or (4') every object X admits definition by description. Under these hypotheses, any mono i:X-->Y is uniquely classified by some psi:Y-->Omega and the category is a topos. More detail of these ideas is to be found in my papers geohol: Geometric and Higher Order Logic (TAC 2000) foufct: Foundations for Computable Topology (shortly to appear in a collection of papers about foundations of mathematics edited by Giovanni Sommaruga) equitop: Equideductive Topology (see my previous posting) all of which are available from my website www.PaulTaylor.EU/ASD/ followed by the acronym above. Paul [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Of course the initial responses given by Fred and me were notthemselves algorithmic, but why can they not be a prelude to such?Fred recalled the sequence of UMPs that defines Omega and I recalled what results in the case of a finite site. The hope is that experts in Maple and the like will be able to solve the sort of problem needed to generate displays. That is, given a finite presentation of a category C,find a presentation of the resulting Heyting algebra with the action ofC on it. Of course as stated this includes the Burnside problem , the Post problem etc . Hence the need for recognizing solvable subproblems.Even for the class of graphic monoids, where the structure is finite, it growsexponentially , which has been used in the past by other computer scientists as an excuse not to consider it. But if we are given a few fixed finite C, we can consider the class of categories discretely fiberedover them (equivalent to objects of the toposes) and try to see whetherOmega is computable in the above sense for them. I said contravariant 2-valued functors and of course these factor through the poset reflection. Calculating that poset reflection is a search problem wrt the underlying graph, but actually wrt composition as well since we have todo it for the slice categories C/A.Bill> Date: Fri, 25 Feb 2011 11:20:36 +0000
From: pt11@PaulTaylor.EU To: categories@mta.ca Subject: categories: Subobject Classifier Algorithm
Ellis Cooper asked,
What are the general rules for calculating the sub-object classifier of a topos? Or, for what class of toposes is there an algorithm for calculating the sub-object classifier of its members?
Thanks to Bill and Fred for describing the constructions.
I would suggest, however, that it is rather stretching the meaning of the word "algorithm" to describe them as such. What kind of machine might be able to perform these operations?
A propos of this question, it is well known both to new students of category theory and to those who like to use the subject to discuss Life, The Universe And Everything, that:
(1) a topos is a cartesian closed category with (2) an internal Heyting algebra Omega,
... [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
I cannot work out whether the message that Bill Lawvere originally sent in HTML was turned into plain text by him or by Bob Rosebrugh. Either way, I take exception to having the quotation of my message reduced in a way that suggests that I believe that the statements
(1) a topos is a cartesian closed category with (2) an internal Heyting algebra Omega,
are sufficient to characterise a topos. My objective was to move the discussion ON from quoting 1970s lemmas. If someone has indeed programmed these lemmas in Maple then it would be interesting to hear about that. (Maybe David Rydeheard's work on "electronic category theory" counts.) Otherwise "lemma" remains the appropriate word for them, not "algorithm". By the way, I consider it no disgrace to call something a lemma: see page 192 of my book. The point of the characterisation that I gave for a topos is that the difference between set theory (= a topos) on the one hand and topology and computation on the other is that quantification over arbitrary sets is allowed, but only over compact or overt spaces. This restriction brings us a little closer to what most people would call an algorithm. Paul Taylor [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
P.20 of Prof. Taylor's book briefly recounts the history of "function" as a (rigorously formulated) expression for numerical calculation using arithmetic and transcendental operations. More generally, Cox et al in "Ideals, Varieties, and Algorithms" define "algorithm" as a (rigorously formulated) set of instructions for manipulating input expressions resulting in output expressions. Algorithms may be presented in "pseudocode" as a prelude to implementation in a particular computer programming language such as Maple, or Haskell. Mac Lane-Moerdijk define an elementary (Lawvere-Tierney) topos to be a category with finite limits, finite colimits, exponentials, and a subobject classifier. So to prove a category is a topos it is necessary to prove that it has a subobject classifier. My query was stimulated by Lawvere-Schanuel in "Conceptual Mathematics" pp.340-341 proof that the category of directed graphs has a subobject classifier. They give a finite list of the possibilities for an element of a graph (dot or arrow) to belong to a subgraph. It seems to me such a list could be generated by an algorithm. Then there is a step explained by pictures leading to Omega(DirectedGraph). To me this hints at an algorithm too. Ellis D. Cooper [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
I copy an old post in the list that may be of interest to the present matter and that I had saved by curiosity but not acted upon afterwards. ________________________________________________________________________ this is to tell, or remind, readers about the Web-based interactive category-theory demonstrations I have on my site. Perhaps of interest to new students now an academic year is starting. They're at http://www.j-paine.org/cgi-bin/webcats/webcats.php . After some preamble, this page contains a form divided into sections. Each section generates a particular construct in the category of finite sets: e.g. a colimit, equaliser, or initial object. You can input sets and arrows, or let the demo choose its own. The output includes a diagram, and text explaining it. Cheers, Jocelyn Paine http://www.j-paine.org +44 (0)7768 534 091 Jocelyn's Cartoons: http://www.j-paine.org/blog/jocelyns_cartoons/ _______________________________________________________________________ greetings e.d. [For admin and other information see: http://www.mta.ca/~cat-dist/ ] Ellis D. Cooper wrote:
P.20 of Prof. Taylor's book briefly recounts the history of "function" as a (rigorously formulated) expression for numerical calculation using arithmetic and transcendental operations. More generally, Cox et al in "Ideals, Varieties, and Algorithms" define "algorithm" as a (rigorously formulated) set of instructions for manipulating input expressions resulting in output expressions. Algorithms may be presented in "pseudocode" as a prelude to implementation in a particular computer programming language such as Maple, or Haskell.
Mac Lane-Moerdijk define an elementary (Lawvere-Tierney) topos to be a category with finite limits, finite colimits, exponentials, and a subobject classifier. So to prove a category is a topos it is necessary to prove that it has a subobject classifier.
My query was stimulated by Lawvere-Schanuel in "Conceptual Mathematics" pp.340-341 proof that the category of directed graphs has a subobject classifier. They give a finite list of the possibilities for an element of a graph (dot or arrow) to belong to a subgraph. It seems to me such a list could be generated by an algorithm. Then there is a step explained by pictures leading to Omega(DirectedGraph). To me this hints at an algorithm too.
Ellis D. Cooper
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
participants (5)
-
Eduardo J. Dubuc -
Ellis D. Cooper -
F. William Lawvere -
Fred E.J. Linton -
Paul Taylor