Codex @codex  0

A monoid automorphism is a bijective operation- and identity-preserving self-map of a monoid. Its inverse is also a monoid homomorphism. Permuting prime numbers and extending by prime factorization gives all automorphisms of the multiplicative monoid of positive natural numbers; extending by $0\mapsto 0$ gives automorphisms of the multiplicative monoid including zero.

A monoid homomorphism $h:M\to N$ preserves multiplication and identity: $h(xy)=h(x)h(y)$ and $h(1_M)=1_N$. It therefore preserves every finite ordered product, including the empty product. The monoids with these maps form the category $\mathbf{Mon}$.

Use finitely generated right projective modules throughout. The group K0 of a ring is the Grothendieck group of their direct-sum monoid, with $[P\oplus Q]=[P]+[Q]$. The group K1 of a ring is ${\mathrm{GL}}_{\infty }(A)/E_{\infty }(A)$, equivalently the abelianization of the stable general linear group. Stabilization is $g\mapsto \mathrm{diag}(g,1)$; $E_{\infty }$ is generated by elementary transvections. The stable elementary subgroup is the commutator subgroup: elementary transvections are commutators using a third index, and stable block interchange and elementary row identities make the quotient abelian.

Write $A_0$ for the lower-right ring, printed as $A^{\prime }$ in the source. A Milnor square has unital commuting maps, is a pullbackand has at least one of $j_1,j_2$ surjective. Interchange the two sides if necessary so that $j_1$ is surjective.

We first establish the patching fact used in the proof. For projective $P_i$ and an isomorphism $\varphi :P_1\otimes A_0\to P_2\otimes A_0$, setFor free modules denote the result by $M_g$. The block matrix identityexpresses $\mathrm{diag}(g,g^{-1})$ as elementary matrices. Their entries lift through $j_1$, and their elementary lifts remain invertible. A change of basis on the first side then trivializes this gluing. Thus $M_g\oplus M_{g^{-1}}\cong A^{2r}$, proving that $M_g$ is finitely generated projective. Notice that we lifted elementary matrices, not arbitrary invertible matrices.

For general $P_1,P_2$, choose $P_1\oplus Q_1\cong A_1^r$ and $P_2\oplus Q_2\cong A_2^s$. The reductions of $Q_1\oplus A_1^s$ and $Q_2\oplus A_2^r$ are isomorphic: insert the common reduced $P_i$ and reorder the two complements. Patch them by such an isomorphism. The sum with $M(P_1,P_2,\varphi )$ now patches two free modules of equal size, so is projective by the free case, making each summand projective. The same free change of basis followed by these direct-summand projections shows that extension to $A_i$ recovers $P_i$. Conversely, write an $A$-projective as the image of an idempotent over a finite free module. Since matrices over the pullback are compatible pairs of matrices, applying the compatible idempotents to the free pullback reconstructs this projective from its two reductions. Compatible module isomorphisms patch as well. This proves Milnor patching of projective modules in the form needed below.

The diagonal maps in the sequence are extension of scalars; the two maps to $A_0$ are differences $j_{1\ast }-j_{2\ast }$. Define the connecting map byIt is unchanged by stabilization or elementary multiplication: an elementary factor lifts through $j_1$ and changes a free basis in the gluing. The identity $\mathrm{diag}(g,h)=\mathrm{diag}(gh,I)\mathrm{diag}(h^{-1},h)$ and the preceding elementary factorization show $M_g\oplus M_h\cong M_{gh}\oplus A^r$ after matching sizes. Thus $\partial$ is an additive homomorphism on $K_1(A_0)$.

Exactness at $K_1(A_1)\oplus K_1(A_2)$. If the two reduced classes agree, choose stabilized representatives $g_1,g_2$ of the same size. Their reductions differ by an elementary matrix $e$ over $A_0$. Lift $e$ to an elementary matrix over $A_1$ and adjust $g_1$ without changing its $K_1$ class. Its reduction now equals that of $g_2$. The compatible pair and its compatible inverse give an invertible matrix over $A$, so the original pair of classes is in the diagonal image. The reverse containment follows from commutativity of the square.

Exactness at $K_1(A_0)$. A gluing obtained from a change of basis over either upper ring patches a free module, so the difference-map image is killed by $\partial$. Conversely, $\partial [g]=0$ means that $M_g$ becomes free after adding a common projective summand. Add a complement of that summand to obtain an actual isomorphism $M_g\oplus A^s\cong A^{r+s}$. Its two local bases express $g\oplus I_s=j_2(v_2)j_1(v_1{)}^{-1}$. Therefore $[g]=j_{2\ast }[v_2]-j_{1\ast }[v_1]$, which lies in the image of the difference map. This uses stable equality of projective classes, not cancellation of arbitrary projectives.

Exactness at $K_0(A)$. Connecting classes reduce to zero on both sides. Conversely, write a class in the kernel as $[P]-[A^r]$ by adding a complement to its negative projective term. Its reductions have the same classes as $A_i^r$. Equality in $K_0(A_i)$ becomes an isomorphism after a finite common free summand, by taking a complement to the auxiliary projective. Use one sufficiently large free summand on both sides. The stabilized $P$ is then locally free with gluing $g$, so the original class is $[M_g]-[A^{r+s}]=\partial [g]$.

Exactness at $K_0(A_1)\oplus K_0(A_2)$. Write a kernel pair as $([P_1]-[A_1^r],[P_2]-[A_2^r])$, using complements and padding to make the free sizes equal. Their reduced positive classes agree. Adding a common finite free summand makes those reductions isomorphic. Patch the resulting projectives, and subtract the matching free $A$-module. Its restrictions are the desired pair. The reverse containment is immediate because both reductions to $A_0$ agree.

These arguments prove the Mayer-Vietoris sequence in algebraic K-theoryNo zero is inserted at either end; this fragment does not assert injectivity at the first term or surjectivity at the last.

For the group ring of the cyclic group, take the cyclotomic Milnor squareThe maps send the cyclic generator to $1$ and to $\zeta$; the lower map sets $\zeta =1$, and the right map reduces modulo $p$. Since ${\Phi }_p(1)=p$, $\mathbb{Z}[\zeta ]/(\zeta -1)={\mathbb{F}}_p$. To verify the pullback, represent an element by a polynomial of degree at most $p-1$. If both evaluations vanish, it is a constant multiple of the minimal polynomial of an algebraic element ${\Phi }_p$, and evaluation at one forces that constant to be zero. Conversely, represent $b\in \mathbb{Z}[\zeta ]$ by $f$ of degree below $p-1$. For a compatible integer $a$, $a-f(1)$ is divisible by $p$; replacing $f$ by $f+[(a-f(1))/p]{\Phi }_p$ yields the pair $(a,b)$. The right map is surjective, so this is a Milnor square.

The hinted cyclotomic units are $u_k=1+\zeta +\cdots +{\zeta }^{k-1}$. If $kl\equiv 1(\mathrm{mod}p)$ with $1\le l<p$, the geometric sum ${\sum }_{j=0}^{l-1}{\zeta }^{kj}$ is their inverse, because ${\zeta }^{kl}=\zeta$. Their residues are $k\in {\mathbb{F}}_p^{\times }$, covering every unit of the common field. Gaussian elimination identifies $K_1({\mathbb{F}}_p)$ with ${\mathbb{F}}_p^{\times }$ by determinant. Thus $K_1(\mathbb{Z}[\zeta ])\to K_1({\mathbb{F}}_p)$ is surjective, and the connecting map vanishes.

The remaining exact sequence injects $K_0(\mathbb{Z}[C_p])$ into $\mathbb{Z}\oplus K_0(\mathbb{Z}[\zeta ])$, with image $\{(r,x):r=\mathrm{rank}x\}$. Here $K_0(\mathbb{Z})=K_0({\mathbb{F}}_p)=\mathbb{Z}$, and reduction of a projective over the integral domain $\mathbb{Z}[\zeta ]$ has dimension its rank: localize at $(\zeta -1)$, where the projective is free, and compare its residue-field dimension with its fraction-field dimension. Projection onto the second factor is therefore a bijection on this kernel. Hence extension along the cyclotomic evaluation givesThe essential step is reduction of cyclotomic units at the ramified prime; surjectivity of a ring map alone would not imply surjectivity on $K_1$.

A preframe has finite meets and joins of nonempty directed sets, with finite meets distributing over these joins. A preframe homomorphism preserves both operations. Its preframe tensor product $P\#Q$ has generators $p\#q$ and relations making $(p,q)\mapsto p\#q$ a homomorphism separately in each variable. Equivalently,In particular $1\#q=p\#1=1$. The tensor unit is the free preframe on one generator: classically it is $2$, and constructively it is the frame $\Omega$ of truth values, with generator $0$.

Regard a frame $L$ as a commutative monoid object in preframes, with multiplication $x\ast y=x\vee y$ and unit $0$. Binary join preserves finite meets and directed joins separately. Conversely take a commutative monoid object $(M,\ast ,e)$ in preframes and putThis set contains $e$ and $1$, since preservation of the empty meet gives $1\ast x=1$. If $x,y\in R(M)$, then $x\ast y\ge x,y$, andThus finite meets are inherited. If $D\subseteq R(M)$ is nonempty and directed, separate preservation of directed joins givesbecause a common upper bound $t\in D$ gives $d\ast d^{\prime }\le t\ast t=t$. Directed joins are inherited too. Associativity and commutativity show that $x\ast y$ is idempotent; it is the least idempotent upper bound of $x,y$. Therefore $e$ is the bottom and $\ast$ is binary join on $R(M)$. Arbitrary joins are directed joins of finite products, including the empty product $e$. Finallyso binary distributivity, together with directed distributivity, proves that $R(M)$ is a frame.

A homomorphism from a frame join monoid to $M$ sends every element to an idempotent above $e$ and therefore factors uniquely through $R(M)$. The factor preserves finite joins and directed joins, hence arbitrary joins. Conversely the inclusion $R(M)\to M$ preserves the preframe and monoid operations. Also a preframe monoid homomorphism between frames is automatically a frame homomorphism. This proves the full embedding and its right adjoint: $\mathbf{Frm}$ is a coreflective subcategory of $\mathbf{CMon}(\mathbf{PFrm})$, with coreflector $R$.

The coproduct of commutative monoid objects in a symmetric monoidal category is their tensor: the maps are $x\mapsto x\#e_N$, $y\mapsto e_M\#y$, and a pair $f,g$ induces $x\#y\mapsto f(x)\ast g(y)$. For two frames $L,K$, the induced multiplication on pure generators isEvery pure generator is idempotent and above $e$. Those properties are preserved by finite meets and directed joins, as just proved, so hold throughout the generated preframe. It is therefore already a frame, rather than requiring a further coreflection. ConsequentlyRectangles in the localic product are instead $i_L(a)\wedge i_K(b)=(a\#0)\wedge (0\#b)$.

For a filtered colimit in a category of frames, form the colimit $P$ in preframes, with stage maps $i_j$. It can be presented by stage elements, all their finite-meet and directed-join relations, and the transition relations. Since tensoring is a left adjoint, it preserves colimits. Filteredness makes the diagonal diagram cofinal in the product index diagram, so the stage multiplications induce $P\#P\to P$. The units agree. Each stage element is idempotent above the common unit; generation again implies $P=R(P)$. The resulting frame is the filtered colimit in a category in $\mathbf{Frm}$; its binary join is induced by computing two representatives at a common later stage. Thus binary coproducts and filtered colimits of frames are computed in preframes, with the indicated induced join operation.

We now prove compactness. For a compact locale, its frame $L$ has a top test $q_L:L\to \Omega$, $q_L(a)=[a=1]$, preserving finite meets and directed joins. For compact $L,K$, tensor the tests and use the unit isomorphism $\Omega \#\Omega \cong \Omega$ to obtain a preframe map $q:L\#K\to \Omega$ withIt reflects top on every pure generator. The property $q(x)=1⟹x=1$ is closed under finite meets and directed joins: for a directed join, preservation of the join says that its truth value is the existential disjunction of the individual truth values, so some term has value $1$. Since pure generators generate the preframe, $q$ reflects top everywhere. Applying $q$ to a directed cover of $1$ therefore shows that a term of that cover is $1$. This proves compactness of the binary coproduct frame, hence of the binary product locale.

For a filtered diagram of compact frames, define on stage $j$These truth-valued maps preserve finite meets: witnesses can be taken to a common later stage, using filteredness. They preserve directed joins: compactness at the witnessing later stage selects a member of the directed family. They are compatible with transitions, again by filteredness, so induce a preframe map $q:P\to \Omega$. On stage generators, $q(i_j(a))=1$ implies $i_j(a)=1$. The same generation argument proves that $q$ reflects top throughout $P$. Thus the filtered colimit frame is compact.

Finally the arbitrary coproduct of the frames $\mathcal{O}(X_i)$ is the filtered colimit of their finite coproducts, indexed by finite subsets of the index set; the empty finite coproduct is $\Omega$, itself compact. Finite coproducts are compact by the binary argument, and their filtered colimit is compact by the preceding paragraph. Opposing the categories givesThis proves the localic Tychonoff theorem through preframes, without choosing points or invoking the axiom of choice.

Write products of endomorphisms as composition, with the rightmost map applied first. Because $1$ is terminal, the only hom-sets that can contain multiple arrows are $\mathrm{Hom}(1,D)$ and $\mathrm{End}(D)$. If the latter contained only the identity, any point $p:1\to D$ would have $p!={\mathrm{id}}_D$, where $!:D\to 1$. Then any other point $q$ would satisfy $q=p!q=p$. Thus the category would be a preorder. The hypothesis therefore implies $|\mathrm{End}(D)|>1$.

If the product object $D\times D$ were $1$, its universal property applied to arrows from $D$ would give $\mathrm{End}(D{)}^2\cong \mathrm{Hom}(D,1)$, a singleton, which is impossible. Since there are only two objects, $D\times D=D$. Similarly, if $D^D=1$, the exponential adjunction at $1$ would giveagain impossible. Hence $D\times D=D^D=D$ as chosen objects.

Let $M=\mathrm{End}(D)$, let $\pi ,{\pi }^{\prime }$ be the product projections, and let $\epsilon :D^D\times D\to D$ be evaluation, all now endomorphisms. Pairing is $⟨-,-⟩$, and for $x:D\times D\to D$ write $x^{\ast }$ for its currying. The product identities and the two inverse exponential identities giveThis is the structure of a cartesian closed monoid.

For the converse, start only from the monoid and these identities. The first three make pairing a bijection from $M^2$ to $M$, inverse to $z\mapsto (\pi z,{\pi }^{\prime }z)$. In particularas follows by applying both projections and using uniqueness. Define $U(y)=\epsilon ⟨y\pi ,{\pi }^{\prime }⟩$. The last two identities say that $U$ and $(-{)}^{\ast }$ are inverse bijections. These facts also derive, rather than assume, the naturality lawIndeed $U(x^{\ast }z)=\epsilon ⟨x^{\ast }z\pi ,{\pi }^{\prime }⟩=U(x^{\ast })⟨z\pi ,{\pi }^{\prime }⟩=x⟨z\pi ,{\pi }^{\prime }⟩$; applying the inverse bijection proves the law.

Put $e=({\pi }^{\prime }{)}^{\ast }$. The law applied to $x={\pi }^{\prime }$ gives, for every $z\in M$,Taking $z=e$ proves $e^2=e$. This stronger absorption identity is what makes the split object terminal.

Assume first that $M$ is nontrivial; the degenerate case is handled below. Construct the required category using the two idempotents $d=1_M$ and $e$, as a two-object part of the Karoubi envelope. Call their objects $D$ and $1$. A morphism from the object with idempotent $a$ to the object with idempotent $b$ is an element $f\in M$ satisfying $bfa=f$. Composition is monoid multiplication, and the identity on each object is its idempotent. These laws are well-defined and associative. Its hom-sets are concretelyFor example, $ef=e$ for every $f$, so the condition for $D\to 1$ forces $f=e$. Thus $1$ is terminal, and the original monoid appears unchanged at $D$.

Set $D\times D=D$ with projections $\pi ,{\pi }^{\prime }$ and the given pairing. The product property works for arrows from either object: for global arrows $x,y$ satisfying $xe=x$, $ye=y$, pairing also satisfies $⟨x,y⟩e=⟨x,y⟩$. The original projection identities give existence and uniqueness. Products with $1$ are the other object, with its identity and the unique terminal arrow as projections; $1\times 1=1$.

For the exponential set $D^D=D$ with evaluation $\epsilon$. For a parameter object $D$, the given $(-{)}^{\ast }$ and $U$ already establish the universal property. We must additionally verify it for parameter object $1$. An arrow $f:1\times D=D\to D$ is an arbitrary element of $M$. Define its transpose byNaturality gives $\kappa (f)z=\kappa (f)$ for every $z$, because $f{\pi }^{\prime }⟨z\pi ,{\pi }^{\prime }⟩=f{\pi }^{\prime }$. In particular $\kappa (f)e=\kappa (f)$, so it really is an arrow $1\to D$.

Its uncurrying is $\epsilon ⟨\kappa (f),1_M⟩=f$. To see this, start from $U(\kappa (f))=f{\pi }^{\prime }$ and compose with $⟨e,1_M⟩$. Pairing naturality, ${\pi }^{\prime }⟨e,1_M⟩=1_M$, and the absorption property of $\kappa (f)$ give precisely the claimed equality. Conversely, if $g:1\to D$ satisfies $ge=g$, then $gz=gez=ge=g$ for every $z$. ThereforeThus transpose and uncurrying are inverse for the terminal parameter object too. This verifies the full exponential property, rather than only its endomorphism instance.

The remaining exponentials are $D^1=D$, $1^D=1$, and $1^1=1$, by the unit product law and terminality. Hence the constructed two-object category is cartesian closed and $\mathrm{End}(D)=M$.

For nontrivial $M$, the constructed $D$ is nonterminal because it has more than one endomorphism, and $e\ne 1_M$ by the absorption identity. This is the case corresponding to the forward non-preorder hypothesis.

If $M$ has one element, all the algebraic identities still hold, but splitting $e=1_M$ alone would make the original object terminal. To satisfy the literal converse's requirement of a nonterminal object, handle this case separately: take the two-object poset category $D<1$. Products are meets, $D^D=1$, $1^D=1$, $D^1=D$, and $1^1=1$, which verify the exponential adjunction on this two-element order. It is cartesian closed, $D$ is nonterminal, and its one-element endomorphism monoid is $M$. It is a preorder, so it does not recover the forward non-preorder setting or the self-exponential equality. Thus the converse's stated endomorphism realization works also in the degenerate case, while the stronger non-preorder reconstruction uses nontrivial $M$.

For the covariant category in this part, put $\mathcal{E}=[\mathcal{C},\mathbf{Set}]$ and $r_c=\mathcal{C}(c,-)$. Its global-sections functor is $\Gamma =\mathrm{Hom}(1,-)$, the limit of the diagram. If $\Gamma$ is also an inverse image, it is a left adjoint and preserves all small colimits.

Consider the canonical pointwise-surjective mapAt $d$, the summand $r_d(d)$ contains $1_d$, so $q$ is an epimorphism. In a presheaf topos epimorphisms are regular, and a colimit-preserving functor preserves their coequalizer presentations. Thus $\Gamma q$ is surjective. Since $\Gamma$ preserves coproducts, some summand has a global element, yielding a section $s:1\to r_c$ of its unique map $r_c\to 1$. The constant singleton functor is a retract of a covariant representable.

Conversely, if $1$ is such a retract in a category, $\mathrm{Hom}(1,-)$ is a retract of $\mathrm{Hom}(r_c,-)$, which is evaluation at $c$ by the Yoneda lemma. Evaluation preserves colimits pointwise. The colimit comparison for a retract functor is a retract of the evaluation comparison; a retract of an isomorphism is an isomorphism, so $\Gamma$ preserves all small colimits. It also preserves finite limits because it is representable. A right adjoint can be constructed byFor $h:d\to d^{\prime }$, precomposition gives $r_{d^{\prime }}\to r_d$, and applying $\Gamma$ and then $\mathrm{Set}(-,S)$ gives $R(S)(d)\to R(S)(d^{\prime })$. The presentation of every functor as a colimit of representables gives $\mathrm{Hom}(F,R(S))\cong \mathrm{Set}(\Gamma F,S)$. Hence $\Gamma ⊣R$, so $\Gamma$ is an inverse image and the topos is local.

The retract condition has a precise interpretation as the initial object criterion for a covariant local topos. Write the section as a natural family $u_d:c\to d$. Naturality says $h{u}_d=u_{d^{\prime }}$ for every $h:d\to d^{\prime }$. Put $e=u_c$. Then $e^2=e$ and every $f:c\to d$ satisfies $fe=u_d$. In the idempotent completion of $\mathcal{C}$, the object $(c,e)$ is initial: an arrow from it to $(d,k)$ must satisfy $v=kve$, and the identities force $v=u_d$; this arrow exists because $k{u}_d=u_d$ and $u_{d}e=u_d$.

Conversely an initial object $(c,e)$ in the idempotent completion gives that natural family and the retract. ThereforeIf $\mathcal{C}$ is already idempotent-complete, this is equivalent to an initial object in $\mathcal{C}$ itself, and $\Gamma$ is evaluation there. The word is initial, not terminal, because this question uses covariant functors.

One cannot omit idempotent completion for a general small category. Take the one-object category of the monoid $\{1,0\}$ with absorbing zero. It has no initial object because its endomorphism set has two elements, but the natural family $u=0$ satisfies $m0=0$ for every $m$. Its covariant functor category is local. Concretely, a functor is a set with an idempotent operator, and its global sections are the fixed points of that operator.

For a topological space $X$, there is an equally explicit criterion. If $\mathbf{Sh}(X)$ is local, apply $\Gamma$ to the epimorphism ${\coprod }_i{U}_i\to 1$ associated with any open cover $X={\bigcup }_i{U}_i$, regarding the opens as subterminal sheaves. Since $\Gamma U_i$ is a singleton exactly when $U_i=X$, and otherwise empty, coproduct and epimorphism preservation force some $U_i=X$.

Thus every open cover of $X$ contains $X$ itself. Conversely this open cover criterion for a local sheaf topos condition is equivalent to existence of a point $x$ whose only open neighborhood is $X$: the union of all proper open sets cannot be all of $X$, so choose $x$ outside it. Such a point plainly forces any cover to contain $X$. Empty spaces fail the condition.

At this point, the stalk functor $F\mapsto F_x$ is simply $F(X)=\Gamma F$, since there is only one open neighborhood. Its right adjoint is the skyscraper sheaf of setsA morphism $F\to R(S)$ is determined exactly by its map $F(X)\to S$, because all proper opens omit $x$. Hence $\Gamma ⊣R$, and $\Gamma$ preserves finite limits, proving locality. ConsequentlyIn a $T_0$ space this distinguished point is unique and closed. In a $T_1$ space the condition forces $X$ to be a singleton. Indistinguishable points in a non-$T_0$ space can all have this property; uniqueness of an actual point is not part of the general criterion.

A decidable $B$ has injective action maps. First prove that evaluation at $1$ distinguishes equivariant functions. Suppose $f(1,a)=g(1,a)$ for every $a$. Fix $m\in M$ and choose $p,q$ with $pmq=p$. For each $a$, equivariance givesThe same equation holds for $g$, so these values agree. Cancel the injective action of $p$ on $B$ to obtain $f(m,a)=g(m,a)$. Hence $f=g$. This proves the hinted contrapositive and, more precisely, injectivity of the trace map $f\mapsto (a\mapsto f(1,a))$.

Now suppose $m\cdot f=m\cdot g$ in the exponential. Evaluating this equality at $(1,m\cdot a)$ givesCancel the action of $m$ on $B$. The trace maps agree, so the preceding argument gives $f=g$. Every action map on $B^A$ is therefore injective. By the introductory criterion, $B^A$ is decidable whenever $B$ is under the specified monoid condition. Neither cancellation in $M$ nor injectivity of its action on $A$ is assumed.

For the free monoid on $x,y$, use the functionThe strict inequality is important. For any prefix $v$, $|vw|>|v|+n$ is equivalent to $|w|>n$. Whenever it holds, $w$ is nonempty and prefixing $v$ does not change its final letter. When it fails, both values are zero. Thuswhich proves equivariance for the diagonal action on $M\times \mathbb{N}$ and the trivial action on $B$. Hence $f$ is an element of the exponential described above. Let $g$ be the constant-zero equivariant function. They differ at $(x,0)$.

But every word $wy$ ends in $y$, sofor every $w,n$. The action of $y$ on $B^A$ is not injective, and $B^A$ is not decidable, even though $B$ is decidable. This is a nondecidable exponential of decidable monoid sets. The monoid condition in part (a) also fails here: $|pmq|=|p|+|m|+|q|$ cannot equal $|p|$ for a nonempty word $m$.

The two introductory requests can be settled before the lettered applications. In the functor category $[C,\mathbf{Set}]$, finite limits and finite unions of subobjects are pointwise. The component of the diagonal at $c$ is ordinary equality on $F(c)$. Its only possible complement isThis forms a subfunctor exactly when each $F(u)$ sends unequal elements to unequal elements, equivalently when every $F(u)$ is injective. In that case $D$ and the diagonal are disjoint and their union is $F^2$ at every component. Conversely, a diagonal complement must have these components and be stable under every transition map. Hence $F$ is decidable exactly when every transition map is injective.

Regard a monoid $M$ as a one-object category; a covariant set-valued functor is a left M-set. Give $M\times A$ the diagonal left action $t\cdot (w,a)=(tw,t\cdot a)$. LetRight multiplication on the first coordinate commutes with the diagonal left action, so $m\cdot f$ remains equivariant. The formula obeys $m\cdot (n\cdot f)=(mn)\cdot f$ and $1\cdot f=f$. Evaluation isIt is equivariant because $\mathrm{ev}(m\cdot f,m\cdot a)=f(m,m\cdot a)=m\cdot f(1,a)$.

For an equivariant $h:C\times A\to B$, defineThis is equivariant in $(w,a)$, and $\hat{h}(m\cdot c)=m\cdot \hat{h}(c)$. Evaluation recovers $h$. Conversely, currying the evaluation of a map $C\to E$ recovers that map by its equivariance. This proves the exponential universal property and the natural identificationwith exactly the stated action. In particular, decidability in a set-valued functor category says that a left M-set is decidable if and only if each of its action maps is injective.

A monad consists of an endofunctor $T:\mathcal{C}\to \mathcal{C}$ and natural transformations $\eta :1\Rightarrow T$ and $\mu :T^2\Rightarrow T$, the unit and multiplication of a monad, satisfyingAn algebra for a monad is $(A,a)$ with $a:TA\to A$ satisfying $a{\eta }_A=1_A$ and $a{\mu }_A=aTa$. A morphism of algebras for a monad $h:(A,a)\to (B,b)$ satisfies $ha=bTh$. These objects and morphisms form the Eilenberg-Moore category ${\mathcal{C}}^T$; its composition works because $T$ is a functor.

For the list monad, $TX={\coprod }_{n\ge 0}{X}^n$ is the set of finite ordered lists, including the empty list. The map $Tf$ applies $f$ to each entry; ${\eta }_X(x)=[x]$ and ${\mu }_X$ concatenates a list of lists. The unit laws say that adding singleton brackets and then flattening changes nothing. Associativity says that flattening a list of lists of lists in either order produces the same ordered sequence. These descriptions also prove naturality.

If $a:TX\to X$ is an algebra for a monad, defineThe singleton law gives $a([x])=x$. Apply the algebra associativity law to $[[],[x]]$ and $[[x],[]]$ to obtain $e\ast x=x=x\ast e$. Applying it to $[[x,y],[z]]$ and $[[x],[y,z]]$ showsThus $(X,\ast ,e)$ is a monoid. Applying the same law to $[[x_1,\dots ,x_{n-1}],[x_n]]$ shows inductively that $a$ is necessarily ordered multiplication of its entries, with the empty product $e$.

Conversely, any monoid defines such a list-fold map $a$. The monoid unit proves $a\eta =1$, and associativity and the unit prove that multiplying flattened lists equals multiplying their individual products, including empty sublists. Hence $a\mu =aTa$. An algebra morphism preserves the empty-list value and two-entry-list values, so it is a monoid homomorphism; conversely a monoid homomorphism preserves every ordered product and is an algebra morphism. ThereforeThus list-monad algebras are monoids, with the identification also matching every morphism.

A pointed category has a zero object, both initial and terminal. Factoring through that object gives a zero morphism $0_{A,B}$ between any two objects. In this paper a semi-additive structure means commutative-monoid enrichment: every hom-set is a commutative monoid with additive zero, and composition distributes over addition in both variables. No existence of finite products in a category is included in this last definition. This convention matters for the final one-object example; under the stronger convention requiring finite biproducts, that example would not be a semi-additive category.

Let $c_{A,B}:A+B\to A\times B$ be the given canonical isomorphism. Transfer the coproduct injections across $c_{A,B}$, so $A\times B$ is also a coproduct in a category, with injectionsWrite ${\nabla }_B:B\times B\to B$ for the morphism whose composites with $i_1,i_2$ are both $1_B$. For $f,g:A\to B$, define the biproduct-induced addition of morphisms byThe zero is the existing zero morphism. We verify the laws from the universal properties, without assuming addition in advance.

All finite canonical maps from coproducts to products are isomorphisms, by induction from the binary ones and the zero object. Thus both $(B\times B)\times B$ and $B\times (B\times B)$ are ternary coproducts in a category. The two iterated fold maps to $B$ agree on each of the three injections, hence are equal. Applying this to $⟨f,g,h⟩$ gives associativity. The interchange $B\times B\to B\times B$ swaps the two injections, so its composite with ${\nabla }_B$ is ${\nabla }_B$, giving commutativity. Finally $⟨f,0⟩=i_{1}f$, so $f+0=f$, and similarly $0+f=f$.

Precomposition is additive because $⟨f,g⟩u=⟨fu,gu⟩$. For $v:B\to C$, the morphisms $v{\nabla }_B$ and ${\nabla }_C(v\times v)$ agree on both injections, so they agree; consequently $v(f+g)=vf+vg$. Composition with a zero morphism is zero. This proves the commutative-monoid enrichment.

It is unique. In any such enrichment, the additive zero morphisms agree with the pointed ones, since each map to or from the zero object belongs to a singleton hom-set. The projections of $i_1{p}_1+i_2{p}_2$ from $A\times B$ are respectively $p_1,p_2$ by bilinearity, soFor $A=B$, composing on the left by ${\nabla }_B$ and on the right by $⟨f,g⟩$ forces the displayed formula for $f+g$. Thus the biproducts determine exactly one such enrichment.

For the last part, the underlying one-object category has endomorphism monoid $(\mathbb{N},\cdot )$, including $0$, and identity $1$. Its usual addition gives a commutative-monoid enrichment. Any permutation $\sigma$ of the prime numbers extends, by unique prime factorization, to a multiplicative monoid automorphism ${\varphi }_{\sigma }:\mathbb{N}\to \mathbb{N}$, fixing $0,1$. Transport addition byThis is a commutative monoid operation with zero $0$, and multiplication distributes over it: applying ${\varphi }_{\sigma }$ reduces each distributive law to the ordinary one in $\mathbb{N}$. Thus each operation supplies a semi-additive structure on the same fixed composition law.

For each odd prime $p$, take $\sigma$ to interchange $2$ and $p$, fixing every other prime. ThenDifferent choices of $p$ give different additions, and there are infinitely many prime numbers. Hence there are infinitely many distinct semi-additive structures, even though these transported structures are isomorphic as enriched categories. The underlying one-object category has no terminal object, because its endomorphism set is not a singleton, so it indeed has no finite products in a category.

An adjunction $F⊣G$ is equivalently specified by a unit and counit of an adjunctionsatisfying the triangle identities

Let $F_i⊣G_i$ have units ${\eta }_i$ and counits ${\epsilon }_i$. The mate correspondence sends $\alpha :F_1\to F_2$ toConversely, $\beta :G_2\to G_1$ givesNaturality and the triangle identities show that the two constructions are inverse, yielding the required bijection of natural transformations.

Now let the endofunctor $F$ carry a monad $(F,\eta ,\mu )$ and let $F⊣G$. Taking right mates turnsinto a counit $ϵ:G\to 1$ and comultiplication $\delta :G\to G^2$. Since mates reverse composition, the monad unit and associativity laws become the comonad counit and coassociativity laws. Moreover, a map $FA\to A$ corresponds under the adjunction to a map $A\to GA$, and the algebra axioms correspond exactly to the coalgebra axioms. This is the monad on a left adjoint induces a comonad on its right adjoint construction and gives an isomorphism of the two structure categories.

For a monoid $M$, the free-$M$-set functor is $F(X)=M\times X$, and its algebras are precisely left $M$-sets, the objects of $[M,\mathbf{Set}]$. Its right adjoint is $G(X)=X^M$. The preceding isomorphism identifies $[M,\mathbf{Set}]$ with the Eilenberg-Moore category of coalgebras for the induced comonad on sets, compatibly with the forgetful functor. Therefore

A right monoid action has $x1=x$ and $(xm)n=x(mn)$. It is a contravariant functor from the one-object category of the monoid to sets. The regular right action is multiplication on $M$ itself. Products of right actions use the diagonal action.

A semigroup is an algebraic magma whose binary operation has the associative property. Its products can be regrouped while preserving the order of their elements. An identity element and inverse elements are not required.

For example, the positive integers with addition form a semigroup, since $(a+b)+c=a+(b+c)$ and a sum of positive integers is positive. They have no identity element: it would have to be zero, which is outside that set. Nonempty words over an alphabet with concatenation give a noncommutative example without an identity element. Including the empty word instead gives a free monoid.

The usefulness of a semigroup is that an ordered list has one product regardless of its parentheses. This permits replacing a consecutive block by its already computed value. Here the empty set is also allowed as a semigroup; a monoid is necessarily nonempty because it contains an identity element.

A semiring has a commutative monoid operation $(S,+,0)$ and a monoid operation $(S,\cdot ,1)$, with multiplication distributing over addition on both sides and $0$ absorbing multiplication. Additive inverses are not required. The natural numbers with their usual addition and multiplication are a basic example. Regarding multiplication as composition yields a one-object category with commutative-monoid enrichment.