1
$\begingroup$

Free functors are left adjoint to forgetful one. If given two free functors F:Set->A,G:Set->B constructing objects of type A & B respectively, is there a canonical free functor F*G that constructs objects that are both of type A & B?

This is probably too simple minded, but since Cat is bicomplete, I considered the pushforward of the functors F,G over Set, and the pullback of the corresponding forgetful functors over Set. Since A X_Set B is not neccessarily isomorphic to A +_Set B, this cannot work...

$\endgroup$

1 Answer 1

10
$\begingroup$

Under the most immediate reading of "both of type A and B", where no sort of compatibility or relationship between the A and B structures is assumed, the answer is no.

A counterexample is where A is the theory of sup-lattices and B is the theory of sets equipped with an unary operator (often called "successor"). If free algebras of the combined theory existed, then in particular there would exist the initial such algebra = free algebra on 0 generators. This can be seen as an algebraic form of the cumulative hierarchy, where such a structure is provably isomorphic to the set of all its small subsets, in contradiction to Cantor's theorem. In other words, there is no such small structure.

In fact, these observations are the beginning of Algebraic Set Theory. See the text by Joyal and Moerdijk (London Math. Soc. LNS 220), or for a very accessible introduction, try these notes by Steve Awodey, where the inexistence is proved on page 2.

Edit: But it seems that I should at least add that if theories A and B have rank (are given by small sets of operation symbols and equational axioms), then the combined theory will also have rank and hence will admit free algebras. In the finitary case, Lawvere indicated in his 1963 thesis that the category of what are now called Lawvere theories admits coproducts, and infinitary Lawvere theories with rank also admit coproducts, which represent the combined theory. It would take a little while however to describe the construction of coproducts here. If you are interested I could say more.

Edit 2: On request, here is a sketch of how to take the coproduct of finitary monads on $Set$. The same construction can be adapted to accessible monads on $Set$.

Let $A$ be a finitary algebraic signature, i.e., a set $F$ (whose elements are called function symbols) together with an arity function $f: F \to \mathbb{N}$. For each finitary monad $M$ there is an underlying signature $S(M) \to \mathbb{N}$ where the fiber $S(M)_n$ is the set $M([n])$, thought of as the $n$-ary operations of the associated Lawvere theory. This gives an underlying functor

$$U: FinMon(Set) \to Set/\mathbb{N}$$

that is monadic; the free monad $F(A)$ on a signature $A$ has for its operations terms generated by $A$.

Next, $FinMon(Set)$ has coequalizers. I actually do find it easier to think about this in terms of Lawvere theories. Given a pair $f, g: S \to T$ of maps between Lawvere theories, form the smallest equivalence relation on morphisms of $T \times T$ which contains pairs $(f(\theta), g(\theta))$ and which is closed under finite products and compositions (i.e., term substitutions) in $T$. Then the coequalizer Lawvere theory of the pair is given by the quotient category of $T$ modulo the equivalence relation.

Then, $FinMon(Set)$ has arbitrary coproducts by mimicking the proof of the proposition given here.

$\endgroup$
2
  • $\begingroup$ Thanks for the counterexample. Yes, I would be interested in learning more. Nlab states that a Lawvere theory is equivalent to a finatary monad, is the construction of the coproduct more natural in a Lawvere theory than a monad? $\endgroup$
    – Shamim
    Dec 16, 2010 at 10:32
  • $\begingroup$ Thanks again, this is what I was looking for but didn't have the mathematical language to pose the question correctly. $\endgroup$
    – Shamim
    Dec 22, 2010 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.