← Notes on Rieg Theory

Older Versions__2023_07_23Ver__Basic_Theory.tex

\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]
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 equipped with a $R$-module structure on itself.
\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