Date: Fri, 10 Jan 1997 12:33:03 -0400 (AST) Subject: question on finiteness in toposes Date: Fri, 10 Jan 1997 12:57:02 MEZ From: Thomas Streicher One knows that for any topos E that the full subcategory of decidable K-finite objects forms a topos itself with 2 = 1+1 as subobject classifier. It is also said that E_kf, the full subcat of E on K-finite objects need not form a topos. That's what I could find out from PTJ's Topos Theory. The counterexample given there is E = Set^2 (where 2 = 0 -> 1). The K-finite objects in Set^2 are the surjective maps between finite sets. It is clear that E_kf is not closed under equalisers taken in E (!). Nevertheless, I think that E_kf itself does have equalisers : if f,g : X -> Y then take the equaliser e_0 of f_0 and g_0 and take the epi-mono-factorisation of x o e_0 : E_0 >---> X_0 | | | epi | x where X = X_0 -> X_1 V V E_1 >---> X_1 this clearly demonstrates that the inclusion E_kf >--> E does not preserve equalisers BUT it does not show that E_kf is not a topos. I would be interested in a reference or example where E_kf really is not a topos. Maybe, E = Set^2 alraedy works but it must have another defect than not being clossed under subobjects w.r.t. E because the decidable K-finite objects have this "defect" as well. Thomas Streicher Date: Sat, 11 Jan 1997 13:15:27 -0400 (AST) Subject: Re: question on finiteness in toposes Date: Sat, 11 Jan 1997 08:38:43 -0500 (EST) From: Peter Freyd The answer that first occures me for Thomas Streicher's question is that in Set^2_kf the terminator generates, hence if it were a topos it would have to be a boolean topos. Which it clearly isn't. Thomas wrote: One knows that for any topos E that the full subcategory of decidable K-finite objects forms a topos itself with 2 = 1+1 as subobject classifier. It is also said that E_kf, the full subcat of E on K-finite objects need not form a topos. That's what I could find out from PTJ's Topos Theory. The counterexample given there is E = Set^2 (where 2 = 0 -> 1). The K-finite objects in Set^2 are the surjective maps between finite sets. It is clear that E_kf is not closed under equalisers taken in E (!). Nevertheless, I think that E_kf itself does have equalisers : if f,g : X -> Y then take the equaliser e_0 of f_0 and g_0 and take the epi-mono-factorisation of x o e_0 : E_0 >---> X_0 | | | epi | x where X = X_0 -> X_1 V V E_1 >---> X_1 this clearly demonstrates that the inclusion E_kf >--> E does not preserve equalisers BUT it does not show that E_kf is not a topos. I would be interested in a reference or example where E_kf really is not a topos. Maybe, E = Set^2 alraedy works but it must have another defect than not being clossed under subobjects w.r.t. E because the decidable K-finite objects have this "defect" as well. Thomas Streicher Date: Sat, 11 Jan 1997 13:16:06 -0400 (AST) Subject: Re: question on finiteness in toposes Date: Sat, 11 Jan 1997 09:05:39 -0500 (EST) From: Peter Freyd Let me expand. If one bores into just why Set^2_kf can't be boolean and looks for a minimal example of its non-booleaness one inevitably lands on the object 2 -> 1. At first blush its lattice of subobjects does look boolean. Until one notices that there's a monomorphism from 2 -> 2 to 2 -> 1 (where 2 -> 2 is the identity map). Having noticed that, one has a quicker proof that it's not a topos: not every mono-epi is an equalizer. Date: Sun, 12 Jan 1997 16:42:58 -0400 (AST) Subject: RE: question on finiteness in toposes Date: Sun, 12 Jan 97 01:31 EST From: Fred E J Linton <0004142427@mcimail.com> Supplementing Peter's answer to Streicher's K-finiteness question, I recall Prop. 7.4 on p. 97 of SLNM #753, which states, for presheaf topoi E = (C^op, Sets), that, with E_Kf the full subcategory of K-finite E-objects: E_Kf is balanced iff it's a topos iff each K-finite is decidable iff C is a "2-way" category iff ... . Streicher's >--> sure isn't 2-way, hence ... . The rest of that 20 year old report on my student Acun~a's thesis with me is also fun. -- Fred Date: Mon, 13 Jan 1997 10:27:19 -0400 (AST) Subject: RE: question on finiteness in toposes Date: Sun, 12 Jan 1997 16:53:57 -0500 (EST) From: F William Lawvere Now that the question of finiteness as been reactivated here, may I bring up again the following question ? What concept of finiteness is appropriate for those important mathematical applications in topology for which K/S doesn't seem right ? (For example the equalizer closure of K/S or...??) Especially, a suitably "finite" module should be a vector bundle or a FAC in the sense of Serre so that our simplified topos theory could apply more directly to those things it should. Bill L Date: Tue, 14 Jan 1997 20:15:08 -0400 (AST) Subject: RE: question on finiteness in toposes Date: Tue, 14 Jan 1997 10:52:38 -0500 (EST) From: F William Lawvere Sorry, I used K/S for an abbreviation of what was called Kuratowski until someone pointed out that it was due to Sierpinski :an object whose mark belongs to the smallest sub-semilattice of its power set which contains the singleton map, or in case there is an NNO an object which in a suitable sense is locally enumerable by the segment under a section of the NNO . While the K/S definition is right for the construction of the object classifier over an arbitrary base topos (as Gavin showed) and hence for classifiers for various kinds of finitary algebras over an arbitrary base topos, still the theory of it in the last 25 years of topos theory seems to mainly be justified by formal analogy and/or independence relative to abstract set theory (=topos with choice). However there are important uses of "finiteness" in algebraic geometry and differential topology (where topos theory after all started) : Consider a ringed topos E,R . For example, the sheaves on an algebraic variety or on a Cinfty manifold. Within the abelian category of R-modules in E, we need to single out two important subcategories FAC (Serre 1955)=coherent sheaves..these tend to be an abelian subcategory and tend to vary covariantly as one E,R is mapped to another E',R' (thus give rise to an extensive K-homology) and vector bundles , which one thinks of as a finite-dimensional vector space varying smoothly over the base space of E ,so they cry out for internalization ; in algebraic geometry these are identified with locally FINITELY free R-modules... they vary contravariantly with E,R (so give rise to K-cohomolgy rigs which act on the FACs,ie intensives acting as densities on the extensives; with further conditions on E,R one can at the level of the riNgs generated by these rigs define a sort of Radon/Nikodym derivative via an alterating sum of Tors , but in general the covariant abelian category FAC and the contravariant tensored category Vect are distinct...The "derived category" of E,R (now allegedly replacing homological algebra in complex analysis and C*-algebra theory) should be the derived category of one of these two linear categories (here I mean dc in the linear sense..nonlinear "derived categories" are more like the stable homotopy of E)) Already the intuitionists speculated about (in effect) subobjects of K/S objects, and it seems we need something of the sort perhaps a category of finites closed under subquotient in order to define the notion of eg finitely-generated R-module in a way which not merely mimics abstract set theory but actually captures the vector bundles . Perhaps it will be easier if E itself satisfies a noetherian condition. It would be best if the desired content could be entirely int- ernalized to E,R but perhaps it is really relative to a base S,K..but perhaps without restriction on S ?? I hope this clarifies the problem. Sincerely Bill Date: Wed, 15 Jan 1997 10:33:30 -0400 (AST) Subject: RE: question on finiteness in toposes Date: Wed, 15 Jan 97 10:19 GMT From: Dr. P.T. Johnstone Not an answer to Bill's question (which I agree is an important one), but a minor correction. Bill wrote: While the K/S definition is right for the construction of the object classifier over an arbitrary base topos (as Gavin showed) and hence for classifiers for various kinds of finitary algebras over an arbitrary base topos, It isn't, and he didn't. Gavin used finite cardinals to construct the object classifier over an arbitrary base topos with NNO (and I subsequently extended the construction to finitary algebraic theories), but it doesn't work over a topos without NNO (and in particular it can't be made to work using K-finiteness). Andreas Blass showed that the existence of an object classifier for toposes over E implies that E has a NNO. Incidentally, I think it is correct to give credit to Kuratowski for the notion of K-finiteness. It's true that Sierpinski's paper was earlier, but his definition was a "global" one (i.e. he defined the class of all finite sets as the sub-semilattice of the universe generated by he singletons), whereas Kuratowski made the crucial observation that the finiteness of a particular set X can be determined locally (i.e. within the power-set of X), without which the notion could never have been imported into topos theory. Peter Johnstone Date: Wed, 15 Jan 1997 21:25:46 -0400 (AST) Subject: RE: question on finiteness in toposes Date: Wed, 15 Jan 1997 15:22:00 -0500 (EST) From: F William Lawvere Concerning Peter Johnstone's clarification: Of course I didn't mean that the object classifier could be constructed without an internal parameterizer for the finite objects in the base S .... but what exactly are the finite objects ? While the classifier as a topos is determined by the 2-category of bounded S-toposes , the site for it isn't. I was under the impression that an internal category parameterizing the objects which are both K-finite and separable(=decidable) could be used (while internal presheaves on "all" K=finites would presumably be much bigger..what does IT classify ?) Anyway my point was that at any rate no further extension of the notion of finiteness is needed for classifying in that sense the objects or the group objects in S-toposes, whereas by contrast it seems that to give the mathematically correct notion of "vector space for which there exists a finite basis" does need such an extension. In any topos, a subobject of a nonnon sheaf is always separable ; when is the converse true ? Perhaps there is an internal topos object V which is largest with respect to being fully embedded in the given topos E while at the same time having A as its subtopos of internal nonnon sheaves. Here by A is meant the Boolean internal topos mentioned above which parameterizes the separable K-finites of E (Fred recalled Acunya's work showing among other things that it is Boolean) and to say that V "is" fully embedded in E has sense for any internal category with a terminal object , namely we require that the canonical parametrized (="indexed") functor from V to E is an equivalence E(X,V)--> E/X for each X. The latter functor is defined by merely pulling back the fibration 1/V--> V of pointed objects in V. When the answer to the above question is affirmative, Johnstone's locally separable reflection Vsubqd will consist of subquotients and the K-finites may fit in . It seems that the inclusion of A in V will preserve sums but only certain epis. The idea is that V can't be too large since the inverse to the inclusion will enrich it in A. On Wed, 15 Jan 1997, categories wrote: > Date: Wed, 15 Jan 97 10:19 GMT > From: Dr. P.T. Johnstone > > Not an answer to Bill's question (which I agree is an important one), > but a minor correction. Bill wrote: > > While the K/S definition is right for the construction of > the object classifier over an arbitrary base topos (as Gavin > showed) and hence for classifiers for various kinds of > finitary algebras over an arbitrary base topos, > > It isn't, and he didn't. Gavin used finite cardinals to construct > the object classifier over an arbitrary base topos with NNO (and I > subsequently extended the construction to finitary algebraic > theories), but it doesn't work over a topos without NNO (and in > particular it can't be made to work using K-finiteness). Andreas > Blass showed that the existence of an object classifier for toposes > over E implies that E has a NNO. > > Incidentally, I think it is correct to give credit to Kuratowski for > the notion of K-finiteness. It's true that Sierpinski's paper was > earlier, but his definition was a "global" one (i.e. he defined the > class of all finite sets as the sub-semilattice of the universe > generated by he singletons), whereas Kuratowski made the crucial > observation that the finiteness of a particular set X can be determined > locally (i.e. within the power-set of X), without which the notion > could never have been imported into topos theory. > > Peter Johnstone Date: Fri, 17 Jan 1997 16:04:52 -0400 (AST) Subject: RE: Finiteness in Toposes Date: Fri, 17 Jan 1997 12:50:13 -0500 (EST) From: F William Lawvere Re: Finiteness in Toposes Jan 17 1997 This concerns the possibility , mentioned in my previous message, of two internal toposes of finite objects. The conjecture that there are two natural internal categories of finite objects is partly supported by the fact that there are two natural natural-numbers objects, the usual one N that parameterizes compositional iteration and another semicontinuous one L with the following features: 0) It is a rig, so receives a homomorphism from N and its elementary arithmetic starts out looking very similar. 1) But unlike N it has a least-number-property in the sense that it is inf-complete and better. 2) It can be constructed internally using truth-valued sheaves on N. 3) Hence it also contains a map from (big) omega, which permits (unlike N) the use of the standard method in finite combinatorics where (for example) a binary relation is considered as a matrix which is valued (not only in a rig where 1+1 = 1, but instead) in a rig in which natural numbers are distinct; the resulting generalized characteristic functions are added, multiplied, infed etc. according to the usual methods of arithmetic and analysis and then translated back into the combinatorics of the original finite structures. Of course, in each case one hopes that the answer to a combinatorial problem might turn out decidable, but that shouldnt require us to stay in the bounds of two-valued subsets in the course of a construction. 4) This internally-defined order-complete rig in E has also an external characterization if E is an S-based topos, namely it is the sheaf of germs of S-geometrical morphisms from E to the topos often called S-sets -through-time (I dont think that depends on any presumption that the N in S ,used to parameterize the transitions through time, coincides with its completion in S). In localic or open set terms, there is in S a (T sub zero) space whose points are N, but whose open sets have the usual order on N as their specialization order; continuous functions from any space E to this space are called semi-continuous and there is in E a sheaf of them. 5) The application to the variable linear algebra over algebraic or complex-analytic spaces needs L too, because dimension of a vector space is a semi-continuous function. More precisely, if A is a good module in a ringed topos E, R then for each X and E there should be a map X--> L which is the fiber-wise dimension of X*A. The basic case is perhaps that where E,R is an algebraic affine scheme, and the conceptual problem is to get at what sort of sets contained in A this dimension function is counting (or bounding). One should not expect that equality of dimension will imply isomorphism. This object L has been discussed for 25 years, but I dont know if anyone published the working-out of its properties and role. Bill Date: Wed, 22 Jan 1997 14:41:45 -0400 (AST) Subject: RE: Finiteness in Toposes Date: Wed, 22 Jan 1997 18:18:53 +0000 From: Steve Vickers >Date: Fri, 17 Jan 1997 12:50:13 -0500 (EST) >From: F William Lawvere > >Re: Finiteness in Toposes Jan 17 1997 > >This concerns the possibility , mentioned in my previous message, of two >internal toposes of finite objects. > > The conjecture that there are two natural internal categories of >finite objects is partly supported by the fact that there are two natural >natural-numbers objects, the usual one N that parameterizes compositional >iteration and another semicontinuous one L with the following features: > >... > > This object L has been discussed for 25 years, but I dont know if >anyone published the working-out of its properties and role. Am I right in thinking this to be Idl N, the ideal completion of the natural numbers (with their usual order)? I conjecture that this is a suitable value domain for the ranks of matrices over localic fields such as the reals: rank^-1{n} is not open, but rank^-1{n, n+1, n+2, ...} is. Then rank A is the set of natural numbers n such that we can find enough apartnesses to prove linear independence of n rows of A, and this is an ideal of N - the definition also smoothly incorporates infinite matrices. (Perhaps this is just one of the things that have have been discussed for 25 years and I'm reiventing it.) Anyway, I have investigated Idl N as a fixpoint object (in the sense of Crole and Pitts) in the category of Grothendieck toposes (modulo 2-categorical niceties that I didn't investigate too closely) in a paper "Topical Categories of Domains". Steve Vickers. Date: Thu, 23 Jan 1997 14:50:30 -0400 (AST) Subject: finiteness Date: Thu, 23 Jan 1997 19:43:40 EST From: carboni@vmimat.mat.unimi.it Regarding the last message of Bill on finiteness and the answer of Vickers, I would like to point out that the 25 years old reference of Bill should be the one at the bottom of page 14 of lesson 3 of 1972 Perugia Notes. In other words,the L he is suggesting should be the internalization of the following description: L consists of those ideals T : N---->Omega such that for all n Tn = Inf{Tm | m > n}. The precise meaning of this definition is explained in the given reference, as well as in Bill's messages. I hope that this is correct. Aurelio Carboni Date: Fri, 24 Jan 1997 10:56:07 -0400 (AST) Subject: Re: finiteness Date: Fri, 24 Jan 1997 10:54:59 +0000 From: Steve Vickers >From: carboni@vmimat.mat.unimi.it > >... L consists of those ideals T : N---->Omega such that for all n >Tn = Inf{Tm | m > n}. I understand this as saying that n is in the ideal iff every greater m is in the ideal (but I think the inequality m > n has to be non-strict to make sense of this). Hence it's really a filter of N. If that's correct, then my suggestion was wrong. L would be not Idl N, but Idl(N^op). That makes sense regarding dimensions, for if a real vector space is finitely presented using an mxn matrix A (presenting R^n/Im A) then its dimension is n-rank(A), so if rank(A) is in Idl(N), the dimension should be in Idl(N^op). (By the way, what's a full reference for the "Perugia Notes"?) Steve. Date: Mon, 27 Jan 1997 13:15:55 -0400 (AST) Subject: finiteness Date: Sun, 26 Jan 1997 18:16:28 EST From: carboni@vmimat.mat.unimi.it Regarding my last message on finiteness, I should have said `functors N---->Omega' instead of `ideals N--->Omega'. I repeat that I `think' that this is what Bill wanted to say, but I am not sure that I am correct. As for the reference of Bill's Perugia Notes, they are an internal publication of Perugia University in 1972 of the lectures given by Bill Lawvere when he was visiting that University. They should be available there (write to prof. L. Stramaccia, Dipartimento di Matematica, Universita' di Perugia, via Vanvitelli 1, 06123 Perugia, Italy, email: stra@gauss.dipmat.unipg.it). Also, they were quite spread out, so that you should be able to find somebody nearby you who has them. Other possibilities are asking the author himself and eventually myself. Aurelio Carboni.