37
$\begingroup$

Here is an interesting question raised by Alice Rhyl.

Let $C$ be a category with a terminal object $1$ and finite coproducts. How many different morphisms $f : 1 \to 1 + 1$ can there be?

There are always two obvious morphisms $f : 1 \to 1 + 1$, coming from the definition of coproduct. But if $C$ is the category with one object and one morphism, $1 + 1 = 1$ so these two obvious morphisms are equal and there's really just one.

Can there be three different morphisms $f : 1 \to 1 + 1$? I don't know.

There can be four. Take $C = \mathrm{Set}^2$; then the terminal object in $C$ is $(1,1)$ (where $1$ is your favorite one-element set), and there are four different morphisms $f: (1,1) \to (1,1) + (1,1)$.

Indeed, any power of two is possible; just take $C = \mathrm{Set}^n$.

What other numbers are possible? (I find finite cardinals more interesting here.)

So far $C$ has just been any category with a terminal object and finite coproducts. In a paper I'm writing with Christian Williams, I'm more interested in the case where $C$ is a cartesian closed category with finite coproducts. How many morphisms $f : 1 \to 1 + 1$ can there be in this case?

(All the examples I've given above are categories of this sort.)

$\endgroup$
1
  • 6
    $\begingroup$ If you restrict to extensive categories, then the set of morphism from $1$ to $1 \coprod 1$ form a boolean algebra. Conversely, if $B$ is a boolean algebra, then in the topos of sheaves over its stone space, the morphisms from $1$ to $1 \coprod 1$ corresponds exactly to elements of $B$. So if you only care about finite set you get exactly power of $2$ in this case. $\endgroup$ Apr 19, 2019 at 19:23

4 Answers 4

33
$\begingroup$

Let $V$ be any variety of idempotent operations, such as the varieties of idempotent groupoids (aka magmas), or idempotent semigroups, or semilattices, or lattices. Then $V$ is complete and cocomplete (if we include in $V$ an empty algebra); $1$ is just the $1$-element algebra, and morphisms $1\to A$ are in 1–1 correspondence with set-theoretical elements of $A$. The object $1$ is also the free algebra on $1$ generator, hence $1+1$ is the free algebra on $2$ generators. So, all in all, there are as many morphisms $1\to1+1$ as is the cardinality of the free $V$-algebra on two generators. For example:

  • If $V$ is the variety of semilattices, the number is $3$.

  • If $V$ is the variety of idempotent semigroups, the number is $6$.

  • If $V$ is the variety of idempotent groupoids, the number is $\aleph_0$. More generally, if $V$ is the variety of all algebras with $\kappa\ge\aleph_0$ idempotent binary operations, then the number is $\kappa$.

$\endgroup$
6
  • 12
    $\begingroup$ [just a little comment about terminology: looking on google I noticed that in universal algebra somebody attaches the term "groupoid" to a very nonstadard definition e.g. something that most people -following Bourbaki- would call "magma" -- the standard definition of "groupoid" being "category where all morphisms are invertible"] $\endgroup$
    – Qfwfq
    Apr 22, 2019 at 10:51
  • 2
    $\begingroup$ It’s the other way round. Calling algebras with a single binary operation groupoids is in fact the standard terminology in algebra, which is why I am following it. Bourbaki’s terminology is highly nonstandard in this area. $\endgroup$ Apr 22, 2019 at 11:52
  • 3
    $\begingroup$ Remains the question: which natural numbers can be realised as the cardinality of the free $V$-algebra on two generators? $\endgroup$ Apr 22, 2019 at 20:52
  • 1
    $\begingroup$ @AndréHenriques I can rewrite my answer into a variety of algebras, see the recent edit to it. $\endgroup$ Apr 23, 2019 at 12:42
  • 1
    $\begingroup$ @DavidESpeyer Very nice, thank you. (Your algebras are even idempotent.) $\endgroup$ Apr 23, 2019 at 12:53
27
$\begingroup$

I just realized that my comment actually answer completely the case of a Cartesian closed category with finite coproducts, and not just extensive categories. So I'm posting it as an answer.

The short version is that the sets you can get out of a Cartesian closed category as $\mathrm{Hom}(1,1 \amalg 1)$ are exactly the Boolean algebras, so the only finite cardinals you get are the $2^n$ and all infinite cardinals can be obtained.

Here is the longer version, with way too much detail:

Let $C$ be a Cartesian closed category with finite coproducts. As products are left adjoint, they commute to colimits, in particular coproducts, so that one has canonical isomorphisms:

$$ \left( A \times X \right) \amalg \left( B \times X \right) \overset{\sim}{\rightarrow} \left( A \amalg B \right) \times X $$

In particular:

$$ (1 \amalg 1) \times (1 \amalg 1) \simeq 1 \amalg 1 \amalg 1 \amalg 1 .$$

This allows to define all the "logical operations" $\vee$, $\wedge$, $\Rightarrow , \dots $ : $(1\amalg 1)^2 \rightarrow (1 \amalg 1)$, simply using the universal property of the coproduct above (one just have to specify the values of these functions on the four summands, which basically means giving their truth table) and using that more generally:

$$ (1 \amalg 1)^n= \coprod_{2^n} 1 $$

one can check that they satisfy all the expected relations (precisely, all the relations that can be checked on finite truth tables). This exactly makes $(1 \amalg 1)$ into a Boolean algebra object in $C$.

In particular:

Proposition : In a Cartesian closed category C, for any object $X$, the set $\mathrm{Hom}(X, 1 \amalg 1)$ has the structure of a Boolean algebra. In particular $\mathrm{Hom}(1, 1 \amalg 1)$ is a Boolean algebra.

Now conversely, if I start with any Boolean algebra $B$, I can consider its Stone space $X$, which is a topological space, such that, among other things the Boolean algebra of clopen subsets of $X$ identifies with $B$.

In a topos of sheaf $\mathrm{Sh}(X)$, $1 \amalg 1$ is the sheaf of locally constant functions with values in $\{0,1\}$, i.e. of clopen subsets: sections of $1 \amalg 1$ over an open subset $U$ are exactly clopen subsets of $U$. So in particular in $\mathrm{Sh}(X)$,

$$ \mathrm{Hom}(1, 1 \amalg 1) \simeq B .$$ Hence:

Proposition : Any Boolean algebra $B$ appears as $\mathrm{Hom}_C(1 , 1 \amalg 1)$ for $C$ a Cartesian closed category, in fact for the Grothendieck topos $C =\mathrm{Sh}(\mathrm{Stone}(B))$.

So in the end the sets you can get from this construction are exactly the Boolean algebra. All finite Boolean algebras are atomic, so of the form $\mathcal{P}(\{1,\dots,n \})$. In this case the Stone space is $\{1,\dots,n \} $ with the discrete topology and this is the example mentioned in the question. But because of the Lowenheim-Skolem theorem, there are Boolean algebras of any infinite cardinality.

$\endgroup$
5
  • 2
    $\begingroup$ The free Boolean algebra on any infinite set $X$ has cardinal $|X|$, so the existence of Boolean algebras of any infinite cardinality is trivial (and in only ZF+DC it shows that any infinite set carries a Boolean algebra structure). $\endgroup$
    – YCor
    Apr 22, 2019 at 11:49
  • 2
    $\begingroup$ @YCor: Whats the ZF+DC version you have in mind? I don’t see how to show this without the assumption that $X \cong X^{<\omega}$, which as far as I recall doesn’t follow from DC for arbitrary infinite X? (Relatedly, an even more direct way to show this, assuming that cardinality property and otherwise using just ZF: the set of all finite-or-cofinite sunsets of $X$ forms a BA of cardinality X.) $\endgroup$ Apr 22, 2019 at 15:27
  • 2
    $\begingroup$ @PeterLeFanuLumsdaine Indeed. Already the statement that $X^2$ injects in $X$ for all infinite sets $X$ is equivalent to the full axiom of choice. $\endgroup$ Apr 22, 2019 at 15:42
  • 2
    $\begingroup$ As a matter of fact, since every Boolean algebra is also an abelian group, the statement that there are Boolean algebras of all infinite cardinalities is itself equivalent to the axiom of choice by mathoverflow.net/a/12988 . $\endgroup$ Apr 22, 2019 at 15:47
  • 2
    $\begingroup$ @PeterLeFanuLumsdaine thanks, indeed I was too optimistic. It's cool that writing a mistaken parenthesis in a comment generates so useful feedback. $\endgroup$
    – YCor
    Apr 22, 2019 at 20:22
13
$\begingroup$

This is effectively a longish comment on Simon Henry's answer. Note that his argument doesn't require the full strength of cartesian closure, only distributivity (of products over coproducts). So what it actually shows is that the object $2 = 1 + 1$ is a Boolean algebra object in any distributive category. A fun non-cartesian example of such a category is the category $\text{Aff}$ of affine schemes, where $2 = \text{Spec } \mathbb{Z}[e]/(e^2 - e)$ is the spectrum of the free idempotent.

This means that any distributive category $C$ is equipped with a natural contravariant functor $\text{Hom}(-, 2)$ taking values in Boolean algebras, and hence, by Stone duality, a natural covariant functor taking values in profinite sets. One might call this functor "etale $\pi_0$"; it gives $C$ a notion of connected components, and when specialized to $\text{Aff}$ gives the Pierce spectrum. I wrote a blog post about all this here.

$\endgroup$
13
$\begingroup$

If all we want is a category with a terminal object and finite coproducts, the following works to show that any $n$ can occur. Let $R$ be a commutative ring of cardinality $n$ (for $n$ finite, it could be $\mathbb{Z}/(n \mathbb{Z})$). Let our category consist of pairs $(M, \mu)$ where $M$ is an $R$-module and $\mu$ is an $R$-module map $M \to R$, and where $\mathrm{Hom}((M,\mu),\ (N, \nu))$ is the set of $R$-module maps $\phi: M \to N$ such that $\phi \circ \nu = \mu$. Then $(R, \mathrm{Id})$ is the terminal object, and the coproduct of $(M, \mu)$ and $(N, \nu)$ is $(M \oplus N,\ \mu + \nu)$.

So $1+1$ is $(R^{\oplus 2},\ [1\ 1])$ and $\mathrm{Hom}(1, 1+1)$ is $\left\{ \left[ \begin{smallmatrix} x \\ y \end{smallmatrix} \right] : x+y=1 \right\}$. There are $n$ solutions to $x+y=1$ in the ring $R$.

Furthermore, this category has all small limits and co-limits. Namely, let $D$ be a directed graph with vertex set $D_0$ and edge set $D_1$, and suppose we have elements $(M_v, \mu_v)$ for $v \in D_0$ and maps $\phi_e$ for edges $e \in D_1$. I claim that the co-limit is $(M, \mu)$ where $M$ is the colimit of the diagram of $M_v$ in the category of $R$-modules and the map $\mu: M \to R$ comes from the universal property of co-limits and the maps $\mu_v$.

To compute the limit, build a new diagram in the category of $R$-modules by adding one more vertex $\infty$ to $D_0$, one edge from every other vertex to $\infty$, with $M_{\infty} = R$ and the map $M_v \to M_{\infty}$ given by $\mu_v$ for each $v$. Then I claim that the limit of our original diagram in our funny category is $(M, \mu)$ where $M$ is the limit of the new diagram in the category of $R$-modules and $\mu$ is the projection $M \to M_{\infty}=R$.


There is a very similar category which is a variety of algebras, thus fitting into Emil's answer. Let $R$ be a commutative ring of cardinality $n$. Define an $R$-affine space to be a set $A$ which, for every $k$-tuple $(r_1, \ldots, r_k)$ of elements of $R$ obeying $\sum r_j=1$, has a $k$-ary operation $\phi_{r_1, \ldots, r_k} : A^k \to A$ obeying certain conditions. The idea is that $\phi_{r_1, \ldots, r_k}(a_1, \ldots, a_k) = \sum r_j a_j$. The conditions can be found at nlab, but you have to ignore all places where they assume $R$ is a field. Basically, the axioms say that $\phi$ is invariant under permuting the $r_j$ and $a_j$ by the same permutation; that, if $a_j = a_j$, then we can replace $r_j$ and $r_k$ by $r_j+r_k$; and that we can expand nested $\phi$'s in the obvious way.

The free $R$-affine space on one element is a single point, and the free $R$-affine space on $2$ points has cardinality $|R|$.

To see the relation between this part of the answer and the part above the line, note that this is the "unbiased definition" of an affine space at nlab (except that we allow the empty set) and the part above the line is the "slice of Vect" definition (except that we don't require the map to $R$ to be surjective).

Useless generalizations: $R$ doesn't have to be commutative, and could be a rig (ring without negation), in which case the free $R$-affine space on two elements has cardinality $\# \{ (x,y) \in R^2 : x+y=1 \}$.

$\endgroup$

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.