\documentclass{amsart} \usepackage[left=2cm, right=2cm]{geometry} \usepackage{amsfonts, amsthm, amssymb, mathtools} \usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref} \usepackage{tikz,tikz-cd} \usepackage{cleveref} \usepackage{array} \usepackage{enumitem} \usepackage[style=alphabetic,sorting=nyt, maxnames=4]{biblatex} % \usepackage[style=authoryear, maxnames=4]{biblatex} \renewbibmacro{in:}{} % \addbibresource{biblio.bib} \addbibresource{CommonBiblio20240922.bib} \tikzset{pullback/.style={minimum size=1.2ex,path picture={ \draw[opacity=1,black,-,#1] (-0.5ex,-0.5ex) -- (0.5ex,-0.5ex) -- (0.5ex,0.5ex);% }}} \usetikzlibrary{calc} \usepackage{framed} \usepackage{placeins} \usepackage{pgfplots} \pgfplotsset{compat=1.18} % --- Theorem environments ------------------------------------------------- % All statement types share one numbering sequence (reset per subsection). % Each type nevertheless gets its own counter, aliased to `theorem' via the % aliascnt package: with a literally shared counter, a cross-reference only % records "counter theorem, value 3.3.10", so \Cref (and \autoref) cannot % know whether the target was a Lemma or a Definition and falls back to % "Theorem". Aliased counters keep the numbering identical while making % every reference carry its true type. \usepackage{aliascnt} \newcommand{\newaliasedtheorem}[2]{% \newaliascnt{#1}{theorem}% \newtheorem{#1}[#1]{#2}% \aliascntresetthe{#1}% } \theoremstyle{plain} \newtheorem{theorem}{Theorem}[subsection] \newaliasedtheorem{proposition}{Proposition} \newaliasedtheorem{lemma}{Lemma} \newaliasedtheorem{corollary}{Corollary} \newaliasedtheorem{todo}{Todo} \newaliasedtheorem{conjecture}{Conjecture} \newaliasedtheorem{fact}{Fact} \newaliasedtheorem{claim}{Claim} \crefname{claim}{Claim}{Claims} \newaliasedtheorem{question}{Question} \newaliasedtheorem{problem}{Problem} \newtheorem*{answer}{Answer} \theoremstyle{definition} \newaliasedtheorem{example}{Example} \newaliasedtheorem{definition}{Definition} \newaliasedtheorem{remark}{Remark} \newaliasedtheorem{notation}{Notation} \newaliasedtheorem{puzzle}{Puzzle} \newaliasedtheorem{idea}{Idea} \newaliasedtheorem{exercise}{Exercise} % \Cref names for types cleveref does not know by default \crefname{todo}{todo}{todos}\Crefname{todo}{Todo}{Todos} \crefname{fact}{fact}{facts}\Crefname{fact}{Fact}{Facts} \crefname{notation}{notation}{notations}\Crefname{notation}{Notation}{Notations} \crefname{puzzle}{puzzle}{puzzles}\Crefname{puzzle}{Puzzle}{Puzzles} \crefname{idea}{idea}{ideas}\Crefname{idea}{Idea}{Ideas} \newcommand{\dq}[1]{``#1"} \newcommand{\memo}[1]{\textcolor{red}{todo: #1}} \newcommand{\invmemo}[1]{\textcolor{blue}{memo: #1}} % \newcommand{\invmemo}[1]{} \newcommand{\horamemo}[1]{\textcolor{green!70!black}{hora: #1}} \newcommand{\para}[1]{\paragraph{\textbf{#1}}} \newcommand{\Here}{ \begin{center} {\huge \color{red} ------------------Here------------------} {\huge \color{blue} ------------------Here------------------} \end{center} } \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathcal{C}} \newcommand{\D}{\mathcal{D}} \newcommand{\E}{\mathcal{E}} \newcommand{\F}{\mathbf{F}} \newcommand{\G}{\mathcal{G}} \renewcommand{\L}{\mathcal{L}} \newcommand{\id}{\mathrm{id}} \newcommand{\op}{\mathrm{op}} \newcommand{\ob}{\mathrm{ob}} \newcommand{\Set}{\mathbf{Set}} \newcommand{\sSet}{\mathbf{sSet}} \newcommand{\FinSet}{\mathbf{FinSet}} \newcommand{\PSh}{\mathbf{PSh}} \newcommand{\Sh}{\mathbf{Sh}} \newcommand{\Cont}{\mathbf{Cont}} \newcommand{\Func}[2]{[#1,#2]} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\demph}[1]{\textit{#1}} \font\maljapanese=dmjhira at 2.5ex \newcommand{\yo}{\textrm{\!\maljapanese\char"48}} \newcommand{\Pow}{\mathcal{P}} \newcommand{\Aut}{\mathrm{Aut}} \newcommand{\Po}[1]{\mathcal{P}(#1)} \newcommand{\Top}{\mathrm{Top}} \newcommand{\HeyAlg}{\mathrm{HeyAlg}} \newcommand{\Rieg}{\mathbf{Riegs}} \newcommand{\Ring}{\mathbf{Rings}} \newcommand{\Rig}{\mathbf{Rigs}} \newcommand{\ti}{\mathbin{\times}} \newcommand{\ex}{\mathbin{\uparrow}} \newcommand{\co}{\mathrm{c}} \newcommand{\2}{\mathbf{2}} \newcommand{\1}{\mathbf{1}} \newcommand{\mult}[1]{\mathrm{mult}(#1)} \newcommand{\mN}{\mult{\N}} \renewcommand{\H}{H} \newcommand{\rad}{\mathrm{rad}} \newcommand{\Mr}[2]{\N_{#1,#2}} \newcommand{\End}{\mathrm{End}} \newcommand{\Groupoid}{\mathrm{Groupoid}} \newcommand{\Groupoidfin}{\Groupoid_{\mathrm{fin}}} \newcommand{\TB}{\star} \newcommand{\ep}{\varepsilon} \newcommand{\loga}{log-able} \newcommand{\ch}{\mathrm{char}} \newcommand{\TV}{\Omega} \newcommand{\chz}{(\infty, 0)} \newcommand{\N}{\mathbb{N}} \newcommand{\Nd}{\N^{\mathrm{div}}} \newcommand{\Np}{\N^*} \newcommand{\K}[1]{#1 / \hspace{-1pt} \scalebox{0.7}{$\cong$}} \newcommand{\biK}[1]{#1 / \hspace{-1pt} \scalebox{0.7}{$\simeq$}} \newcommand{\lcm}{\mathrm{lcm}} \newcommand{\pro}[1]{\widehat{#1}} \newcommand{\proN}{\pro{\mathbb{N}}} \newcommand{\proZ}{\pro{\mathbb{Z}}} \newcommand\binuparrow{\mathbin{\uparrow}} \newcommand{\powow}{\binuparrow \binuparrow} \newcommand{\Image}{\mathrm{Im}} \newcommand{\OF}{\mathrm{OverFlow}} \newcommand{\T}{\mathbb{T}} \newcommand{\TAlg}{\mathrm{Alg}_{\T}} \newcommand{\finTAlg}{\mathrm{finAlg}_{\T}} \newcommand{\TTAlg}{\Top\TAlg} \newcommand{\Quot}{\operatorname{Quot}} \newcommand{\FinQuot}{\operatorname{FinQuot}} \newcommand{\jump}{\lambda^{*}} \newcommand{\B}{\mathfrak{B}} \newcommand{\CCCc}{\mathbf{CCCc}} \newcommand{\Hom}{\mathrm{Hom}} \title[Rieg theory]{Notes on Rieg theory: semiring with exponentials in logic, profinite arithmetic, enumerative combinatorics, and category theory \memo{0th draft}} \author{Ryuya Hora} \address{ZEN University, Tokyo, Japan} \email{ryuya\_hora@zen.ac.jp} % \date{\today} \subjclass[2020]{16Y60, 03G10, 11D61, 20E18, 18D15, 18B25} \keywords{Semiring, rig, exponential, profinite set, Tarski highschool problem, objective number theory, cartesian closed category, topos, Burnside rig, Heyting algebra, equational theory.} \begin{document} \definecolor{shadecolor}{gray}{0.9} \begin{abstract} In this paper, we introduce the notion of a \textit{rieg}, that is, a semiring equipped with a binary operation called exponentiation, and present its basic theory along with numerous examples. We begin by reviewing the classification of quotient riegs over $\mathbb{N}$ given by Burris and Lee. Then, through concrete examples, we propose how riegs can appear in (pro)finite arithmetic, category theory, enumerative combinatorics, and logic. Typical examples of a rieg include the rieg of natural numbers $\N$, the five cyclic models ($\Mr{1}{1},\Mr{1}{2},\Mr{1}{6},\Mr{1}{42},$ and $\Mr{1}{1806}$), other quotient riegs of $\mathbb{N}$ ($=$ modulo arithmetic with exponentials), the canonical profinite rieg $\mathbb{N} \sqcup \widehat{\mathbb{Z}}$, the topological rieg of $10$-adic natural numbers $\Mr{\infty}{10^{\infty}} = \N \sqcup (\Z_2 \times \Z_5)$ (which does not work for the $5$-adic natural numbers $\N \sqcup \Z_5$), the cardinal arithmetic like $2^{\aleph_0}$, the rieg of truth values $\{\bot, \top\}$ with $p^q \coloneqq (q\to p)$, Heyting algebras including the set of open subsets $\mathcal{O}(X)$ of a topological space $X$, the rieg of finite directed graphs, the Burnside rieg of a finite group, the rieg of rooted trees, the rieg of isomorphism classes of finite groups, and other decategorified topoi. \end{abstract} \maketitle \tableofcontents \section{Introduction} The aim of the present paper is to popularise an algebraic structure, which we will call \demph{riegs}, by providing several theorems and examples. As a \demph{rig} defined as a \dq{ri\textbf{n}g without \textbf{n}egatives} (\cite{schanuel1990negative}) a \demph{rieg} is a \dq{rig with \textbf{e}xponentials.} In other words, a rieg is a ring-like structure that has $0,1,+,\ti,$ and a binary operation $\ex$ (\Cref{def:rieg}). The prototypical example of a rieg is the rieg of natural numbers. Of course, the idea of considering ring-like structures with exponentials is not new. In the context of algebras, \memo{write about rings with unary exponentials} In the context of objective number theory, \memo{write} In the context of ($p$-adic) dynaical systems, \memo{write} In the context of category theory, \cite{birkhoff1942generalized} \begin{quote}\cite{schanuel2000objective} Objective number theory is the study of addition and multiplication (and eventually exponentiation) of objects in suitable categories. \end{quote} Fiore \cite{fiore2006remarks} To the best of the author’s knowledge, the field in which rigs with (binary) exponentiation have been most actively studied is (finite) model theory. The Tarski High School problem concerns the theory of the positive integers with addition, multiplication, and exponentiation. Even after this problem was resolved, research on small models continued to progress. The story until 2005 is summarized in \cite{burris2005saga}. In the context of (finite) model theory, \memo{write} \para{Acknowledgement} The author would like to thank his supervisor Ryu Hasegawa for helpful discussions and suggestions. He was supported by JSPS KAKENHI Grant Number JP24KJ0837 and FoPM, WINGS Program, the University of Tokyo. He is also grateful to Ivan Di Liberti for pointing out \Cref{rmk:Meadow}. \memo{MSpaceTopos, Koizumi, Kamio, Menni, } \para{Survey} \begin{itemize} \item[1942] One can see the idea of an algebra of structures, with exponential in \cite{birkhoff1942generalized}. \item[1980s] Wilkie gives a solution to Tarski's high school algebra problem, circulated as a preprint and published in 2000 \cite{wilkie1980exponentiation}. \item[1992] \cite{burris1992small} (and its summary \cite{burris1993tarski}) give what we call \demph{the Burris-Lee theorem} \item[2000] Schanuel publishes papers on objective number theory \cite{schanuel2000objective}\cite{schanuel2000transcendencein} \item[2005] The survey paper \cite{burris2005saga} was published. \item[2006] Fiore, Cosmo, and Balat give a type-theoretic view on this structure, with $0$ \cite{fiore2006remarks}. \end{itemize} \begin{notation}\label{not:notationsOfNaturalNumberRelatedSystems} We adopt the following notations: \begin{itemize} \item $\N$ denotes the set of all non-negative integers. Sometimes, we regard it as a poset with the natural ordering. \item $\Np$ denotes the set of all positive integers. We may regard it as a poset with the divisibility order. \end{itemize} \end{notation} \section{Riegs}\label{sec:riegs} \subsection{Preliminaries: rigs}\label{ssec:rigs} Since our theory of riegs is based on the theory of rigs ($=$ semirings), we start by recalling the notion of rigs. (The word \dq{rig} comes from \dq{ri\textbf{n}g without \textbf{n}egatives} \cite{schanuel1990negative}.) We only need the definition and a few examples. \begin{definition}[Rig]\label{def:rigs} A (possibly non-commutative) \demph{rig} is a set $R$ equipped with \begin{itemize} \item two constants ($=$ nullary operations) $0,1 \in R$ and \item two binary operations, $+, \ti \colon R \times R \to R$ \end{itemize} such that the following equations hold for all $x,y,z \in R$: % \footnote{some of which might be redundant.} \begin{enumerate} \item $0+x=x$, % \item $x+0=x$, \item $(x+y)+z=x+(y+z)$, \item $x+y=y+x$, \item $1\ti x =x$, \item $x\ti 1 =x$, \item $(x\ti y)\ti z=x\ti (y\ti z)$, % \item $x\ti y=y\ti x$, \item $x\ti 0=0$, \item $x\ti (y+z)=(x\ti y) + (x\ti z)$, \item $0\ti x=0$, and \item $(x+y)\ti z=(x\ti z)+(y\ti z)$. \end{enumerate} If $R$ satisfies an additional equation \begin{enumerate}[resume] \item $x\ti y = y\ti x$, \end{enumerate} we call it a \demph{commutative rig}. A \demph{rig homomorphism} is a function that preserves the four operations $0,1,+,\ti$. The category of rigs and rig homomorphisms is denoted by $\Rig$. \end{definition} For the sake of simplicity, we may write $xy$ for $x\ti y$. Let us provide three examples, each of which plays a specific role in what follows. \begin{example}[Rings]\label{exmp:RingsAreRigs} 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 (\Cref{prop:riegIsNotRing}). \end{example} \begin{example}[Rig of natural numbers]\label{exmp:RigOfNaturalNumbers} The rig of natural numbers (with the usual addition and multiplication) $\N$ is the initial object of the category $\Rig$. Its quotients will be the main subject of \Cref{sec:RiegsInFiniteAndProfiniteArithmetic}. \end{example} \begin{example}[Rig of endohomomorphisms on a commutative monoid]\label{exmp:EndRig} For a commutative monoid $(A, e, \ast)$, the set of monoid endohomomorphisms $\End(A, e, \ast)$ admits a rig structure as follows: \begin{itemize} \item The element $0 \in \End(A, e, \ast)$ is the constant function to the neutral element $A \to A\colon a \mapsto e$. \item The element $1 \in \End(A, e, \ast)$ is the identity function $\id_A\colon A \to A$. \item The sum $f+g$ of two elements $f,g\in \End(A, e, \ast)$ is given by $(f+g)(a) \coloneqq f(a) \ast g(a)$. (Here, we use the commutativity of $\ast$.) \item The product $f\ti g$ of two elements $f,g\in \End(A, e, \ast)$ is given by the composite $f\circ g$. \end{itemize} % This rig is typically non-commutative. For the additive monoid $(\N,0,{+})$, the rig $\End(\N,0,{+})$ is isomorphic to the rig of natural numbers $(\N, 0, 1, +, \ti)$. A rig of endohomomorphisms is, however, typically non-commutative; for the additive group $(\Z^2, 0, {+})$, the rig $\End(\Z^2,0,{+})$ is isomorphic to the ring $M_2(\Z)$ of $2 \ti 2$ matrices over $\Z$, which is not commutative. This is the example that we will use to define riegs (\Cref{def:rieg}). \end{example} % \begin{example} % The free rig generated by one element $x$ is the rig of polynomials with natural number coefficients $\N[x]$. % \end{example} % In what follows, we will write $xy$ for $$ \subsection{Definition}\label{ssec:definitionOfRiegs} This subsection aims to introduce the notion of riegs. Although it is possible to define riegs by familiar but numerous equations (\Cref{prop:EquationalDefinition}), we adopt another definition, which turns out to be surprisingly simple. % , which is much more memorable. Note that $\End(R, 1,\ti)$ in the definition below is the rig explained in \Cref{exmp:EndRig} obtained from the multiplicative commutative monoid $(R, 1,\ti)$. % We define the notion of `rieg', which is intended to be a rig with \textbf{e}xponentials, to be a commutative rig with a module structure on itself. \begin{definition}[Rieg]\label{def:rieg} A \demph{rieg} is a commutative rig $(R, 0, 1, +, \ti )$ equipped with a rig homomorphism $R \to \End(R, 1,\ti)$. \end{definition} At first glance, this definition may not seem to have anything to do with exponents. So let us unpack the definition into a sequence of equalities. The rig homomorphism $R \to \End(R, 1, \ti)$ sends an element $x\in R$ to a (commutative) monoid homomorphism, which will be denoted by \[ {-}^x \colon (R, 1, \ti) \to (R, 1, \ti). \] The condition that ${-}^x \colon R \to R$ is a monoid homomorphism is equivalent to the familiar equations \begin{itemize} \item $1^x=1$, and \item $(yz)^x = y^x z^x$. \end{itemize} For the function $R \to \End(R, 1, \ti)$ to be a rig homomorphism, it must preserve $0$, $1$, $+$, and $\ti$. Preservation of each operation corresponds to the equation listed in \Cref{table:riegequations}. \begin{table}[ht] \centering \begin{tabular}{c|c} \hline Preserved rig structure& The required equation\\ \hline $0$& $x^0 = 1$ \\ \hline $1$&$x^1 = x$ \\ \hline $+$& $x^{y+z} = x^y x^z$\\ \hline $\ti$&$x^{yz} = (x^z)^y$ \\ \hline \end{tabular} \caption{Four of the rieg equations} \label{table:riegequations} \end{table} % \begin{description} % \item[$0$] $x^0 = 1$ % \item [$1$] $x^1 = x$ % \item [$+$] $x^{y+z} = x^y x^z$ % \item [$\ti$] $x^{yz} = (x^z)^y$ % \end{description} Summarising the above observations, we obtain an equational definition of the notion of riegs. While it is longer than \Cref{def:rieg}, it consists only of familiar conditions. \begin{proposition}[Equational definition of riegs]\label{prop:EquationalDefinition} The definition of riegs (\Cref{def:rieg}) can be rephrased by the five operations: \begin{itemize} \item two constants ($=$ nullary operations), $0,1 \in R$, and \item three binary operations, $+, \ti, \ex\colon R\times R \to R$, \end{itemize} and fourteen equations: \begin{enumerate} \item $0+x=x$ \item $(x+y)+z=x+(y+z)$ \item $x+y=y+x$ \item $1 x =x$ \item $(x y) z=x (y z)$ \item $x y=y x$ \item $x 0 =0$ \item $x (y+z)=x y + x z$ \item $1 ^ x = 1$ \item $(yz)^x = y^x z^x$. \item $x ^ 0 = 1$ \item $x^ 1 = x$ \item $x^ {y+z} =x^ y x^ z$ \item $x^{y z} = (x^ z)^ y$, \end{enumerate} where $xy$ denotes $x\ti y$, and $x^y$ denotes $x\ex y$ as usual. \end{proposition} If we forget the constant $0$, these are exactly the eleven \dq{high school identities} of Tarski \cite{burris2005saga}. The other three equations, $0+x=x$, $x\ti 0 = 0$, and $x^0=1$, are the ones that involve $0$. \memo{Deferred (2026-07-25): Tarski never published the list himself, so there is no original paper to cite; \cite{burris2005saga} reports that the identities already occur in Dedekind's \emph{Was sind und was sollen die Zahlen?} (1888). Decide whether to add a footnote saying so, and whether it belongs here or in the introduction.} \begin{remark} \label{rmk:zerotozeroisone} As a special case of the equation $x ^ 0 = 1$, we have $0^0=1$. % In any rieg, we have % $0^0=1$. This convention will be repeatedly interpreted in many ways in this paper. % \memo{I can write its logical, categorical, ... interpretation.} \end{remark} % \memo{If $0^x=1$, then is $x$ zero? No, Heyting algebras} From this equational (or algebraic) definition, we can define the notion of rieg homomorphisms in the usual way. \begin{definition} A \demph{rieg homomorphism} is a function that preserves all (five) operations $0,1,+,\ti,\ex$. We write $\Rieg$ for the category of riegs. \end{definition} % Before we later turn to the sections on examples, As we will see numerous examples later, for now, we introduce only two trivial (but important!) examples of riegs: the initial object and the terminal object in the category of riegs. % The basic example is, of course, the rieg of natural numbers: \begin{example}[The initial rieg: natural numbers] \label{exmp:TheInitialRiegOfNaturalNumbers} The set of all natural numbers $\N = \{0,1, 2, \dots\}$ equipped with the usual zero $0$, one $1$, addition $+$, multiplication $\ti$, and exponentiation $\ex$, forms the rieg of natural numbers $\N$. Here are a few remarks about this example: \begin{itemize} \item This rieg $\N$ is an initial object in the category $\Rieg$. Indeed, for a rieg $R$, the unique rig homomorphism $\phi \colon \N \to R$ automatically preserves $\ex$: for $n,m \in \N$, the equations $x^{y+z} = x^y x^z$, $x^1=x$, and $x^0=1$ give $\phi(n)^{\phi(m)} = \phi(n)^{1+\dots+1} = \phi(n) \cdots \phi(n) = \phi(n^m)$, where both products have $m$ factors. \item This is the unique rieg structure on the rig of natural numbers, since $\N$ is the initial rig (\Cref{exmp:RigOfNaturalNumbers}) and a rieg structure is given by a rig homomorphism $\N \to \End(\N, 1, \ti)$. \item We adopt the convention that $0^0 = 1$ (see \Cref{rmk:zerotozeroisone}). \end{itemize} \end{example} \begin{example}[The degenerate rieg] \label{exmp:ThedegenerateRieg} A singleton $\{*\}$ admits exactly one rieg structure, which we call the \demph{degenerate rieg} $\1$. The degenerate rieg is a terminal object of the category $\Rieg$. \end{example} \subsection{Digression: Why rigs, not rings?} The reader may wonder: why do we develop our theory using rigs, even though rings are so famous and successful? There are several possible answers, but perhaps the simplest is that subtraction and exponentiation are fundamentally incompatible---if we have subtraction, then we have to give a meaning to $0^{-1}$! \begin{claim}\label{clm:AdditiveInverseOfOne} If a rieg $R$ contains an additive inverse $-1$ of $1$, then it is degenerate, that is, $R\cong\1$ (cf. \Cref{exmp:ThedegenerateRieg}). \end{claim} \begin{proof} We have the equation $ 1=0^0=0^{1+(-1)}=0^{1}\ti 0^{-1}=0 \ti 0^{-1}=0. $ This implies that every element $r\in R$ is equal to $0$, since $r= r\ti 1 = r\ti 0 =0$. \end{proof} \begin{proposition}[No rieg is a ring]\label{prop:riegIsNotRing} If a rieg $R$ is a ring, then it is degenerate, that is, $R\cong \1$. % No rieg is a ring unless it is the degenerate rieg $\1$. \end{proposition} \begin{proof} % Let $R$ be a rieg that is also a ring. % % If (the underlying rig of) the rieg $R$ is a ring, % Then % w A ring contains an additive inverse of $1$, so \Cref{clm:AdditiveInverseOfOne} applies. \end{proof} \begin{remark}\label{rmk:Meadow} A similar problem appears for division, and there we have a solution. A \demph{meadow} is a commutative ring with a total inverse operation, and its axioms imply $0^{-1}=0$ \cite{bergstra2009meadows}. 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 \ti 0^{-1} = 0$, and the proof of \Cref{clm:AdditiveInverseOfOne} still gives $1=0$. \end{remark} For example, exponentiation can be defined on the rig $\N$ % (which is the decategorification of finite sets) , but it is impossible on the ring $\Z$ (\Cref{prop:riegIsNotRing}). To the best of the author’s understanding, one reason why exponential structures---despite being present in many mathematical objects---have not received the attention they perhaps deserve is that the process of decategorification often involves introducing formal subtraction. For example, the ring of integers $\Z$ is obtained by introducing a formal subtraction to $\N$, which inherently admits the exponential structure of the cartesian closed category $\FinSet$ (\Cref{sec:CategoryAndEnumerations}). This subtraction does help clarify theories (sometimes by reducing the amount of information), but at the same time, it forces us to entirely forget the exponential structure. \section{Example 1: Riegs in finite and profinite arithmetic}\label{sec:RiegsInFiniteAndProfiniteArithmetic} \subsection{Rieg theoretic phenomena} Before delving into the technical details, let us first take a look at a few phenomena that will be studied in the rest of this section. % % {Modular arithmetic with exponentials} \subsubsection{Phenomenon 1: modular arithmetic with exponentials}\label{sssec:FiniteArithmetic} Let us consider the following high school level problem from elementary number theory, which involves exponentiation. % can be solved by modular arithmetic: \begin{puzzle} Find all pairs of natural numbers $(n,m)$ such that \[2^n +5 =m^2.\] \end{puzzle} \begin{answer} Consider the equation modulo $8$. If $n \geq 3$, the equation is simplified to \[ 5 \equiv m^2 \mod 8. \] % then $2^n \equiv 0 \pmod{8}$, so the left-hand side is congruent to $5 \pmod{8}$. However, since the quadratic residues modulo $8$ are $0$, $1$, and $4$, % so $m^2 \equiv 5 \pmod{8}$ 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)$. \end{answer} In this example, when considering exponentiation modulo $8$, we have to set aside the \dq{first exceptions}, namely the three numbers $n=0,1,2$. \subsubsection{Phenomenon 2: Profinite dynamical systems with exponentials}\label{sssec:ProiniteArithmeticDynamicalSystems} Let us consider the following puzzle. \begin{puzzle}[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$. \end{puzzle} There is a surprisingly simple way to obtain the solution --- namely, iteration! First, take an arbitrary natural number $n$, say $n=2024$. Then, repeatedly replace $n$ by the last four digits of $3^n$\footnote{Thanks to the repeated squaring algorithm, a computer can conduct this calculation in a short time. }. \begin{itemize} \item $3^{2024} \equiv 6481$ \item $3^{6481} \equiv 6803$ \item $3^{6803} \equiv 2027$ \item $3^{2027} \equiv 4987$ \item $3^{4987} \equiv 9387$ \item $3^{9387} \equiv 5387$ \item $3^{5387} \equiv 5387$ \end{itemize} % \begin{itemize} % \item % \begin{itemize} % \item $3^{2024} \equiv 6481$ % \item $3^{6481} \equiv 6803$ % \item $3^{6803} \equiv 2027$ % \item $3^{2027} \equiv 4987$ % \item $3^{4987} \equiv 9387$ % \item $3^{9387} \equiv 5387$ % \item $3^{5387} \equiv 5387$ % \end{itemize} % \item We obtain an answer $n=5387$. % \end{itemize} We obtain an answer $n=5387$. \begin{answer} $n=5387$ is the only answer. \end{answer} Then, it is natural to ask whether we can go farther: \begin{question}\label{q:ThreeToTheNDigits} Is there an infinite sequence of decimal digits \[\dots a_4 a_3 a_2 a_1\] such that, for every integer $k \geq 1$, the truncation $n_k \coloneqq \sum_{i=1}^{k} a_i 10^{i-1}$ satisfies the congruence \[ 3^{n_k} \equiv n_k \pmod{10^k}? \] \end{question} The answer is Yes! (See \Cref{fig:PictureListOfthreetotheN}) \begin{figure}[ht] \centering \begin{shaded} \begin{align*} 3^{87} &\equiv 87 \mod{100}\\ 3^{387} &\equiv 387 \mod{1000}\\ 3^{5387} &\equiv 5387 \mod{10000}\\ 3^{95387} &\equiv 95387 \mod{100000}\\ 3^{195387} &\equiv 195387 \mod{1000000}\\ 3^{4195387} &\equiv 4195387 \mod{10000000}\\ 3^{64195387} &\equiv 64195387 \mod{100000000}\\ 3^{464195387} &\equiv 464195387 \mod{1000000000}\\ &\vdots \end{align*} \caption{The unique solution of $3^n=n \mod{10^k}$ for each $k\geq 2$} \label{fig:PictureListOfthreetotheN} \end{shaded} \end{figure} \begin{remark}[Attribution]\label{rmk:ThreeToTheNAttribution} The affirmative answer is not new. It is a special case of a theorem of Jim\'enez Urroz and Yebra \cite[Theorem 3]{jimenez2009equation}: for every \demph{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 \pmod{b^{n}}$ for all sufficiently large $n$. The base $b=10$ is valid, and our digit sequence is recorded as \cite{OEIS_A133613}, known there as the final digits of Graham's number; the truncations displayed in \Cref{fig:PictureListOfthreetotheN} form \cite{OEIS_A183613}. What rieg theory adds is not the statement but a conceptual proof: the sequence is the unique fixed point of the contraction $3^{x}$ (\Cref{prop:FixedPointOfThreeToTheX}). \end{remark} % For any $k>1$ \memo{$k=1$ is also fine}, there is a unique $k$-digits natural number $n$ such that the last $k$-digits of $3^n$ are equal to $n$. This phenomenon is reminiscent of $p$-adic integers. Indeed, the stabilization of the digits of an iterated exponential (or \demph{tower}) modulo a fixed number is classically known, and is even used as a computational tool \cite{hittmeir2020reduction}. However, in this case, the exponential operation is involved not only as an iteration of a fixed function but as a binary operation on the number system itself. In this section, we will construct profinite systems of numbers, which can be regarded as $p$-adic number systems with exponentials. Using that structure, we will be able to answer the above question easily. The rough sketch of our proof is as follows: \begin{answer}[Rough sketch] % In a topological rieg $\Mr{\infty}{10^\infty}$, the sequence % \[(3 \powow 1) =3, (3 \powow 2) =3^3, (3 \powow 3) =3^{3^3}, (3 \powow 4) =3^{3^{3^3}}, \dots\] % converges to an element $(3 \powow \infty) \in \Mr{\infty}{10^\infty}$. In a topological rieg $\Mr{\infty}{10^\infty}$ (\Cref{def:TenAdicRieg}), we can take the limit $\alpha$ of the sequence \[3, 3^3, 3^{3^3}, 3^{3^{3^3}}, 3^{3^{3^{3^3}}} \dots \to \alpha.\] % converges to an element $\alpha \in \Mr{\infty}{10^\infty}$. By the continuity of $3^x \colon \Mr{\infty}{10^\infty} \to \Mr{\infty}{10^\infty}$, we have $3^ \alpha = \alpha$. \end{answer} Furthermore, the fixed point $\alpha$ turns out to be unique, which explains why the iteration in the above puzzle reaches the same answer regardless of the starting value: we will later regard $3^x$ as a contraction with respect to a natural metric and apply the Banach fixed-point theorem (\Cref{prop:FixedPointOfThreeToTheX}). \subsubsection{Phenomenon 3: Well-defined modulo exponentials}\label{sssec:Well-definedModuloExponentials} Let us conclude this subsection by introducing the fact that first attracted the author to riegs. As far as the author knows, it was originally proven by Burris and Lee \cite{burris1992small, burris1993tarski}. It is well-known that the addition and multiplications of natural numbers (or even of integers) are well-defined modulo $n$, for any positive integer $n\in \N$. It is just saying that $\Z/n\Z$ is a well-defined ring. But how about exponentials? \begin{puzzle} Find all positive integer $n>0$ such that, for any positive integers $a,b,a', b'$, we have \[ (a\equiv a' \mod n) \land (b\equiv b' \mod n) \implies (a^b\equiv {a'}^{b'} \mod n). \] \end{puzzle} For the obvious reason, $n=1$ satisfies the condition. Since a (positive) power of an odd (resp. even) number is odd (resp. even), $n=2$ also satisfies the condition. However, $n=3$ does not, since we have a counter example $2^1 \equiv 2 \not \equiv 1 \equiv 2^{1+3}$. \begin{answer}[A special case of \cite{burris1992small, burris1993tarski}] There are exactly $5$ possibilities: $n=1,2,6,42,1806$ \end{answer} % $1,2,6,42,1806$ \subsection{Finite arithmetic: the Burris-Lee theorem} Ordinary modular arithmetic remembers only a residue. Exponentiation also needs a finite initial part in which small exponents remain distinct. The result is a finite arithmetic with a tail followed by a cycle. \subsubsection{The Burris--Lee classification} \begin{definition}[$\Mr{a}{b}$]\label{def:QuotientRigMrab} For a natural number $a\geq 0$ and a positive integer $b>0$, let $\Mr{a}{b}$ be the $(a+b)$-element quotient $\N/{\sim_{a,b}}$, where \[n \sim_{a,b} m \iff (n=m)\lor ((n,m\geq a) \land (n\equiv m \mod{b})). \] Thus the numbers below $a$ form the initial exceptional part, and the numbers from $a$ onward repeat with period $b$. \end{definition} \Cref{fig:ModuleRieg} shows this tail--cycle picture for $\Mr{3}{4}$. \begin{figure}[ht] \begin{shaded} \centering \begin{tikzpicture} [scale = 2] \fill[black] (0,2) circle (0.06) node[above]{}; \fill[black] (1,2) circle (0.06) node[above]{}; \fill[black] (2,2) circle (0.06) node[above]{}; \fill[black] (3,2) circle (0.06) node[above]{}; \fill[black] (4-0.36,1+0.36) circle (0.06) node[above]{}; \fill[black] (3,0+0.36+0.36) circle (0.06) node[above]{}; \fill[black] (2+0.36,1+0.36) circle (0.06) node[above]{}; \draw[black, thick](3,1+0.36) circle (0.64); \draw[black, thick] (0,2) -- (3,2); \end{tikzpicture} \caption{$\Mr{3}{4}$} \label{fig:ModuleRieg} \end{shaded} \end{figure} By \cite[Proposition 3.6]{burris1992small}, every finite quotient of the positive integers has this tail--cycle form. The same paper determines exactly when exponentiation descends to it. \begin{theorem}[Burris--Lee {\cite[Theorem 3.12]{burris1992small}}]\label{thm:BurrisLeeTheorem} For $a\geq 0$ and $b>0$, the canonical operations descend from $\N$ to $\Mr{a}{b}$ if and only if, for every prime $p$ and every positive integer $e$, \[ p^e\mid b\Longrightarrow e\leq a, \qquad p\mid b\Longrightarrow p-1\mid b. \] \end{theorem} Burris and Lee work with the positive integers and the language $\{+,\ti,\ex,1\}$.\footnote{For $a\geq1$, their algebra $N_{a,b}$ is the positive part of $\Mr{a}{b}$. Adjoining a distinct $0$ adds only the forced rules for $0$, so it adds no new condition. For $a=0$, the displayed conditions force $b=1$, which gives the degenerate rieg.} \subsubsection{Examples and the five cyclic models} \begin{example}[The rieg of truth values]\label{exmp:RiegOfTruthValues} The quotient $\Mr{1}{1}$ is the rieg of truth values $\2=\{\bot,\top\}$ from \Cref{sec:RiegsInLogic}. \end{example} \begin{example}[Parity rieg]\label{exmp:ParityRieg} The quotient $\Mr{1}{2}$ is \[ \{0,\ \text{positive odd},\ \text{positive even}\}, \] which we call the \demph{parity rieg}. Keeping $0$ separate is essential: exponentiation does not descend to $\Z/2\Z$, since $2^0$ is odd but $2^2$ is even. \end{example} \begin{example}[Overflow riegs]\label{exmp:OverflowRiegs} For $n\geq0$, the quotient $\Mr{n}{1}$ is the \demph{overflow rieg with threshold $n$}, denoted by $\OF_n$. Its elements are $0,1,\dots,n-1,\TB$, where every natural number at least $n$ is sent to $\TB$. \end{example} The theorem gives all finite quotient riegs at once. \Cref{fig:PlotsOfQuotientRiegsOfN,PictureListOfModuloRiegs} keep their distribution visible. \begin{figure} \centering \begin{shaded} \begin{tikzpicture} \begin{axis}[ width=14cm, height=18cm, xlabel={$a$}, ylabel={$b$}, ymin=1, ymax=130, xmin=0, xmax=10, xtick={0,...,10}, ytick={1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 42, 48, 54, 60, 64, 72, 80, 84, 96, 100, 108, 120, 126, 128}, axis on top, enlargelimits=false, grid=major, tick label style={font=\small}, label style={font=\small} ] % points \addplot[ only marks, mark=square*, mark size=1pt, color=black ] coordinates { (0,1) (1,1) (1,2) (1,6) (1,42) (2,1) (2,2) (2,4) (2,6) (2,12) (2,18) (2,20) (2,36) (2,42) (2,60) (2,84) (2,100) (2,126) (3,1) (3,2) (3,4) (3,6) (3,8) (3,12) (3,18) (3,20) (3,24) (3,36) (3,40) (3,42) (3,54) (3,60) (3,72) (3,84) (3,100) (3,108) (3,120) (3,126) (4,1) (4,2) (4,4) (4,6) (4,8) (4,12) (4,16) (4,18) (4,20) (4,24) (4,36) (4,40) (4,42) (4,48) (4,54) (4,60) (4,72) (4,80) (4,84) (4,100) (4,108) (4,120) (4,126) (5,1) (5,2) (5,4) (5,6) (5,8) (5,12) (5,16) (5,18) (5,20) (5,24) (5,32) (5,36) (5,40) (5,42) (5,48) (5,54) (5,60) (5,72) (5,80) (5,84) (5,96) (5,100) (5,108) (5,120) (5,126) (6,1) (6,2) (6,4) (6,6) (6,8) (6,12) (6,16) (6,18) (6,20) (6,24) (6,32) (6,36) (6,40) (6,42) (6,48) (6,54) (6,60) (6,64) (6,72) (6,80) (6,84) (6,96) (6,100) (6,108) (6,120) (6,126) (7,1) (7,2) (7,4) (7,6) (7,8) (7,12) (7,16) (7,18) (7,20) (7,24) (7,32) (7,36) (7,40) (7,42) (7,48) (7,54) (7,60) (7,64) (7,72) (7,80) (7,84) (7,96) (7,100) (7,108) (7,120) (7,126) (7,128) (8,1) (8,2) (8,4) (8,6) (8,8) (8,12) (8,16) (8,18) (8,20) (8,24) (8,32) (8,36) (8,40) (8,42) (8,48) (8,54) (8,60) (8,64) (8,72) (8,80) (8,84) (8,96) (8,100) (8,108) (8,120) (8,126) (8,128) (9,1) (9,2) (9,4) (9,6) (9,8) (9,12) (9,16) (9,18) (9,20) (9,24) (9,32) (9,36) (9,40) (9,42) (9,48) (9,54) (9,60) (9,64) (9,72) (9,80) (9,84) (9,96) (9,100) (9,108) (9,120) (9,126) (9,128) (10,1) (10,2) (10,4) (10,6) (10,8) (10,12) (10,16) (10,18) (10,20) (10,24) (10,32) (10,36) (10,40) (10,42) (10,48) (10,54) (10,60) (10,64) (10,72) (10,80) (10,84) (10,96) (10,100) (10,108) (10,120) (10,126) (10,128) }; \end{axis} \end{tikzpicture} \caption{Finite quotient riegs of $\N$ for small $a$ and $b$} \label{fig:PlotsOfQuotientRiegsOfN} \end{shaded} \end{figure} \begin{figure}[ht] \centering \begin{shaded} \begin{align*} a=0 &:\ \Mr{0}{1}\\ a=1 &:\ \Mr{1}{1},\Mr{1}{2},\Mr{1}{6},\Mr{1}{42},\Mr{1}{1806}\\ a=2 &:\ \Mr{2}{1},\Mr{2}{2},\Mr{2}{4},\Mr{2}{6},\Mr{2}{12},\Mr{2}{18},\Mr{2}{20},\Mr{2}{36},\Mr{2}{42},\Mr{2}{60},\Mr{2}{84},\dots \\ a=3 &:\ \Mr{3}{1},\Mr{3}{2},\Mr{3}{4},\Mr{3}{6},\Mr{3}{8},\Mr{3}{12},\Mr{3}{18},\Mr{3}{20},\Mr{3}{24},\Mr{3}{36},\Mr{3}{40}, \dots \\ a=4 &:\ \Mr{4}{1},\Mr{4}{2},\Mr{4}{4},\Mr{4}{6},\Mr{4}{8},\Mr{4}{12},\Mr{4}{16},\Mr{4}{18},\Mr{4}{20},\Mr{4}{24},\Mr{4}{36}, \dots \\ \vdots&\\ \dq{a=\infty}&:\ \N \end{align*} \caption{Finite quotient riegs of $\N$, arranged by $a$} \label{PictureListOfModuloRiegs} \end{shaded} \end{figure} When $a=1$, the positive part has no tail: its successor operation is a single cycle. Following \cite{alsulami2025cyclic}, we call such positive algebras \demph{cyclic models}. There are surprisingly few of them. \begin{corollary}[{\cite[Corollary 3.14]{burris1992small}, attributed there to D.~Higgs}]\label{CorollaryClassificationOfCharacteristics} The only finite quotient riegs of $\N$ with cyclic positive part are \[ \Mr{1}{1},\quad \Mr{1}{2},\quad \Mr{1}{6},\quad \Mr{1}{42},\quad \Mr{1}{1806}. \] \end{corollary} Equivalently, if a rieg $R$ has a least positive integer $n$ such that \[ 1=1+\underbrace{1+\dots+1}_{n}, \] then $n$ is one of $1,2,6,42,1806$. This is precisely the puzzle in \Cref{sssec:Well-definedModuloExponentials}; no separate calculation is needed here. \begin{example} The number $8=2^3$ satisfies both conditions in \Cref{thm:BurrisLeeTheorem} with $a=3$. Hence $\Mr{3}{8}$ is a rieg. This is exactly the finite arithmetic used in the high-school calculation of \Cref{sssec:FiniteArithmetic}. \end{example} \begin{example}\label{exmp:TenPowerN} The number $10$ fails the second Burris--Lee condition, since $5\mid10$ but $4\nmid10$. For every $n\geq2$, however, $10^n=2^n5^n$ and $4\mid10^n$, so $\Mr{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~\ref{def:TenAdicRieg}). \end{example} \subsubsection{Characteristics of riegs} Recall that the characteristic of a ring $R$ is the smallest positive integer $n$ such that $0 = \underbrace{1 + 1 + \dots + 1}_{n \text{ times}}$, if such an $n$ exists; otherwise, the characteristic is defined to be $0$. For quotient rigs and riegs, we need to record both the beginning of the cycle and its period. We order $\N\times\Np$ by \[ (a,b)\leq(a',b')\quad\Longleftrightarrow\quad a\leq a'\text{ and }b\mid b'. \] \begin{definition}[Characteristic]\label{def:CharacteristicOfRigsAndRiegs} The \demph{characteristic} of a rig or rieg $R$, denoted by $\ch R$, is the minimum pair $(a,b)\in\N\times\Np$ such that \[ \underbrace{1+\dots +1}_{a \text{ times}}= \underbrace{1+\dots +1}_{a \text{ times}}+ \underbrace{1+\dots +1}_{b \text{ times}}, \] if it exists. Otherwise, we put $\ch R=\chz$, where $\chz$ is a formal maximum element. \end{definition} \begin{corollary}[Burris--Lee theorem in terms of rieg characteristics {\cite{burris1992small,burris1993tarski}}] A pair $(a,b)\in\N\times\Np$ is the characteristic of a rieg if and only if \[ p^e\mid b\Longrightarrow e\leq a, \qquad p\mid b\Longrightarrow p-1\mid b \] for every prime $p$ and every positive integer $e$. \end{corollary} \begin{remark}[Why this definition is natural] Let $R$ be a rig or rieg. Factor the unique homomorphism from the initial object as \[ \N\twoheadrightarrow\Image(\N\to R)\rightarrowtail R. \] If this image is finite, then it is $\Mr{a}{b}$ and $\ch R=(a,b)$. If the map $\N\to R$ is injective, then $\ch R=\chz$. 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 \Cref{clm:AdditiveInverseOfOne}. 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 \demph{characteristic} of $R$ in general. For rings, the initial algebra is $\Z$, the image is $\Z/n\Z$, and we recover the usual characteristic $n$. For riegs, the image is $\Mr{a}{b}$, and $\ch R=(a,b)$ is just a name for this quotient. \end{remark} \FloatBarrier \subsection{Profinite arithmetic: a total exponentiation} In this subsection, we take the profinite completion of the initial rieg $\N$ and describe it explicitly. Its underlying set turns out to be $\N\sqcup\proZ$. The main point is not that the exponentiation is total---this holds in every rieg by definition---but where it is total: although no non-degenerate ring admits a rieg structure (\Cref{prop:riegIsNotRing}), the completion contains the profinite ring $\proZ$, and the exponentiation $x^y$ is still defined for all pairs. \subsubsection{Profinite natural numbers with total exponentiation} For $\C=\Rig$ or $\Rieg$, let $\Quot_{\C}(\N)$ denote the poset of quotient $\C$-algebras of $\N$. We put $Q\leq Q'$ if there is a quotient map $Q'\twoheadrightarrow Q$ compatible with the maps from $\N$. Let $\FinQuot_{\C}(\N)$ denote its subposet of finite quotients. Thus we use four notations, which form a square of subposets of $\Quot_{\Rig}(\N)$: \[ \begin{tikzcd}[column sep=small, row sep=small] & \Quot_{\Rig}(\N) & \\ \Quot_{\Rieg}(\N) \ar[ru, hook] & & \FinQuot_{\Rig}(\N) \ar[lu, hook'] \\ & \FinQuot_{\Rieg}(\N) \ar[lu, hook] \ar[ru, hook'] & \end{tikzcd} \] Going down-left in the square imposes the arithmetic condition of \Cref{thm:BurrisLeeTheorem} (admitting a rieg structure); going down-right imposes finiteness. The smallest poset $\FinQuot_{\Rieg}(\N)$, placed at the bottom, satisfies both conditions. Every finite quotient rig is of the form $\Mr{a}{b}$. The finite quotient riegs are the ones that satisfy \Cref{thm:BurrisLeeTheorem}, and $\N$ is the maximum element of each full quotient poset. For two finite quotients, the order is \[ \Mr{a}{b}\leq\Mr{a'}{b'} \quad\Longleftrightarrow\quad a\leq a'\text{ and }b\mid b'. \] Recall that the profinite completion of an algebraic structure is the limit of its finite quotient algebras (\Cref{ssec:GeneralTheoryOfProfiniteAlgebras}). \begin{definition} The \demph{rieg of profinite natural numbers} $\proN$ is the profinite completion of the initial rieg $\N$. \end{definition} Thus \[ \proN \coloneqq \lim\left(\FinQuot_{\Rieg}(\N)^{\op}\to\Rieg\right). \] \begin{lemma}\label{lem:SimplifyingWithFactorial} The quotient rieg $\Mr{n}{n!}$ exists for every $n\in\N$. Moreover, the family \[ \{\Mr{n}{n!}\mid n\in\N\} \] is cofinal in $\FinQuot_{\Rieg}(\N)$. \end{lemma} \begin{proof} Suppose that $p$ is prime and that $p^e\mid n!$, where $e$ is maximal. Counting the factors divisible by $p^k$ gives \[ e = \sum_{k=1}^{\infty} \left\lfloor {\frac{n}{p^k}}\right\rfloor \leq \sum_{k=1}^{\infty} \frac{n}{p^k} =\frac{n}{p-1} \leq n. \] Moreover, if $p\mid n!$, then $p\leq n$, so $p-1$ divides $n!$. Thus $\Mr{n}{n!}$ is a rieg by \Cref{thm:BurrisLeeTheorem}. Now let $\Mr{a}{b}$ be a finite quotient rieg and take $n=\max(a,b)$. Then $a\leq n$ and $b\mid n!$, so \[ \Mr{a}{b}\leq\Mr{n}{n!}. \] This proves cofinality. \end{proof} \begin{proposition}\label{prop:profiniteInteger} The profinite rieg $\proN$ is the limit of the following diagram. \[ \begin{tikzcd} % \proN \cdots \ar[r, twoheadrightarrow , "\pi_4"]& \Mr{3}{3!}\ar[r, twoheadrightarrow, "\pi_3"] & \Mr{2}{2!}\ar[r, twoheadrightarrow, "\pi_2"] & \Mr{1}{1!}\ar[r, twoheadrightarrow, "\pi_1"] & \Mr{0}{0!} \end{tikzcd} \] \end{proposition} \begin{proof} By \Cref{lem:SimplifyingWithFactorial}, the order-preserving functor \[ \N\longrightarrow\FinQuot_{\Rieg}(\N), \qquad n\longmapsto\Mr{n}{n!}, \] is final. Therefore, it gives the same limit. \end{proof} \begin{theorem}[The underlying set of $\proN$]\label{thm:UnderlyingSetOfProfiniteRieg} The underlying set of $\proN$ is \[ \proN = \N \sqcup \proZ, \] where $\proZ$ denotes the usual set of profinite integers. The canonical projection $\pi_{a,b}\colon \proN \to \Mr{a}{b}$ restricts to the canonical maps \[ \N \twoheadrightarrow \Mr{a}{b} \] and \[ \proZ \twoheadrightarrow \Z/b\Z \rightarrowtail \Mr{a}{b}. \] \end{theorem} \begin{proof} By \Cref{prop:profiniteInteger,lem:LimitsofTopologicalAlgebras}, an element of $\proN$ is a compatible sequence \[ (x_n\in\Mr{n}{n!})_{n\geq0}. \] Suppose that one coordinate is an exceptional element $kk),\\ [k] &(m\leq k). \end{cases} \] Hence the sequence comes from the natural number $k$. Otherwise, every coordinate belongs to the modular part \(\Z/n!\Z\subset\Mr{n}{n!}\), so the sequence is an element of \[ \proZ=\lim_n\Z/n!\Z. \] Conversely, every element of $\N$ and every element of $\proZ$ gives a compatible sequence of the indicated form. \end{proof} \begin{figure}[htbp] \centering \begin{tikzpicture}[x=12cm, y=-0.8cm] \fill[black!60] (0.0000,0) rectangle (1.0000,0.3); \fill[black!60] (0.0000,1) rectangle (0.4000,1.3); \fill[black!60] (0.6000,1) rectangle (1.0000,1.3); \fill[black!60] (0.0000,2) rectangle (0.1067,2.3); \fill[black!60] (0.1467,2) rectangle (0.2533,2.3); \fill[black!60] (0.2933,2) rectangle (0.4000,2.3); \fill[black!60] (0.6000,2) rectangle (0.7067,2.3); \fill[black!60] (0.7467,2) rectangle (0.8533,2.3); \fill[black!60] (0.8933,2) rectangle (1.0000,2.3); \fill[black!60] (0.0000,3) rectangle (0.0213,3.3); \fill[black!60] (0.0284,3) rectangle (0.0498,3.3); \fill[black!60] (0.0569,3) rectangle (0.0782,3.3); \fill[black!60] (0.0853,3) rectangle (0.1067,3.3); \fill[black!60] (0.1467,3) rectangle (0.1680,3.3); \fill[black!60] (0.1751,3) rectangle (0.1964,3.3); \fill[black!60] (0.2036,3) rectangle (0.2249,3.3); \fill[black!60] (0.2320,3) rectangle (0.2533,3.3); \fill[black!60] (0.2933,3) rectangle (0.3147,3.3); \fill[black!60] (0.3218,3) rectangle (0.3431,3.3); \fill[black!60] (0.3502,3) rectangle (0.3716,3.3); \fill[black!60] (0.3787,3) rectangle (0.4000,3.3); \fill[black!60] (0.6000,3) rectangle (0.6213,3.3); \fill[black!60] (0.6284,3) rectangle (0.6498,3.3); \fill[black!60] (0.6569,3) rectangle (0.6782,3.3); \fill[black!60] (0.6853,3) rectangle (0.7067,3.3); \fill[black!60] (0.7467,3) rectangle (0.7680,3.3); \fill[black!60] (0.7751,3) rectangle (0.7964,3.3); \fill[black!60] (0.8036,3) rectangle (0.8249,3.3); \fill[black!60] (0.8320,3) rectangle (0.8533,3.3); \fill[black!60] (0.8933,3) rectangle (0.9147,3.3); \fill[black!60] (0.9218,3) rectangle (0.9431,3.3); \fill[black!60] (0.9502,3) rectangle (0.9716,3.3); \fill[black!60] (0.9787,3) rectangle (1.0000,3.3); \fill[black!60] (0.0000,4) rectangle (0.0034,4.3); \fill[black!60] (0.0045,4) rectangle (0.0079,4.3); \fill[black!60] (0.0090,4) rectangle (0.0124,4.3); \fill[black!60] (0.0134,4) rectangle (0.0169,4.3); \fill[black!60] (0.0179,4) rectangle (0.0213,4.3); \fill[black!60] (0.0284,4) rectangle (0.0319,4.3); \fill[black!60] (0.0329,4) rectangle (0.0363,4.3); \fill[black!60] (0.0374,4) rectangle (0.0408,4.3); \fill[black!60] (0.0419,4) rectangle (0.0453,4.3); \fill[black!60] (0.0464,4) rectangle (0.0498,4.3); \fill[black!60] (0.0569,4) rectangle (0.0603,4.3); \fill[black!60] (0.0614,4) rectangle (0.0648,4.3); \fill[black!60] (0.0658,4) rectangle (0.0693,4.3); \fill[black!60] (0.0703,4) rectangle (0.0737,4.3); \fill[black!60] (0.0748,4) rectangle (0.0782,4.3); \fill[black!60] (0.0853,4) rectangle (0.0887,4.3); \fill[black!60] (0.0898,4) rectangle (0.0932,4.3); \fill[black!60] (0.0943,4) rectangle (0.0977,4.3); \fill[black!60] (0.0988,4) rectangle (0.1022,4.3); \fill[black!60] (0.1033,4) rectangle (0.1067,4.3); \fill[black!60] (0.1467,4) rectangle (0.1501,4.3); \fill[black!60] (0.1511,4) rectangle (0.1546,4.3); \fill[black!60] (0.1556,4) rectangle (0.1590,4.3); \fill[black!60] (0.1601,4) rectangle (0.1635,4.3); \fill[black!60] (0.1646,4) rectangle (0.1680,4.3); \fill[black!60] (0.1751,4) rectangle (0.1785,4.3); \fill[black!60] (0.1796,4) rectangle (0.1830,4.3); \fill[black!60] (0.1841,4) rectangle (0.1875,4.3); \fill[black!60] (0.1886,4) rectangle (0.1920,4.3); \fill[black!60] (0.1930,4) rectangle (0.1964,4.3); \fill[black!60] (0.2036,4) rectangle (0.2070,4.3); \fill[black!60] (0.2080,4) rectangle (0.2114,4.3); \fill[black!60] (0.2125,4) rectangle (0.2159,4.3); \fill[black!60] (0.2170,4) rectangle (0.2204,4.3); \fill[black!60] (0.2215,4) rectangle (0.2249,4.3); \fill[black!60] (0.2320,4) rectangle (0.2354,4.3); \fill[black!60] (0.2365,4) rectangle (0.2399,4.3); \fill[black!60] (0.2410,4) rectangle (0.2444,4.3); \fill[black!60] (0.2454,4) rectangle (0.2489,4.3); \fill[black!60] (0.2499,4) rectangle (0.2533,4.3); \fill[black!60] (0.2933,4) rectangle (0.2967,4.3); \fill[black!60] (0.2978,4) rectangle (0.3012,4.3); \fill[black!60] (0.3023,4) rectangle (0.3057,4.3); \fill[black!60] (0.3068,4) rectangle (0.3102,4.3); \fill[black!60] (0.3113,4) rectangle (0.3147,4.3); \fill[black!60] (0.3218,4) rectangle (0.3252,4.3); \fill[black!60] (0.3263,4) rectangle (0.3297,4.3); \fill[black!60] (0.3307,4) rectangle (0.3342,4.3); \fill[black!60] (0.3352,4) rectangle (0.3386,4.3); \fill[black!60] (0.3397,4) rectangle (0.3431,4.3); \fill[black!60] (0.3502,4) rectangle (0.3536,4.3); \fill[black!60] (0.3547,4) rectangle (0.3581,4.3); \fill[black!60] (0.3592,4) rectangle (0.3626,4.3); \fill[black!60] (0.3637,4) rectangle (0.3671,4.3); \fill[black!60] (0.3681,4) rectangle (0.3716,4.3); \fill[black!60] (0.3787,4) rectangle (0.3821,4.3); \fill[black!60] (0.3831,4) rectangle (0.3866,4.3); \fill[black!60] (0.3876,4) rectangle (0.3910,4.3); \fill[black!60] (0.3921,4) rectangle (0.3955,4.3); \fill[black!60] (0.3966,4) rectangle (0.4000,4.3); \fill[black!60] (0.6000,4) rectangle (0.6034,4.3); \fill[black!60] (0.6045,4) rectangle (0.6079,4.3); \fill[black!60] (0.6090,4) rectangle (0.6124,4.3); \fill[black!60] (0.6134,4) rectangle (0.6169,4.3); \fill[black!60] (0.6179,4) rectangle (0.6213,4.3); \fill[black!60] (0.6284,4) rectangle (0.6319,4.3); \fill[black!60] (0.6329,4) rectangle (0.6363,4.3); \fill[black!60] (0.6374,4) rectangle (0.6408,4.3); \fill[black!60] (0.6419,4) rectangle (0.6453,4.3); \fill[black!60] (0.6464,4) rectangle (0.6498,4.3); \fill[black!60] (0.6569,4) rectangle (0.6603,4.3); \fill[black!60] (0.6614,4) rectangle (0.6648,4.3); \fill[black!60] (0.6658,4) rectangle (0.6693,4.3); \fill[black!60] (0.6703,4) rectangle (0.6737,4.3); \fill[black!60] (0.6748,4) rectangle (0.6782,4.3); \fill[black!60] (0.6853,4) rectangle (0.6887,4.3); \fill[black!60] (0.6898,4) rectangle (0.6932,4.3); \fill[black!60] (0.6943,4) rectangle (0.6977,4.3); \fill[black!60] (0.6988,4) rectangle (0.7022,4.3); \fill[black!60] (0.7033,4) rectangle (0.7067,4.3); \fill[black!60] (0.7467,4) rectangle (0.7501,4.3); \fill[black!60] (0.7511,4) rectangle (0.7546,4.3); \fill[black!60] (0.7556,4) rectangle (0.7590,4.3); \fill[black!60] (0.7601,4) rectangle (0.7635,4.3); \fill[black!60] (0.7646,4) rectangle (0.7680,4.3); \fill[black!60] (0.7751,4) rectangle (0.7785,4.3); \fill[black!60] (0.7796,4) rectangle (0.7830,4.3); \fill[black!60] (0.7841,4) rectangle (0.7875,4.3); \fill[black!60] (0.7886,4) rectangle (0.7920,4.3); \fill[black!60] (0.7930,4) rectangle (0.7964,4.3); \fill[black!60] (0.8036,4) rectangle (0.8070,4.3); \fill[black!60] (0.8080,4) rectangle (0.8114,4.3); \fill[black!60] (0.8125,4) rectangle (0.8159,4.3); \fill[black!60] (0.8170,4) rectangle (0.8204,4.3); \fill[black!60] (0.8215,4) rectangle (0.8249,4.3); \fill[black!60] (0.8320,4) rectangle (0.8354,4.3); \fill[black!60] (0.8365,4) rectangle (0.8399,4.3); \fill[black!60] (0.8410,4) rectangle (0.8444,4.3); \fill[black!60] (0.8454,4) rectangle (0.8489,4.3); \fill[black!60] (0.8499,4) rectangle (0.8533,4.3); \fill[black!60] (0.8933,4) rectangle (0.8967,4.3); \fill[black!60] (0.8978,4) rectangle (0.9012,4.3); \fill[black!60] (0.9023,4) rectangle (0.9057,4.3); \fill[black!60] (0.9068,4) rectangle (0.9102,4.3); \fill[black!60] (0.9113,4) rectangle (0.9147,4.3); \fill[black!60] (0.9218,4) rectangle (0.9252,4.3); \fill[black!60] (0.9263,4) rectangle (0.9297,4.3); \fill[black!60] (0.9307,4) rectangle (0.9342,4.3); \fill[black!60] (0.9352,4) rectangle (0.9386,4.3); \fill[black!60] (0.9397,4) rectangle (0.9431,4.3); \fill[black!60] (0.9502,4) rectangle (0.9536,4.3); \fill[black!60] (0.9547,4) rectangle (0.9581,4.3); \fill[black!60] (0.9592,4) rectangle (0.9626,4.3); \fill[black!60] (0.9637,4) rectangle (0.9671,4.3); \fill[black!60] (0.9681,4) rectangle (0.9716,4.3); \fill[black!60] (0.9787,4) rectangle (0.9821,4.3); \fill[black!60] (0.9831,4) rectangle (0.9866,4.3); \fill[black!60] (0.9876,4) rectangle (0.9910,4.3); \fill[black!60] (0.9921,4) rectangle (0.9955,4.3); \fill[black!60] (0.9966,4) rectangle (1.0000,4.3); \end{tikzpicture} \caption{$\proZ$ as limits of $\Z/n!\Z$} \end{figure} \begin{corollary}[The unique continuous extension of exponentiation]\label{cor:TotalExponentiationOnProfiniteN} The exponentiation of $\N$ extends to a continuous operation \[ (-)^{(-)}\colon\proN\times\proN\longrightarrow\proN \] defined for all pairs of elements, and such a continuous extension is unique. \end{corollary} \begin{proof} The limit defining $\proN$ is taken in the category of topological riegs. Hence its operations, including exponentiation, are defined coordinatewise and are continuous by \Cref{lem:LimitsofTopologicalAlgebras}. For the uniqueness, it suffices to show that the image of $\N$ is dense in $\proN$: then $\N\times\N$ has dense image in $\proN\times\proN$, and two continuous maps into the Hausdorff space $\proN$ that agree on a dense subset must coincide. By \Cref{prop:profiniteInteger}, every non-empty basic open subset of $\proN$ is the preimage of a non-empty subset $S\subseteq\Mr{n}{n!}$ under the projection $\proN\to\Mr{n}{n!}$ for some $n\in\N$. Since the composite $\N\twoheadrightarrow\Mr{n}{n!}$ is surjective, this preimage contains an element of $\N$. \end{proof} This is different from the usual $p$-adic exponentiation, which is not defined on all pairs in $\Z_p\times\Z_p$. In fact, a non-degenerate ring cannot be a rieg by \Cref{prop:riegIsNotRing}. The summand $\N$ in \Cref{thm:UnderlyingSetOfProfiniteRieg} is what makes $\proN$ different from a ring. By using a smaller diagram of finite quotient riegs, we obtain variants of $\proN$. The following one appeared in Phenomenon 2 (\Cref{sssec:ProiniteArithmeticDynamicalSystems}). \begin{definition}[The topological rieg of $10$-adic natural numbers]\label{def:TenAdicRieg} The \demph{topological rieg of $10$-adic natural numbers} $\Mr{\infty}{10^{\infty}}$ is the limit of the following diagram in the category of topological riegs: \[ \begin{tikzcd} \cdots \ar[r, twoheadrightarrow]& \Mr{4}{10^4}\ar[r, twoheadrightarrow] & \Mr{3}{10^3}\ar[r, twoheadrightarrow] & \Mr{2}{10^2}. \end{tikzcd} \] By \Cref{exmp:TenPowerN}, each $\Mr{n}{10^n}$ is a rieg for $n\geq2$. \end{definition} By the same argument as in \Cref{thm:UnderlyingSetOfProfiniteRieg}, the underlying set of $\Mr{\infty}{10^{\infty}}$ is given by \[ \Mr{\infty}{10^{\infty}} = \N \sqcup \Z_{10} = \N \sqcup (\Z_2 \times \Z_5), \] where $\Z_{10} \coloneqq \lim_{n} (\Z/10^n\Z) \cong \Z_2 \times \Z_5$ denotes the set of $10$-adic integers. \begin{remark}[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 \Cref{thm:BurrisLeeTheorem} fails. Hence the rig $\Mr{a}{5^n}$ admits no rieg structure for any $a$. In this sense, there is no topological rieg of \dq{$5$-adic natural numbers} $\N \sqcup \Z_5$ obtained in this way. \end{remark} \subsubsection{Contractive exponential dynamics} \begin{definition}[Carmichael function {\cite{carmichael1910note}}]\label{def:CarmichaelFunction} For a positive integer $n$, the \demph{Carmichael function} $\lambda(n)$ is the least positive integer $d$ such that \[ u^d\equiv1\pmod n \] for every $u\in(\Z/n\Z)^\times$. Equivalently, $\lambda(n)$ is the exponent of the group $(\Z/n\Z)^\times$. \end{definition} \begin{remark}[The jump function]\label{rmk:JumpFunction} With respect to the divisibility order, the Carmichael function has a right adjoint $\jump\colon\Np\to\Np$, whose notation $\lambda^{*}$ we borrow from \cite[Theorem 5.2(b)]{cameron2009primitive}. Thus \[ \lambda(b')\mid b \quad\Longleftrightarrow\quad b'\mid\jump(b). \] Therefore, $\jump(b)$ records the possible next periods $b'$ for which exponentiation raises the precision. \end{remark} \begin{lemma}[A metric for an inverse sequence]\label{lem:MetricForInverseSequence} Let \[ X=\lim\left(\cdots\twoheadrightarrow X_2\twoheadrightarrow X_1\twoheadrightarrow X_0\right) \] be an inverse limit of non-empty finite sets and surjective maps, where $X_0$ has one element. Write $\pi_n\colon X\to X_n$ for the projections. For distinct $x,y\in X$, let \[ \nu(x,y)=\max\{n\in\N\mid \pi_i(x)=\pi_i(y)\text{ for every }i\leq n\}, \] and put \[ d(x,y)=2^{-\nu(x,y)},\qquad d(x,x)=0. \] Then $(X,d)$ is a complete ultrametric space. Suppose that a map $F\colon X\to X$ satisfies \[ \pi_n(x)=\pi_n(y) \quad\Longrightarrow\quad \pi_{n+1}(F(x))=\pi_{n+1}(F(y)) \] for every $n\geq0$. Then $F$ is a contraction with Lipschitz constant $\frac12$. \end{lemma} \begin{proof} The ultrametric inequality follows because two elements that agree with a third element through level $n$ also agree with each other through level $n$. A Cauchy sequence stabilizes at every finite level. These stable coordinates form an element of $X$, so the metric is complete. If $x$ and $y$ agree through level $n$, then $F(x)$ and $F(y)$ agree through level $n+1$. Hence \[ d(F(x),F(y))\leq\frac12d(x,y). \] \end{proof} We now use another inverse sequence for the same topological rieg: \[ \begin{tikzcd}[column sep=small] \cdots \ar[r, twoheadrightarrow]& \Mr{4}{10^4}\ar[r, twoheadrightarrow]& \Mr{3}{10^3}\ar[r, twoheadrightarrow]& \Mr{2}{100}\ar[r, twoheadrightarrow]& \Mr{2}{20}\ar[r, twoheadrightarrow]& \Mr{2}{4}\ar[r, twoheadrightarrow]& \Mr{2}{2}\ar[r, twoheadrightarrow]& \Mr{2}{1}. \end{tikzcd} \] All the displayed objects are quotient riegs by \Cref{thm:BurrisLeeTheorem}. Adding the last four quotients does not change the limit in \Cref{def:TenAdicRieg}. The periods in this sequence are \[ 1\mid2\mid4\mid20\mid100\mid1000\mid10^4\mid\cdots. \] The standard formula for the Carmichael function \cite{carmichael1910note} gives \[ \lambda(2)=1,\quad \lambda(4)=2,\quad \lambda(20)=4,\quad \lambda(100)=20, \] and \[ \lambda(10^{k+1})\mid10^k \qquad(k\geq2). \] The modular parts of this inverse sequence have limit \[ \Z_{10}=\Z_2\times\Z_5. \] We equip this limit with the metric in \Cref{lem:MetricForInverseSequence}. Since $\Mr{\infty}{10^\infty}$ is a topological rieg, its total exponentiation defines a map \[ T\colon\Mr{\infty}{10^{\infty}}\longrightarrow\Mr{\infty}{10^{\infty}}, \qquad T(x)=3^x. \] This map preserves the modular part: at each finite quotient, a modular exponent can be represented by an integer $m$ above the tail, and $3^m$ is again above the tail. If two elements of the modular part agree modulo a period $b$, then their images agree modulo the next period $b'$: indeed, $\lambda(b')\mid b$ and $3$ is invertible modulo $b'$. Therefore, $T$ raises the agreement by one level. By \Cref{lem:MetricForInverseSequence}, the restriction \[ T\colon\Z_2\times\Z_5\longrightarrow\Z_2\times\Z_5 \] is a contraction with Lipschitz constant $\frac12$. \begin{lemma}[Stabilization of the last two digits]\label{lem:StabilizationOfTwoDigits} For every element $\xi$ of the modular part $\Z/10^2\Z \subset \Mr{2}{10^2}$, we have $T^4 (\xi) = [87]$. \end{lemma} \begin{proof} The first four transitions of the above sequence give \[ T(\xi)\equiv1\pmod2,\qquad T^2(\xi)\equiv3\pmod4, \] and then \[ T^3(\xi)\equiv3^3\equiv7\pmod{20},\qquad T^4(\xi)\equiv3^7\equiv87\pmod{100}. \] \end{proof} \begin{proposition}[The unique fixed point of $3^x$]\label{prop:FixedPointOfThreeToTheX} The function $T(x) = 3^x$ on $\Mr{\infty}{10^{\infty}}$ has a unique fixed point $\alpha$, which belongs to $\Z_2 \times \Z_5$, and every iteration sequence $x, T(x), T^2(x), \dots$ starting from $x \in \Z_2\times \Z_5$ converges to $\alpha$. Furthermore, for each $k \geq 2$, the reduction of $\alpha$ is the unique solution of $3^x = x$ in $\Z/10^k\Z \subset \Mr{k}{10^k}$ (cf.\ \Cref{fig:PictureListOfthreetotheN}). \end{proposition} \begin{proof} There is no fixed point in the natural-number part, since $3^n>n$ for every $n\in\N$. On the modular part, the map $T$ is a contraction on a non-empty complete metric space. The Banach fixed-point theorem gives a unique fixed point $\alpha\in\Z_2\times\Z_5$, and every iteration sequence in the modular part converges to $\alpha$. It remains to prove the statement at each finite level. If $r\in\Z/10^2\Z$ satisfies $3^r=r$, then \[ r=T^4(r)=[87] \] by \Cref{lem:StabilizationOfTwoDigits}. Suppose that the solution is unique modulo $10^k$, and let $r$ and $r'$ be solutions modulo $10^{k+1}$. Their reductions modulo $10^k$ coincide. Since $\lambda(10^{k+1})\mid10^k$, we obtain \[ r=3^r\equiv3^{r'}=r'\pmod{10^{k+1}}. \] Hence the solution is unique at every level. The reduction of $\alpha$ gives its existence. \end{proof} We close this subsection by determining the solutions of another exponential equation, $x^{x}=x$, in the same topological rieg. \begin{proposition}[The solutions of $x^{x}=x$]\label{prop:XToTheXEqualsX} In $\Mr{\infty}{10^{\infty}}=\N\sqcup(\Z_2\times\Z_5)$, the equation $x^{x}=x$ has exactly $11$ solutions: the element $1$ of the summand $\N$, and the ten elements \[ (0,0),\ (0,1),\qquad (1,0),\ (1,1),\ (1,i),\ (1,-1),\ (1,-i),\qquad (-1,0),\ (-1,1),\ (-1,-1) \] of $\Z_2\times\Z_5$, where $\mu_4=\{1,i,-1,-i\}$ denotes the group of fourth roots of unity in ${\Z_5}^{\times}$. \end{proposition} \begin{proof} In the summand $\N$, we have $0^{0}=1\neq0$, $1^{1}=1$, and $n^{n}>n$ for $n\geq2$, so $1$ is the only solution there. Let $x$ belong to the modular part $\Z_2\times\Z_5$, let $k\geq2$, and choose an integer $n\geq k$ with $n\equiv x\pmod{10^{k}}$. Since $\Mr{k}{10^{k}}$ is a rieg (\Cref{exmp:TenPowerN}), the reduction of $x^{x}$ to $\Z/10^{k}\Z$ is $[n^{n}]$. Therefore, \[ x^{x}=x \quad\Longleftrightarrow\quad n^{n}\equiv n\pmod{10^{k}}\text{ for every }k\geq2. \tag{$\ast$} \] Below, $v_{p}$ denotes the $p$-adic valuation and $p$ ranges over $\{2,5\}$. First, suppose $1\leq v_{p}(x)<\infty$ and put $a\coloneqq v_{p}(x)$. Taking $k>a$ in $(\ast)$, we have $v_{p}(n)=a$, and $n^{n}-n=n(n^{n-1}-1)$ with $p\mid n$ and $n-1\geq1$, so $p\nmid n^{n-1}-1$ and \[ v_{p}(n^{n}-n)=as$, we have $v_{p}(n-1)=s$. For $p=2$, the order of $u$ is a power of $2$ dividing $n-1$, hence divides $2^{s}$. For $p=5$, the order divides $4\cdot5^{k-1}$; its $5$-part divides $n-1$, hence divides $5^{s}$, while its prime-to-$5$ part divides $4$. In both cases the orders are bounded independently of $k$, so $u$ is a torsion element of ${\Z_p}^{\times}$. The torsion subgroup of ${\Z_2}^{\times}$ is $\{\pm1\}$, and that of ${\Z_5}^{\times}$ is $\mu_4$. Finally, we determine which of the remaining $3\times5$ combinations satisfy $(\ast)$; note that the same representative $n$ serves both coordinates. If the $2$-coordinate is $0$, then $4\mid n$, so $n-1$ is odd, and the order of the $5$-coordinate must be odd: the $5$-coordinate is $0$ or $1$. If the $2$-coordinate is $1$, then $2^{k}\mid n-1$, so every order in $\{1,2,4\}$ divides $n-1$: the $5$-coordinate can be any element of $\{0\}\cup\mu_4$. If the $2$-coordinate is $-1$, then $n\equiv3\pmod4$, so $v_{2}(n-1)=1$: the order $2$ divides $n-1$ but $4$ does not, and the $5$-coordinate lies in $\{0,1,-1\}$. This yields the $2+5+3=10$ listed elements. Conversely, each listed element satisfies $(\ast)$: a coordinate $0$ gives $v_{p}(n)\geq k$, hence $n^{n}\equiv0\equiv n\pmod{p^{k}}$, and the case analysis above shows precisely that the order of each torsion coordinate divides $n-1$. \end{proof} \begin{remark}[The levelwise counts diverge]\label{rmk:XToTheXLevelCounts} Contrast \Cref{prop:XToTheXEqualsX} with \Cref{prop:FixedPointOfThreeToTheX}, where every level has a unique solution. The numbers of solutions of $x^{x}=x$ in $\Z/10^{k}\Z\subset\Mr{k}{10^{k}}$ for $k=2,3,\dots,7$ are \[ 22,\ 38,\ 196,\ 196,\ 1412,\ 1412, \] and they are unbounded, even though the limit has only $11$ points: for a unit $u\equiv1\pmod4$ with $s\coloneqq 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\leq2s$. Pairing such $u$ with the $5$-coordinate $0$ produces, for $k\geq4$, 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 $\Z_2\times\Z_5$ but not in the summand $\N$: modulo $10^{k}$, the class $[0]$ is represented by $10^{k}$, and ${(10^{k})}^{10^{k}}\equiv0$. This illustrates the splitting $\N\sqcup\Z_{10}$ of \Cref{def:TenAdicRieg}. \end{remark} \section{Example 2: Riegs in category theory and combinatorics}\label{sec:CategoryAndEnumerations} % : Decategorifying cartesian closed categories} In this section, we consider the rieg structures obtained through decategorification. Since many of these are defined via universality, the verification of the rieg structure follows from abstract nonsense. However, when one tries to write them down explicitly, it looks non-trivial that all fourteen axioms of a rieg are satisfied. For example, from abstract nonsense, it follows immediately that the set of all isomorphism classes of finite directed graphs admits a natural rieg structure. But can you imagine what the exponentiation looks like? For instance, consider a single edge $\to$, and then consider taking the exponential of that edge with itself, denoted $\to^\to$. The resulting graph is depicted in \Cref{fig:ExponentialGraphArrowArrow}: its four vertices are the four functions from the vertex set $\{0,1\}$ of $\to$ to itself (the two constant functions $c_0, c_1$, the identity $\id$, and the transposition $\mathrm{swap}$), and it has exactly four edges, one of which is a loop. Notice that the vertex $\mathrm{swap}$ is isolated. \begin{figure}[ht] \centering \begin{shaded} \begin{tikzpicture}[>=Latex] \node (c0) at (0,0) {$c_0$}; \node (id) at (2.4,0) {$\id$}; \node (c1) at (4.8,0) {$c_1$}; \node (sw) at (7.2,0) {$\mathrm{swap}$}; \draw[->, thick] (c0) -- (id); \draw[->, thick] (c0) to[bend right=35] (c1); \draw[->, thick] (id) -- (c1); \path (id) edge[->, thick, loop above] (id); \end{tikzpicture} \caption{The exponential graph $\to^{\to}$} \label{fig:ExponentialGraphArrowArrow} \end{shaded} \end{figure} Regarding the decategorified semiring structure, numerous studies have been conducted under the name \emph{Burnside rig}. However, to the author's knowledge, research on its exponential structure has been very limited. Despite the exponential structure satisfying numerous equations in the definition of rieg, these have been left unused. See \cite{schanuel2000transcendencein} \subsection{Burnside rieg of CCC with finite coproducts (and a topos)} \subsubsection{The Burnside rieg functor \texorpdfstring{$\B$}{B}} \begin{definition}[] The ($1$-)category $\CCCc$ is defined as follows: \begin{itemize} \item Its objects are small categories that are cartesian closed and have finite coproducts. \item Its morphisms are functors between these categories that preserve finite products, finite coproducts, and exponentials, where we consider functors up to natural isomorphism\footnote{The author admits that it is more natural to consider this category as a $2$-category.}. \end{itemize} \end{definition} % \begin{definition} % % The category of cartesian closed categories with finite coproducts, which will be denoted by $\CCCc$, % The category $\CCCc$ has small cartesian closed categories with finite coproducts as objects, and natural isomorphism classes of functors between them that preserves finite products, finite coproducts, and exponentials as morphisms. % \end{definition} \begin{proposition}\label{prop:BurnsideRieg} For a cartesian closed category $\C$ with finite coproducts, the set of isomorphism classes of $\C$ forms a rieg with the categorical initial object, the binary coproducts, the terminal object, the binary products, and the exponentials. \end{proposition} \begin{proof} All of the fourteen axioms are implied by the universalities. \end{proof} \begin{remark}[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\ti B$ is a categorical product to prove some axioms including $(x\ti y)^z=x^z\ti y^z$. \end{remark} We borrow the following notation from \cite{menni2017every} (and from \cite{schanuel1990negative}). \begin{definition} The \demph{Burnside rieg functor} $\B \colon \CCCc \to\Rieg$ sends an object $\C$ of the category $\CCCc$ to the rieg induced by $\C$ (\Cref{prop:BurnsideRieg}), and a functor in $\CCCc$ to the induced rieg homomorphisms. \end{definition} \begin{proposition}[Topos to rieg functor]\label{prop:ToposToRiegFunctor} For a locally cartesian closed small category $\C$ with finite coproduct (in particular, an elementary topos $\C$), the correspondence \[ \ob(\C) \ni c \mapsto \B(\C/c)\in \Rieg \] defines a contravariant functor \[ \B(\C/{-})\colon \C^{\op} \to \Rieg. \] \end{proposition} \begin{example}[Finite sets to natural numbers]\label{exmp:NaturalNumbersAsBurnsideRieg} The Burnside rieg of finite sets is isomorphic to the rieg of natural numbers \[ \B(\FinSet) \cong \N. \] \end{example} \begin{example}[Infinite sets to cardinal arithmetic]\label{exmp:CardinalArithmeticAsBurnsideRieg} Let $\kappa$ be an infinite cardinal and $\Set_{<\kappa}$ be the (essentially small) category of sets with cardinality less than $\kappa$. The category $\Set_{<\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 $\B(\Set_{<\kappa})$, 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, $\B(\Set_{<\beth_{\omega}})$ is a countable rieg with $2^{\aleph_0}= \aleph_1$. However, without the GCH, there are many other possibilities of this rieg structure. \end{example} \begin{example}[Finite presheaf topos] For any small category $\C$, $\FinSet^{\C}$ has all finite limits and colimits. Therefore, if $\FinSet^{\C}$ is cartesian closed, we obtain a rieg $\B(\FinSet^{\C})$. For example, if $\C$ is a finite category or a (possibly infinite) group, then $\FinSet^\C$ is known to be cartesian closed (and a topos). \begin{itemize} \item The category of finite functions $[\to,\FinSet]$ forms a rieg of multisets of natural numbers (or Dirichlet polynomials \cite{spivak2023dirichlet}). \item More generally, for any finite category $\C$, its finite (co)presheaf category $[\C,\FinSet]$ forms a rieg. Examples include the category of finite graphs $[\rightrightarrows,\FinSet]$ and the category of rooted forests $[\omega^{\op},\FinSet]$. \item For any (possibly infinite) group $G$, the category of its finite actions $[G,\FinSet]$ forms the \emph{Burnside rig} of the group $G$. Examples include the category of sets with involution $[\Z/2\Z,\FinSet]$ and the category of finite loops $[\Z,\FinSet]$. \end{itemize} On the other hand, the category of finite discrete dynamical systems $[\N, \FinSet]$ is not cartesian closed. \end{example} \begin{question} % This is one of my motivations to consider the question: When is a finite presheaf category $[\C^{\op}, \FinSet]$ cartesian closed? The author is also interested in the closely related question: when is a finite presheaf category a topos? \end{question} \begin{example} $\HeyAlg$ Every Heyting algebra $H$ is a cartesian closed poset with finite coproducts, and thus a rieg. \end{example} % \begin{remark} % The category of finite discrete dynamical systems $[\N, \FinSet]$ does not form a rieg since it is not cartesian closed. This is one of my motivations to consider the question: when is a finite presheaf category $[\C, \FinSet]$ cartesian closed?\footnote{The author is also interested in the closely related question: when is a finite presheaf category a topos?} % \end{remark} \subsubsection{Enumerations} In many cases, to utilize the Burnside rieg $\B(\C)$ to enumerate something, we consider a \demph{enumeration function} $\abs{-}\colon \B(\C)\to \N$, which is typically a rig homomorphism. There are several ways to choose such enumeration function. \begin{example}[Global sections for a connected topos] For example, for a locally finite topos $\C$ we have the global section functor $\Gamma=\C(1, -)\colon \C \to \FinSet$, which preserves products, but not necessarily coproducts. If the topos $\C$ is connected (i.e., if $\Gamma$ preserves finite coproduct), then the functor $\Gamma\colon \C \to \FinSet$ induces the rig homomorphism $\abs{-}_\Gamma\colon \B(\C) \to \N$ that counts the number of global sections. \end{example} \begin{example}[Connected components for a stably locally connected topos] If a topos $\C$ admits an adjoint triple $\pi_0 \dashv \Delta \dashv \Gamma\colon \C \to \FinSet$ such that $\pi_0$ preserves finite products (see \demph{stable local connectedness} in \cite{johnstone2011remarks}), then the functor $\pi_0$ induces a rig homomorphism $\abs{-}_{\pi_0}\colon \B(\C) \to \N$. \end{example} \begin{example}[Enumeration with a torsion-free atom.] Let $\E$ be a small topos. Due to \Cref{prop:ToposToRiegFunctor}, every object $X\in \ob(\E)$ induces a rieg homomorphism $\B(\E) \xrightarrow{\B(X \to 1)}\B(\E/X)$. Therefore, if $\E/X \simeq \FinSet$, then we obtain a rieg homomorphism $\B(\E) \to \N$. According to the terminology in \cite{kock1991presentations}, we call such an object $X$ a \demph{torsion-free atom}\footnote{An object $X$ of a topos $\E$ is an \demph{atom} if it has exactly two subobjects. Following \cite[Definitions 1.1 and 1.9]{kock1991presentations}, an object $X$ of a topos with a geometric morphism $\gamma \colon \E \to \FinSet$ is \demph{torsion-free} if every map with codomain $X$ is locally monic relative to $\gamma$; in the topos of finite $G$-sets, for instance, this means that every $G$-orbit of $X$ is free. If $\E/X \simeq \FinSet$, then $X$ is a torsion-free atom in this sense.}. \end{example} \subsection{Riegs of functions \texorpdfstring{$\B(\FinSet^{\to})$}{}: List of numbers and Liouville's divisor theorem} \subsubsection{The Burnside rieg of functions \texorpdfstring{$\B(\FinSet^{\to})$}{}} Our first example is the Burnside rieg of the topos $\FinSet^{\to}$, which is called the topos of (finite) fucntions or the (finite) Sierpinski topos. An object of the topos is a function $p\colon A \to B$. % , which is also regarded as a family of sets $\{A_b\}_{b\in B}$, where $A_b \coloneqq p^{-1}(b)$. Since a function $f\colon A \to B$ can be regarded as a family of sets $\{f^{-1}(b)\}_{b\in B}$, the isomorphism classes of the topos $\FinSet^{\to}$ are in bijective correspondence with the finite multiset of natural numbers. Let $\mN$ denote the set of all multisets of natural numbers. Each multiset will be denoted as a list of natural numbers $(), (3,1,4), (1,2,3,1,1,0,0) \in \mN$, and rearranged lists are identified $(1,2,3,1,1,0,0) = (0,0,1,1,1,2,3)\in \mN$. The addition is given by a concatenation of lists, and the product is given by the list of all ccomponent-wise products. \begin{align*} (3,1,4)+ (1,2,7,0)&=(3,1,4,1,2,7,0)\\ (3,1,4)\ti (1,2,7,0)&= (3,6,21,0,1,2,7,0,4,8,28,0) % (3\ti 1,3\ti 2,3\ti 7, 3\ti 0, 1\ti 1, 1\ti 2, 1\ti 7, 1\ti 0, 4\ti 1, 4\ti 2, 4\ti 7, 4\ti 0) \end{align*} \cite{spivak2023dirichlet} explains that this rig structure is isomorphic to the rig of (formal) Dirichlet polynomials \[ \mN \cong \N\left[0^{-x},1^{-x},2^{-x},\dots \right] \text{ in } \Rig. \] % $\N\left[\frac{1}{n^x}\mid n=0,1,2,\dots\right]$ However, exponentials are different: \[(n_1, \dots,n_k)^{(m)}=({n_1}^m , \dots, {n_k}^m ).\] There is a unique extension of this exponential to all exponentials. For example, \begin{align*} (3,1,4)^{ (2,0)} &= (3,1,4)^{ (2)} (3,1,4)^{ (0)} \\ &=(9,1,16)(1,1,1)\\ &=(9,9,9,1,1,1,16,16,16). \end{align*} \begin{remark}[$\mult{R}$ and Artin gluing] \end{remark} \subsubsection{Liouville's theorem} The equation \[ (1+2+3+\dots + n)^2 =1^3+ 2^3+ \dots +n^3 \] is well-known. As studied in \cite{barbeau2013sum}, there are so many similar equations including \begin{itemize} \item $(1+2+2+ 4)^2 =1^3+ 2^3+ 2^3+ 4^3$, \item $(1+2+2+3+5)^2 = 169 = 1^3+2^3+2^3+3^3+5^3$, and \item $(1+2+2+3+4+6)^2 =1^3+ 2^3+ 2^3+ 3^3+4^3+6^3$. \end{itemize} So the question is: for a given finite list of natural numbers $(a_1, \dots a_n)$, does the equation \begin{equation}\label{eq:SquareOfSumEqualSumOfCubes} \left(\sum_{i=1}^n a_1\right)^2 = \sum_{i=1}^n a_i^3. \end{equation} % \[ % \left(\sum_{i=1}^n a_1\right)^2 = \sum_{i=1}^n a_i^3. % \] holds? Writing $d(n)$ for the number of divisors of a positive integer $n$, Liouville's theorem states that \[ \left(\sum_{m|n} d(m)\right)^2 = \sum_{m|n} d(m)^3. \] For example, in the case of $n=10$, we obtain the equation \[ (d(1)+d(2)+d(5)+d(10))^2 = d(1)^3+d(2)^3+d(5)^3+d(10)^3. \] The proof of this theorem is not difficult, and is just a highschool level problem. Given the equation $(1+2+3+\dots + n)^2 =1^3+ 2^3+ \dots +n^3$, it suffices to prove that the problem can be reduced to the case of $m=p^e$ for some prime number $p$. In other words, the only non-trivial part is to prove that if two sequence $(a_1, \dots, a_n)$ and $(b_1, \dots , b_m)$ satisfies the equation, so does their \dq{product sequence} $(a_1\cdot b_1, a_1\cdot b_2, \dots, a_1\cdot b_m, a_2\cdot b_1, \dots , a_n\cdot b_m)$. Here is a categorified (or Burnside) point of view. % A finite list of natural numbers can be naturally regarded as an object of $\FinSet^{\to}$. Consider the Burnside rieg $\B(\FinSet^{\to})$ of the topos of functions between finite sets. We obtain the equivalence % if and only if \[ \text{a list $C= (a_1, \dots a_n)$ satisfies \Cref{eq:SquareOfSumEqualSumOfCubes} } \iff \#{\Hom(A,C)} = \#{\Hom(B,C)}, \] where $A,B \in \FinSet^{\to} $ are given in \Cref{fig:representingObjectOfSum-of-cubesAndSquare-of-sum}. \begin{figure}[htbp] \centering \begin{tikzpicture} % left \begin{scope}[shift={(-3,0)}] \draw[rounded corners, thick] (-2,1) rectangle (2,-4); \node at (-1,0) {\LARGE$\cdot$}; \node at (0,0) {\LARGE$\cdot$}; \node at (1,0) {\LARGE$\cdot$}; \node at (0,-3) {\LARGE$\cdot$}; \draw[->] (-1,-0.2) -- (0,-2.8); \draw[->] (0,-0.2) -- (0,-2.8); \draw[->] (1,-0.2) -- (0,-2.8); \node[below] at (0,-4.5) {$A=(3)$}; \end{scope} % right \begin{scope}[shift={(3,0)}] \draw[rounded corners, thick] (-2,1) rectangle (2,-4); \node at (-1,0) {\LARGE$\cdot$}; \node at (1,0) {\LARGE$\cdot$}; \node at (-1,-3) {\LARGE$\cdot$}; \node at (1,-3) {\LARGE$\cdot$}; \draw[->] (-1,-0.2) -- (-1,-2.8); \draw[->] (1,-0.2) -- (1,-2.8); \node[below] at (0,-4.5) {$B=(1,1)$}; \end{scope} \end{tikzpicture} \caption{The representing object of sum-of-cubes and square-of-sum in $\FinSet^{\to}$} \label{fig:representingObjectOfSum-of-cubesAndSquare-of-sum} \end{figure} \subsection{Rieg of finite groups}\label{ssec:RiegOfFiniteGroups} \subsubsection*{Counting problems} We will give a rieg-theoretic method to answer the following undergraduate-level counting problems. \begin{question}\label{QuestionIndex2} For a finite group $G$, let $n_G$ denote the number of subgroups whose index (= the number of cosets) is $2$. Write $n_{G\times H}$ using $n_G$ and $n_H$. \end{question} \begin{question}\label{QuestionDsix} Count the number of group homomorphisms from $D_6$ to itself. (Hint: $D_6$ is the dihedral group of order $12$, and $D_6 \cong S_3 \times C_2$.) \end{question} Notice that all operations $0,1, +, \times, \ex$ of the cartesian closed category of finite groupoids $\Groupoidfin$ are well-defined up to equivalence. Therefore, (as a $2$-categorical analogy of \Cref{prop:BurnsideRieg}), the equivalence classes of finite groupoids, which are the formal sums of finite groups, form a rieg! The aim of this section is to concretely describe the rieg structure. \begin{definition} We definite \emph{the rig of finite groups} $\G$ as follows: \begin{itemize} \item The underlying additive commutative monoid is the free commutative monoid of the set of isomorphism classes of finite groups, which is given by the finite formal sum. \[\G \coloneqq \bigoplus_{[G]\text{: iso.class}}\N\] \item The multiplication is given by the unique extension of \[[G]\times [H] \coloneqq [G\times H].\] \end{itemize} \end{definition} % We will write $[G]$ just by $G$. Hereafter, the isomorphism class of a group $G$ % , % denoted as $[G]$, will be simply referred to as $G$. \begin{notation} The (isomorphism class of) the cyclic group $\Z/n\Z$ is denoted by $C_n$. \end{notation} \begin{example}Some examples of calculations include: \begin{itemize} \item $C_{12} = C_3 \times C_4$ \item $D_6 = S_3 \times C_2$ \item $(S_3 + C_2)^2 = {S_3}^2 + 2 (S_3\times C_2) + {C_2}^2= {S_3}^2 + 2 D_6 + {C_2}^2$ \end{itemize} \end{example} \begin{definition}[Conjgacy classes of homomorphism] Let $G$ and $H$ be finite groups. \begin{itemize} \item Two homomorphisms $\phi,\psi \colon G\to H$ are \emph{conjugate} if there exists $h\in H$ such that $\phi = h\psi h^{-1}$ holds. \item The automorphism group (or the stabilizer) of a homomorphism $\phi \colon G\to H$ is the subgroup of $H$, defined by $\Aut(\phi)\coloneq \{h\in H\mid h\phi h^{-1} = \phi\}$. \end{itemize} \end{definition} \begin{theorem} The rig of finite groups $\G$ admits the following rieg structure: \begin{itemize} \item For two finite groups $G$ and $H$, its exponential $H^G$ is defined by \[ H^G \coloneqq \sum_{[\phi]:conj.class} \Aut(\phi) \] \item In general, the exponential is defined by \[{\left(\sum_{j} H_j\right)}^{\left(\sum_{i} G_i\right)} \coloneqq \prod_{i}\sum_{j} \left({H_j}^{G_i}\right),\] for any two families of finite groups $(G_i)_{i}$ and $(H_j)_{j}$. \end{itemize} \end{theorem} \begin{proof} This is the rieg of equivalent classes of finite groupoids, explained at the beginning of this section. % Since all operations $0,1, +, \times, \ex$ of the category of finite groupoids $\Groupoidfin$ is well-defined up to equivalence, the equivalence classes of finite groupoids, which are % % Since the equivalence classes of finite groupoids are % the formal sums of finite groups, form a rieg. % % The above exponential operation is % The exponential structures above $\G$ is the quotient rieg of the rieg of finite groupoids. \end{proof} % \begin{remark} % This is a $2$-categorical version of \Cref{PropositionCCC}. % \end{remark} \begin{example}\label{ExampleExp} Let's try to calculate ${D_6}^{D_6}$. In order to utilize the exponential rules, we first calculate smaller parts: % Some examples of calculations include: \begin{itemize} % % \item ${C_{12}}^{C_2} = {C_{3}}^{C_2} \cdot {C_{4}}^{C_2} = C_3 \cdot (C_4 + C_4) = {C_{12}} + {C_{12}}$ % WARNING: the commented-out line below is WRONG (${S_3}^{C_2} \neq S_3 + 3\cdot C_2$; % the correct value is $C_2 + S_3$, as in the displayed list). Do not uncomment. % \item ${D_6}^{C_2} = {S_3}^{C_2}\cdot {C_2}^{C_2} = (S_3 + 3 \cdot C_2) \cdot (2\cdot C_2) =2\cdot D_6 + 6\cdot {C_2}^2$ % \item ${C_2}^{D_6} = {\left({C_2}^{C_2}\right)}^{S_3}= 2\cdot {C_2}^{S_3}= 4 \cdot C_2$ % \item ${C_2}^{S_3} = 2\cdot C_2$ % \item ${D_6}^{C_2} = {S_3}^{C_2}\cdot {C_2}^{C_2} = (S_3 + C_2) \cdot (2\cdot C_2) =2\cdot D_6 + 2\cdot {C_2}^2$ % \item ${S_3}^{S_3} = 1+ C_2 + S_3$ % \item ${D_6}^{D_6} = {\left({D_6}^{C_2}\right)}^{S_3} = ({S_3}^{S_3} + {C_2}^{S_3}) \cdot (2\cdot {C_2}^{S_3})$ \item ${C_2}^{C_2}= 2\cdot C_2 $ \item ${C_2}^{S_3} = 2\cdot C_2$ \item ${S_3}^{C_2} = C_2 + S_3$ \item ${S_3}^{S_3} = 1+ C_2 + S_3$ \end{itemize} Then we obtain % \begin{itemize} % \item ${D_6}^{D_6} % = {\left({S_3}^{S_3}\right)}^{C_2}\cdot {\left({C_2}^{S_3}\right)}^{C_2} % = {\left(1+ C_2 + S_3\right)}^{C_2}\cdot {\left(2\cdot C_2\right)}^{C_2} % = {\left(1+ 3\cdot C_2 + S_3\right)}\cdot {\left(4\cdot C_2\right)} % = 4\cdot C_2 + 12 \cdot {C_2}^2 + 4\cdot D_6. % $ % \end{itemize} \[{D_6}^{D_6} = {\left({S_3}^{S_3}\right)}^{C_2}\cdot {\left({C_2}^{S_3}\right)}^{C_2} = {\left(1+ C_2 + S_3\right)}^{C_2}\cdot {\left(2\cdot C_2\right)}^{C_2} = {\left(1+ 3\cdot C_2 + S_3\right)}\cdot {\left(4\cdot C_2\right)} = 4\cdot C_2 + 12 \cdot {C_2}^2 + 4\cdot D_6. \] \end{example} Some properties of finite groups, like being abelian, are characterized in terms of this rieg structure. \begin{proposition}\label{PropositionAbelian} For a finite group $A$, \begin{itemize} \item if $A$ is abelian, then we have $A^G = \#\Hom(G,A) \cdot A.$ \item conversely, if $A^G$ is a sum of $A$ for any $G$, then $A$ is abelian. \end{itemize} \end{proposition} \begin{proof} The former statement is immediate from the definition. If $A^G$ is a sum of $A$ for any $G$, then $A^A$ is a sum of $A$. Especially, we have $\Aut(\id_{A})=A$ and $A$ is abelian. \end{proof} % Just to have fun, let's utilize the exponential rules for solving a Bacherar-level group theory problem! % To have fun using the exponential rules, let's try solving an undergraduate-level group theory problem! Now we can answer the first problem, \Cref{QuestionIndex2}! \begin{answer}[to \Cref{QuestionIndex2}]\label{AnswerIndex2} Since ${C_2}^G = (n_G + 1)\cdot C_2$, we have % \begin{align*} % (n_{G\times H} + 1)\cdot C_2 % &={C_2}^{G\times H}\\ % &={\left({C_2}^{G}\right)}^H\\ % &={(n_G + 1)\cdot C_2}^H\\ % &=(n_G + 1)\cdot (n_H + 1)\cdot C_2 \\ % \end{align*} \[ (n_{G\times H} + 1)\cdot C_2 ={C_2}^{G\times H} ={\left({C_2}^{G}\right)}^H ={(n_G + 1)\cdot C_2}^H =(n_G + 1)\cdot (n_H + 1)\cdot C_2. \] This proves $n_{G\times H} = n_G \cdot n_H + n_G + n_H$. \end{answer} \begin{remark} For a limit cardinal $\kappa$, one can consider a rieg of larger groups, in which we can similarly consider representations of product groups, like ${\mathbb{C}\mathbf{Vect}_{\text{f.d.iso.}}}^{G\times H}={\left(\sum_{k=0}^{\infty}\mathrm{GL}_k(\mathbb{C})\right )}^{G\times H}$. \end{remark} % This puzzle is easily solved by the following observation: % \begin{itemize} % \item For any abelian group $A$, we have % \[ % A^G = \#\Hom(G,A) \cdot A. % \] % \item For any abelian group $A$, we have % \[ % A^G = \#\Hom(G,A) \cdot A. % \] % \end{itemize} \subsubsection{Groupoid cardinality}\label{SectionGC} In order to utilize riegs for counting something, the basic rieg theoretic method is to consider a \textbf{rig} homomorphism from a given rieg to the rig of numbers, like $\N, \Z, \Q$. For the rieg of finite groups $\G$, the notion of \emph{groupoid cardinality}, introduced in \cite{baez2001finite}, is useful. We can utilize it to obtain rational numbers from elements of $\G$. \begin{definition} For $x=\sum_{i} G_i \in \G$, its \emph{groupoid cardinality} $\abs{x} \in \Q$ is defined by \[\abs{x} \coloneqq \sum_{i} \frac{1}{\# G_i}.\] \end{definition} \begin{proposition}\label{PropositionExpGC} The groupoid cardinality function $\abs{-}\colon \G \to \Q$ is a rig homomorphism. Furthermore, for finite groups $G$ and $H$, we have \[ \abs{G^H} = \frac{\# \Hom(H,G)}{\# G}. \] \end{proposition} \begin{proof} For sums and products, the proof is easy. Regarding exponentials, one can use the orbit-stabilizer theorem for the conjugate action of $G$ on $\Hom(H,G)$. % One can find the proof, which is fairly easy, in \cite{baez2001finite}. % But the proof is not hard. \end{proof} \begin{exercise} Check that \Cref{PropositionExpGC} is compatible with \Cref{PropositionAbelian}. \end{exercise} Let us finish this introductory note by giving the answer to \Cref{QuestionDsix}! % \begin{exercise} % Utilizing \Cref{PropositionExpGC} and \Cref{ExampleExp}, calculate the number of group homomorphisms from $D_6$ to itself. % \end{exercise} \begin{answer}[to \Cref{QuestionDsix}]\label{AnswerDsix} In \Cref{ExampleExp}, we obtained ${D_6}^{D_6} = 4\cdot C_2 + 12 \cdot {C_2}^2 + 4\cdot D_6$. By taking the groupoid cardinality, we obtain \[ \frac{\# \Hom(D_6,D_6)}{12} = \frac{4}{2} + \frac{12}{4} + \frac{4}{12}. \] This proves that $\#\Hom(D_6,D_6) = 64$. \end{answer} % are compatible % \memo{Counting with Euler characteristic} % \subsection{Rieg of multisets, Liouville's divisor theorem} % \subsection{Riegs from toposes, repeating decimal} % \input{Games} % \input \section{Example 3: Riegs in logic}\label{sec:RiegsInLogic} % . As generalized Heyting algebras} In this subsection, we investigate the riegs that consist of \dq{propositions.} The motivating examples are the rieg of truth values and the rieg of subsets: \begin{example}[Rieg of truth values] The set of truth values $\2 = \{\bot, \top\}$ has a natural rieg structure, as $(\2, \bot, \top, \lor, \land, \leftarrow)$. This is isomorphic to the overflow rieg with threshold $1$ and $\Mr{1}{1}$. \end{example} \begin{example}[Powerset]\label{ExamplePowerset} For any set $X$, its powerset $\Po{X}$ has a rieg structure with $(\Po{X}, \emptyset, X, \cup,\cap, \leftarrow)$, where $A\leftarrow B$ is defined to be $A\cup B^{\co}$. More generally, every Heyting algebra\footnote{or CCC} is a rieg. When $X=\emptyset$, its powerset rieg is the degenerate rieg. When $X$ is a singleton, its power rieg is the rieg of truth values. \end{example} The above riegs have special properties: \begin{itemize} \item $1+1=1$ \item The underlying rig is a lattice \item They are Heyting algebras. \end{itemize} For each property, we have a class of riegs. We will study them one by one. \subsection{Riegs in which \texorpdfstring{$1+1=1$}{one plus one is one}} \begin{proposition}\label{PropositionIdempotent} For a rieg $R$, the followings are equivalent: \begin{enumerate} \item $1+1=1$ \label{Conditionch2_1} \item $\ch R = (0,1)$ or $(1,1)$\label{Conditionch2_2} \item There is a rieg homomorphism from the rieg of truth values $\2=\{\bot, \top\}$\label{Conditionch2_added} \item The addition is idempotent. (i.e., for any $x\in R$, $x+x=x$)\label{Conditionch2_3} \item Both addition and multiplication are idempotent. (i.e, for any $x\in R$, $x+x=x\ti x =x$)\label{Conditionch2_4} \end{enumerate} \end{proposition} \begin{proof} The equivalence between \ref{Conditionch2_1}, \ref{Conditionch2_2} and \ref{Conditionch2_added} follows from the definition of characteristics. By multiplying $x$, we have \ref{Conditionch2_1} $\implies$ \ref{Conditionch2_3}. To prove \ref{Conditionch2_4} from $\ref{Conditionch2_1}$, we can use \[x\ti x = x^{1+1} = x^1 = x.\] The remaining implications are trivial. \memo{Check whether the terminology \dq{characteristic} for rigs is standard, and cite a source if so.} \end{proof} \begin{example}[Max-plus is not a rieg] The max-plus algebra $(\R\cup \{-\infty\},-\infty,\oplus, 0,\otimes)$ % denote the max-plus algebra, which is the set of all non-negative integers (or real numbers) with $\oplus=\max$ as addition and $\otimes=+$ as multiplication. These data make $M$ a rig. % $M$ admits no rieg structures. If it admits a rieg structure, since $1\oplus 1=\max(1,1)= 1$, the multiplication $\otimes$, (which is the addition in the usual sense) should also be idempotent. However, $1\otimes 1 = 1+1 = 2\neq 1$, contradiction. \end{example} \begin{definition}\label{def:idempotentRieg} A rieg $R$ is said to be \demph{idempotent}, if it satisfies the conditions of \Cref{PropositionIdempotent}. \end{definition} \begin{remark}(Multiplicatively idempotent riegs) Even if a rieg $R$ is multiplicatively idempotent, it might not be additively idempotent. For example, the parity rieg \Cref{exmp:ParityRieg} is multiplicatively idempotent but not additively idempotent. However, there is a strong restriction on the characteristics. For a multiplicatively idempotent rieg $R$, its characteristics $\ch R$ should be less than $(2,2)$ % (\Cref{DefinitionOrderCharacteristics}), since $2 = 2\times 2 = 4$. Therefore, there are only finitely many possible characteristics, namely \[\ch R =(0,1), (1,1), (1,2), (2,1), \text{or } (2,2).\] And all of them are possible, since $\Mr{0}{1},\Mr{1}{1},\Mr{1}{2},\Mr{2}{1},\text{ and }\Mr{2}{2}$ are multiplicatively idempotent. \end{remark} \subsection{Riegs that are lattices} Next, we will study when (the underlying rig of) a rieg is a lattice. The necessary condition is being idempotent (\Cref{def:idempotentRieg}). However, this is not sufficient: \begin{example}[Idempotent rieg that is not a lattice]\label{exmp:IdempotentNotLattice} In \Cref{ExamplePolynomialexp}, we observed that $\N[x]$ with exponential \[f(x)^{g(x)} = f(x)^{g(0)}= \underbrace{f(x)\ti\dots \ti f(x)}_{g(0)\text{ times}}\] is a rieg. Dividing $\N[x]$ into $4$ groups \begin{align*} \mathrm{ZC}&=\{f(x)\in \N[x]\mid f(0)=0\text{ and }f\text{: constant}\} = \{0\}\\ \mathrm{ZI}&=\{f(x)\in \N[x]\mid f(0)=0\text{ and }f\text{: increasing}\}\\ \mathrm{PC}&=\{f(x)\in \N[x]\mid f(0)>0\text{ and }f\text{: constant}\}\\ \mathrm{PI}&=\{f(x)\in \N[x]\mid f(0)>0\text{ and }f\text{: increasing}\}, \end{align*} we obtain a $4$-element rieg $\{\mathrm{ZC},\mathrm{ZI},\mathrm{PC},\mathrm{PI}\}$ as a quotient rieg. Indeed, the group to which $f$ belongs is determined by the pair of data (whether $f(0)=0$ or $f(0)>0$; whether $f$ is constant or increasing), and this pair for $f+g$ and for $f\ti g$ is determined by the pairs for $f$ and $g$ (for the multiplication, note that $\mathrm{ZC}=\{0\}$ consists of the single element $0$). For the exponential, observe that $f^{g} = f^{g(0)}$ is equal to $1\in \mathrm{PC}$ if $g(0)=0$, and belongs to the same group as $f$ if $g(0)>0$; in both cases, the group of $f^g$ depends only on the groups of $f$ and $g$. The underlying rig of this quotient is the rig presented by a single generator $x$ and two equations $1+1=1$ and $x^2=x$. (The additive idempotency follows from $1+1=1$ via $f+f = f\ti(1+1) = f$; hence the presented rig consists of the four elements $0, 1, x$, and $1+x$, corresponding to $\mathrm{ZC}, \mathrm{PC}, \mathrm{ZI}$, and $\mathrm{PI}$, respectively.) This rieg satisfies $1+1 = 1$, but the underlying rig is not a lattice since $1+x\neq 1$. \end{example} \memo{reference for lattice theory} \begin{proposition}[Rieg and Lattice]\label{prop:WhenIsARiegALattice} For a rieg $R$, the following conditions are equivalent: \begin{enumerate} \item The underlying rig is a (bounded) lattice. \label{ConditionLattice1} \item For any $x\in R$, $1+x=1$. \label{ConditionLattice2} \end{enumerate} \end{proposition} \begin{proof} The implication $\text{\ref{ConditionLattice1}}\implies \text{\ref{ConditionLattice2}}$ follows from the fact that $1$ is the maximum element in a lattice. We prove \ref{ConditionLattice1} from \ref{ConditionLattice2}. Substituting $x$ with $1$, we obtain $1+1=1$, i.e., this rieg is idempotent (\Cref{def:idempotentRieg}). Now it is enough to prove the absorption laws \begin{align*} x+xy&=x\\ x(x+y)&=x. \end{align*} It is proven as $x(x+y) = x^2 +xy = x+xy = x(1+y)=x1=x$. \end{proof} \memo{The condition \ref{ConditionLattice2} is called \demph{absorbing} (with respect to addition).} \subsection{Heyting algebras are riegs} A Heyting algebra is not just related but is a rieg satisfying additional equations. \begin{proposition} Every Heyting algebra $(H,0,1,\lor,\land, \leftarrow)$ is a rieg. \end{proposition} \begin{proof} We can directly prove this. Alternatively, this is also an immediate corollary of \Cref{prop:BurnsideRieg}, since a Heyting algebra is a bicartesian closed category whose underlying category is a poset. \end{proof} \begin{example}[A rieg that is a lattice but not a Heyting algebra] Let $\Po{X}$ be the power set of a non-empty set $X$, equipped with a rig structure given by $\emptyset, X, \cup$ and $\cap$. We consider a rieg structure on $\Po{X}$ that is different from \Cref{ExamplePowerset}. First, fix an arbitrary element $x\in X$ and define the exponential as \[ A^B\coloneqq \begin{cases} A & (x\in B)\\ X & (x \notin B). \end{cases} \] This rieg structure is given by the composition of two rig homomorphisms. The first one is a rig homomorphism to the rig of truth value $\2 = \{\bot, \top\}$ defined as \[\Po{X} \to \2\colon A \mapsto \dq{x\in X}.\] The other is the unique rig homomorphism \[\2 \to \End(\Po{X}, X, \cap),\] which sends $0\in \2$ to the constant funciton $\mathrm{const}_{X}\colon \Po{X} \to \Po{X}$ and $1\in \2$ to the identity function $\mathrm{id}_{X}\colon \Po{X} \to \Po{X}$. \begin{remark}[Riegs from ultrafilters]\label{rmk:RiegsFromUltrafilters} Rig homomorphisms $\Po{X} \to \2$ correspond exactly to ultrafilters on $X$. For each ultrafilter $\mathcal{U}$ on $X$, the same construction equips the rig $\Po{X}$ with a rieg structure: the exponentiation is given by $A^{B} = A$ if $B \in \mathcal{U}$, and $A^{B} = X$ otherwise. The example above is the special case where $\mathcal{U}$ is the principal ultrafilter generated by $x \in X$. \end{remark} % where $\2$ denotes the rieg of truth values. % \begin{itemize} % \item $\Po{X}\to \2= \{\bot, \top\}$ % \item $\2 \to \End(\Po{X}, X, \cap)$ % \end{itemize} If $X$ has at least two elements, this rieg is not a Heyting algebra, because \[\{x\}^{\{x\}}=\{x\}\neq X.\] \end{example} \begin{proposition} A rieg $R$ is a Heyting algebra, if and only if it satisfies the following additional equations: \begin{itemize} \item $1+x=1$ % \item $x\ti x=x$ % \item $1+1=1$ %$x+x = x$ \item $x^x =1$ % \item $x(y+1)=x$ %$$xy+y=y$ % \item $x^{y+1}=x$ %$y y^x = y$ % \item $(x+y)y=y$ \item $x y^x = xy$ \end{itemize} \end{proposition} \begin{corollary} The category of Heyting algebras $\HeyAlg$ is a reflective full subcategory of the category of riegs $\Rieg$. \[ \begin{tikzcd} \HeyAlg \ar[r, shift right, hookrightarrow]&\Rieg \ar[l, shift right] \end{tikzcd} \] \end{corollary} The construction of the left adjoint is the usual one: quotient by new equations. For example, the associated Heyting algebra of $\N$ is the Heyting algebra of truth values $\{\bot, \top\}.$\footnote{This particular example is a trivial case, since a left adjoint preserves colimits.} The relation between Heyting algebras and riegs is not an addition of structures, but an addition of properties. In this respect, it is closer to the relationship between abelian groups and groups rather than to the relationship between rings and groups. \appendix \section{Preliminaries on equational theory and profinite topology} In this section, let $\T$ be a (finite arity single-sorted) algebraic theory. We are especially interested in the case $T= \text{(the theory of riegs)}$. The category of $\T$-algebras is denoted by $\TAlg$. \subsection{Categorical properties of riegs (and general \texorpdfstring{$\T$}{T}-algebras)} \begin{remark}[Categorical properties of riegs] Several category-theoretic properties of $\Rieg$ immediately follow from the mere existence of an equational definition by the theory of categorical universal algebra. Some of them are noted below. % However, if you are not familiar with category theory, you can ignore them, since most of the content of this paper is understandable without them. \begin{itemize} \item The category of riegs $\Rieg$ has all small limits and colimits. \item Furthermore, the forgetful functor $U\colon \Rieg \to \Set$ (preserves and) creates all limits. \item The forgetful functor $U\colon \Rieg \to \Set$ has a left adjoint $F\colon \Set \to \Rieg$ \item Every rieg homomorphism $f\colon R \to S$ is uniquely (up to the canonical isomorphism) decomposed into the composition of a surjective homomorphism followed by an injective homomorphism $R \twoheadrightarrow \Image(f) \rightarrowtail S$. \end{itemize} This means we can construct arbitrary small limits using limits in $\Set$. For a given family of riegs $\{R_{\lambda}\}_{\lambda\in \Lambda}$, its categorical product is given by the product set $\prod_{\lambda\in \lambda} R_{\lambda}$ with the index-wise operations. \end{remark} An element of the free rieg $F(\{x\})$ looks like \[(3^{x}+x^{x^{x}})^{x^{2^{x}}+5^{x+0^{x}}+1}+0^{x} x.\] \subsection{Topological \texorpdfstring{$\T$}{T}-algebras and their profinite completion}\label{ssec:GeneralTheoryOfProfiniteAlgebras} A \demph{topological $\T$-algebra} is a model of $\T$ in the category $\Top$, that is, a $\T$-algebra equipped with a topology such that all operations of $\T$ are continuous. Morphisms of topological $\T$-algebras are continuous $\T$-algebra homomorphisms. The category of topological $\T$-algebras is denoted by $\TTAlg$. It is straightforward to verify the next lemma. \begin{lemma}[Limits in the topological $\T$-algebras]\label{lem:LimitsofTopologicalAlgebras} $\TTAlg$ admits all small limits, which are preserved by the two forgetful functors $\TTAlg\to \TAlg$ and $\TTAlg\to \Top$. \end{lemma} In otherwords, a small limit in $\TTAlg$ is just the limit at the underlying set level equipped with the canonical $\T$-algebra structure and the initial topology. % For a \begin{notation} % For a $\T$-algebra $R$, % \end{notation} For a given $\T$-algebra $R$, a \demph{quotient} $\T$-algebra is a surjective $\T$-algebra homomorphism $R\twoheadrightarrow Q$, up to the canonical isomorphisms. The quotients form a complete lattice $\Quot_{\T}(R)$. We put $Q\leq Q'$ if there exists a homomorphism $Q'\twoheadrightarrow Q$ that commutes with the quotient maps from $R$. Let $\FinQuot_{\T}(R)$ denote the subposet of finite quotient $\T$-algebras. \begin{definition}[Profinite completion of a $\T$-algebra] For a $\T$-algebra $R$, its \demph{profinite completion} $\pro{R}$ is the limit of all finite quotients of $R$. In other words, $\pro{R}$ is the limit of the following diagram: \[ {\FinQuot_{\T}(R)}^{\op} \to \TAlg \xrightarrow{\text{discrete}} \TTAlg. \] \end{definition} \begin{remark}[As a codensity monad] It is much more natural to define the profinite completion as an endofunctor on the category $\TTAlg$ although we will not need it in the present paper. The category of finite (and discrete) $\T$-algebras $\finTAlg$ is a full subcategory of the category $\TTAlg$, and the codensity monad of the embedding $\finTAlg \hookrightarrow \TTAlg$ is the profinite completion. \end{remark} \section{Other (counter)examples} \subsection{Basic examples}\label{sec:BasicExamples} \begin{example}[Non-negative real numbers] The set of non-negative real numbers $[0,\infty)$ has the natural rieg structure, defining \[ 0^x= \left\{ \begin{array}{ll} 1 & (x=0) \\ 0 & (x>0). \end{array} \right. \] The rieg of natural numbers is a subrieg of this rieg. However, the subset of all non-negative rational numbers is not subrieg, since it is not closed under exponentials. \end{example} \begin{proposition}[J.~Koizumi, personal communication]\label{prop:KoizumiRigidity} Let $f\colon (0,\infty)\to(0,\infty)$ preserve the exponentiation, i.e.\ satisfy \[ f(x^{y}) = f(x)^{f(y)} \qquad (x,y>0). \] Then $f$ is either the constant function $1$ or the identity function. \end{proposition} \begin{proof} Putting $x=y=1$, the value $a\coloneqq f(1)$ satisfies $a=a^{a}$, hence $(a-1)\log a = 0$ and $a=1$. Applying $f$ to $x^{yz}=(x^{y})^{z}$ gives \[ f(x)^{f(yz)} = f(x^{y})^{f(z)} = f(x)^{f(y)f(z)}\qquad (x,y,z>0). \] Assume $f$ is not constantly $1$, and fix $x_0$ with $f(x_0)\neq 1$; then $f(yz)=f(y)f(z)$, i.e.\ $f$ is multiplicative. Put $\varphi(u)\coloneqq \log f(e^{u})$ for $u\in \R$. Multiplicativity gives $\varphi(u+v)=\varphi(u)+\varphi(v)$, while the original equation with $x=e^{u}$ gives $\varphi(yu) = f(y)\varphi(u)$ for all $u\in\R$ and $y>0$. Fixing $u_0$ with $\varphi(u_0)\neq 0$, we obtain $f(y)=\varphi(yu_0)/\varphi(u_0)$, so additivity of $\varphi$ makes $f$ additive: $f(y+y')=f(y)+f(y')$. An additive function with positive values is strictly increasing, and $f(1)=1$ forces $f(q)=q$ for every positive rational $q$; being increasing and agreeing with the identity on a dense subset, $f=\id$. Conversely, both functions do satisfy the equation. \end{proof} \begin{remark} The hypothesis has to be $f(x^{y})=f(x)^{f(y)}$, that is, $f$ is an endomorphism of the binary operation $\ex$. Under the weaker reading $f(x^{y})=f(x)^{y}$ the statement is false, since $f(x)=x^{c}$ satisfies $(x^{y})^{c}=(x^{c})^{y}$ for every $c>0$. Note also that $(0,\infty)$ is not a rieg, having no $0$; it is a model of the eleven high school identities, so the correct reading of \Cref{prop:KoizumiRigidity} is a rigidity statement about $\ex$-endomorphisms. \end{remark} \begin{remark}[The rig ${[0,\infty]}$ is not a rieg]\label{RemarkExtendedReals} It is natural to ask whether this rieg structure can be extended to the rig $[0,\infty]$. The answer is no. The rig ${[0,\infty]}$ cannot have a rieg structure. Suppose that there is an extension to a rieg structure. First, since $2^{\infty}=2^{\infty+1}= 2^{\infty} \ti 2$, we have $2^{\infty}\in \{0,\infty\}$. And, since $2^{\infty}(0.5)^{\infty} = 1^{\infty} =1$, we have $2^{\infty}\in (0,\infty)$, contradiction. \end{remark} \memo{What's called the exponential ring of complex numbers} \subsubsection{Numbers with Infinites} \begin{example}[Complemented natural numbers] $\N\cup\{\infty\}$ has a canonical rieg structure, which is obtained as the limit of the overflow riegs \[ \begin{tikzcd} \dots\ar[r]&\OF_{2}\ar[r]&\OF_{1}\ar[r]&\OF_{0}. \end{tikzcd} \] In this sense, this rieg is the overflow rieg with threshold $\infty$. Notice that this construction is similar to the construction of $p$-adic integers. % In \Cref{SubsectionProfinite}, we will see the profinite completion of $\N$, which is a refinement of $\N\cup\{\infty\}$ \end{example} \subsubsection{Rig with many rieg structures} \label{sssection:rigwithmany} \begin{example}[Rieg of dual numbers \memo{Constructed by Yuhi Kamio}] \label{exmp:RiegofDualNumbers} Recall that a dual number is a number plus an \dq{infinitesimal number} \[a+b\ep \ (a,b \in \R)\] The ring of infinitesimal numbers is denoted by $\R[\ep]$ and algebraically defined as $\R[\ep]=\R[x]/(x^2).$ There is a similar rieg, which we call the \demph{dual number rieg.} \begin{definition}[Dual numbers, concrete definition]\label{SubsubsectionDualNumbers} The dual number rieg $\N[\ep]$ has $\N \times \Z$ as the underlying set and its element $(n,m)$ is denoted by $n+m\epsilon$. Three operations are defined as follows: \begin{enumerate} \item $(n+m\ep)+ (n'+m'\ep)=(n+n')+(m+m')\ep$ \item $(n+m\ep)\ti (n'+m'\ep)=(nn')+(nm'+n'm)\ep$ \item The exponential depends only on the natural-number part $n'$ of the exponent: \[ (n+m\ep)\ex (n'+m'\ep) =\underbrace{(n+m\ep)\ti \dots \ti (n+m\ep)}_{n' \text{times}} = \begin{cases} 1 & (n'=0),\\ n^{n'}+n'n^{n'-1}m\ep & (n'>0). \end{cases} \] \end{enumerate} \end{definition} \end{example} This definition has a more conceptual paraphrase, with which we can easily prove that it's actually a rieg. First notice that the projection \[\N[\ep]\to \N\colon n+m\ep \mapsto n\] is a rig homomorphism to the initial rig $\N$. Thus we have the composite rig homomorphism \[\N[\ep]\to \N\to \End(\N[\ep],\ti,1),\] and this gives the exponential structure of the dual number rieg. More generally, we have the following proposition. \begin{proposition}[Rieg structure by a natural number evaluation]\label{PropositionNNevaluation} For a commutative rig $R$ and a rig homomorphism (or say, \dq{natural number evaluation}) \[v\colon R \to \N,\] $R$ admits an induced rieg structure \[R \to \N \to \End(R,\ti,1).\] \end{proposition} In other words, the exponential is given by \[x^y = \underbrace{x\ti\dots \ti x}_{v(y)\text{ times}}.\] For example, we can replace the additive group $\Z\ep$ in the definition of the dual number rieg with an arbitrary commutative monoid. \begin{example}\label{ExamplePolynomialexp} In \Cref{PropositionNNevaluation}, letting $v\colon R \to \N$ be the evaluation function \[\mathrm{ev}_0 \colon \N[x]\to \N \colon x\mapsto 0,\] we have a rieg structure on $\N[x]$ with \[f(x)^{g(x)} = f(x)^{g(0)}= \underbrace{f(x)\ti\dots \ti f(x)}_{g(0)\text{ times}}.\] \end{example} \begin{example}[Rieg of polynomials] \label{exmp:PolynomialRieg} Is it possible to have more than one rieg structure on a single rig? The answer is (not at all surprisingly) yes. A typical example is the rig of polynomials $\N[x]$. Since $\N[x]$ is the free rig with a generator $x$, rieg structures on $\N[x]$ \[\N[x] \to \End(\N[x],\ti,1)\] bijectively correspond to the elements of $\End(\N[x],\ti,1).$ \end{example} \subsection{Riegs of three elements} The degenerate rieg $\1$ is the unique $1$-element rieg. The rieg of truth values $\2$ is the unique $2$-element rieg. This subsection aims to provide all $3$-element riegs. \begin{proposition}[$3$-element riegs] There are $8$ isomorphism classes of $3$-element riegs. \end{proposition} Let $R$ be a $3$-element rieg. There are three possible characteristics $\ch(R) = (1,1), (1,2), (2,1)$. \para{Case 1: $\ch(R) = (1,2), (2,1)$} If $\ch(R) = (1,2), (2,1)$, then $R$ is the parity rieg (\Cref{exmp:ParityRieg}) or the overflow rieg with the threshold $2$ (\Cref{exmp:OverflowRiegs}). \para{Case 2: $\ch(R) = (1,1)$} So we need to classify all $3$-element riegs with characteristics $\ch(R) = (1,1)$. Let $R= \{0,1,a\}$. We distinguish cases based on the value of $1 + a$. \para{- Case 2.1: $\ch(R) = (1,1)$ and $1+a=1$} If $1+a=1$, then the rieg $R$ satisfies the equation $1+x=1$, which means that the underlying rig of $R$ is the lattice $(\{0=Latex, scale=1, every node/.style={scale=1}] \coordinate (O1) at (0,0); \coordinate (A1) at (0,2); \coordinate (B1) at (0,4); \coordinate (O2) at (1,0); \coordinate (A2) at (1,2); \coordinate (B2) at (1,4); \filldraw (O1) circle (2pt) node[left] {$0$}; \filldraw (A1) circle (2pt) node[left] {$a$}; \filldraw (B1) circle (2pt) node[left] {$1$}; \filldraw (O2) circle (2pt) node[right] {$0$}; \filldraw (A2) circle (2pt) node[right] {$a$}; \filldraw (B2) circle (2pt) node[right] {$1$}; \draw[dashed] (O1) -- (A1) -- (B1); \draw[dashed] (O2) -- (A2) -- (B2); \draw[->, line width=0.6pt] (O1) -- (O2); \draw[->, line width=0.6pt] (A1) -- (A2); \draw[->, line width=0.6pt] (B1) -- (B2); \coordinate (O3) at (2.5,0); \coordinate (A3) at (2.5,2); \coordinate (B3) at (2.5,4); \coordinate (O4) at (3.5,0); \coordinate (A4) at (3.5,2); \coordinate (B4) at (3.5,4); \filldraw (O3) circle (2pt) node[left] {$0$}; \filldraw (A3) circle (2pt) node[left] {$a$}; \filldraw (B3) circle (2pt) node[left] {$1$}; \filldraw (O4) circle (2pt) node[right] {$0$}; \filldraw (A4) circle (2pt) node[right] {$a$}; \filldraw (B4) circle (2pt) node[right] {$1$}; \draw[dashed] (O3) -- (A3) -- (B3); \draw[dashed] (O4) -- (A4) -- (B4); \draw[->, line width=0.6pt] (O3) -- (A4); \draw[->, line width=0.6pt] (A3) -- (A4); \draw[->, line width=0.6pt] (B3) -- (B4); \coordinate (O5) at (5,0); \coordinate (A5) at (5,2); \coordinate (B5) at (5,4); \coordinate (O6) at (6,0); \coordinate (A6) at (6,2); \coordinate (B6) at (6,4); \filldraw (O5) circle (2pt) node[left] {$0$}; \filldraw (A5) circle (2pt) node[left] {$a$}; \filldraw (B5) circle (2pt) node[left] {$1$}; \filldraw (O6) circle (2pt) node[right] {$0$}; \filldraw (A6) circle (2pt) node[right] {$a$}; \filldraw (B6) circle (2pt) node[right] {$1$}; \draw[dashed] (O5) -- (A5) -- (B5); \draw[dashed] (O6) -- (A6) -- (B6); \draw[->, line width=0.6pt] (O5) -- (O6); \draw[->, line width=0.6pt] (A5) -- (B6); \draw[->, line width=0.6pt] (B5) -- (B6); \coordinate (O7) at (7.5,0); \coordinate (A7) at (7.5,2); \coordinate (B7) at (7.5,4); \coordinate (O8) at (8.5,0); \coordinate (A8) at (8.5,2); \coordinate (B8) at (8.5,4); \filldraw (O7) circle (2pt) node[left] {$0$}; \filldraw (A7) circle (2pt) node[left] {$a$}; \filldraw (B7) circle (2pt) node[left] {$1$}; \filldraw (O8) circle (2pt) node[right] {$0$}; \filldraw (A8) circle (2pt) node[right] {$a$}; \filldraw (B8) circle (2pt) node[right] {$1$}; \draw[dashed] (O7) -- (A7) -- (B7); \draw[dashed] (O8) -- (A8) -- (B8); \draw[->, line width=0.6pt] (O7) -- (B8); \draw[->, line width=0.6pt] (A7) -- (B8); \draw[->, line width=0.6pt] (B7) -- (B8); \end{tikzpicture} \caption{The four possible exponentiations $x \mapsto x^a$} \label{fig:FourExponentials} \end{figure} \para{- Case 2.2: $\ch(R) = (1,1)$ and $1+a=a$} The only remaining case is $1+a=a$, since $1+a=0$ is impossible (\Cref{clm:AdditiveInverseOfOne}). Since $R$ is idempotent (\Cref{def:idempotentRieg}), the underlying rig structure is determined: \[ R \cong \langle a \mid 1+1=1, 1+a=a, a^2=a\rangle \text{ in } \Rig \] Therefore, the rieg structures on $R$ are in bijective correspondence with monoid homomorphisms $\phi \colon (R, 1, \ti) \to (R,1,\ti)$ with \begin{itemize} \item $x \ti x = x$, which always holds \item $x\ti\phi(x) = \phi(x)$, and \item $\phi^2(x) = \phi(x)$. \end{itemize} There are two such morphisms visualized in \Cref{fig:TwoExponentials}. \begin{figure}[htbp] \centering \begin{tikzpicture}[>=Latex, scale=1, every node/.style={scale=1}] \coordinate (O1) at (0,0); \coordinate (A1) at (0,2); \coordinate (B1) at (0,4); \coordinate (O2) at (1,0); \coordinate (A2) at (1,2); \coordinate (B2) at (1,4); \filldraw (O1) circle (2pt) node[left] {$0$}; \filldraw (A1) circle (2pt) node[left] {$a$}; \filldraw (B1) circle (2pt) node[left] {$1$}; \filldraw (O2) circle (2pt) node[right] {$0$}; \filldraw (A2) circle (2pt) node[right] {$a$}; \filldraw (B2) circle (2pt) node[right] {$1$}; \draw[->, line width=0.6pt] (O1) -- (O2); \draw[->, line width=0.6pt] (A1) -- (A2); \draw[->, line width=0.6pt] (B1) -- (B2); \coordinate (O3) at (3.5,0); \coordinate (A3) at (3.5,2); \coordinate (B3) at (3.5,4); \coordinate (O4) at (4.5,0); \coordinate (A4) at (4.5,2); \coordinate (B4) at (4.5,4); \filldraw (O3) circle (2pt) node[left] {$0$}; \filldraw (A3) circle (2pt) node[left] {$a$}; \filldraw (B3) circle (2pt) node[left] {$1$}; \filldraw (O4) circle (2pt) node[right] {$0$}; \filldraw (A4) circle (2pt) node[right] {$a$}; \filldraw (B4) circle (2pt) node[right] {$1$}; \draw[->, line width=0.6pt] (O3) -- (O4); \draw[->, line width=0.6pt] (A3) -- (O4); \draw[->, line width=0.6pt] (B3) -- (B4); \end{tikzpicture} \caption{The two possible exponentiations $x \mapsto x^a$} \label{fig:TwoExponentials} \end{figure} % \subsection{profinite constructions and topological rieg}\label{SubsectionProfinite} % \memo{Interpret LTE lemma} % \memo{We can do analysis, using topology. For example, something like an infinite tower of exponential} % % (related question: how about in $\Mr{\infty}{p^{\infty}}$)? This does not even exist!} % % % % \input{2023_07_23Ver/riegsOfPropositions0729} \printbibliography \end{document}