Categories as a "foundation" for math
In the 1966 La Jolla conference volume appeared Lawvere's paper "The category of categories as a foundation for mathematics". Is it known just how much mathematics can be done using Lawvere's axiom scheme? My confusion on this point arises partly from a remark by Gray in his paper "The categorical comprehension scheme" in which he asserted that Lawvere's axioms couldn't do all that was claimed for them. Of course all of this predates the recognition that an elementary topos (with nn object) can be treated as a "universe of sets". I know that there has been some work (e.g. Joyal and Moerdijk) on constructing models of ZF set theory within categories with special properties. Can such categories be constructed using Lawvere's axioms? I hope this question makes sense but my skills in set theory and logic are pretty limited. Carl Futia 11-Mar-2005 13:01:41 -0400,22182;000000000001-00000000
Hello, Carl Futia wrote:
Is it known just how much mathematics can be done using Lawvere's axiom scheme? My confusion on this point arises partly from a remark by Gray in his paper "The categorical comprehension scheme" in which he asserted that Lawvere's axioms couldn't do all that was claimed for them. Of course all of this predates the recognition that an elementary topos (with nn object) can be treated as a "universe of sets".
As I see it, the problem is with the replacement scheme. Even if you start with ZF and classical logic, you have problems to express replacement in terms of first-order properties of the category of sets. An infinite cardinal a is called a strong limit cardinal, if b<a implies 2^a<b. For every strong limit cardinal a the category of all sets of cardinality < a is en elementary topos, regardless whether a is regular or not; regular strong lomit cardinals are inaccessible cardinals. Replacement should yield regularity of a, but how to express it? The easiest way to find a singular strong limit cardinal a is to start with an arbitrary infinite cardinal b(0), define b(n+1):=2^b(n), and a the sum of al b(n) for all natural number n. Then a is obviously singular because it is uncountable but the sum of countably many strictly smaller cardinals; a is a strong limit cardial because every cardinal <a is <b(n) for some n. Greetings Reinhard 12-Mar-2005 19:27:06 -0400,7017;000000000001-00000000
An infinite cardinal a is called a strong limit cardinal, if b<a implies 2^a<b. For every strong limit cardinal a the category of all sets of cardinality < a is en elementary topos,
In the definition of strong limit cardinal (with 2^b < a of course), some authors set a lower bound of either nonzero or uncountable on strong limit cardinals, seemingly arbitrarily. In view of the above connection, presumably a toposopher would argue for the former lower bound and against the latter. (One certainly wouldn't want to overlook the topos of finite sets, and, lacking Omega, the empty category cannot be a topos.) The inclusion of "nonzero" somewhere in the definition of strong limit cardinal would therefore nail down that detail at least for topos theory. That goes for Elephant A.2.1.2, which overlooks the case \kappa=0 by giving the above as the definition of what Peter J. calls a "limit power cardinal." (This seems an odd name for "strong limit cardinal" btw, given that no strong limit cardinal can be a power cardinal in the sense of arising as 2^a for some cardinal a. "Power limit cardinal" maybe, but why proliferate terminology?) If one were looking for differences in outlook between set theory and topos theory, the stranger notion of limit cardinal might be a more fruitful object to contemplate. A limit cardinal is defined as for a strong limit cardinal with a+ in place of 2^a, where a+ denotes the least cardinal strictly greater than a. Whereas 2^a is a perfectly good notion in a topos, with Cantor's theorem making it a fine successor operation for transfinite cardinals, a+ is the sort of thing I would have thought only a fan of ZFC could love. Or is there in fact a constructively acceptable notion of limit cardinal that is weaker than strong limit cardinal? For a constructivist the very need for "strong" in the definition of limit cardinal seems like a bad hangover from set theory. On the relevance of replacement to the relationship between set theory and category theory, how much better off are "working mathematicians" with replacement as a tool of their trade than with category theory? My impression is that category theory is used increasingly more in applied mathematics these days. Is there a comparable trend for replacement? Vaughan Pratt 14-Mar-2005 20:16:35 -0400,1428;000000000001-00000000
An infinite cardinal a is called a strong limit cardinal, if b<a implies 2^a<b. For every strong limit cardinal a the category of all sets of cardinality < a is en elementary topos,
In the definition of strong limit cardinal (with 2^b < a of course), some authors set a lower bound of either nonzero or uncountable on strong limit cardinals, seemingly arbitrarily. In view of the above connection, presumably a toposopher would argue for the former lower bound and against the latter. (One certainly wouldn't want to overlook the topos of finite sets, and, lacking Omega, the empty category cannot be a topos.) The inclusion of "nonzero" somewhere in the definition of strong limit cardinal would therefore nail down that detail at least for topos theory.
While we're about it, let's include "greater than 1" in the definition of regular cardinal please, so that 2 and omega are regular but 0 and 1 are not. This would ensure that, for each regular cardinal kappa, the endofunctor on Set taking A to the set of subsets (or nonempty subsets) of A of size < kappa is a monad. To put it another way, regularity means in essence "closed under dependent sum", and singleton is the unit of dependent sum. Paul 16-Mar-2005 11:16:08 -0400,5626;000000000000-00000000
Vaughan Pratt wrote in part:
A limit cardinal is defined as for a strong limit cardinal with a+ in place of 2^a, where a+ denotes the least cardinal strictly greater than a. Whereas 2^a is a perfectly good notion in a topos, with Cantor's theorem making it a fine successor operation for transfinite cardinals, a+ is the sort of thing I would have thought only a fan of ZFC could love.
Without using any form of Choice (not even Excluded Middle), you can define X+ (for any set X) as the set of ordinal numbers (where an ordinal number is a set equipped with a well founded, transitive, extensive binary relation; modulo isomorphism) that can be injected (as sets) into X; this is a quotient set (as we mod out by isomorphism of sets equipped with binary relations) of a subset (as we pick only the well founded, transitive, extensive binary relations) of the power set of X + X^2 (as we pick a subset of X and a binary relation on X that we restrict to the chosen subset). There is a big analogy that runs like this: a+ : 2^a :: aleph : beth :: Burali-Forti : Cantor :: more? X+ is the _Hartogs_number_ of X. -- Toby 16-Mar-2005 11:18:09 -0400,5075;000000000001-00000000
Dear colleagues, Reinhard Boerger has appropriately raised (as others before) the question of the relation of "replacement" with categories of sets. As stated in my 1964 - 1965 papers and as understood already before 1920 (1) closure under exponentiation is sufficient for a foundation for mathematics if by mathematics one means algebraic geometry, functional analysis, dynamical systems, partial differential equations, combinatorics, etc.; (2) but closure under exponentiation is not sufficient for certain speculations in which set theorists had developed an interest; if one wished, one could introduce stronger axioms. From the standpoint of a theory in the Frege-Peano style, it might appear that the replacement schema is the principal means for justifying those speculations. However, the left adjoint (Ua incl b iff a incl Pb) to the power set operation P is equally important, exploiting as it does the hidden structure as a FAMILY of sets that any set of such a theory has. The usual "image" version of the replacement operation does not give directly any sets of cardinality larger than its inputs; only in the case where the set it produces is "really" a family (of increasingly large sets, even if few) the union axiom can then give a larger result. On the other hand (assuming the axiom of choice) it is through producing larger cardinals that stronger axioms can express their strength. Thus, for a principle combining the union and replacement principles in a context where families are explicitly recognized as such, I proposed: If E ---> B is such that B exists and the fibers E sub b exist for each b, then E exists. Note that the usual way in geometry (hence in topos theory) for expressing a family indexed by B is by such a fibration over B. (In case the sets in the family are given as subsets of a set X, their union is a quotient of E modulo the usual "nerve" resolution.) Most families that arise in mathematics are easily put into this form, i.e. are not abstractly imposed from outside and hence do not need extra axioms to insure their existence; therefore the "internal limits and colimits" in topos theory can work well as tools for geometrical construction: they are honest adjoints but applied only to "internal families" and universal among internal families. The above existence principle is intended to have several interpretations, depending on how many and what kind of families are to be representable as fibers in the geometrical way. Besides the tautological "internal" answer (sufficient for most purposes) there are two distinct kinds of answers to the question: "From where do we take the families E to which we want to apply the "existence" assertion?" The subjective answer, attributed to Fraenkel and followed by most books on set theory is that we take E from the world of formulas. (For category theory we need to consider formulas of category theory (not epsilon theory), having one free variable ranging over points of B and another ranging over objects of the category and enjoying the "function" hypothesis up to isomorphism.) The other (objective) answer, similar in spirit to the (finitely axiomatizable) Bernays-Goedel theory, is that E lives initially in another category into which the one we are describing is embedded (either as a subcategory or as an internal category object). Such an embedding may or may not be full; when it is, then our objective "replacement" principle is revealed as equivalent to inaccessibility (of the category). As explained in the Appendix of the book "Sets for Mathematics" the demand for more sets has its source in the need to objectively parameterize mathematical objects. I can only recall two occasions where topos theorists needed more parameterizers than those obviously guaranteed by exponentiation and boundedness of geometric morphisms; in such situations one can explicitly assume more about the toposes under investigation (guided by available experience in avoiding inconsistencies). The best context for discussing these matters is the category of categories. However, assumptions of large cardinal strength can be applied equally to a category of categories and to the corresponding topos of discrete categories, since categories can be represented as finite diagrams of discrete categories. Greetings, Bill Lawvere REFERENCES: Elementary Theory of the Category of Sets, Proceedings of the National Academy of Science 52, No. 6 (December 1964), 1506-1511. An Elementary Theory of the Category of Sets, Preprint, University of Chicago, 1965, 32 pages. The Category of Categories as a Foundation for Mathematics, La Jolla Conference on Categorical Algebra, Springer Verlag (1966), 1 - 20. "Sets for Mathematics" with Robert Rosebrugh Cambridge University Press, 2003. On Sat, 12 Mar 2005 Reinhard.Boerger@FernUni-Hagen.de wrote:
Hello,
Carl Futia wrote:
Is it known just how much mathematics can be done using Lawvere's axiom scheme? My confusion on this point arises partly from a remark by Gray in his paper "The categorical comprehension scheme" in which he asserted that Lawvere's axioms couldn't do all that was claimed for them. Of course all of this predates the recognition that an elementary topos (with nn object) can be treated as a "universe of sets".
As I see it, the problem is with the replacement scheme. Even if you start with ZF and classical logic, you have problems to express replacement in terms of first-order properties of the category of sets. An infinite cardinal a is called a strong limit cardinal, if b<a implies 2^a<b. For every strong limit cardinal a the category of all sets of cardinality < a is en elementary topos, regardless whether a is regular or not; regular strong lomit cardinals are inaccessible cardinals. Replacement should yield regularity of a, but how to express it? The easiest way to find a singular strong limit cardinal a is to start with an arbitrary infinite cardinal b(0), define b(n+1):=2^b(n), and a the sum of al b(n) for all natural number n. Then a is obviously singular because it is uncountable but the sum of countably many strictly smaller cardinals; a is a strong limit cardial because every cardinal <a is <b(n) for some n.
Greetings Reinhard
17-Mar-2005 17:13:39 -0400,2360;000000000000-00000000
Reinhard.Boerger@FernUni-Hagen.de wrote:
As I see it, the problem is with the replacement scheme. Even if you start with ZF and classical logic, you have problems to express replacement in terms of first-order properties of the category of sets. An infinite cardinal a is called a strong limit cardinal, if b<a implies 2^a<b. For every strong limit cardinal a the category of all sets of cardinality < a is en elementary topos, regardless whether a is regular or not; regular strong lomit cardinals are inaccessible cardinals. Replacement should yield regularity of a, but how to express it?
cardinal< aleph_0. This is useful notationally as omega*2 refers to ordinal multiplication (so it has the same order type as omega \times 2 with lexicographic order) and should not confused with cardinal multiplication aleph_0 * 2, which of course is just aleph_0. I mention
I have always wondered why when talking about toposes from sets, people only mention "all sets of cardinality < something". Unless you have classes of some kind (with the attendant problem of making sense of categories of categories), it doesn't even make sense. If a is any limit ordinal, the category of all sets of rank < a is a topos. [for those who might have forgotten: Define V_a for >ordinals< a by transfinite induction as V_0 is the empty set, V_{a+1} is the power set of V_a, if a is a limit ordinal V_a is the union of V_b for b < a. Rank is very different from cardinality: {V_a} has rank a+1, which can be very large, but has cardinality 1, as small as it can get for any non-empty set.] [Another parenthetical remarks may be in order: I am making the customary intentional distinction between the >ordinal< omega and the this explicitly because, once, I saw V_{omega*2} taken to be as "the 'set' of all sets of cardinality < omega*2", whatever that may mean. Also, recently I noticed that in "Sketches of an Elephant", the first infinite cardinal referred to as $\omega$.] If a is a limit ordinal, but not the first, then V_a has a natural number object. So, in some sense V_{omega*2} is (very) small boolean topos with a natural number object. I find it useful to keep this example in mind when thinking about boolean toposes. For example, I would be very surprised if anything like Adams completion or Bousefield completion exist V_{omega*2}. [Bousfield completion can be made functorial before passing to the homotopy category. This is an useful fact. But the original aim can be expressed without functors: For any space X, there is a map X \to Y such that ...] So, I find the claim that mathematics that does not refer to 'all sets' etc can be done in toposes. Switching back to the original topic: Given ZF(C) - replacement, Fraenkel's version of replacement will prove the same theorems (just about sets) as reflection: To ZF(C) - replacement, add the assumption of an internal universe V that is elementarily equivalent to the 'whole universe'. It would be interesting to look at a topos theoretic version, but I have no idea of what the language of an internal topos means, much less how to say such things as "the natural number object of the internal topos T is the natural number object of the containing topos' [perhaps it is "N \times T \to T" is a small fibration, and the corresponding internal category of T is the natural number of object of T", but what is an internal category of an internal category?] Note that in the above, V will be an V_a, but a need not be a cardinal; for all I know, it may be consistent for a to have cofinality omega as an ordinal of the "big universe". Thus inaccessibility is a red herring when talking about a universe of sets that satisfy ZFC. BTW, do we know if Fraenkels' version of replacement (replacement for predicative functions as opposed to replacement for arbitrary functions) is inadequate for theorems "in the wild" that talk only about sets? [So theorems about "the category of all ...", or, say, model categories where the factorizations need not be given by predicative functions, do not count.] In other words, does mathematics really need Grothendieck universes? Nath Rao 16-Mar-2005 11:19:02 -0400,7295;000000000000-00000000
participants (7)
-
F W Lawvere -
Nath Rao -
Paul B Levy -
Reinhard.Boerger＠FernUni-Hagen.de -
Toby Bartels -
Topos8＠aol.com -
Vaughan Pratt