Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I had come across countless uses of the (Cartesian) product of sets long before I first ever met the concept of a "co-product"1 of sets. In fact, anyone who has learned basic analytic geometry in high-school is already acquainted with at least one good example of a Cartesian product of sets.

Does the concept of a co-product of sets have a useful life prior (or at least independent of) its role as obligatory example of elementary category theory?

I'm looking for examples accessible to "non-mathematicians" (by which I really mean non-math-majoring undergraduates) in which the concept of a co-product of sets proves natural and useful (in the same way that, say, the product of two coordinate axes provides a natural and useful way to think about points on a plane).


Epilogue

The answers I received were very thought-provoking; thank you all!

While thinking about MJD's and Martin Brandenburg's answers in particular my understanding of co-products of sets, and of their products for that matter, changed radically. Now I've come to regard the co-product as a more natural and ubiquitous construct than the product2. This is a complete reversal of how I saw them when I first posted my question. I'd like put out these thoughts here, for whatever utility they may have for others, and whatever constructive criticism I may get.

Since what follows is a bit long, here's the punchline:

In $\def\Set{\mathbf{Set}}\Set$,
  • co-products are partitioned domains;
  • products are parametrized codomains.

OK, here it goes. After mulling over your answers, my thought now is that the standard description of the co-product in the $\Set$ category as "the disjoint union" makes it appear a lot more exotic than it is in reality. Basically, the co-product arises whenever a domain is partitioned into subdomains: the partitioned domain is the co-product of these subdomains. (The inclusion of the subdomains into the domain are, of course, the co-product's canonical inclusions.)

This situation arises all the time. Anyone who has been exposed to highschool math is familiar with piecewise definitions of functions, such as, for example, the standard definition of the absolute value function $|\cdot|:\mathbb{R}\to\mathbb{R}_{\ge 0}$,

$$ \left|x\right| = \left\{ \begin{array}{lr} x, & \mathrm{if}\; x \ge 0\\ -x, & \mathrm{if}\; x < 0 \end{array} \right. $$

Such piecewise definitions amount to expressing the domain of a $\Set$ morphism (i.e. the function being defined) as the co-product of the domains of the "pieces" that the definition "stitches together." In the example above, these stitched-together pieces are the $\Set$ morphisms $f_0:\mathbb{R}_{\ge 0}\to\mathbb{R}_{\ge 0}$ and $f_1:\mathbb{R}_{< 0}\to\mathbb{R}_{\ge 0}$ defined by $$ \begin{array}{lr} f_0(x) = & x\\ f_1(x) = & -x \end{array} $$

But such maneuvers are not limited to Mathematics. Every procedure whose first stage is a "channeling" of the input into one of several mutually exclusive cases (e.g. "whites" and "colors"), and associates a different sub-procedure with each case (e.g. "wash in hot water" and "wash in lukewarm water"), to finally produce an output of "a uniform kind" (e.g., "washed laundry"), is one that fits the description of the co-product in $\Set$.

I think that what makes it so easy to miss the ubiquity of the co-product in $\Set$ is that expressions such as

$$X = \bigsqcup X_\alpha$$

tend to be interpreted as describing a synthetic operation, namely, one that starts with some arbitrary sets $X_\alpha$, and combines them into "their disjoint union". My point is that in practice such a maneuver is rare in comparison to the one that goes in the "opposite direction", namely, the analytic operation that starts with some set $X$, and partitions it into subsets $X_\alpha$.

The unfortunate irony here is that it is precisely the needs of the in-practice-rare synthetic operation that necessitates introducing an exotic "disjoint union" operation (and even more exotic constructions of it, via "tagged sets" and the like), since arbitrary sets $\{X_\alpha\}$ cannot be assumed to be pairwise-disjoint.

In contrast, the analytic operation, which is readily recognizable by anyone who has ever sorted out a bunch of items into separate classes, is one that does not require introducing any new set operation. (At most, it requires to formally define a partition of a set $X$ as a cover of $X$ consisting of pairwise-disjoint subsets of $X$.)

In light of the above, I've come to realize that the term "disjoint union" could also be interpreted simply as shorthand for "a union of disjoint (and covering) subsets", instead of an exotic new set operation. (There's precedent in Mathematics for transposing the adjective from the parts to the whole; for example an "open cover" is defined as a "cover by open sets".)

Thinking of the co-product in $\Set$ as an manipulation on a domain also sharpened my appreciation of the product in $\Set$ as a manipulation on a codomain: whereas the co-product partitions a domain into subdomains, the product parametrizes a codomain by component sets. With the co-product, several functions that have disjoint domains and the same codomain are stitched together. With the product, several functions that have the same domain, and "independent" codomains are bound together into a single composite function.

As MJD's answer alluded to, in programming the co-product manifests itself as "switch" statements, or, more generally, as sequences of if , else if ... else if , else expressions:

function f(x):
    if test_1(x):
        return f_1(x)
    else if test_2(x):
        return f_2(x)
    ...
    else:
        return f_n(x)
    end
end

Here, the domain $X$ of f is effectively partitioned into disjoint subsets $X_1, X_2, \dots, X_n$, where $X_i$ consists of all those elements of $X$ for which test_i is true, and test_j is false for every $j < i$. The function f "stitches together" the functions f_1, ..., f_n, having (effective) domains $X_1, \dots, X_n$, respectively. This function f is the "unique morphism" in $\Set$, for the given f_1, ..., f_n, that is guaranteed by the definition of the co-product.3

In contrast, the product manifests itself in programming most commonly whenever real-world entities are modeled as composites of a finite number of parameters in such a way that (1) any two model objects are considered identical if and only if their parameter values parameters all match, (2) any combination of allowable values for the parameters represents a valid model object4. The simplest example of this would be modeling space as a collection of three parameters, x, y, and z. Then, for example:

function pos(t):
    return (pos_x(t), pos_y(t), pos_z(t))

The function pos "bundles together", the functions pos_x, pos_y, and pos_z. It is the "unique morphism" in $\Set$, for the given pos_x, pos_y, and pos_z, that is guaranteed by the definition of the product.

Note that the function f given earlier is a function from the co-product (IOW the co-product serves as the domain), whereas the function pos given here is a function to the product (IOW, the product serves as the codomain). This is characteristic.

In short, the take-home message is: co-products are partitioned domains, products are parametrized codomains. Or better yet (as explained in footnote 2),

sums are partitioned domains, cosums are parametrized codomains.


1 In the case of co-product I deliberately avoid the common practice of omitting the hyphen, as in cotangent, cohomology, cokernel, etc. In natural language, juxtaposition is not associative (that's why, e.g., the components of the word unionized are parsed out differently by a chemist and a labor activist), and the non-standard, but plausibly intelligible, parsing "copro-duct" (literally: "excrement conduit") gives the unhyphenated version of the word a ... let's say, suspicious aura.

2 In fact, I now think that it's a bit unfortunate that learners of category theory are usually told about the co-product, and often summarily, only after being taught the product. At least in $\Set$, it would be more natural to being with the co-product (or rather, with partitions, expressed as "sums" of disjoint subsets), and then introduce the product, or rather, the cosum! Then the slogan given elsewhere could be restated a bit more memorably as: sums are partitioned domains, cosums are parametrized codomains.

3 Pedantic caveat: in order to interpret f as the morphism guaranteed by the definition of the co-product, the f_i must be construed as the restrictions of the implemented functions to their effective domains $X_i$. In practice, the domains of the implemented functions f_i will often be proper supersets of their effective domains $X_i$. Still, considering only its role in the implementation of f, the domain of each f_i is indeed $X_i$.

4 Note that these two conditions correspond, respectively, to the existence and uniqueness conditions on the morphism that is guaranteed by the definition of a product. Dually, the conditions on the subsets of a partition, namely (1) that they be pairwise-disjoint, and (2) that they cover the original set, correspond, respectively, to the existence and uniqueness conditions on the morphism that is guaranteed by the definition of a co-product.

share|improve this question
4  
+1 for the copro-duct joke. –  Malice Vidrine Mar 3 at 13:02
5  
The co-product of sets is just the disjoint union, so whenever you add the number of elements in two sets, you count the number of elements in the co-product. –  Tobias Kildetoft Mar 3 at 13:04
    
Are you able to find a fancy etymology for "col-imit" too? –  alex Mar 3 at 13:04

3 Answers 3

up vote 5 down vote accepted

Consider a computer system which has a data type of integers, called $\def\Int{\mathtt{Int}}\Int$, and a data type of errors, called $\def\Err{\mathtt{Err}}\Err$. Now consider a function, which might run successfully and return an $\Int$, or unsuccessfully and return an $\Err$. Such a function returns values from the coproduct type $\Int + \Err$. Typically, this will be implemented as a storage cell that is big enough to hold either an $\Int$ or an $\Err$, plus a tag that identifies which of the two types is actually stored.

How are values of $\def\IE{\Int + \Err}\IE$ constructed? There must be two constructors: one to turn values of type $\Int$ into values of type $\Int+\Err$, and one to turn values of type $\Err$ into values of type $\Int + \Err$. The former, which we might call $\def\L{\mathtt{Left}}\L$, is a function of type $\Int\to\IE$, which takes the $\Int$ it is given, allocates a new $\IE$, stores the $\Int$ into the storage cell, and sets the tag to indicate that an $\Int$ was stored. There is a corresponding function $\def\R{\mathtt{Right}}\R$ of type $\Err\to\IE$ that does the same for an $\Err$ value. These functions are exactly the canonical injections $\iota_\Int$ and $\iota_\Err$ of the coproduct.

To be useful we need some way of examining the value stored in an $\IE$ and extracting the underlying $\Int$ or $\Err$ value from it. Typically the way this is done is with a construction that takes an $\IE$ value $v$, a function $f:\Int\to C$, and a function $g:\Err\to C$; it extracts the stored value from the $\IE$ and passes it to either $f$ or $g$ as appropriate; the result either way is a value of type $C$. This construction might appear in the programming language as something like this:

$$\begin{array}{rl} \mathtt{case}_{f,g} & v\quad \mathtt{ of}& \Int\ x\mathtt{:}& f(x) \\ & & \Err\ y\mathtt{:}& g(y) \end{array}$$

This $\mathtt{case}_{f,g}(v)$ construction is exactly the universal arrow that is guaranteed to exist by the universal property of coproducts.

universal diagram for coproduct

The universal property for coproducts says that for any object $C$ and any arrows $f:\Int\to C$ and $g:\Err\to C$, there is a unique arrow $\mathtt{case}_{f,g}(v)$ with the property that $$\begin{align}\mathtt{case}_{f,g}(\L\ x) &= f(x) \\ \mathtt{case}_{f,g}(\R\ y) &= g(y)\end{align}$$

share|improve this answer

$\mathrm{Humans} = \mathrm{Men} \sqcup \mathrm{Women}$

$\mathrm{Integers} = \mathrm{odd} \sqcup \mathrm{even}$

Do you really seriously ask if there is any use of the disjoint union of sets? It arises everywhere.

share|improve this answer
2  
@MaliceVidrine Excuse me, did you mean a co-product? –  Christoph Mar 3 at 13:10
3  
@Christoph: I leave it as an exercise for the reader to show how any set may be expressed as a length of sewer conduit. –  Malice Vidrine Mar 3 at 13:25
4  
This answer is not really correct. A coproduct isn't simply a disjoint union of sets; it is a tagged disjoint union. The coproduct of men and women isn't simply "humans", as you would have it; it's something more like $\{(m,1)\mid m\in\text{Men}\} \cup \{(w,2)\mid w\in\text{Women}\}$. Otherwise it is not clear that the required universal arrow exists. –  MJD Mar 3 at 15:12
1  
@MJD: The answer is correct. Recall the definition of a coproduct. If $X,Y$ are already disjoint, then $X \cup Y$ is a coproduct of $X$ and $Y$. There is not only one construction of the coproduct. –  Martin Brandenburg Mar 3 at 15:22
3  
In all seriousness, I think our disagreement is over the semantics of men and women. I have no objection to your evens/odds example because there it is clear that the sets are disjoint and that the universal arrow is well-defined. I imagine that you think the same about the men/women example, but there it seems to me that the universal arrow is not clear. –  MJD Mar 3 at 15:29

As you said, you think of $\mathbb R$ as a line and $\mathbb R\times\mathbb R$ as a plane. Well, we think of $\mathbb R \sqcup \mathbb R$ as two disjoint lines. Of course already thinking of $\mathbb R$ as a line implies a topology on $\mathbb R$ at least, as well as thinking of $\mathbb R\times\mathbb R$ as a plane implies a topology, after all $\mathbb R\cong_{\text{Set}} \mathbb R\times \mathbb R$ in the category of sets. So for the disjoint union, thinking of $\mathbb R\sqcup\mathbb R$ as two disjoint lines really is the co-product in the category of topological spaces. We also have $\mathbb R\cong_{\text{Set}}\mathbb R\sqcup\mathbb R$ in the category of sets.

share|improve this answer
    
We don't need a topology ... –  Martin Brandenburg Mar 3 at 13:53
    
I didn't say we need one, I said thinking of $\mathbb R$ as a line implies more structure than just a set of elements. –  Christoph Mar 3 at 13:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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