← Notes on Rieg Theory
Older Versions__2023_07_23Ver__riegsOfPropositions0729.tex
\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}
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, take an arbitrary element $x\in X$ and define the exponential as
\[
A^B\coloneqq
\begin{cases}
A & (x\in B)\\
X & (x \notin B).
\end{cases}
\]
This rieg structure is given by the composition of two rig homomorphisms. The first one is a rig homomorphism to the rig of truth value $\2 = \{\bot, \top\}$ defined as
\[\Po{X} \to \2\colon A \mapsto \dq{x\in X}.\]
The other is the unique rig homomorphism
\[\2 \to \End{(\Po{X}, X, \cap)},\]
which sends $0\in \2$ to the constant funciton $\mathrm{const}_{X}\colon \Po{X} \to \Po{X}$ and $1\in \2$ to the identity function $\mathrm{id}_{X}\colon \Po{X} \to \Po{X}$.
\memo{Since rig homomorphisms $\Po{X} \to \2$ correspond to ultrafilters on $X$, we can construct similar rieg structure for each ultrafilter $\mathcal{F}$ on $X$. The above example is the special case where $\mathcal{F}$ is a principal filter generated by $x\in X$.}
% where $\2$ denotes the rieg of truth values.
% \begin{itemize}
% \item $\Po{X}\to \2= \{\bot, \top\}$
% \item $\2 \to \End{(\Po{X}, X, \cap)}$
% \end{itemize}
If $X$ has at least two elements, this rieg is not a Heyting algebra, because
\[\{x\}^{\{x\}}=\{x\}\neq X.\]
\end{example}
\begin{proposition}
A rieg $R$ is a Heyting algebra, if and only if it satisfies the following additional equations:
\begin{itemize}
\item $1+x=1$
% \item $x\ti x=x$
% \item $1+1=1$ %$x+x = x$
\item $x^x =1$
% \item $x(y+1)=x$ %$$xy+y=y$
% \item $x^{y+1}=x$ %$y y^x = y$
% \item $(x+y)y=y$
\item $x y^x = xy$
\end{itemize}
\end{proposition}
\memo{Are all of them necessary?}
\begin{corollary}
The category of Heyting algebras $\HeyAlg$ is a reflective full subcategory of the category of riegs $\Rieg$.
\[
\begin{tikzcd}
\HeyAlg \ar[r, shift right, hookrightarrow]&\Rieg \ar[l, shift right]
\end{tikzcd}
\]
\end{corollary}
The construction of the left adjoint is the usual one: quotient by new equations. For example, the associated Heyting algebra of $\N$ is the Heyting algebra of truth values $\{\bot, \top\}.$\footnote{This particular example is a trivial case, since a left adjoint preserves colimits.}
The relation between Heyting algebras and riegs is not an addition of structures, but an addition of properties. In this respect, it is closer to the relationship between abelian groups and groups rather than to the relationship between rings and groups.
\memo{Full sub. Birkhoff's theorem}
\memo{Is it Malcev?}