Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory internal-categories k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

Atrium > Mathematics, Physics & Philosophy: Question on size matters in algebraic theories

Bottom of Page

1 to 37 of 37

  1.  
    • CommentRowNumber1.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 2nd 2010

    I’m trying to deepen my understanding of algebraic theories. As an algebraic topologist, my categorical understanding of these matters is not great: I tend to think in terms of groups and rings and think of algebraic theories as “things like groups” rather than via monads or anything else.

    That source of intuition seems to be okay for Lawvere theories, but reading algebraic theory, and particularly following through to the comments on the ncafe here, it seems that my intuition might break down as size becomes an issue.

    I feel okay with the ideas expressed on the page Lawvere theory; namely that there is a “universal thingy” (say, group) and that all other thingies (groups and group-like things) are shadows of that Platonic thing (indeed, this was the theme of my colloquium on category theory). This seems to extend; certainly in my reading of C *C^*-algebras, I got the idea that there was a “universal C *C^*-algebra” and the only problem was that people didn’t know what it was (more precisely, what the larger free C *C^*-algebras were).

    So suppose I start off with some random category 𝒟\mathcal{D} in which there is a distinguished object, DD, and every other object is isomorphic to some product of DD. How much of Lawvere theory goes through for that? Presumably, I can consider a category of models in Set for that theory, and consider models of that theory in other categories, as product-preserving functors from 𝒟\mathcal{D} into Set or into Blah.

    The implication that I get from the cafe discussion is that the real distinction is between bounded and unbounded theories. Is that a fair statement? Thus C *C^*-algebras are “okay” since they are bounded, albeit not finite. Is there a simple test to see if my random category is bounded or not? (Apologies if this is on the pages somewhere, I think part of this project of understanding this might be involve cleaning up the relevant pages and linking them a bit better.)

    In particular, does anyone of a reference for the study of this process of starting with a random category 𝒟\mathcal{D} as described above and considering the corresponding algebraic theory? (Assuming that what I’ve described works and I haven’t overlooked something!)

    • CommentRowNumber2.
    • CommentAuthorTobyBartels
    • CommentTimeAug 2nd 2010

    I think that the boundedness that you want is that your random category 𝒟\mathcal{D} is small. If it is locally small and every object is isomorphic to D nD^n for some finite nn, then you have this.

    One really only thinks about unbounded theories because they sometimes arise in the wild. But they don’t so arise in the form of a large category 𝒟\mathcal{D}.

    • CommentRowNumber3.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 2nd 2010

    Definitely locally small (categories that aren’t this scare me). So then to be small I need every object to be isomorphic to D XD^X for XX drawn from some set (ℕ\mathbb{N}, in your example) - am I right?

    Right, but my random category might not have this property itself and yet be equivalent to one (in terms of the theory so-defined) to one that does. For example, I could take the theory of groups and just throw in all arbitrary powers of my universal group object. Then in any complete category, the models of this theory are equivalent to that of groups. Can you (or anyone) think of how to tell if my random category is of this form?

    • CommentRowNumber4.
    • CommentAuthorTobyBartels
    • CommentTimeAug 2nd 2010

    Definitely locally small (categories that aren’t this scare me).

    It’s not really necessary here, but nobody should ever have to be afraid of large sizes.

    Then in any complete category, the models of this theory are equivalent to that of groups.

    No, you’re mixing two doctrines here.

    If you’re working in the doctrine of categories with all products, then the theory of groups is precisely the category that you constructed, and a model is a functor that preserves all products, and so a model of this theory is a group.

    However, we’ve been working in the doctrine of categories with finite products, where a model is a functor that preserves finite products, but it need not preserve all products. So a model of this theory consists of rather more information than a single group GG, since the infinitary powers don’t actually have to be of the form G κG^\kappa.

    • CommentRowNumber5.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 2nd 2010

    I didn’t mean to mix two doctrines! They just happened to be next to each other on the shelf and I grabbed the wrong one.

    Seriously, what I had in mind was that when I make this “throw in all products” extension then I would also require my functors (when defining what a model means) to preserve all products. So my infinitary powers would all be of the form G κG^\kappa. So when I ponder about enlarging the “finite” bit of a Lawvere theory, I try to do so consistently and enlarge it everywhere I see it.

    • CommentRowNumber6.
    • CommentAuthorTobyBartels
    • CommentTimeAug 2nd 2010

    when I make this “throw in all products” extension then I would also require my functors (when defining what a model means) to preserve all products

    Good, then you’re not mixing doctrines; you’re simply changing doctrines. Is that what you meant to do all along?

    • CommentRowNumber7.
    • CommentAuthorTobyBartels
    • CommentTimeAug 2nd 2010
    • (edited Aug 3rd 2010)
    Maybe I’ve been reading your whole post wrong from the beginning. Are you saying this?:

    Recall that a Lawvere theory is a category with finite products with an object XX such that every object is of the form X nX^n for some finite cardinal number nn. Now let us move from the doctrine of finite products to the doctrine of small products. Then a Lawvere theory becomes a category with small products with an object XX such that every object is of the form X nX^n for some small cardinal number nn. How much of what we know about Lawvere theories continues to work in this situation?

    I will call this an infinitary Lawvere theory. Then one question is whether every infinitary Lawvere theory gives a monad on SetSet. Then the answer is No, precisely because an infinitary Lawvere theory might not be bounded. (Edit: This is not a precise reason, since not every monad is bounded either. Furthermore, a locally small infinitary Lawvere theory will give a monad, as Mike says below.)

    Now fix a cardinal number κ\kappa. (We might want κ\kappa to be regular, or something like that.) Then we have a doctrine of categories with products indexed by a cardinal number less than κ\kappa. Let us call such a category a κ\kappa-ary Lawvere theory if it has an object XX such that every object is of the form X nX^n for some cardinal number n<κn \lt \kappa. Then every κ\kappa-ary Lawvere theory does give a monad on SetSet.

    Conjecture: An infinitary Lawvere theory is bounded if and only if it is a κ\kappa-ary Lawvere theory for some small cardinal number κ\kappa. (Note that we have inclusions of doctrines FinProd→κProd→ProdFin Prod \to \kappa Prod \to Prod, which are left adjoint to the inclusions of 22-categories Prod→κProd→FinProdProd \to \kappa Prod \to Fin Prod, so this condition makes sense.)

    • CommentRowNumber8.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 2nd 2010

    Yes, that’s what I’m saying. So:

    1. If I want free objects, does it need to be monadic?
    2. Since I can simply extend doctrines by adding in products, producing the sequence FinProd→κProd→ProdFin Prod \to \kappa Prod \to Prod as you say, to say that an infinitary Lawvere theory is bounded if and only if it is a κ\kappa-ary Lawvere theory for some small cardinal number κ\kappa (as you conjecture) feels a bit evil. Wouldn’t it be better to say “If it is in the image of κProd→Prod\kappa Prod \to Prod for some small cardinal number κ\kappa”?
    3. If the answer to that is “Yes” (or even “Yes, but …”) then I can ask my real question: how do I recognise this image?
    • CommentRowNumber9.
    • CommentAuthorMike Shulman
    • CommentTimeAug 2nd 2010

    Then one question is whether every infinitary Lawvere theory gives a monad on Set. Then the answer is No, precisely because an infinitary Lawvere theory might not be bounded.

    I don’t understand exactly what “bounded” is being used to mean, but I thought the conclusion of the cafe discussion linked above was that an infinitary (locally small) Lawvere theory really is exactly the same as a monad on Set.

    Whatever the case is, when we work it out we should make sure to nLabify it clearly, so we don’t have to work it out a third time.

    If I want free objects, does it need to be monadic?

    Yes. I suppose “free objects” technically means just having a left adjoint, which is in general not the same as being monadic, but I think for anything called an “algebraic theory,” having a left adjoint is sufficient to be monadic.

    • CommentRowNumber10.
    • CommentAuthorTobyBartels
    • CommentTimeAug 3rd 2010

    @ Andrew

    Wouldn’t it be better to say “If it is in the image of κProd→Prod\kappa Prod \to Prod for some small cardinal number κ\kappa”?

    That is the definition of ‘if it is a κ\kappa-ary Lawvere theory for some small cardinal number κ\kappa’. (And ‘is’ in ‘is in the image’ should be interpreted up to equivalence too.) Just like the definition of whether a real number is rational is if it is in the image of ℚ→ℝ\mathbb{Q} \to \mathbb{R}. I tried to make that clear by mentioning κProd→Prod\kappa Prod \to Prod and writing ‘so this condition makes sense’.

    For the rest of my reply to you, Andrew, see my upcoming reply to Mike.

    • CommentRowNumber11.
    • CommentAuthorTobyBartels
    • CommentTimeAug 3rd 2010
    • (edited Aug 3rd 2010)

    @ Mike (and Andrew)

    an infinitary (locally small) Lawvere theory really is exactly the same as a monad on Set

    For a counterexample (edit: this is not a counterexample, since it is not locally small), take the theory of complete lattices. This is an infinitary Lawvere theory generated by two commutative operations sup n,inf n:X n→X\sup_n, \inf_n\colon X^n \to X for each cardinal number nn (which take an nn-set of elements to their supremum or infimum) and some equations that I hope are obvious. But there are no free complete lattices on a set with more than two elements.

    The problem is that we not only have a large number of morphisms (obviously, since the category is large) but also a large number of generating morphisms sup n,inf n\sup_n, \inf_n; see below.

    I think for anything called an “algebraic theory,” having a left adjoint is sufficient to be monadic.

    One theorem along these lines is that any equationally presented category with free objects is monadic.

    Andrew wrote:

    how do I recognise this image?

    If you’re given an infinitary Lawvere theory in a way that looks algebraic, such as my description of the theory of complete lattices was meant to be, then you can recognise it as monadic if you use only a small set of operations to generate all of the morphisms. (That’s a theorem at the previous link.)

    H’m, and that shows how to prove my conjecture. If we need only a small set of operations, then there is largest arity nn of these operations, hence it lives in n +Prodn^+ Prod; QED.

    • CommentRowNumber12.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 3rd 2010
    • (edited Aug 3rd 2010)

    Let me test to see if I’m following so far. In my random category, 𝒟\mathcal{D}, where every object is isomorphic to a product of some chosen object, say RR, I want to know whether or not this is algebraic. So I want to know if it is generated by a small set of morphisms. I want to say that this happens if (and only if) there is some cardinal κ\kappa such that for every set XX of cardinality larger than κ\kappa, every morphism R X→RR^X \to R factors through R κR^\kappa (note that this is a per morphism factorisation). Is that right?

    The example that springs to mind here is of totally convex space where although nominally we can talk of arbitrarily infinite convex sums, any such will have at most countably non-zero terms.

    I need to think some more about this, though, particularly about the example with lattices, because I thought that I had an argument that said that in the theory defined by my random category 𝒟\mathcal{D} then there were free algebras and the free algebra on XX is the product-preserving functor 𝒟(R X,−)\mathcal{D}(R^X,-). Thus the underlying set of the free algebra on XX is 𝒟(R X,R)\mathcal{D}(R^X,R). The adjunctions are given by:

    ε X:X→𝒟(R X,R) \epsilon_X \colon X \to \mathcal{D}(R^X,R)

    sends xx to the xxth projection R X→RR^X \to R, whilst the other natural transformation is itself a natural transformation

    η V:𝒟(R |V|,−)→V \eta_V \colon \mathcal{D}(R^{|V|},-) \to V

    (here V:𝒟→SetV \colon \mathcal{D} \to Set is a product-preserving covariant functor and |V|=V(R)|V| = V(R) is its “underlying set”) and so, by Yoneda, is given by an element of V(R |V|)V(R^{|V|}). Since VV is product-preserving, we have:

    V(R |V|)≅V(R) |V|≅Set(|V|,V(R))=Set(V(R),V(R)) V(R^{|V|}) \cong V(R)^{|V|} \cong Set(|V|,V(R)) = Set(V(R),V(R))

    and so V(R |V|)V(R^{|V|}) has a specific element corresponding to the identity in Set(V(R),V(R))Set(V(R),V(R)). These give (I believe) the required adjunctions.

    I don’t see where size becomes an issue in the above.

    • CommentRowNumber13.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 3rd 2010

    Ah, I have an idea of where size might make an appearance. In my set-up, the algebras are product-preserving functors 𝒟→Set\mathcal{D} \to Set. The morphisms are natural transformations between such functors. But how do I know that such natural transformations form a set? Only if 𝒟\mathcal{D} satisfies some smallness condition. As my functors are product-preserving, I don’t need to know that 𝒟\mathcal{D} is a small category, but that it is generated by a small category where in generating one category from another I’m allowed to throw in products as well as isomorphisms (hope that made sense).

    How’m I doing?

    • CommentRowNumber14.
    • CommentAuthorTobyBartels
    • CommentTimeAug 3rd 2010

    there is some cardinal κ\kappa such that for every set XX of cardinality larger than κ\kappa, every morphism R X→RR^X \to R factors through R κR^\kappa

    The hypothesis that X>κX \gt \kappa is unnecessary but probably harmless. However, you need to require that the factor R X→R κR^X \to R^\kappa is one of the X κX^\kappa structure morphisms of a category with products; otherwise the condition is trivial.

    nominally we can talk of arbitrarily infinite convex sums, any such will have at most countably non-zero terms

    That’s a good analogy! Nominally we can talk of operations with abitrarily infinite arities, but any such will depend on at most κ\kappa arguments.

    I don’t see where size becomes an issue in the above.

    H’m, let me try this with complete lattices, setting XX to 33. (Because already the free complete lattice on 33 elements is large, or so Johnstone says on page 31 of Stone Spaces, although I have not followed the proof in detail.) Certainly the underlying set should be 𝒟(R 3,R)\mathcal{D}(R^3,R). So maybe 𝒟\mathcal{D} is not locally small???

    • CommentRowNumber15.
    • CommentAuthorTobyBartels
    • CommentTimeAug 3rd 2010

    I want to prove a theorem that if 𝒟\mathcal{D} and Prod[𝒟,Set]Prod[\mathcal{D},Set] are locally small (and these seem to be independent questions), then 𝒟\mathcal{D} must be bounded. (Then this might be the result that Mike recalled in #9.) But I have to go now.

    • CommentRowNumber16.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 3rd 2010

    One problem I have with the complete lattices example is that it’s not clear to me what 𝒟\mathcal{D} and RR should be. For example, if we wanted to recover groups then we can take 𝒟\mathcal{D} to be the opposite category of the full subcategory of groups consisting of (things isomorphic to) the free groups - much as in the example at Lawvere theory. As free lattices don’t exist, the machinery doesn’t get started!

    So above you had your inclusions of 2-categories: FinProd→κProd→ProdFinProd \to \kappa Prod \to Prod. In this, we could insert ⋃κProd\bigcup \kappa Prod between the second and third terms. Then ⋃κProd\bigcup \kappa Prod would include (?) into the 2-category AlgCatAlgCat of algebraic categories, but this wouldn’t extend to ProdProd and, moreover, wouldn’t be surjective (in any sense) as it wouldn’t hit things like complete lattices.

    • CommentRowNumber17.
    • CommentAuthorTobyBartels
    • CommentTimeAug 3rd 2010

    If 𝒟\mathcal{D} is the infinitary Lawvere theory for complete lattices, then the objects of 𝒟\mathcal{D} are just cardinal numbers (or sets), although we write the number nn as R nR^n (with RR in place of R 1R^1 and 11 in place of R 0R^0, to be completely precise) when thinking of it as an object of 𝒟\mathcal{D}. From this perspective, it’s only the morphisms that are interesting; a morphism from R mR^m to R nR^n is a family of nn words, each written using mm variables, in the operations of complete lattices, modulo equations that follow from the axioms of a complete lattice. In other words, it’s a family of nn expressions built out of sup\sup, inf\inf, and mm variables, modulo an equivalence relation.

    And indeed, this 𝒟\mathcal{D} is not locally small; Wikipedia has a proof (which is the same as Johnstone’s and presumably goes back to Hales) that 𝒟(R 3,R)\mathcal{D}(R^3,R) is a proper class. (This result should have been obvious to me after reading Andrew’s #12, but it was helpful to actually look at the proof again.) Nevertheless, Prod[𝒟,Set]Prod[\mathcal{D},Set] is locally small, since it is CompLatComp Lat.

    Conversely, if 𝒟\mathcal{D} is locally small, we don’t need that Prod[𝒟,Set]Prod[\mathcal{D},Set] must be locally small. For a counterexample, let 𝒟\mathcal{D} be the free category with products on a proper class XX of objects; an object of 𝒟\mathcal{D} is a small family of elements of XX and a morphism from one family to another is a way of expressing the first as a multisubset of the second, and the number of ways to do this is bounded by their cardinalities. Now let F:𝒟→SetF\colon \mathcal{D} \to Set take each generator to 22, so that it takes a general object, thought of as a family, to its cardinality. Then a natural transformation from FF to itself consists of XX independent endomorphisms of 22, and there are 4 X4^X of these.

    But if 𝒟\mathcal{D} and Prod[𝒟,Set]Prod[\mathcal{D},Set] are both locally small, then I agree with the argument in Andrew #12. So presumably this is the result that Mike quotes from the Café (due there to Sridhar) that every infinitary Lawvere theory gives a monad; you don’t count it as an infinitary Lawvere theory unless it’s locally small (because who wants to deal with categories that aren’t?) and its category of product-preserving functors to SetSet is locally small (because how can you use it in algebra if it isn’t?). I thought that I’d read that discussion earlier, but now I see that there was much more to it!

    • CommentRowNumber18.
    • CommentAuthorTobyBartels
    • CommentTimeAug 3rd 2010

    I see the converse that Mike just added to the bottom of functor category. Basically, this says that in the doctrine of all categories, a Lawvere theory, if required to be useful in the sense that both it and its category of functors to SetSet are locally small, must itself be small.

    Here we are working in the doctrine of categories with products, so the Lawvere theory need not actually be small. But it still must satisfy a smallness condition, as Andrew suggested, being generated in a small way.

    • CommentRowNumber19.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 3rd 2010

    I think I understood that! And I’m actually coming to realise that keeping track of the size of everything is important. Now I just need to check whether any of the examples I have in mind satisfy the required conditions. They’re all locally small, so I need to check that is locally small. I guess that finding factorisations is the way to go.

    • CommentRowNumber20.
    • CommentAuthorTobyBartels
    • CommentTimeAug 3rd 2010
    • (edited Aug 4th 2010)

    Another condition that you could use is that 𝒟\mathcal{D} has a small subcategory 𝒞\mathcal{C} such that the sub(category with products) of 𝒟\mathcal{D} spanned by 𝒞\mathcal{C} is all of 𝒟\mathcal{D}; that is, every morphism in 𝒟\mathcal{D} is a composite of product projections and tuplings of morphisms in 𝒞\mathcal{C}. (So basically, we are bounding the number of generating morphisms rather than bounding the size of the generating objects.) In the doctrine of all categories, the analogue of this is is that 𝒟\mathcal{D} has a small subcategory 𝒞\mathcal{C} such that 𝒞\mathcal{C} is all of 𝒟\mathcal{D}, which is to say that 𝒟\mathcal{D} itself is small, hence the theorem that Mike added to the end of functor category.

    By the way, my uses of ‘is’ should all be interpreted up to isomorphism or equivalence, as appropriate.

    • CommentRowNumber21.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 4th 2010

    By the way, my uses of ‘is’ should all be interpreted up to isomorphism or equivalence, as appropriate.

    I was working under that assumption (Axiom of Toby), but thanks for the confirmation.

    Right! This is all looking very nice. I just need to go back to my examples of 𝒟\mathcal{D} and see what happens in practice.

    • CommentRowNumber22.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 4th 2010
    • (edited Aug 4th 2010)

    Wait, wait, wait … I’ve just confused myself again (easily done, I know).

    We have 𝒟\mathcal{D} as above: a complete, locally small category wherein every object is equivalent to some power of a specified object, say DD. We want to consider the category of product-preserving functors 𝒟→Set\mathcal{D} \to Set, this is what Toby calls Prod[𝒟,Set]Prod[\mathcal{D},Set]. The question is: is that locally small?

    I think it is. I think that the natural transformations from V 1V_1 to V 2V_2 injects in to the set Set(V 1(D),V 2(D))Set(V_1(D),V_2(D)). Firstly, the map is obvious: send α:V 1→V 2\alpha \colon V_1 \to V_2 to its value at DD. For the injection, we need to show that if α D=β D\alpha_D = \beta_D then α=β\alpha = \beta. This comes from the fact that V 1V_1 and V 2V_2 are product preserving: for every projection p x:D X→Dp_x \colon D^X \to D we have a commutative diagram:

    V 1(D X) →α D X V 2(D X) V 1(p x)↓ ↓V 2(p x) V 1(D) →α D V 1(D) \array{ V_1(D^X) & \overset{\alpha_{D^X}}{\to} & V_2(D^X) \\ \mathllap{V_1(p_x)} \downarrow & & \downarrow \mathrlap{V_2(p_x)} \\ V_1(D) & \overset{\alpha_D}{\to} & V_1(D) }

    As V 1V_1 and V 2V_2 are product-preserving, V 1(p x)=p xV_1(p_x) = p_x and V 2(p x)=p xV_2(p_x) = p_x. Hence, by the characterisation of products, α D X\alpha_{D^X} is uniquely determined by α D\alpha_D.

    Thus Prod[𝒟,Set]Prod[\mathcal{D},Set] is locally small.

    Am I right? Or is there some flaw that I’ve overlooked?

    • CommentRowNumber23.
    • CommentAuthorTobyBartels
    • CommentTimeAug 4th 2010

    every object is equivalent to some power of a specified object, say DD

    It used to be RR. Earlier in the thread it was XX. I’m going to stick with RR in this comment.

    Am I right?

    Yes, I think that you’re right!

    In #17, I gave an example of a complete, locally small category 𝒟\mathcal{D} such that Prod[𝒟,Set]Prod[\mathcal{D},Set] is not locally small, but my example was not an infinitary Lawvere theory, because there was no single object RR that generated the others. Instead, my example was a many-sorted infinitary Lawvere theory (which I noticed but didn’t mind) with a large number of sorts (which I didn’t really notice). Your proof generalises to any many-sorted infinitary Lawvere theory with a small number of sorts, since then Nat(V 1,V 2)Nat(V_1,V_2) injects into ∏ iSet(V 1(R i),V 2(R i))\prod_i Set(V_1(R_i),V_2(R_i)). Conversely, if Prod[𝒟,Set]Prod[\mathcal{D},Set] is locally small, then (by previous arguments) we have a small subcategory 𝒞\mathcal{C} that spans 𝒟\mathcal{D}, so we can take the sorts to be the objects of 𝒞\mathcal{C}, so again we have a many-sorted Lawvere theory with a small number of sorts.

    So to sum up, in order to get the best results, we should define a many-sorted infinitary Lawvere theory to be a complete category 𝒟\mathcal{D} that is

    1. locally small and
    2. equipped with a small family of objects (the sorts) such that every object is a small product of these sorts,

    rather than the naïve definition of any complete category (equipped with a family of sorts if you like, but with the option of letting every object be a sort). Then it is a theorem that Prod[𝒟,Set]Prod[\mathcal{D},Set] is locally small, so it is the category of 𝒟\mathcal{D}-modules (aka 𝒟\mathcal{D}-algebras or 𝒟\mathcal{D}-models). More generally, if 𝒮\mathcal{S} is any locally small complete category, then Prod[𝒟,𝒮]Prod[\mathcal{D},\mathcal{S}] is locally small, so it is the category of 𝒮\mathcal{S}-valued 𝒟\mathcal{D}-modules.

    In the finitary case, if a many-sorted Lawvere theory 𝒟\mathcal{D} is equipped with a small family of sorts (and is locally small), then 𝒟\mathcal{D} itself must be small; so you can actually take any small finitely-complete category as a many-sorted Lawvere theory, letting every object be a sort by default. When you generalise to infinitary Lawvere theories, 𝒟\mathcal{D} will no longer be small (except in a few degenerate cases), but this doesn’t mean that you simply drop the smallness clause; you still have to let the objects of 𝒟\mathcal{D} be generated by a small family of sorts. (And you still have to require 𝒟\mathcal{D} to be locally small if you want the theorems to generalise, such as the existence of free modules.) This was throwing me off earlier.

    • CommentRowNumber24.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 4th 2010

    every object is equivalent to some power of a specified object, say DD

    It used to be RR. Earlier in the thread it was XX. I’m going to stick with RR in this comment.

    Sorry! “Mathematics is that which is invariant under change of notation.”

    I agree with your definition - that seems a good one. Thinking about the reference Mike added at functor category, we’re effectively saying that when we look at product-preserving functors, then “small” means “set of generators/sorts”. So presumably there’s a theorem that says that 𝒟\mathcal{D} and Prod[𝒟,Set]Prod[\mathcal{D},Set] are locally small if and only if 𝒟\mathcal{D} has a small set of sorts. And to check that I understand the example of complete lattices: one just cannot get started with this machinery in that case.

    That is Fantastic - captial ’F’ for sure - as I wasn’t looking forward to digging deep in the definitions of the morphisms in my category.

    So, is this known? Are these definitions and results that we’re rediscovering (at least, for me, the rest of you may know them already)? I want to use this stuff and I’m quite happy to put in a reference, or put in the whole argument.

    At the very least, we should nLabify it - or am I getting ahead of myself?

    • CommentRowNumber25.
    • CommentAuthorTobyBartels
    • CommentTimeAug 4th 2010

    So presumably there’s a theorem that says that 𝒟\mathcal{D} and Prod[𝒟,Set]Prod[\mathcal{D},Set] are locally small if and only if 𝒟\mathcal{D} has a small set of sorts.

    Your argument in comment #22 generalises to prove that Prod[𝒟,Set]Prod[\mathcal{D},Set] is locally small if 𝒟\mathcal{D} has a small set of sorts. The argument from Freyd and Street generalises to prove that 𝒟\mathcal{D} has a small set of sorts if both 𝒟\mathcal{D} and Prod[𝒟,Set]Prod[\mathcal{D},Set] are locally small.

    However, it is possible that 𝒟\mathcal{D} has a small set of sorts yet is not locally small; the theory of complete lattices, as defined in my comment #17, is an example.

    I would like to prove that 𝒟\mathcal{D} has a small set of sorts if Prod[𝒟,Set]Prod[\mathcal{D},Set] alone is locally small, or else find a counterexample, but I haven’t got that yet.

    And to check that I understand the example of complete lattices: one just cannot get started with this machinery in that case.

    One can get started: one has 𝒟\mathcal{D} (although it’s not locally small), and Prod[𝒟,Set]=CompLatProd[\mathcal{D},Set] = Comp Lat (which is locally small, as it must be since there is only 11 sort). But one can’t go on to prove (as in your comment #12) that the functor from Prod[𝒟,Set]Prod[\mathcal{D},Set] to SetSet generated by V↦V(R)V \mapsto V(R) has a left adjoint, because 𝒟\mathcal{D} is not locally small.

    So, is this known?

    Mike’s been quiet lately. Maybe he knows?

    At the very least, we should nLabify it - or am I getting ahead of myself?

    I’d like to make sure that we understand everything, but yes. I’ll put a stub at infinitary Lawvere theory, pointing to this discussion.

    • CommentRowNumber26.
    • CommentAuthorMike Shulman
    • CommentTimeAug 5th 2010

    Mike’s been quiet lately.

    Mike’s been very busy lately with unrelated stuff, like buying a house.

    But I also don’t know whether this stuff is “known” – although I haven’t encountered a lot of people thinking about infinitary Lawvere theories.

    I also feel like there is something interesting to be said here relating back to the “levels of embodiment” conclusion we reached back at the Cafe. Saying that the category is locally small and has a small set of sorts is more or less saying that it’s small when considered as a category with virtual finite products, i.e. at one lower level of embodiment. One could then ask for stronger finiteness assumptions like additionally having a small generating set of operations, or also a small generating set of axioms, corresponding to the lower levels of embodiment. It seems like the general fact is that “small theories” at any level of embodiment are well-behaved, but that a small theory at one level of embodiment can become large when embodied further (at least when the doctrine is large, as for the doctrine of finite products).

    • CommentRowNumber27.
    • CommentAuthorzskoda
    • CommentTimeAug 9th 2010

    Buying a house ? Are you getting a permanent job ? Did I miss some good news ?

    • CommentRowNumber28.
    • CommentAuthorDavidRoberts
    • CommentTimeAug 10th 2010

    A possibly relevant example is in the following email from Gordon Plotkin on the categories list (I’ve taken the liberty of texing the asciimaths):

    Dear Sergey, In the paper by Hyland, Levy, Power and myself, Combining algebraic effects with continuations, there is a proof that the tensor of the continuations monad R (R −)R^{(R^-)} (|R|≥2)(|R| \ge 2) with itself, or, indeed with any monad TT with a constant (i.e. such that T(0)T(0) is not empty), is the trivial monad.

    It is not hard to see this directly, via large Lawvere theories. The large Lawvere theory LL of the continuations monad has:

    L(X,Y)=Set(R X,R Y)L(X,Y) = Set(R^X,R^Y)

    and so the constants L(0,1)L(0,1) correspond to maps 1→R1 \to R. Further, using two distinct constants, any two operations R X→R YR^X \to R^Y can be coded up into one operation R (X+1)→R YR^{(X +1)} \to R^Y and then recovered via the two constants. Given maps of large Lawvere theories L T→M←LL_T \to M \leftarrow L such that the images of any two operations in L TL_T and LL commute, as L TL_T has a constant all (the images of) constants in LL are identified, as usual, but then so are all images of any two operations R X→R YR^X \to R^Y (which will, for example, include all pairs of projections) and so MM is trivial.

    A more general theorem is also proved in the paper which has as a consequence that the tensor of any monad with rank with the continuations monad exists.

    • CommentRowNumber29.
    • CommentAuthorMike Shulman
    • CommentTimeAug 10th 2010

    Are you getting a permanent job?

    No, but my wife is, and in a place where we both really want to live (San Diego). I’ve got 2 years left on my portable NSF postdoc, after which point there are many options. (-:

    • CommentRowNumber30.
    • CommentAuthorDavidRoberts
    • CommentTimeAug 10th 2010
    • (edited Aug 10th 2010)

    In #28 I’m assuming that ’large Lawvere theories’ might have something to do with the infinitary theories discussed here. The rest is just context.

    • CommentRowNumber31.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 10th 2010

    (Following on from DR’s two comments)

    I’d noticed that message go flying by on the categories mailing list as well and wondered as to its relevance.

    Clearly, there’s parts of the story of “infinitary Lawvere theory” that are well-known and well-studied. Things like C *C^*-algebras are an obvious example of a non-finite Lawvere theory (that is, nonetheless, finitely presented) and compact Hausdorff spaces being another (is that one bounded?), whilst the theory of complete lattices is sort-of similar but not quite. I guess what my plan for this at the moment is:

    1. Finish off the proofs on infinitary Lawvere theory. Even if this stuff is standard, it’s not standard to me and I’d like to be sure that I understand it. The best way being to prove the stuff! Plus it’s a good exercise that’ll increase my skills at handling categories, I hope.
    2. Trace the notions in the literature. This might also involve a well-phrased question on both the categories mailing list and MO.
    3. In particular, track down references that deal with the general theory as that’s what I’m primarily interested in.
    • CommentRowNumber32.
    • CommentAuthorSridharRamesh
    • CommentTimeAug 10th 2010

    Just to clarify, though I think it’s probably already become clear by now, the notion of “infinitary Lawvere theory” which I was discussing in the nCafe conversation was “a locally small category whose objects are of the form R^k for each small arity k (i.e., it has small products, and its objects are generated by this from a single object))”. Such unsorted infinitary Lawvere theories L correspond precisely to monads M on Set and furthermore the category Prod[L, Set] is equivalent to the category of Eilenberg-Moore algebras for the corresponding monad M.

    • CommentRowNumber33.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 10th 2010

    Sridhar: do you have a reference for the correspondence (between such Lawvere theories and monads) and the equivalence of Prod[L,Set]Prod[L,Set] and EM-algebras? I would imagine that both would need only the obvious tweaking to make the corresponding statements in the many-sorted cases.

    • CommentRowNumber34.
    • CommentAuthorTobyBartels
    • CommentTimeAug 10th 2010

    Thanks, Sridhar. That had eventually become clear to me, but it’s helpful to have your confirmation.

    • CommentRowNumber35.
    • CommentAuthorSridharRamesh
    • CommentTimeAug 10th 2010

    @Andrew: No, I’m afraid I don’t have any reference; it’s just something I worked out for myself when I was first exposed to the idea of using monads to represent infinitary algebraic theories and needed to get a better grip on it. I could write out the details if you’d like, though.

    • CommentRowNumber36.
    • CommentAuthorAndrew Stacey
    • CommentTimeAug 10th 2010

    Sridhar, in that case I’d ask you to hold off for a moment! I’m learning a lot by working through it for myself. Of course, it would be useful to have your input in the general discussion (both here at at the discussion in the thread titled “infinitary Lawvere theories”).

    • CommentRowNumber37.
    • CommentAuthorFinnLawler
    • CommentTimeAug 12th 2010

    Have you tried looking at Linton’s paper An outline of functorial semantics, LNM 80 (TAC reprint)? It’s not an easy one to read, but it seems as though it might help.

1 to 37 of 37

  1.