NOTES ON RIEG THEORY: SEMIRING WITH EXPONENTIALS IN LOGIC, PROFINITE ARITHMETIC, ENUMERATIVE COMBINATORICS, AND CATEGORY THEORY

Notation 1.0.1. We adopt the following notations:

• $\mathbb{N}$ denotes the set of all non-negative integers. Sometimes, we regard it as a poset with the natural ordering.
• ${\mathbb{N}}^{\ast }$ denotes the set of all positive integers. We may regard it as a poset with the divisibility order.

Definition 2.1.1 (Rig). A (possibly non-commutative) rig is a set $R$ equipped with

• two constants ($=$ nullary operations) $0,1\in R$ and
• two binary operations, $+,\times :R\times R\to R$

such that the following equations hold for all $x,y,z\in R$:

(1)

$0+x=x$,

(2)

$(x+y)+z=x+(y+z)$,

(3)

$x+y=y+x$,

(4)

$1\times x=x$,

(5)

$x\times 1=x$,

(6)

$(x\times y)\times z=x\times (y\times z)$,

(7)

$x\times 0=0$,

(8)

$x\times (y+z)=(x\times y)+(x\times z)$,

(9)

$0\times x=0$, and

(10)

$(x+y)\times z=(x\times z)+(y\times z)$.

If $R$ satisfies an additional equation

(11)

$x\times y=y\times x$,

we call it a commutative rig. A rig homomorphism is a function that preserves the four operations $0,1,+,\times$. The category of rigs and rig homomorphisms is denoted by $\mathrm{𝐑𝐢𝐠𝐬}$.

Example 2.1.2 (Rings). Of course, every ring is a rig; the theory of rigs is obtained from that of rings by dropping the axiom that every element has an additive inverse. However, rings will play only a marginal role in this paper: we will see that the only rieg whose underlying rig is a ring is the degenerate one (Proposition 2.3.2).

Example 2.1.3 (Rig of natural numbers). The rig of natural numbers (with the usual addition and multiplication) $\mathbb{N}$ is the initial object of the category $\mathrm{𝐑𝐢𝐠𝐬}$. Its quotients will be the main subject of Section 3.

Example 2.1.4 (Rig of endohomomorphisms on a commutative monoid). For a commutative monoid $(A,e,\ast )$, the set of monoid endohomomorphisms $\mathrm{End}(A,e,\ast )$ admits a rig structure as follows:

• The element $0\in \mathrm{End}(A,e,\ast )$ is the constant function to the neutral element $A\to A:a\mapsto e$.
• The element $1\in \mathrm{End}(A,e,\ast )$ is the identity function ${\mathrm{id}}_A:A\to A$.
• The sum $f+g$ of two elements $f,g\in \mathrm{End}(A,e,\ast )$ is given by $(f+g)(a):=f(a)\ast g(a)$. (Here, we use the commutativity of $\ast$.)
• The product $f\times g$ of two elements $f,g\in \mathrm{End}(A,e,\ast )$ is given by the composite $f\circ g$.

For the additive monoid $(\mathbb{N},0,+)$, the rig $\mathrm{End}(\mathbb{N},0,+)$ is isomorphic to the rig of natural numbers $(\mathbb{N},0,1,+,\times )$. A rig of endohomomorphisms is, however, typically non-commutative; for the additive group $({\mathbb{Z}}^2,0,+)$, the rig $\mathrm{End}({\mathbb{Z}}^2,0,+)$ is isomorphic to the ring $M_2(\mathbb{Z})$ of $2\times 2$ matrices over $\mathbb{Z}$, which is not commutative. This is the example that we will use to define riegs (Definition 2.2.1).

Definition 2.2.1 (Rieg). A rieg is a commutative rig $(R,0,1,+,\times )$ equipped with a rig homomorphism $R\to \mathrm{End}(R,1,\times )$.

Proposition 2.2.2 (Equational definition of riegs). The definition of riegs (Definition 2.2.1) can be rephrased by the five operations:

• two constants ($=$ nullary operations), $0,1\in R$, and
• three binary operations, $+,\times ,\uparrow :R\times R\to R$,

and fourteen equations:

(1)

$0+x=x$

(2)

$(x+y)+z=x+(y+z)$

(3)

$x+y=y+x$

(4)

$1x=x$

(5)

$(\mathit{𝑥𝑦})z=x(\mathit{𝑦𝑧})$

(6)

$\mathit{𝑥𝑦}=\mathit{𝑦𝑥}$

(7)

$x0=0$

(8)

$x(y+z)=\mathit{𝑥𝑦}+\mathit{𝑥𝑧}$

(9)

$1^x=1$

(10)

${(\mathit{𝑦𝑧})}^x=y^x{z}^x$.

(11)

$x^0=1$

(12)

$x^1=x$

(13)

$x^{y+z}=x^y{x}^z$

(14)

$x^{\mathit{𝑦𝑧}}={(x^z)}^y$,

where $\mathit{𝑥𝑦}$ denotes $x\times y$, and $x^y$ denotes $x\uparrow y$ as usual.

Remark 2.2.3. As a special case of the equation $x^0=1$, we have $0^0=1$. This convention will be repeatedly interpreted in many ways in this paper.

Definition 2.2.4. A rieg homomorphism is a function that preserves all (five) operations $0,1,+,\times ,\uparrow$. We write $\mathrm{𝐑𝐢𝐞𝐠𝐬}$ for the category of riegs.

Example 2.2.5 (The initial rieg: natural numbers). The set of all natural numbers $\mathbb{N}=\{0,1,2,\dots \}$ equipped with the usual zero $0$, one $1$, addition $+$, multiplication $\times$, and exponentiation $\uparrow$, forms the rieg of natural numbers $\mathbb{N}$. Here are a few remarks about this example:

• This rieg $\mathbb{N}$ is an initial object in the category $\mathrm{𝐑𝐢𝐞𝐠𝐬}$. Indeed, for a rieg $R$, the unique rig homomorphism $\varphi :\mathbb{N}\to R$ automatically preserves $\uparrow$: for $n,m\in \mathbb{N}$, the equations $x^{y+z}=x^y{x}^z$, $x^1=x$, and $x^0=1$ give $\varphi {(n)}^{\varphi (m)}=\varphi {(n)}^{1+\cdots +1}=\varphi (n)\cdots \varphi (n)=\varphi (n^m)$, where both products have $m$ factors.
• This is the unique rieg structure on the rig of natural numbers, since $\mathbb{N}$ is the initial rig (Example 2.1.3) and a rieg structure is given by a rig homomorphism $\mathbb{N}\to \mathrm{End}(\mathbb{N},1,\times )$.
• We adopt the convention that $0^0=1$ (see Remark 2.2.3).

Example 2.2.6 (The degenerate rieg). A singleton $\text{{∗}}$ admits exactly one rieg structure, which we call the degenerate rieg $1$. The degenerate rieg is a terminal object of the category $\mathrm{𝐑𝐢𝐞𝐠𝐬}$.

Claim 2.3.1. If a rieg $R$ contains an additive inverse $-1$ of $1$, then it is degenerate, that is, $\mathit{𝑅\cong }1$ (cf. Example 2.2.6).

Proposition 2.3.2 (No rieg is a ring). If a rieg $R$ is a ring, then it is degenerate, that is, $\mathit{𝑅\cong }1$.

Remark 2.3.3. A similar problem appears for division, and there we have a solution. A meadow is a commutative ring with a total inverse operation, and its axioms imply $0^{-1}=0$ [BHT09]. So we may hope to do the same thing here, that is, to choose a value of $0^{-1}$. This does not work. Whatever the value of $0^{-1}$ is, we have $0\times 0^{-1}=0$, and the proof of Claim 2.3.1 still gives $1=0$.

Puzzle 3.1.1. Find all pairs of natural numbers $(n,m)$ such that

Answer. Consider the equation modulo $8$. If $n\ge 3$, the equation is simplified to

However, since the quadratic residues modulo $8$ are $0$, $1$, and $4$, it is impossible. Therefore, we only need to check $n=0$, $1$, and $2$. We conclude that the only solution is $(n,m)=(2,3)$.

Puzzle 3.1.2 (A puzzle provided by J.Koizumi). Find a four-digit natural number $n$ such that the last four digits of $3^n$ are equal to $n$.

Answer. $n=5387$ is the only answer.

Question 3.1.3. Is there an infinite sequence of decimal digits

such that, for every integer $k\ge 1$, the truncation $n_k:={\sum }_{i=1}^k{a}_{i}10^{i-1}$ satisfies the congruence

Remark 3.1.4 (Attribution). The affirmative answer is not new. It is a special case of a theorem of Jiménez Urroz and Yebra [JY09, Theorem 3]: for every valid base $b$ (an integer such that $q\mid b$ for every prime $p\mid b$ and every prime $q\mid p-1$) and every integer $a$ not divisible by the squarefree part of $b$, there is a unique such digit sequence for the congruences $a^x\equiv x(\mathit{𝑚𝑜𝑑}{b}^n)$ for all sufficiently large $n$. The base $b=10$ is valid, and our digit sequence is recorded as [OEIa], known there as the final digits of Graham’s number; the truncations displayed in Figure 1 form [OEIb]. What rieg theory adds is not the statement but a conceptual proof: the sequence is the unique fixed point of the contraction $3^x$ (Proposition 3.3.12).

Answer (Rough sketch).

In a topological rieg ${\mathbb{N}}_{\infty ,10^{\infty }}$ (Definition 3.3.6), we can take the limit $\alpha$ of the sequence

By the continuity of $3^x:{\mathbb{N}}_{\infty ,10^{\infty }}\to {\mathbb{N}}_{\infty ,10^{\infty }}$, we have $3^{\alpha }=\alpha$.

Puzzle 3.1.5. Find all positive integer $n>0$ such that, for any positive integers $a,b,a^{\prime },b^{\prime }$, we have

Answer (A special case of [BL92; BL93]). There are exactly $5$ possibilities: $n=1,2,6,42,1806$

Definition 3.2.1 (${\mathbb{N}}_{a,b}$). For a natural number $a\ge 0$ and a positive integer $b>0$, let ${\mathbb{N}}_{a,b}$ be the $(a+b)$-element quotient $\mathbb{N}∕{\sim }_{a,b}$, where

Thus the numbers below $a$ form the initial exceptional part, and the numbers from $a$ onward repeat with period $b$.

Theorem 3.2.2 (Burris–Lee [BL92, Theorem 3.12]). For $a\ge 0$ and $b>0$, the canonical operations descend from $\mathbb{N}$ to ${\mathbb{N}}_{a,b}$ if and only if, for every prime $p$ and every positive integer $e$,

Example 3.2.3 (The rieg of truth values). The quotient ${\mathbb{N}}_{1,1}$ is the rieg of truth values $\mathbf{\text{2}}=\{\perp ,\top \}$ from Section 5.

Example 3.2.4 (Parity rieg). The quotient ${\mathbb{N}}_{1,2}$ is

which we call the parity rieg. Keeping $0$ separate is essential: exponentiation does not descend to $\mathbb{Z}∕2\mathbb{Z}$, since $2^0$ is odd but $2^2$ is even.

Example 3.2.5 (Overflow riegs). For $n\ge 0$, the quotient ${\mathbb{N}}_{n,1}$ is the overflow rieg with threshold $n$, denoted by ${\mathrm{\text{OverFlow}}}_n$. Its elements are $0,1,\dots ,n-1,\star$, where every natural number at least $n$ is sent to $\star$.

Corollary 3.2.6 ([BL92, Corollary 3.14], attributed there to D. Higgs). The only finite quotient riegs of $\mathbb{N}$ with cyclic positive part are

Example 3.2.7. The number $8=2^3$ satisfies both conditions in Theorem 3.2.2 with $a=3$. Hence ${\mathbb{N}}_{3,8}$ is a rieg. This is exactly the finite arithmetic used in the high-school calculation of Section 3.1.1.

Example 3.2.8. The number $10$ fails the second Burris–Lee condition, since $5\mid 10$ but $4\nmid 10$. For every $n\ge 2$, however, $10^n=2^n{5}^n$ and $4\mid 10^n$, so ${\mathbb{N}}_{n,10^n}$ is a rieg. These riegs form the finite inverse system used below to construct the topological rieg of $10$-adic natural numbers (Definition 3.3.6).

Definition 3.2.9 (Characteristic). The characteristic of a rig or rieg $R$, denoted by $\mathrm{\text{char}}R$, is the minimum pair $(a,b)\in \mathbb{N}\times {\mathbb{N}}^{\ast }$ such that

if it exists. Otherwise, we put $\mathrm{\text{char}}R=(\infty ,0)$, where $(\infty ,0)$ is a formal maximum element.

Corollary 3.2.10 (Burris–Lee theorem in terms of rieg characteristics [BL92; BL93]). A pair $(a,b)\in \mathbb{N}\times {\mathbb{N}}^{\ast }$ is the characteristic of a rieg if and only if

for every prime $p$ and every positive integer $e$.

Remark 3.2.11 (Why this definition is natural). Let $R$ be a rig or rieg. Factor the unique homomorphism from the initial object as

If this image is finite, then it is ${\mathbb{N}}_{a,b}$ and $\mathrm{\text{char}}R=(a,b)$. If the map $\mathbb{N}\to R$ is injective, then $\mathrm{\text{char}}R=(\infty ,0)$. The usual definition for rings cannot be used directly: if a positive integer $n$ satisfies $n=0$ in a rieg, then $n-1$ is an additive inverse of $1$, and the rieg is degenerate by Claim 2.3.1.

This viewpoint makes sense for any equational theory: for an algebra $R$, the image of the canonical map from the initial algebra is a quotient of the initial algebra, and this quotient deserves to be called the characteristic of $R$ in general. For rings, the initial algebra is $\mathbb{Z}$, the image is $\mathbb{Z}∕n\mathbb{Z}$, and we recover the usual characteristic $n$. For riegs, the image is ${\mathbb{N}}_{a,b}$, and $\mathrm{\text{char}}R=(a,b)$ is just a name for this quotient.

Definition 3.3.1. The rieg of profinite natural numbers $\widehat{\mathbb{N}}$ is the profinite completion of the initial rieg $\mathbb{N}$.

Lemma 3.3.2. The quotient rieg ${\mathbb{N}}_{n,n!}$ exists for every $n\in \mathbb{N}$. Moreover, the family

is cofinal in ${\mathrm{FinQuot}}_{\mathbf{\text{𝐑𝐢𝐞𝐠𝐬}}}\left(\mathbb{N}\right)$.

Proposition 3.3.3. The profinite rieg $\widehat{\mathbb{N}}$ is the limit of the following diagram.

Theorem 3.3.4 (The underlying set of $\widehat{\mathbb{N}}$). The underlying set of $\widehat{\mathbb{N}}$ is

where $\widehat{\mathbb{Z}}$ denotes the usual set of profinite integers. The canonical projection ${\pi }_{a,b}:\widehat{\mathbb{N}}\to {\mathbb{N}}_{a,b}$ restricts to the canonical maps

and

Corollary 3.3.5 (The unique continuous extension of exponentiation). The exponentiation of $\mathbb{N}$ extends to a continuous operation

defined for all pairs of elements, and such a continuous extension is unique.

Definition 3.3.6 (The topological rieg of $10$-adic natural numbers). The topological rieg of $10$-adic natural numbers ${\mathbb{N}}_{\infty ,10^{\infty }}$ is the limit of the following diagram in the category of topological riegs:

By Example 3.2.8, each ${\mathbb{N}}_{n,10^n}$ is a rieg for $n\ge 2$.

Remark 3.3.7 (No $5$-adic analogue). This construction does not work for the powers of a single odd prime, say $5$: since $5\mid 5^n$ but $4=5-1\nmid 5^n$, the second condition in Theorem 3.2.2 fails. Hence the rig ${\mathbb{N}}_{a,5^n}$ admits no rieg structure for any $a$. In this sense, there is no topological rieg of “$5$-adic natural numbers” $\mathbb{N}\bigsqcup {\mathbb{Z}}_5$ obtained in this way.

Definition 3.3.8 (Carmichael function [Car10]). For a positive integer $n$, the Carmichael function $\lambda \left(n\right)$ is the least positive integer $d$ such that

for every $u\in {(\mathbb{Z}∕n\mathbb{Z})}^{\times }$. Equivalently, $\lambda \left(n\right)$ is the exponent of the group ${(\mathbb{Z}∕n\mathbb{Z})}^{\times }$.

Remark 3.3.9 (The jump function). With respect to the divisibility order, the Carmichael function has a right adjoint ${\lambda }^{\ast }:{\mathbb{N}}^{\ast }\to {\mathbb{N}}^{\ast }$, whose notation ${\lambda }^{\ast }$ we borrow from [CP09, Theorem 5.2(b)]. Thus

Therefore, ${\lambda }^{\ast }\left(b\right)$ records the possible next periods $b^{\prime }$ for which exponentiation raises the precision.

Lemma 3.3.10 (A metric for an inverse sequence). Let

be an inverse limit of non-empty finite sets and surjective maps, where $X_0$ has one element. Write ${\pi }_n:X\to X_n$ for the projections. For distinct $x,y\in X$, let

and put

Then $(X,d)$ is a complete ultrametric space.

Suppose that a map $F:X\to X$ satisfies

for every $n\ge 0$. Then $F$ is a contraction with Lipschitz constant $\frac{1}{2}$.

Lemma 3.3.11 (Stabilization of the last two digits). For every element $\xi$ of the modular part $\mathbb{Z}∕10^2\mathbb{Z}\subset {\mathbb{N}}_{2,10^2}$, we have $T^4\left(\xi \right)=\left[87\right]$.

Proposition 3.3.12 (The unique fixed point of $3^x$). The function $T\left(x\right)=3^x$ on ${\mathbb{N}}_{\infty ,10^{\infty }}$ has a unique fixed point $\alpha$, which belongs to ${\mathbb{Z}}_2\times {\mathbb{Z}}_5$, and every iteration sequence $x,T\left(x\right),T^2\left(x\right),\dots$ starting from $x\in {\mathbb{Z}}_2\times {\mathbb{Z}}_5$ converges to $\alpha$. Furthermore, for each $k\ge 2$, the reduction of $\alpha$ is the unique solution of $3^x=x$ in $\mathbb{Z}∕10^k\mathbb{Z}\subset {\mathbb{N}}_{k,10^k}$ (cf. Figure 1).

Proposition 3.3.13 (The solutions of $x^x=x$). In ${\mathbb{N}}_{\infty ,10^{\infty }}=\mathbb{N}\bigsqcup ({\mathbb{Z}}_2\times {\mathbb{Z}}_5)$, the equation $x^x=x$ has exactly $11$ solutions: the element $1$ of the summand $\mathbb{N}$, and the ten elements

of ${\mathbb{Z}}_2\times {\mathbb{Z}}_5$, where ${\mu }_4=\{1,i,-1,-i\}$ denotes the group of fourth roots of unity in ${{\mathbb{Z}}_5}^{\times }$.

Remark 3.3.14 (The levelwise counts diverge). Contrast Proposition 3.3.13 with Proposition 3.3.12, where every level has a unique solution. The numbers of solutions of $x^x=x$ in $\mathbb{Z}∕10^k\mathbb{Z}\subset {\mathbb{N}}_{k,10^k}$ for $k=2,3,\dots ,7$ are

and they are unbounded, even though the limit has only $11$ points: for a unit $u\equiv 1\left(\mathrm{mod}4\right)$ with $s:=v_2(u-1)$, one has $v_2(u^{2^s}-1)=2s$, so $u$ solves the $2$-adic part of the equation modulo $2^k$ precisely when $k\le 2s$. Pairing such $u$ with the $5$-coordinate $0$ produces, for $k\ge 4$, at least $2^{\lfloor k∕2\rfloor }$ solutions at level $k$, almost all of which die at a later level. Note also that $0$ is a solution in the summand ${\mathbb{Z}}_2\times {\mathbb{Z}}_5$ but not in the summand $\mathbb{N}$: modulo $10^k$, the class $\left[0\right]$ is represented by $10^k$, and ${\left(10^k\right)}^{10^k}\equiv 0$. This illustrates the splitting $\mathbb{N}\bigsqcup {\mathbb{Z}}_{10}$ of Definition 3.3.6.

Definition 4.1.1. The ($1$-)category $\mathbf{\text{𝐂𝐂𝐂𝐜}}$ is defined as follows:

• Its objects are small categories that are cartesian closed and have finite coproducts.
• Its morphisms are functors between these categories that preserve finite products, finite coproducts, and exponentials, where we consider functors up to natural isomorphism3 .

Proposition 4.1.2. For a cartesian closed category $\mathcal{\text{𝒞}}$ with finite coproducts, the set of isomorphism classes of $\mathcal{\text{𝒞}}$ forms a rieg with the categorical initial object, the binary coproducts, the terminal object, the binary products, and the exponentials.

Remark 4.1.3 (Symmetric monoidal closed categories). This construction does not work for a symmetric monoidal closed category with finite coproducts, since we use the fact that the product $A\times B$ is a categorical product to prove some axioms including ${(x\times y)}^z=x^z\times y^z$.

Definition 4.1.4. The Burnside rieg functor $𝔅:\mathbf{\text{𝐂𝐂𝐂𝐜}}\to \mathbf{\text{𝐑𝐢𝐞𝐠𝐬}}$ sends an object $\mathcal{\text{𝒞}}$ of the category $\mathbf{\text{𝐂𝐂𝐂𝐜}}$ to the rieg induced by $\mathcal{\text{𝒞}}$ (Proposition 4.1.2), and a functor in $\mathbf{\text{𝐂𝐂𝐂𝐜}}$ to the induced rieg homomorphisms.

Proposition 4.1.5 (Topos to rieg functor). For a locally cartesian closed small category $\mathcal{\text{𝒞}}$ with finite coproduct (in particular, an elementary topos $\mathcal{\text{𝒞}}$), the correspondence

defines a contravariant functor

Example 4.1.6 (Finite sets to natural numbers). The Burnside rieg of finite sets is isomorphic to the rieg of natural numbers

Example 4.1.7 (Infinite sets to cardinal arithmetic). Let $\kappa$ be an infinite cardinal and ${\mathbf{\text{𝐒𝐞𝐭}}}_{<\kappa }$ be the (essentially small) category of sets with cardinality less than $\kappa$. The category ${\mathbf{\text{𝐒𝐞𝐭}}}_{<\kappa }$ is a topos if and only if it is cartesian closed if and only if $\kappa$ is a strong limit cardinal. Therefore, if $\kappa$ is a strong limit cardinal, then we obtain the induced rieg $𝔅\left({\mathbf{\text{𝐒𝐞𝐭}}}_{<\kappa }\right)$, which is the (small) rieg of cardinal arithmetic.

Obviously, the structure of this rieg is interconnected with set theory, especially continuum hypothesis. With the generalized continuum hypothesis, $𝔅\left({\mathbf{\text{𝐒𝐞𝐭}}}_{<{\beth }_{\omega }}\right)$ is a countable rieg with $2^{{\aleph }_0}={\aleph }_1$. However, without the GCH, there are many other possibilities of this rieg structure.

Example 4.1.8 (Finite presheaf topos). For any small category $\mathcal{\text{𝒞}}$, ${\mathbf{\text{𝐅𝐢𝐧𝐒𝐞𝐭}}}^{\mathcal{\text{𝒞}}}$ has all finite limits and colimits. Therefore, if ${\mathbf{\text{𝐅𝐢𝐧𝐒𝐞𝐭}}}^{\mathcal{\text{𝒞}}}$ is cartesian closed, we obtain a rieg $𝔅\left({\mathbf{\text{𝐅𝐢𝐧𝐒𝐞𝐭}}}^{\mathcal{\text{𝒞}}}\right)$. For example, if $\mathcal{\text{𝒞}}$ is a finite category or a (possibly infinite) group, then ${\mathbf{\text{𝐅𝐢𝐧𝐒𝐞𝐭}}}^{\mathcal{\text{𝒞}}}$ is known to be cartesian closed (and a topos).