← Notes on Rieg Theory

culm.tex

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox, amsmath}
\usepackage{blindtext}
\usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref}
\usepackage{tikz,tikz-cd}
\usepackage{array}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{framed}
\usepackage{autobreak}
\graphicspath{ {images/} }
\usepackage[style=alphabetic,sorting=nyt]{biblatex}
\renewbibmacro{in:}{}
\addbibresource{bibl.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);%
}}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}
\newtheorem{problem}[theorem]{Problem}
\newtheorem*{answer}{Answer}

\newcommand{\dq}[1]{``#1"}
\newcommand{\memo}[1]{\textcolor{red}{memo: #1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Po}[1]{\mathcal{P}(#1)}
\newcommand{\co}{\mathrm{c}}
\newcommand{\Set}{\mathrm{Set}}
\newcommand{\FinSet}{\mathrm{FinSet}}
\newcommand{\Top}{\mathrm{Top}}
\newcommand{\HeyAlg}{\mathrm{HeyAlg}}
\newcommand{\Rieg}{\mathrm{Rieg}}
\newcommand{\Ring}{\mathrm{Ring}}
\newcommand{\ti}{\times}
\newcommand{\ex}{\uparrow}
\newcommand{\2}{\mathbf{2}}
\newcommand{\mult}[1]{\mathrm{mult}(#1)}
\newcommand{\mN}{\mult{\N}}
\newcommand{\di}{\mathrm{dim}}
\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{\C}{\mathcal{C}}
\newcommand{\ep}{\varepsilon}
\newcommand{\loga}{log-able}
\newcommand{\ch}{\mathrm{char}}
\newcommand{\TV}{\Omega}
\newcommand{\chz}{(\infty, 0)}
\newcommand{\Tame}{\mathbb{T}\mathrm{ame}}
\newcommand{\Char}{\mathbb{C}\mathrm{har}}
\newcommand{\finChar}{\mathrm{f}\mathbb{C}\mathrm{har}}
\newcommand{\qTame}{\overline{\N\times \N_{>}}}
\newcommand{\K}[1]{#1 / \hspace{-1pt} \scalebox{0.7}{$\cong$}}
\newcommand{\biK}[1]{#1 / \hspace{-1pt} \scalebox{0.7}{$\simeq$}}
\newcommand{\lcm}{\mathrm{lcm}}
\newcommand{\proN}{\hat{\mathbb{N}}}
\newcommand{\proZ}{\hat{\mathbb{Z}}}
\newcommand\binuparrow{\mathbin{\uparrow}}
\newcommand{\powow}{\binuparrow \binuparrow}
\newcommand{\Inf}{I}

\begin{document}

\title{Notes on Rieg Theory \memo{Draft}}
\author{Ryuya Hora}
\date{\today}
\maketitle
\definecolor{shadecolor}{gray}{0.9}
\maketitle

\begin{abstract}
In ring theory classes, we are told that \dq{natural numbers do not have the structure of a ring, but only a semiring (or a \emph{rig}).} In fact, it does not have the structure of a ring like $2-3=-1 \notin \N$, but it does have a rich algebraic structure in another direction, exponentials $2^3=8$.

In combinatorics, when considering the action of a finite group on a finite set, one sometimes constructs a Burnside rig of the isomorphism classes. However, even in this case, if we do not extend it to a ring, it has an exponential structure.

In this article, we investigate the properties of such semirings with exponentials, which we call \emph{riegs}, and observe their connections with bicartesian closed categories and toposes as categorifications.

Let us spoil some of the wonders of rieg theory. In contrast to field theory, there are only a finite number of possible \dq{positive characteristics} of a rieg! They are $1,2,6,42$, and $1806$.
\end{abstract}
\memo{[PRECEDING STUDIES]}
The classification theorem of modulo riegs is proven in Burris and Lee's \cite{burris1993tarski}.
\url{https://math.stackexchange.com/questions/599172/structures-with-addition-multiplication-and-exponentiation}
\url{https://en.wikipedia.org/wiki/Tarski\%27s_high_school_algebra_problem}
\url{https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0896-09.pdf}
\url{https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1476-17.pdf}
exponential rings
There is a survey paper on this topic: \cite{burris2005saga}.
\cite{sc}
\newpage
\tableofcontents
\newpage
\newpage
\section{Selected Phenomena}\label{SectionPhenomena}
\subsection{Expected Phenomena}\label{SubsectionExpectedPhenomena}
\subsubsection{Rig theoretic definition}\label{SubsubsectionRigTheoreticDefinition}
We will define a rieg as a set with several operations $0,1,+,\ti, \ex$, satisfying numerous but familiar axioms (Definition \ref{DefinitionRiegAxiomatic}).  
However, in terms of rigs ($=$ semirings), its definition becomes much simpler. That is a rig $R$ equipped with a rig homomorphism (Proposition \ref{PropositionRiegdefinition})
\[R \to \End (R, 1, \ti).\] 

This memorable paraphrase is useful to prove several properties of riegs and plays a central role in this note. For example, one can easily prove that there is exactly one rieg structure on the rig $\N$, because $\N$ is the initial object in the category of rigs.
\subsubsection{Modulo arithmetic with exponentials}\label{SubsubsectionModuloArithmeticWithExponentials}
% In this section, we treat modular arithmetic with exponentials. As an introduction, l
Let us consider the following typical elementary number theory problem, which can be solved by modular arithmetic:

\begin{problem}
Find all pairs of natural numbers $(n,m)$ such that
    \[2^n +5 =m^2.\]
\end{problem}
\begin{answer}
Consider the remainder by $8$. If $n$ is greater than or equal to $3$, the left-hand side is congruent with $5$, and the right-hand side is one of the square remainders of $8$, which are $0,1,4$, and it's absurd. Therefore, it suffices to check all the cases where $n=0,1,2$,  and we find that $(n,m)=(2,3)$ is the only solution.
\end{answer}

Now, we can ask two questions: in which algebraic structure did we calculate? Where do those \dq{first $3$ exceptions} come from?
For both of them, the rieg theory provides a unifying answer: the quotient rieg $\Mr{3}{8}$.

The quotient rieg $\Mr{3}{8}$ has $3+8=11$ elements
\[
\Mr{3}{8} =\{0,1,2, [3],[4],[5],[6],[7],[8],[9],[10]\}.
\]

For the first question, the naive (and wrong) answer is the quotient ring $\Z/8\Z$. However, we cannot regard the exponent $n$ as an element of $\Z/8\Z$. 
Because $\Z/8\Z$ is not equipped with an exponential structure. (And in fact, it cannot have any rieg structure! see the next subsubsection and Proposition \ref{PropositionMinusOne}.) To conduct modular arithmetic, we want to consider \dq{quotient riegs} of the rieg of natural numbers $\N$, instead of quotient rings.

In this example, when considering exponentiation modulo $8$, we should divide \dq{first exceptions}, namely three numbers $n=0,1,2.$
In section \ref{SectionFiniteandProfiniteArithmetic}, we will observe that the appropriate rieg structure is 
\[
\Mr{3}{8} =\{0,1,2, [3],[4],[5],[6],[7],[8],[9],[10]\}.
\]
That is rieg of $\mathord{\mathrm{mod}} 8$

% However, the quotient rig $\Z/ 8\Z$ does not have any rieg structure! (see Proposition \ref{PropositionMinusOne})
% 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.


\subsubsection{Relationship with rings}\label{SubsubsectionRelationwithrings}

\subsection{Unexpected Phanomena}
\begin{itemize}
    \item finite and profinite riegs $3^x=x$
    \item Combinatorial games
    \item Type theory
    \item Tarski High School algebra
    \item Decategorifications and numerous combinatorial (and functorial) construction
    \begin{itemize}
        \item Liouville's number theorem and list rieg
        \item Dillichlet polynomial
        \item 
    \end{itemize}
    
    \item relation to rings
    \item rig theoretic definition
    \item Positive characteristics
    \item Containing Heyting algebras
    \item Rieg of finite groups
\end{itemize}

\subsubsection{Exponential Equation of profinite numbers}
\memo{Thanks to J.Koizumi}
Let us consider the following question:
\begin{question}
    Find a $4$-digits natural number $n$ such that 
    \[3^n \equiv n \mod 10000.\]
\end{question}

There is a surprisingly simple way to find an answer. That is the iteration:

\begin{itemize}
    \item First, take an arbitrary natural number $n$, like $n=2024$.
    \item 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 $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}

\memo{The maximum number of iterations is explained by the characteristic theory of riegs.}



\section{Introduction}\label{SectionIntroduction}
\subsection{Motivation 0: Riegs themselves}
\cite{599172}
\subsection{Motivation 1: Topoi}
\subsubsection{Burnside-type rig}
\subsubsection{Atomic quotients}
\cite{yoshida1987burnside}
\memo{Liouville's divisor theorem}
\subsection{Motivation 2: Logic, Equational theory}
Tarski's high school problem, \cite{fiore2006remarks}
\cite{gurevivc1985equational}
\cite{GUREVIC19901} \memo{Decidability of equational consequences of HSI (?)}



\cite{henry2017localic}
\subsection{Motivation 3: Combinatorics}
\subsection{Motivation 4: Modular arithmetic with exponentials}
\subsection{Motivation 5: Rig theory}
\cite{gondran2008graphs}
\subsection{Motivation 6: As a Heyting algebra with quantity}




\newpage

\section{Basic theory}
\subsection{Riegs}
Since what we will consider is a ring with \textbf{e}xponentials instead of \textbf{n}egatives, we call it a \emph{rieg}.
First, we define riegs with numerous but familiar axioms about exponential. In the next subsection, we will give more conceptual (but equivalent) definition (Proposition \ref{PropositionRiegdefinition}), which is much more memorable.
\begin{definition}[Rieg, axiomatic definition]\label{DefinitionRiegAxiomatic}
A \emph{rieg} is a set $R$ equipped with
\begin{itemize}
    \item two $0$-ary operations, $0,1 \in R$ and
    \item three $2$-ary operations, $+, \ti, \ex\colon R\times R \to R$
\end{itemize}
that satisfies the following axioms:\footnote{some of them are derivable from others}

\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}
\memo{This is a little bit different from Tarski's high school algebra problem. How about the rieg case of the problem? I believe this is the \dq{right} question.}

From now, $x^y$ denotes $x\ex y$ and $xy$ denotes $x\ti y$, as usual.
For example, with this notation and elimination of obvious redundant axioms, the above definitions look a little simpler like this:
\begin{itemize}
    \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 $(x y)^ z = x^ z y^ z$
    \item $x ^ 0 = 1$
    \item $x^ {y+z} =x^ y  x^ z$
    \item $x^ 1 = x$
    \item $x^{y z} = (x^ y)^ z$.
\end{itemize}

% The prototypical example is the rieg of natural numbers.
% \begin{example}[Natural numbers]
% $(\N,0,1,+,\ti,\ex)$. 
% \end{example}
We will see numerous examples of riegs in this note!

\memo{semiring with tetrations}

From this definition, we obtain the notion of rieg homomorphisms, as usual.
\begin{definition}
    A rieg homomorphism is a function that preserves all (five) operations $0,1,+,\ti,\ex$.
\end{definition}



The category of riegs is referred to as $\Rieg$. 

\subsection{Relation with rigs}
In terms of rigs (or semirings), we can simplify the definition of riegs. First, recall the notion of rigs. 
In this note, we refer to a semiring as a \emph{rig}, because it is a ring without \textbf{n}egatives (and a rieg without \textbf{e}xponentials.)

\begin{definition}[Rig]
A \emph{rig} is a set $R$ equipped with
\begin{itemize}
    \item two $0$-ary operations, $0,1 \in R$ and
    \item two $2$-ary operations, $+, \ti$
\end{itemize}
that satisfies the following axioms:\footnote{some of them are derivable from others}

\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)$
\end{itemize}

If $R$ satisfies $x\ti y = y\ti x$, we call it a \emph{commutative rig}.
\end{definition}
\memo{We don't assume $xy=yx$.}
% We will give two 
% % seemingly different (but, of course, equivalent)
% definitions of riegs. The first one is more conceptual and easy to remember, and the latter equational one is theoretically convenient.

% First, recall that, for a commutative monoid $(A, e, \ast)$, the set of endomorphisms $\End{(A, e, \ast)}$ has a rig structure. The addition is elementwise addition, and the multiplication is the composition.

\begin{lemma}
    For a commutative monoid $(A, e, \ast)$, the set of monoid endohomorphisms $\End{(A, e, \ast)}$ has a rig structure. The addition is elementwise addition, and the multiplication is the composition.
\end{lemma}

\begin{proposition}[Rieg, conceptual definition]\label{PropositionRiegdefinition}
A rieg is a commutative rig $(R, 0, 1, +, \ti )$ equipped with a rig homomorphism 
\[R \to \End{(R, 1,\ti)}.\]
\end{proposition}
\begin{proof}
    Straightforward. Notice that we use the commutativity of the multiplication.
\end{proof}

\begin{remark}
    This is a reminiscent of the definition of modules. For a ring $A$, its module is an abelian group $M$ equipped with a ring homomorphism
    \[A \to \End{(M,0,+)}.\]
    From this point of view, a rieg is a commutative rig $R$ equipped with a $R$-module structure on its own multiplicative structure.
\end{remark}
\subsection{Basic properties}

The first thing to point out is the following equality which follows immediately from the axiom $x^0=1$.
\begin{proposition}
    $0^0=1$.
\end{proposition}
\memo{If $0^x=1$, then is $x$ zero? No, Heyting algebras}

This is a natural algebraic requirement, and we will later observe that it is also consistent with a category-theoretic construction. For example, the number of functions from an empty set to an empty set is one.

Both riegs and rings are variants of rigs, but with different atmospheres. In fact, when those two structures coexist, an anomaly of $0^{-1}$ immediately occurs!
\begin{proposition}[Riegs and Rings]\label{PropositionMinusOne}
If a rieg $R$ has an additive inverse for $1$, then $R$ is a singleton (with the trivial rieg structure).
In particular, if a rieg $R$ is a ring, then it is a zero ring. \footnote{As a rieg, lately we will call it the \emph{trivial rieg}.}
\end{proposition}
\begin{proof}
Using the additive inverse $-1$, we have
$1=0^0=0^{1-1}=0^{1}\ti 0^{-1}=0 \ti 0^{-1}=0$.
Therefore, for any $x\in R$, we have
$x=1x=0x=0$.
\end{proof}
\memo{In terms of pullbacks}

This is a simple but typical argument that transitions between addition and multiplication. The key feature of rieg theory
% , which is not found in mere semicyclic theory, 
is that addition and multiplication are closely interconnected, transformed into each other by exponential $\ex$.

\memo{Is $0$ the only element that has additive inverse?}

\begin{remark}[Relation to Dioids]\label{RemarkDioidsandRiegs}
    Dioids are another variant of rigs that is also almost disjoint to rings. For the definition, see Remark \ref{RemarkDefinitionOfDioids} or the introductory book \cite{gondran2008graphs}. Until now, the author could not find a direct connection between dioids and riegs. At least, there is no inclusion relation. The parity rieg (Example \ref{ExampleParityRieg}) is a rieg, but not dioid. Conversely, the dioid of extended non-negative real numbers $[0, \infty]$ cannot have a rieg structure (Remark \ref{RemarkExtendedReals}).
    \memo{The terminology dioid has several different meanings}
\end{remark}

Several category-theoretic properties follow immediately from the mere existence of an equation-theoretic definition. 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{proposition}[Limits and colimits in $\Rieg$]
    The category of riegs $\Rieg$ has all small limits and colimits.
    Furthermore, the forgetful functor $U\colon \Rieg \to \Set$ (preserves and) creates all limits.
\end{proposition}

This means we can construct arbitrary small limits using limits in $\Set$. For example, the terminal object is a singleton with obvious operations, which we call it the \emph{trivial rieg} (see Example \ref{ExampleTrivialRieg}). 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]
    The forgetful functor $U\colon \Rieg \to \Set$ has a left adjoint $F\colon \Set \to \Rieg$
\end{proposition}

Furthermore, we have a variation of the homomorphism theorem:
\begin{proposition}[Surj-inj factorization system]
    A rieg homomorphism is uniquely (up to the canonical isomorphism) decomposed into the composition of a surjective homomorphism followed by an injective homomorphism.
\end{proposition}

\memo{cite context and write monadic aspects}
% \begin{example}[Initial rieg: natural numbers]
% The rieg of natural numbers $\N$ is the initial object of $\Rieg$.
% \end{example}

% \begin{example}[Terminal rieg: trivial rieg]\label{ExampleTrivialRieg}
% As for every equational theory, the terminal rieg consists of only one element $0=1$. We call it the \emph{trivial rieg}.
% \end{example}

% For categorical (small) colimits, the existence follows from categorical universal algebra. However, concrete calculations tend to be exhausting. 
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.\]

\begin{question}
    Is there a combinatorial expression of elements of free algebras?
\end{question}

\begin{question}
    There is the unique rieg homomorphism for the free rieg for $\{x\}$ to $\N$ that sends $x$ to $0$.  For example,
    \[x\ex \ex n = \underbrace{x \ex x \ex \dots \ex x}_{n}\] is sent to $0$ or $1$, depending on the parity of $n$. What is that function? \memo{combinatorial game theory}
    % whether $n$ is odd or even.

    \memo{I found it! \url{https://golem.ph.utexas.edu/category/2006/10/classical_vs_quantum_computati_3.html\#c005578}}
\end{question}

% \begin{question}
%     What functions can be \dq{programmed} as an element of the free algebra? \memo{Using overflow riegs, there is a strong limitation. But for finite sequences?}
% \end{question}

\begin{proposition}[Quotient riegs]\label{PropositionQuotient}
    
\end{proposition}

% \section{Examples}
\newpage
\section{Riegs of Numbers}
\subsection{Non-negative numbers}
It's time to play with concrete examples! In this section, we will see \dq{numerical} examples. The prototypical example is the rieg of natural numbers. 
\begin{example}[Natural numbers]
The set of non-negative integers (or natural numbers) with usual operations $(\N,0,1,+,\ti,\ex)$ is a rieg. Note that $0^0=1$, as mentioned earlier. We call it the rieg of natural numbers. This is the initial object of the category $\Rieg$.
\end{example}

% \memo{$\{0,1,2,\dots \infty\}$ is a rieg. (Quotient rieg of cardinal arithmetic) and its quotient $\{0, \text{positive finite}, \infty\}$}
\memo{$\{0,1,2,\dots \infty\}$ is a rieg. (Quotient rieg of cardinal arithmetic). But it is not the case for its quotient rig $\{0, \text{positive finite}, \infty\}$, since $1^{\infty} \neq 2^{\infty}$}\memo{How about $\{0,1, \mathrm{plural}, \infty\}$? $\ch = (2,1)$}
% \memo{$\{0,1,2,\dots \infty\}$ is not a rieg at lest in the naive way. (Quotient rieg of cardinal arithmetic), since $1^\infty \noteq $ and its quotient $\{0, \text{positive finite}, \infty\}$}
\memo{We can construct \dq{$p$-adic} numbers or profinite constructions. $\lim \Mr{a}{b}$m $\lim \Mr{n}{1}$ and $\lim\Mr{n}{p^n}NOOO$}


\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}
\begin{question}
    What's the subrieg of $[0,\infty)$ generated by non-negative rational numbers? Are there any non-trivial equations? Is it isomorphic to \dq{free rieg} of a rig $\mathbb{Q}_{\geq}?$
\end{question}

\subsection{Finite system of numbers}
\begin{example}[Overflow riegs]
    Consider finite memory versions of the natural number rieg.
    % \emph{overflow riegs}. 
    For any natural number $n$, we define \emph{the overflow rieg with threshold $n$}. The underlying set is the set with $n+1$-elements
    \[\{0,1,2, \dots n-1, \TB\}.\]
    The operations are basically the same as the riegs of natural numbers, but values greater than or equal to $n$ overflow and are changed into $\TB$. Intuitively, the symbol $\TB$ means \dq{too big!}. For example, in the overflow rieg with threshold $5$, we have $0+1=1$, $2^3=\TB$, 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*}
\end{example}

\begin{example}[Trivial rieg]\label{ExampleTrivialRieg}
    The \emph{trivial rieg} is a singleton $\{\TB\}$ equipped with the unique rieg structure. In other words, it is the overflow rieg with threshold $0$ and the terminal object of the category $\Rieg$.
\end{example}

The overflow rieg with threshold $1$ will appear soon (Example \ref{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 in Section \ref{SectionCharacteristics}.

Let's briefly touch upon it here. First, simply considering $\Z/n\Z$ does not work well, because it is a ring not rieg (except $n=0$). However, by separating out $0$ or, more generally, small natural numbers, it is sometimes possible to develop modular arithmetic. 

\begin{example}[Parity rieg]\label{ExampleParityRieg}
The set $\{0, \text{positive odd}, \text{positive even} \}$ equipped with the intended operations, which are well-defined is a rieg.  We call it the \emph{parity rieg}.
\end{example}

Actually, for any $n$, it is possible to construct a finite rieg $M$ and decompose the unique rig homomorphism
\[\N \twoheadrightarrow \Z/n\Z\]
into a rieg homomorphism followed by a rig homomorphism
\[\N \twoheadrightarrow M \twoheadrightarrow \Z/n\Z.\]
% with a unique surjective rig homomorphism $M \twoheadrightarrow \Z/n\Z$,
In this sense, one can do modular arithmetic, including exponentiation! See Section \ref{SectionCharacteristics}.

\begin{example}[$\Mr{a}{b}$]
    
\end{example}

\memo{For any $n\in \N$, we can construct a finite rieg that has surjective rig homomorphism to $\Z/n\Z$. In this sense, we can treat exponentials in modular arithmetic. If you want to calculate exponential $\mod{5}$, you should use $\Mr{2}{20}$ Is it \dq{free rieg} of the rig?}

\memo{Rieg of functions with first-order differential coefficients}

\memo{What's called the exponential ring of complex numbers}

\memo{Cardinal arithmetic}

\memo{Some example from Heyting, e.g. max-min of [0,1]}

\memo{max-plus algebra}

\subsection{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]&\mathrm{OverFlow}_{2}\ar[r]&\mathrm{OverFlow}_{1}\ar[r]&\mathrm{OverFlow}_{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 subsection \ref{SubsectionProfinite}, we will see the profinite completion of $\N$, which is a refinement of $\N\cup\{\infty\}$
\end{example}
\subsection{Lists of numbers}

\subsection{Dual numbers}
\memo{Constructed by Yuhi Kamio}

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 \emph{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}

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 proposition \ref{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}

\subsection{Polynomials}
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).$

\begin{example}[Shift operator]
    
\end{example}

\newpage
\section{Characteristic and Modulo arithmetic}\label{SectionCharacteristics}
\memo{The most non-trival theorem in this section is a known result}
\subsection{Chracteristics}

Recall that a characteristic of a ring is a minimum positive integer $n$ such that
\[0=\underbrace{1+1+\dots +1}_{n \text{ times}},\]
if such $n$ exists, and otherwise $0$.

We will define similar notion to riegs. However, the exactly same definition does not work, since if we have a positive integer $n$ such that $0=n$, then $n-1$ is the additive inverse of $1$ and the rieg should be isomorphic to the trivial rieg (Proposition \ref{PropositionMinusOne}). 

We adopt a relaxed definition:
\begin{definition}[Characteristic]
    For a rieg $R$, its characteristic $\ch R$ is a minimum pair \memo{Clarify the meaning of \dq{minimum.} But I think there is no room for confusion...?} $(a,b)$ of non-negative integer $a$ and a positive integer $b$ such that 
    \[
    \underbrace{1+\dots +1}_{a \text{ times}}=
    \underbrace{1+\dots +1}_{a \text{ times}}+
    \underbrace{1+\dots +1}_{b \text{ times}}.
    \]
    If there does not exists such a pair, the characteristic is defined to be $\chz$.
\end{definition}

\begin{example}[Trivial rieg]
    The characteristic of the trivial rieg is $(0,1)$. Conversely, if the characteristic of a rieg $R$ is $(0,1)$, then $0=1$ and $R$ turns out to be trivial.

    More generally, if the characteristic of $R$ is $(0,b)$, then we have $0=1+\dots+1$ and $b-1 =-1$. Then we can conclude that $R$ is trivial and $b=1$. No rieg has characteristic $(0,b)$ for $b\geq2$.
\end{example}

\begin{example}[Overflow riegs]
\memo{later!}
\end{example}
\begin{example}[Parity riegs]
\memo{later!}
\end{example}

After reading the definition and examples, you may ask two questions: \dq{Is this definiton natural?} and \dq{Which pair $(a,b)$ can be realized as a characteristic of a rieg?} In the remaining part of this subsection, we will focus on the first question. The second question is the main topic of the next subsection.\memo{This turned out to be a known result.}


\subsubsection*{Is this definiton natural?}
From an abstract point of view, this defnition 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}

Therefore, what we need to do is classify the quoteits of $\N$.
The starting point is the classification of quotients of the additive monoid $\N$.
% By the classification of quotients of the additive monoid $(\N,0,+)$, 
It is known that all non-trivial congruence $\sim$ on $(\N,0,+)$ is of the form
 \[n \sim m \iff (n=m)\lor ((n,m\geq a) \land (n\equiv m \mod{b})) \]
% \[n \sim m \iff (n\equiv m \mod{b})\land ((n=m)\lor (n,m\geq a)) \]
with $a\geq0$ and $b>0$. \memo{reference} Let $\Mr{a}{b}$ denote the quotient additive monoid. It is quicker to look at the picture of $\Mr{3}{4}$ than to look at the logical symbols (Figure \ref{PictureModuleRieg}).

    \begin{figure}
    \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{Picture of $\Mr{3}{4}$}
    \label{PictureModuleRieg}
    \end{shaded}
    \end{figure}

For example, (the underlying additive monoid of) the trivial 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.
    The 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..}
\begin{proof}
    
\end{proof}
 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.}

\subsubsection*{Which pair $(a,b)$ can be realized as a characteristic of a rieg?}
\memo{For semirings, every value can be realized.}
% \begin{remark}[Is this definition natural?]
    
% \end{remark}

% For example, a rieg $R$ with characteristic $\ch R= (0,1)$ is a rieg with $0=1$, which is the trivial rieg.

\subsection{Classification of the quotients of $\N$}
\memo{On the terminology \dq{modulo riegs}}
Before we get into the theoretical considerations, let us list a few examples.

\begin{example}[$\N$ itself]
    $\N$ itself is a trivial modulo rieg.
\end{example}

\begin{example}[Trivial rieg]
    A singleton $\{\ast\}$ has a unique rieg structure. We call it \emph{trivial rieg}. It is the terminal rieg and can be regarded as a modulo rieg by the unique homomorphism $\N \to \{\ast\}$.
\end{example}

\begin{example}[Truth value rieg]
    As we will see later, the set of truth values $\2 = \{\bot, \top\}$ has a natural rieg structure, as $(\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 proposition 
    \[\text{IsPositive}\colon \N \twoheadrightarrow \2\]
    is a surjection and defines a modulo rieg.
    % The set $\{\text{zero},\text{positive}\}$ and the natural surjection $\N \to \{\text{zero},\text{positive}\}$ induces a rieg structure on $\{\text{zero},\text{positive}\}$. 
    % For several reasons, we call this rieg $\2$.
\end{example}

\begin{example}[Parity rieg]
    As a bit more non-trivial example, the natural surjection
    \[\N \twoheadrightarrow \{0, \text{positive odd}, \text{positive even} \}\]
    induces a modulo rieg. We call it the \emph{parity rieg}.
\end{example}

Before stating the classification theorem, we introduce two terminologies.

\begin{definition}[Tame number]
    A positive integer $n$ is said to be \emph{tame} if, for any prime factor $p$ of $n$, $p-1$ also divides $n$. 
\end{definition}

The list of tame numbers begins as:
\[1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 42, 48, 54, 60, 64, 72, 80, 84, 96, 100, 108, \dots.\]
Notice that there are infinitely many tame numbers since $2^k$ is tame.

The reason for considering tame numbers is the following algebraic paraphrase.
Simply put, \dq{$n$ is tame if and only if exponentials are also well-defined by $\mod{n}$.}
\begin{lemma}[Algebraic characterization of tame numbers]\label{LemmaAlgebraicCharacterizationOfTameNumbers}
For a positive integer $n$, the following conditions are equivalent:
\begin{enumerate}
    \item $n$ is tame.
    \item for any $x \in (\Z/n\Z)^{\times}$, $x^n \equiv 1 \mod{n}.$
\end{enumerate}
\end{lemma}
\begin{proof}
    First, we will prove (2), assuming (1). 
    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}.
    \]
    Therefore, it is enough 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}}$. But this immediately follows from tameness of $n$, since $\#  (\Z/ {p_i}^{k_i} \Z)^{\times} = (p-1)p^{k_i -1}$, which divide $n$.

    Conversely, we will prove (1) from (2). Let $p$ be an odd prime factor of $n$. (The case where $p=2$ is obvious.) The multiplicative group $(\Z/n\Z)^{\times}$ has a element $x$ whose order is $p-1$, because $(\Z/ {p}^{k} \Z)^{\times}$ is cyclic. \footnote{This is not obvious by definition, but well-known.} By the assumption $x^n \equiv 1 \mod n$, we have $p-1 \mid n$.
    % \[(\Z/ p^{k_l} \Z)^{\times} \simeq \Z/(p-1)p^{}\]
\end{proof}

\begin{remark}[Carmichael numbers]
This is reminiscent of Carmichael numbers, which are defined as a positive integer $n$ that satisfies
\begin{itemize}
    \item for any $x \in (\Z/n\Z)^{\times}$, $x^{n-1} \equiv 1 \mod{n}.$
\end{itemize}
Although the definitions are very similar, the only tame Carmichael numbers are obviously only trivial ones, namely $1$ and $2$. In light of these facts, rather than the boring name \dq{tame numbers,} perhaps we should call them anti-Carmichael numbers (?)
\end{remark}
\begin{definition}[Dimention]
    A \emph{dimension} of a positive integer $n$ is the maximum value of the exponent that appears in the prime factorization of $n$. It is denoted by $\di(n)$.
\end{definition}

For example, the dimentions of small numbers are $\di(1)=0, \di(2)=1, \di(3)=1, \di(4)=2, \di(5) = 1, \di(6)=1, \di(7)=1, \di(8)=3$.

\begin{remark}[Radical]\label{RemarkRadical}
    A dimension is inextricably linked to the notion of \emph{radicals} of positive integers.
    \memo{ABC conjecture} Recall that the radical of a positive integer $n$, often denoted by $\rad(n)$, is a positive integer obtained by replacing all exponents in the prime factorization of $n$ by $1$. For example, $\rad(5400)=\rad(2^3\cdot 3^3\cdot  5^2)=2\cdot  3\cdot  5 = 30$.

     The dimension $\dim(n)$ is the minimum $d$ such that $n$ divide $\rad(n)^d$, and conversely $\rad(n)$ is the maximum $1$-dimensional divisor of $n$.
\end{remark}




\begin{theorem}[Classification of modulo riegs \cite{burris1993tarski}]\label{TheoremPossibleChar}
For $a\geq 0$ and $b>0$, $\Mr{a}{b}$ has a rieg structure if and only if $b$ is a tame number whose dimension is at most $a$. 
% \begin{enumerate}
%     \item $a\geq \di(b)$
%     \item $b$ is tame.
% \end{enumerate}
\end{theorem}
\begin{proof}
    Assuming $\Mr{a}{b}$ has a rieg structure, we will prove $b$ is a tame 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 Lemma \ref{LemmaAlgebraicCharacterizationOfTameNumbers}, $b$ is tame. 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 \dim(b)$, we obtain \[\rad(b) ^a\equiv 0 \mod{b},\] equivalently, $a\geq \dim(b)$.

     Conversely, assuming that $b$ is a tame 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 \dim(b) \leq a \leq y_0,y_1.\] 
     If $x$ is coprime with $p$, it follows from tameness of $b$ and $\# (\Z/p^k \Z)^{\times} = (p-1)p^{k-1}$.
     The proof is complete.
\end{proof}

As a result, we obtain the complete (infinite) list of modulo riegs (Figure \ref{PictureListOfModuloRiegs}).


\begin{figure}
    \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}


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{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 $1,2,6,42,1806$ are the only tame numbers of dimension at most $1$. If $n$ is a $1$-dimensional tame number and $p$ is the maximum prime factor, then $n/p$ is also a ($0$ or $1$-dimensional) tame number and $p-1$ is a divisor of $n/p$. Therefore, we can inductively generate all $1$-dimensional tame 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 tame numbers.
\end{conjecture}
\cite{OEISsyl}\cite{burris1993tarski}

By a computer calculation, we know there is a $2$-dimensional tame number bigger than $10^{10000}$. 
\memo{In the case of $1$-dimensional tame 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 tame numbers.}
\begin{example}
    For any non-negative integer $n$, $1$ is a tame number whose dimension is $n$. 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 tame 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 tame 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 tame 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}
\begin{example}
For any non-negative integer $n$, its factorial $n!$ is tame. Furthermore, its dimension is at most $n$. It is because, for any prime number $p$, the number that $p$ divides $n!$ is given by Legendre's formula
\[
\sum_{k=1}^{\infty} \left\lfloor {\frac{n}{p^k}}\right\rfloor
\]
and is bounded from above by $n$ as follows:
\[
\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 $\Mr{n}{n!}$. \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 \emph{characteristic} of a rieg is \memo{write}
% \end{definition}

% \memo{Solve some Diophantus equation utilizing those riegs}

% \begin{definition}\label{DefinitionOrderCharacteristics}
    
% \end{definition}
% \section{Relation to other algebraic structures}


\subsection{Application: riegs of three elements}
$n=1,2$: Unique
\memo{Utilize characteristics theory}
% \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!}
% % \newpage
% % \input{2023_07_23Ver/riegsOfPropositions0729}

\section{Finite and Profinite arithmetics}\label{SectionFiniteandProfiniteArithmetic}
% \label{SubsectionProfinite}
\subsection{Introduction}

% % {Modular arithmetic with exponentials}
\subsubsection*{Finite arithmetic}
\memo{sent to Phenomena}
In this section, we treat modular arithmetic with exponentials. As an introduction, let us consider the following typical elementary number theory problem, which can be solved by modular arithmetic:

\begin{problem}
Find all pairs of natural numbers $(n,m)$ such that
    \[2^n +5 =m^2.\]
\end{problem}
\begin{answer}
Consider the remainder by $8$. If $n$ is greater than or equal to $3$, the left-hand side is congruent with $5$, and the right-hand side is one of the square remainders of $8$, which are $0,1,4$, and it's absurd. Therefore, it suffices to check all the cases where $n=0,1,2$,  and we find that $(n,m)=(2,3)$ is the only solution.
\end{answer}

In this example, when considering exponentiation modulo $8$, we should divide \dq{first exceptions}, namely three numbers $n=0,1,2.$ 

 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.

 \subsubsection*{Profinite arithmetic}

 \cite[][Chapter 7, section 1/ Chapter 10, section 1]{khrennikov2004p}
 \memo{J.Koizumi}

 Consider the next question
 \begin{problem}
     Find a two-digit natural number $n$ such that the last two digits of $3^n$ are equal to $n$.
 \end{problem}
 \begin{answer}
     $n=87$ is the only answer.
 \end{answer}

  \begin{problem}
     Find a three-digit natural number $n$ such that the last three digits of $3^n$ are equal to $n$.
 \end{problem}
 \begin{answer}
     $n=387$ is the only answer.
 \end{answer}
 \begin{problem}
     Find a four-digit natural number $n$ such that the last four digits of $3^n$ are equal to $n$.
 \end{problem}
 \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 a infinite sequence \[\dots a_4 a_3 a_2 a_1\] of dicimal digits
     % $\a_i \in \{0,1,2,3,4,5,6,7,8,9\}$
     such that, for any $k\geq 1$, the number $n=a_k \dots a_1 $ (regarded as decimal notation) satisfies $3^n \equiv n \mod{10^k}$?
 \end{question}
 The answer is Yes! (See Figure \ref{PictureListOfthreetotheN}) 
 % 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}$}
 

 \begin{figure}[h]
    \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
    % \\
    % 3^{2464195387} &\equiv 2464195387 \mod{10000000000}\\
    % 3^{62464195387} &\equiv 62464195387 \mod{100000000000}\\
    % 3^{262464195387} &\equiv 262464195387 \mod{1000000000000}\\
    % 3^{7262464195387} &\equiv 7262464195387 \mod{10000000000000}\\
    % 3^{27262464195387} &\equiv 27262464195387 \mod{100000000000000}
    \end{align*}
    \caption{Solutions of $3^n=n \mod{10^k}$}
    \label{PictureListOfthreetotheN}
    \end{shaded}
\end{figure}

%  \begin{figure}
%     \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}\\
%     3^{2464195387} \equiv 2464195387 &\mod{10000000000}\\
%     3^{62464195387} \equiv 62464195387 &\mod{100000000000}\\
%     3^{262464195387} \equiv 262464195387 &\mod{1000000000000}\\
%     3^{7262464195387} \equiv 7262464195387 &\mod{10000000000000}\\
%     3^{27262464195387} \equiv 27262464195387 &\mod{100000000000000}\\
%     \end{align*}
%     \caption{$3^x=x$}
%     \label{PictureListOfthreetotheN}
%     \end{shaded}
% \end{figure}

% \subsubsection*{Theoretical motivation}

% There is another more theoretical motivation to classify all modulo riegs.
% For rings, the quotient rings of the initial ring $\Z$ are easily classified and described as $\Z/n\Z$ using natural numbers $n$. This classification is important even if you are not interested in integer ring $\Z$ itself. It is because it can be used to define the \emph{characteristic} of a ring $R$ (or usually, fields), considering the unique ring homomorphism
% \[\Z \to R \text{ in }\Ring\]
% and its surjection-injection factorization.

% We can establish similar characteristics theory for riegs, utilizing quotient algebras of the initial rieg $\N$ (i.e. modulo riegs) and
% % We call them \emph{modulo riegs}. 
% % As in the ring case, we can discuss the theory of rieg's \dq{characteristic}, 
% considering the unique rieg homomorphism
% \[\N \to R\text{ in }\Rieg\]
% and its surjection-injection factorization.

% Just as examining the prime ideals of an integer ring $\Z$ reveals that the characteristics of any fields are either zero or prime, examining the modulo rieg (of $\N$) leads to properties about arbitrary riegs.
% For example, see Corollary \ref{CorollaryClassificationOfCharacteristics}. 



\subsection{The complete lattice of characteristics}
The characteristic of a rieg, a priori, takes value in the complete lattice
\[
    \qTame \coloneqq \N \times \N_{>} \cup \{\chz\},
\]
equipped with the component-wise (usual, divisibility) order relation.
In Theorem \ref{TheoremPossibleChar}, we specified the realizable values, which are the elements of
\[\Char = \{(a,b)\in \qTame\mid \text{$b$ is a tame number whose dimension is at most $a$}\},\]
which contains $\chz$ as well.
Let $\finChar$ denotes $\Char\setminus \{\chz\}$.

This order relation can be rephrased in terms of rigs and riegs:
\begin{proposition}
    For $(a,b), (a',b') \in \qTame$, $(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 \Tame$, $(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, $\qTame$ is isomorphic to the complete lattice of the quotient rigs of $\N$, and $\Tame$ is isomorphic to the complete lattice of the quotient riegs of $\N$.

\begin{lemma}\label{LemmaTameapprox}
    For any positive integer $b$, there is the minimum tame number $b'$ such that $b$ divides $b'$.
\end{lemma}
\begin{proof}
Here is a comcrete algorithm:
If $b$ is tame, then return $b$.
    If $b$ is not tame, then take the maximum prime number $p$ such that $p$ divides $b$ but $p-1$ does not divide $b$.
    And (recursively) return the minimum tame number $b'$ such that $\lcm (b, p-1)$ divides $b'$.

    This algorithm halts, since the taken prime number $p$ becomes smaller and smaller. It is easy to prove the minimality.
\end{proof}

\begin{example}[The minimum tame 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 tame number that is divided by $11$.
\end{example}

\begin{proposition}[Tame approximation]\label{PropositionTameapprox}
    For any $(a,b)\in \N\times \N_{>}$, there is the minimum $(a',b')\in \finChar$ such that 
    \[(a,b)\leq (a',b').\]
    % < \chz.\]
\end{proposition}
\begin{proof}
    First, by Lemma \ref{LemmaTameapprox}, we can take the minimum tame number $b'$ that is divided by $b$. Then, $a'$ is defined to be $\max(a,\dim{(b)})$.
\end{proof}
This implies that the embedding (order-preserving) function
\[\Char \hookrightarrow \qTame \]
has the left adjoint. \memo{This data defines a \dq{closure operator} on $\qTame$. but not preserving meets.}

As an immediate corollary, we obtain the following propositions.
\begin{proposition}
    $\finChar$ 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 Proposition \ref{PropositionTameapprox} to $(0,n)\in \N\times \N_{>}$.
\end{proof}

\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 integers}
Recall that the profinite completion of an algebraic structure $A$ is defined as the limit of its finite quotient algebras.
\begin{definition}
    \emph{The rieg of profinite integers} $\proN$ is defined as the profinite completion of the initial rieg $\N$.
\end{definition}

Our aim in this subsection is to analyze the algebraic and topological structures of $\proN$.
\begin{theorem}
    The underlying set of the rieg of profinite integers $\proN$ is given by
    \[\textstyle \proN = \N \coprod \proZ,\]
    where $\proZ$ denotes the usual ring 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}
    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 \finChar}$ 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}

\subsection{Discrete Dynamical System on Profinite Integers}
\subsection{Metrics}
% (related question: how about in $\Mr{\infty}{p^{\infty}}$)? This does not even exist!}
% \newpage
% \input{2023_07_23Ver/riegsOfPropositions0729}

\section{Riegs of Propositions}

In this subsection, we investigate the riegs that consist of \dq{propositions.}
The motivating examples are the rieg of truth values and 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 trivial 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 $1+1=1$}
\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 $\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 $([0,\infty],\oplus, \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$ 
    cannot have a rieg structure. 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{DefinitionIdempotent}
    A rieg $R$ is idempotent, if it satisfies the conditions in Proposition \ref{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 \ref{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)$ (Definition \ref{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 (Definition \ref{DefinitionIdempotent}). However, this is not sufficient:
\begin{example}[Idempotent rieg that is not a lattice]
    In Example \ref{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]
    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 (Definition \ref{DefinitionIdempotent}). 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 \emph{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 Proposition \ref{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 Example \ref{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{example}[totally ordered set]
    Let $P$ be a totally ordered set with a top element $1$ and a bottom element $0$.
    % \begin{align*}
    %     x\land y\leq z \iff &(x\leq y \land x\leq z) \lor (x\geq y \land y\leq z)
    % \end{align*}
    Since we have
    \[
        x\land y\leq z \iff 
        \begin{cases}
            x\leq 1 & (y\leq z)\\
            x\leq z &(y> z),
        \end{cases}
    \]
    the poset $P$ is a Heyting algebra with
    \[
    z^y =
    \begin{cases}
            1 & (y\leq z)\\
            z &(y> z).
        \end{cases}
    \]
    \memo{If this is a $T_1$-topological rieg, it should be very disconnected... maybe}
\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?}
\section{Free riegs and combinatorial games}

Free Lattices, Communication and Money Games
\section{Riegs of Structures}
\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 \emph{bicartesian closed category} gives an example of riegs.

\begin{definition}[Bicartesian closed category]
    A category $\C$ is \emph{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?}

\subsection{Connectedness and augmentation: enumerative comnibatorics}
\subsection{Riegs of sets}
\subsection{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 concatenations 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}$}

\subsection{Riegs of graphs}
\subsection{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$.
\subsection{Riegs of loops: Counting repeating dicimals}


\subsection{Riegs of Higher structures}
% \subsection{Bicartesian closed bicategory}
\subsection{Riegs of categories}
\subsection{Riegs of finite groups}
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}


\subsection{Functorial construction of riegs}
\subsection{Functor from a locally bicartesian closed category}
\subsection{Examples of induced rieg homomorphisms}
\subsection{Categories and discrete fibrations}
\memo{categorification of the multiset construction}
\subsection{Topological spaces and \'etale maps}
\subsection{Quasitoposes}
\memo{Heyting algebra}
\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}



% \section{Rieg of multisets, Liouville's divisor theorem}
% \section{Riegs from toposes, repeating decimal}
\memo{CC and CCC functor, \'etendue, logical morphism, directed graph, and group actions}
% \input{Games}
% \input 

\section{Structures of riegs}
\subsection{Canonical preorder of a rieg}
\begin{definition}[Canonical preorder of a monoid]
    The \emph{canonical preorder} of a monoid $(M, \ast, e)$ is defined by \[x\leq y \iff \exists z\in M ( x \ast z = y).\]
\end{definition}


\begin{definition}[Canonical preorder of a rig]
    The \emph{canonical preorder} of a rig or rieg is the canonical preorder with respect to the addition.
\end{definition}

\begin{example}
    The canonical preorder of the natural number rieg $\N$ is the usual total order.
\end{example}

This preorder is used in several contexts.
\begin{remark}[Dioids]\label{RemarkDefinitionOfDioids}
    A rig $R$ is called \emph{dioid} if the canonical preorder is antisymmetric (i.e., partial order). This structure is used for algorithm theory \cite{gondran2008graphs}. As mentioned in Remark \ref{RemarkDioidsandRiegs}, until now, the author does not know the direct connection between dioids and riegs.
\end{remark}



\begin{definition}[Minimal element]
    An element $x\in R$ of a rieg $R$ is said to be minimal if it satisfies the following two conditions:
    \begin{enumerate}
        \item $\lnot(x\leq 0)$
        \item For any $0\leq y \leq x$, $y=0$ or $y=x$.
        % \item If $x=y+y'$, then $y=0$ or $y'=0$.
    \end{enumerate}
\end{definition}

The second condition is equivalent to saying that ``
If $x=y+y'$, then $y=0$ or $y'=0$." This condition is some sense of indecomposability.

\begin{question}
    Can we replace the first condition with a more simply looking condition $x \neq 0$? In other words,
    Is $0$ the only minimum element in a rieg?  Is $0$ the only element that has the additive inverse?

    No! by the dual number rieg, see subsubsection \ref{SubsubsectionDualNumbers}.
\end{question}



\subsection{Connected Element}
\begin{definition}
    An element $x\in R$ of a rieg $R$ is said to be \emph{connected} if it satisfies the following two conditions:
    \begin{enumerate}
        % \item $(-)^{x}\colon R \to R$ is a rig homomorphism.
        \item $0^x= 0$ 
        \item $(a+b)^x=a^x + b^x$ .
    \end{enumerate}
\end{definition}

In other words, $x$ is connected if $(-)^{x}\colon R \to R$ is a rig homomorphism.

\begin{proposition}[Internally connected objects and connected elements]
    
\end{proposition}


\subsection{Connectedly based rieg}

\begin{proposition}
    For a connectedly based rieg, 
    \[0^x = \]
\end{proposition}

\subsection{infinitesimal element}
\memo{motivation: In a sufficiently disconnected (for example, $T_1$) topological rieg, $0$ and $1$ are disconnected? e.g. $\{0\}\sqcup (0,\infty)$ No, the weak infinite dimensional sphere}
\begin{definition}\label{def:infinitesimalelement}
    An element $x\in R$ of a rieg $R$ is called \emph{infinitesimal} if 
    \[
    0^x=1
    \]
    holds. The set of all infinitesimal elements is denoted by  $\Inf_R\subset R$
\end{definition}
\begin{lemma}
    $\Inf_R$ is an ideal of $R$, i.e., 
    \begin{itemize}
        \item we have $0_R\in \Inf_R$, 
        \item for any $i,j\in \Inf_R$, we have $i+j\in \Inf_R$, and
        \item for any $i\in \Inf_R$ and $r\in R$, we have $ri\in \Inf_R$.
    \end{itemize}
    Furthermore, if $R$ is a $T_1$-topological rieg, the ideal $I_R$ is an closed subset.
\end{lemma}
The unit element $1_R$ cannot be infinitesimal unless $R$ is trivial.

\memo{Heyting, locally connected, strict initial}

% \input{FutureWorks}
% \appendix
% \input{Programs}

\section{Possibly interesting Structures}
\begin{definition}

    An element of a rieg $x\in R$ is \emph{\loga} if the exponential function $y\mapsto x^y$ is injective. 
\end{definition}

\memo{Is the subobject classifier \loga? This is difficult question. For example, even if two sets have the same cardinality of powersets, we cannot prove those sets have same cardinality. In fact, it is independent from ZFC.}

\memo{endo of $(0, \infty)$}

\printbibliography

\appendix
\section{Rigs}
\subsection{definition}
\subsection{augmentated rigs}
For our purpose of applying rieg theory to enumerative combinatorics, it is natural to consider homomorphism from a ri(e)g to $\N$. We call such a structure, augmentation. \memo{It's conventional in ring theory}
\begin{definition}
    For a rig $R$, an ($\N$-)augmentation of $R$ is a rig homomorphism $R\to \N$.
\end{definition}

\end{document}