← Notes on Rieg Theory
Older Versions__20250401.tex
\documentclass{amsart}
\usepackage[left=2cm, right=2cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox}
\usepackage{blindtext}
\usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref}
\usepackage{tikz,tikz-cd}
\usepackage{cleveref}
\usepackage{xcolor}
\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}
\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);%
}}}
\usepackage{pgfplots}
\pgfplotsset{compat=1.18}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[subsection]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{todo}[theorem]{Todo}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}{Claim}[theorem]
\crefname{claim}{Claim}{Claims}
\renewcommand{\theclaim}{\thetheorem.\alph{claim}}
\newtheorem{question}[theorem]{Question}
\newtheorem{problem}[theorem]{Problem}
\newtheorem*{answer}{Answer}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{puzzle}[theorem]{Puzzle}
\newtheorem{idea}[theorem]{Idea}
\newtheorem{exercise}[theorem]{Exercise}
\newcommand{\dq}[1]{``#1"}
\newcommand{\memo}[1]{\textcolor{red}{memo: #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{\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}{\times}
\newcommand{\ex}{\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{\RigCh}{\mathbb{T}\mathrm{ame}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Nd}{\N^{\mathrm{div}}}
% \newcommand{\Nd}{\N^*}
% \newcommand{\Ndp}{\Nd_{>}}
% \newcommand{\Ndp}{\N^*}
\newcommand{\Np}{\N^*}
\newcommand{\Ch}{\mathfrak{C}}
% \newcommand{\RigfCh}{\N \times \Np}
% \newcommand{\RigCh}{\overline{\N\times \Np}}
% \newcommand{\RiegCh}{\mathbb{C}\mathrm{har}}
\newcommand{\RigCh}{\Ch_{\mathrm{rig}}}
\newcommand{\RigfCh}{{\RigCh^*}}
\newcommand{\RiegCh}{\Ch_{\mathrm{rieg}}}
\newcommand{\RiegfCh}{{\RiegCh^*}}
% \newcommand{\RiegfCh}{\mathrm{f}\mathbb{C}\mathrm{har}}
% \newcommand{\RigCh}{\overline{\N\times \Np}}
% \newcommand{\chz}{(\infty, 0)}
\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{\TTAlg}{\mathrm{Top}\T\text{-}\mathrm{Alg}}
\newcommand{\Quo}{\mathrm{Q}}
\newcommand{\fQuo}{\Quo_{\mathrm{fin}}}
\renewcommand{\j}{\mathfrak{j}}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\B}{\mathbf{B}}
\newcommand{\BN}{\B\N}
\newcommand{\BZ}{\B\Z}
\title[Rieg theory]{Notes on Rieg theory: semiring with exponentials in logic, profinite arithmetic, enumerative combinatorics, and category theory}
\author{Ryuya Hora}
\address{Graduate School of Mathematical Sciences, University of Tokyo, Tokyo, Japan}
\email{hora@ms.u-tokyo}
\date{\today}
\subjclass[2020]{}
\keywords{h}
\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$, quotient riegs of $\mathbb{N}$, the profinite completion $\N \rightarrowtail\mathbb{N} \cup \widehat{\mathbb{Z}}$, the cardinal arithmetic, the rieg of truth values $\{\bot, \top\}$, heyting algebras, 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 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{ring without negatives} (\cite{schanuel1990negative}) a \demph{rieg} is a \dq{rig with exponentials.} 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.
\para{Survey}
\begin{itemize}
\item[1942] One can see the idea of an algebra of structures, with exponential in \cite{birkhoff1942generalized}.
\item[1980] Wilkie gives a solution to Tarski's high school algebra problem \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.
\item $\RigfCh$ denotes the product poset of $\N$ and $\Np$.
\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 `rig' means `ring without negatives.' \cite{schanuel1990negative})
\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}
that satisfies
% \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$.
% Of course, every ring is a rig.
\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$.
\end{example}
% \begin{example}[Rings]\label{exmp:RingsAreRigs}
% Of course, every ring is a rig. However, we will see that
% \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 endohomorphisms $\End{(A, e, \ast)}$ admits a (typically non-commutative) 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) + g(a)$.
\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.
\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 numerous equations (\Cref{prop:EquationalDefinition}), we adopt another definition, 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}
Let us unpack the definition of a rieg. The rig homomorphism $R \to \End(R, 1, \ti)$ sends an element $x\in R$ to a (commutative) monoid homomorphism, for which we will write
\[
{-}^x \colon (R, 1, \ti) \to (R, 1, \ti).
\]
The condition that this is a monoid homomorphism is equivalent to the usual equations
\begin{itemize}
\item $1^x=1$, and
\item $(yz)^x = y^x z^x$.
\end{itemize}
For $R \to \End(R, 1, \ti)$ to be a rig homomorphism, it must preserve $0$, $1$, $+$, and $\ti$, each of which corresponds to an equation listed in \Cref{table:riegequations}.
\begin{table}[ht]
\centering
\begin{tabular}{c|c} \hline
Rig structure& Corresponding 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 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 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 $x^y$ denotes $x\ex y$ and $xy$ denotes $x\ti y$, as usual.
\end{proposition}
\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$.
\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 definition, we obtain the notion of rieg homomorphisms, as usual.
\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, we introduce here two trivial (but important!) examples of riegs: namely, the initial and terminal objects 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 natural numbers $\N = \{0,1, 2, \dots\}$ equipped with the usual zero $0$, one $1$, addition $+$, multiplication $\ti$, and exponentiation $\ex$, form 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$.
\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}
Every singleton admits the only one rieg structure, which we call a \demph{degenerate rieg} $\1$. A degenerate rieg is a terminal object of the category $\Rieg$.
\end{example}
\memo{I would write the summary of the following contents, picking a central example from each section.}
\memo{remark:as a module of itself}
\subsection{Digression: Why rigs, not rings?}
The reader may wonder: why develop a 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—indeed, there is $0^{-1}$!
\begin{proposition}\label{prop:riegIsNotRing}
If a rieg $R$ is a ring, then it is degenerate $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
We have $-1\in R$, which yields 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}
For example, exponentiation can be defined on the rig $\N$ (which is the decategorification of finite sets), but not on the ring $\Z$.
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. 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{Introduction}
Before delving into the technical details, let us first take a look at a few phenomena that will be studied in \Cref{sec:RiegsInFiniteAndProfiniteArithmetic}.
% % {Modular arithmetic with exponentials}
\subsubsection{Phenomenon 1: modular arithmetic with exponentials}\label{sssec:FiniteArithmetic}
Let us consider the following typical 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$, then $2^n \equiv 0 \pmod{8}$, so the left-hand side is congruent to $5 \pmod{8}$.
However, the quadratic residues modulo $8$ are $0$, $1$, and $4$, so $m^2 \equiv 5 \pmod{8}$ is impossible.
Therefore, we only need to check $n = 0$, $1$, and $2$.
We find that the only solution is $(n,m) = (2,3)$.
\end{answer}
In this example, when considering exponentiation modulo $8$, we should divide \dq{first exceptions}, namely three numbers $n=0,1,2$. \memo{I will write more}
% Rieg theory is involved here. The modular arithmetic of modulo $b$ requires first exceptions and that the number of them, $a$ must (not surprisingly) be greater than or equal to any number that appears as an exponent in the prime factorization of $b$. The rieg of modulo $b$ with first exceptions less than $a$ is denoted by $\Mr{a}{b}$. For example, in the above equation, we utilized the modulo rieg $\Mr{3}{8}$. In this section, we classify what $a,b$ is possible.
\memo{Write a picture}
\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 find an answer; iteration.F irst, take an arbitrary natural number $n$, like $n=2024$. Then, repeatedly replace $n$ by the last $4$-digits of $3^n$\footnote{Thanks to the repeated squaring algorithm, a computer can conduct this calculation in a short time. \memo{say, by Wolfram alpha}}.
\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}
\begin{answer}
$n=5387$ is the only answer.
\end{answer}
Then, it is natural to ask whether we can go farther:
\begin{question}
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 number $n = a_k \dots a_1$ (interpreted in decimal)
satisfies the congruence
\[
3^n \equiv n \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}
\memo{Explain how this is an instance of Banach fixed point theorem. Explain why it works for $\Z_{10}$ but not for $\Z_5$. }
% 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 a reminiscent of $p$-adic integers.
\memo{write something} However, in this case, the exponential operation is involved.
In this section, we will construct profinite systems of numbers, which can be regarded as a $p$-adic number system with exponentials. Using that structure, we will be able to answer the above question easily.
\memo{How to find it. }
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}$, 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}
\memo{This should be unique. If $3^{\beta} = \beta$, then $\beta \equiv 87 \mod 100$. Since $\alpha \equiv \beta \mod{100}$, $\alpha = 3^{\alpha} \equiv 3^{\beta} = \beta \mod{1000}$}
\subsubsection{Phenomenon 3: Well-defined modulo exponentials}\label{sssec:Well-definedModuloExponentials}
$1,2,6,42,1806$
\subsection{The Burris-Lee theorem: Classification of quotient riegs of \texorpdfstring{$\N$}{N}}
Modular arithmetic is based on considering quotient rings of the (initial) ring $\Z$. Similarly, by considering quotient riegs of the (initial) rieg $\N$, we aim to obtain tools for a modular arithmetic involving exponentiation. The goal of this subsection is to introduce the Burris–Lee theorem \cite{burris1992small,burris1993tarski}, which provides a classification of all quotient riegs of $\N$. Although the definitions are slightly different, all of the crucial arguments in this subsection are due to \cite{burris1992small,burris1993tarski}. For the reader's convenience, the full details of the proof will be given in this subsection.
% \memo{On the terminology \dq{modulo riegs}}
Let us start by clarifying what `quotient rieg' means.
\begin{definition}[Quotient rieg]\label{def:quotientRieg}
A \demph{quotient rieg} of a rieg $R$ is a rieg $R'$ equipped with a surjective rieg homomorphism $R\twoheadrightarrow R'$.
\end{definition}
Since $\N$ is the initial rieg, there exists a unique rieg homomorphism $\N \to R$ for any rieg $R$. Therefore, it makes sense to ask whether a given rieg $R$ is a quotient rieg of $\N$ without explicitly referring to the homomorphism $\N \to R$.
\subsubsection{Examples of quotient riegs of \texorpdfstring{$\N$}{N}}
Before we get into the theoretical considerations, let us list some examples of quotient riegs of $\N$. The reader does not need to check that they are actually riegs, since \Cref{thm:BurrisLeeTheorem} will verify everything.
\begin{example}[Two trivial examples]
The degenerate rieg $\1$ (\Cref{exmp:ThedegenerateRieg}) and $\N$ itself are trivially quotient riegs of $\N$.
\end{example}
\begin{example}[The rieg of truth values]\label{exmp:RiegOfTruthValues}
As we will see later, \memo{cite the section} the set of truth values $\2 = \{\bot, \top\}$ has a natural rieg structure $(\2, \bot, \top, \lor, \land, \leftarrow)$.
% \begin{itemize}
% \item $0$ is the $\bot$
% \item $1$ is $\top$
% \item $x+y$ is $x \lor y$
% \item $xy$ is $x\land y$
% \item $x^y$ is $y \to x$
% \end{itemize}
The function $\text{IsPositive}\colon \N \twoheadrightarrow \2$ defined by
\[
\text{IsPositive}(n) \coloneqq
\begin{cases}
\top &(n>0)\\
\bot &(n=0)
\end{cases}
\]
is the unique rieg homomorphism $\N \to \2$, which witnesses that $\2$ is a quotient rieg of $\N$.
\end{example}
\begin{example}[Parity rieg]\label{exmp:ParityRieg}
As a slightly more nontrivial example, the natural surjection
\[
\mathbb{N} \twoheadrightarrow \{0,\ \text{positive odd},\ \text{positive even}\}
\]
induces a quotient rieg structure on the $3$-element set $\{0,\ \text{positive odd},\ \text{positive even}\}$, which we refer to as the \demph{parity rieg}. Notice that the surjection
\[
\mathbb{N} \twoheadrightarrow \{\text{odd}, \text{even}\} =\Z/2\Z
\]
does not induce a rieg structure on the set $\{\text{odd}, \text{even}\}=\Z/2\Z$, since $2^0=1$ is odd and $2^2=4$ is even. (This also follows from \Cref{prop:riegIsNotRing}.)
\end{example}
\begin{example}[Overflow riegs]\label{exmp:OverflowRiegs}
For any natural number $n \geq 0$, we define the \demph{overflow rieg with threshold $n$} on the $(n+1)$-element set
\[
\{0, 1, 2, \dots, n-1, \TB\}.
\]
It will be denoted by $\OF_n$.
The rieg structure is induced by the natural surjection
\[
\mathbb{N} \twoheadrightarrow \{0, 1, 2, \dots, n-1, \TB\}.
\]
Intuitively, the symbol $\TB$ stands for “too big to remember”: any number greater than or equal to $n$ is said to \emph{overflow} and is mapped to $\TB$.
For example, in the overflow rieg with threshold $5$, we have $2^3=\TB$, $0^{\TB}=0$, and
\begin{align*}
0^\TB \cdot 2^3+1^{4+2} +2^{1^{3+2}}
&=0\cdot \TB+1^{\TB} +2^{1^{\TB}} \\
&=0+1+2^{1} \\
&=3.
\end{align*}
The overflow rieg with threshold $n=0$ (respectively, $n=1$) is the degenerate rieg in \Cref{exmp:ThedegenerateRieg} (respectively, the rieg of truth values in \Cref{exmp:RiegOfTruthValues}).
\end{example}
\subsubsection{Quotient rigs of \texorpdfstring{$\N$}{N}}
Every quotient rieg $\N \twoheadrightarrow R$ is obviously a quotient rig of $\N$. So we first classify all quotient rigs of $\N$. Since $\N$ is initial also in the category of rigs $\Rig$, it makes sense to ask whether a given rig $R$ is a quotient rig of $\N$ without mentioning the rig homomorphism $\N \to R$.
\begin{definition}[$\Mr{a}{b}$]\label{def:QuotientRigMrab}
For a natural number $a\geq 0$ and a positive integer $b>0$, we define a surjection $\N \twoheadrightarrow\Mr{a}{b}$ onto the $(a+b)$-element set $\Mr{a}{b}\coloneqq \N/{\sim_{a,b}}$, where $\sim_{a,b}$ denotes the equivalence relation defined by
\[n \sim_{a,b} m \iff (n=m)\lor ((n,m\geq a) \land (n\equiv m \mod{b})). \]
\end{definition}
\Cref{fig:ModuleRieg} is a visualization of $\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}
\begin{proposition}[Quotient rigs of $\N$]\label{prop:quotientrigs}
% Let $a\geq 0$ be a natural number and $b>0$ be a positive integer.
For a natural number $a\geq 0$ and a positive integer $b>0$, the surjection $\N \twoheadrightarrow\Mr{a}{b}$ induces a rig structure on $\Mr{a}{b}$. Conversely, every quotient rig of $\N$ is either the identity $\id_\N \colon \N \to \N$ or is of this form.
% \begin{itemize}
% \item The surjection $\N \twoheadrightarrow\Mr{a}{b}$ induces a rig structure on $\Mr{a}{b}$.
% \item The rig $\Mr{a}{b}$ is
% \end{itemize}
\end{proposition}
\begin{proof}
\memo{easy...}
\end{proof}
% For example, (the underlying rig of) the degenerate rieg is $\Mr{0}{1}$, the truth value rieg $\2$ is $\Mr{1}{1}$, and the parity rieg is $\Mr{1}{2}$. \memo{Overflow riegs}
% \begin{proposition}
% % For any $a\geq 0$ and $b>0$, $\Mr{a}{b}$ admits the unique rig structure such that the canonical surjection $\N \twoheadrightarrow \Mr{a}{b}$ is a rig homomorphism.
% A rieg structure on the rig $\Mr{a}{b}$ is unique, if it exists.
% % Every quotient of $\N$ is $\N$ itself or otherwise of the form of $\Mr{a}{b}$ for some $a\geq 0$ and $b>0$.
% \end{proposition}\memo{Modify this later..}
If the rig $\Mr{a}{b}$ admits a rieg structure, the unique rig homomorphism $\N \twoheadrightarrow \Mr{a}{b}$ should be a rieg homomorphism.
Therefore, a rieg structure on the rig $\Mr{a}{b}$ is unique if it exists. So it makes sense to ask whether $\Mr{a}{b}$ is a rieg. Not every $\Mr{a}{b}$ is a rieg. For example, $\Mr{0}{b} \cong \Z/b\Z$ is a rieg if and only if $b=1$ (see \Cref{exmp:ThedegenerateRieg} and \Cref{prop:riegIsNotRing}). In the rest of the present subsection, we will study a sufficient and necessary condition for $(a,b)$ to make $\Mr{a}{b}$ a rieg in terms of elementary number theory. (\Cref{fig:PlotsOfQuotientRiegsOfN} shows the small pairs of $(a,b)$ that makes $\Mr{a}{b}$ a rieg.)
\subsubsection{shifted-Carmichael numbers}
As a preparation of \Cref{thm:BurrisLeeTheorem} (and the following contents), we introduce the notion of shifted-Carmichael numbers.
% Before stating the classification theorem, we introduce two terminologies.
\begin{definition}[Shifted-Carmichael number]
A positive integer $n$ is said to be \demph{shifted-Carmichael} if
\[
p \mid n \implies (p-1) \mid n
\]
for any prime number $p$.
\end{definition}
The list of shifted-Carmichael numbers begins with:
\[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, \dots.\]
Notice that there are infinitely many shifted-Carmichael numbers since $k!$ is shifted-Carmichael for any $k\geq 0$.
\begin{remark}[Comparison with Carmichael numbers]
Recall that a positive integer $n$ is said to be a \demph{Carmichael number} if
% \begin{description}
% \item[Carmichael] for any $x \in (\Z/n\Z)^{\times}$, $x^{n-1} \equiv 1 \mod{n}$
% \end{description}
\begin{center}
for any $x \in (\Z/n\Z)^{\times}$, $x^{n-1} \equiv 1 \mod{n}$.
\end{center}
On the other hand, \Cref{lem:AlgebraicCharacterizationOfShifted_CarmichaelNumbers} will show that a positive integer $n$ is shifted-Carmichael if and only if
% \begin{description}
% \item[shifted-Carmichael] for any $x \in (\Z/n\Z)^{\times}$, $x^{n} \equiv 1 \mod{n}$.
% \end{description}
\begin{center}
for any $x \in (\Z/n\Z)^{\times}$, $x^{n} \equiv 1 \mod{n}$.
\end{center}
% Compared with the algebraic characterization of shifted-Carmichael numbers (\Cref{lem:AlgebraicCharacterizationOfShifted_CarmichaelNumbers}),
The only difference is that the exponent $n$ is shifted by one. This is a reason for our terminology, shifted-Carmichael\footnote{Another passive reason is that many other names, including \demph{anti-Carmichael numbers}, are already used.}.
A natural number $n$ cannot be simultaneously Carmichael and shifted-Carmichael, unless $n$ is $1$ or $2$.
\end{remark}
\subsubsection{The Burris-Lee theorem}
To state \Cref{thm:BurrisLeeTheorem}, we need one more (very elementary) notion:
\begin{definition}($H(n)$)\label{def:Hn}
For a positive integer $n>0$, we write $H(n)$ for the maximum exponent in the prime factorization.
\end{definition}
More concretely, for a positive integer $n>0$ with the prime factorization $n={p_1}^{k_1}\dots {p_l}^{k_l}$, the value of $H(n)$ is given by $H(n) \coloneqq \max(k_1 , \dots, k_n)$.
The notation $H(n)$ is borrowed from \cite{niven1969averages}\footnote{In \cite{niven1969averages}, $H(1)$ is defined to be $1$, while we adopt another convension $H(1) =0$.}. The first $9$ values of $H(n)$ are listed in \Cref{tab:Hn}.
\begin{table}[ht]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|l|l|l} \hline
$n$& 1& 2& 3& 4& 5& 6 & 7&8 &9\\ \hline
$H(n)$& 0& 1& 1& 2& 1& 1& 1&3 &2\\ \hline
\end{tabular}
\caption{First values of $H(n)$}
\label{tab:Hn}
\end{table}
% For example, the values of $\H(n)$ for small $n$ are $\H(1)=0, \H(2)=1, \H(3)=1, \H(4)=2, \H(5) = 1, \H(6)=1, \H(7)=1, \H(8)=3$.
\begin{theorem}[The Burris-Lee theorem \cite{burris1992small, burris1993tarski}]\label{thm:BurrisLeeTheorem}
For $a\geq 0$ and $b>0$, the rig $\Mr{a}{b}$ admits a rieg structure if and only if
% $b$ is a shifted-Carmichael number whose dimension is at most $a$.
\begin{enumerate}
\item $a\geq \H(b)$ and
\item $b$ is shifted-Carmichael.
\end{enumerate}
\end{theorem}
As a result, we obtain the complete (infinite) list of modulo riegs (\Cref{PictureListOfModuloRiegs}).
\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,
% title={Shifted-Carmichael},
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{The list of quotient riegs of $\N$}
\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{The complete list of modulo riegs}
\label{PictureListOfModuloRiegs}
\end{shaded}
\end{figure}
\subsubsection{Examples and corollaries}
As promised, this classification theorem implies non-trivial properties about general riegs. The following corollary is particularly impressive.
% As a corollary of the classification theorem, we obtain the following proposition:
\begin{corollary}[Classification of characteristics, case $a=1$ \cite{burris1992small, burris1993tarski}]\label{CorollaryClassificationOfCharacteristics}
For a rieg $R$, if there exists the minimum positive integer $n$ such that
\[1=1+\underbrace{1+\dots +1}_{n},\]
then there are only five possible values of $n$, $n=1,2,6,42,1806$.
\end{corollary}\memo{I thought this might be a new result.}
\begin{proof}
This is equivalent to saying that $n= 1,2,6,42,1806$ are the only shifted-Carmichael numbers with $1\geq H(n)$. If $n$ is a $1$-dimensional shifted-Carmichael number and $p$ is the maximum prime factor, then $n/p$ is also a ($0$ or $1$-dimensional) shifted-Carmichael number and $p-1$ is a divisor of $n/p$. Therefore, we can inductively generate all $1$-dimensional shifted-Carmichael numbers. By concrete calculations, we can check that the inductive procedure stops when $n=1806$.
The concrete calculation is conducted as follows:
Start with $n=1$. Adding $1$ to the divisor of $n=1$ and checking if it is prime, we find prime $1+1=2$ and newly obtain $n=1*2=2$.
Again, adding $1$ to the divisors of (newly obtained) $n=2$ and checking if they are prime, we find two prime numbers $2$ and $3$. Thus we obtain a new number $n=2*3=6$.
We repeat this procedure.
Adding $1$ to the divisors of $n=6$ and checking if they are prime, we find prime numbers $2, 3$, and $7$ and obtain $n=6*7=42$.
Again, adding $1$ to the divisors of $n=42$ and checking if they are prime, we find primes $2, 3, 7$, and $43$ and newly obtain $n=42*43=1806$. Adding $1$ to the divisors of $n=1806$ and checking if they are prime, we find only the already found primes $2,3,7,43$. (For example, $86+1=3\cdot 29$, $301+1=2\cdot 151$, and $1806+1 = 13\cdot 139$.) Thus this procedure is over, and all possible $n$ are $1,2,6,42,1806$.
\end{proof}
\memo{Sylvester's sequence}
\begin{conjecture}
There are infinitely many 2-dimensional shifted-Carmichael numbers.
\end{conjecture}
\cite{OEISsyl}\cite{burris1992small, burris1993tarski},
By a computer calculation, we know there is a $2$-dimensional shifted-Carmichael number bigger than $10^{10000}$.
\memo{In the case of $1$-dimensional shifted-Carmichael numbers, there are only $4$ different prime number appear, $p=2,3,7,43$. By computer calculation, we observed that at least $1000$ prime numbers appear in $2$-dimensional shifted-Carmichael numbers.}
\begin{example}
For any non-negative integer $n$, $1$ is a shifted-Carmichael number whose dimension is $0$. Thus we obtain a rieg $\Mr{n}{1}$, which is isomorphic to the overflow rieg. \memo{ref, 2-adic and n=3 case}
\end{example}
\begin{example}
For any non-negative integer $n$, $2^n$ is a shifted-Carmichael number whose dimension is $n$. Thus we obtain a rieg $\Mr{n}{2^n}$. \memo{ref}
\end{example}
\begin{example}
How about $10^n$? For $n=1$, $10$ is not a shifted-Carmichael number. That means we cannot do modular arithmetic only with
% $\mod{10}$, i.e.,
the last digits. For example, $3^3=7 \mod 10$ but $3^{13}=3 \mod 10$.
% For example, $3^3=27 \equiv 7 \mod 10$ but $3^{13}=1594323\equiv 3$)
However, for $n\geq 2$, $10^n$ is a shifted-Carmichael number whose dimension is $n$. Thus we obtain a rieg $\Mr{n}{10^n}$. Later, we utilize those riegs to define a profinite riegs. \memo{ref}
\end{example}
% However, not all $\Mr{a}{b}$ has a rieg structure. The obvious restriction is
% \begin{itemize}
% \item $a=0 \implies b=1$,
% \end{itemize} and for something a bit more non-trivial,
% \begin{itemize}
% % \item the order of elements of $(\Z/b\Z)^{\times}$ must be divisors of $b$.
% \item if a prime number $p$ divides $b$, then $p-1$ must divide $b$.
% \end{itemize}
% As we will see later, for $a=1$, there are exactly five possible $b$, namely $1,2,6,42,1806$.
% \subsection{Characteristics of riegs}
% \begin{definition}
% The \demph{characteristic} of a rieg is \memo{write}
% \end{definition}
% \memo{Solve some Diophantus equation utilizing those riegs}
% \begin{definition}\label{DefinitionOrderCharacteristics}
% \end{definition}
% \subsection{Relation to other algebraic structures}
\subsection{The complete lattice of characteristics}
From this subsection, we will use the following notations:
\begin{itemize}
\item $\RigfCh$ denotes the product poset $\N \times \Np$.
\item $\RigCh$ denotes the poset $\RigfCh$ with a formal maximum element $\chz$.
\item $\RiegfCh$ denotes the full sub poset of $\RigfCh$ defined by
\[
\RiegfCh\coloneqq \{(a,b \in \RigfCh\mid b \text{ is shifted-Carmichael and }a\geq H(b)\}.
\]
\item $\RiegCh$ denotes the poset $\RigfCh$ with a formal maximum element $\chz$.
\end{itemize}
These notations are based on a general theory of characteristics (See \Cref{sec:generaltheoryOfCharacteristics}). Notice that $\RigCh$ (respectively, $\RiegCh$) is isomorphic to the complete lattice of quotient rigs (respectively, quotient riegs) of $\N$. Even in those poset, we write $(a,b) \leq (a',b')$ for the associated order, which always means that $a\leq a'$ in the usual order, and $b\mid b'$. Of course, the formal maximum element $\chz$ is defined to be maximum.
\subsubsection{Chracteristics of a rieg}
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$. The most fundamental fact in field theory is that, if the ring $R$ is a field, its characteristic should be a prime number (or $0$). In other words, the existence of division imposes a number theoretic condition on its characteristic.
We will define a similar notion for rigs and riegs. Recall that $\N$ denotes the usual poset of natural numbers, that $\Np$ denotes the poset of positive integers with the divisibility order, and that $\RigfCh$ denotes their product poset (\Cref{not:notationsOfNaturalNumberRelatedSystems}).
\begin{definition}[Characteristic]\label{def:CharacteristicOfRigsAndRiegs}
The \demph{characteristic} of a rig (or a rieg) $R$, which is denoted by $\ch R$, is the minimum pair
% \memo{Clarify the meaning of \dq{minimum.} But I think there is no room for confusion...?}
$(a,b) \in \RigfCh$ 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, $\ch R$ is defined to be $\chz$.
\end{definition}
\begin{corollary}[Burris-Lee theorem in terms of rieg characteristics \cite{burris1992small, burris1993tarski}]
A pair $(a, b)\in \RigCh$ is a characteristic of a rieg if and only if $(a,b)\in \RiegCh \subset \RigCh$.
\end{corollary}
This is analogous to the fact that the characteristics of fields should be prime, while those of rings can take all natural numbers.
\begin{remark}[Is this definitin natural?]
We slightly changed the definition of characteristic from the case of rings. In fact, the exact same definition does not work well. If there exists a positive integer $n$ such that $0 = n$, then $n - 1$ must be the additive inverse of $1$, and the rieg is isomorphic to the degenerate rieg (\Cref{prop:riegIsNotRing}). Our definition follows a general theory of characteristics of algebraic theory \Cref{sec:generaltheoryOfCharacteristics}.
\end{remark}
This order relation can be rephrased in terms of rigs and riegs:
\begin{proposition}
For $(a,b), (a',b') \in \RigCh$, $(a,b) \geq (a',b')$ if and only if there is a rig homomorphism $\Mr{a}{b} \to \Mr{a'}{b'}$.
Furthermore, in the case where $(a,b), (a',b') \in \RiegCh$, $(a,b) \geq (a',b')$ if and only if there is a rieg homomorphism $\Mr{a}{b} \to \Mr{a'}{b'}$.
\end{proposition}
In other words, $\RigCh$ is isomorphic to the complete lattice of the quotient rigs of $\N$, and $\RiegCh$ is isomorphic to the complete lattice of the quotient riegs of $\N$.
\begin{lemma}\label{lem:Shifted_Carmichaelapprox}
For any positive integer $b$, there is the minimum shifted-Carmichael number $b'$ such that $b$ divides $b'$.
\end{lemma}
\begin{proof}
Here is a concrete algorithm:
If $b$ is shifted-Carmichael, then return $b$.
If $b$ is not shifted-Carmichael, then take the maximum prime number $p_b$ such that $p_b$ divides $b$ but $p_b -1$ does not divide $b$.
And (recursively) return the minimum shifted-Carmichael number $b'$ such that $\lcm (b, p_b-1)$ divides $b'$.
This algorithm halts, since the prime number $p_b$ becomes smaller and smaller. It is easy to prove the minimality.
\end{proof}
\begin{example}[The minimum shifted-Carmichael number that is divided by $11$]
First, start with $b=11$, we replace it with $\lcm (11, 11-1)=110$. Next, we replace $b=110$ with $\lcm (110,5-1)= 220$ and conclude $220$ is the least shifted-Carmichael number that is divided by $11$.
\end{example}
\begin{proposition}[Shifted-Carmichael approximation]\label{prop:riegCharacteristicApprox}
For any $(a,b)\in \RigCh$, there is the minimum $(a',b')\in \RiegCh$ such that
$(a,b)\leq (a',b')$.
Furthermore, if $(a,b)\in \RigfCh$, then $(a',b')\in \RiegfCh$.
\end{proposition}
\begin{proof}
If $(a,b)= \chz$, then $(a',b')=\chz$. We may assume $(a,b)\in \RigfCh$.
Due to \Cref{lem:Shifted_Carmichaelapprox}, we can take the minimum shifted-Carmichael number $b'$ that is divided by $b$. Then, define $a'$ by $a\coloneqq \max(a,\H{(b)})$.
\end{proof}
In categorical terms,
\Cref{prop:riegCharacteristicApprox} states that the two embedding (order-preserving) functions
\[\RiegCh \hookrightarrow \RigCh \]
\[\RiegfCh \hookrightarrow \RigfCh \]
have a left adjoint.
% . \memo{This data defines a \dq{closure operator} on $\RigCh$. but not preserving meets.}
As an immediate corollary, we obtain the following propositions.
\begin{proposition}
$\RiegfCh$ is unbounded in $\N\times \N_{>}$.
\end{proposition}
\begin{proposition}[]
For any $n\in \N$, the canonical rig homomorphism
\[\N \twoheadrightarrow \Z/n\Z\] can be factored as
\[\N \twoheadrightarrow \Mr{a}{b}\twoheadrightarrow \Z/n\Z,\]
where $\N \twoheadrightarrow \Mr{a}{b}$ is a rieg homomorphism and $\Mr{a}{b}\twoheadrightarrow \Z/n\Z$ is a rig homomorphism.
\end{proposition}
\begin{proof}
We can take $(a,b)$ by applying \Cref{prop:riegCharacteristicApprox} to $(0,n)\in \N\times \N_{>}$.
\end{proof}
\memo{mention: The part of phenomena: $(0,8) \mapsto (3,8)$, and $(0,10) \mapsto (2, 20)$}
\memo{Interpret LTE lemma}
\memo{We can do analysis, using topology. For example, something like an infinite tower of exponential}
\memo{Are there infinitely many solutions for $x^x =x$ in $\Mr{\infty}{10^{\infty}}$?}
\memo{Write on the unique solution of $3^x =x$ in $\Mr{\infty}{10^{\infty}}$.}
\subsection{The topological rieg of profinite natural numbers}
Recall that the profinite completion of an algebraic structure $A$ is defined as the limit of its finite quotient algebras (in the category of algebras or in the category of topological algebras) (\Cref{ssec:GeneralTheoryOfProfiniteAlgebras}). Our aim in this subsection is to analyze the algebraic and topological structures of $\proN$.
\begin{definition}
\demph{The rieg of profinite integers} $\proN$ is defined as the profinite completion of the initial rieg $\N$.
\end{definition}
In other words, the rieg $\proN$ is defined as the limit
\[
\proN \coloneqq \lim \left (\RiegfCh^{\op} \to \Rieg \right ).
\]
Although it is possible to calculate it by definition, the shape of the above diagram $\RiegfCh^{\op}$ is a little tricky to calculate. So we will make it simpler by the next lemma.
\begin{lemma}\label{lem:SimplifyingWithFactorial}
For any $n\in \N$, we have $(n, n!)\in \RiegfCh$. Furthermore, for any $(a,b)\in \RiegfCh$, there exists an $n\in \N$ such that $(a,b ) \leq (n, n!)$.
\end{lemma}
\begin{proof}
For any $n\in \N$, the factorial $n!$ is shifted-Carmichael since if $p\mid n!$ then $p\leq n$, which implies $p-1 \leq n$ and $(p-1)\mid n!$. Furthermore, $n\geq H(n!)$ holds since the exponent of $p$ in the prime factorization of $n!$, which is denoted by $v_p(n!)$ is given by Legendre's formula
% \[
% \sum_{k=1}^{\infty} \left\lfloor {\frac{n}{p^k}}\right\rfloor
% \]
and is bounded above by $n$ as follows:
\[
v_p(n!) = \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.
\]
Therefore, we obtain a rieg $(n, n!)\in \RiegfCh$.
The latter part follows since we can define $n$ by $n\coloneqq \max(a,b)$.
\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}
\Cref{lem:SimplifyingWithFactorial} proves that the order preserving function
\[
\N \to \RiegfCh: n\mapsto (n,n!)
\]
is well-defined and is a final functor. Therefore, the limit of the shape of $\RiegfCh^{\op}$ is reduced to the limit of the shape of $\N^{\op}$.
\end{proof}
\begin{theorem}
The underlying set of the rieg of profinite integers $\proN$ is given by
\[\textstyle \proN = \N \sqcup \proZ,\]
where $\proZ$ denotes the usual set of profinite integers. The canonical projection map $\pi_{a,b}\colon \proN \to \Mr{a}{b}$ is given by the canonical functions
% \[
% \pi_{a,b} (x) =
% \begin{cases}
% &(x=n \in \N)\\
% \end{cases}
\[
\N \twoheadrightarrow \Mr{a}{b}
\]
and
\[
\proZ \twoheadrightarrow \Z/b\Z \rightarrowtail \Mr{a}{b}.
\]
\end{theorem}
\begin{proof}
Due to \Cref{lem:SimplifyingWithFactorial} (and \Cref{lem:LimitsofTopologicalAlgebras}), the elements of $\proN$ are in bijevtive correspondence with the element of
\[
\{(x_n \in \Mr{n}{n!})_{n\geq 0}\mid \forall n\geq 0,\; \pi_{n+1} (x_{n+1}) = x_{n}\}.
\]
Let $(x_n \in \Mr{n}{n!})_{n\geq 0}$
% be a sequence in the right hand side set. $(x_n \in \Mr{n}{n!})_{n\geq 0}$,
If at least one term $x_n \in \Mr{n}{n!}$ is in the \dq{first exceptions,} in other words written as $x_n=k \in \Mr{n}{n!}$ for some $0\leq k<n$, then we have
\[
x_n =
\begin{cases}
k & (n> k)\\
[k] & (n\leq k).
\end{cases}
\]
Otherwise, every term $x_n$ belongs to the subset $x_n \in \Z/n!\Z \subset \Mr{n}{n!}$. Therefore, $x_n$ can be naturally regarded as an element of $\proZ = \lim_{n\to \infty}(\Z/n! \Z)$.
% Since the forgetful functor $U \colon \Rieg \to \Set$ creates all small limits, the element of $\proN$ corresponds to a family of elements $\{x_{a,b} \in \Mr{a}{b}\}_{(a,b) \in \RiegfCh}$ such that if $(a,b) \leq (a',b')$ then $x_{a,b}= \mathrm{pr} (x_{a',b'})$, where $\mathrm{pr}$ denotes the canonical comparison homomorphism $\Mr{a'}{b'}\twoheadrightarrow \Mr{a}{b}$.
\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{remark}
$\Mr{\infty}{10^{\infty}}$.
\end{remark}
% \subsection{Discrete Dynamical System on Profinite Integers}
\subsection{Metrics}
\begin{definition}[Period function $\p$]
The \demph{period function} $\p \colon \Np \to \Np$ sends a positive integer $n\in \Np$ to the minimum positive integer $\p(n)\in \Np$ such that
\[
\forall x\in (\Z/n\Z)^{\times},\; x^{\p(n)} \equiv 1 \mod n.
\]
\end{definition}
\begin{lemma}\label{lem:ExplicitDescriptionOfPeriodFunction}
For a positive integer $n=2^e\times p_1^{e_1} \times \dots \times p_k^{e_k}$, $\p(n)$ is the least common multiple of
\begin{itemize}
\item $\begin{cases}
1 & (e=0,1)\\
2 & (e=2)\\
2^{e-2} & (e\geq 3)\\
\end{cases}$, and
\item $(p_i -1)p_i^{e_i -1}$ for each $1\leq i \leq k$.
\end{itemize}
\end{lemma}
\begin{proof}
This follows from the following fact
\[
(\Z/p^e\Z)^{\times} \cong
\begin{cases}
\Z/1\Z &(p=2, e=1)\\
\Z/2\Z \times \Z/2^{e-2}\Z &(p=2, e\geq 2)\\
\Z/(p-1)p^{e-1} \Z &(p>2, e\geq 1),
\end{cases}
\]
and the group isomorphism
\[
(\Z/n\Z)^{\times} \cong (\Z/2^e\Z)^{\times} \times (\Z/p_1^{e_1})^{\times}\times \dots \times (\Z/p_k^{e_k})^{\times}.
\]
\end{proof}
\begin{definition}[Jump function]\label{def:JumpFunction}
The \demph{jump function} $\j \colon \Np \to \Np$ is the right adjoint of $\p \colon \Np \to \Np$.
\end{definition}
\begin{para}{Explicit construction of $\j$.}
% \begin{proof}[Explicit construction of $\j$.]
Let $n\in \Np$ be a positive integer, and
% Let $1=d_0< \dots <d_{l}=n$ be the list of all divisors of $n$.
% Let
$p_0<\dots <p_{k} $ be the list of all prime numbers in the set $\{d+1\mid d\text{ is a divisor of } n\}$.
% $\{d_0+1, \dots ,d_l +?1\}$.
Notice that $p_0$ is always equal to $2$. Then, $\j(n)$ is given by
% \[
% \begin{cases}
% 2\times p_2^{v_{p_2}(n)+1}\times \dots \times p_k^{v_{p_k}(n)+1} & (\text{$n$ is odd})\\
% 2^{v_2(n) +2}\times p_2^{v_{p_2}(n)+1}\times \dots \times p_k^{v_{p_k}(n)+1} & (\text{$n$ is even})
% \end{cases}
% \]
\[
\j(n) =
p_1^{v_{p_1}(n)+1}\times \dots \times p_k^{v_{p_k}(n)+1} \times
\begin{cases}
2 & (\text{$n$ is odd})\\
2^{v_2(n) +2} & (\text{$n$ is even}).
\end{cases}
\]
\end{para}
% More explicitly,
% (related question: how about in $\Mr{\infty}{p^{\infty}}$)? This does not even exist!}
%
% \input{2023_07_23Ver/riegsOfPropositions0729}
\begin{lemma}
For a positive integer $n\in \Np$, the following conditions are equivalent:
\begin{itemize}
\item $n$ is shifted-Carmichael.
\item $\p(n) \mid n$.
\item For any $x\in (\Z/n\Z)^\times$, $x^{n}\equiv 1 \mod n$.
\item $n\mid \j(n)$.
\end{itemize}
\end{lemma}\memo{cite \Cref{lem:AlgebraicCharacterizationOfShifted_CarmichaelNumbers}}
\begin{example}[Values of $\j(n)$]
The first values of the function $\j(n)$ are given as follows:
\begin{itemize}
% \item $\j(1) = 2^1 = 2$.
% \item $\j(2) = 2^{1+2}\times (2+1)^1 = 24$.
% \item $\j(3) = 2^1 = 2$.
% \item $\j(4) = 2^{2+2}\times (2+1)^1\times (4+1)^1 = 240$
% \item $\j(5) = 2^1 = 2$.
% \item $\j(6) = 2^{1+2} \times (2+1)^2 \times (6+1)^1 = 504$.\\
% $\vdots$
% \item $\j(24) = 2^{3+2}\times (2+1)^2 \times (4+1)^1\times (6+1)^1\times (12+1)^1 = 131040$\\
\item $\j(1) = 2$.
\item $\j(2) = 2^3\times 3 = 24$.
\item $\j(3) = 2$.
\item $\j(4) = 2^4\times 3\times 5= 240$
\item $\j(5) = 2$.
\item $\j(6) = 2^3 \times 3^2 \times 7 = 504$.\\
$\vdots$
\item $\j(24) = \j^3(1)= 2^5\times 3^2 \times 5\times 7\times 13 = 131040$\\
$\vdots$
\item $\j(131040) = \j^4(1)=
2^7 \times 3^3 \times 5^2 \times 7^2 \times 11 \times 13^2 \times 17 \times 19 \times 29 \times 31 \times 37 \times 41 \times 43 \times 53 \times 61 \times 71 \times 73 \times 79 \times 97 \times 113 \times 127 \times 131 \times 157 \times 181 \times 211 \times 241 \times 281 \times 313 \times 337 \times 421 \times 521 \times 547 \times 631 \times 673 \times 911 \times 937 \times 1009 \times 1093 \times 1171 \times 1249 \times 1873 \times 2017 \times 2081 \times 2341 \times 2521 \times 2731 \times 3121 \times 3361 \times 6553 \times 8191 \times 8737 \times 14561 \times 16381 \times 21841 \times 26209 \times 65521 \times 131041\\
=7901305745373962606443311460923388877392435575153307522511397623413909251201188609878243610\\9212612531421258837566664694002671767681076647237504997468800$
\end{itemize}
\end{example}
\begin{lemma}
For any $n,m\in \Np$, there exists a natural number $k\in \N$ such that $n\mid \j^k(m)$.
\end{lemma}
\begin{proof}
% Since $\j$ is a right adjoint, $\j$ is order preserving. So we may assume $m=1$.
% We will prove that, for every $n\in \Np$, there exists $k\in \N$ such that $n\mid \j^k(1)$.
By the adjointness $\p \dashv \j$, we have the equivalence
\[
n\mid \j^k(m) \iff \p^k(n) \mid m.
\]
% the condition $n\mid \j^k(1)$ is equivalent to $\p^k(n) \mid 1$.
Therefore, it is enough to prove that the sequence $n \geq \p(n)\geq \p^2(n)\geq \dots$ contains $1$. This follows since $\p(n)<n$ for any $n\geq 2$.
% , by the induction (with respect to the usual order of natural number). The bottom case $n=1$ is trivial since $n=1\mid \j^0(1) = 1$. If $n>1$, then we have $\p(n)<n$, and by the induction hypothesis, we can take $k\in \N$ such that $\p(n)\mid \j^k(1)$. Finally, the adjointness $\p \dashv \j$ implies $n\mid \j^{k+1}(1)$.
\end{proof}
\section{Example 2: Riegs in category theory and combinatorics}
% : Decategorifying cartesian closed categories}
\subsection{Bicartesian closed category forms a rieg}
We have seen that every Heyting algebra is a rieg. More generally, in this section, we will observe that every \demph{bicartesian closed category} gives an example of riegs.
\begin{definition}[Bicartesian closed category]
A category $\C$ is \demph{bicartesian closed},
if $\C$ is
\begin{itemize}
\item bicartesian (i.e., has all finite products and finite coproducts), and
\item cartesian closed.
\end{itemize}
\end{definition}
Examples include the category of sets, finite sets, posets, categories, groupoids, directed graphs, and group actions. Every topos is bicartesian closed.
We will see those examples in the following subsections.
\begin{proposition}\label{PropositionbiCCC}
For a bicartesian closed category $\C$, the set of all isomorphism classes $\K{\C}$ equipped with the five operations induced from bicartesian closed structure, is a rieg.
\end{proposition}
\begin{remark}[Size matter]
\end{remark}
\memo{Explain, why not monoidal, but cartesian}
\memo{For bicartesian closed bicategories? finite groupoids, finite groups}
\memo{Rieg of species? Differential operator?}
\subsubsection{Connectedness and augmentation: enumerative comnibatorics}
\memo{Heyting algebras}
\subsection{A fucntor from a topos to riegs}
\subsubsection{Riegs of sets}
\subsubsection{Riegs of functions: Liouville's divisor theorem}
\begin{example}[Multisets of natural numbers]
Let $\mN$ be a set of all multiset of natural numbers. Each multiset will be denoted just like lists of natural numbers. For example, \[(), (3,1,4), (1,2,3,1,1,0,0) \in \mN.\] Note here that the list may be rearranged as desired, \[(1,2,3,1,1,0,0) = (0,0,1,1,1,2,3)\in \mN\]
This set of multisets has a standard rieg structure.
The addition is concatenation of lists. The product is a component-wise \memo{confusing} product.
\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*}
This rig structure is isomorphic to the rig of (formal) Dirichlet polynomials $\N[\frac{1}{n^x}\mid n=0,1,2,\dots]$ \cite{spivak2020dirichlet}. 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*}
\end{example}
\memo{Write the generalization and $\mult{1}$}
\subsubsection{Riegs of graphs}
\subsubsection{Riegs of group actions: Burnside riegs}
\memo{rieg homomorphism to $\N$, which induced by atomic geometric morphism}
\paragraph{Rieg of involutions}
$A^x = n + \frac{n^2 -n}{2} x$, where $n= |A|$.
\subsubsection{Riegs of loops: Counting repeating dicimals}
\subsubsection{Categories and discrete fibrations}
\subsubsection{Topological spaces and \'etale maps}
\memo{Quasitoposes}
\subsection{Riegs of Higher structures}
% \subsection{Bicartesian closed bicategory}
\subsubsection{Riegs of categories}
\subsubsection{Riegs of finite groups}
\section*{Counting problems}
Later, 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 \cong S_3 \times C_2$.)
\end{question}
\section{Definition of riegs}
Since what we will consider is a ring with \textbf{e}xponentials instead of \textbf{n}egatives, we call it a \emph{rieg}.
We define riegs with numerous but familiar axioms about exponential.
\begin{definition}[Rieg, axiomatic definition]\label{DefinitionRiegAxiomatic}
A \emph{rieg} is a set $R$ equipped with
\begin{itemize}
\item two nullary operations, $0,1 \in R$ and
\item three binary operations, $+, \ti, \ex\colon R\times R \to R$
\end{itemize}
that satisfies the following \dq{usual} fourteen
% \footnote{Some of them are redundant.}
axioms:
\begin{itemize}
% \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$
% \item $(x+y)\ti z=(x\ti z)+(y\ti z)$
\item $1 \ex x = 1$
\item $(x\ti y)\ex z = (x\ex z)\ti (y\ex z)$
\item $x \ex 0 = 1$
\item $x\ex (y+z) =(x\ex y) \ti (x\ex z)$
\item $x\ex 1 = x$
\item $x\ex (y\ti z) = (x\ex y)\ex z$.
\end{itemize}
\end{definition}
\begin{remark}
For those who know rigs (=semirings), our definition above has a much more memorable form: It is just a commutative rig (= semiring) $(R, 0, 1, +, \ti )$ equipped with a rig homomorphism $R \to \End{(R, 1,\ti)}$.
\end{remark}
\begin{example}
The prototypical example is the rieg of natural numbers $\N$. Notice that we adopt $0^0=1$.
\end{example}
\begin{exercise}
Prove that if the underlying rig of a rieg $R$ is a ring, then $R$ is a singleton. (Hint: consider $0^{-1}$.)
\end{exercise}
% \begin{remark}[Alternative definition]
% If you know the notion of rigs (= semirings), a rieg is just a commutative rig $(R, 0, 1, +, \ti )$ equipped with a rig homomorphism $R \to \End{(R, 1,\ti)}$.
% \end{remark}
\begin{remark}
A similar algebraic structure, \emph{Tarski high school identities}, has been studied by (finite) model theorists \cite{burris1993tarski}\cite{burris2005saga}.
\end{remark}
\section{CCC with finite coproducts form a rieg}
\begin{proposition}\label{PropositionCCC}
For a cartesian closed category $\C$ with finite coproducts, the set of isomorphism classes of $\C$ forms a rieg with the categorical initial object, terminal object, coproducts, products, and exponentials.
\end{proposition}
\begin{proof}
All of the fourteen axioms are implied by the universalities.
\end{proof}
\begin{exercise}
Explain why this construction does not work for a symmetric monoidal closed category.
\end{exercise}
The following examples are
% just to help you understand. They are
not necessary to follow the latter sections of this note.
\begin{example}
% There have been so many studies on the following rig sturcture. But as far as the author knows, there are few researches on the rieg structures on it.
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.
\begin{itemize}
\item The category $\FinSet$ forms a rieg of natural numbers.
\item The category $\Set$ forms a rieg of cardinal arithmetic\footnote{There is a size matter. One can fix a strong limit cardinal $\kappa$ and consider only sets with cardinality less than $\kappa$. Then, (the isomorphism classes of) $\Set_{<\kappa}$ form a (small) rieg.} The structure of this rieg is closely related to set theory, especially the (generalized) continuum hypothesis.
% Consider $2^{\aleph_{0}}$.
% The structure of this rieg is closely related to set theory. Consider $2^{\aleph_{0}}$}.
% \item For a strong limit cardinal $\kappa$, the category $\Set_{<\kappa}$ forms a rieg of cardinal arithmetic\footnote{The structure of this rieg is closely related to set theory. Consider $2^{\aleph_{0}}$}.
\item The category of finite functions $[\to,\FinSet]$ forms a rieg of multisets of natural numbers (or Dirichlet polynomials \cite{spivak2020dirichlet}).
\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 The category of finite graphs $[\rightrightarrows,\FinSet]$ forms a rieg.
\item For any (possibly infinite) group $G$, the category of its finite actions $[\B G,\FinSet]$ form the \emph{Burnside rig} of the group $G$. Examples include the category of sets with involution $[\B \Z/2\Z,\FinSet]$ and the category of finite loops $[\BZ,\FinSet]$.
% \item The category of rooted forests $[\omega^{\op},\FinSet]$ forms a rieg.
\item Every Heyting algebra $H$ is a cartesian closed poset with finite coproducts, and thus a rieg.
\item The category of quasi-categories $\mathbf{qCat}$ forms a rieg. This rieg contains the rieg of categories $\mathbf{Cat}$, posets $\mathbf{Poset}$, and groupoids $\mathbf{Groupoid}$. Conversely, this rieg is contained by the rieg of simplicial sets $\mathbf{sSet}$.
\end{itemize}
\end{example}
\begin{exercise}
Describe the exponentials of $[\to, \FinSet]$, in terms of multisets.
\end{exercise}
\begin{exercise}
Prove that the category of finite discrete dynamical systems $[\BN, \FinSet]$ is NOT cartesian closed\footnote{This is one of my motivations to consider the question: when is a finite presheaf category $[\C, \FinSet]$ cartesian closed? The author is also interested in the closely related question: when is a finite presheaf category a topos?}.
\end{exercise}
% \begin{remark}
% The category of finite discrete dynamical systems $[\BN, \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}
\section{Rieg of finite groups}
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 Proposition \ref{PropositionCCC}), 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 Proposition \ref{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}}$
% \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}
% \begin{remark}
% By using Appendix \ref{AppendixGC}, one can extract rational numbers from elements of $\G$. Utilizing it, one can easily calculate the number of group homomorphisms from $D_6$ to itself.
% % One can partially check the validity of these calculations.
% \end{remark}
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 = \#\mathrm{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, Question \ref{QuestionIndex2}!
\begin{answer}[to Question \ref{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 = \#\mathrm{Hom}(G,A) \cdot A.
% \]
% \item For any abelian group $A$, we have
% \[
% A^G = \#\mathrm{Hom}(G,A) \cdot A.
% \]
% \end{itemize}
\section{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 $\abs*{-}\colon \G \to \Q$ preserves sum and products. Furthermore, for finite groups $G$ and $H$, we have
\[
\abs*{G^H} = \frac{\# \mathrm{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 $\mathrm{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 Proposition \ref{PropositionExpGC} is compatible with Proposition \ref{PropositionAbelian}.
\end{exercise}
Let us finish this introductory note by giving the answer to Question \ref{QuestionDsix}!
% \begin{exercise}
% Utilizing Proposition \ref{PropositionExpGC} and Example \ref{ExampleExp}, calculate the number of group homomorphisms from $D_6$ to itself.
% \end{exercise}
\begin{answer}[to Question \ref{QuestionDsix}]\label{AnswerDsix}
In Example \ref{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{\# \mathrm{Hom}(D_6,D_6)}{12} = \frac{4}{2} + \frac{12}{4} + \frac{4}{12}.
\]
This proves that $\mathrm{Hom}(D_6,D_6) = 64$.
\end{answer}
% are compatible
% \memo{Counting with Euler characteristic}
Since the category of finite groupoids $\Groupoidfin$ is bicartesian closed, we have the riegs of finite groupoids, $\K{\Groupoidfin}$.
Furthermore, since all five operations are compatible with equivalences, we have its quotient $\biK{\Groupoidfin}$.
\memo{Using the rieg structure, compute the number of subgroups of order $2$, faster!}
\memo{compute $n$-dimensional representation of a product group}
\memo{categorification of the multiset construction}
\cite{nlab:quasitopos}
\begin{definition}
\end{definition}
\begin{example}
The category of (finite) categories and (finite) discrete fibrations.
\end{example}
\memo{When is $\FinSet^{\C}$ a topos? \url{https://ncatlab.org/nlab/show/category+of+presheaves\#finite_presheaves}}
\begin{example}
The category of topological spaces and local homeomorphisms.
\end{example}
% \subsection{Rieg of multisets, Liouville's divisor theorem}
% \subsection{Riegs from toposes, repeating decimal}
\memo{CC and CCC functor, \'etendue, logical morphism, directed graph, and group actions}
% \input{Games}
% \input
\section{Example 3: Riegs in logic}
% . 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 $2$ 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.
\memo{Then, there is a free construction of \dq{associated Heyting algebras}}
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{For terminology, see \cite{golan2013semirings}}
\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{ExampleParityRieg} 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. \memo{How about the converse? Is there a multiplicatively non-idempotent rieg with those characteristics? For $(0,1),(1,1)$, there is not.}
\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]\memo{Isn't this wrong? $2^{1+x}$ is increasing, but $1^{1+x}$ is constant.}
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}\}\\
\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*}
% By considering an equivalence relation $\simeq$ as
we obtain a $4$-elements riegs
$\{\mathrm{ZC},\mathrm{ZI},\mathrm{PC},\mathrm{PI}\}$
as a quotient rieg. \memo{There are several things to check here. But all of them are straightforward.}
\memo{The underlying rig is the freely generated rig with a generator $x$ and two equations $1+1=1$ and $x^2=x$.} This rieg satisfies $1+1 = 1$, but the underlying rig is not a lattice since $1+x\neq 1$.
% \begin{itemize}
% \item $\mathrm{ZC}=\{f(x)\in \N[x]\mid f(0)=0\text{ and }f\text{: constant}\}$
% \item $\mathrm{ZI}=\{f(x)\in \N[x]\mid f(0)=0\text{ and }f\text{: increasing}\}$
% \item $\mathrm{PC}=\{f(x)\in \N[x]\mid f(0)>0\text{ and }f\text{: constant}\}$
% \item $\mathrm{PI}=\{f(x)\in \N[x]\mid f(0)>0\text{ and }f\text{: increasing}\}$
% \end{itemize}
\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{PropositionbiCCC}, 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}$.
\memo{Since rig homomorphisms $\Po{X} \to \2$ correspond to ultrafilters on $X$, we can construct similar rieg structure for each ultrafilter $\mathcal{F}$ on $X$. The above example is the special case where $\mathcal{F}$ is a principal filter generated by $x\in X$.}
% 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}
\memo{Are all of them necessary?}
\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.
\memo{Full sub. Birkhoff's theorem}
\memo{Is it Malcev?}
\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{Characteristic of \texorpdfstring{$\T$}{T}-algebras}\label{ssec:generaltheoryOfCharacteristics}
From an abstract point of view, this definition is quite natural. In fact, we can \dq{deduce} this definition from a general setting. For an arbitrary equational theory $\T$, we can define a notion of \dq{characteristic} of $\T$-algebra as follows. Recall that the category of $\T$-algebras admits the (surjection, injection) factorization system, or (regular epi, mono) factorization in terms of category theory. \memo{reference}
% and the initial object $I$.
Therefore, for each $\T$-model $A$, we can canonically associate a quotient $Q$ of the initial $\T$-algebra $I$ obtained by factorizing the unique homomorphism
\[I\twoheadrightarrow Q \rightarrowtail A.\]
In the case of rings, the associated quotient is $\Z /n\Z$, where $n$ is the characteristic of the given ring $A$. So this abstract definition is a generalization of the notion of characteristics. \memo{I don't claim that this is the most natural gereralization.}
In the case of pointed groups, which are groups with a distingished element, the characteristic of a pointed group $(G,g)$ is $\Z /n \Z$, where $n$ is the order of the element $g\in G$. In the case of pointed $\Q$-algebras, the characteristics of the pointed $\Q$-algebra $(\overline{\Q},\alpha)$ is $\Q[x]/(f(x))$, where $f(x)$ is the minimum polynomial of $\alpha$.
Then, how about the case of riegs? The initail rieg is the rieg of natural numbers.
\begin{proposition}
The rieg of natural numbers $\N$ is the initial object in the category of riegs.
\end{proposition}
With those proof, we can rephrase the definition of the characteristics.
% \begin{proposition}
% For a rieg $R$ with characteristic $\ch R =(a,b)$, the unique rieg homomorphism $\N \to R$ is factored as
% \[\N\twoheadrightarrow \Mr{a}{b} \rightarrowtail R.\]
% The characteristic of $R$ is $0$ if and only if $\N \to R$ is injetive.
% \end{proposition}
\begin{proposition}[Chraracteristic, in terms of the quotients of $\N$]
For a rieg $R$ and the (surjection, injection) factorization of the unique morphism $\N \to \R$,
\[\N\twoheadrightarrow Q \rightarrowtail R,\]
\begin{itemize}
\item $Q\cong \Mr{a}{b} \iff \ch R = (a,b)$
\item $Q \cong \N \iff \ch R = \chz.$
\end{itemize}
\end{proposition}
% \memo{Uniqueness of rieg structure on $\Mr{a}{b}$, if it exists.}
\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.
\begin{proposition}[Free forgetful adjunction]
\end{proposition}
Furthermore, we have a variation of the homomorphism theorem:
\begin{proposition}[Surj-inj factorization system]
\end{proposition}
\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 of $R$ form a complete lattice $\Quo(R)$, in which $Q\geq Q'$ if and only if there exists a $\T$-algebra homomorphism $Q\twoheadrightarrow Q'$ that commutes with the associated surjection from $R$. By the definition of order, there is the canonical functor $\Quo(R)^{\op} \to \TAlg$.
Let $\fQuo(R)$ denote the subposet of $\Quo(R)$ that consists of all 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:
\[
{\fQuo(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}
The profinite completion admits a metric structure defined by \dq{distinguishing distance.}
\begin{definition}
For a $\T$-algebra
\end{definition}
\begin{proposition}[]
\end{proposition}
\begin{remark}
Pro(finite $\T$-algebra) and $\T$-algerba on a profintie space. Jonsson-Tarski algebras... ?
\end{remark}
\subsection{Profinite topology and ultrametric on a profinite set}
In this subsection, let $J$ be a small category, $F\colon J \to \FinSet$ be a functor, and $\{\alpha_j\colon P \to Fj\}_{j\in \ob(J)}$ be a limit cone over the functor
\[
J \xrightarrow{F} \FinSet \xrightarrow{\text{discrete}} \Top.
\]
As a topological space,
$P$ is profinite, i.e. compact Hausdorff and totally disconnected. (This is a well known fact, for example, see \memo{Cite} for a proof.)
\begin{definition}[distinguishing value]
For two elements $p,q \in P$, we define its \demph{distinguishing value} $r(p,q)\in \N\sqcup\{\infty\}$ by
\[
v(p,q) \coloneqq \inf\{|Fj| \in \N\mid j\in \ob(J), \;\alpha_j(p) \neq \alpha_j(q)\}.
\]
\end{definition}
\begin{lemma}\label{lem:LemmaForUltrametric}
With the above settings, we have the following:
\begin{enumerate}
\item For any $p, q\in P$, we have $v(p,q) = \infty \iff p=q$.
\item For any $p,q \in P$, we have $v(p,q) = v(q,p)$.
\item For any $p,q,r$, we have $\min (v(p,q), v(q,r)) \leq v(p,r)$.
\end{enumerate}
\end{lemma}
\begin{proof}
To prove $(1)$, we observe that $p=q$ if and only if $\alpha_j(p) = \alpha_j(q)$ for any $j\in \ob(J)$ if and only if $v(p,q) = \infty$.
$(2)$ is trivial by definition.
We prove $(3)$. If $p=r$, then $(1)$ implies $v(p,r)=\infty$, and the inequality. If $p\neq r$, let $j\in \ob(J)$ be an object such that $\alpha_j(p)\neq \alpha_j(r)$ and $v(p,r) = |F_j|$. Then, either $\alpha_j(p) \neq \alpha_j(q)$ or $\alpha_j(q) \neq \alpha_j(r)$ holds. Therefore, either $v(p,q) \leq |Fj| = v(p,r)$ or $v(q,r) \leq |Fj| = v(p,r)$ holds. This implies the inequality.
\end{proof}
\begin{proposition}\label{prop:UltrametricOfProfiniteDiagram}
The function $d(p,q)\coloneqq 2^{-v(p,q)}$ is an ultrametric over the set $P$, that is, $(P, d)$ satisfies the following conditions.
\begin{enumerate}
\item For any $p, q\in P$, we have $d(p,q) = 0 \iff p=q$.
\item For any $p, q\in P$, we have $d(p,q) = d(q,p)$.
\item For any $p, q, r\in P$, we have $\max(d(p,q),d(q,r)) \geq d(q,r)$.
\end{enumerate}
\end{proposition}
\begin{proof}
This follows from \Cref{lem:LemmaForUltrametric}.
\end{proof}
In this metric space, the inequality $d(p,q) \leq \frac{1}{2^N}$ holds if and only if $|Fj|<N$ implies $\alpha_j(p) = \alpha_j(q)$ for any $j\in \ob(J)$.
\begin{remark}[This metric does NOT induce the profinite topology in general.]
Even if the indexing category $J$ is cofiltered, this metric structure does not necessarily induce the profinite topology on $P$.
For example, the Cantor space $2^{\N}$ is the cofiltered limit of the finite products $2^S$ for all finite subsets $S\subset \N$. Every pair of distinct elements $(p,q)$ can be distinguished by $2^{\{k\}}$ with a singleton $\{k\}\subset \N$, so $r(p,q) = 2$ and $d(p,q)=2^{-2}$. This proves that the ultrametric $d$ induces the discrete topology on $2^{\N}$.
\end{remark}
\begin{proposition}
The identity function $(P,d) \xrightarrow{\id_P} (P, \mathcal{O}_{\text{initial}})$ is continuous.
Under the following assumption, the continuous function is homeomorphic.
\begin{itemize}
\item For any $n\in \N$, there exists an object $t_n \in \ob(J)$ such that, for any $j\in J$ such that $|Fj|<n$, there exists at least one morphism $t_n \to j $ in $J$.
\end{itemize}
% If, for any $n\in \N$ there exists an object $j_n \in \ob(J)$ such that, for any $j\in J$ such that $|Fj|<n$, there exists at least one morphism $j_n \to j \in J$.
\end{proposition}
\begin{proof}
Let us take an element $p\in P$ and an open neighborhood $p\in U$ with respect to the initial topology. Then, there exist a finite number of objects $j_1 , \dots, j_n$ such that $p\in \cup_{i=1}^n \alpha_{j_i}^{-1}(\alpha_{j_i}(p))\subset U$. Let $N$ be the maximum value of $|Fj_i|$ among all $1\leq i\leq n$. If $d(p,q)\leq\frac{1}{2^{N+1}}$, then we obtain $\alpha_{j_i}(p) = \alpha_{j_i}(q)$ which implies $q\in \alpha_{j_i}^{-1}\alpha_{j_i}(p)$ and $q\in U$. This completes the proof of the continuity of $(P, d) \to (P, \mathcal{O}_{\text{initial}})$.
Suppose the assumption in the statement. We prove that the identity function $(P,d) \xrightarrow{\id_P} (P, \mathcal{O}_{\text{initial}})$ is homeomorphic. Take a point $p\in P$ and an arbitrary positive real number $\epsilon>0$. Then let $N$ be the minimum natural number such that $\frac{1}{2^N}< \epsilon$. By the assumption, we take an object $t_N\in \ob(J)$ with the required conditions. We prove that the open subset $p\in \alpha_{t_N}^{-1}\alpha_{t_N}(p) \in \mathcal{O}_{\text{initial}}$ is subsumed by the $\epsilon$-ball of the point $p$. Take an arbitrary element $q\in \alpha_{t_N}^{-1}\alpha_{t_N}(p)$. Then, for any $j\in \ob(J)$ with $|F_j|<N$, we have a morphism $\beta \colon t_N \to j$ in $J$. Therefore, we have $\alpha_j(p) = \beta(\alpha_{t_N}(p))= \beta(\alpha_{t_N}(q)) = \alpha_j(q)$. This proves $d(p,q) \leq \frac{1}{2^N}<\epsilon$.
\end{proof}
\begin{corollary}
Let $\T$ be an equational theory with only finitely many functional symbols, and $A$ be a $\T$-algebra. Then, its profinite completion $\pro{A}$ is a complete metric space with respect to its distinguishing metric.
\end{corollary}
\begin{proof}
This follows since $\fQuo(A)$ is filtered, and there are only finitely many isomorphism classes for $n$-element $\T$-algebras.
\end{proof}
\section{Proof of the Burris-Lee theorem}
But why do we consider shifted-Carmichael numbers? How is it related to exponentiation?
% Why do we call them shifted-Carmichael?
One answer is the following algebraic characterization of shifted-Carmichael numbers.
% Simply put, \dq{$n$ is shifted-Carmichael if and only if exponentials are also well-defined modulo $n$.}
\begin{lemma}[Algebraic characterization of shifted-Carmichael numbers]\label{lem:AlgebraicCharacterizationOfShifted_CarmichaelNumbers}
For a positive integer $n$, the following conditions are equivalent:
\begin{enumerate}
\item $n$ is shifted-Carmichael.
\item for any $x \in (\Z/n\Z)^{\times}$, $x^n \equiv 1 \mod{n}.$
\end{enumerate}
\end{lemma}
\begin{proof}
Let $n={p_1}^{k_1}\dots {p_l}^{k_l}$ be the prime factorization of $n$.
Then we have a group isomorphism
\[
(\Z/n\Z)^{\times} \cong (\Z/ {p_1}^{k_1} \Z)^{\times}\times \dots \times (\Z/ {p_l}^{k_l} \Z)^{\times}.
\]
First, we will prove $(1) \implies (2)$. By the above group isomomorphism, it suffices to prove that, for any $1\leq i \leq l$ and $x \in (\Z/ {p_i}^{k_i} \Z)^{\times}$, $x^n \equiv 1 \mod{{p_i}^{k_i}}$. Under the assumption that $n$ is shifted-Carmichael, this follows since $|(\Z/ {p_i}^{k_i} \Z)^{\times}| = (p-1)p^{k_i -1}$ divides $n$.
Next, we will prove $(2) \implies (1)$.
% Let $p$ be a prime factor of $n$.
We prove $(p_i-1)\mid n$ for an arbitrary taken $1\leq i\leq l$. Since the case of $p_i =2$ is trivial, we may assume that $p_i$ is odd. Since $p_i$ is odd, the multiplicative group $(\Z/ {p}^{k} \Z)^{\times}$ is isomorphic to the cyclic group $\Z/(p_i^{k_i} - p_i^{k_i -1})\Z$. In particular, the group $(\Z/ {p}^{k} \Z)^{\times}$ contains an element whose order is $p_i -1$.
Therefore, the multiplicative group $(\Z/n\Z)^{\times}$, which contains $(\Z/ {p}^{k} \Z)^{\times}$ as a subgroup, also admits an element $x\in (\Z/n\Z)^{\times}$ whose order is $p_i-1$.
% \footnote{This is not obvious by definition, but well-known.}.
By the assumption $x^n \equiv 1 \mod n$, we obtain $p-1 \mid n$. This completes the proof.
% \[(\Z/ p^{k_l} \Z)^{\times} \simeq \Z/(p-1)p^{}\]
\end{proof}
\begin{definition}\label{def:Rad}
For a positive integer $n>0$, the \demph{radical} of $n$, which is denoted by $\rad(n)$, is the maximum sqare-free devisor of $n$.
\end{definition}
In other words, the radical of $n={p_1}^{k_1}\dots {p_l}^{k_l}$ is defined by
\[\rad(n)\coloneqq p_1 \cdots p_k.\]
For example, $\rad(2025)=\rad(3^4 \cdot 5^2)=3\cdot 5 = 15$.
$H(n)$ and $\rad(n)$ are mutually strongly related.
$\H(n)$ is the minimum natural number $h\geq 0$ such that $n$ divides $\rad(n)^{h}$. Conversely, $\rad(n)$ is the maximum divisor $r\mid n$ such that $H(r)=1$.
\begin{proof}[Proof of \Cref{thm:BurrisLeeTheorem}]
Assuming $\Mr{a}{b}$ has a rieg structure, we will prove $b$ is a shifted-Carmichael number whose dimension is at most $a$. Let $[x] \in \Mr{a}{b}$ denote the equivalence class that contains $x\in \N$. For an arbitrary natural number $x$ that is coprime with $b$, we have
\[
[x^{a+b}]=[x]^{[a+b]}=[x]^{[a]}=[x^{a}],
\]
hence \[x^{a+b} \equiv x^{a} \mod{b},\] and \[x^b \equiv 1 \mod{b}.\] By \Cref{lem:AlgebraicCharacterizationOfShifted_CarmichaelNumbers}, $b$ is shifted-Carmichael. Next, we move on to the dimension of $b$. For any non-negative integer $m\geq 0$, we have
\[[\rad(b) ^a]=[\rad(b)]^{[a]}=[\rad(b)]^{[a+mb]}=[\rad(b)^{a+mb}],\]
and \[\rad(b) ^a\equiv \rad(b) ^{a+mb} \mod{b}.\]
By taking a sufficiently large $m$ such that $a+mb\geq \H(b)$, we obtain \[\rad(b) ^a\equiv 0 \mod{b},\] equivalently, $a\geq \H(b)$.
Conversely, assuming that $b$ is a shifted-Carmichael number whose dimension is at most $a$, we will prove the rig $\Mr{a}{b}$ has a rieg structure. It is enough to prove that $\ex$ is well-defined.\footnote{Here, we implicitly use the fact of universal algebra: if an equivalence relation is compatible with all operations, then its quotient set has the unique (same type of) algebraic structure such that the canonical surjection is homomorphic.} If $a=0$, then $b=1$, and this case is trivial. In the rest of the proof, we assume $a>0$.
We begin with the easier case: assuming $[x_0]=[x_1]$, we will prove $[{x_0} ^{y}]=[{x_1}^{y}]$. If $x_0 = x_1$ or $y=0$, this is trivial. Suppose $x_0 < x_1$ and $y>0$. Since $x_0 \neq x_1$, we have $a\leq x_0,x_1$ and ${x_0} \equiv {x_1} \mod{b}$. Since $y>0$, we have $a\leq x_0,\leq {x_0}^y\leq {x_1}^{y}$. As a result, we obtian $a\leq {x_0}^y, {x_1}^{y}$ and ${x_0}^y \equiv {x_1}^{y}\mod{b}$, which mean $[{x_0} ^{y}]=[{x_1}^{y}]$.
Lastly, assuming $[y_0]=[y_1]$, we will prove $[x ^{y_0}]=[x^{y_1}]$. If $y_0=y_1$, this is trivial. Therefore, we can assume $0<a\leq y_0, y_1$ and $y_0\equiv y_1 \mod{b}$. Since the cases where $x=0,1$ are trivial, \footnote{For $x=0$ case, we used $0< y_0,y_1$.} we can also assume $x\geq 2$. Under those assumptions, because we have $a\leq y_0 \leq x^{y_0}$ and $a\leq y_1 \leq x^{y_1}$, it is enough to prove
\[x^{y_0}\equiv x^{y_1} \mod{b}.\]
Take an arbitrary prime factor $p$ of $b$ and let $k$ be the number of times that $p$ divides $b$. We prove
\[x^{y_0}\equiv x^{y_1} \mod{p^k}.\]
If $p$ divides $x$, both sides of the equation are equal to zero, because \[k\leq \H(b) \leq a \leq y_0,y_1.\]
If $x$ is coprime with $p$, it follows from shifted-Carmichaelness of $b$ and $|(\Z/p^k \Z)^{\times}| = (p-1)p^{k-1}$.
The proof is complete.
\end{proof}
\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.
\memo{The rieg $[0,\infty)$ is not a $\Top$-internal rieg, since $\ex$ is not continuous. Then, the rig of non-negative continuous functions is not closed under element-wise exponentials. How about non-negative $L^1$ functions?}
\memo{(J. Koizumi) exp-preserving function $(0,\infty)\to (0,\infty)$ is either the constant function to $1$ or the identity function.}
\end{example}
\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}
\subsubsection{Finite system of numbers}
% The overflow rieg with threshold $1$ will appear soon (\Cref{ExampleRiegOfTruthValues}) as the rieg of truth values.
\memo{threshold $2$ is also theoretically important: $\{0,1, \mathrm{plural}\}$. $2^{\infty}\neq 1^{\infty}$}
Is it possible to perform modular arithmetic in rieg theory? In fact, this question is of great importance in the development of general rieg theory, especially the theory of characteristics, and will be discussed in detail.
\memo{Rieg of functions with first-order differential coefficients}
\memo{What's called the exponential ring of complex numbers}
\memo{Some example from Heyting, e.g. max-min of [0,1]}
\memo{max-plus algebra}
\subsubsection{Numbers with Infinites}
There are some riegs, wth \dq{infinites}. This cannot happen for a (non-trivial) ring, because $0+\infty = 1+ \infty$ implies $0=1$.
\begin{example}[Cardinal numbers]
The cardinal arithmetic also has the structure of a rieg. However, one must be careful about the size problem, since the class of all cardinal numbers is a proper class, not a set.
The familiar solution is to assume the existence of a Grothendieck universe, but there is no need to go to such great lengths. We can simply take a strong limit cardinal $\kappa$ (for example, $\beth_{\omega}$) and consider the set of all cardinal numbers less than $\kappa$. Then this set has a rieg structure by cardinal arithmetic. When $\kappa = \aleph_0$, this is the rieg of natural numbers.
\memo{The regularity of $\kappa$ is not needed here, but in some situations, it may be useful to take a strong limit cardinal with cofinality greater than $\omega$, such as $\beth_{\omega_1}$).}
\memo{Relation to topos}
\end{example}
\memo{Under the GCH (generalized continuum hypothesis), the rieg induced from $\beth_{\omega}$($=\aleph_{\omega}$ by the GCH) is worth mentioning.}
\memo{And, forcing can access this rieg structure.}
% The next example cannot be realized with substitution operations. In this sense, it is $$
\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$.
\memo{$[0,\infty]$ does not have a rieg structure}
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{Lists of numbers}
\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 $(n+m\ep)\ex (n'+m'\ep)=\underbrace{(n+m\ep)\ti \dots \ti (n+m\ep)}_{n' \text{times}} = (n^{n'}, n^{n'-1}n'm\ep).$
\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 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}
\begin{example}[Shift operator]
\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<a<1\}, 0, \lor, 1, \land)$ (\Cref{prop:WhenIsARiegALattice}). This rig $0<a<1$ is isomorphic to the rig
\[
R \cong \langle a \mid 1+1=1, 1+a=1, a^2=a\rangle \text{ in } \Rig
\]
Therefore, the rieg structures $R \to \End(R,1,\land)$ on the rig $R$ are in bijective correspondence with the monoid homomorphisms $\phi \colon (R, 1, \land) \to (R,1,\land)$, which correspond to the exponentiation function ${-}^a\colon R \to R$, that satisfy
\begin{itemize}
\item $x \land x = x$, which always holds,
\item $x\land \phi(x) = x$, and
\item $\phi^2 (x) = \phi (x)$.
\end{itemize}
In other words, the rieg structures on the rig $(\{0<a<1\}, 0, \lor, 1, \land)$ are in bijective correspondence with the idempotent $\land$-semilattice homomorphisms ${-}^a = \phi \colon (R, 1, \land)\to (R, 1 , \land)$ with $\phi(x)\geq x$.
One can show that there are exactly $4$ rieg structures on the rig $(\{0<a<1\}, 0, \lor, 1, \land)$, which are visualized in \Cref{fig:FourExponentials}.
\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[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{prop:riegIsNotRing}).
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}
% \memo{Are there infinitely many solutions for $x^x =x$ in $\Mr{\infty}{10^{\infty}}$?}
% % (related question: how about in $\Mr{\infty}{p^{\infty}}$)? This does not even exist!}
% %
% % \input{2023_07_23Ver/riegsOfPropositions0729}
\printbibliography
\end{document}