How many morphisms from 1 to 1+1 can there be?

Question

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.)

Answer 1

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$.

Answer 2

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.

Answer 3

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.

Answer 4

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 \}$.