Congruence lattices of connected monounary algebras

Abstract

The system of all congruences of an algebra (A, F) forms a lattice, denoted ${{\,\mathrm{Con}\,}}(A, F)$. Further, the system of all congruence lattices of all algebras with the base set A forms a lattice $\mathcal {E}_A$. We deal with meet-irreducibility in $\mathcal {E}_A$ for a given finite set A. All meet-irreducible elements of $\mathcal {E}_A$ are congruence lattices of monounary algebras. Some types of meet-irreducible congruence lattices were already described. In the case when a monounary algebra (A, f) is connected, we prove necessary and sufficient condition under which ${{\,\mathrm{Con}\,}}(A, f)$ is $\wedge$-irreducible.

1 Introduction

Congruences and congruence lattices on algebras have been studied by many authors, recently e.g. by [1, 2, 4]. Further, [5] and [10] studied congruences on other types of structures.

Our paper is a continuation of [6] and [7]. As it was mentioned in [7], the subject of the papers is related to the finite representation problem in its concrete version.

For a fixed finite set A we consider all possible congruence lattices of algebras with the base set A. These congruence lattices, ordered by inclusion, form a lattice themselves; it is denoted $\mathcal {E}_A$. All join-irreducible congruence lattices of $\mathcal {E}_A$ were characterized in [7]. In this paper, we study meet-irreducibility in the lattice $\mathcal {E}_A$.

Since $F \subseteq G$ implies ${{\,\mathrm{Con}\,}}(A, G) \subseteq {{\,\mathrm{Con}\,}}(A, F)$, all $\wedge$-irreducible elements in $\mathcal {E}_A$ must be of the form ${{\,\mathrm{Con}\,}}(A, f)$ for a single mapping f, otherwise ${{\,\mathrm{Con}\,}}(A, F)$ would be the intersection of all ${{\,\mathrm{Con}\,}}(A, f)$ where $f \in F$. Therefore, it is sufficient to explore meet-irreducibility of congruence lattices of monounary algebras (i.e. algebras with a single unary operation). While studying properties of monounary algebras, we often benefit from the fact that they can be easily visualized as digraphs which are always planar, hence easy to draw [8].

In general, the problem which unary operations f yield $\wedge$-irreducibles is difficult. Some partial results exist for special classes of operations f ([6, 7]). Let us remark that maximal $\wedge$-irreducibles, i.e. the coatoms in $\mathcal {E}_A$, are described completely in [7].

In this paper, we prove a necessary and sufficient condition under which ${{\,\mathrm{Con}\,}}(A, f)$ is $\wedge$-irreducible in $\mathcal {E}_A$ in the case when (A, f) is connected (definitions are in the section Preliminary):

Theorem 1.1

Let (A, f) be a connected monounary algebra with at least 3 cyclic elements. Then ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-irreducible if and only if the set of cyclic elements is covered and there exist distinct noncyclic elements $a,b,c,d\in A$ such that f(a), f(c) are cyclic and $f(b)=a, f(d)=c$.

Remark 1.2

Let us note that in the case when (A, f) is a monounary algebra with at most two cyclic elements, the necessary and sufficient condition under which ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-irreducible was proved in [6].

2 Preliminary

In the following, let A be a fixed, non-empty, finite set and f be a mapping on A. The pair (A, f) is said to be a monounary algebra. For the notions concerning monounary algebras, see [8].

Let us denote ${\mathbb {N}}:= \{1, 2, 3, \ldots \}$ and ${\mathbb {N}}_0:= {\mathbb {N}} \cup \{0\}$.

For a mapping $f:A\rightarrow A$, f(a) denotes the image of the element $a \in A$ in the mapping f, and if $n \in {\mathbb {N}}$ then $f^n$ denotes the n-fold composition of f. By convention, $f^0$ denotes the identity mapping $\text {id}_A.$

The operation $f:A\rightarrow A$ is called trivial if it is either identity $x \mapsto x$ or the constant mapping $x \mapsto a$. Otherwise it is called nontrivial.

An element $x\in A$ is called cyclic if there exists $n\in {\mathbb {N}}$ such that $f^n(x)=x$, otherwise it is called noncyclic. In this case, the set $\{x,f^{1}(x),f^{2}(x),\ldots$, $f^{n-1}(x)\}$ is called a cycle of (A, f). Since A is finite, for each $a \in A$ there exists $k \in {\mathbb {N}}_0$ such that $f^k(a)$ is cyclic. The cycle containing $f^k(a)$ will be denoted C(a).

Definition 2.1

A monounary algebra (A, f) is called connected, if for every $x,y \in A$ there exist $m, n \in {\mathbb {N}}_0$ such that $f^m(x)=f^n(y)$.

Apparently, a connected monounary algebra (A, f) contains exactly one cycle. In [6], Definitions 2.2, 2.3 were introduced.

Definition 2.2

A monounary algebra (A, f) is called a permutation-algebra if the operation f is a permutation on A.

Definition 2.3

Let $({{\bar{A}}}, {{\bar{f}}})$ be a monounary algebra. Then $({{\bar{A}}}, {{\bar{f}}})$ is said to be a permutation-algebra with short tails if there is a subalgebra (B, f) of $({{\bar{A}}}, {{\bar{f}}})$ such that (B, f) is a permutation-algebra and ${{\bar{f}}}(x)\in B$ for each $x\in {{\bar{A}}}$. In this case (B, f) is called a permutation-algebra corresponding to $({{\bar{A}}}, {{\bar{f}}})$.

Notation 2.4

Let $t_f(a) := \min \{n\in {\mathbb {N}}_0: f^n(a) \in C(a)\}$. Clearly, if a is cyclic then $t_f(a) =0$. For $k\in {\mathbb {N}}$ we denote $C_k:=\{x\in A: t_f(x)=k\}.$

Definition 2.5

For every element $x \in A$ such that $t_f(x) = t$, there is a single cyclic element $y\in A$ such that $f^t(x) = f^t(y)$. We will call this element a colleague of x and we denote it $x'$. It is clear that $(f(x))'=f(x').$

Notation 2.6

For $a\in A$, we denote $\langle a)_f:=\{f^k(a): k\in {\mathbb {N}}_0\}$ and $(a)_f:=\{f^k(a): k\in {\mathbb {N}}\}$.

Let us denote the least and the greatest congruence on the set A as $\Delta := \{(x, x): x \in A\}$ and $\nabla := A \times A,$ respectively.

For $x, y \in A$ let $\theta _f(x, y)$ be the smallest congruence on (A, f) such that $(x, y) \in \theta _f(x, y)$. In [3], the following notations were introduced. For $a \in A$ cyclic, $d\in {\mathbb {N}}$, we denote $\theta ^{(d)}$ the smallest congruence on (A, f) such that $(a, f^d(a))\in \theta ^{(d)}$.

Notice that if $m, n \in {\mathbb {N}}$ such that m divides n then $\theta ^{(n)} \subseteq \theta ^{(m)}$.

Let x belong to a cycle with n elements and let $y=f^i(x), i \in {\mathbb {N}}.$ Then $\theta _f(x,y)= \theta ^{(d)},$ where $d=\gcd (i,n).$

Let ${{\,\mathrm{Eq}\,}}(A)$ denote the set of all equivalence relations on a given set A (i.e., reflexive, symmetric and transitive relations). For the sake of simplification, we will use the following notation to denote the equivalence classes.

Notation 2.7

For $\varkappa \in {{\,\mathrm{Eq}\,}}(A)$ consider the corresponding partition $A/\varkappa$ into equivalence classes. If $A_1=\{a_{11},a_{12},\dots \}$, $A_2=\{a_{21},a_{22},\dots \}$, ..., $A_k=\{a_{k1},a_{k2},\dots \}$ are the equivalence classes of $\varkappa$ with at least two elements, then we use the notation

$$\begin{aligned} \varkappa&=[a_{11},a_{12},\dots ]\,[a_{21},a_{22},\dots ]\,\dots \, [a_{k1},a_{k2},\dots ]\text { or } \\ \varkappa&=[A_1]\,[A_2]\,\dots \,[A_k]. \end{aligned}$$

Definition 2.8

If L is lattice, then a non-unit element $a \in L$ is called meet-irreducible (shortly $\wedge$-irreducible) if $a=b_1 \wedge b_2$ implies $a \in \{b_1, b_2\}$. Similarly, nonzero element $a \in L$ is called join-irreducible ($\vee$-irreducible) if $a=b_1 \vee b_2$ implies $a \in \{b_1, b_2\}$ (see e.g. [9]).

Lemmas 2.9, 2.10 present some properties of operations $f, g \in A^A$ with ${{\,\mathrm{Con}\,}}(A,f)\subseteq {{\,\mathrm{Con}\,}}(A,g)$, (see [7]).

Lemma 2.9

Let $f,g\in A^A$ be nontrivial and ${{\,\mathrm{Con}\,}}(A,f)\subseteq {{\,\mathrm{Con}\,}}(A,g)$. Then we have

• (i) $\forall x,y\in A: (x,y)\in \varkappa \in {{\,\mathrm{Con}\,}}(A,f)\implies (g(x),g(y))\in \varkappa$, in particular we have $(g(x),g(y))\in \theta _f(x,y)$ and $\theta _{g}(x,y)\subseteq \theta _{f}(x,y)$.

• (ii) Let B be a subalgebra of (A, f). Then either B is also a subalgebra of (A, g) or g is constant on B, where the constant does not belong to B.

Lemma 2.10

Let $f, g \in A^A$ be nontrivial. Then

$$\begin{aligned} {{\,\mathrm{Con}\,}}(A,f) \subseteq {{\,\mathrm{Con}\,}}(A,g) \Leftrightarrow \forall x, y \in A: (g(x), g(y)) \in \theta _f(x, y).\end{aligned}$$

Corollary 2.11

Let $g_i, i\in I$ be nontrivial operations on A. Then

$$\begin{aligned} {{\,\mathrm{Con}\,}}(A, f)= \bigcap _{i\in I} {{\,\mathrm{Con}\,}}(A, g_i) \Leftrightarrow \forall x,y\in A: \theta _f(x,y)= \bigvee _{i\in I} \theta _{g_i}(x,y).\end{aligned}$$

Lemma 2.12

Assume that a is a noncyclic element of A and $a'$ is its colleague. Let $d=\min \{m\in {\mathbb {N}}: f^m(a)=a'\}.$ Then |C(a)| divides d.

Proof

Let $|C(a)|=c$ and $k=t_f(a)$. Since a is noncyclic, $a' = f^{i-1}(f^k(a)),$ where $i =\min \{n\in {\mathbb {N}}, n+k-1 \equiv 0 \pmod {c}\}$, i.e., $a' = f^{k+i-1}(a)$. Clearly, $d=k+i-1 \equiv 0\pmod {c}$, hence c divides d. $\square$

Corollary 2.13

Let $x,y \in A$ be noncyclic, $C(x)=C(y)$. Then $(x', y')\in \theta _f(x,y)$ i.e., $\theta _f(f(x'), f(y')) \subseteq \theta _f(f(x), f(y))$.

Proof

Let $|C(x)|=c$. Lemma 2.12 yields that there exist $k,l \in {\mathbb {N}}$ such that $f^{ck}(x)=x'$ and $f^{cl}(y)=y'$. Hence $f^{ck+cl}(x)=x'$ and $f^{ck+cl}(y)=y'$, which implies $\theta _f(x, y)=[x,y][f(x), f(y)]\dots [x', y']\dots$ $\square$

Lemma 2.14

Let a be a noncyclic element of A. Then $(a', a) \in \theta _f(a, x)$ for each $x\in (a)_f.$

Proof

Let $|C(a)|=c$ and $d\in {\mathbb {N}}$ be such that $f^d(a)=x.$ Clearly, there exists $j\in {\mathbb {N}}$ such that $f^{jd}(a),f^{jd}(x)\in C(a),$ which implies that

$$\begin{aligned} \theta _f(f^{jd}(a),f^{jd}(x))=\theta ^{(\gcd (d,c))} \subseteq \theta _f(a,x). \end{aligned}$$

We denote $m=\gcd (d,c),$ hence there exist $k,l \in {\mathbb {N}}$ such that

$$\begin{aligned} d=km, c=lm.\end{aligned}$$

According to Lemma 2.12, there exists $i\in {\mathbb {N}}$ such that $f^{ic}(a)=a'.$ Apparently, $(f^{ic}(a), f^{ic}(x))=(a', f^{iml}(x))\in \theta _f(a,x)$. Moreover, $f^{nd}(x)=f^{nkm}(x), f^{ic}(x)=f^{nkm}(x)\in C(a)$ imply that

$$\begin{aligned} (f^{nkm}(x), f^{ilm}(x)) \in \theta ^{(m)} \subseteq \theta _f(a,x).\end{aligned}$$

It is easy to see that the following elements are congruent in $\theta _f(a,x):$

$$\begin{aligned}&a, f^{d}(a)=x, f^{2d}(a), \dots \\&x, f^{d}(x), f^{2d}(x), \dots , f^{nd}(x), \dots \end{aligned}$$

which yields that $(a, f^{nd}(x))=(a, f^{nkm}(x))\in \theta _f(a,x).$

Hence, we get $(a', f^{iml}(x)), (f^{ilm}(x),f^{nkm}(x)),(f^{nkm}(x),a) \in \theta _f(a,x)$ and from transitivity, it follows that $(a, a') \in \theta _f(a, x).$ $\square$

Corollary 2.15

Let (A, f) be a connected monounary algebra. Let $x,y\in A$ such that x is cyclic, y is noncyclic. Then $(b,b')\in \theta _f(x,y)$ for each $b\in \langle y)_f.$

Proof

Holds trivially if b is cyclic.

Assume that b is noncyclic. For $b=y$, the assertion holds according to Lemma 2.14.

If $b\in (y)_f$ then there is $n\in {\mathbb {N}}$ such that $f^n(y)=b.$ Then $(f^n(x),b)=(f^n(x),f^n(y))\in \theta _f(x,y)$ which implies that $\theta _f(b, f^n(x))\subseteq \theta _f(x,y).$ Moreover, $f^n(x)$ is cyclic, hence $f^n(x)\in (b)_f$ and from Lemma 2.14 we get $(b,b')\in \theta _f(b, f^n(x))\subseteq \theta _f(x,y).$ $\square$

If (A, f) is either a permutation-algebra with short tails or its cycle contains at most 2 elements, then the necessary and sufficient conditions under which ${{\,\mathrm{Con}\,}}(A, f)$ is meet-irreducible were already proved in [6] and [7].

Definition 2.16

Let (A, f) be a connected algebra with the cycle C such that $|C|=n, n\ge 3.$ Next, let $C=\{0,1,\ldots ,n-1\}$ where $f(0)=1, f(1)=2, \ldots , f(n-1)=0$ (on C, we compute modulo n). We say that a cyclic element c is covered if there exists a noncyclic $x\in A\setminus C_1$ such that $c=x'$.

Further, we denote the canonical decomposition of the number of elements of C as $n=p_1^{\alpha _1}\ldots p_k^{\alpha _k}$; the numbers $p_l^{\alpha _l}$ for $l\in \{1,\ldots ,k\}$ are said to be elementary divisors of n. The cycle C is called covered if each equivalence class modulo $\sigma$, where $\sigma$ is an elementary divisor of n, contains at least one covered $c\in C$.

The following conditions are the conditions mentioned in Theorem 1.1.

Notation 2.17

Consider the following two conditions:

${(*1)}$:

the set C is covered,

${(*2)}$:

there exist distinct noncyclic elements $a,b,c,d\in A$ with $f(a), f(c)\in C$ and $f(b)=a, f(d)=c.$

3 The necessary condition

In this section, we prove that if either of the conditions ${(*1), (*2)}$ is not satisfied, then ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-reducible.

Lemma 3.1

Let (A, f) be a cycle with $\alpha \cdot \beta$ elements, where $\alpha$ and $\beta$ are mutually prime. If $g_1=f^\alpha$, $g_2=f^\beta$, then ${{\,\mathrm{Con}\,}}(A,f)={{\,\mathrm{Con}\,}}(A,g_1,g_2)$.

Proof

Clearly, ${{\,\mathrm{Con}\,}}(A,f)\subseteq {{\,\mathrm{Con}\,}}(A,g_1,g_2)$.

By number theory there exist positive integers $\iota , \kappa , \tau$ such that

$$\begin{aligned} \tau \alpha \beta +1=\iota \alpha +\kappa \beta .\end{aligned}$$

Let $\theta \in {{\,\mathrm{Con}\,}}(A,g_1,g_2)$, $(x,y)\in \theta .$ Then

$$\begin{aligned} (f(x),f(y))&=(f^{\tau \alpha \beta +1}(x), f^{\tau \alpha \beta +1}(y))=(f^{\iota \alpha +\kappa \beta }(x), f^{\iota \alpha +\kappa \beta }(y))\\ {}&=(g_1^\iota (g_2^\kappa (x)),g_1^\iota (g_2^\kappa (y)))\in {{\,\mathrm{Con}\,}}(A,g_1,g_2), \end{aligned}$$

hence ${{\,\mathrm{Con}\,}}(A,g_1,g_2)\subseteq {{\,\mathrm{Con}\,}}(A,f)$. $\square$

From now on, we use the notations from Definition 2.16.

Until Proposition 3.5 let us assume that ${(*1)}$ is not satisfied and that (A, f) is not a cycle. This yields that there are $l\in \{1,\dots ,k\}$ and $i\in C$ such that $c\equiv i \pmod {p_l^{\alpha _l}}$ fails to hold for any covered element $c\in C$. Without loss of generality, let $i=0$. Thus if c is covered then $p_l^{\alpha _l}$ does not divide c. Notice that then $f^{p^\alpha }(y)\in C$ for each $y\in A$.

Now we set $p=p_l$, $\alpha =\alpha _l$, $\beta =\frac{n}{p^\alpha }$, $j=p^{\alpha -1}\cdot \beta$.

We define the following operations on A:

$$\begin{aligned} g_3(x)&:=x'+p^{\alpha },\\ g_4(x)&:=x'+\beta \end{aligned}$$

for each $x\in A$, and

$$\begin{aligned} g(x):= {\left\{ \begin{array}{ll} x'+j+1 &{}\text {if}~{ x\in C\cup C_1, p^\alpha }~\text { divides}~{ x'}, \\ f(x) &{}\text {otherwise.} \end{array}\right. } \end{aligned}$$

Notice that the operations $g_3, g_4$ and g are nontrivial, distinct and not equal to f. Therefore, if ${{\,\mathrm{Con}\,}}(A,f)={{\,\mathrm{Con}\,}}(A,g_3)\cap {{\,\mathrm{Con}\,}}(A,g_4)\cap {{\,\mathrm{Con}\,}}(A,g),$ then ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-reducible.

Lemma 3.2

Let $x,y\in A$. Then $\theta _{g_3}(x,y)\vee \theta _{g_4}(x,y)\subseteq \theta _{f}(x,y).$

Proof

Let us show that $\theta _{g_3}(x,y)\subseteq \theta _{f}(x,y).$ The other inclusion is analogous. There is $t\in {\mathbb {N}}$ such that $\{f^t(x),f^t(y)\}\subseteq C$. This implies

$$\begin{aligned} (g_3(x),g_3(y))&=(x'+p^{\alpha },y'+p^{\alpha })\in \theta _f(x'+p^{\alpha },y'+p^{\alpha })\\&= \theta _f(x',y')=\theta _f(x'+t,y'+t)\\&=\theta _f(f^t(x),f^t(y))\subseteq \theta _f(x,y). \end{aligned}$$

$\square$

Lemma 3.3

Let $x,y\in A$. Then $\theta _{g}(x,y)\subseteq \theta _{f}(x,y).$

Proof

It is sufficient to show that $(g(x),g(y))\in \theta _{f}(x,y)$. Let $g(x)\ne f(x)$. Thus $x\in C\cup C_1$, $p^\alpha$ divides $x'$, $g(x)=x'+j+1$. If $g(y)=y'+j+1$, then we can proceed analogously as in the previous proof.

Suppose that $g(y)=f(y)$. Then $p^\alpha$ does not divide $y'$. Clearly,

$$\begin{aligned} (x'+1,f(y))=(f(x'),f(y))=(f(x),f(y))\in \theta _{f}(x,y). \end{aligned}$$

Since $(x',y')\in \theta _{f}(x,y)$, it holds that $\theta _{f}(x',y')\subseteq \theta _{f}(x,y)$. Moreover,

$$\begin{aligned} \theta _f(x',y')=\theta ^{(d)}, d=\gcd (x'-y',p^\alpha \beta ) \end{aligned}$$

Further, $p^\alpha$ does not divide $x'-y'$ and d divides $p^\alpha \beta$, thus d divides $p^{\alpha -1}\beta =j$. This implies

$$\begin{aligned} (x'+j+1,x'+1) =(f^{x'+1}(j), f^{x'+1}(0) )\in \theta _{f}(j,0)\subseteq \theta ^{(d)}\subseteq \theta _{f}(x,y). \end{aligned}$$

By transitivity, $(g(x),g(y))=(x'+j+1,f(y))\in \theta _{f}(x,y).$ $\square$

Lemma 3.4

Let $x,y\in A$. Then $\theta _{f}(x,y)\subseteq \theta _{g}(x,y)\vee \theta _{g_3}(x,y)\vee \theta _{g_4}(x,y).$

Proof

We want to prove that $(f(x),f(y))\in \theta _{g}(x,y)\vee \theta _{g_3}(x,y)\vee \theta _{g_4}(x,y).$ Let $\phi =\theta _{g}(x,y)\vee \theta _{g_3}(x,y)\vee \theta _{g_4}(x,y).$ Without loss of generality, $f(x)\ne g(x)$, i.e., $x\in C\cup C_1$, $p^\alpha$ divides $x'$, $g(x)=x'+j+1, f(x)=x'+1$.

If $g(y)=y'+j+1$ then $f(y)=y'+1$ and

$$\begin{aligned}(f(x),f(y))=(x'+1,y'+1)\in \theta _{f}(x'+1,y'+1)=\theta _{f}(x'+j+1,y'+j+1).\end{aligned}$$

For cyclic elements we will use Lemma 3.1, therefore

$$\begin{aligned}&\theta _{f}(x'+j+1,y'+j+1)\\ {}&={} \theta _{g_3}(x'+j+1,y'+j+1)\vee \theta _{g_4}(x'+j+1,y'+j+1)\\ {}&={} \theta _{g_3}(g(x),g(y))\vee \theta _{g_4}(g(x),g(y))\subseteq \phi , \end{aligned}$$

hence $(f(x),f(y))\in \phi .$

Now let $g(y)=f(y)$. Then $p^{\alpha }$ does not divide $y'$. We have

$$\begin{aligned}(x'+j+1,f(y))=(g(x),g(y))\in \phi . \end{aligned}$$

Next, $(x'+p^\alpha ,y'+p^\alpha )=(g_3(x),g_3(y))\in \phi .$ The elements $x'+p^\alpha ,y'+p^\alpha$ are cyclic, hence

$$\begin{aligned}&\theta _{g_3}(x'+p^\alpha ,y'+p^\alpha )\vee \theta _{g_4}(x'+p^\alpha ,y'+p^\alpha )=\theta _{f}(x'+p^\alpha ,y'+p^\alpha )\\&\quad ={} \theta _f(x',y')=\theta _{g_3}(x',y')\vee \theta _{g_4}(x',y'). \end{aligned}$$

This implies that $(x',y')\in \phi$ (and analogously $(x'+1,y'+1)\in \phi$), thus

$$\begin{aligned}(x'+j+1,y'+1)=(g(x'),g(y'))\in \phi . \end{aligned}$$

So, the congruence $\phi$ contains the pairs

$$\begin{aligned}(x'+1,y'+1), (y'+1,x'+j+1),(x'+j+1,f(y)), \end{aligned}$$

so by transitivity it also contains the pair $(x'+1,f(y))=(f(x),f(y))$. $\square$

Proposition 3.5

If (A, f) does not satisfy the condition ${(*1)}$, then ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-reducible.

Proof

For a single cycle, ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-reducible (see [6], Theorem 5.19). If (A, f) fails to be a cycle, then the assertion is valid according to Lemmas 3.2–3.4. $\square$

In 3.6–3.11, let us suppose that the condition ${(*2)}$ is not valid and that $C_2$ is nonempty.

Let k be the least positive integer such that there exist distinct noncyclic elements $a,b,c,d,e,t\in A$ such that $b\in C_k$, $f(b)=a,$ $f(c)=f(e)=b,$ $f(d)=c,$ $f(t)=e.$ If such k does not exist, then put $k=1$ and $a=f(b)$ for $c\in C_2, b=f(c)$.

Notice that if $k=1$ then $a\in C$.

First we will investigate the case $k> 1$.

We define the operations $g_5$ and $g_6$ on A by putting

$$\begin{aligned} g_5(x)&:= {\left\{ \begin{array}{ll} b' &{}\text {if}~{ f(x)=b}, \\ f(x) &{}\text {otherwise,} \end{array}\right. }\\ g_6(x)&:= {\left\{ \begin{array}{ll} a' &{}\text {if}~{ f(x)=a}, \\ f(x) &{}\text {otherwise.} \end{array}\right. } \end{aligned}$$

Lemma 3.6

Let $x,y\in A$. Then $\theta _{g_5}(x,y)\vee \theta _{g_6}(x,y)\subseteq \theta _{f}(x,y).$

Proof

The proof is easy; let us show it e.g. for $g_5$, $g_5(y)\ne g_5(x)\ne f(x)$. Then $f(x)=b,$ $g_5(x)=b',$ and $g_5(y)=f(y)$. It is sufficient to show that,

$$\begin{aligned} (b',f(y))=(g_5(x),g_5(y))\in \theta _f(f(x),f(y))=\theta _f(b,f(y)). \end{aligned}$$

Clearly, $f(y)\not =b,$ hence one of the following holds:

• 1) If $f(y)\in (b)_f$ then Lemma 2.14 yields $(b, b')\in \theta _f(b, f(y)).$

• 2) If $b\in (f(y))_f$ then Lemma 2.14 and Corollary 2.13 imply that $(f(y)',f(y))\in \theta _f(b,f(y))$ and $(f(y)',b')\in \theta _f(b,f(y)),$ respectively.

In both cases, the transitivity yields $(b',f(y))\in \theta _f(b,f(y)).$ $\square$

Lemma 3.7

Let $x,y\in A$. Then $\theta _{f}(x,y)\subseteq \theta _{g_5}(x,y)\vee \theta _{g_6}(x,y).$

Proof

Denote the relation on the right side by $\phi$. Suppose that $f(y)\ne f(x)\ne g_6(x)$. This implies $f(x)=a=g_5(x)$, $g_6(x)=a'$, $g_6(y)=f(y)$. If $g_5(y)=f(y)$, the assertion is obvious. Thus $g_5(y)=b'$ and $f(y)=b$. Then $(a',b)=(g_6(x),g_6(y))\in \phi$ and also $(f(a'),a)=(g_5(a'),g_5(b))\in \phi$. From the definition of $g_5,$ it follows that $(b',a')\in \phi$. Next, we have $(a,b')=(g_5(x),g_5(y))\in \phi$ and $(a',b)=(g_6(x),g_6(y))\in \phi ,$ therefore $(a,b)=(f(x),f(y))\in \phi$. $\square$

As a corollary of Lemmas 3.6 and 3.7 we obtain:

Corollary 3.8

If $k\ne 1$ then ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-reducible.

Now we deal with the case $k= 1$.

Let $g_7$ and $g_8$ be the following operations on A:

$$\begin{aligned} g_7(x)&:= {\left\{ \begin{array}{ll} b' &{}\text {if}{ f(x)=b}, \\ f(x) &{}\text {otherwise,} \end{array}\right. }\\ g_8(x)&:= {\left\{ \begin{array}{ll} b &{}\text {if}~{ f(x)\in C}, \\ b' &{}\text {otherwise.} \end{array}\right. } \end{aligned}$$

Lemma 3.9

Let $x,y\in A$. Then $\theta _{g_7}(x,y)\vee \theta _{g_8}(x,y)\subseteq \theta _{f}(x,y).$

Proof

Suppose that $g_8(x)\ne g_8(y)\ne f(y)$, hence without loss of generality: $g_8(x)=b, g_8(y)=b'.$ Therefore $f(x)\in C$ and $f(y)\notin C.$ From Corollary 2.15 we get $(g_8(x), g_8(y))=(b,b')\in \theta (f(x),f(y)).$

The proof for $g_7$ is analogous as in Lemma 3.6. $\square$

Lemma 3.10

Let $x,y\in A$. Then $\theta _{f}(x,y)\subseteq \theta _{g_7}(x,y)\vee \theta _{g_8}(x,y).$

Proof

Denote the relation on the right side by $\phi$. Let $f(y)\ne f(x)\ne g_7(x)$. Then $f(x)=b$, $g_7(x)=b'=g_8(x)$, $g_7(y)=f(y)$. We have $(b',f(y))=(g_7(x),g_7(y))\in \phi$, $(b',g_8(y))=(g_8(x),g_8(y))\in \phi .$

Let us show that $(b,f(y))=(f(x),f(y))\in \phi$, i.e., that $(b,b')\in \phi$.

If $f(y)\in C$ then $g_8(y)=b$ and the assertion is valid. Otherwise $f(y)\ne f(x)$ yields $f(y)\ne b$ hence $f^2(y)\notin C.$ Therefore $(b, b')=(g_8(b'), g_8(f(y)))=(g_8(g_7(x)), g_8(g_7(x)))\in \phi .$ $\square$

From Lemmas 3.9 and 3.10 it follows:

Corollary 3.11

If $k= 1$ then ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-reducible.

Proposition 3.12

If (A, f) does not satisfy the condition ${(*2)}$, then ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-reducible.

Proof

If (A, f) is a permutation-algebra with short tails, then ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-reducible (see [6], Theorem 5.19). Otherwise the assertion holds due to Corollary 3.8 and 3.11 . $\square$

4 The sufficient condition

In this section (until Proposition 4.7), we suppose that the condition ${(*1)}$ (with notations from Definition 2.16) and the condition ${(*2)}$ are satisfied. Our aim is to prove that ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-irreducible.

Notice that since the condition ${(*2)}$ is satisfied, there exist distinct noncyclic elements $a,b,c,d\in A$ such that $f(a), f(c)\in C$ and $f(b)=a, f(d)=c.$

Lemma 4.1

Let g be a nontrivial operation on A with ${{\,\mathrm{Con}\,}}(A,f)\subseteq {{\,\mathrm{Con}\,}}(A,g)$. Then $g(a)=g(a')\in C$, $g(c)=g(c')\in C$ and either

• (a) $g(b)=a$, $g(d)=c$, $g(b')=a'$, $g(d')=c'$, or

• (b) $g(b)=g(b')\in C$, $g(d)=g(d')\in C$.

Proof

Let $g(a)\ne g(a').$ Since $\theta _{g}(a,a')\subseteq \theta _{f}(a,a')=[a,a']$, this implies $g(a)=a',$ $g(a')=a.$ Then by Lemma 2.9, $g(x)=a$ for each $x\in C$. Thus

$$\begin{aligned} (g(c),a)=(g(c),g(c'))\in \theta _{g}(c,c')\subseteq \theta _{f}(c,c')=[c,c'],\end{aligned}$$

hence $g(c)=a,$ and

$$\begin{aligned} (a,a')=(g(c),g(a))\in \theta _{f}(a,c)=[a,c]\ \ldots , \end{aligned}$$

which is a contradiction. It follows that $g(x)=g(x')$ for each $x\in C_1$.

Let $g(a)= g(a')=y\notin C.$ Then

$$\begin{aligned} (g(y), y)=(g(y),g(y'))\in \theta _{f}(y,y')=[y,y']\ \ldots , \end{aligned}$$

implies that $g(y)\in \{y,y'\}.$ Let $g(y)=y'$ and without loss of generality, let $y\not = a$ (otherwise, let $y\not = c$). It follows that

$$\begin{aligned} (y, y')=(g(a),g(y))\in \theta _{f}(a,y)=[a,y]\ \dots , \end{aligned}$$

which is a contradiction. Therefore, $g(x)=g(x')\in C$ for each $x\in C_1.$

Next, $(g(b),g(d))\in \theta _{f}(b,d)=[b,d] [a,c]\ \ldots$

Clearly, if $g(b)\in C$ then $g(d)\in C$. Moreover,

$$\begin{aligned} (g(b),g(b'))&\in \theta _{f}(b,b')=[b,b'] [a,a'],\\ (g(d),g(d'))&\in \theta _{f}(d,d')=[d,d'] [c,c'], \end{aligned}$$

imply that $g(b)=g(b')$ and $g(d)=g(d')$, hence the condition (b) is valid.

If $g(b)\notin C$ then $g(b)\in \{a,b\}.$ Since

$$\begin{aligned} (g(b),g(c))\in \theta _{f}(b,c)=[b,c] [a,\ldots ]\ \ldots , \end{aligned}$$

and $g(a)\in C$, we get $g(b)=a$. Similarly, $g(d)=c$ and (a) holds. $\square$

Lemma 4.2

Suppose that ${{\,\mathrm{Con}\,}}(A, f)$ is $\wedge$-reducible. Then there exists a nontrivial operation g on A such that ${{\,\mathrm{Con}\,}}(A, f) \subsetneq {{\,\mathrm{Con}\,}}(A, g)$ and the condition (a) of Lemma 4.1 is valid.

Proof

${{\,\mathrm{Con}\,}}(A, f)$ is $\wedge$-reducible implies that there is a set G of nontrivial operations on A such that $|G|\ge 2$ and

$$\begin{aligned} {{\,\mathrm{Con}\,}}(A, f)=\bigcap _{g\in G}{{\,\mathrm{Con}\,}}(A, g),\ {{\,\mathrm{Con}\,}}(A, f)\not = {{\,\mathrm{Con}\,}}(A, g) \text { for } g\in G. \end{aligned}$$

Assume that for every $g\in G$ the condition (a) fails to hold. Then according to Lemma 4.1, the condition (b) is valid and $g(b)=g(b')$. This yields

$$\begin{aligned} \bigvee _{g\in G} \theta _{g}(b,b')=[b,b']\not = [b,b'][a,a']=\theta _f(b, b'), \end{aligned}$$

which is a contradiction. $\square$

In Lemmas 4.3–4.6 we will suppose that g is a nontrivial operation on A such that ${{\,\mathrm{Con}\,}}(A, f) \subseteq {{\,\mathrm{Con}\,}}(A, g)$ and the condition (a) of Lemma 4.1 is satisfied.

Lemma 4.3

$g(x)=f(x)$ for each $x\in A\setminus (C\cup C_1)$.

Proof

Let $x\in A\setminus (C\cup C_1)$. Then either $a\notin \langle x)_f$ or $c\notin \langle x)_f.$ Without loss of generality, let $a\notin \langle x)_f.$ Then

$$\begin{aligned} (g(x),a)=(g(x),g(b))\in \theta _f(x,b)=[x,b][f(x),a]\dots , \end{aligned}$$

implies that $g(x)\in \{f(x),a\}$. Further,

$$\begin{aligned}g(x')\in C\quad \text {and} \quad (g(x),g(x'))\in \theta _f(x,x') \subseteq [\langle x)_f] \end{aligned}$$

imply $g(x)\in \langle x)_f$, hence $g(x)\in \{f(x),a\} \cap \langle x)_f$. Moreover, $a\notin \langle x)_f$, which yields $g(x)=f(x)$. $\square$

Lemma 4.4

$g(t)=f(t)$ for each covered element $t\in C$.

Proof

Let $t\in C$ be covered. If $x\in A{\setminus }(C\cup C_1)$ is an element covering t, i.e. $t=x'$, then we can assume that $x\in C_i$ for $2\le ~i\le n+1$ with $t=x'$. From Lemma 4.3, it follows that $g(x)=f(x)$. If $i\le n$ then

$$\begin{aligned} (g(t),f(x))=(g(t),g(x))\in \theta _{f}(t,x)=[t,x][f(t),f(x)]\dots [f^{i-1}(t),f^{i-1}(x)]. \end{aligned}$$

Hence, $g(t)\in \{f(t), f(x)\}$. Moreover, the assumption that the condition (a) of Lemma 4.1 is satisfied implies that $g(a')\in C$ and from Lemma 2.9 (ii) it follows that $f(t)\in C$. Therefore we get $g(t)=f(t)$.

If $i=n+1$, then

$$\begin{aligned} (g(t),f(x))&=(g(t),g(x))\in \theta _{f}(t,x)\\&=[t,x, f^{n}(x)][f(t),f(x)]\ldots [f^{n-1}(t),f^{n-1}(x)]. \end{aligned}$$

Analougously as in the previous case, we get $g(t)=f(t)$. $\square$

Lemma 4.5

$g(i)=f(i)$ for each $i\in C$.

Proof

Let $i\in C$. The condition ${(*1)}$ implies that for each $l\in \{1,\ldots ,k\}$ there exists a covered $c_l\in C$ such that $c_l\equiv i \pmod {p_l^{\alpha _l}}$. By Lemma 4.4

$$\begin{aligned} (g(i),c_l+1)= (g(i),f(c_l))=(g(i),g(c_l))\in \theta _{f}(i,c_l)\subseteq \theta ^{(p_l^{\alpha _l}) }, \end{aligned}$$

thus $g(i)\equiv c_l+1 \pmod {p_l^{\alpha _l}}$ for each l. According to Chinese Remainder Theorem, the system of congruences $x\equiv c_l+1 \pmod {p_l^{\alpha _l}}, l \in \{1,\ldots ,k\}$ has a solution, and the solution is unique modulo $n=p_1^{\alpha _1}\ldots p_k^{\alpha _k}$. Moreover, $i+1$ is a solution of this system, what yields that $g(i)=i+1=f(i)$. $\square$

Lemma 4.6

$g(t)=f(t)$ for each $t\in C_1$.

Proof

Using Lemma 4.5 we have

$$\begin{aligned} (g(t),f(t'))=(g(t),g(t'))\in \theta _{f}(t,t')=[t,t'], \end{aligned}$$

hence $g(t)=f(t')=f(t)$. $\square$

Proposition 4.7

If the conditions ${(*1)}$ and ${(*2)}$ are valid, then ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-irreducible.

Proof

Suppose that the conditions ${(*1)}$ and ${(*2)}$ are valid and that ${{\,\mathrm{Con}\,}}(A, f)$ is $\wedge$-reducible. Due to Lemma 4.2 there exists a nontrivial operation g on A such that ${{\,\mathrm{Con}\,}}(A, f) \subsetneq {{\,\mathrm{Con}\,}}(A, g)$ and the condition (a) of Lemma 4.1 is valid. Then Lemmas 4.3–4.6 imply that $g(x)=f(x)$ for each $x\in A,$ which is a contradiction. $\square$

From Proposition 3.12 and Proposition 4.7 we obtain:

Theorem 4.8

Let (A, f) be a connected monounary algebra with at least 3 cyclic elements. Then ${{\,\mathrm{Con}\,}}(A,f)$ is $\wedge$-irreducible if and only if the conditions ${(*1)}$ and ${(*2)}$ are satisfied.

Hence Theorem 1.1 is valid.