3

Show that every variety of mono-unary algebras is defined by a single identity.

Intuitively this makes sense but I am having trouble showing it. An example of a mono-unary algebra is $\langle \mathbb{N}, f \rangle$ where $f(n) = n + 1, \forall n \in \mathbb{N}.$ I'm not sure what identity would be used here, maybe $f^{n}(x) = f^{m}(y), n \le m; m,n \in \mathbb{N}$. Seems like some sort of 'least' identity is the one we are after since from the above we can generate many many more identities of the same 'flavour'.

I'm not sure how to generalize this more; it makes sense when I consider this specific mono-unary algebra.

oliverjones
  • 4,199
  • To see what the posible identities are, you have to see first what the terms that you can construct with one unary predicate: can you see this? – Mariano Suárez-Álvarez Nov 08 '16 at 01:16
  • @MarianoSuárez-Álvarez Let $(A, f)$ be the algebra. if given the set of variables $X$ from which we generate terms we know $x_i = x_j$ iff $i = j$ when $x$ is a variable. And only having one unary operation for $p,q \in T(X)$ we can have $p(x_1, ... x_n) = q(x_1, ... ,x_n)$ translates to $p^{A}(x_i) = q^{A}(x_j)$ but we only have one operation so $p^{A} = q^{A} = f$. Is this what you mean? – oliverjones Nov 08 '16 at 01:33
  • I don't know what relation there is between my question and your answer ;-) What posible expressions can you write using variables and the one unary operator? – Mariano Suárez-Álvarez Nov 08 '16 at 01:53
  • @MarianoSuárez-Álvarez well you can have the variables $x_1, x_2, ...$ and we can have $f(x_1), f(x_1), ...$ where $f$ is the single operator. so we can have $x_i = x_j$ or $f(x_i) = f(x_j)$. Is this what you are after? I see no other expressions I can write. – oliverjones Nov 08 '16 at 02:08
  • A term is the sort of thing that appears on the sides of an equal sign. Indeed, the only terms in a unary algebra are of the form $f^k(X)$ with X some variable and K a non negative integer. It follows that the only identities for such an algebra are precisely of the form you described in your question. – Mariano Suárez-Álvarez Nov 08 '16 at 02:46
  • Can you see how to find a minimal such identity valid in a variety? – Mariano Suárez-Álvarez Nov 08 '16 at 02:46
  • @MarianoSuárez-Álvarez It seems that $f^m(x) = f^m(y)$ is the minimal identity but I am not sure why that would me. – oliverjones Nov 08 '16 at 02:56
  • But surely the minimal identity depends on the variety! – Mariano Suárez-Álvarez Nov 08 '16 at 03:01
  • @MarianoSuárez-Álvarez true, but I'm still not seeing what that gives me in terms of finding a minimal identity. – oliverjones Nov 08 '16 at 03:05
  • To solve your problem, you have to pick a variety, consider the set of all the identities it satisfies and look for a "minimal" one that implies all the others. For that, you have to think a bit about what you can say about the set of all the identities satisfied by your variety. (You must surely have done something similar, unless this exercise came out of the blue...) – Mariano Suárez-Álvarez Nov 08 '16 at 03:14
  • @MarianoSuárez-Álvarez , This is a new problem. Just started looking at identities. It makes sense but I guess I am not seeing what might happen differently from one variety to another when dealing with mono-unary algebras. – oliverjones Nov 08 '16 at 04:51
  • Well, the identity $f^2(x)=f^3(x)$ defines a variety, and the identity $f^9(x)=f^{23}(x)$ defines a variety: are these two varieties the same one? – Mariano Suárez-Álvarez Nov 08 '16 at 06:16

1 Answers1

3

I think a good approach to this (might be a bit of an overkilling but I don't find it easy to give a different explicit proof of this) is by using subdirectly irreducible algebras.

You might know which are the subdirectly irreducible mono-unary algebras (otherwise that can be another interesting exercise).
These are $$\mathbf{C}_{n^p}, \quad \mathbf{C}_{n^p}\dot\cup\mathbf{C}_{1}, \quad \mathbf{L}_n, \quad \mathbf{L}_{\infty},$$ where $p$ is a prime number, $\mathbf{C}_n$ is a cycle with $n$ elements, $\mathbf{L}_n$ is a chain with $n$ elements and $\mathbf{L}_{\infty}$ is an infinite chain with a last element (with respect to the operation) that is the image of itsef.
Like this:

enter image description here

Now we have: $$\mathbf{C}_{p^n}, \mathbf{C}_{p^n} \dot\cup \mathbf{C}_{1} \vDash f^{p^n}(x) \approx x,\; \mathbf{L}_n \vDash f^n(x) \approx f^n(y),\; \mathbf{L}_{\infty} \vDash x \approx x,$$ and $\mathbf{L}_{\infty}$ doesn't satisfy any nontrivial identity.

Let, for $n \geq 0$ and $m > 0$, $$U_n = Mod(f^n(x) \approx f^n(y)),\; U_{m,n} = Mod(f^n(x) \approx f^{n+m}(x)), \; U = Mod(x \approx x).$$ Then $V(\mathbf{C}_{p^n}) = V(\mathbf{C}_{p^n} \dot\cup \mathbf{C}_{1}) = U_{p^n,0}$, $V(\mathbf{L}_n) = U_n$ and $V(\mathbf{L}_{\infty}) = U$.

Then we have $$U_i \vee U_j = U_{\max\{i,j\}}, \; U_i \wedge U_j = U_{\min\{i,j\}},$$ $$U_i \vee U_{j,k} = U_{\max\{i,k\},j}, \; U_i \wedge U_{j,k} = U_{\min\{i,k\}},$$ $$U_{ij} \vee U_{kl} = U_{\max\{j,l\},\mathrm{lcm}\{i,k\}}, \; U_{ij} \wedge U_{kl} = U_{\min\{j,l\},\gcd\{i,k\}},$$ and so all varieties of mono-unary algebras belong to this family.

I might later look for a reference from where I got a hint to this, but I can't find it now and don't have much time, sorry...

Edit. Now I know why I couldn't find that reference: I never had it. I only had a review of a paper to which I couldn't get access, but perhaps you can. Anyway, I suppose it's not strictly necessary. It's the review of the paper The lattice of equational classes of algebras with one unary operation of Eugene Jacobs and Robert Schwabauer, published in The American mathematical monthly, vol. 71 (1964), pp. 151—155.

amrsa
  • 12,917