The variety generated by semi-Heyting chains

Abstract

The purpose of this paper was to investigate the structure of semi-Heyting chains and the variety ${{\mathcal{CSH}}}$ generated by them. We determine the number of non-isomorphic n-element semi-Heyting chains. As a contribution to the study of the lattice of subvarieties of ${{\mathcal{CSH}}},$ we investigate the inclusion relation between semi-Heyting chains. Finally, we provide equational bases for ${{\mathcal{CSH}}}$ and for the subvarieties of ${{\mathcal{CSH}}}$ introduced in [5].

1 Introduction and preliminaries

In [5], Sankappanavar introduced a new equational class of algebras, which he called “semi-Heyting Algebras”, as an abstraction of Heyting algebras. This variety includes Heyting algebras and shares with them some rather strong properties. For example, the variety of semi-Heyting is arithmetical; semi-Heyting algebras are pseudocomplemented distributive lattices, and their congruences are determined by filters.

The purpose of this paper was to investigate the properties of semi-Heyting chains and the structure of the variety ${{\mathcal{CSH}}}$ generated by all semi-Heyting chains. In [5], Sankappanavar posed the following problem: for ${{\mathcal{V}}}$ a subvariety of semi-Heyting algebras and n a natural number, if $f({{\mathcal{V}}},n)$ denotes the number of non-isomorphic n-element semi-Heyting chains in ${{\mathcal{V}}},$ find a formula for $f({{\mathcal{V}}},n)$. In Sect. 2, we prove some results on semi-Heyting chains and find $f({{\mathcal{SH}}},n),$ i.e., we determine the number of non-isomorphic structures of semi-Heyting algebra that can be defined over an n-element chain. Section 3 is devoted to investigate the behavior of the subalgebras of a given semi-Heyting chain. Finally, we find equational bases for many subvarieties of ${{\mathcal{CSH}}}$ in Sect. 4, solving the problems 14.6–14.10 posed in [5].

We start by recalling some definitions and results. For basic notation and results, the reader is referred to [1–4].

Definition 1.1

An algebra ${\bf L} = \langle L, \vee, \wedge, \rightarrow, 0, 1\rangle$ is a semi-Heyting algebra if the following conditions hold:

• (SH1) $\langle L, \vee, \wedge, 0, 1\rangle$ is a lattice with 0 and 1;

• (SH2) $x \wedge (x \rightarrow y) \approx x \wedge y;$

• (SH3) $x \wedge (y \rightarrow z) \approx x \wedge [(x \wedge y) \rightarrow (x \wedge z)];$

• (SH4) $x \rightarrow x \approx 1.$

We will denote by ${{\mathcal{SH}}}$ the variety of semi-Heyting algebras.

Semi-Heyting algebras are pseudocomplemented distributive lattices, with the pseudocomplement given by $x^{*} = x \rightarrow 0$ (see [5]).

Lemma 1.2

[5] Let ${{\mathbf{L}}} \in {{\mathcal{SH}}}$ and $a, b \in L.$

• (a) If $a \rightarrow b =1$ then $a \, \leq \, b.$

• (b) If $a \, \leq \, b$ then $a \, \leq \, a \rightarrow b.$

• (c) $a=b$ if and only if $a \to b = b \to a = 1.$

• (d) $1 \to a = a.$

Proof

From $a \to b = 1$ and (SH3), we get $a \wedge 1 = a \wedge b,$ i.e., $a = a \wedge b,$ and we have (a). For (b), by (SH3) and $a \, \leq \, b$ it follows that $a =a \wedge (a \to b) \, \leq \, a \to b.$ Property (c) is clear. To prove (d), observe that $a = 1 \wedge a = 1 \wedge (1 \to a) = 1 \to a.$ $\square$

Congruences on semi-Heyting algebras are determined by filters. Besides, we have the following characterization of subdirectly irreducible algebras in ${{\mathcal{SH}}}$ (see [5, Theorem 7.5])

Theorem 1.3

Let${{\mathbf{L}}} \in {{\mathcal{SH}}}$with$|{{\mathbf{L}}}| \, \geq \, 2.$The following are equivalent:

• (a) Lis subdirectly irreducible.

• (b) Lhas a unique coatom.

Observe that as a consequence of this theorem, if L is subdirectly irreducible, then $1 \in L$ is $\vee$-irreducible.

2 Semi-Heyting chains

We say that ${{\mathbf{L}}} \in {{\mathcal{SH}}}$ is a semi-Heyting chain if the lattice reduct of L is totally ordered. In this section, we prove some results on semi-Heyting chains, and we determine a formula for the number of semi-Heyting structures that can be defined on an n-element chain. We generalize the results of Sankappanavar in [5] for chains with 2, 3, and 4 elements.

The following lemma states that part of the operation table of $\to$ in a semi-Heyting chain is uniquely determined.

Lemma 2.1

[5] Let L be a semi-Heyting chain, $a,b \in L.$ If $a < b$ then $b \rightarrow a = a.$

Proof

From $b \wedge a = b \wedge (b \to a)$ and $a < b,$ we obtain $a = b \wedge (b \to a).$ As L is a chain, $a = b$ or $a = b \to a,$ so $a = b \to a.$ $\square$

The next two lemmas are useful when we have to verify if a given chain is a semi-Heyting algebra.

Lemma 2.2

Let$\langle L, \vee, \wedge, \rightarrow, 0, 1\rangle$be a totally ordered bounded lattice L with a binary operation → such that if$a, b \in L$with$a< b$then$b \rightarrow a = a.$The following conditions are equivalent:

• (1)

  • (a) $x \rightarrow x \approx 1;$

  • (b) $x \wedge (x \rightarrow y) \approx x \wedge y;$

• (2)

  • (a) $x \rightarrow x \approx 1;$

  • (b) If $x < y$ then $x \wedge (x \rightarrow y) = x \wedge y.$

Proof

We only have to prove that $(2) \Rightarrow (1).$ We want to prove that $a \wedge (a \to b) = a \wedge b$ for every $a, b \in L.$ If $a < b,$ by (2) (b), $a \wedge (a \to b) = a \wedge b.$ If $a = b$ by (2)(a), $a \wedge (a \to a) = a \wedge 1 = a = a \wedge a.$ Finally, if $a > b,$ by hypothesis $a \rightarrow b = b$ and so, $a \wedge (a \to b) = a \wedge b.$ $\square$

Lemma 2.3

Let$\langle L, \vee, \wedge, \rightarrow, 0, 1\rangle$be a totally ordered bounded lattice L with a binary operation → such that if$a, b \in L$with$a< b$then$b \rightarrow a = a.$The following conditions are equivalent

• (1) $\langle L, \vee, \wedge, \rightarrow, 0, 1\rangle \in {{\mathcal{SH}}};$

• (2)

  • (a) $x \rightarrow x \approx 1;$

  • (b) $x \wedge (x \rightarrow y) \approx x \wedge y;$

  • (c) If $y < x < z,$ then $x \wedge (y \rightarrow x) = x \wedge (y \rightarrow z).$

Proof

• (1)$\Rightarrow$ (2). As ${{\mathbf{L}}} = \langle L, \vee, \wedge, \rightarrow, 0, 1\rangle \in {{\mathcal{SH}}}, {{\mathbf{L}}}$ satisfies (2)(a) and (2)(b). Let $a, b, c \in L$ such that $b < a < c.$ Then $a \wedge (b \to c) = a \wedge [(a \wedge b) \to (a \wedge c)] = a \wedge (b \to a).$

• (2)$\Rightarrow$ (1). It is enough to prove (SH3). Let $a,b,c \in L,$ and suppose that $c < b.$

If $a < c,$ then $a \wedge b = a \wedge c = a.$ So $a \wedge (b \to c) = a \wedge c = a$ and $a \wedge [(a \wedge b) \to (a \wedge c)] = a \wedge a = a.$ If either $c < a < b$ or $c < b < a,$ then $a \wedge c < a \wedge b.$ Thus, $a \to [(a \wedge b) \to (a \wedge c)] = a \wedge a = a.$

The other cases are similar. $\square$

Lemma 2.4

LetLbe a semi-Heyting chain. The following conditions are equivalent:

• (a) $0 \to a = 0$ for some $a \in L$ with $a \not= 0.$

• (b) $0 \to b = 0$ for every $b \in L$ with $b \not= 0.$

Proof

Suppose that $0 \to a = 0$ for some $a \in L,$ $a \neq 0.$ $0 = a \wedge 0 = a \wedge (0 \to a) = a \wedge ((0 \wedge a) \to (1 \wedge a)) = a \wedge (0 \to 1).$ As $a \not= 0$ and L is a chain, $0 \to 1 = 0.$ Let $b \in L$ such that $b \not= 0.$ $0= b \wedge 0 = b \wedge (0 \to 1)\buildrel{(SH3)} \over {=} b \wedge (0 \to b).$ As $b \not= 0$ and L is a chain, $0 \to b = 0.$ $\square$

In particular, if $0 \to 1 = 0,$ then $0 \to b = 0$ for every $b \in L,$ $b \not= 0.$

In order to determine the number of semi-Heyting algebras that can be defined on an n-element chain, let us consider first the following example, since it contains the main ideas underlying in the procedure.

Let L be a 4-element lattice, $L = \{ 0 , a_1, a_2, 1\},$ with $0 = a_0 < a_1 < a_2 < a_3 = 1.$ Consider a binary operation $\to: {\bf L} \times {\bf L} \to {\bf L}$ in such a way that $\langle L, \wedge, \vee, \to, 0, 1 \rangle$ is a semi-Heyting chain. From Lemma 2.1, we know that for $x,y \in L,$ if $x < y$ then $y \to x = x.$ Consequently, the lower half under the main diagonal, including that diagonal, of the operation table of $\to$ of L is uniquely determined. So, it remains to fill in the upper half of the table, i.e., the elements $x \to y$ for $x < y.$

Observe that if $x \, \leq \, y$ then $x \, \leq \, x \to y$ (Lemma 1.2).

If $0 \to 1 = 0,$ then by Lemma 2.4, $0 \to a_1 = 0 \to a_2 = 0.$ So, the first row in the table is

If $0 \to 1 = a_1,$ then $0 \to a_2 = a_2$ and $0 \to a_1 \in [a_1),$ where $[x) = \{y \in L: x \, \leq \, y\}.$

Indeed, $a_1 = a_2 \wedge a_1 = a_2 \wedge (0 \to 1) = a_2 \wedge (0 \to a_2),$ so $0 \to a_2 = a_1;$ and $a_1 = a_1 \wedge (0 \to 1) \buildrel{(SH3)} \over {=} a_1 \wedge (0 \to a_1),$ i.e., $0 \to a_1 \, \geq \, a_1.$

So in this case, the first row of the table is

In a similar way, it can be seen that if $0 \to 1 = a_2$ or $0 \to 1 = 1,$ then $0 \to a_2 \in [a_2)$ and $0 \to a_1 \in [a_1).$ So we have

Then we can write for the first row

$$ (0 \to 1, 0 \to a_2, 0 \to a_1) = \left\{ \begin{array}{ll} (0,0,0) , & \\ (a_1,a_1,z) , & \hbox{with } z \in [a_1) \\ (x,y,z) , & \hbox{with } x,y \in [a_2), z \in [a_1),\\ \end{array} \right. $$

i.e., $(0 \to 1, 0 \to a_2, 0 \to a_1) \in \left\{\{0\} \times \{0\} \times \{0\} \right\} \cup \left\{ \{a_1\} \times \{a_1\} \times [a_1)\right\} \cup \left\{ \{a_2\} \times [a_2) \times [a_1)\right\} \cup \left\{ \{1\} \times [a_2) \times [a_1)\right\}.$

For the second and third rows, we would have the following possibilities, determined by $a_1 \to 1$ and $a_2 \to 1,$ respectively:

Observe that the behavior of each row is independent of the others, and that, for $x < y,$ the element $x \to y$ depends on the element $x \to 1.$

The following lemma shows that in every semi-Heyting chain, the operation table of $\to$ behaves as in the previous example.

Lemma 2.5

Let L be a semi-Heyting chain and let $a,b,c \in L,$ $a \not= 1.$ If $a \rightarrow 1 = b$ then for $c > a$

$$\left\{ \begin{array}{ll} a \to c = b & \hbox{if } b<c; \\ a \to c \in [c) & \hbox{if } b \ge c.\\ \end{array} \right. $$

Proof

Suppose that $b<c.$ From $a \to 1 = b$ we get $c \wedge (a \to 1) = c \wedge b = b,$ i.e., $c \wedge [(c \wedge a) \to (c \wedge 1)] = b.$ Thus, $c \wedge (a \to c) = b.$ As L is a chain and $b < c,$ then $b = a \to c.$

The case $b \, \geq \, c$ is similar. $\square$

Let ${{\mathbf{L}}}_{n} = \langle L_n, \wedge, \vee, 0, 1 \rangle$ be an n-element totally ordered lattice:

$$ 0 = a_{0} < a_{1} < \cdots < a_{n-2} < a_{n-1} = 1. $$

Let $\to: {\bf L}_{n} \times {\bf L}_{n} \to {\bf L}_{n}$ be a function such that $\langle L_{n}, \wedge, \vee, \to, 0 , 1 \rangle \in {{\mathcal{SH}}}.$

Motivated by the previous example, we are going to introduce the following sets:

For $a_{j} \in L_{n},$ $0 \, \leq \, j \, \leq \, n-1,$ and for $1 \, \leq \, k \, \leq \, n-1,$

$$ E_{k}^{j} = \left\{ \begin{array}{lll} \left\{a_{j}\right\} & \text{if} & k < n - j\\ \left[a_{n - k}\right) & \text{if} & k \ge n - j \\ \end{array} \right. $$

and for $a_i \, \leq \, a_j,$

$$ E_{a_j}^{a_i} = \prod\limits_{k = 1}^{n - i - 1} E_{k}^{j} $$

Finally, let $F_{i}$ be the set

$$ F_i = \bigcup\limits_{j = i}^{n-1}E_{a_j}^{a_i}\quad \text{with} \quad 0 \le i < n - 1, $$

where $F_i$ would represent the row in the table that corresponds to the elements of the form $a_{i} \to y$ with $a_{i} < y.$

In the previous example (n = 4),

$$ \begin{aligned} F_{0} &= \bigcup\limits_{j = 0}^{3}E_{a_j}^{a_0} = E_{a_0}^{a_0} \cup E_{a_1 }^{a_0 } \cup E_{a_2 }^{a_0 } \cup E_{a_3 }^{a_0 } = \left\{ E_{1}^{0} \times E_{2}^{0} \times E_{3}^{0} \right\} \cup \left\{ E_{1}^{1} \times E_{2}^{1} \times E_{3}^{1} \right\} \cup \\ &\left\{ E_{1}^{2} \times E_{2}^{2} \times E_{3}^{2} \right\} \cup \left\{ E_{1}^{3} \times E_{2}^{3} \times E_{3}^{3} \right\}\\ = & \left\{ \{a_{0}\} \times \{a_{0}\} \times \{a_{0}\} \right\} \cup \left\{ \{a_{1}\} \times \{a_{1}\} \times [a_{1})\right\} \cup \left\{ \{a_{2}\} \times [a_{2}) \times [a_{1})\right\} \cup \left\{ \{a_{3}\} \times [a_{2}) \times [a_{1})\right\}, \\ \end{aligned} $$

We have $(0 \to 1, 0 \to a_2, 0 \to a_1) \in F_0,$ $(a_1 \to 1, a_1 \to a_2) \in F_1$ and $a_2 \to 1 \in F_2$ and we will write $((0 \to 1, 0 \to a_2, 0 \to a_1),(a_1 \to 1, a_1 \to a_2), a_2 \to 1) \in F_{0} \times F_{1} \times F_{2}.$

This motivates the introduction of the following set F that would represent the upper half above the main diagonal of the table:

$$ F = \prod\limits_{i = 0}^{n - 2} {F_i }. $$

Lemma 2.6

$(a_{i} \to 1;a_{i} \to a_{n-2}, \ldots, a_{i} \to a_{i+1}) \; \in \; F_{i}.$

Proof

As $a_{i} \, \leq \, 1,$ then $a_{i} \to 1 \, \geq \, a_{i}.$ Suppose that $a_{i} \to 1 = a_{k}$ with $i \, \leq \, k \, \leq \, n-1.$ We will see that $(a_{i} \to 1;a_{i} \to a_{n-2}, \ldots, a_{i} \to a_{i+1})\; \in E_{a_{k}}^{a_{i}}.$ By Lemma 2.5,

$$ a_i \to a_j \left\{ \begin{array}{lllll} = a_k & \text{if} & k < j &\\ \ge a_j & \text{if} & k \ge j & \text{with} & j > i\\ \end{array} \right. .$$

(1)

We will see that $a_{i} \to a_{j} \in E_{n-j}^{k}$ with $i+1 \, \leq \, j \, \leq \, n-1.$ If $n-j < n-k,$ then $j > k.$ Hence, by Eq. 1, $a_{i} \to a_{j} = a_{k}$ and, consequently, $a_{i} \to a_{j} \in E_{n-j}^{k}.$ If $n-j \, \geq \, n-k,$ then $j \, \leq \, k.$ Thus, by Eq. 1, $a_{i} \to a_{j} \, \geq \, a_{j},$ and then $a_{i} \to a_{j} \in [a_{n-(n-j)}).$ So, $a_{i} \to a_{j} \in E_{n-j}^{k}$ and $(a_{i} \to 1;a_{i} \to a_{n-2}, \ldots, a_{i} \to a_{i+1}) \in E_{a_{k}}^{a_{i}}.$ Therefore, $(a_{i} \to 1;a_{i} \to a_{n-2}, \ldots, a_{i} \to a_{i+1}) \; \in \; F_{i}. \square$

Notation 2.7

We denote $\alpha_{\to}(i) = (a_{i} \to 1;a_{i} \to a_{n-2}, \ldots, a_{i} \to a_{i+1})$ with $0 \, \leq \, i \, \leq \, n-2.$

Corollary 2.8

$(\alpha_{\to}(0), \alpha_{\to}(1), \ldots, \alpha_{\to}(n-2))\; \in \; F.$

Now we are going to construct an implication from a given element $x \in F.$

Consider the set F and $x \in F.$ Then $x = (x(0), x(1), \ldots, x(n-2)),$ where $x(i) \in F_{i}$ for $0 \, \leq \, i \, \leq \, n-2.$ Now, for each i, there exists $j_{i}$ with $i \, \leq \, j_{i} \, \leq \, n-1$ such that $x(i) \in E_{a_{j_{i}}}^{a_{i}}.$ Hence, $x(i) = (x(i)_{j_{i}}(1),x(i)_{j_{i}}(2), \ldots,x(i)_{j_{i}}(n-i-1))$ with $x(i)_{j_{i}}(k) \in E_{k}^{j_{i}},$ $1 \, \leq \, k \, \leq \, n-i-1.$ We define in $L_{n}$ an operation $\Rightarrow$ in the following way:

$$ a_{r} \Rightarrow a_{l} = \left\{ \begin{array}{lll} a_l & \text{if} & r > l \\ a_{n - 1} & \text{if} & r = l\\ x_{j_r} (r)(n - l) & \text{if} & r < l\\ \end{array} \right. $$

The following lemma proves that $\Rightarrow$ is a semi-Heyting implication.

Lemma 2.9

$\langle L_{n}, \wedge, \vee, \Rightarrow, 0, 1\rangle \; \in\; {{\mathcal{SH}}}.$

Proof

First observe that if $r < l,$ then $1 \, \leq \, n-l \, \leq \, n-r-1.$ So $\Rightarrow$ is well defined.

Now, we will see that $\Rightarrow$ it is an implication of semi-Heyting algebras.

By definition of $\Rightarrow, L \models x \Rightarrow x \approx 1.$

Let us see that $L \models x \wedge (x \Rightarrow y) \approx x \wedge y.$ Let $x,y \in L$ with $x < y.$ Then $x = a_{r}$ and $y = a_{l}$ with $0 \, \leq \, r,l \, \leq \, n-1$ and $r<l.$ Thus, $a_{r} \Rightarrow a_{l} = x(r)_{j_{r}}(n-l)$ that belongs to

$$ E_{n - l}^{j_r} = \left\{ \begin{array}{lll} \left\{ a_{j_r}\right\} & \text{if} & n - l < n - j_r \\ \left[ a_{n - (n - l)}\right) & \text{if} & n -l \ge n - j_r \\ \end{array} \right. . $$

As $r \,\leq \, j_{r}$ and $r < l,$ $a_{r} \wedge (a_{r} \Rightarrow a_{l}) = a_{r} = a_{r} \wedge a_{l}.$ Hence, $x \wedge (x \Rightarrow y) = x \wedge y.$ By Lemma 2.2, $L \models x \wedge (x \Rightarrow y) \approx x \wedge y.$

It is long but computational to prove that $L \models x \wedge (y \Rightarrow z) \approx x \wedge [(x \wedge y) \Rightarrow (x \wedge z)].$

By Lemma 2.3, $\Rightarrow$ is a semi-Heyting implication. $\square$

From the previous results, we have the following:

Theorem 2.10

Let$S_{n} = \{\to: L_{n}^{2} \to L_{n} | \langle L_{n}, \wedge, \vee, \to, 0, 1\rangle \in {{\mathcal{SH}}}\}.$There exists a bijective correspondence between$S_{n}$ and F.

Proof

We define $\alpha: S_{n} \to F$ as follows: $\alpha(\to) = (\alpha_{\to}(0), \alpha_{\to}(1), \ldots, \alpha_{\to}(n-2))$ for each $\to \in S_{n}.$ By Corollary 2.8, $\alpha(\to) \in F.$ By Lemma 2.9, $\alpha$ is onto.

Let us prove that $\alpha$ is injective. Let $\to_{1}, \to_{2} \in S_{n}$ such that $\alpha(\to_{1}) = \alpha(\to_{2}).$ By Lemma 2.1, if $a_{r} > a_{l}$ then $a_{r} \to_{1} a_{l} = a_{l} = a_{r} \to_{2} a_{l}.$ If $a_{r} = a_{l},$ $a_{r} \to_{1} a_{l} = 1 = a_{r} \to_{2} a_{l}.$ As $\alpha(\to_{1}) = \alpha(\to_{2}),$ $(\alpha_{\to_{1}}(0), \alpha_{\to_{1}}(1), \ldots, \alpha_{\to_{1}}(n-2)) = (\alpha_{\to_{2}}(0), \alpha_{\to_{2}}(1), \ldots, \alpha_{\to_{2}}(n-2)).$ Hence, $\alpha{\to_{1}}(i) = \alpha{\to_{2}}(i)$ for all i with $0 \, \leq \, i < n-1.$ Then $a_{i} \to_{1} 1 = a_{i} \to_{2} 1, a_{i} \to_{1} a_{n-2} = a_{i} \to_{2} a_{n-2}, \ldots, a_{i} \to_{1} a_{i+1} = a_{i} \to_{2} a_{i+1}$ for all i with $0 \, \leq \, i < n-1.$ Hence, $\to_{1} = \to_{2},$ and $\alpha$ is injective. $\square$

Our next objective is to determine the cardinal of the set F.

Lemma 2.11

$E_{a_{j}}^{a_{i}} \cap E_{a_{k}}^{a_{i}} = \emptyset$ with $j\not= k.$

Proof

Let $x \in E_{a_{j}}^{a_{i}} \cap E_{a_{k}}^{a_{i}}$ and suppose that $j < k.$ As $x \in E_{a_{j}}^{a_{i}}$ then $x = (x(1), x(2), \ldots, x(n-i-1)),$ with $x(m) \in E^{j}_{m}, 1 \, \leq \, m \, \leq \, n-i-1.$ As $x \in E_{a_{k}}^{a_{i}}$ then $x = (z(1), z(2), \ldots, z(n-i-1))$ with $z(m) \in E^{k}_{m}, 1 \, \leq \, m \, \leq \, n-i-1.$ Now, if $1 < n-j,$ $x(1) = a_{j}$ and if $1 \, \geq \, n-j,$ then $x(1) = 1.$ If $1 < n-k,$ $z(1) = a_{k}$ and if $1 \, \geq \, n-k,$ then $z(1) = 1.$ Moreover, as $j < k,$ $n-j> n-k.$ If $1 < n-k < n-j,$ $x(1) = a_{j}$ and $z(1) = a_{k}$ a contradiction since $x(1) = z(1) .$ The other cases are similar. Consequently, $E_{a_{j}}^{a_{i}} \cap E_{a_{k}}^{a_{i}} = \emptyset. \square$

Lemma 2.12

$\left| F \right| = \prod\limits_{i = 0}^{n - 2} {\left[ {1 + (n - i - 1)!\sum\limits_{j = i + 1}^{n - 1} \frac{1}{(n - j - 1)!}}\right]}$

Proof

By Lemma 2.11, $\left| F_i \right| = \sum\limits_{j = i}^{n - 1}\left| E_{a_j }^{a_i} \right|$ with $\left| {E_{a_j}^{a_i}} \right| = \left| {E_1^j } \right| \cdot \left| {E_2^j } \right| \cdots \left| {E_{n - i - 1}^j } \right|.$

$$ \left| {E_k^j} \right| = \left\{ \begin{array}{lll} 1 & \text{if} & k < n - j\\ n - 1 - (n - k) + 1 & \text{if} & k \ge n - j \\ \end{array} \right. = \left\{ \begin{array}{lll} 1 & \text{if} & k < n - j \\ k & \text{if} & k \ge n - j \\ \end{array} \right.. $$

Hence, $\left| {E_{a_j }^{a_i}} \right| = \left\{ \begin{array}{lll} (n - j) \cdot (n - j + 1) \cdots (n - i - 1) & \text{if} & j > i \\ 1 & \text{if} & j = i \\ \end{array}\right..$ So,

$$ \begin{aligned} \left| F_i \right| &= 1 + \sum\limits_{j = i + 1}^{n - 1}{(n - j) \cdot (n - j + 1) \cdots (n - i - 1)} = 1 + \sum\limits_{j = i + 1}^{n - 1} \frac{(n - i - 1)!}{(n - j - 1)!}\\ &= 1 + (n - i - 1)!\sum\limits_{j = i + 1}^{n - 1} \frac{1}{(n - j - 1)!}. \end{aligned} $$

Thus, $\left| F \right| = \prod\limits_{i = 0}^{n - 2}\left[ 1 + (n - i - 1)!\sum\limits_{j = i + 1}^{n - 1} \frac{1}{(n - j - 1)!} \right].$ $\square$

By Lemma 2.12 and Theorem 2.10, it follows immediately the next corollary:

Corollary 2.13

There are

$$ \prod\limits_{i = 0}^{n - 2} {\left[ {1 + (n - i - 1)!\sum\limits_{j = i + 1}^{n - 1} \frac{1}{(n - j - 1)!}} \right]} $$

non-isomorphic n-element semi-Heyting chains, for $n \, \geq \, 2.$

For $n = 2,3,4$ this formula gives 2, 10, and 160, respectively, which coincide with the numbers determined by Sankappanavar in [5]. For $n = 5,$ there are 10,400 non-isomorphic semi-Heyting chains with five elements.

3 Isomorphic subalgebras of a semi-Heyting chain

When one investigates the lattice of subvarieties of ${{\mathcal{CSH}}},$ it is important to characterize the subalgebras of a finite semi-Heyting chain and to study the inclusion relation between chains in ${{\mathcal{CSH}}}.$

In this section, we consider the following related problem, which will show the complexity of the general problem. Given an n-element chain L, we wish to know when an $(n+1)$-element semi-Heyting chain L′ contains a subalgebra isomorphic to L, and the number of semi-Heyting chains L′ satisfying this condition.

Consider the following example. Let ${{\mathbf{L}}} = \langle L, \wedge, \vee, \to , 0,1 \rangle$ be a 4-element semi-Heyting chain, $L : 0 < a < b < 1.$ We want to know the number of 5-element semi-Heyting chains L′ such that L is (isomorphic to) a subalgebra of L′. Let L′ be a 5-element semi-Heyting chain such that ${{\mathbf{L}}}\in {{\mathbb{IS}}}({{\mathbf{L}}}')$ and assume that $L' = L \cup \{c\}.$

Suppose first that $0 < a < c < b < 1.$ We have just to consider the elements $x \to c$ for $x < c$ and the elements $c \to y$ for $c < y.$

If $0 \to b \, \leq \, a,$ then $c \wedge (0 \to c) = c \wedge (0 \to b) = 0 \to b.$ Since L is a chain, $0 {\to}c =0 {\to}b.$

If $0 \to b \, \geq \, b,$ then $c \wedge (0 \to c) = c \wedge (0 \to b) = c.$ So, $0 \to c \, \geq \, c,$ i.e.,

$$ 0 \to c = 0 \to b \hbox{ if } 0 \to b \, \leq \, a \hbox{ and } 0 \to c \, \geq \, c \hbox{ if } 0 \to b \, \geq \, b. $$

Similarly, if $a \to b = a$ then $a \to c = a \to b,$ and if $a \to b \, \geq \, b$ then $a \to c \, \geq \, c,$ i.e.,

$$ a \to c = a \to b \hbox{ if } a \to b = a \hbox{ and } a \to c \, \geq \, c \hbox{ if } 0 \to b \, \geq \, b. $$

Besides, $c \to 1 \, \geq \, c$ and

$$ c \to b = c \to 1 \hbox{ if } c \to 1 = c \hbox{ and } c \to b \, \geq \, b \hbox{ if } c \to 1 \, \geq \, b. $$

So, we conclude that

$$ (c \to 1, c \to b) \in \left( \{c\} \times \{c\} \right) \cup \left( \{b\} \times [b) \right) \cup \left( \{1\} \times [b) \right). $$

In a similar way, we should consider the cases $0 < a < b < c < 1$ and $0 < c < a < b < 1.$

In general, let ${\bf L} = \langle L, \wedge, \vee, \to, 0, 1\rangle$ be an n-element semi-Heyting chain, $n\, \geq \, 3,$ with

$$ L: 0 = a_{0} < a_{1} < \cdots < a_{n-2} < a_{n-1} = 1. $$

For a given $0 \, \leq \, i \, \leq \, n-2 ,$ let $\langle L^{i}, \wedge, \vee, 0, 1\rangle$ be an $(n+1)$-element chain with $L^i = L \cup \{b_i\},$ $b_{i} \notin L,$ and

$$ L^{i}:0 = a_{0} < a_{1} < \cdots < a_{i}< b_{i} < a_{i+1} < \cdots < a_{n-1} = 1. $$

We want to find conditions on an implication $\to: L^{i} \times L^{i} \to L^{i}$ in order for ${\bf L}$ to be a subalgebra of ${\bf L}^{i} = \langle L^{i}, \wedge, \vee, \to, 0, 1\rangle$ and to determine the number of implication operations that satisfy those conditions.

Consider the following sets

• (a) $F_{j}^{k} = \left\{ \begin{array}{lll} \left\{ a_k \right\} & \text{if} & k < j \\ \left[ a_j \right) & \text{if} & k \ge j \\ \end{array} \right.$

• (b) $F_{k}^{i} = \left\{ a_k \right\} \times \prod\limits_{j = i + 1}^{n - 2} F_j^k$

• (c) $F_{0}^{i} = \left\{ b_i \right\} \times \prod\limits_{j = i + 1}^{n - 2}\left\{b_i\right\}$

• (d) $E_{j}^{i} = \left\{ \begin{array}{lll} \left\{ a_j \to a_{i + 1}\right\} & \text{if} & a_j \to a_{i + 1} \le a_i \\ \left[b_i \right) & \text{if} & a_j \to a_{i + 1} > a_i \\ \end{array} \right.$

• (e) $E^{i} = \prod\limits_{j = 0}^i E_j^i$

• (f) $G^{i} = E^i \times \left[\left(\bigcup\limits_{k = i + 1}^{n - 1} F_k^i\right) \cup F_0^i\right]$

Lemma 3.1

Let L and ${\bf L}^{i}$ be as defined earlier. Then

$$ ((a_{0} \to b_{i}, a_{1} \to b_{i}, \ldots, a_{i} \to b_{i}), (b_{i} \to 1, b_{i} \to a_{i+1}, b_{i} \to a_{i+2}, \ldots, b_{i} \to a_{n-2})) \in G^{i}. $$

Proof

For $0 \, \leq \, j \, \leq \, i,$ $a_{j} < a_{i+1},$ and then by Lemma 1.2, $a_{j} \to a_{i+1} \, \geq \, a_{j}.$ If $a_{j} \to a_{i+1} = a_{l}$ with $j \, \leq \, l \, \leq \, i,$ as $b_{i} > a_{l},$ by Lemma 2.5 $a_{j} \to b_{i} = a_{l} = a_{j} \to a_{i+1}.$ If $a_{j} \to a_{i+1} = a_{l}$ with $i+1 \, \leq \, l \, \leq \, n-1,$ by Lemma 2.5 $a_{j} \to b_{i} \, \geq \, b_{i}.$ Then $a_{j} \to b_{i} \in E_{j}^{i}.$ Consequently, $(a_{0} \to b_{i}, a_{1} \to b_{i}, \ldots, a_{i} \to b_{i}) \in E^{i}.$ Moreover, as $b_{i} < 1,$ by Lemma 1.2, $b_{i} \to 1 \, \geq \, b_{i}.$ Hence, $b_{i} \to 1 = b_{i}$ or $b_{i} \to 1 = a_{k}$ with $i+1 \, \leq \, k \, \leq \, n-1.$

Suppose that $b_{i} \to 1 = b_{i}.$ Consider $j$ with $i+1 \, \leq \, j \, \leq \, n-2.$ By Lemma 2.5, $b_{i} \to a_{j} = b_{i}.$ Then $( b_{i} \to 1, b_{i} \to a_{i+1}, \ldots, b_{i} \to a_{n-2}) \in F_{0}^{i}.$

If $b_{i} \to 1 = a_{k}$ with $i+1 \, \leq \, k \, \leq \, n-1,$ consider j with $i+1 \, \leq \, j \, \leq \, n-2.$ If $j \, \leq \, k,$ by Lemma 2.5, $b_{i} \to a_{j} \, \geq \, a_{j}.$ If $j > k,$ by Lemma 2.5, $b_{i} \to a_{j} =a_{k}.$ Then $( b_{i} \to 1, b_{i} \to a_{i+1}, \ldots, b_{i} \to a_{n-2}) \in F_{k}^{i}.$

Therefore, $( b_{i} \to 1, b_{i} \to a_{i+1}, \ldots, b_{i} \to a_{n-2}) \in \bigcup_{k=i+1}^{n-1} F_{k}^{i} \cup F_{0}^{i}.$ Thus, $((a_{0} \to b_{i}, a_{1} \to b_{i}, \ldots, a_{i} \to b_{i}), (b_{i} \to 1, b_{i} \to a_{i+1}, b_{i} \to a_{i+2}, \ldots, b_{i} \to a_{n-2})) \in G^{i}. \square$

Now we will construct an implication from a given element of the set $G^{i}.$

Consider now the set $G^{i}.$ Let $\alpha \in G^{i}.$ $\alpha = (\alpha_{1}, \alpha_{2})$ with $\alpha_{1} \in E^{i}$ and $\alpha_{2} \in \left( \bigcup\nolimits_{k = i + 1}^{n - 1} F_k^i\right) \cup F_0^i.$ As $\alpha_{1} \in E^{i},$ then $\alpha_{1} = (\alpha_{1}(0), \alpha_{1}(1), \ldots, \alpha_{1}(i))$ with $\alpha_{1}(j) \in E_{j}^{i}$ for every j, 0 ≤ j ≤ i. As $\alpha_{2} {\in}\left(\bigcup\nolimits_{k =i+1}^{n-1} F_k^i \right)\cup F_0^i,$ then $\alpha_{2} \in F^{i}_{k_{0}}$ for any $k_{0}$ with $i+1 \, \leq \, k_{0} \, \leq \, n-1$ ó $\alpha_{2} \in F_{0}^{i}.$ Hence, $\alpha_{2} = (\alpha_{2}(n-1), \alpha_{2}(i+1), \alpha_{2}(i+2), \ldots, \alpha_{2}(n-2)).$ If $\alpha_{2} \in F^{i}_{k_{0}}$ for any $k_{0}$ with $i+1 \, \leq \, k_{0} \, \leq \, n-1,$ $\alpha_{2}(n-1)=a_{k_{0}}$ and $\alpha_{2}(j) \in F_{j}^{k_{0}}$ with $i+1 \, \leq \, j \, \leq \, n-2.$ If $\alpha_{2} \in F_{0}^{i},$ $\alpha_{2}(n-1) = b_{i}$ and $\alpha_{2}(j) = b_{i}$ with $i+1 \, \leq \, j \, \leq \, n-2.$ In $L^{i}$ we define an operation $\Rightarrow$ as:

$$ x \Rightarrow y = \left\{ \begin{array}{lllll} x \to y & \text{if} & x,y \in L & & \\ 1 & \hbox{if} & x = y & &\\ y & \hbox{if} & (x,y) = (a_j ,b_i) & \hbox{with} & i + 1 \le j \le n - 1\\ y & \hbox{if} & (x,y) = (b_i ,a_j) & \hbox{with} & 0 \le j \le i\\ \alpha_1 (j) & \hbox{if} & (x,y) = (a_j , b_i) & \hbox{with} & 0 \le j \le i\\ \alpha_2 (j) & \hbox{if} & (x,y) = (b_i , a_j) & \hbox{with} & i + 1 \le j \le n - 1\\ \end{array} \right. $$

Lemma 3.2

Let${\bf L}^{i} = \langle L^{i}, \wedge, \vee, \Rightarrow, 0, 1\rangle .$Then${\bf L}^{i} \in {{\mathcal{SH}}}$and, consequently, ${\bf L}$is a subalgebra of${\bf L}^{i}.$

Proof

Clearly, ${\bf L}^{i} \models x \Rightarrow x \approx 1.$

We will see that ${\bf L}^{i} \models x \wedge (x \Rightarrow y) \approx x \wedge y.$ Let $a , b \in L^{i}$ with $a < b.$

If $a, b \in L,$ then $a \wedge (a \Rightarrow b) = a \wedge (a \to b) = a \wedge b.$

Suppose that $a = b_{i},$ $b = a_{r}$ with $i+1 \, \leq \, r \, \leq \, n-1$ and $\alpha_{2} \in F_{k_{0}}^{i}$ with $i+1 \, \leq \, k_{0} \, \leq \, n-1.$ Then $b_{i} \wedge (b_{i} \Rightarrow a_{r}) = b_{i} \wedge \alpha_{2}(r).$ If $r=n-1,$ $b_{i} \wedge (b_{i} \Rightarrow 1) = b_{i} \wedge \alpha_{2}(n-1) = b_{i} \wedge a_{k_{0}} = b_{i} = b_{i} \wedge 1.$ If $r < n-1,$ $b_i \Rightarrow a_r = \left\{ \begin{array}{lllll} a_{k_0} & \text{if} & k_0 < r\\ x & \text{if} & k_0 \ge r & \text{with} & x \ge a_r \\ \end{array} \right..$

Consequently, $b_i \wedge \left({b_i \Rightarrow a_r}\right)= \left\{ \begin{array}{lll} b_i & \text{if} & k_0 < r \\ b_i & \text{if} & k_0 \ge r \\ \end{array} \right. = b_i \wedge a_r$

Suppose now that $a = b_{i},$ $b = a_{r}$ with $i+1 \, \leq \, r \, \leq \, n-1$ and $\alpha_{2} \in F_{0}^{i}.$ In this case $b_{i} \wedge (b_{i} \Rightarrow a_{r}) = b_{i} \wedge \alpha_{2}(r) = b_{i} \wedge b_{i}=b_{i}=b_{i} \wedge a_{r}.$

Finally, if $a = b_{i}$ and $b = a_{r}$ with $0 \, \leq \, r \, \leq \, i.$ $a_{r} \wedge (a_{r} \Rightarrow b_{i}) = a_{r} \wedge \alpha_{1}(r).$ Thus,

$$ \alpha_1 (r) = \left\{ \begin{array}{lllll} a_r \to a_{i + 1} & \text{if} & a_r \to a_{i + 1} \le a_i & &\\ x & \text{if} & a_r \to a_{i + 1}> a_i & \text{with} & x \ge \mathop b\nolimits_i\\ \end{array} \right., $$

so,

$$ a_r\wedge \alpha_1 (r) = \left\{ \begin{array}{lllll} a_r \wedge (a_r \to a_{i + 1}) & \text{if} & a_r \to a_{i + 1} \le a_i & & \\ a_r \wedge x & \text{if} & a_r \to a_{i + 1} > a_i & \text{with} & x \ge b_i \\ \end{array} \right.. $$

Hence, $a_{r} \wedge (a_{r} \Rightarrow b_{i}) = a_{r} \wedge \alpha_{1}(r)=a_{r} = a_{r} \wedge b_{i}.$

In a similar way, it can be proved that ${\bf L}^i \models x \wedge (y \Rightarrow z) \approx x \wedge [(x \wedge y) \Rightarrow (x \wedge z)].$

By Lemma 2.3, ${\bf L}^{i}_{\to} \in\ {{\mathcal{SH}}}. \square$

Remark 3.3

From the previous lemma, it follows that for every n-element semi-Heyting chain L there exists an (n + 1)-element semi-Heyting chain L′ such that L is a subalgebra of L′.

From the previous results, we can establish the following correspondence:

Theorem 3.4

Let $S_{i}$ be the set of operations $\to : L^{i} \times L^{i} \to L^{i}$ such that ${\bf L}^i = \langle L^{i}, \wedge, \vee, \to, 0, 1\rangle \in {{\mathcal{SH}}}$ and L is a subalgebra of ${\bf L}^i.$ Then there exists a bijective correspondence between $S_{i}$ and $G^{i}.$

Proof

We define $\alpha: S_{i} \to G^{i}$ as $\alpha(\to) = ((a_{0} \to b_{i}, a_{1} \to b_{i}, \ldots, a_{i} \to b_{i}), (b_{i} \to 1, b_{i} \to a_{i+1}, b_{i} \to a_{i+2}, \ldots, b_{i} \to a_{n-2})).$ By Lemmas 3.1 and 3.2, $\alpha$ is well defined, and it is onto. The injectivity is left to the reader. $\square$

Now we want to determine the cardinal of the set $G^{i}.$

Lemma 3.5

Let $i+1 \, \leq \, k,k' \, \leq \, n-1$ and $0 \, \leq \, i \, \leq \, n-2.$ Then $F_{k}^{i} \cap F_{k'}^{i} = \emptyset$ if $k \not= k'.$

Proof

Let $\alpha \in F_{k}^{i} \cap F_{k'}^{i}$ and suppose that $k < k'.$ As $\alpha \in F_{k}^{i}, \alpha = (\alpha_{1}, \alpha_{i+1}, \alpha_{i+2}, \ldots, \alpha_{n-2})$ with $\alpha_{1} = a_{k}$ and $\alpha_{j} \in F_{j}^{k}$ with $i+1 \, \leq \, j \, \leq \, n-2.$ As $\alpha \in F_{k'}^{i}, \alpha = (\alpha_{1}, \alpha_{i+1}, \alpha_{i+2}, \ldots, \alpha_{n-2})$ with $\alpha_{1} = a_{k'}$ and $\alpha_{j} \in F_{j}^{k'}$ with $i+1 \, \leq \, j \, \leq \, n-2.$ Hence, $a_{k} = a_{k'}.$ Then $k=k'$ a contradiction. $\square$

Lemma 3.6

$$ \left| G^i \right| = \prod\limits_{j = 0}^i A_j^i \left( \sum\limits_{k = i + 1}^{n - 2} \frac{(n - (i + 1) - 1)!}{(n - (i + 1) - (k - (i + 1) + 2))!} + (n - (i + 1) - 1)! + 1 \right), $$

where

$$ A_j^i = \left\{ \begin{array}{lll} 1 & \text{if} & a_j \to a_{i + 1} \le a_i \\ n - i & \text{if} & a_j \to a_{i + 1} > a_i \\ \end{array} \right. . $$

Proof

We have that $F_{j}^{k} = \left\{ \begin{array}{lll} \left\{a_k\right\} & \text{if} & k < j\\ \left[a_j \right) & \text{if} & k \ge j\\ \end{array} \right.$ and then

$$ \left| F_j^k \right| = \left\{ \begin{array}{lll} 1 & \text{if} & k < j\\ n - 2 - j + 1 & \text{if} & k \ge j\\ \end{array} \right. = \left\{ \begin{array}{lll} 1 & \text{if} & k < j\\ n - j - 1 & \text{if} & k \ge j\\ \end{array} \right. $$

Hence, for $k \not= n-1$ ,

$$ \prod\limits_{j = i + 1}^{n - 2}\left| F_j^k \right| = \frac{(n - (i + 1) - 1)!}{(n - (i + 1) - (k - (i + 1) + 2))!}. $$

If $k=n-1,$ $\prod\nolimits_{j = i + 1}^{n - 2} \left| F_j^k\right| = (n - (i + 1) - 1)!.$

Besides, as

$$ E_{j}^{i} = \left\{ \begin{array}{lll} \left\{ a_j \to a_{i + 1} \right\} & \text{if} & a_j \to a_{i + 1} \le a_i \\ \left[b_i \right) & \text{if} & a_j \to a_{i + 1} > a_i \\ \end{array} \right., $$

then $| E_{j}^{i} | = \left\{ \begin{array}{lll} 1 & \text{if} & a_j \to a_{i + 1} \le a_i \\ |\left[b_i \right)| & \text{if} & a_j \to a_{i + 1} > a_i \\ \end{array} \right.$ with $|[b_{i})| = n-1-(i+1)+2=n-1-i-1+2=n-i.$

Let

$$ A_{j}^{i} = \left\{ \begin{array}{lll} 1& \text{if} & a_j \to a_{i + 1} \le a_i\\ n-i & \text{if} & a_j \to a_{i + 1} > a_i\\ \end{array} \right.. $$

Then $G^{i} = E^i \times \left[\left( \bigcup\nolimits_{k = i + 1}^{n - 1}F_k^i \right) \cup F_0^i \right],$ by Lemma 3.5

$$ \left| G^i \right| = \prod\limits_{j = 0}^i A_j^i \left(\sum\limits_{k = i + 1}^{n - 2} \frac{(n - (i + 1) - 1)!}{(n - (i + 1)-(k-(i + 1) + 2))!}+(n-(i+1)-1)!+1\right). $$

$\square$

From Lemma 3.6 and Theorem 3.4 the next corollary follows.

Corollary 3.7

The number of non-isomorphic algebras${\bf L}^{i}$is given by the number:

$$ \prod\limits_{j = 0}^i A_j^i \left( \sum\limits_{k = i + 1}^{n - 2}{\frac{(n - (i + 1) - 1)!}{(n - (i + 1) - (k - (i + 1) + 2))!}}+ (n - (i + 1) - 1)! + 1 \right) $$

where

$$ A_j^i = \left\{ \begin{array}{lll} 1 & \text{if} & a_j \to a_{i + 1} \le a_i \\ n - i & \text{if} & a_j \to a_{i + 1} > a_i \\ \end{array} \right.. $$

Corollary 3.8

The number of non-isomorphic$(n+1)$-element semi-Heyting chains${\bf L}^{i}$such that${\bf L}$is a subalgebra of${\bf L}^{i}$is given by

$$ \sum\limits_{i = 0}^{n - 2} \left[\prod\limits_{j = 0}^i A_j^i \left(\sum\limits_{k = i + 1}^{n - 2}\frac{(n - (i + 1) - 1)!}{(n - (i + 1) - (k - (i + 1) + 2))!} + (n - (i + 1) - 1)! + 1 \right)\right] $$

where

$$ A_j^i = \left\{ \begin{array}{lll} 1 & \text{if} & a_j \to a_{i + 1} \le a_i\\ n - i & \text{if} & a_j \to a_{i + 1} > a_i \\ \end{array} \right. $$

It remains to consider the case $n=2.$

Let ${\bf 2}$ and ${{\mathbf{\overline{2}}}}$ denote the two-element semi-Heyting chains whose operation $\to$ satisfies $0 \to 1 = 1$ and $0 \to 1 = 0,$ respectively. It is easy to see that ${\bf 2}$ is a Heyting algebra (which is also a Boolean algebra), while ${{\mathbf{\overline{2}}}}$ is not.

Let ${\bf L}$ be either ${\bf 2}$ or ${{\mathbf{\overline{2}}}}.$ Let ${{\mathbf{L}}}'=\langle L', \wedge, \vee, 0, 1 \rangle$ be a chain with $L': 0 < b < 1$ and $b \notin L.$ If ${\bf L}$ is a subalgebra of ${\bf L}',$ then we have just to determine the elements $0 \to b$ and $b \to 1.$ From Lemma 2.5, if $0 \to 1 = 0$ then $0 \to b = 0$ and if $0 \to 1 = 1$ then $0 \to b \, \geq \, b.$ In addition, $b \to 1 \, \geq \, b.$

So we have

Corollary 3.9

There are two non-isomorphic$3$-element semi-Heyting chains that contain${\bf 2}$as a subalgebra and$\text{four}$non-isomorphic$3$-element semi-Heyting chains that contain${{\mathbf{\overline{2}}}}$as a subalgebra.

Theorem 3.10

Let$n \, \geq \, 3.$There is an$(n+1)$-element semi-Heyting chain that does not have an n-element subalgebra.

Proof

Let $L': b_{0} < b_{1} < \cdots < b_{n-1} < b_{n}.$ We define $\to: L' \times L' \to L'$ by means of

$$ b_i \to b_j = \left\{ \begin{array}{lllll} b_{i + 1} & \text{if} & i < j & &\\ 1& \text{if} & i = j & & \\ b_j & \text{if} & i > j& \text{with} & 0 \le i,j \le n\\ \end{array} \right. $$

It is easy to prove that $\to$ is a semi-Heyting implication.

Suppose that there exists a subalgebra ${\bf L}$ of ${\bf L}'$ and $|{\bf L}| = n.$ Then there exists $0 < k < n$ such that $L = L' \setminus \{b_{k}\}.$ Now, $b_{k} = b_{k-1} \to b_{k+1},$ and then $b_k \in L,$ a contradiction. $\square$

4 Equational basis for ${{\mathcal{CSH}}}$

In this section, we give equational bases for the variety ${{\mathcal{CSH}}}$ and some of its subvarieties.

Lemma 4.1

Let L be a semi-Heyting chain. Then L satisfies the following identity

$$ ((x \vee (x \rightarrow y)) \rightarrow (x \rightarrow y)) \vee(y \rightarrow (x \wedge y)) \approx 1\quad {\rm (Ch)} $$

Proof

Let $a, b \in L.$ As L is a chain, $a \, \leq \, b$ or $b < a.$ If $a \, \leq \, b,$ by Lemma 1.2, $a \, \leq \, a \to b.$ Hence, $a \vee (a \to b)= a \to b,$ so $(a \vee (a \to b)) \to (a \to b) = (a \to b) \to (a \to b) = 1.$ If $b < a,$ $b = b \wedge a,$ and then $b \to (a \wedge b) = b \to b = 1.$ $\square$

Lemma 4.2

Let${\mathbb{V}}$be the subvariety of${{\mathcal{SH}}}$defined by (Ch). If${\bf L} \in {\mathbb{V}}$is subdirectly irreducible, then${\bf L}$is a chain.

Proof

Let ${\bf L} \in {\mathbb{V}}$ subdirectly irreducible and let $a, b \in L.$ Since L satisfies (Ch), $((a \vee (a \rightarrow b)) \rightarrow (a \rightarrow b)) \vee (b \rightarrow (a \wedge b)) = 1.$ As L is subdirectly irreducible, 1 is $\vee$-irreducible. Thus, $(a \vee (a \rightarrow b)) \rightarrow (a \rightarrow b) = 1$ or $b \rightarrow (a \wedge b) = 1.$

Suppose that $(a \vee (a \rightarrow b)) \rightarrow (a \rightarrow b) = 1.$ Then $a \vee (a \rightarrow b) \, \leq \, a \to b,$ and thus, $a \, \leq \, a \vee (a \rightarrow b) \, \leq \, a \to b.$ Hence, $a \wedge b = a \wedge (a \to b) = a,$ so $a \, \leq \, b.$

If $b \rightarrow (a \wedge b) = 1,$ then $b \, \leq \, a\wedge b,$ and thus, $b \, \leq \, a.$

Hence, ${\bf L}$ is a chain. $\square$

From Lemmas 4.1 and 4.2, we have the following:

Theorem 4.3

An equational basis for ${{\mathcal{CSH}}}$ relative to ${{\mathcal{SH}}}$ is given by

$$ ((x \vee (x \rightarrow y)) \rightarrow (x \rightarrow y)) \vee (y \rightarrow (x \wedge y)) \approx 1\quad {\rm(Ch)}. $$

Let ${{\mathcal{C}}}_{n}$ denote the subvariety of ${{\mathcal{SH}}}$ generated by all the $n$-element chains, $n \, \geq \, 2.$

It is easily seen that the following theorem holds.

Theorem 4.4

An equational basis for ${{\mathcal{C}}}_{2}$ is given by

$$ ((x \vee (x \rightarrow y)) \rightarrow (x \rightarrow y)) \vee (y \rightarrow (x \wedge y)) \approx 1\quad {\rm (Ch)} $$

and

$$ x \vee x^{*} \approx 1. $$

Observe that ${{\mathcal{C}}}_{2}$ is the subvariety generated by the algebras 2 and ${{\mathbf{\overline{2}}}},$ which have the 2-element chain as their lattice reduct and whose operation $\to$ satisfies $0 \to 1 = 1$ and $0 \to 1 = 0,$ respectively.

Theorem 4.5

An equational basis for ${{\mathcal{C}}}_{n}$ with $n \, \geq \, 3$ is given by the identities

$$ ((x \vee (x \rightarrow y)) \rightarrow (x \rightarrow y)) \vee (y \rightarrow (x \wedge y)) \approx 1\quad {\rm (Ch)} $$

and

$$ \bigvee_{i=1}^{n-1}(x_{i} \vee x_{i}^{*}) \vee \bigvee_{j=1;j < i}^{n-1} (x_{i} \rightarrow x_{j}) \approx 1 \quad {\rm (H_{n})} $$

Proof

Let ${\bf L}$ be an $n$-element semi-Heyting chain, $L: 0 < a_{1} < a_{2} < \cdots < a_{n-2} < 1.$ By Theorem 4.3, ${\bf L}$ satisfies (Ch).

Let us prove that L satisfies ${\rm (H_n)}.$ Let $z_{1}, z_{2}, \ldots, z_{n-1} \in L.$ If $z_{k} \in \{0,1\}$ for some k, $1 \, \leq \, k \, \leq \, n-1,$ then $z_{k} \vee z_{k}^{*} = 1.$ Suppose that $z_{k} \not\in \{0,1\}$ for every $k,$ $1 \, \leq \, k \, \leq \, n-1,$ i.e., $z_{k} \in \{a_{1}, a_{2}, \ldots, a_{n-2}\}$ for every $k.$ Then there exists $j < i$ such that $z_{i} = z_{j},$ and so $z_{i} \to z_{j} = 1.$ Hence, L satisfies ${\rm (H_n)}.$

Let ${\mathbb{V}}$ be the subvariety of ${{\mathcal{SH}}}$ defined by ${\rm (Ch)}$ and ${\rm (H_n)}$ and consider a subdirectly irreducible algebra ${{\mathbf{L}}} \in {\mathbb{V}}.$ By Theorem 4.3, ${\bf L} \in {{\mathcal{CSH}}},$ and by Lemma 4.2, $L$ is a chain. Suppose that exists $a_{1}, a_{2}, \ldots, a_{n-2}, a_{n-1} \in L$ such that $0 < a_{1} < a_{2} < \cdots < a_{n-2} < a_{n-1} < 1.$ Then $\bigvee_{i=1}^{n-1} \left( a_{i} \vee a_{i}^{*} \right) = \bigvee_{i=1}^{n-1} \left( a_{i} \vee 0 \right) = a_{n-1}.$ By hypothesis, $a_{n-1} \vee \bigvee_{i,j=1;j < i}^{n-1} \left( a_{i} \to a_{j} \right) = 1,$ and as $1$ is $\vee$-irreducible, $a_{i} \to a_{j} = 1$ for some $j < i.$ Hence, $a_{i} \, \leq \, a_{j},$ a contradiction. Thus, $|L| \, \leq \, n,$ and consequently ${\bf L} \in {{\mathcal{C}}}_{n}.$ $\square$

As an immediate corollary of Theorem 4.3 we can determine equational bases for the following subvarieties of ${{\mathcal{CSH}}}$ introduced in [5]: ${{\mathcal{CFTT}}} (0 \rightarrow 1 \approx 1), {{\mathcal{CFTD}}} ((0 \rightarrow 1)^{*} \approx 0),$ quasi-Heyting chains $(y \, \leq \, x \rightarrow y),$ Heyting chains $((x \wedge y) \rightarrow x \approx 1), {{\mathcal{CFTF}}} (0 \rightarrow 1 \approx 0)$ and conmutative semi-Heyting chains $(x \rightarrow y \approx y \rightarrow x).$