# Finite magmas representing all unary functions by terms

Say that a magma $$\mathcal{M}=(M;*)$$ is unary-rich iff for every function $$f:M\rightarrow M$$ there is a (one-variable, parameter-free) term $$t_f$$ such that $$t_f^\mathcal{M}=f$$. For example:

• The one-element magma (and the empty magma if we permit such) is trivially unary-rich.

• A bit less trivially, there is a two-element unary-rich magma (in fact exactly 0ne up to isomorphism): namely $$M=\{a,b\}$$ and $$*$$ given by $$a*a=b, a*b=a, b*a=a, b*b=b$$ via the terms, $$x, xx, (xx)x,$$ and $$(xx)(xx)$$.

My question is:

Are there unary-rich magmas of every (or at least arbitrarily large) finite cardinality?

Of course every unary-rich magma is finite since there are only countably many terms. Note that if $$\vert M\vert=n<\omega$$ then $$M$$ is unary-rich iff $$M$$ has $$n^n$$-many distinct one-variable terms up to equality-as-functions.

Already the case of $$3$$-element magmas seems interesting and difficult to brute-force.

• If I'm not missing anything here, this is the case whenever the magma is primal. And we know that there is an asymptotic proportion of $1/e$ primal magmas among all magmas; hence at least that proportion of unary-rich magmas, and therefore arbitrarily large. For every finite cardinality is another thing... Jun 2, 2021 at 14:35
• @amrsa Ooh, neat - I didn't know about primal algebras! A bit of googling turns up results about primal algebras more complicated than magmas, do you have a citation for the result you mention? Jun 2, 2021 at 14:38
• I've just linked it. Of course it doesn't answer the question completely. Jun 2, 2021 at 14:39
• One of the binary operations on a two element set that makes the associated magma primal is called the Sheffer stroke (it is more commonly known as the NAND operation). I've searched for "n-valued analogues of the Sheffer stroke", but the results are difficult to decipher due to old-fashioned language.
– Eran
Jun 2, 2021 at 15:31
• If you take the operation $\ast$ found in Keith Kearnes answer to this question and apply the criteria found in his answer to this question, you get a binary operation that gives rise to a primal magma of any cardinality.
– Eran
Jun 5, 2021 at 18:52

From this answer by Eran, we know that the asymptotic proportion of primal magmas among all magmas is $$1/e$$.

In a primal algebra all operations defined on its carrier set are terms of the algebra, so certainly every primal magma is unary-rich, and it follows that the asymptotic proportion of unary-rich magmas is equal or greater than $$1/e$$.

In particular, there have to be arbitrarily large ones.
It may however be the case that is not one of every cardinality.

Added. From the book "Universal Algebra and Applications in Theoretical Computer Science", by Klaus Denecke and Shelly Wismath, I've got the following results.

Proposition 10.5.7
(i) Let $$\mathbf A$$ be a primal algebra. Then

1. $$\mathbf A$$ has no proper subalgebras,
2. $$\mathbf A$$ has no non-identical automorphisms,
3. $$\mathbf A$$ is simple, and
4. $$\mathbf A$$ generates an arithmetical variety.

(ii) Every functional complete algebra is simple

and then

Theorem 10.5.8 For a finite algebra $$\mathbf A$$ the following propositions are equivalent:

1. $$\mathbf A$$ is primal.
2. $$\mathbf A$$ generates an arithmetical variety, has no non-identical automorphisms, has no proper subalgebras and is simple.
3. There is a ternary discriminator term which induces a term operation on $$\mathbf A$$, and the algebra $$\mathbf A$$ has no proper subalgebras and no non-identical automorphisms.

Here a ternary discriminator term is an operation $$t:A^3\to A$$ defined by $$t(x,y,z) = \begin{cases} z &\text{ if } x=y,\\ x &\text{otherwise,} \end{cases}$$

and a variety is arithmetical iff it is both congruence-distributive and congruence-permutable.

• Do you happen to know if there is a primal $3$-element magma? Jun 2, 2021 at 14:48
• @NoahSchweber Not from the top of my head. I don't know many examples, although we know there are so many Jun 2, 2021 at 14:49
• Sure, I'm just thinking about getting magmas. Actually, here's a variant question. Let $s(x,y)$ be a term in the language of rings (including $0$ and $1$ as nullary functions) and given a ring $R$ let $R_s$ be the magma whose domain is the same as $R$ and whose operation is $s^R$. Which rings $R$ admit a term $s$ such that $R_s$ is primal (or at least unary-rich)? For example, for $R=\mathbb{Z}/2\mathbb{Z}$ the term $s(x,y)=(x+1)(y+1)$ makes $R_s$ the two-variable magma in my question. I wonder if there are rings with no "primal term reducts" ... Jun 2, 2021 at 15:01
• I think that could well be the topic for another question. Jun 2, 2021 at 15:02
• I've taken the liberty of adding the definition of "arithmetical variety." Jun 2, 2021 at 15:29

The following is an example of a unary rich magma on $$3$$ elements I think, the multiplication table is the following:

$$\begin{pmatrix} 1 0 0\\ 0 2 0 \\ 1 0 0 \end{pmatrix}$$

The terms found for each function are as follows:

$$0\rightarrow 0 \quad 1\rightarrow 0 \quad 2\rightarrow 0$$

$$((xx)x)$$

$$0\rightarrow 0 \quad 1\rightarrow 0 \quad 2\rightarrow 1$$

$$(x(xx))$$

$$0\rightarrow 0 \quad 1\rightarrow 0 \quad 2\rightarrow 2$$

$$((x(xx))(((xx)x)((xx)x)))$$

$$0\rightarrow 0 \quad 1\rightarrow 1 \quad 2\rightarrow 0$$

$$((xx)(x(xx)))$$

$$0\rightarrow 0 \quad 1\rightarrow 1 \quad 2\rightarrow 1$$

$$((xx)((xx)x))$$

$$0\rightarrow 0 \quad 1\rightarrow 1 \quad 2\rightarrow 2$$

$$x$$

$$0\rightarrow 0 \quad 1\rightarrow 2 \quad 2\rightarrow 0$$

$$(x((x(xx))(x(xx))))$$

$$0\rightarrow 0 \quad 1\rightarrow 2 \quad 2\rightarrow 1$$

$$(x((x(xx))((xx)x)))$$

$$0\rightarrow 0 \quad 1\rightarrow 2 \quad 2\rightarrow 2$$

$$(((xx)((xx)x))(((xx)x)((xx)x)))$$

$$0\rightarrow 1 \quad 1\rightarrow 0 \quad 2\rightarrow 0$$

$$(x(x(xx)))$$

$$0\rightarrow 1 \quad 1\rightarrow 0 \quad 2\rightarrow 1$$

$$(x((xx)x))$$

$$0\rightarrow 1 \quad 1\rightarrow 0 \quad 2\rightarrow 2$$

$$((x(xx))((xx)((xx)x)))$$

$$0\rightarrow 1 \quad 1\rightarrow 1 \quad 2\rightarrow 0$$

$$((x(xx))((xx)x))$$

$$0\rightarrow 1 \quad 1\rightarrow 1 \quad 2\rightarrow 1$$

$$(((xx)x)((xx)x))$$

$$0\rightarrow 1 \quad 1\rightarrow 1 \quad 2\rightarrow 2$$

$$((x(xx))(x(xx)))$$

$$0\rightarrow 1 \quad 1\rightarrow 2 \quad 2\rightarrow 0$$

$$(xx)$$

$$0\rightarrow 1 \quad 1\rightarrow 2 \quad 2\rightarrow 1$$

$$(x((xx)(x(xx))))$$

$$0\rightarrow 1 \quad 1\rightarrow 2 \quad 2\rightarrow 2$$

$$(((xx)((xx)x))((xx)((xx)x)))$$

$$0\rightarrow 2 \quad 1\rightarrow 0 \quad 2\rightarrow 0$$

$$((xx)((x(xx))(x(xx))))$$

$$0\rightarrow 2 \quad 1\rightarrow 0 \quad 2\rightarrow 1$$

$$((xx)(xx))$$

$$0\rightarrow 2 \quad 1\rightarrow 0 \quad 2\rightarrow 2$$

$$((x((xx)x))(((xx)x)((xx)x)))$$

$$0\rightarrow 2 \quad 1\rightarrow 1 \quad 2\rightarrow 0$$

$$((xx)(x((xx)x)))$$

$$0\rightarrow 2 \quad 1\rightarrow 1 \quad 2\rightarrow 1$$

$$((xx)(x(x(xx))))$$

$$0\rightarrow 2 \quad 1\rightarrow 1 \quad 2\rightarrow 2$$

$$((x((xx)x))(x((xx)x)))$$

$$0\rightarrow 2 \quad 1\rightarrow 2 \quad 2\rightarrow 0$$

$$(((x(xx))(x(xx)))((x(xx))(x(xx))))$$

$$0\rightarrow 2 \quad 1\rightarrow 2 \quad 2\rightarrow 1$$

$$(((x(xx))(x(xx)))((x(xx))((xx)x)))$$

$$0\rightarrow 2 \quad 1\rightarrow 2 \quad 2\rightarrow 2$$

$$((((xx)x)((xx)x))(((xx)x)((xx)x)))$$

I found $$1596$$ different ones by only checking a small set of terms and going over all the $$3^9$$ magmas on $$0,1,2$$.

• Under the supposition that it is indeed unary-rich, this algebra has the following additional interesting feature: since it's not simple, because the congruence $\Theta(0,2)$ is just $\{0,2\}^2\cup\{1\}^2$, it follows that it's not primal, and so we know that there are unary-rich magmas which are not primal (as I suppose it should be expected). Jun 2, 2021 at 15:41
• @amrsa: The algebra in this example is simple. Jun 3, 2021 at 3:38

G. Rousseau, Completeness in finite algebras with a single operation, Proc. Amer. Math. Soc. 18 (1967) 1009-1013

This paper proves that a finite algebra with one $$n$$-ary operation, $$n>1$$, is primal iff it has no proper subalgebra, no non-identity automorphism, and no proper nontrivial congruence. Therefore the following are equivalent for a finite algebra with one binary operation:

• $$\bf A$$ is unary-rich.
• $$\bf A$$ is primal.
• $$\bf A$$ has no proper subalgebra, no non-identity automorphism, and no proper nontrivial congruence.
• So actually I already had the ingredients to give a full answer when I wrote mine one! Of course if an algebra is unary-rich then from $a\theta b$ we get $c\theta d$ for every $(c,d)$ using a unary function with $f(a)=c$ and $f(b)=d$, and similar reasoning for subalgebras. Jun 3, 2021 at 10:01
• In conjunction with Eran's comment above this fully answers my question, thanks! (@amrsa thanks for your answer too, unfortunately I can only accept one.) Jun 5, 2021 at 18:56
• @NoahSchweber You're welcome. And we agreed from the beginning that what I had to say on the subject wouldn't be a full answer. Jun 5, 2021 at 20:37