http://www.cs.upc.edu

††thanks: This research was supported the recognition 2017SGR-856 (MACDA) from
AGAUR (Generalitat de Catalunya).

# Equidecomposable magmas

Carles Cardó  Departament de Ciències de la Computació,
Campus Nord, Edifici Omega, Jordi Girona Salgado 1-3. 08034
Universitat Politècnica de Catalunya
Barcelona,
Catalonia (Spain<EMAIL_ADDRESS>
###### Abstract.

A magma is called equidecomposable when the operation is injective, or, in
other words, if $x+y=x^{\prime}+y^{\prime}$ implies that $x=x^{\prime}$ and
$y=y^{\prime}$. A magma is free iff it is equidecomposable and graded, hence
the notion of equidecomposability is very related to the notion of freeness
although it is not sufficient. We study main properties of such magmas. In
particular, an alternative characterization of freeness, which uses a weaker
condition, is proved. We show how equidecomposable magmas can be split into
two disjoint submagmas, one of which is free. Certain tranformations on finite
presentations permit to obtain a reduced form which allows us identify all the
finite presented equidecomposable magmas up to isomorphisms.

###### Key words and phrases:

Equidecomposable magma, Free magma, Initial magma, Full magma, Isomorphism of
magmas, Jónsson-Tarski algebra

###### 1991 Mathematics Subject Classification:

08A02, 08A30, 08B20, 08C15, 20N99

##  1\. Introduction

A magma is _equidecomposable_ when given two decompositions of an element,
$x+y$ and $x^{\prime}+y^{\prime}$, we have that they are the same,
$x=x^{\prime}$ and $y=y^{\prime}$. A magma is free iff it is equidecomposable
and graded, [5]. Hence, the notion of equidecomposability is very related to
the notion freeness although it is not sufficient. Since this condition is so
strong, one could wonder if the totality of such magmas can be identified. We
study the main properties of equidecomposable magmas, show characterizations,
and finally, we classify up to isomorphisms all the finitely presented
equidecomposable magmas. Thus, this article proportions a good perspective of
this kind of structures.

We review some preliminary and necessary concepts in Section 2, which were
already proved in [5], with some extra result. The article is almost self-
contained, with the exception of the proofs of a few lemmas.

In Section 3 we define and see first examples of equidecomposable magmas.
Section 4 reviews freeness. In particular we obtain an alternative
characterization of freeness, by weakening the condition of being graded. A
magma is _initial_ iff it can be generated entirely by its indecomposable
elements. Then, a magma is free if and only if is equidecomposable and
initial.

Another important kind of magmas is that of _full_ magmas. A magma is full iff
all its elements are decomposable. We show in Section 5 that any
equidecomposable magma can be split into two submagmas, the largest full
submagma and the initial submagma, as:

$\displaystyle M=\mathfrak{I}(M)\sqcup\mathfrak{F}(M),$

where $\mathfrak{I}(M)$ and $\mathfrak{F}(M)$ denote respectively the initial
part and the largest full magma and $\sqcup$ is the disjoint union of sets.

In section 6, we characterize equidecomposable magmas as a quotient of a free
magma by a closed congruence. This allows us to study finite presentations,
Section 7, and we show how to obtain a fixed form for finite presentations of
an equidecomposable magma. More specifically, for each finitely presented
equidecomposable magma $M$ there is an injective mapping
$\varphi:A\longrightarrow\mathbb{M}_{A}$, with some additional conditions,
such that $M\cong\langle A\mid\varphi\rangle$. We write $\mathbb{E}(\varphi)$
these magmas. Using this form we identify up to isomorphisms all the finitely
presented equidecomposable magmas. We say that two mappings
$\varphi:A\longrightarrow\mathbb{M}_{A}$ and
$\psi:B\longrightarrow\mathbb{M}_{B}$ are _conjugated_ when they are the same,
up to renaming the generators $A$ and $B$. We will prove in the last Section 8
that two magmas $\mathbb{E}(\varphi)$ and $\mathbb{E}(\psi)$ are isomorphic
iff $\varphi$ and $\psi$ are conjugated.

##  2\. Notation and preliminaries on magmas

A _magma_ is a set $M$ with an operation $+:M\times M\longrightarrow M$. A
_submagma_ of a magma $M$ is a subset of $M$ that is stable for the operation.
For convenience, we accept the empty set as a magma. An element $z\in M$ is
_decomposable_ iff there are $x,y\in\mathbb{M}$ such that $z=x+y$, otherwise
it is said _indecomposable_. We denote $\mathcal{I}=\\{0\\}$ the _trivial_
magma with only one element.

Notions of _lattice, semi-lattice, direct product, homomorphism, isomorphism,
monomorphism_ , and _epimorphism_ of magmas are defined as is usual. See, for
example, [3, 4, 8, 13, 6] for algebraic elementary concepts.

######  Definition 2.1.

Given a non-empty subset $X$ of a submagma $M$, $\langle X\rangle$ denotes the
least submagma containing $X$, that is:

$\displaystyle\langle X\rangle=\bigcap_{X\subseteq N}N.$

We say that $X$ _generates_ $\langle X\rangle$. Given two submagmas
$N,N^{\prime}\subseteq M$, we write $N\vee N^{\prime}=\langle N\cup
N^{\prime}\rangle$.

We also define $\langle\\!\langle X\rangle\\!\rangle=\bigcup_{k\geq 1}X_{k}$
where $X_{k}$ is the sequence:

$\displaystyle X_{1}$ $\displaystyle=X;$ $\displaystyle X_{k}$
$\displaystyle=\bigcup_{\stackrel{{\scriptstyle i,j\geq
1}}{{i+j=k}}}X_{i}+X_{j},\,\,\mbox{ for }k>1.$

######  Lemma 2.2.

Given a non-empty subset $X$ of a submagma $M$, $\langle
X\rangle=\langle\\!\langle X\rangle\\!\rangle$.

###### Proof.

See [4, p. 33]. ∎

######  Definition 2.3.

$\sqcup$ denotes de disjoint union of sets. Given a non-empty set $A$ consider
the sequence of sets:

$\displaystyle X_{1}$ $\displaystyle=A;$ $\displaystyle X_{k}$
$\displaystyle=\bigsqcup_{\stackrel{{\scriptstyle i,j\geq
1}}{{i+j=k}}}X_{i}\times X_{j},\,\,\mbox{ for }k>1.$

The _free magma on_ $A$ is the magma $(\mathbb{M}_{A};+)$, where
$\mathbb{M}_{A}=\bigcup_{k\geq 1}X_{k}$ and $x+y=(x,y)$ for each
$x,y\in\mathbb{M}_{A}$. In general, we say that a magma $M$ is _free_ iff
there is some set $A$ such that $M\cong\mathbb{M}_{A}$. The _length_ of an
element $x\in\mathbb{M}_{A}$ is defined as $\ell(x)=k$ where $x\in X_{k}$.
Indeed, the length is an epimorphism of magmas,
$\ell:\mathbb{M}_{A}\longrightarrow\mathbb{N}$ with
$\ell(x+y)=\ell(x)+\ell(y)$, for any $x,y\in\mathbb{M}_{A}$.

######  Remark 2.4.

The set $A$ is the unique minimal generator set of $\mathbb{M}_{A}=\langle
A\rangle$. We have adopted the definition of Bourbaki [3, p. 81] which is
equivalent to define freeness by satisfying the _universal mapping property_ ,
see [4, p. 71].

######  Notation 2.5.

Following the same notation in [5], the cyclic free magma is written
$\mathbb{M}$ and we take as a generator the symbol $1$. Thus,
$\mathbb{M}=\mathbb{M}_{\\{1\\}}$ and its elements are of the form
$1,(1+1),1+(1+1),(1+1)+1,\ldots$. We use the following abbreviations, $2=1+1$,
and:

$\displaystyle 1_{-}=1,\,\,\,\,\,\,\,\,\,(n+1)_{-}=n_{-}+1,$ $\displaystyle
1_{+}=1,\,\,\,\,\,\,\,\,\,(n+1)_{+}=1+n_{+},$

for any integer $n\geq 0$.

A _polynomial_ over a magma $M$ is a mapping $P:M^{n}\longrightarrow M$,
defined by the substitution of the _variables_ $x_{1},\ldots,x_{n}$ of a term
$P\in\mathbb{M}_{\\{x_{1},\ldots,x_{n}\\}}$ by elements of $M$. Some example
of polynomials are $P(x)=x+(x+x)$ or $P(x,y,z)=(x+y)+z$. More formally:

######  Definition 2.6.

Let $M$ be a magma and let $P\in\mathbb{M}_{Z}$, where $Z$ is a finite set
called the _variables_. If $\ell(P)=1$, the _polynomial over $M$_ is defined
as the _identity mapping_ $P:M\longrightarrow M$, $P(z)=z$. If $\ell(P)>1$,
then $P$ can be decomposed as $P=Q+R$, where $Q\in\mathbb{M}_{Y}$,
$R\in\mathbb{M}_{Z}$, and $X\cup Y\subseteq Z$. Let
$X=\\{x_{1},\ldots,x_{r}\\}$, $Y=\\{y_{1},\ldots,y_{s}\\}$, and
$\\{z_{1},\ldots,z_{n}\\}=X\cup Y$. The _polyomial over $M$_ is the mapping
$P:M^{n}\longrightarrow M$, defined recursively as:

$\displaystyle
P(z_{1},\ldots,z_{n})=Q(x_{1},\ldots,x_{r})+R(y_{1},\ldots,y_{s}).$

In a free magma each submagma has a unique minimal generator set which can be
calculated as the union of the necessary generators to generate individually
each element of the submagma.

######  Definition 2.7.

Given a non-empty submagma $N\subseteq\mathbb{M}_{A}$, consider the mapping
$g_{N}:N\longrightarrow 2^{N}$ defined recursively as:

$\displaystyle g_{N}(z)=\begin{cases}g_{N}(x)\cup g_{N}(y)&\mbox{ if
}z=x+y\mbox{ for some }x,y\in N;\\\ \\{z\\}&\mbox{ otherwise. }\end{cases}$

We define $\mathcal{G}(N)=\bigcup_{x\in N}g_{N}(x)$ when $N$ is non-empty, and
$\mathcal{G}(\emptyset)=\emptyset$.

######  Lemma 2.8.

Given a non-empty submagma $N\subseteq\mathbb{M}_{A}$, $\mathcal{G}(N)$ is the
unique minimal generating set of $N$. We have that if $N$ is a submagma of
$\mathbb{M}_{A}$, then $\langle\mathcal{G}(N)\rangle=N$; and if $X$ is a
subset of $\mathbb{M}_{A}$, then $\mathcal{G}(\langle X\rangle)\subseteq X$.
In particular, $\langle\cdot\rangle$ and $\mathcal{G}$ form a Galois
connection.

###### Proof.

See [5]. ∎

######  Lemma 2.9.

Given a non-empty submagma $N\subseteq\mathbb{M}_{A}$ we have that $x+y\in N$
iff either $x,y\in N$ or $x+y\in\mathcal{G}(N)$.

###### Proof.

See [5]. ∎

######  Definition 2.10.

Given a magma $M$, a set $X\subseteq M$ is said _closed_ iff $x+y\in X$
implies that $x,y\in X$.

The intersection and the union of closed sets are closed. Hence, closed sets
of a magma $M$ form a complete lattice with bounds $\emptyset$ and $M$. The
complement of a closed set is a submagma. Here we are interested in the case
that closed sets are in addition submagmas. See [5, 12] for some questions on
closed sets

##  3\. Equidecomposable magmas

######  Definition 3.1.

We say that a magma $M$ is _equidecomposable_ iff for each
$x,y,x^{\prime},y^{\prime}\in M$ we have:

$\displaystyle x+y=x^{\prime}+y^{\prime}\implies x=x^{\prime},y=y^{\prime}.$

Equivalently, $M$ is equidecomposable iff the operation $+:M\times
M\longrightarrow M$ is injective. We will use the abbreviation _equidec_ for
equidecomposable magmas.

######  Example 3.2.

The trivial magma $\mathcal{I}=\\{0\\}$ is trivially equidec since the
equation $x+y=x^{\prime}+y^{\prime}$ has the unique solution
$x=y=x^{\prime}=y^{\prime}=0$. Free magmas $\mathbb{M}_{A}$ are also equidec.

Since $|M\times M|=|M|^{2}>|M|$, provided $|M|>1$, by the pigeonhole
principle, the trivial magma is the unique equidec finite magma.

The equidecomposability condition is so strong that there are not commutative,
associative, with-neutral-element, nor medial equidec magmas, excepting the
trivial magma. Let $M$ be an equidec magma. If $M$ is commutative, then for
all $x,y\in M$:

$\displaystyle x+y=y+x\implies x=y\implies M\cong\mathcal{I}.$

If $M$ is associative, then for all $x,y\in M$:

$\displaystyle x+(y+x)=(x+y)+x$ $\displaystyle\implies$ $\displaystyle
x=x+y\mbox{ and }y+x=x$ $\displaystyle\implies$ $\displaystyle x+y=y+x.$

Therefore, $M$ is commutative, and then $M\cong\mathcal{I}$. The cases of
magmas with neutral element and medial magmas are similar (see [10] for medial
magmas).

######  Example 3.3.

We see some constructions of equidec magmas. Since submagmas inherit the
operation, if $N$ is a submagma of $M$ and $M$ is equidec, then $N$ is
equidec. It is also trivial to check that the direct product of two equidec
magma is an equidec magma. However the direct product is not in general
finitely generated. Consider, for example, the free magma
$\mathbb{M}_{A}\times\mathbb{M}_{B}$ which needs infinite generators; see
later Theorem 5.12. We will see that the free product of two finitely
presented equidec magmas yields an equidec magma; see later Example 8.5.

The length $\ell:\mathbb{M}\longrightarrow\mathbb{N}$ is an epimorphism of
magmas. However, $(\mathbb{N},+)$ is not equidec since it is commutative and
associative, see Example 3.2, which shows that the class of equidec magmas is
not closed under image of homomorphisms. Equidec magmas do not form a variety
but a quasivariety, see [4, p. 250].

######  Example 3.4.

Let us write $\mathbf{Tree}$ the magma of planar binary trees with finite or
infinite depth. Given two trees $x,y\in\mathbf{Tree}$, we consider the tree
$x+y$ as the result of join $x$ and $y$ by a new root. Then,
$(\mathbf{Tree},+)$ is an equidec magma. $\mathbf{Tree}$ is an extension of
the cyclic free magma. There is a monomorphism
$\Phi:\mathbb{M}\longrightarrow\mathbf{Tree}$, defined by $\Phi(1)=\circ$,
where $\circ$ is the tree with only one vertex. For example:

$\displaystyle\Phi\Big{(}(1+1)+(1+(1+1))\Big{)}={\forest
fortree={circle,draw,lsep=1pt,ssep=10pt}[[[][]][[][[][]]]]}\,.$

$\mathbf{Tree}_{\infty}$ denotes the set of infinite trees, and
$\mathbf{Tree}_{<\infty}$, the set of finite trees. Both are submagmas and:

$\displaystyle\mathbf{Tree}_{<\infty}=\Phi(\mathbb{M}),\,\,\,\,\,\,\mathbf{Tree}_{\infty}=\mathbf{Tree}\setminus\Phi(\mathbb{M}).$

######  Proposition 3.5.

Let $M$ be an equidec magma, $P$ a polynomial over $M$ with $n$ variables, and
$k\in M$. The equation:

$\displaystyle P(x_{1},\ldots,x_{n})=k,$

has at most one solution.

###### Proof.

By induction on the length of the polynomial. If $\ell(P)=1$, then $n=1$, and
$P(x)=x$. The equation has trivially one solution, $x=k$. We assume that the
statement is true for polynomials with length less or equal to $m$, with $m>1$
and let $P$ be a polynomial with $\ell(P)=m+1$. We suppose that $k$ can be
decomposed as $k=k_{1}+k_{2}$, otherwise the equation has no solution and we
are done. Since $\ell(P)>1$, we can decompose $P$ as $P(x)=P_{1}(x)+P_{2}(x)$,
where $x=(x_{1},\ldots,x_{n})$. Since $M$ is equidec:

$\displaystyle P(x)=k\implies P_{1}(x)+P_{2}(x)=k_{1}+k_{2}\implies
P_{1}(x)=k_{1},P_{2}(x)=k_{2}.$

Equations $P_{i}(x)=k_{i}$, $i=1,2$ have length less than $m+1$, and by
hypothesis of induction these equations has at most one solution. If both
equations $P_{i}(x)=k_{i}$, $i=1,2$ have solution, the equation $P(x)=k$ has a
unique solution; if one of them does not have solution, the equation does not
have solution. ∎

######  Example 3.6.

Let $P(x,y)$ be a polynomial over the equidec magma $(M;+)$. The magma
$(M;\odot)$ with $x\odot y=P(x,y)$ is equidec. This is a straightforward
consequence of Proposition 3.5.

######  Example 3.7.

Let $\Sigma=\\{\alpha,\beta\\}$ be an _alphabet_ and let
$(\Sigma^{*};\cdot,\varepsilon)$ be the free monoid on $\Sigma$. We write
$\mathbf{Lan}=2^{\Sigma^{*}}$ the set of _languages_ on the alphabet $\Sigma$.
See [9] for terminology on formal languages. We adopt the usual convention of
notating singleton languages $\\{x\\}$ as $x$.

Given, $L,L^{\prime}\in\mathbf{Lan}$, consider the operation:

$\displaystyle L\oplus L^{\prime}=\alpha L\cup\beta L^{\prime},$

and let us see that $(\mathbf{Lan};\oplus)$ is a non-countable equidec magma.
First we see an elementary result on sets. Let $X,Y,Z,T$ be sets such that:

$\displaystyle X\cap Y=X\cap T=Z\cap Y=Z\cap T=\emptyset.$

We have that:

$\displaystyle X\cup Y=Z\cup T\implies X=Z,Y=T.$

Let us see a quick proof:

$\displaystyle X=X\cap(X\cup Y)=X\cap(Z\cup T)=(X\cap Z)\cup\emptyset=X\cap
Z,$

whence $X\subseteq Z$. By symmetry we get $X=Z$. Similarly we get $Y=Z$. Now
we can see that the operation $\oplus$ is equidec. We suppose: $L\oplus
L^{\prime}=H\oplus H^{\prime}$, for some
$L,L^{\prime},H,H^{\prime}\in\mathbf{Lan}$. This means: $\alpha L\cup\beta
L^{\prime}=\alpha H\cup\beta H^{\prime}$. Clearly $\alpha L\cap\beta
H^{\prime}=\beta L^{\prime}\cap\alpha H=\emptyset$ and $\alpha L\cap\beta
L^{\prime}=\alpha H\cap\beta H^{\prime}=\emptyset$. Then, applying the above
result, $\alpha L=\alpha H$ and $\beta L^{\prime}=\beta H^{\prime}$.
Therefore, $L=H$ and $L^{\prime}=H^{\prime}$.

Let us see some submagmas in $\mathbf{Lan}$. A language $L$ is _prefix free_ ,
when $xy\in L$ implies that $x\not\in L$. The set of prefix free languages is
a submagma. Many classical families of languages, such as finite languages,
_regular_ languages, _context-free_ languages, _context-sensitive_ languages,
_recursive_ languages, amongst others, are submagmas. For example, the family
of regular languages is closed, amongst other operations, under products and
unions; see [9]. Thus, if $L,L^{\prime}$ are regular, then $\alpha L\cup\beta
L^{\prime}$ is.

There is a copy of $\mathbf{Tree}$ in $\mathbf{Lan}$. Given a binary tree we
label left branches with $\alpha$, and right branches, with $\beta$. The path
from the root to a vertex is a word in $\Sigma^{*}$. We define the
monomorphism $\Psi:\mathbf{Tree}\longrightarrow\mathbf{Lan}$ where $\Psi(x)$
is the set of all the word paths of the leaves of the tree $x$. We have
indeed:

$\displaystyle\mathbb{M}\cong\Psi(\mathbf{Tree}_{<\infty})=\langle\varepsilon\rangle.$

######  Example 3.8.

A _left semiringoid_ structure $(M;+,\cdot,1)$ is a magma $(M;+)$ such that,
for any $x,y,z\in M$:

$\displaystyle x\cdot 1=1\cdot x=x,$ $\displaystyle(x\cdot y)\cdot
z=x\cdot(y\cdot z),$ $\displaystyle x\cdot(y+z)=x\cdot y+x\cdot z.$

A _right semiringoid_ is defined symmetrically. Given $a\in M$, the set
$a\cdot M$ is a submagma of $M$, which we call _principal_ ($M\cdot a$ for the
case of right semiringoids). A homomorphism of semiringoids preserves the sum,
the unity and the product. An anti-homomorphism preserves the sum, the unity,
and reverses the product order.

The free magma $(\mathbb{M};+,\cdot,1)$ is a left semiringoid, where the
product $x\cdot y$ consists in substituting each $1$ of $y$ by $x$. See [1, 2]
for operations defined over a free magma. In [5] we studied the arithmetical
properties of this structure. Every cyclic submagma of $\mathbb{M}$ is
principal, $\langle a\rangle=a\mathbb{M}$.

The product of languages is distributive with $\oplus$:

$\displaystyle(L\oplus L^{\prime})S=(\alpha L\cup\beta L^{\prime})S=\alpha
LS\cup\beta L^{\prime}S=LS\oplus L^{\prime}S.$

In addition: $L\cdot\varepsilon=\varepsilon\cdot L=L$. Thus,
$(\mathbf{Lan};\oplus,\cdot,\varepsilon)$ is a right semiringoid.

Let us compare the semiringoids $\mathbf{Lan}$ and $\mathbb{M}$. We have that
$\langle\varepsilon\rangle$ and $\langle 1\rangle=\mathbb{M}$ are anti-
isomorphic ringoids. That is, both are the same up to the order of the factors
in the product operation. However, $\mathbf{Lan}$ is much complex magma.
Cyclic submagmas of $\mathbf{Lan}$ are not principal. For example:
$\langle\varepsilon\rangle\subsetneq\mathbf{Lan}\cdot\varepsilon=\mathbf{Lan}$.
Finally, $\mathbb{M}$ with the product, $(\mathbb{M};\cdot,1)$, is a non-
finitely generated free monoid, while $(\mathbf{Lan};\cdot,\varepsilon)$ has,
for instance, the non-trivial relation $\beta^{*}\cdot\beta^{*}=\beta^{*}$.

The magma $\mathbf{Tree}$ can also enriched to obtain a ringoid. We define the
product of two trees $x\bullet y$ as the result of hanging the tree $x$ from
each leave in $y$. For instance:

$\displaystyle\Big{(}{\forest
fortree={circle,draw,lsep=1pt,ssep=10pt}[[][]]}\Big{)}\,\,\,\bullet\,\,\,\Big{(}\,{\forest
fortree={circle,draw,lsep=1pt,ssep=10pt}[[][[][]]]}\Big{)}={\forest
fortree={circle,draw,lsep=1pt,ssep=10pt}[[[][]][[[][]][[][]]]]}\,.$

##  4\. Graded, semigraded, initial and free magmas

Let $(\mathbb{N};+)$ the set of positive integers with the ordinary sum. A
_gradation_ of a magma $M$ is a homomorphism
$\ell:M\longrightarrow\mathbb{N}$, so that $\ell(x+y)=\ell(x)+\ell(y)$. The
length is a gradation for free magmas. In [5] we proved that a magma is free
iff it is equidec and graded.

######  Example 4.1.

The condition of being equidec is necessary. For example, the commutative
monoid $(\mathbb{N};+)$ is graded with $\ell(x)=x$, but it is not a free
magma.

The condition of being graded is necessary. $\mathbf{Tree}$ is not free
because we have, for example, the relation given by the infinite full binary
tree $t$, $t=t+t$. This relation disallows to define a gradation since
$\ell(t)=\ell(t)+\ell(t)$ implies that $\ell(t)=0$, which is impossible since
gradations must be positive.

######  Example 4.2.

$\mathbf{Lan}$ is not free since, for example, we have the relation
$\emptyset\oplus\emptyset=\emptyset$, or for example:

$\displaystyle\varepsilon\oplus\beta^{*}\alpha=\alpha\cup\beta\beta^{*}\alpha=\beta^{*}\alpha.$

Consider the set of finite languages $\mathbf{Fin}\subset\mathbf{Lan}$. Notice
that $\langle\varepsilon\rangle\subsetneq\mathbf{Fin}$. Since $\alpha
L\cap\beta L^{\prime}=\emptyset$, $|L\oplus L^{\prime}|=|L|+|L^{\prime}|$.
Then we have the natural gradation $\ell(L)=|L|$, for which, in addition,
$\ell(LL^{\prime})=\ell(L)\ell(L^{\prime})$. $\mathbf{Fin}$ is clearly
submagma of $\mathbf{Lan}$. Since it is graded, it is free. However, it is not
finitely generated. Singleton languages $L$ cannot be decomposed into other
languages by $\oplus$ (otherwise, if $L=L^{\prime}\oplus L^{\prime\prime}$,
then $1=\ell(L)=\ell(L^{\prime})+\ell(L^{\prime\prime})>1$). This means that
any singleton language must be a generator. Since we have infinite singleton
languages $\mathbf{Fin}$ is not finitely generated.

######  Remark 4.3.

We notice that for any generator set $A$ of a magma $M$, we have that
$M\setminus(M+M)\subseteq A$. Thus, the set $M\setminus(M+M)$ is always
involved to generate $M$.

######  Definition 4.4.

We define the _initial part_ of a magma $M$ as the submagma genererated by the
indecomposable elements, or what is the same:

$\displaystyle\mathfrak{I}(M)=\langle M\setminus(M+M)\rangle.$

We say that $M$ is _initial_ when $\mathfrak{I}(M)=M$.

The condition of being graded can be substituted by the weaker condition of
being initial.

######  Theorem 4.5.

A magma is free iff it is initial and equidec.

###### Proof.

$(\Rightarrow)$ Trivial, since free magmas are initial. $(\Leftarrow)$ Let $M$
be a initial and equidec magma. We take the sequence:

$\displaystyle X_{1}$ $\displaystyle=M\setminus(M+M);$ $\displaystyle X_{k}$
$\displaystyle=\bigcup_{\stackrel{{\scriptstyle i,j\geq
1}}{{i+j=k}}}X_{i}+X_{j}.$

We are going to see that the succession $\\{X_{k}\\}_{k\geq 1}$ forms a
partition of $M$. On the one hand, by Lemma 2.2, we have:

$\displaystyle\bigcup_{k\geq 1}X_{k}=\langle\\!\langle
M\setminus(M+M)\rangle\\!\rangle=\langle M\setminus(M+M)\rangle.$

Since $M$ is initial $\langle M\setminus(M+M)\rangle=\mathfrak{I}(M)=M$. On
the other hand we need to prove that $X_{i}\cap X_{j}=\emptyset$, for any
$i\not=j$. First we consider the cases $X_{1}\cap X_{j}$ and $X_{i}\cap
X_{1}$, provided $i,j\not=1$. We have $X_{1}\cap X_{j}=\emptyset$, since
$X_{1}=M\setminus(M+M)$ is the set of indecomposable elements, while elements
in $X_{j}$ are clearly decomposable by definition. For the same reason
$X_{i}\cap X_{1}=\emptyset$.

Now we prove that if $X_{i}\cap X_{j}\not=\emptyset$ with $i,j>1$, then there
are some $i^{\prime}<i$ and $j^{\prime}<j$ such that $X_{i^{\prime}}\cap
X_{j^{\prime}}\not=\emptyset$. If $X_{i}\cap X_{j}\not=\emptyset$, then there
must be an element such that $x\in X_{i}$ and $x\in X_{j}$. Since $i,j>1$, $x$
can be decomposed into two forms:

$\displaystyle x=x_{i^{\prime}}+x_{i^{\prime\prime}},\mbox{ with
}i=i^{\prime}+i^{\prime\prime},x_{i^{\prime}}\in
X_{i^{\prime}},x_{i^{\prime\prime}}\in X_{i^{\prime\prime}};$ $\displaystyle
x=x_{j^{\prime}}+x_{j^{\prime\prime}},\mbox{ with
}j=j^{\prime}+j^{\prime\prime},x_{j^{\prime}}\in
X_{j^{\prime}},x_{j^{\prime\prime}}\in X_{j^{\prime\prime}}.$

Since $M$ is equidec:

$\displaystyle
x=x_{i^{\prime}}+x_{i^{\prime\prime}}=x_{j^{\prime}}+x_{j^{\prime\prime}}\implies
x_{i^{\prime}}=x_{j^{\prime}}\mbox{ and
}x_{i^{\prime\prime}}=x_{j^{\prime\prime}}.$

And this means that $X_{i^{\prime}}\cap X_{j^{\prime}}\not=\emptyset$ and
$X_{i^{\prime\prime}}\cap X_{j^{\prime\prime}}\not=\emptyset$. Since
$i=i^{\prime}+i^{\prime\prime}$, $j=j^{\prime}+j^{\prime\prime}$, and
$i^{\prime},i^{\prime\prime},j^{\prime},j^{\prime\prime}>1$, we have that
$i^{\prime}<i$ and $j^{\prime}<j$.

By reduction to the absurd, we suppose that $X_{i}\cap X_{j}\not=\emptyset$.
By applying sufficiently times the last result, we will get that there must be
subscripts $i^{\prime},j^{\prime}$ such that either $X_{1}\cap
X_{j^{\prime}}\not=\emptyset$ or $X_{i^{\prime}}\cap X_{1}\not=\emptyset$,
which is a contradiction.

Finally, we define recursively the following succession of mappings:

$\displaystyle f_{1}(z)$
$\displaystyle=z\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mbox{
if }z\in X_{1},$ $\displaystyle f_{k}(z)$
$\displaystyle=f_{i}(x)+f_{j}(y)\,\,\,\,\,\mbox{ if }z\in X_{k},$

where $z=x+y$, $x\in X_{i}$ and $y\in X_{j}$ and $k=i+j$. Since the
decomposition $x+y$ is unique and since $\\{X_{k}\\}_{k\geq 1}$ forms a
partition, $i$ and $j$ are determined uniquely and $f_{k}$ is well-defined. If
we join all these mappings:

$\displaystyle f=\bigsqcup_{k\geq 1}f_{k},$

we get a mapping $f:M\longrightarrow\mathbb{M}_{X}$ and we only need to see
that it is an isomorphism of magmas. $f$ is trivially a homomorphism. In
addition, since $\langle\\!\langle M\setminus(M+M)\rangle\\!\rangle=M$, $f$ is
surjective. Injectivity can be proved by induction on $k$. ∎

######  Definition 4.6.

We say that a magma $M$ is semigraded iff there is a mapping
$\mu:M\longrightarrow\mathbb{N}$ such that:

$\displaystyle\mu(x+y)>\mu(x),\mu(y).$

######  Proposition 4.7.

Given a magma $M$, we have the implications:

$\displaystyle M\mbox{ is graded }\implies M\mbox{ is semigraded}\implies
M\mbox{ is initial}.$

###### Proof.

The first implication is trivial. We see the second one. By definition,
$\mathfrak{I}(M)\subseteq M$. We see that if $M$ is semigraded with the
semigradation $\mu$, then $M\subseteq\mathfrak{I}(M)$. Let $z\in M$, and we
see by induction on the number $\mu(z)$ that $z\in\mathfrak{I}(M)$. If
$\mu(z)=1$, then $z$ is not decomposable, otherwise, $z=x+y$ implies
$1=\mu(z)>\mu(x),\mu(y)$ is not possible, since semigradations are positive.
This means that $z\in M\setminus(M+M)\subseteq\mathfrak{I}(M)$.

Let us suppose that the statement is true for any $x$ such that $\mu(x)<n$,
with $n>1$. Let $z\in M$ such that $\mu(z)=n$. If $z$ is not decomposable,
then we are done, as above. So, let $z=x+y$. Since $\mu(x),\mu(y)<n$, by
hypothesis of induction $x,y\in\mathfrak{I}(M)$, and then
$z=x+y\in\mathfrak{I}(M)$. ∎

######  Theorem 4.8.

Let $M$ be a magma. We have the following equivalences:

  1. (1)

$M$ is equidec and graded;

  2. (2)

$M$ is equidec and semigraded;

  3. (3)

$M$ is equidec and initial;

  4. (4)

$M$ is free.

###### Proof.

Implications $(1)\Rightarrow(2)\Rightarrow(3)$ are consequence of Proposition
4.7. By Theorem 4.5, $(3)\Rightarrow(4)$. The last implication
$(4)\Rightarrow(1)$ is trivial. ∎

######  Example 4.9.

Consider the magma $\mathbb{N}_{\uparrow}=(\mathbb{N};\uparrow)$, where:

$\displaystyle x\uparrow y=2^{x}\cdot 3^{y}.$

By the uniqueness of decomposition in prime numbers, the magma is equidec. It
can be graded, but there is not a closed formula. However, it is semigraded by
the identity mapping $\mu(x)=x$, and, by Theorem 4.8, it is free. This magma
is not finitely generated. For instance, any number in $\mathbb{N}\setminus
6\mathbb{N}$ is, amongst others, an indecomposable element under $\uparrow$
operation.

######  Example 4.10.

The condition of being initial is strictly weaker than the condition of being
graded. Consider, for example, the magma $M=\\{a,b\\}$ with the constant
operation: $x+y=b$, for any $x,y\in M$. $M$ is an initial magma
$\mathfrak{I}(M)=\langle a\rangle=M$, but it cannot be graded nor semigraded.

##  5\. Full magmas and a decomposition theorem

######  Definition 5.1.

We say that a magma is _full_ iff every element has a decomposition in the
magma.

######  Example 5.2.

The trivial magma $\mathcal{I}$ is full. Any semilattice $(L;\wedge)$ is full
by doing $x=x\wedge x$, for any $x\in L$. Any group, actually any monoid,
$(G;\cdot)$ is full by doing $g=1\cdot g$, for any $g\in G$. The magmas
$\mathbb{M}_{A}$, $\mathbf{Tree}$, and $\mathbf{Lan}$ are not full, with the
counterexamples: any generator $a\in A$, the tree with only one vertex
$\circ$, and the language $\varepsilon$, respectively.

######  Example 5.3.

There are some equivalent ways to say that a magma is full. $M$ is full iff
the the operation is surjective. $M$ is full iff $M+M=M$. Even, $M$ is full
iff $\mathfrak{I}(M)=\emptyset$. In particular, semigraded magmas are not
full. Notice that in order to see if a magma $M=\langle A\rangle$ is full we
only have to inspect the generators, since elements in $M\setminus A$ are
trivially decomposable.

Let $M,N$ be magmas. If $M,N$ are full, then $M\times N$ is full, and the free
product $M*N$ is full. If $f:M\longrightarrow N$ is a homomorphism and $M$ is
full, then $f(M)$ is full.

######  Example 5.4.

Let us consider a non-trivial example of full and equidec magma. A magma is
equidec and full iff the operation is injective and surjective, that is,
$+:M\times M\longrightarrow M$ is a bijection. A classic geometric
construction proves that $\mathbb{N}$ and $\mathbb{N}^{2}$ are equinumerous,
see [7]:

There is a closed expression for this bijection which defines an operation:

$\displaystyle x\diamond y=\frac{1}{2}(x^{2}+y^{2}+2xy-x-3y+2).$

Therefore, $\mathbb{N}_{\diamond}=(\mathbb{N};\diamond)$ is an equidec and
full magma. We notice that we have the relations:

$\displaystyle 1\diamond 1=1\,\,\,\,\mbox{ and }\,\,\,\,2=1\diamond 2.$

By using the following property:

$\displaystyle(x+1)\diamond(y-1)=(x\diamond y)+1,$

provided that $y>1$, one can prove by induction that $\langle
1,2\rangle=\mathbb{N}$. In addition, we have that for any $x,y\geq 3$,
$x\diamond y>x,y$, disallows any other non-trivial relation. Actually, the
identity $\mu(x)=x$ is a semigradation for the submagma
$\mathbb{N}\setminus\\{1,2\\}$, which means that it is free by Theorem 4.8.

######  Example 5.5.

A _Jónsson-Tarski algebra_ , or a _Cantor algebra_ , is an algebra $(M;+,p,q)$
of type (2,1,1), that is, a binary operation $+$ and two unary operations
$p,q$, such that:

$\displaystyle p(x+y)=x,\,\,\,\,q(x+y)=y,\,\,\,\,p(z)+q(z)=z,$

for each $x,y,z\in M$. See [11]. It turns that, given an algebra $(M;+,p,q)$
of type (2,1,1), $(M;+,p,q)$ is a Jónsson-Tarski algebra iff $(M;+)$ is a full
and equidec magma. The operations $p$ and $q$ are just the first and the
second component of the decomposition of each element. Given a full and
equidec magma $M$ we write $\widetilde{M}$ for its Jónsson-Tarski algebra.

By taking the three operations $+,p,q$, finitely generated Jónsson-Tarski
algebras are always cyclic. If $A\cup\\{x,y\\}$ generates a Jónsson-Tarski
algebra, where $x,y\not\in A$, then $A\cup\\{x+y\\}$ equally generates the
algebra. Thus, by induction, one can reduce the generators to a single one.
For example, $\widetilde{\mathbb{N}}_{\diamond}$ is generated by $2$ as
Jónsson-Tarski algebra but we need two generators $1,2$ as the magma
$\mathbb{N}_{\diamond}$. See Example 8.7 and last Remark 8.12 for more aspects
on this class of algebras.

######  Example 5.6.

Let $\mathbf{Seq}(X)$ be the set of infinite sequences over a finite non-empty
set $X$. Consider the “shuffle” operation:

$\displaystyle(a_{1},a_{2},a_{3},\ldots)\curlyvee(b_{1},b_{2},b_{3},\ldots)=(a_{1},b_{1},a_{2},b_{2},a_{3},b_{3},\ldots).$

$(\mathbf{Seq};\curlyvee)$ is equidec and given a sequence we always can
decompose it into two sequences:

$\displaystyle(a_{1},a_{2},a_{3},a_{4},a_{5},a_{6}\ldots)=(a_{1},a_{3},a_{5},\ldots)\curlyvee(a_{2},a_{4},a_{6},\ldots).$

Hence, $\mathbf{Seq}(X)$ is a full magma. When $|X|=1$,
$\mathbf{Seq}(X)\cong\mathcal{I}$. Let us see some submagmas in
$\mathbf{Seq}(X)$:

  1. (1)

Of course, if $X\subseteq Y$, we have the submagma
$\mathbf{Seq}(X)\subseteq\mathbf{Seq}(Y)$.

  2. (2)

Let $X=\\{0,\alpha_{1},\ldots,\alpha_{n}\\}$. We have:

$\displaystyle\langle(\alpha_{1},0,0,0,\ldots),\ldots,(\alpha_{n},0,0,0,\ldots)\rangle\cong\mathbb{M}_{X\setminus\\{0\\}}.$

  3. (3)

We say that a sequence $(a_{n})$ is _periodic_ iff there is a positive integer
$T$, called a _period_ , such that:

$\displaystyle n\equiv m\mod T\implies a_{n}=a_{m}.$

$\tau(a_{n})$ denotes the least of the periods of $a_{n}$, provided it is
periodic. If $a_{n}$ and $b_{n}$ are periodic sequences, then $a_{n}\curlyvee
b_{n}$ is periodic and:

$\displaystyle\tau(a_{n}\curlyvee b_{n})\leq
2\cdot\operatorname{lcm}(\tau(a_{n}),\tau(b_{n})).$

Therefore, the set of periodic sequences
$\mathbf{Per}(X)\subset\mathbf{Seq}(X)$ is a submagma.

######  Remark 5.7.

For any arbitrary family of full submagmas $N_{i}\subseteq M$, $i\in I$ for
some set of subscripts $I$, the submagma $H=\bigvee_{i\in I}N_{i}$ is full. As
we commented in Example 5.3, we only need to see whether the generators of a
generating set of $H$ are decomposable, for example, $\bigcup_{i\in I}N_{i}$.
Since the elements in $N_{i}$ are decomposable in $N_{i}$ for each $i\in I$,
$H$ is full. In other words, there exists always the largest full submagma of
a given magma. Notice that, in general, the intersection of full magmas is not
longer full. And in particular, a full magma can contain non-full submagmas.

######  Notation 5.8.

Let $M$ be a magma. We write:

$\displaystyle\mathfrak{F}(M)=\bigvee_{N\subseteq M\mbox{ full}}N,$

the largest full submagma in $M$. Thus, $M$ is full iff $\mathfrak{F}(M)=M$.

######  Lemma 5.9.

The full submagmas of a given equidec magma are closed.

###### Proof.

Let $N$ be a submagma of a magma $M$, and let $z=x+y\in N$. Since $N$ is full,
$z$ can be decomposed $z=x^{\prime}+y^{\prime}$ with $x^{\prime},y^{\prime}\in
N$. Since $M$ is equidec, $N$ is equidec, and then
$x=x^{\prime},y=y^{\prime}$. Thus, $x,y\in N$, and hence, $N$ is closed. ∎

######  Theorem 5.10.

Each equidec magma $M$ can be split as:

$\displaystyle M=\mathfrak{I}(M)\sqcup\mathfrak{F}(M),$

where $\sqcup$ is the disjoint union of sets. In addition, the initial part is
free.

###### Proof.

We consider the decomposition:
$M=\mathfrak{I}(M)\sqcup(M\setminus\mathfrak{I}(M))$. First we show that
$M\setminus\mathfrak{I}(M)$ is a submagma of $M$. Let $x,y\in
M\setminus\mathfrak{I}(M)$, which means that $x$ and $y$ cannot be generated
by indecomposable elements. Let us suppose that $x+y\in\langle
a_{1},\ldots,a_{n}\rangle$ for some $a_{1},\ldots,a_{n}\in M\setminus(M+M)$.
Then, there is a polynomial $P$ over $M$ such that
$x+y=P(a_{1},\ldots,a_{n})$. If $\ell(P)=1$, then $n=1$ and $x+y=a_{1}$, which
means that $x+y$ is indecomposable, which is clearly absurd. If $\ell(P)>1$,
then there are two polynomials $Q,R$ such that $P=Q+R$, and then
$x+y=Q(a_{1},\ldots,a_{n})+R(a_{1},\ldots,a_{n})$. Since $M$ is equidec, we
have that $x=Q(a_{1},\ldots,a_{n})$ and $y=R(a_{1},\ldots,a_{n})$, whereby
$x,y$ should be generated by initial elements, which is a contradiction. This
proves that $M\setminus\mathfrak{I}(M)$ is a submagma.

Now we see that $M\setminus\mathfrak{I}(M)$ is full. Let $z\in
M\setminus\mathfrak{I}(M)$ and we suppose that $z$ is indecomposable. Then
$z\in M\setminus(M+M)\subseteq\mathfrak{I}(M)$, which is clearly a
contradiction.

Finally we see that for any other full submagma $N$ we have $N\subseteq
M\setminus\mathfrak{I}(M)$. Let us suppose that $N\not\subseteq
M\setminus\mathfrak{I}(M)$. This means that
$N\cap\mathfrak{I}(M)\not=\emptyset$. Let $x\in N\cap\mathfrak{I}(M)$. $x$
should be generated by indecomposable elements. That is, there is a polynomial
$P$ and indecomposable elements $a_{1},\ldots,a_{n}$ such that
$x=P(a_{1},\ldots,a_{n})$. By Lemma 5.9, $N$ is closed, which means that
$a_{1},\ldots a_{n}\in N$. However, $N$ is full by hypothesis and their
elements must be decomposable which is a contradiction. This means that
$M\setminus\mathfrak{I}(M)$ is the largest full submagma,
$\mathfrak{F}(M)=M\setminus\mathfrak{I}(M)$.

The initial part of a magma is a initial magma. By Theorem 4.5,
$\mathfrak{I}(M)$ is free. ∎

######  Example 5.11.

Theorem 5.10 provides a first way to differentiate equidec magmas, since
isomorphic magmas must have isomorphic parts. Let us calculate them for the
known magmas, which demonstrates that they are quite different structures:

  1. (1)

Free magmas, $\mathbb{M}_{A}$, does not have full part. That is:

$\displaystyle\mathfrak{I}(\mathbb{M}_{A})=\mathbb{M}_{A},\,\,\,\,\,\,\,\,\,\,\mathfrak{F}(\mathbb{M}_{A})=\emptyset.$

  2. (2)

The initial part of the magma of trees, $\mathbf{Tree}$, coincides with the
submagma of finite trees, while the full part coincides with the submagma of
infinite trees:

$\displaystyle\mathfrak{I}(\mathbf{Tree})=\mathbf{Tree}_{<\infty}\cong\mathbb{M},\,\,\,\,\,\,\,\,\,\mathfrak{F}(\mathbf{Tree})=\mathbf{Tree}_{\infty}.$

  3. (3)

The magmas $\mathbb{N}_{\diamond}$ and $\mathbf{Seq}(X)$ are full, so these
magmas have no initial part:

$\displaystyle\mathfrak{I}(\mathbb{N}_{\diamond})=\emptyset,$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathfrak{F}(\mathbb{N}_{\diamond})=\mathbb{N}_{\diamond},$
$\displaystyle\mathfrak{I}(\mathbf{Seq}(X))=\emptyset,$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathfrak{F}(\mathbf{Seq}(X))=\mathbf{Seq}(X).$

We remark that the initial part of an equidec magma is free, but it is not
necessarily the largest free submagma in $M$. In the Example 5.6, we saw that
$\mathbf{Seq}(X\sqcup\\{0\\})$ contains the free magma $\mathbb{M}_{X}$,
whereas $\mathfrak{I}(\mathbf{Seq}(X))=\emptyset$.

  4. (4)

In the case of the magma of languages $\mathbf{Lan}$, we have that:

$\displaystyle\mathfrak{I}(\mathbf{Lan})=\langle\varepsilon\rangle\vee\langle\alpha\mathbf{Lan}\cup\beta\mathbf{Lan}\rangle.$

Let us see it. Given $x\in\Sigma^{*}$, let $\operatorname{First}(x)$ be the
first letter of $x$, when $x\not=\varepsilon$, and
$\operatorname{First}(\varepsilon)=\varepsilon$. Then:

$\displaystyle\mathbf{Lan}\oplus\mathbf{Lan}=\\{L\in\mathbf{Lan}\mid\operatorname{First}(L)=\Sigma\\}$
$\displaystyle\implies$
$\displaystyle\mathbf{Lan}\setminus(\mathbf{Lan}\oplus\mathbf{Lan})=\\{L\in\mathbf{Lan}\mid\operatorname{First}(L)\not=\Sigma\\}$
$\displaystyle=\\{L\in\mathbf{Lan}\mid\operatorname{First}(L)=\\{\varepsilon\\},\\{\alpha\\},\mbox{
or }\\{\beta\\}\\}$ $\displaystyle\implies$
$\displaystyle\mathfrak{I}(\mathbf{Lan})=\langle\mathbf{Lan}\setminus(\mathbf{Lan}\oplus\mathbf{Lan})\rangle=\langle\\{\varepsilon\\}\cup\alpha\mathbf{Lan}\cup\beta\mathbf{Lan}\rangle$
$\displaystyle=\langle\varepsilon\rangle\vee\langle\alpha\mathbf{Lan}\cup\beta\mathbf{Lan}\rangle.$

The direct product of equidec magmas behaves in a different way to other
algebraic structures, such as monoids or groups. For example, there are not
the inclusion monomorphisms $M,N\longrightarrow M\times N$. Recall that an
equidec magma does not have a neutral element, but for the trivial magma, see
Example 3.2; and, in general, equidec magmas need not have idempotent
elements. A bit more surprisingly, an equidec magma by a free magma is a free
magma:

######  Theorem 5.12.

If $M$ is an equidec magma, then:

$\displaystyle\mathbb{M}_{A}\times M\cong\mathbb{M}_{(A\times
M)\cup(\mathbb{M}_{A}\times\operatorname{Ind}(M))},$

where $\operatorname{Ind}(M)=M\setminus(M+M)$ is the set of indecomposable
elements of $M$.

###### Proof.

We define the gradation $\tilde{\ell}(x,y)=\ell(x)$, where $\ell(x)$ is the
gradation of the free magma $\mathbb{M}_{A}$. Since the product of equidec
magmas is equidec, $\mathbb{M}_{A}\times M$ is a free magma. Now notice that
the indecomposable elements are:

$\displaystyle\operatorname{Ind}(\mathbb{M}_{A}\times M)=(A\times
M)\cup(\mathbb{M}_{A}\times\operatorname{Ind}(M)).$

Since the product is a free magma, it is an initial magma generated by these
elements. Then, the isomorphism is defined over the generators by the
identity. ∎

######  Example 5.13.

Some particular cases of Theorem 5.12 are the following:

  1. (1)

When $M=\mathcal{I}$, $\operatorname{Ind}(M)=\emptyset$, and we have:

$\displaystyle\mathbb{M}_{A}\times\mathcal{I}=\mathbb{M}_{(A\times\mathcal{I})\cup(\mathbb{M}_{A}\times\emptyset)}\cong\mathbb{M}_{A\times\mathcal{I}}\cong\mathbb{M}_{A}.$

  2. (2)

If $M$ is full, then $\operatorname{Ind}(M)=\emptyset$, whereby:

$\displaystyle\mathbb{M}_{A}\times M\cong\mathbb{M}_{A\times M}.$

  3. (3)

When $M=\mathbb{M}_{B}$, $\operatorname{Ind}(\mathbb{M}_{B})=B$, and we have:

$\displaystyle\mathbb{M}_{A}\times\mathbb{M}_{B}\cong\mathbb{M}_{(A\times\mathbb{M}_{B})\cup(\mathbb{M}_{A}\times
B)}.$

Notice that:

$\mathbb{M}\not\cong\mathbb{M}^{2}\cong\mathbb{M}^{3}\cong\mathbb{M}^{4}\cong\cdots\cong\mathbb{M}_{\omega},$

where $\omega$ is any countably infinite set.

##  6\. Closed submagmas of a free magma and quotient characterization

######  Notation 6.1.

Given a set $X$, $\Delta(X)=\\{(x,x)\mid x\in X\\}$ denotes the _diagonal
set_. Let $M$ be a magma. A _congruence on $M$_ is an equivalence relation
such that it is in addition a submagma of $M^{2}$. Given a subset $X\subseteq
M^{2}$, $\Xi(X)$ denotes the least _equivalence relation_ containing $X$.
$\Theta(X)$ denotes the least congruence in $M^{2}$ containing $X$. Thus,
$\Xi(X)\subseteq\Theta(X)$, and $\langle X\rangle\subseteq\Theta(X)$. Given a
congruence $\theta$ on $M$, $[x]=\\{y\mid(x,y)\in\theta\\}$ is the
_equivalence class_ of the element $x\in M$. The _natural projection_ is the
epimorphism $\pi:M\longrightarrow M/\theta$, $\pi(x)=[x]$.

We remark that congruences on $\mathbb{M}_{A}$ are subsets of:

$\displaystyle\mathbb{M}_{A}^{2}\cong\mathbb{M}_{(A\times\mathbb{M}_{A})\cup(\mathbb{M}_{A}\times
A)},$

which is a non-finitely generated free magma, recall Theorem 5.12.
$\mathcal{G}(N)$ denotes the unique minimal generator set of a submagma
$N\subseteq\mathbb{M}_{A}$, Definition 2.7.

######  Lemma 6.2.

Let $N$ be a submagma of a free magma $N\subseteq\mathbb{M}_{A}$. We have that
$N$ is closed iff $\mathcal{G}(N)\subseteq A$. In particular, the unique
closed submagmas of the free magma $\mathbb{M}_{A}$ are $\mathbb{M}_{B}$ with
$B\subseteq A$.

###### Proof.

$(\Rightarrow)$ Let $z\in N$ and suppose that $z$ can be decomposed $z=x+y$.
Since $N$ is closed, $x,y\in N$. Hence $z$ is not a generator. This means that
the generators of $N$ are those that cannot be decomposed, that is, the
elements in $A$.

$(\Leftarrow)$ By Lemma 2.9 if $x+y\in N$ then either $x,y\in N$ or
$x+y\in\mathcal{G}(N)\subseteq A$. But this last one is not possible since
generators in $A$ are indecomposable. therefore, $N$ is closed. ∎

######  Lemma 6.3.

Let $f:M\longrightarrow N$ be a homomorphism of magmas. Then, $f(M)$ is
equidec iff $\ker f$ is a closed submagma of $M^{2}$.

###### Proof.

We have the following equivalences, where the statements must be read with the
prefix “for any $x,y,x^{\prime},y^{\prime}\in M$”:

$\displaystyle f(M)\mbox{ is equidec}$ $\displaystyle\iff$
$\displaystyle\mbox{ if }f(x)+f(x^{\prime})=f(y)+f(y^{\prime}),\mbox{ then
}f(x)=f(y),f(x^{\prime})=f(y^{\prime})$ $\displaystyle\iff$
$\displaystyle\mbox{ if }f(x+x^{\prime})=f(y+y^{\prime}),\mbox{ then
}f(x)=f(y),f(x^{\prime})=f(y^{\prime})$ $\displaystyle\iff$
$\displaystyle\mbox{ if }(x+x^{\prime},y+y^{\prime})\in\ker f,\mbox{ then
}(x,y),(x^{\prime},y^{\prime})\in\ker f$ $\displaystyle\iff$
$\displaystyle\mbox{ if }(x,y)+(x^{\prime},y^{\prime})\in\ker f,\mbox{ then
}(x,y),(x^{\prime},y^{\prime})\in\ker f$ $\displaystyle\iff$
$\displaystyle\ker f\mbox{ is closed}.\qed$

######  Theorem 6.4.

Let $\theta\subseteq\mathbb{M}_{A}^{2}$ be a congruence on $\mathbb{M}_{A}$.
The following statements are equivalent:

  1. (1)

$\mathbb{M}_{A}/\theta$ is equidec;

  2. (2)

$\theta$ is closed;

  3. (3)

$\mathcal{G}(\theta)\subseteq(A\times\mathbb{M}_{A})\cup(\mathbb{M}_{A}\times
A)$.

###### Proof.

We consider the epimorphism
$\pi:\mathbb{M}_{A}\longrightarrow\mathbb{M}_{A}/\theta$. By the _isomorphism
theorem_ for magmas, [3, p. 47], we have $\ker\pi=\theta$. Applying Lemma 6.3,
we get the equivalence $(1)\Leftrightarrow(2)$.

The equivalence $(2)\Leftrightarrow(3)$ follows from Lemma 6.2 and from the
fact that congruences are submagmas of the free magma $\mathbb{M}_{A}^{2}$,
with
$\mathcal{G}(\mathbb{M}_{A}^{2})=(A\times\mathbb{M}_{A})\cup(\mathbb{M}_{A}\times
A)$. ∎

##  7\. Presentations

Given a presentation of a group, the so-called _Tietze transformations_ allow
to add and remove superfluous generators and relations without changing the
group. Tietze transformations are possible also in magma theory. In addition
in the category of equidec magmas there is an extra general transformation: we
can substitute a relation by its generators in
$\mathcal{G}(\mathbb{M}_{A}^{2})$, since congruences on equidec magmas must be
closed.

Since the intersection of closed sumagmas is a closed submagma, it makes sense
to define the least closed congruence.

######  Definition 7.1.

Given a magma $M$, and a subset $X\subseteq M^{2}$, $\boxminus(X)$ denotes the
least closed congruence on $M$ containing $X$.

######  Remark 7.2.

In general we have that $\Theta(X)\subseteq\boxminus(X)$. Notice that each
magma contains at least a closed submagma, the same magma in itself. Hence, if
$M^{2}$ does not have any propper closed submagma, then
$M/\boxminus(X)\cong\mathcal{I}$ for any set $X\subseteq M^{2}$, since
$\boxminus(X)=M^{2}$. In addition, by Theorem 6.4, $M/\boxminus(X)$ is always
an equidec magma.

If $M$ is equidec, the diagonal set $\Delta(M)$ is the least closed
congruence. Thus, closed congruences on an equidec magma $M$ form a complete
algebraic lattice with operations $\theta\cap\theta^{\prime}$ and
$\boxminus(\theta\cup\theta^{\prime})$, for closed congruences
$\theta,\theta^{\prime}$, and bounds $\Delta(M)$ and $M^{2}$ (see [4, p. 21]
or [6, p. 48, 147]).

######  Definition 7.3.

A _presentation_ is a pair $(A,R)$ where $R\subseteq\mathbb{M}_{A}^{2}$.
Elements in $A$ are called _generators_ ; elements in $R$, are called
_relations_. We say that a presentation is _finite_ when the sets $A$ and $R$
are finite. We will write:

$\displaystyle\langle A\mid
R\rangle_{\boxminus}=\faktor{\mathbb{M}_{A}}{\boxminus(R)}$

We say that an equidec magma $M$ is _finitely presented_ iff there is a finite
presentation $(A,R)$ such that $M\cong\langle A\mid R\rangle_{\boxminus}$.

For clarity, we will write the pair $(A,R)$ for a presentation as $(A\mid R)$.
As it is usual, to show specific examples, relations $(x,y)\in R$ will be
written as $x\approx y$. In addition, since we are going to work only with
equidec magmas, we will write $\langle A\mid R\rangle=\langle A\mid
R\rangle_{\boxminus}$.

The free product of two equidec magmas with finite presentations $M=\langle
A\mid R\rangle$, and $N=\langle B\mid S\rangle$ is defined as:

$\displaystyle M*N=\langle A\sqcup B\mid R\sqcup S\rangle.$

It can be proved that this product does not depend on the presentations.

######  Example 7.4.

We see some presentations.

  1. (1)

The trivial magma and the free magma have presentations:

$\displaystyle\mathcal{I}=\langle a\mid a\approx a+a\rangle\,\,\,\mbox{ and
}\,\,\,\mathbb{M}_{A}=\langle A\mid\emptyset\rangle,$

respectively. And as it could be expected:

$\displaystyle\mathbb{M}_{A}*\mathbb{M}_{B}=\mathbb{M}_{A\sqcup B}.$

  2. (2)

The simplest non-trivial equidec magmas are:

$\displaystyle\mathcal{C}_{3_{+}}=\langle a\mid a\approx
a+(a+a)\rangle,\,\,\,\,\mathcal{C}_{3_{-}}=\langle a\mid
a\approx(a+a)+a\rangle.$

$\mathcal{C}_{3_{+}}$ and $\mathcal{C}_{3_{-}}$ are not isomorphic, but anti-
isomorphic. See later Example 8.11 for the notation $\mathcal{C}_{x}$.

  3. (3)

Consider the submagma
$\langle\varepsilon,\beta^{*}\alpha\rangle\subset\mathbf{Lan}$. We have the
unique non-trivial relation:

$\displaystyle\varepsilon\oplus\beta^{*}\alpha=\alpha\varepsilon\cup\beta\beta^{*}\alpha=\beta^{*}\alpha.$

Thus, this magma can be presented as:

$\displaystyle\langle a,b\mid b\approx a+b\rangle.$

  4. (4)

Let us see a free decomposition. Consider the trees $\circ,t\in\mathbf{Tree}$,
where $\circ$ is the one-vertex tree, and $t$ is the infinite full binary
tree. We have:

$\displaystyle\langle\circ,t\rangle\cong\langle a,b\mid b\approx
b+b\rangle\cong\mathbb{M}*\mathcal{I}.$

That is, there is no non-trivial equation relating $\circ$ and $t$.

  5. (5)

We saw in Example 5.4 that $\mathbb{N}_{\diamond}$ has only two non-trivial
relations

$\displaystyle 1=1\diamond 1\,\,\,\mbox{ and }\,\,\,2=1\diamond 2.$

Hence,

$\displaystyle\mathbb{N}_{\diamond}\cong\langle a,b\mid a\approx
a+a,\,\,\,b\approx a+b\rangle.$

######  Notation 7.5.

We introduce the following notations. Let $a\in A,y\in\mathbb{M}_{A}$.
$f_{a\rightarrow y}:\mathbb{M}_{A}\longrightarrow\mathbb{M}_{A}$ denotes the
homomorphism of free magmas defined over the generators as:

$\displaystyle f_{a\rightarrow y}(x)=\begin{cases}x&\mbox{ if }x\not=a,\\\
y&\mbox{ if }x=a.\end{cases}$

We will write $f^{2}_{a\rightarrow y}((x,y))=(f_{a\rightarrow
y}(x),f_{a\rightarrow y}(y))$. We abbreviate
$\mathbf{g}(x)=g_{\mathbb{M}_{A}^{2}}(x)$ which, recall, yields the set of the
necessary generators in order to generate $x$, see Definition 2.7.

######  Definition 7.6.

Given a finite presentation $(A,R)$, we say that it is _firstly reducible_ iff
some of the following transformations is applicable.

  * (I)

If there is some $(x,y)\in R$ such that
$(x,y)\not\in\mathcal{G}(\mathbb{M}_{A}^{2})$, then we set the presentation:

$\displaystyle(A^{\prime}\mid R^{\prime})=\big{(}A\mid\mathbf{g}(R)\big{)}.$

  * (II)

If there are a pair of relations $(a,y),(a,y^{\prime})\in
R\cap(A\times(\mathbb{M}_{A}\setminus A))$, such that $y\not=y^{\prime}$, then
we set:

$\displaystyle(A^{\prime}\mid R^{\prime})=\big{(}A\mid
R\setminus\\{(a,y^{\prime})\\}\cup\mathbf{g}((y,y^{\prime}))\big{)}.$

  * (III)

If there are a pair of relations $(x,b),(x^{\prime},b)\in
R\cap((\mathbb{M}_{A}\setminus A)\times A)$, such that $x\not=x^{\prime}$,
then we set:

$\displaystyle(A^{\prime}\mid R^{\prime})=\big{(}A\mid
R\setminus\\{(x^{\prime},b)\\}\cup\mathbf{g}((x,x^{\prime}))\big{)}.$

We say that the presentation is _secondly reducible_ iff some of the following
transformations is applicable.

  * (IV)

If there is some $(x,y)\in R$ such that $x\not\in A$, then we set:

$\displaystyle(A^{\prime}\mid
R^{\prime})=(A\mid(R\setminus\\{(x,y)\\})\cup\\{(y,x)\\}).$

  * (V)

If there is some $a\in A$ such that $(a,y)\not\in R$ and $(a,a)\not\in R$ for
all $y\in M_{A}$, then we set:

$\displaystyle(A^{\prime}\mid R^{\prime})=(A\mid R\cup\\{(a,a)\\}).$

  * (VI)

If there are a pair of relations $(a,y),(a^{\prime},y)\in
R\cap(A\times\mathbb{M}_{A})$ with $a\not=a^{\prime}$, then we set:

$\displaystyle(A^{\prime}\mid R^{\prime})=(A\setminus\\{a^{\prime}\\}\mid
f_{a^{\prime}\rightarrow a}^{2}\big{(}R\setminus\\{(a^{\prime},y)\\}\big{)}).$

  * (VII)

If there is some $(a,y)\in R\cap(A\times\mathbb{M}_{A})$ such that $a\not\in
g_{\mathbb{M}_{A}}(y)$, and $(a,y^{\prime})\not\in R$ for any other
$y^{\prime}\not=y$, then we set:

$\displaystyle(A^{\prime}\mid R^{\prime})=(A\setminus\\{a\\}\mid
f_{a\rightarrow y}^{2}\big{(}R\big{)}).$

When some transformation (I)-(III) is applied we write $(A\mid
R)\leadsto_{1}(A^{\prime}\mid R^{\prime})$ and when some transformation
(IV)-(VII) is applied, $(A\mid R)\leadsto_{2}(A^{\prime}\mid R^{\prime})$. And
in general, we write $(A\mid R)\leadsto(A^{\prime}\mid R^{\prime})$ when some
transformation (I)-(VII) is applicable. We say that a presentation is
_irreducible_ iff it is not firstly nor secondly reducible.

######  Lemma 7.7.

Let $(A\mid R)$ and $(A^{\prime}\mid R^{\prime})$ be finite presentations.

$\displaystyle(A\mid R)\leadsto(A^{\prime}\mid R^{\prime})\implies\langle
A\mid R\rangle\cong\langle A^{\prime}\mid R^{\prime}\rangle.$

###### Proof.

We check that transformations (I)-(VII) preserve the magma:

  * (I)

Let $(x,y)\in R$. A relation $(x,y)$ can be obtained by sums of its generators
$\mathbf{g}((x,y))$. Hence, we have that:

$\displaystyle(x,y)\in\boxminus(R)\iff\mathbf{g}((x,y))\subseteq\boxminus(R).$

For the direction $(\Rightarrow)$ we use that $\boxminus(R)$ is a closed
congruence. For the direction $(\Leftarrow)$ we use that $\boxminus(R)$ is a
submagma. This means that $\boxminus(R)=\boxminus(\mathbf{g}(R))$, which
implies: $\langle A\mid R\rangle=\langle A\mid\mathbf{g}(R)\rangle=\langle
A^{\prime}\mid R^{\prime}\rangle$.

  * (II)

We notice that if $(a,y),(a,y^{\prime})\in R$ then we can substitute the
relation $(a,y^{\prime})$ by $(y,y^{\prime})$, since the operator $\boxminus$
will generate $(a,y^{\prime})$ by the transitivity property. However, as in
the case (I), we can substitute the relation $(y,y^{\prime})$ by the set of
relations $\mathbf{g}((y,y^{\prime}))$, since $\boxminus(R)$ is a closed
submagma. Hence, $\boxminus(R)=\boxminus(R^{\prime})$.

  * (III)

this case is symmetric to case (II).

  * (IV)

Since the operator $\boxminus(R)$ yields an equivalence relation, we can
change any relation $(x,y)$ by the relation $(y,x)$ preserving the magma.

  * (V)

Since the operator $\boxminus(R)$ yields an equivalence relation, we can add
diagonal elements $(a,a)$ preserving the magma.

  * (VI)

If we have a pair of relations $(a,y)$ and $(a^{\prime},y)$ in
$R\cap(A\times\mathbb{M}_{A})$, then we have a redundant generator, say
$a^{\prime}$. We can remove it, but we have to rewrite all the relations
substituting $a^{\prime}$ by $a$ which is made by $f_{a^{\prime}\rightarrow
a}$.

  * (VII)

If $a\not\in g_{\mathbb{M}_{A}}(y)$, then $a$ does not “participate” in $y$.
The relation $(a,y)$ just renames $y$ as $a$. It might be the case that there
is another relation $(a,y^{\prime})$, however this case is excluded in the
condition of applicability. So we can remove it and rewrite the relations. ∎

######  Remark 7.8.

Transformations (IV)-(VII) are valid for any magma, whereas transformations
(I)-(III) work only for the quasivariety of equidec magmas.

######  Lemma 7.9.

Let $(A\mid R)$ a finite presentation. Then, either the presentation is
firstly irreducible, or there is a finite sequence of presentations such that:

$\displaystyle(A\mid R)\leadsto_{1}(A_{1}\mid R_{1})\leadsto_{1}(A_{2}\mid
R_{2})\leadsto_{1}\cdots\leadsto_{1}(A_{n}\mid R_{n}),$

where $(A_{n}\mid R_{n})$ is firstly irreducible.

###### Proof.

Given a set of relations $R$ we define the number:

$\displaystyle\alpha(R)=\max\\{\max\\{\ell(x),\ell(y)\\}\mid(x,y)\in R\\}.$

We prove that if some transformation (I)-(III) is be applied, then the number
$\alpha(R)$ decreases. First we notice that if
$(x,y)\not\in\mathcal{G}(\mathbb{M}_{A}^{2})$, then:

$\displaystyle\alpha\big{(}\mathbf{g}((x,y))\big{)}<\alpha\big{(}\\{(x,y)\\}\big{)}.$

  * (I)

By the remark above, we have that
$\alpha\big{(}\mathbf{g}(R)\big{)}<\alpha(R)$.

  * (II)

We have the inequalities:

$\displaystyle\alpha(R^{\prime})$
$\displaystyle=\alpha\big{(}(R\setminus\\{(a,y^{\prime})\\})\cup\mathbf{g}((y,y^{\prime}))\big{)}$
$\displaystyle<\alpha\big{(}(R\setminus\\{(a,y^{\prime})\\})\cup\\{(y,y^{\prime})\\}\big{)}$
$\displaystyle=\alpha(R).$

In the second line we have used the condition of applicability according which
$a\in A$ and $y,y^{\prime}\not\in A$. Thus,
$(y,y^{\prime})\not\in\mathcal{G}(\mathbb{M}_{A}^{2})$, whereby, by the above
comment:
$\alpha\big{(}\mathbf{g}((y,y^{\prime}))\big{)}<\alpha\big{(}\\{(y,y^{\prime})\\}\big{)}$.
Then:

$\displaystyle\alpha\big{(}\,(R\setminus\\{(a,y^{\prime})\\})\cup\mathbf{g}((y,y^{\prime}))\,\big{)}<\alpha\big{(}\,(R\setminus\\{(a,y^{\prime})\\})\cup\\{(y,y^{\prime})\\}\,\big{)}.$

In the last line we have used that $\ell(a)=1$, and that
$(a,y),(a,y^{\prime})\in R$. Hence:

$\displaystyle\alpha\big{(}\\{(y,y^{\prime})\\}\big{)}=\alpha\big{(}\\{(a,y),(y,y^{\prime})\\}\big{)}=\alpha\big{(}\\{(a,y),(a,y^{\prime})\\}\big{)},$

and then:

$\displaystyle\alpha\big{(}(R\setminus\\{(a,y^{\prime})\\})\cup\\{(y,y^{\prime})\\}\big{)}=\alpha(R).$

  * (III)

Similar to case (II).

Since the number $\alpha$ decreases, there are only a finite number of
transformations (I)-(III) that can be applied. Therefore, the presentation $P$
can be reduced to a presentation that is firstly irreducible. ∎

######  Lemma 7.10.

Let $(A\mid R)$ a finite presentation firstly irreducible. Then, either the
presentation is secondly irreducible, or there is a finite number of
presentations such that:

$\displaystyle(A\mid R)\leadsto_{2}(A_{1}\mid R_{1})\leadsto_{2}(A_{2}\mid
R_{2})\leadsto_{2}\cdots\leadsto_{2}(A_{n}\mid R_{n}),$

where $(A_{n}\mid R_{n})$ is firstly and secondly irreducible, that is, it is
irreducible.

###### Proof.

Given a presentation $P=(A\mid R)$ we define the numbers:

$\displaystyle\beta(P)$
$\displaystyle=\beta_{1}(P)+\beta_{2}(P)+\beta_{3}(P)+\beta_{4}(P),$
$\displaystyle\beta_{1}(P)$ $\displaystyle=|A|,$ $\displaystyle\beta_{2}(P)$
$\displaystyle=|R|,$ $\displaystyle\beta_{3}(P)$
$\displaystyle=|R\cap(\mathbb{M}_{A}\times A)|,$ $\displaystyle\beta_{4}(P)$
$\displaystyle=|\Delta(A)\setminus(\Delta(A)\cap R)|.$

$\beta_{1}$ counts the number of generators; $\beta_{2}$ counts the number of
relations; $\beta_{3}$ counts the number of relations of the form $(x,a)$ with
$a\in A$; $\beta_{4}$ counts the number of relations that are not in the
diagonal.

We see that if $P\leadsto_{2}P^{\prime}$ for some transformation (IV)-(VII),
then the number $\beta$ decreases. We only specify those numbers that change,
the rest of numbers remain equal.

  * (IV)

$\alpha_{3}(P^{\prime})=\alpha_{3}(P)-1$.

  * (V)

$\alpha_{4}(P^{\prime})=\alpha_{4}(P)-1$.

  * (VI)

$\alpha_{1}(P^{\prime})=\alpha_{1}(P)-1$,
$\alpha_{2}(P^{\prime})=\alpha_{2}(P)-1$.

  * (VII)

$\alpha_{1}(P^{\prime})=\alpha_{1}(P)-1$.

Thus, $\beta(P^{\prime})<\beta(P)$. Since the number $\beta$ always decreases,
there are only a finite number of transformations (IV)-(VII) that can be
applied. Therefore, the presentation $P$ can be reduced to a presentation
secondly irreducible.

Finally we need to see that the presentation is still firstly irreducible. Let
$P=(A\mid R)$ and $P^{\prime}=(A^{\prime}\mid R^{\prime})$ presentations. We
prove that if $P$ is firstly irreducible and $P\leadsto_{2}P^{\prime}$, then
$P^{\prime}$ is still firstly irreducible, or what is the same, no
transformation (I)-(III) is applicable.

On the one hand, since $P$ is firstly irreducible, transformation (I) is not
applicable, which is equivalent to say that
$R\subseteq\mathcal{G}(\mathbb{M}_{A}^{2})$. This is because transformations
(IV)-(VII) reverse coordinates, add diagonal elements, remove relations or
rewrite generators. Therefore,
$R^{\prime}\subseteq\mathcal{G}(\mathbb{M}_{A}^{2})$, whereby (I) is not
applicable on $P^{\prime}$.

On the other hand, transformation (II) is not applicable iff given $a\in A$,
if $(a,y),(a,y^{\prime})\in R$, then $y=y^{\prime}$. Transformation (IV) does
not affect this condition since it requires that $a\not\in A$. Transformation
(V) just introduces a diagonal element, which does not affect the condition.
Transformations (VI) and (VII) rewrite a generator, whereby the condition
holds.

Finally we notice that if a presentation is secondly irreducible, the
transformation (III) cannot be applied because all the relations are in
$A\times\mathbb{M}_{A}$. ∎

##  8\. $\mathbb{E}$-magmas

######  Definition 8.1.

Let $\varphi:A\longrightarrow\mathbb{M}_{A}$ be a mapping. We say that
$\varphi$ is in _E-form_ iff $\varphi$ is injective and $a\in
g_{\mathbb{M}_{A}}(\varphi(a))$ for each $a\in A$, and then we write:

$\displaystyle\mathbb{E}(\varphi)=\faktor{\mathbb{M}_{A}}{\boxminus(\varphi)}.$

We call these magmas $\mathbb{E}$-_magmas_.

######  Theorem 8.2.

$\mathbb{E}$-magmas are equidec. Each finitely presented equidec magma is an
$\mathbb{E}$-magma.

######  Example 8.3.

This theorem synthesizes the last Section 7: an irreducible presentation
defines a mapping in $E$-form. Let us see an example. Consider the following
transformations over the presentation of an equidec magma $M$:

$\displaystyle\big{(}a,b,c,d\mid(c+d)+(a+c)\approx(a+a)+a\big{)}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\footnotesize(I)}}}{{\leadsto}}\,\,\,$
$\displaystyle\big{(}a,b,c,d\mid c\approx a,\,\,d\approx a,\,\,a+c\approx
a\big{)}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\footnotesize(IV)}}}{{\leadsto}}\,\,\,$
$\displaystyle\big{(}a,b,c,d\mid c\approx a,\,\,d\approx a,\,\,a\approx
a+c\big{)}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\footnotesize(V)}}}{{\leadsto}}\,\,\,$
$\displaystyle\big{(}a,b,c,d\mid c\approx a,\,\,d\approx a,\,\,a+c\approx
a,\,\,b\approx b\big{)}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\footnotesize(VII)}}}{{\leadsto}}\,\,\,$
$\displaystyle\big{(}a,b,d\mid d\approx a,\,\,a+a\approx a,\,\,b\approx
b\big{)}$
$\displaystyle\stackrel{{\scriptstyle\mbox{\footnotesize(VII)}}}{{\leadsto}}\,\,\,$
$\displaystyle\big{(}a,b\mid a\approx a+a,\,\,b\approx b\big{)}.$

The relations in the last presentation form a injective mapping
$\varphi:\\{a,b\\}\longrightarrow\mathbb{M}_{\\{a,b\\}}$, $\varphi(a)=a+a$,
$\varphi(b)=b$. Hence:

$\displaystyle M\cong\mathbb{E}(\varphi)=\langle a,b\mid a\approx
a+a,\,\,b\approx b\rangle\cong\mathcal{I}*\mathbb{M}.$

###### Proof of Theorem 8.2..

The first statement is trivial, since the operator $\boxminus$ yields a closed
congruence. For the second statement, consider a finitely presented magma $M$.
That is, $M=\langle A\mid R\rangle$ for some finite presentation $(A\mid R)$.
By Lemma 7.9 and Lemma 7.10 we can assume that the presentation is
irreducible, otherwise we reduce the presentation.

Since the presentation is irreducible, no transformation (I)-(VII) in
Definition 7.6 is applicable. Since (I) is not applicable, all the elements of
$R$ are in $\mathcal{G}(\mathbb{M}_{A}^{2})$. Since (V) is not applicable,
$R\subseteq A\times\mathbb{M}_{A}$. Since (VII) is not applicable, we have
that $R$ defines a mapping, maybe partial, $R:A\longrightarrow\mathbb{M}_{A}$.
Since (VI) is not applicable, the mapping must be total. Since (VII) is not
applicable, we have that $a\in g_{\mathbb{M}_{A}}(R(a))$. In addition, the
unique relations in $A\times A$ are the diagonal elements. Since (II) is not
applicable, for each $a\in A,y,y^{\prime}\in\mathbb{M}_{A}\setminus A$, we
have that $(a,y),(a,y^{\prime})\in R$, implies $y=y^{\prime}$. Since the
unique relations in $A\times A$ are the diagonal elements, the last statement
can be extended to any $y,y^{\prime}\in\mathbb{M}_{A}$. Therefore, the mapping
is injective. In sum, if $(A\mid R)$ is irreducible, then $R$ is a mapping in
E-form. ∎

######  Example 8.4.

Free magmas occur when the mapping $\varphi:A\longrightarrow\mathbb{M}_{A}$ is
the identity $\mathbb{E}(\Delta(A))\cong\mathbb{M}_{A}$. Actually, the initial
part of an $\mathbb{E}$-magma can be calculated as:

$\displaystyle\mathfrak{I}\big{(}\mathbb{E}(\varphi)\big{)}=\mathbb{E}\big{(}\varphi\cap\Delta(A)\big{)}.$

In particular, by Theorem 5.10, $\mathbb{E}(\varphi)$ is full when
$\varphi\cap\Delta(A)=\emptyset$ and it is free when
$\varphi\cap\Delta(A)=\varphi$.

######  Example 8.5.

The free product of two $\mathbb{E}$-magmas is easy to calculate. Let
$\varphi:A\longrightarrow$ and $\psi:B\longrightarrow\mathbb{M}_{B}$ be
mappings in E-form. The set $\varphi\sqcup\psi$ defines a mapping in E-form:

$\displaystyle\big{(}\varphi\sqcup\psi\big{)}(x)=\begin{cases}\varphi(x)\mbox{
if }x\in A,\\\ \psi(x)\mbox{ if }x\in B.\end{cases}$

Then, we have:

$\displaystyle\mathbb{E}(\varphi)*\mathbb{E}(\psi)\cong\mathbb{E}(\varphi\sqcup\psi),$

which states that the free product of $\mathbb{E}$-magmas is an
$\mathbb{E}$-magma.

######  Remark 8.6.

$\mathbb{E}$-magmas form a large class of equidec magmas. Although the direct
product of two equidec magmas is equidec, we cannot ensure here that the
direct product of two $\mathbb{E}$-magmas is an $\mathbb{E}$-magma. That is,
we do not know if there is a mapping in E-form, say $\phi$, for which
$\mathbb{E}(\varphi)\times\mathbb{E}(\psi)\cong\mathbb{E}(\phi)$, beyond some
trivial cases. The difficulty reflects the fact that the direct product is not
in general finitely generated, recall Theorem 5.12.

######  Example 8.7.

Let us consider an example of equidec magma but possibly non
$\mathbb{E}$-magma. Let the alphabet be $\Sigma=\\{p,q\\}$. The following
magma:

$\langle\Sigma^{*}\mid x\approx px+qx,\,\,x\in\Sigma^{*}\rangle$

is a non-finitely represented equidec full magma. The set of relations defines
a injective mapping $\Sigma^{*}\longrightarrow\mathbb{M}_{\Sigma^{*}}$, but it
is not in $E$-form since $x\not\in g_{M_{\Sigma^{*}}}(\varphi(x))$. This
presentation has an interesting property: every generator is superfluous. We
can remove any generator $x$ since it can be generated by $px$ and $qx$.
However, we cannot remove an infinite set of generators.

When we consider its Jónsson-Tarski algebra (recall Example 5.5), the
operations $p,q$ for the first and second component are $p(x)=px$ and
$q(x)=qx$, for each element $x$ of the magma. This structure is isomorphic to
the cyclic free Jónsson-Tarski algebra which is generated by the empty word
$\varepsilon$.

######  Lemma 8.8.

Consider the equidec magma $\mathbb{E}(\varphi)$ where
$\varphi:A\longrightarrow\mathbb{M}_{A}$.The projection
$\pi:A\longrightarrow\pi(A)$ is a bijection.

###### Proof.

First we notice that given a subset $X\subseteq\mathbb{M}_{A}^{2}$, any
element in $\boxminus(X)\setminus\Xi(X)$ is always decomposable. If
$x\in\boxminus(X)$ is indecomposable, then the unique “part” of the operator
$\boxminus$ that could contribute to generate $x$ is
$\Xi(X)\subseteq\boxminus(X)$.

Let us suppose that $\pi(a)=\pi(b)$ for some $a,b\in A$, that is,
$(a,b)\in\Theta(\varphi)$. $(a,b)$ is clearly indecomposable, therefore, by
the above comment, $(a,b)\in\Xi(X)$. We have that for any $x\in A$:

$\displaystyle\Xi\big{(}(x,\varphi(x)\big{)}=\\{(x,x),(\varphi(x),\varphi(x)),(x,\varphi(x)),(\varphi(x),x)\\}.$

In addition, given $x\in A$, we have that $\varphi(x)\in A$ iff
$\varphi(x)=x$, since $x\in g_{\mathbb{M}_{A}}(\varphi(x))$. Then, we can
calculate $\Xi(\varphi)$ as:

$\displaystyle\Xi(\varphi)=\Delta(A)\cup\Delta(\varphi(A))\cup\varphi\cup\overline{\varphi},$

where $\overline{\varphi}=\\{(y,x)\mid(x,y)\in\varphi\\}$. And now it is easy
to check that if $a\not=b$, then $(a,b)$ is not in any of those subsets. Thus,
$\pi:A\longrightarrow\pi(A)$ is injective, and therefore bijective. ∎

######  Definition 8.9.

Let $\varphi,\psi$ be mappings $\varphi:A\longrightarrow\mathbb{M}_{A}$ and
$\varphi:B\longrightarrow\mathbb{M}_{B}$. We say that $\varphi$ and $\psi$ are
_conjugated_ iff there is an isomorphism of free magmas
$g:\mathbb{M}_{A}\longrightarrow\mathbb{M}_{B}$ that makes commutative the
diagram:

######  Theorem 8.10.

$\mathbb{E}(\varphi)\cong\mathbb{E}(\psi)$ iff $\varphi,\psi$ are conjugated.

###### Proof.

$(\Rightarrow)$ Let $f:\mathbb{E}(\varphi)\longrightarrow\mathbb{E}(\psi)$ be
the isomorphism. First we prove that there is an isomorphism of free magmas
$g$ such that the diagram commutes:

By Lemma 8.8, $\pi_{A}:A\longrightarrow\pi(A)$ and
$\pi_{B}:B\longrightarrow\pi(A)$ are bijective. This allows us to define a
mapping $g:A\longrightarrow B$ as:

$\displaystyle g(a)=(\pi^{-1}_{B}\circ f\circ\pi_{A})(a).$

$g$ so defined over the generators defines a homomorphism
$g:\mathbb{M}_{A}\longrightarrow\mathbb{M}_{B}$. $g$ clearly commutes in the
diagram since we have for the generators that:

$\displaystyle g(a)=b\iff f([a]_{A})=[b]_{B}\iff
f(\pi_{A}(a))=\pi_{B}(b)=\pi_{B}(g(a)),$

and, since $f,g,\pi_{A},\pi_{B}$ are homomorphisms, this can be extended to
any element $x\in\mathbb{M}_{A}$. Hence $f\circ\pi_{A}=\pi_{B}\circ$. Since
$g:A\longrightarrow B$ is bijective,
$g:\mathbb{M}_{A}\longrightarrow\mathbb{M}_{B}$ is an isomorphism. Now we need
to see that $\varphi$ and $\psi$ are conjugated. Since we deal with
homomorphisms, we only need to see for the generators. We have:

$\displaystyle f([a]_{A})=[b]_{B}$ $\displaystyle\implies$ $\displaystyle
f([\varphi(a)]_{A})=[\psi(b)]_{B}$ $\displaystyle\implies$ $\displaystyle
g(\varphi(a))=\psi(b)$ $\displaystyle\implies$ $\displaystyle
g(\varphi(a))=\psi(g(a)).$

$(\Leftarrow)$ Let $g$ be the isomorphism of free magmas
$g:\mathbb{M}_{A}\longrightarrow\mathbb{M}_{B}$, such that
$g\circ\varphi=\psi\circ g$. We write $\big{(}g\times
g\big{)}(x,y)=\big{(}g(x),g(y)\big{)}$. It is clear that if $\theta$ is a
congruence on $\mathbb{M}_{A}$, then:

$\displaystyle\faktor{\mathbb{M}_{A}}{\theta}\cong\faktor{g(\mathbb{M}_{A})}{(g\times
g)(\theta)}.$

Now we see that, considering $\varphi=\\{\big{(}a,\varphi(a)\big{)}\mid a\in
A\\}$ as a subset of $\mathbb{M}_{A}^{2}$, we have:

$\displaystyle(g\times g)(\varphi)$
$\displaystyle=\\{\big{(}g(a),(g(\varphi(a))\big{)}\mid a\in A\\}$
$\displaystyle=\\{\big{(}g(a),\psi(g(a))\big{)}\mid a\in A\\}$
$\displaystyle=\\{(b,\psi(b))\mid b\in B\\}$ $\displaystyle=\psi.$

Therefore, $(g\times
g)\big{(}\boxminus(\varphi)\big{)}=\boxminus\big{(}(g\times
g)(\varphi)\big{)}=\boxminus(\psi)$. And then:

$\displaystyle\mathbb{E}(\varphi)$
$\displaystyle=\faktor{\mathbb{M}_{A}}{\boxminus(\varphi)}\cong\faktor{g(\mathbb{M}_{A})}{(g\times
g)\big{(}\boxminus(\varphi)\big{)}}=\faktor{\mathbb{M}_{B}}{\boxminus(\psi)}=\mathbb{E}(\psi).\qed$

######  Example 8.11.

Cyclic equidec magmas have at most one non-trivial relation, which allows to
write them $\mathcal{C}_{x}=\mathbb{E}(1\approx x)$, where $x\in\mathbb{M}$.
The first cyclic equidec magmas are:

$\displaystyle\mathcal{C}_{1}\cong\mathbb{M},\,\,\,\mathcal{C}_{2}\cong\mathcal{I},\,\,\,\mathcal{C}_{3_{-}}\cong\langle
1\mid 1\approx 3_{-}\rangle,\,\,\,\mathcal{C}_{3_{+}}\cong\langle 1\mid
1\approx 3_{+}\rangle,\ldots$

where we recall Notation 2.5 for the elements in $\mathbb{M}$. We have that:

$\displaystyle\mathcal{C}_{x}\cong\mathcal{C}_{y}\iff x=y.$

Thus, for each $x\in\mathbb{M}$ we have a unique cyclic equidec magma.

######  Remark 8.12.

Let $\mathbf{K}$ be a class of algebras. It is said that an algebra $A$ is
$\mathbf{K}$-_freely generated by the set_ $X$ iff $X$ generates $A$ and if
for every algebra $B\in\mathbf{K}$, every mapping $f:X\longrightarrow B$ can
be extended to a homomorphism of algebras of $A$ into $B$. Let
$\mathbf{K}_{2}$ be the class of Jónsson-Tarski algebras. In [11] (Theorem 5)
it is proved that if two Jónsson-Tarski algebras are finitely
$\mathbf{K}_{2}$-freely generated then they must be isomorphic.

Notice that, in particular, the isomorphism of these algebras is preserved
into magmas, that is, if $\widetilde{M}\cong\widetilde{N}$, then $M\cong N$.
Notwithstanding, the examples of Jónsson-Tarski algebras from a full and
equidec magma in this article are not $\mathbf{K}_{2}$-freely generated, with
the only exception of the Example 8.7.

Let us see, as illustration, that the Jónsson-Tarski algebra
$\widetilde{\mathbb{N}}_{\diamond}$ of Example 5.5 is not
$\mathbf{K}_{2}$-freely generated. Every cyclic equidec magma is full with the
only exception of $\mathcal{C}_{1}\cong\mathbb{M}$, recall Example 8.4.
Consider the particular case of the magma $\mathcal{C}_{3_{+}}$. In this magma
the equation $[1]=x+[1]$ has no solution, otherwise we would have two
different relations in the magma $[1]=[1]+([1]+[1])$ and $[1]=x+[1]$, which
makes no sense. We saw that $\widetilde{\mathbb{N}}_{\diamond}$ is generated
by the integer $2$ which satisfied the relation $2=1\diamond 2$. Now we
consider a mapping $f:\\{2\\}\longrightarrow\widetilde{\mathcal{C}}_{3_{+}}$
defined as $f(2)=[1]$. We see that $f$ cannot be extended to a homomorphism
$f:\widetilde{\mathbb{N}}_{\diamond}\longrightarrow\widetilde{\mathcal{C}}_{3_{+}}$,
otherwise we would have $[1]=f(2)=f(1\diamond 2)=f(1)+f(2)=f(1)+[1]$, for some
value $f([1])\in\mathcal{C}_{3_{+}}$, and this is absurd.

In the proof of Theorem 5 in [11], Jónsson and Tarski used a general form of
the algebra $\widetilde{\mathbb{N}}_{\diamond}$ to prove that the class
$\mathbf{K}_{2}$ contains non-trivial algebras, although the
$\mathbf{K}_{2}$-freeness of that algebra is not required for the proof. By
similar means one can prove that cyclic magmas and other full and equidec
magmas seen in this article are not $\mathbf{K}_{2}$-freely generated.

## Acknowledgment

Many thanks to the anonymous reviewer for so exhaustive and accurate revision,
specially for shortening the proof in the Example 3.7 and the reference of the
article of Jónsson and Tarski.

## References

  * [1] Blondel, V.: Une famille d’opérations sur les arbres binaires. C. R. Acad. Sci. Paris 321, 491–494 (1995)
  * [2] Blondel, V.: Structured numbers, properties of a hierarchy of operations on binary trees. Acta Inform. 35, 1–15 (1998)
  * [3] Bourbaki, N.: Algebra I, Chapters 1-3. Springer-Verlag, Berlin (1989)
  * [4] Burris, S., Sankappanavar, H.P.: A course in Universal Algebra. The Millenium Edition (2012). http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html
  * [5] Cardó, C.: Arithmetic and k-maximality of the cyclic free magma. Algebra Univ. 80, 35 (2019)
  * [6] Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge University Press, New York (2002)
  * [7] Enderton, H.B.: Elements of set theory. Academic press, London (1977)
  * [8] Grätzer, G.: Universal Algebra. The university series in higher mathematics. D. Van Nostrand Co., Princeton (1968)
  * [9] Hopcroft, J.E., Raajeev, M., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Pearson education. Addison Wesley, Reading (2001)
  * [10] Ježek, J. and Kepka, T.: Medial groupoids. Rozpravy ČSAV, Řada Mat. a Přír, Věd, 93-2, Academia Praha (2019)
  * [11] Jónsson, B. and Tarski, A.: On two properties of free algebras. Math. Scand. 9, 95–101 (1961)
  * [12] Reutenauer, C.: Free Lie Algebras. Clarendon Press, Oxford (1993)
  * [13] Rosenfeld, A.: An Introduction to Algebraic Structures. Holden-Day, San Francisco (1968)