Traces of Ternary Relations Based on Bandler–Kohout Compositions

Abstract

Recently, we have introduced and studied all possible four-point compositions (one degree of freedom) and five-point compositions (two degrees of freedom) of ternary relations in analogy with the usual composition of binary relations. In this paper, we introduce and study new types of compositions of ternary relations inspired by the compositions of binary relations introduced by Bandler and Kohout (BK-compositions, for short). Moreover, we pay particular attention to the link between BK-compositions and the traces of binary relations and use it as source of inspiration to introduce traces of ternary relations. Moreover, we show that these new notions of BK-compositions and traces are useful tools to solve some relational equations in an unknown ternary relation.

1. Introduction

The calculus of (binary) relations was initiated in the late eighteenth century by Peirce [1] and was further developed by Shröder [2]. At the core of this calculus is the basic operation called ‘composition’. Surprisingly, only a century after the conception of the relational calculus, two additional relational compositions were introduced by Bandler and Kohout (referred to as BK-compositions from here on), resulting from the replacement of the underlying existential quantifier with the existential quantifier and logical conjunction with logical implication [3,4] (or, in set-theoretic terms, replacing non-empty intersection with inclusion). After initially attracting a lot of interest from various fields of application, including medical diagnosis [5,6] and decision making [7,8,9], these new compositions also caught the attention of a variety of mathematicians and led to further modifications and generalizations in the context of L-fuzzy sets [10,11,12,13]. A particularly interesting use of these BK-compositions is that they allow the expression of the greatest solution of relational equations (a generalization of Boolean lattice equations [14]) in an elegant manner (for more information, see [11,15,16,17]).

On a rather specific topic, Doignon et al. [18] associated two specific binary relations with a given binary (fuzzy) relation called ‘left and right traces’ for the purpose of characterizing (fuzzy) biorder relations. Fodor [19] redefined the traces of a binary fuzzy relation as fuzzy relations and demonstrated their usefulness in characterizing the basic properties of binary fuzzy relations. Several authors followed the idea of characterizing the properties of a binary relation through the properties of its traces, e.g., in the theory of conjoint measurement [20] and in the context of fuzzy relations [21,22]. Note that the traces of a binary relation can be formulated more concisely as the BK-compositions of the relation with itself.

In contrast to binary relations, ternary relations have received far less attention, and the attention they have received has been mainly over the last decades. Even the basic notion of ‘composition’ had not been consolidated, with only isolated proposals arising in different contexts [23,24,25]. Only recently the topic received a holistic treatment, leading to the identification of all possible four-point and five-point compositions [26]. The same applies to traces, with Zedam et al. [27] generalizing the notions of left and right traces of a binary relation to the left, middle, and right traces of a ternary relation. In this initial approach, the traces associated with a ternary relation were defined as binary relations and were used to study several properties of ternary relations.

With the general aim of expanding the knowledge on ternary relations, we unfold a similar path of reasoning in this paper. Having identified all compositions of ternary relations in our previous work, we can easily generalize the BK-compositions to ternary relations as well. In turn, we can introduce the corresponding traces and again identify left, middle, and right traces of a ternary relation yet this time as genuine ternary relations. We demonstrate their usefulness in the study and characterization of certain properties of ternary relations.

This paper is organized as follows. In Section 2, we recall the necessary basic concepts and properties of binary and ternary relations. After recalling the notions of BK-compositions of binary relations, we introduce the BK-compositions of ternary relations in Section 3. In Section 4, we explore some interesting links between the BK-compositions of binary relations and the BK-compositions of ternary relations. In Section 5, we study the interaction between the usual compositions and the BK-compositions of ternary relations. In Section 6, we recall the notions of left and right traces of a binary relation and introduce the left, middle, and right traces of a ternary relation. We end this section by characterizing the main properties of a ternary relation in terms of its traces. Finally, we present some concluding remarks in Section 7.

2. Preliminaries on Binary and Ternary Relations

In this section, we recall some basic notions that will be needed further on. Throughout this paper, X represents a non-empty universe. An n-ary relation on X, with $n\in \mathbb{N}$, is a subset of $X^n$; if $n=2$, then we talk about a binary relation, while if $n=3$, then we talk about a ternary relation.

2.1. Binary Relations

We recall some basic definitions and properties of binary relations. For more details, we refer to [28,29,30]. A binary relation R on X is said to be:

(i)

Reflexive if, for any $x\in X$, it holds that $(x,x)\in R$;

(ii)

Symmetric if, for any $x,y\in X$, it holds that $(x,y)\in R$ implies $(y,x)\in R$;

(iii)

Transitive if, for any $x,y,z\in X$, it holds that $(x,y)\in R\wedge (y,z)\in R$ implies $(x,z)\in R$.

The composition of two binary relations R and S on X is defined as [1]:

$$R\circ S=\{(x,z)\in X^2\mid (\exists t\in X)((x,t)\in R\wedge (t,z)\in S)\}.$$

Note that a binary relation R is transitive if and only if $R\circ R\subseteq R$. One could imagine alternative definitions of the composition of binary relations:

$$\begin{array}{ccc}\hfill R{\circ }_{1}S& =& \{(x,z)\in X^2\mid (\exists t\in X)((t,x)\in R\wedge (t,z)\in S)\};\hfill \\ \hfill R{\circ }_{2}S& =& \{(x,z)\in X^2\mid (\exists t\in X)((x,t)\in R\wedge (z,t)\in S)\};\hfill \\ \hfill R{\circ }_{3}S& =& \{(x,z)\in X^2\mid (\exists t\in X)((t,x)\in R\wedge (z,t)\in S)\};\hfill \\ \hfill R{\circ }_{4}S& =& \{(x,z)\in X^2\mid (\exists t\in X)((z,t)\in R\wedge (t,x)\in S)\};\hfill \\ \hfill R{\circ }_{5}S& =& \{(x,z)\in X^2\mid (\exists t\in X)((t,z)\in R\wedge (t,x)\in S)\};\hfill \\ \hfill R{\circ }_{6}S& =& \{(x,z)\in X^2\mid (\exists t\in X)((z,t)\in R\wedge (x,t)\in S)\};\hfill \\ \hfill R{\circ }_{7}S& =& \{(x,z)\in X^2\mid (\exists t\in X)((t,z)\in R\wedge (x,t)\in S)\}.\hfill \end{array}$$

As all of these compositions link two 2-tuples while allowing for one degree of freedom, we refer to them as three-point compositions.

Consider the two 2-permutations mapping any 2-tuple as follows: ${\rho }_0(u,v)=(u,v)$ and ${\rho }_1(u,v)=(v,u)$, then any of the above three-point compositions is determined by three 2-permutations ${\rho }_i,{\rho }_j,{\rho }_k$, as explained next. First of all, let us fix two 2-permutations ${\rho }_i$ and ${\rho }_j$. If we say that a 2-tuple $(x,z)\in X^2$ belongs to some composition of two binary relations R and S on X if there exists an element $t\in X$ such that ${\rho }_i(x,t)\in R$ and ${\rho }_j(z,t)\in S$, then this allows to retrieve the first four compositions above. If, additionally, we allow it to permute the 2-tuple $(x,z)$, then we can also retrieve the last four compositions (after a proper renaming of variables). This view allows the development of the following enumeration scheme. For any $q\in \{0,\dots ,7\}$, with ${\circ }_0:=\circ$ the basic composition, the composition $R{\circ }_{q}S$ can be written as:

$$R{\circ }_{q}S=\{{\rho }_k(x,z)\in X^2\mid (\exists t\in X)({\rho }_i(x,t)\in R\wedge {\rho }_j(t,z)\in S)\},$$

(1)

with $q={\left(kji\right)}_2=4k+2j+i$ and $i,j,k\in \{0,1\}$.

For a binary relation R and a 2-permutation $\rho$, the binary relation $R^{\rho }$ is defined as $R^{\rho }=\{\rho (x,y)\in X^2\mid (x,y)\in R\}$; in particular, the transpose $R^t$ of R corresponds to $R^{{\rho }_1}$. We can express the compositions ${\circ }_q$, $q\in \{1,\dots ,7\}$ in terms of the basic composition ${\circ }_0$ as follows:

$$R{\circ }_{q}S={\left(R^{{\rho }_i}{\circ }_0{S}^{{\rho }_j}\right)}^{{\rho }_k}.$$

(2)

Note that the composition ${\circ }_q$, with $q={\left(kji\right)}_2$, and the composition ${\circ }_{q^{\prime }}$, with $q^{\prime }=7-{\left(\overline{k}\overline{i}\overline{j}\right)}_2$, $\overline{0}=1$, and $\overline{1}=0$, are linked as follows. For any two binary relations R and S on X, it holds that

$$R{\circ }_{q}S=S{\circ }_{q^{\prime }}R.$$

2.2. Ternary Relations

We recall some basic definitions and properties of ternary relations. For more details, we refer to [23,24,31]. A ternary relation T on X is said to be:

(i)

Weakly reflexive if, for any x in X, it holds that $(x,x,x)\in T$;

(ii)

Left reflexive if, for any $x,y$ in X, it holds that $(y,x,x)\in T$;

(iii)

Middle reflexive if, for any $x,y$ in X, it holds that $(x,y,x)\in T$;

(iv)

Right reflexive if, for any $x,y$ in X, it holds that $(x,x,y)\in T$;

(v)

Strongly reflexive if, for any $x,y,z$ in X such that $\#\{x,y,z\}\le 2$, it holds that $(x,y,z)\in T$.

Next, we introduce the notion of symmetry of ternary relations by considering the six 3-permutations listed according to the lexicographical order, mapping any 3-tuple $(u,v,w)$ as follows:

$$\begin{array}{lll}{\sigma }_0(u,v,w)=(u,v,w)\hspace{1em}& {\sigma }_1(u,v,w)=(u,w,v)\hspace{1em}& {\sigma }_2(u,v,w)=(v,u,w)\\ {\sigma }_3(u,v,w)=(v,w,u)\hspace{1em}& {\sigma }_4(u,v,w)=(w,u,v)\hspace{1em}& {\sigma }_5(u,v,w)=(w,v,u).\end{array}$$

For a ternary relation T and a 3-permutation $\sigma$, the ternary relation $T^{\sigma }$ is defined as $T^{\sigma }=\{\sigma (x,y,z)\in X^3\mid (x,y,z)\in T\}$. A ternary relation T on X is said to be:

(i)

Left symmetric if $T=T^{{\sigma }_1}$;

(ii)

Middle symmetric if $T=T^{{\sigma }_5}$;

(iii)

Right symmetric if $T=T^{{\sigma }_2}$.

For more details on ternary relations, we refer to [23,24,27].

2.3. Compositions of Ternary Relations

In [26], we introduced two types of compositions of ternary relations, called four-point compositions and five-point compositions.

Definition 1 

([26]). Let $p\in \{0,\dots ,215\}$ with $p={\left(kji\right)}_6=36k+6j+i$ and $i,j,k\in \{0,\dots ,5\}$. For any two ternary relations S and T on X, the compositions $S{☐}_p^{0}T$, $S{☐}_p^{1}T$ and $S{☐}_p^{2}T$ are defined as:

$$\begin{array}{ccc}\hfill S{☐}_p^{0}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\exists t\in X)({\sigma }_i(x,y,t)\in S\wedge {\sigma }_j(x,t,z)\in T)\};\hfill \\ \hfill S{☐}_p^{1}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\exists t\in X)({\sigma }_i(x,y,t)\in S\wedge {\sigma }_j(z,t,z)\in T)\};\hfill \\ \hfill S{☐}_p^{2}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\exists t\in X)({\sigma }_i(y,y,t)\in S\wedge {\sigma }_j(x,t,z)\in T)\}.\hfill \end{array}$$

Definition 2 

([26]). Let $p\in \{0,\dots ,215\}$ with $p={\left(kji\right)}_6=36k+6j+i$ and $i,j,k\in \{0,\dots ,5\}$. For any two ternary relations S and T on X, the composition $S{⬠}_{p}T$ is defined as:

$$S{⬠}_{p}T=\{{\sigma }_k(x,y,z)\in X^3\mid (\exists (s,t)\in X^2)({\sigma }_i(\widehat{x},y,t)\in S\wedge {\sigma }_j(\check{x},t,z)\in T)\},$$

with

$$\widehat{x}=\left\{\begin{array}{cc}x\hfill & ,\mathrm{if}k\in \{0,3,4\}\hfill \\ s\hfill & ,\mathrm{if}k\in \{1,2,5\}\hfill \end{array}\right.,\check{x}=\left\{\begin{array}{cc}s\hfill & ,\mathrm{if}k\in \{0,3,4\}\hfill \\ x\hfill & ,\mathrm{if}k\in \{1,2,5\}\hfill \end{array}\right..$$

We proved in [26] that none of the compositions ${☐}_p^1$ and ${☐}_p^2$ are associative, while the composition ${☐}_p^0$ is associative if and only if $p\in \{0,43,86,129,172,215\}$, and the composition ${⬠}_p$ is associative if and only if $p\in \{0,12,43,46,86,87,117,129,172,178,210,215\}$.

In order to focus our attention and as the case of five-point compositions has already been partially studied in [27], we restrict to the four-point compositions in the remainder of this work.

For further use, we recall the following result.

Proposition 1. 

Let $p={\left(kji\right)}_6\in \{0,\dots ,215\}$ and $r\in \{0,1,2\}$. For any two ternary relations S and T on X, the four-point composition $S{☐}_p^{r}T$ can be written in terms of the composition ${☐}_0^r$ as follows:

$$S{☐}_p^{r}T={\left(S^{{\sigma }_i^{-1}}{☐}_0^r{T}^{{\sigma }_j^{-1}}\right)}^{{\sigma }_k}.$$

3. Bandler–Kohout Compositions of Ternary Relations

In this section, we introduce three new types of compositions of ternary relations inspired by the sub-composition, super-composition, and square-composition of binary relations proposed by Bandler and Kohout [3,4,10,11], which we will briefly refer to as BK-compositions.

3.1. Definition of BK-Compositions of Ternary Relations

We first recall the BK-compositions of binary relations.

Definition 3 

([3]). The sub-composition $R{\displaystyle ◁}S$, super-composition $R{\displaystyle ▷}S$ and square-composition $R\diamond S$ of two binary relations R and S on X are defined as:

$$\begin{array}{cc}\hfill R{\displaystyle ◁}S& =\{(x,z)\in X^2\mid (\forall y\in X)((x,y)\in R\Rightarrow (y,z)\in S)\};\\ \hfill R{\displaystyle ▷}S& =\{(x,z)\in X^2\mid (\forall y\in X)((x,y)\in R\Leftarrow (y,z)\in S)\};\\ \hfill R\diamond S& =\{(x,z)\in X^2\mid (\forall y\in X)((x,y)\in R\iff (y,z)\in S)\}.\end{array}$$

Note that slight modifications of these notions (essentially differing in the way empty sets are handled) were studied in [11]. Similar to Equation (2), for any $q={\left(kji\right)}_2\in \{0,\dots ,7\}$, we define the compositions $R{{\displaystyle ◁}}_{q}S$, $R{{\displaystyle ▷}}_{q}S$ and $R{\diamond }_{q}S$ as:

$$\begin{array}{c}\hfill R{{\displaystyle ◁}}_{q}S={\left(R^{{\rho }_i}{\displaystyle ◁}{S}^{{\rho }_j}\right)}^{{\rho }_k};\\ \hfill R{{\displaystyle ▷}}_{q}S={\left(R^{{\rho }_i}{\displaystyle ▷}{S}^{{\rho }_j}\right)}^{{\rho }_k};\\ \hfill R{\diamond }_{q}S={(R^{{\rho }_i}\diamond S^{{\rho }_j})}^{{\rho }_k}.\end{array}$$

Moreover, the above-mentioned compositions verify the following commutativity-like properties, with $q^{\prime }=7-q$:

$$\begin{array}{cc}& R{{\displaystyle ◁}}_{q}S=S{{\displaystyle ▷}}_{q^{\prime }}R;\end{array}$$

(3)

$$\begin{array}{cc}& R{\diamond }_{q}S=S{\diamond }_{q^{\prime }}R.\end{array}$$

(4)

Next, we extend the above notions to the ternary setting.

Definition 4. 

Let $p\in \{0,\dots ,215\}$ with $p={\left(kji\right)}_6$. For any two ternary relations S and T on X, the sub-composition $S\boxed{{\displaystyle ◁}}T$, super-composition $S\boxed{{\displaystyle ▷}}T$ and square-composition $S\boxed{\diamond }T$ are defined as:

$$\begin{array}{ccc}\hfill S{\boxed{{\displaystyle ◁}}}_p^{0}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_i(x,y,t)\in S\Rightarrow {\sigma }_j(x,t,z)\in T)\};\hfill \\ \hfill S{\boxed{{\displaystyle ▷}}}_p^{0}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_i(x,y,t)\in S\Leftarrow {\sigma }_j(x,t,z)\in T)\};\hfill \\ \hfill S{\boxed{\diamond }}_p^{0}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_i(x,y,t)\in S\iff {\sigma }_j(x,t,z)\in T)\};\hfill \\ \hfill S{\boxed{{\displaystyle ◁}}}_p^{1}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_i(x,y,t)\in S\Rightarrow {\sigma }_j(z,t,z)\in T)\};\hfill \\ \hfill S{\boxed{{\displaystyle ▷}}}_p^{1}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_i(x,y,t)\in S\Leftarrow {\sigma }_j(z,t,z)\in T)\};\hfill \\ \hfill S{\boxed{\diamond }}_p^{1}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_i(x,y,t)\in S\iff {\sigma }_j(z,t,z)\in T)\};\hfill \\ \hfill S{\boxed{{\displaystyle ◁}}}_p^{2}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_i(y,y,t)\in S\Rightarrow {\sigma }_j(x,t,z)\in T)\};\hfill \\ \hfill S{\boxed{{\displaystyle ▷}}}_p^{2}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_i(y,y,t)\in S\Leftarrow {\sigma }_j(x,t,z)\in T)\};\hfill \\ \hfill S{\boxed{\diamond }}_p^{2}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_i(y,y,t)\in S\iff {\sigma }_j(x,t,z)\in T)\}.\hfill \end{array}$$

These compositions can be expressed in terms of three representative ones, just as in the case of the composition of binary relations.

Proposition 2. 

Let $p={\left(kji\right)}_6\in \{0,\dots ,215\}$ and $r\in \{0,1,2\}$. For any two ternary relations S and T on X, the compositions $S{\boxed{{\displaystyle ◁}}}_p^{r}T$, $S{\boxed{{\displaystyle ▷}}}_p^{r}T$ and $S{\boxed{\diamond }}_p^{r}T$ can be written in terms of the compositions $S{\boxed{{\displaystyle ◁}}}_0^{r}T$, $S{\boxed{{\displaystyle ▷}}}_0^{r}T$ and $S{\boxed{\diamond }}_0^{r}T$ as:

(i)

$S{\boxed{{\displaystyle ◁}}}_p^{r}T={\left(S^{{\sigma }_i^{-1}}{\boxed{{\displaystyle ◁}}}_0^r{T}^{{\sigma }_j^{-1}}\right)}^{{\sigma }_k}$;

(ii)

$S{\boxed{{\displaystyle ▷}}}_p^{r}T={\left(S^{{\sigma }_i^{-1}}{\boxed{{\displaystyle ▷}}}_0^r{T}^{{\sigma }_j^{-1}}\right)}^{{\sigma }_k}$;

(iii)

$S{\boxed{\diamond }}_p^{r}T={\left(S^{{\sigma }_i^{-1}}{\boxed{\diamond }}_0^r{T}^{{\sigma }_j^{-1}}\right)}^{{\sigma }_k}$.

Proof. 

We give the proof for ${\boxed{{\displaystyle ◁}}}_p^0$:

$$\begin{array}{ccc}\hfill S{\boxed{{\displaystyle ◁}}}_p^{0}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\exists t\in X)({\sigma }_i(x,y,t)\in S\Rightarrow {\sigma }_j(x,t,z)\in T)\}\hfill \\ & =& \{{\sigma }_k(x,y,z)\in X^3\mid (\exists t\in X)((x,y,t)\in S^{{\sigma }_i^{-1}}\Rightarrow (x,t,z)\in T^{{\sigma }_j^{-1}})\}\hfill \\ & =& \{{\sigma }_k(x,y,z)\in X^3\mid (x,y,z)\in S^{{\sigma }_i^{-1}}{\boxed{{\displaystyle ◁}}}_0^0{T}^{{\sigma }_j^{-1}}\}\hfill \\ & =& {\left(S^{{\sigma }_i^{-1}}{\boxed{{\displaystyle ◁}}}_0^0{T}^{{\sigma }_j^{-1}}\right)}^{{\sigma }_k}.\hfill \end{array}$$

□

The following example illustrates the composition $S{\boxed{{\displaystyle ◁}}}_0^{0}T$ for two simple ternary relations S and T.

Example 1. 

Consider the two ternary relations S and T on the set $X=\{x,y,z\}$ given as:

$$\begin{array}{ccc}\hfill S& =& \left\{\right(y,y,z),(z,y,x),(z,z,x\left)\right\}\hfill \\ \hfill T& =& \left\{\right(x,x,x),(z,x,y),(z,x,z\left)\right\}.\hfill \end{array}$$

We have

$$\begin{array}{ccc}\hfill S{\boxed{{\displaystyle ◁}}}_0^{0}T=& & \left\{\right(x,x,x),(x,x,y),(x,x,z),(x,y,x),(x,y,y),(x,y,z),(x,z,x),(x,z,y),(x,z,z),\hfill \\ & & (y,x,x),(y,x,y),(y,x,z),(y,z,x),(y,z,y),(y,z,z),(z,x,x),(z,x,y),(z,x,z),\hfill \\ & & (z,y,y),(z,y,z),(z,z,y),(z,z,z)\}.\hfill \end{array}$$

3.2. Properties of BK-Compositions of Ternary Relations

In this section, we study the properties of the newly introduced compositions. The following proposition concerns the refinement of the BK-compositions of ternary relations.

Proposition 3. 

Let $p\in \{0,\dots ,215\}$ and $r\in \{0,1,2\}$. For any two ternary relations S and T on X, the following inclusions hold:

(i)

$S{\boxed{\diamond }}_p^{r}T\subseteq S{\boxed{{\displaystyle ◁}}}_p^{r}T$;

(ii)

$S{\boxed{\diamond }}_p^{r}T\subseteq S{\boxed{{\displaystyle ▷}}}_p^{r}T$.

Although the compositions $\boxed{{\displaystyle ◁}}$, $\boxed{{\displaystyle ▷}}$, and $\boxed{\diamond }$ are not commutative in general, interesting mixed-commutativity properties can be established.

Proposition 4. 

Let $p={\left(kji\right)}_6\in \{0,\dots ,215\}$. For any two ternary relations S and T on X, the following equalities hold:

(i)

$S{\boxed{{\displaystyle ◁}}}_p^{0}T=T{\boxed{{\displaystyle ▷}}}_{p^{\prime }}^{0}S$;

(ii)

$S{\boxed{{\displaystyle ◁}}}_p^{1}T=T{\boxed{{\displaystyle ▷}}}_{p^{\prime }}^{2}S$;

(iii)

$S{\boxed{\diamond }}_p^{0}T=T{\boxed{\diamond }}_{p^{\prime }}^{0}S$;

(iv)

$S{\boxed{\diamond }}_p^{1}T=T{\boxed{\diamond }}_{p^{\prime }}^{2}S$;

with $p^{\prime }={\left(\pi \left(k\right)\pi \left(i\right)\pi \left(j\right)\right)}_6$ and π the permutation of $\{0,\dots ,5\}$ given by

Table 1. The permutation $\pi$.

u	0	1	2	3	4	5
$\pi \left(u\right)$	1	0	4	5	2	3

:

Proof. 

We only give the proof for (i):

$$\begin{array}{ccc}\hfill S{\boxed{{\displaystyle ◁}}}_p^{0}T& =& \{{\sigma }_k(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_i(x,y,t)\in S\Rightarrow {\sigma }_j(x,t,z)\in T)\}\hfill \\ & =& \{{\sigma }_k(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_j(x,t,z)\in T\Leftarrow {\sigma }_i(x,y,t)\in S)\}\hfill \\ & =& \{{\sigma }_k\left({\sigma }_1(x,z,y)\right)\in X^3\mid (\forall t\in X)({\sigma }_j\left({\sigma }_1(x,z,t)\right)\in T\Leftarrow {\sigma }_i\left({\sigma }_1(x,t,y)\right)\in S)\}\hfill \\ & =& \{{\sigma }_k\left({\sigma }_1(x,y,z)\right)\in X^3\mid (\forall t\in X)({\sigma }_j\left({\sigma }_1(x,y,t)\right)\in T\Leftarrow {\sigma }_i\left({\sigma }_1(x,t,z)\right)\in S)\}.\hfill \end{array}$$

Since ${\sigma }_u\left({\sigma }_1(x,y,z)\right)={\sigma }_{\pi \left(u\right)}(x,y,z)$, it follows that

$$S{\boxed{{\displaystyle ◁}}}_p^{0}T=\{{\sigma }_{\pi \left(k\right)}(x,y,z)\in X^3\mid (\forall t\in X)({\sigma }_{\pi \left(j\right)}(x,y,t)\in T\Leftarrow {\sigma }_{\pi \left(i\right)}(x,t,z)\in S)\}=T{\boxed{{\displaystyle ▷}}}_{p^{\prime }}^{0}S.$$

□

4. Links between the BK-Compositions of Binary Relations and the BK-Compositions of Ternary Relations

In this section, we explore some interesting links between the BK-compositions of binary relations and the BK-compositions of ternary relations. The notions of binary projections of a ternary relation and of cylindrical extensions of a binary relation will play a central role in establishing these links.

Definition 5 

([27]). Let R be a binary relation on X.

(i)

The left cylindrical extension of R is the ternary relation $C_{\mathcal{l}}\left(R\right)$ on X defined as:

$$C_{\mathcal{l}}\left(R\right)=\{(x,y,z)\in X^3\mid (y,z)\in R\};$$

(ii)

The middle cylindrical extension of R is the ternary relation $C_m\left(R\right)$ on X defined as:

$$C_m\left(R\right)=\{(x,y,z)\in X^3\mid (x,z)\in R\};$$

(iii)

The right cylindrical extension of R is the ternary relation $C_r\left(R\right)$ on X defined as:

$$C_r\left(R\right)=\{(x,y,z)\in X^3\mid (x,y)\in R\}.$$

Definition 6 

([27]). Let T be a ternary relation on X.

(i)

The left projection of T is the binary relation $P_{\mathcal{l}}\left(T\right)$ on X defined as:

$$P_{\mathcal{l}}\left(T\right)=\{(x,y)\in X^2\mid (\exists z\in X)((z,x,y)\in T)\};$$

(ii)

The middle projection of T is the binary relation $P_m\left(T\right)$ on X defined as:

$$P_m\left(T\right)=\{(x,y)\in X^2\mid (\exists z\in X)((x,z,y)\in T)\};$$

(iii)

The right projection of T is the binary relation $P_r\left(T\right)$ on X defined as:

$$P_r\left(T\right)=\{(x,y)\in X^2\mid (\exists z\in X)((x,y,z)\in T)\}.$$

For further use, we introduce the following mapping and lemma. Consider the mapping $\Gamma :\{\mathcal{l},m,r\}\times \{0,1\}\to \{0,\dots ,5\}$ defined by

Table 2. The mapping $\Gamma$.

i	$\mathbf{\Gamma }(\mathit{\ell },\mathit{i})$	$\mathbf{\Gamma }(\mathit{m},\mathit{i})$	$\mathbf{\Gamma }(\mathit{r},\mathit{i})$
0	0	2	3
1	1	4	5

:

Lemma 1. 

Let $i\in \{0,1\}$ and $\lambda \in \{\mathcal{l},m,r\}$. For any binary relation R on X, it holds that

$${\sigma }_{\Gamma (\lambda ,i)}(x,y,z)\in C_{\lambda }\left(R\right)\iff {\rho }_i(y,z)\in R.$$

Proof. 

We only give the proof for $\lambda =\mathcal{l}$. From Table 2, it follows that

$$\begin{array}{ccc}\hfill {\sigma }_{\Gamma (\mathcal{l},i)}(x,y,z)\in C_{\mathcal{l}}\left(R\right)& \iff & {\sigma }_i(x,y,z)\in C_{\mathcal{l}}\left(R\right)\hfill \\ & \iff & {\rho }_i(y,z)\in R.\hfill \end{array}$$

□

The following proposition links the ternary BK-compositions of the cylindrical extension of binary relations with the cylindrical extensions of the binary BK-compositions of these relations.

Proposition 5. 

Let $q={\left(kji\right)}_2\in \{0,\dots ,7\}$, $r\in \{0,1,2\}$ and $\alpha ,\beta ,\gamma \in \{\mathcal{l},m,r\}$. For any two binary relations R and P on X, the following inclusions hold:

(i)

$C_{\alpha }\left(R\right){\boxed{{\displaystyle ◁}}}_p^r{C}_{\beta }\left(P\right)\subseteq C_{\gamma }\left(R{{\displaystyle ◁}}_{q}P\right)$;

(ii)

$C_{\alpha }\left(R\right){\boxed{{\displaystyle ▷}}}_p^r{C}_{\beta }\left(P\right)\subseteq C_{\gamma }\left(R{{\displaystyle ▷}}_{q}P\right)$;

(iii)

$C_{\alpha }\left(R\right){\boxed{\diamond }}_p^r{C}_{\beta }\left(P\right)\subseteq C_{\gamma }\left(R{\diamond }_{q}P\right)$;

with $p={\left(\Gamma (\gamma ,k)\Gamma (\beta ,j)\Gamma (\alpha ,i)\right)}_6$.

Proof. 

We only give the proof for (i) with $r=0$:

$$\begin{array}{ccc}\hfill C_{\alpha }\left(R\right){\boxed{{\displaystyle ◁}}}_p^0{C}_{\beta }\left(P\right)& =& \left\{{\sigma }_{\Gamma (\gamma ,k)}(x,y,z)\mid (\forall t\in X)({\sigma }_{\Gamma (\alpha ,i)}(x,y,t)\in C_{\alpha }\left(R\right)\right.\hfill \\ & & \left.\Rightarrow {\sigma }_{\Gamma (\beta ,j)}(x,t,z)\in C_{\beta }\left(P\right))\right\}\hfill \\ & \subseteq & \left\{{\sigma }_{\Gamma (\gamma ,k)}(x,y,z)\mid (\forall t\in X)({\rho }_i(y,t)\in R\Rightarrow {\rho }_j(t,z)\in P)\right\}\hfill \\ & =& \left\{{\sigma }_{\Gamma (\gamma ,k)}(x,y,z)\mid {\rho }_k(y,z)\in R{{\displaystyle ◁}}_{q}P\right\}\hfill \\ & =& \left\{{\sigma }_{\Gamma (\gamma ,k)}(x,y,z)\mid {\sigma }_{\Gamma (\gamma ,k)}(x,y,z)\in C_{\gamma }\left(R{{\displaystyle ◁}}_{q}P\right)\right\}\hfill \\ & =& C_{\gamma }\left(R{{\displaystyle ◁}}_{q}P\right).\hfill \end{array}$$

□

Conversely, in order to link the BK-compositions of ternary relations with the BK-compositions of their binary projections, we consider the mapping $\Pi :\{0,\dots ,5\}\times \{\mathcal{l},m,r\}\to \{0,1\}$ defined as:

$$\Pi (k,\lambda )=\left\{\begin{array}{cc}1\hfill & ,\mathrm{if}\Gamma (1,\lambda )=k\hfill \\ 0\hfill & ,\mathrm{otherwise}\hfill \end{array}\right..$$

The mapping $\Pi$ is listed explicitly in

Table 3. The mapping $\Pi$.

k	$\mathbf{\Pi }(\mathit{k},\mathit{\ell })$	$\mathbf{\Pi }(\mathit{k},\mathit{m})$	$\mathbf{\Pi }(\mathit{k},\mathit{r})$
0	0	0	0
1	1	0	0
2	0	0	0
3	0	0	0
4	0	1	0
5	0	0	1

:

Furthermore, we consider the mapping $\omega :\{0,\dots ,5\}\to \{\mathcal{l},m,r\}$ defined by

Table 4. The mapping $\omega$.

k	0	1	2	3	4	5
$\omega \left(k\right)$	ℓ	ℓ	m	r	m	r

:

We will use the following two lemmas to establish the links. The first lemma is straightforward and is stated without proof.

Lemma 2. 

Let T be a ternary relation on X. For any $k\in \{0,\dots ,5\}$, it holds that

$$P_{\omega \left(k\right)}\left(T^{{\sigma }_k}\right)={\left(P_{\mathcal{l}}\left(T\right)\right)}^{{\rho }_{\Pi (k,\omega (k\left)\right)}}.$$

Lemma 3. 

Let $r\in \{0,1,2\}$. For any two ternary relations S and T on X, the following inclusions hold:

(i)

$P_{\mathcal{l}}\left(S{\boxed{{\displaystyle ◁}}}_0^{r}T\right)\subseteq P_{\mathcal{l}}\left(S\right){\displaystyle ◁}{P}_{\mathcal{l}}\left(T\right)$;

(ii)

$P_{\mathcal{l}}\left(S{\boxed{{\displaystyle ▷}}}_0^{r}T\right)\subseteq P_{\mathcal{l}}\left(S\right){\displaystyle ▷}{P}_{\mathcal{l}}\left(T\right)$;

(iii)

$P_{\mathcal{l}}\left(S{\boxed{\diamond }}_0^{r}T\right)\subseteq P_{\mathcal{l}}\left(S\right)\diamond P_{\mathcal{l}}\left(T\right)$.

Proof. 

We only give the proof for (i)

$$\begin{array}{ccc}\hfill (y,z)\in P_{\mathcal{l}}\left(S{\boxed{{\displaystyle ◁}}}_0^{0}T\right)& \iff & (\exists x\in X)((x,y,z)\in S{\boxed{{\displaystyle ◁}}}_0^{0}T)\hfill \\ & \iff & (\exists x\in X)(\forall t\in X)\left(\right(x,y,t)\in S\Rightarrow (x,t,z)\in T)\hfill \\ & \Rightarrow & (\forall t\in X)((y,t)\in P_{\mathcal{l}}\left(S\right)\Rightarrow (t,z)\in P_{\mathcal{l}}\left(T\right))\hfill \\ & \Rightarrow & ((y,z)\in P_{\mathcal{l}}\left(S\right){\displaystyle ◁}{P}_{\mathcal{l}}\left(T\right).\hfill \end{array}$$

□

The following proposition relates the projection of the BK-composition of ternary relations with the BK-composition of their binary projections.

Proposition 6. 

Let $p={\left(kji\right)}_6\in \{0,\dots ,215\}$ and $r\in \{0,1,2\}$. For any two ternary relations S and T on X, the following inclusions hold, with $q={\left(\Pi (k,\omega (k\left)\right)\Pi (j,\omega (j\left)\right)\Pi (i,\omega (i\left)\right)\right)}_2$:

(i)

$P_{\omega \left(k\right)}\left(S{\boxed{{\displaystyle ◁}}}_p^{r}T\right)\subseteq P_{\omega \left(i\right)}\left(S\right){{\displaystyle ◁}}_q{P}_{\omega \left(j\right)}\left(T\right)$;

(ii)

$P_{\omega \left(k\right)}\left(S{\boxed{{\displaystyle ▷}}}_p^{r}T\right)\subseteq P_{\omega \left(i\right)}\left(S\right){{\displaystyle ▷}}_q{P}_{\omega \left(j\right)}\left(T\right)$;

(iii)

$P_{\omega \left(k\right)}\left(S{\boxed{\diamond }}_p^{r}T\right)\subseteq P_{\omega \left(i\right)}\left(S\right){\diamond }_q{P}_{\omega \left(j\right)}\left(T\right)$.

Proof. 

We only give the proof for (i) with $r=0$. From Proposition 2 and Lemmas 2 and 3, it follows that

$$\begin{array}{ccc}\hfill P_{\omega \left(k\right)}\left(S{\boxed{{\displaystyle ◁}}}_p^{0}T\right)& =& P_{\omega \left(k\right)}\left({\left(S^{{\sigma }_i^{-1}}{\boxed{{\displaystyle ◁}}}_0^0{T}^{{\sigma }_j^{-1}}\right)}^{{\sigma }_k}\right)\hfill \\ & =& {\left(P_{\mathcal{l}}\left(S^{{\sigma }_i^{-1}}{\boxed{{\displaystyle ◁}}}_0^0{T}^{{\sigma }_j^{-1}}\right)\right)}^{{\rho }_{\Pi (k,\omega (k\left)\right)}}\hfill \\ & \subseteq & {\left(P_{\mathcal{l}}\left(S^{{\sigma }_i^{-1}}\right){\displaystyle ◁}{P}_{\mathcal{l}}\left(T^{{\sigma }_j^{-1}}\right)\right)}^{{\rho }_{\Pi (k,\omega (k\left)\right)}}.\hfill \end{array}$$

Lemma 2 also implies that $P_{\mathcal{l}}\left(T^{{\sigma }_i^{-1}}\right)={\left(P_{\omega \left(i\right)}\left(T\right)\right)}^{{\rho }_{\Pi (i,\omega (i\left)\right)}}$, and hence,

$$P_{\omega \left(k\right)}\left(S{\boxed{{\displaystyle ◁}}}_p^{0}T\right)\subseteq {\left(P_{\omega \left(i\right)}{\left(S\right)}^{{\rho }_{\Pi (i,\omega (i\left)\right)}}{\displaystyle ◁}{P}_{\omega \left(j\right)}{\left(T\right)}^{{\rho }_{\Pi (j,\omega (j\left)\right)}}\right)}^{{\rho }_{\Pi (k,\omega (k\left)\right)}}=P_{\omega \left(i\right)}\left(S\right){{\displaystyle ◁}}_q{P}_{\omega \left(j\right)}\left(T\right).$$

□

5. Interactions between the Compositions of Ternary Relations and Their BK-Compositions

In this section, we show some interactions between the four-point compositions and the BK-compositions of ternary relations.

5.1. Mixed-Associativity of BK-Compositions of Ternary Relations

The following proposition shows a mixed-associativity property of BK-compositions.

Proposition 7. 

Let $p\in \{0,43,86,129,172,215\}$. For any three ternary relations R, S, and T on X, the following equality holds:

$$R{\boxed{{\displaystyle ◁}}}_p^0\left(S{\boxed{{\displaystyle ▷}}}_p^{0}T\right)=\left(R{\boxed{{\displaystyle ◁}}}_p^{0}S\right){\boxed{{\displaystyle ▷}}}_p^{0}T.$$

Proof. 

We only give the proof for the case $p=0$. Using the following tautology which holds for any three Boolean propositions $P,Q,R$,

$$P\Rightarrow (Q\Rightarrow R)\iff Q\Rightarrow (P\Rightarrow R),$$

we obtain

$$\begin{array}{c}(x,y,z)\in R{\boxed{{\displaystyle ◁}}}_0^0\left(S{\boxed{{\displaystyle ▷}}}_0^{0}T\right)\hfill \\ \iff (\forall t\in X)((x,y,t)\in R\Rightarrow (x,t,z)\in \left(S{\boxed{{\displaystyle ▷}}}_0^{0}T\right))\hfill \\ \iff (\forall t\in X)((x,y,t)\in R\Rightarrow \left((\forall s\in X)(x,t,s)\in S\Leftarrow (x,s,z)\in T)\right)\hfill \\ \iff (\forall (s,t)\in X^2)\left((x,y,t)\in R\Rightarrow \left(\right(x,s,z)\in T\Rightarrow (x,t,s)\in S)\right)\hfill \\ \iff (\forall (s,t)\in X^2)\left((x,s,z)\in T\Rightarrow \left((x,y,t)\in R\Rightarrow (x,t,s)\in S\right)\right)\hfill \\ \iff (\forall s\in X)\left((\forall t\in X)\left((x,y,t)\in R\Rightarrow (x,t,s)\in S\right)\Leftarrow (x,s,z)\in T\right)\hfill \\ \iff (\forall s\in X)\left((x,y,s)\in R{\boxed{{\displaystyle ▷}}}_0^{0}S\right)\Leftarrow (x,s,z)\in T)\hfill \\ \iff (x,y,z)\in \left(R{\boxed{{\displaystyle ▷}}}_0^{0}S\right){\boxed{{\displaystyle ▷}}}_0^{0}T.\hfill \end{array}$$

□

The following example illustrates that the above property does not hold for the compositions ${\boxed{{\displaystyle ◁}}}_p^r$ and ${\boxed{{\displaystyle ▷}}}_p^r$ with $r\in \{1,2\}$.

Example 2. 

Consider the ternary relations R, S, and T on the set $X=\{x_1,x_2,x_3,x_4,x_5\}$ given as

$$\begin{array}{ccc}\hfill R& =& \left\{(x_1,x_2,x_3)\right\},\hfill \\ \hfill S& =& \left\{(x_4,x_3,x_5)\right\},\hfill \\ \hfill T& =& \left\{(x_4,x_5,x_4)\right\}.\hfill \end{array}$$

It is clear that $(x_1,x_2,x_4)\in R{\boxed{{\displaystyle ◁}}}_0^1\left(S{\boxed{{\displaystyle ▷}}}_0^{1}T\right)$, but $(x_1,x_2,x_4)\notin \left(R{\boxed{{\displaystyle ◁}}}_0^{1}S\right){\boxed{{\displaystyle ▷}}}_0^{1}T$. Hence,

$$R{\boxed{{\displaystyle ◁}}}_0^1\left(S{\boxed{{\displaystyle ▷}}}_0^{1}T\right)\ne \left(R{\boxed{{\displaystyle ◁}}}_0^{1}S\right){\boxed{{\displaystyle ▷}}}_0^{1}T.$$

Proposition 8. 

Let $p\in \{0,43,86,129,172,215\}$. For any three ternary relations R, S, and T on X, the following equalities hold:

(i)

$R{\boxed{{\displaystyle ◁}}}_p^0\left(S{\boxed{{\displaystyle ◁}}}_p^{0}T\right)=\left(R{☐}_p^{0}S\right){\boxed{{\displaystyle ◁}}}_p^{0}T$;

(ii)

$R{\boxed{{\displaystyle ▷}}}_p^0\left(S{☐}_p^{0}T\right)=\left(R{\boxed{{\displaystyle ▷}}}_p^{0}S\right){\boxed{{\displaystyle ▷}}}_p^{0}T$.

Proof. 

We only give the proof for (i) with $p=0$. Again using the Boolean tautology from the proof of Proposition 7, we obtain

$$\begin{array}{c}(x,y,z)\in R{\boxed{{\displaystyle ◁}}}_0^0\left(S{\boxed{{\displaystyle ◁}}}_0^{0}T\right)\hfill \\ \iff (\forall t\in X)\left((x,y,t)\in R\Rightarrow (x,t,z)\in \left(S{\boxed{{\displaystyle ◁}}}_0^{0}T\right)\right)\hfill \\ \iff (\forall t\in X)\left((x,y,t)\in R\Rightarrow \left((\forall s\in X)\left(\right(x,t,s)\in S\Rightarrow (x,s,z)\in T\right)\right)\hfill \\ \iff (\forall (s,t)\in X^2)\left((x,y,t)\in R\Rightarrow \left((x,t,s)\in S\Rightarrow (x,s,z)\in T\right)\right)\hfill \\ \iff (\forall (s,t)\in X^2)\left(\left((x,y,t)\in R\wedge (x,t,s)\in S\right)\Rightarrow (x,s,z)\in T\right)\hfill \\ \iff (\forall s\in X)\left((\exists t\in X)\left((x,y,t)\in R\wedge (x,t,s)\right)\in S\Rightarrow (x,s,z)\in T\right)\hfill \\ \iff (\forall s\in X)\left((x,y,s)\in R{☐}_0^{0}S\Rightarrow (x,s,z)\in T\right)\hfill \\ \iff (x,y,z)\in \left(R{☐}_0^{0}S\right){\boxed{{\displaystyle ◁}}}_0^{0}T.\hfill \end{array}$$

□

5.2. The Role of BK-Compositions in Relational Equations

In this subsection, we show that the BK-compositions of ternary relations are a valuable tool to express the greatest solutions of relational equations. The following proposition expresses an adjointness-like relationship [32] between the different types of compositions of ternary relations.

Proposition 9. 

For any three ternary relations R, S, and T on X, the following equivalences hold:

$$R{☐}_0^{0}S\subseteq T\iff R\subseteq T{\boxed{{\displaystyle ▷}}}_0^0{S}^{{\sigma }_1}\iff S\subseteq R^{{\sigma }_1}{\boxed{{\displaystyle ◁}}}_0^{0}T.$$

Proof. 

We only give the proof for the first equivalence. For the direct implication, suppose that $R{☐}_0^{0}S\subseteq T$. Let $(x,y,z)\in R$, and then we need to show that $(x,y,z)\in T{\boxed{{\displaystyle ▷}}}_0^0{S}^{{\sigma }_1}$; i.e., for any $t\in X$, it holds that $(x,y,t)\in T\Leftarrow (x,z,t)\in S$. Suppose that $(x,z,t)\in S$, then the fact that $(x,y,z)\in R$ implies that $(x,y,t)\in R{☐}_0^{0}S$. The hypothesis $R{☐}_0^{0}S\subseteq T$ guarantees that $(x,y,t)\in T$. Thus, $(x,y,t)\in T\Leftarrow (x,z,t)\in S$. For the converse implication, let $(x,y,z)\in R{☐}_0^{0}S$, and then there exists $t\in X$ such that $(x,y,t)\in R$ and $(x,t,z)\in S$. Since $R\subseteq T{\boxed{{\displaystyle ▷}}}_0^0{S}^{{\sigma }_1}$, it follows that $(x,y,t)\in T{\boxed{{\displaystyle ▷}}}_0^0{S}^{{\sigma }_1}$. Thus, for any $s\in X$, it holds that $(x,y,s)\in T\Leftarrow (x,t,s)\in S$. Since $(x,t,z)\in S$, it holds that $(x,y,z)\in T$. □

The following proposition extends the previous result to account for all $p\in \{0,\dots ,215\}$.

Proposition 10. 

Let $p={\left(kji\right)}_6\in \{0,\dots ,215\}$. For any three ternary relations R, S, and T on X, the following equivalences hold:

$$R{☐}_p^{0}S\subseteq T\iff R\subseteq T{\boxed{{\displaystyle ▷}}}_{p^{\prime }}^{0}S\iff S\subseteq R{\boxed{{\displaystyle ◁}}}_{p^{″}}^{0}T,$$

with $p^{\prime }=\left(i\pi \left(j\right)k\right)$ and $p^{″}=\left(jk\pi \left(i\right)\right)$.

Proof. 

We only show the first equivalence. Suppose that $R{☐}_p^{0}S\subseteq T$. From Proposition 1, it follows that $R^{{\sigma }_i^{-1}}{☐}_0^0{S}^{{\sigma }_j^{-1}}\subseteq T^{{\sigma }_k^{-1}}$. Proposition 9 implies that $R^{{\sigma }_i^{-1}}\subseteq T^{{\sigma }_k^{-1}}{\boxed{{\displaystyle ▷}}}_0^0{\left(S^{{\sigma }_j^{-1}}\right)}^{{\sigma }_1}$. Hence, $R\subseteq {\left(T^{{\sigma }_k^{-1}}{\boxed{{\displaystyle ▷}}}_0^0{S}^{{\sigma }_{\pi \left(j\right)}^{-1}}\right)}^{{\sigma }_i}$. Proposition 3 guarantees that $R\subseteq T{\boxed{{\displaystyle ▷}}}_{p^{\prime }}^{0}S$, with $p^{\prime }=\left(i\pi \left(j\right)k\right)$. □

The following proposition concerns the greatest solution of the most basic ternary relational equation.

Proposition 11. 

Let S and T be two ternary relations on X. The following statements hold:

(i)

The relational equation $S{☐}_0^{0}U=T$ in the unknown relation U is solvable if and only if $S^{{\sigma }_1}{\boxed{{\displaystyle ◁}}}_0^{0}T$ is its greatest solution.

(ii)

The relational equation $U{☐}_0^{0}S=T$ in the unknown relation U is solvable if and only if $T{\boxed{{\displaystyle ▷}}}_0^0{S}^{{\sigma }_1}$ is its greatest solution.

Proof. 

Suppose that the relational equation $S{☐}_0^{0}U=T$ has a solution U; then, Proposition 9 guarantees that $U\subseteq S^{{\sigma }_1}{\boxed{{\displaystyle ◁}}}_0^{0}T$. Next, it suffices to show that $S^{{\sigma }_1}{\boxed{{\displaystyle ◁}}}_0^{0}T$ is a solution; i.e., $T=S{☐}_0^0\left(S^{{\sigma }_1}{\boxed{{\displaystyle ◁}}}_0^{0}T\right)$. The fact that $U\subseteq S^{{\sigma }_1}{\boxed{{\displaystyle ◁}}}_0^{0}T$ implies that $T=S{☐}_0^{0}U\subseteq S{☐}_0^0\left(S^{{\sigma }_1}{\boxed{{\displaystyle ◁}}}_0^{0}T\right)$. Conversely, let $(x,y,z)\in S{☐}_0^0\left(S^{{\sigma }_1}{\boxed{{\displaystyle ◁}}}_0^{0}T\right)$; then, there exists $t\in X$ such that $(x,y,t)\in S$ and $(x,t,z)\in S^{{\sigma }_1}{\boxed{{\displaystyle ◁}}}_0^{0}T$. Hence, for any $t^{\prime }\in X$, we have that $(x,t^{\prime },t)\in S$ implies $(x,t^{\prime },z)\in T$. Since $(x,y,t)\in S$, it follows that $(x,y,z)\in T$.

The converse implication is trivial. □

Proposition 12. 

Let $p\in \{0,\dots ,215\}$. For any two ternary relations S and T on X, the following statements hold, where $p^{\prime }$ and $p^{″}$ are as in Proposition 10:

(i)

The relational equation $S{☐}_p^{0}U=T$ in the unknown relation U is solvable if and only if $T{\boxed{{\displaystyle ◁}}}_{p^{\prime }}^0{S}^{{\sigma }_1}$ is its greatest solution.

(ii)

The relational equation $U{☐}_p^{0}S=T$ in the unknown relation U is solvable if and only if $S^{{\sigma }_1}{\boxed{{\displaystyle ▷}}}_{p^{″}}^{0}T$ is its greatest solution.

Proof. 

The proof is similar to that of Proposition 11. □

6. Traces of Ternary Relations

In this section, we introduce the traces of a ternary relation and investigate their properties.

6.1. Revisiting the Traces of Binary Relations

First, we recall the notions of left and right trace of a binary relation introduced by Doignon et al. [18]. We then express these traces in terms of the BK-compositions and recall some of their properties.

Definition 7 

([19]). Let R be a binary relation on X.

(i)

The left trace of R is the binary relation $R^{\mathcal{l}}$ on X defined as

$$\begin{array}{c}\hfill R^{\mathcal{l}}=\{(x,y)\in X^2\mid (\forall z\in X)((x,z)\in R\Rightarrow (y,z)\in R)\}.\end{array}$$

(ii)

The right trace of R is the binary relation $R^r$ on X defined as

$$\begin{array}{c}\hfill R^r=\{(x,y)\in X^2\mid (\forall z\in X)((z,x)\in R\Rightarrow (z,y)\in R)\}.\end{array}$$

Theorem 1 

([19]). Let R be a binary relation on X. The following statements are equivalent:

(i)

R is reflexive;

(ii)

${\left(R^{\mathcal{l}}\right)}^t\subseteq R$;

(iii)

$R^r\subseteq R$.

Theorem 2 

([19]). Let R be a binary relation on X. The following statements are equivalent:

(i)

R is transitive;

(ii)

$R\subseteq {\left(R^{\mathcal{l}}\right)}^t$;

(iii)

$R\subseteq R^r$.

Theorem 3 

([19]). For any binary relation R on X, it holds that

$${\left(R^{\mathcal{l}}\right)}^t\circ R=R\circ R^r=R.$$

Remark 1. 

It is interesting to note that these traces can be expressed in terms of the BK-compositions:

$$\begin{array}{ccc}\hfill R^r& =& R{{\displaystyle ◁}}_{1}R=R{{\displaystyle ▷}}_{6}R;\hfill \\ \hfill R^{\mathcal{l}}& =& R{{\displaystyle ◁}}_{2}R=R{{\displaystyle ▷}}_{5}R.\hfill \end{array}$$

Following this line of reasoning, we can define other traces as follows. For any binary relation R on X and any $n\in \{0,\dots ,7\}$, the n-th trace of R, denoted by $R^{{{\displaystyle ◁}}_n}$, is defined as:

$$R^{{{\displaystyle ◁}}_n}:=R{{\displaystyle ◁}}_{n}R=R{{\displaystyle ▷}}_{7-n}R.$$

6.2. Transitivity Properties of Ternary Relations

Recall that a binary relation R is transitive if and only if $R\circ R\subseteq R$. In a similar way, one can associate a notion of transitivity with any four-point composition of ternary relations. Here, we limit our attention to the associative compositions.

Definition 8. 

A ternary relation T on X is said to be:

(i)

Left transitive if $T{☐}_{0}T\subseteq T$, or, equivalently, $T{☐}_{43}T\subseteq T$;

(ii)

Middle transitive if $T{☐}_{86}T\subseteq T$, or, equivalently, $T{☐}_{172}T\subseteq T$;

(iii)

Right transitive if $T{☐}_{129}T\subseteq T$, or, equivalently, $T{☐}_{215}T\subseteq T$.

Proposition 13. 

Let T be a ternary relation on X. The following statements hold:

(i)

If T is left reflexive, then $T{☐}_{i}T\supseteq T$ for $i\in \{0,43\}$;

(ii)

If T is middle reflexive, then $T{☐}_{i}T\supseteq T$ for $i\in \{86,172\}$;

(iii)

If T is right reflexive, then $T{☐}_{i}T\supseteq T$ for $i\in \{129,215\}$.

Proof. 

We only give the proof for (i). Let $(x,y,z)\in T$; then, the left reflexivity of T implies that $(x,z,z)\in T$. Hence, $(x,y,z)\in T{☐}_{0}T$. Thus, $T\subseteq T{☐}_{0}T$. □

In view of Proposition 13 and Definition 8, we have the following corollary.

Corollary 1. 

Let T be a ternary relation on X. The following statements hold:

(i)

if T is left reflexive and left transitive, then $T=T{☐}_{i}T$ for $i\in \{0,43\}$;

(ii)

if T is middle reflexive and middle transitive, then $T=T{☐}_{i}T$ for $i\in \{86,172\}$;

(iii)

if T is right reflexive and right transitive, then $T=T{☐}_{i}T$ for $i\in \{129,215\}$.

6.3. Traces of Ternary Relations Based on BK-Compositions

Similarly as for binary relations, we can introduce the traces of a ternary relation T as the BK-compositions of T with itself.

Definition 9. 

Let $p={\left(kji\right)}_6\in \{0,\dots ,215\}$ and $r\in \{0,1,2\}$. The traces of a ternary relation T on X are the ternary relations defined as:

$$T^{{\boxed{{\displaystyle ◁}}}_p^r}:=T{\boxed{{\displaystyle ◁}}}_p^{r}T=T{\boxed{{\displaystyle ▷}}}_{p^{\prime }}^{r^{\prime }}T,$$

where $r^{\prime }$ and $p^{\prime }$ are as in Proposition 4.

Example 3. 

For the ternary relation T in Example 1, we have

$$\begin{array}{ccc}\hfill S{\boxed{{\displaystyle ◁}}}_0^{0}T=& & \left\{\right(x,x,x),(x,x,y),(x,x,z),(x,y,x),(x,y,y),(x,y,z),(x,z,x),(x,z,y),(x,z,z),\hfill \\ & & (y,x,x),(y,x,y),(y,x,z),(y,y,x),(y,y,y),(y,y,z),(y,z,x),(y,z,y),(y,z,z),\hfill \\ & & (z,x,x),(z,x,y),(z,x,z),(z,y,y),(z,y,z),(z,z,y),(z,z,z)\}.\hfill \end{array}$$

Obviously, these traces are not all distinct. Among them, we identify those that preserve the properties in Theorems 1–3.

Proposition 14. 

Let T be a ternary relation on X.

(i)

The following traces are left reflexive and left transitive:

(a) 

$T^{{\boxed{{\displaystyle ◁}}}_1^0}=T^{{\boxed{{\displaystyle ◁}}}_6^0}=T^{{\boxed{{\displaystyle ◁}}}_{16}^0}=T^{{\boxed{{\displaystyle ◁}}}_{23}^0}=T^{{\boxed{{\displaystyle ◁}}}_{26}^0}=T^{{\boxed{{\displaystyle ◁}}}_{33}^0}$;

(b) 

$T^{{\boxed{{\displaystyle ◁}}}_{37}^0}=T^{{\boxed{{\displaystyle ◁}}}_{42}^0}=T^{{\boxed{{\displaystyle ◁}}}_{52}^0}=T^{{\boxed{{\displaystyle ◁}}}_{59}^0}=T^{{\boxed{{\displaystyle ◁}}}_{62}^0}=T^{{\boxed{{\displaystyle ◁}}}_{69}^0}$.

(ii)

The following traces are middle reflexive and middle transitive:

(a) 

$T^{{\boxed{{\displaystyle ◁}}}_{73}^0}=T^{{\boxed{{\displaystyle ◁}}}_{78}^0}=T^{{\boxed{{\displaystyle ◁}}}_{88}^0}=T^{{\boxed{{\displaystyle ◁}}}_{95}^0}=T^{{\boxed{{\displaystyle ◁}}}_{98}^0}=T^{{\boxed{{\displaystyle ◁}}}_{105}^0}$;

(b) 

$T^{{\boxed{{\displaystyle ◁}}}_{109}^0}=T^{{\boxed{{\displaystyle ◁}}}_{114}^0}=T^{{\boxed{{\displaystyle ◁}}}_{124}^0}=T^{{\boxed{{\displaystyle ◁}}}_{131}^0}=T^{{\boxed{{\displaystyle ◁}}}_{134}^0}=T^{{\boxed{{\displaystyle ◁}}}_{141}^0}$.

(iii)

The following traces are right reflexive and right transitive:

(a) 

$T^{{\boxed{{\displaystyle ◁}}}_{145}^0}=T^{{\boxed{{\displaystyle ◁}}}_{150}^0}=T^{{\boxed{{\displaystyle ◁}}}_{160}^0}=T^{{\boxed{{\displaystyle ◁}}}_{167}^0}=T^{{\boxed{{\displaystyle ◁}}}_{170}^0}=T^{{\boxed{{\displaystyle ◁}}}_{177}^0}$;

(b) 

$T^{{\boxed{{\displaystyle ◁}}}_{181}^0}=T^{{\boxed{{\displaystyle ◁}}}_{186}^0}=T^{{\boxed{{\displaystyle ◁}}}_{196}^0}=T^{{\boxed{{\displaystyle ◁}}}_{203}^0}=T^{{\boxed{{\displaystyle ◁}}}_{206}^0}=T^{{\boxed{{\displaystyle ◁}}}_{213}^0}$.

The following proposition expresses the link between the traces in statements (a) and (b) of Proposition 14.

Proposition 15. 

Let T be a ternary relation on X.

(i)

$T^{{\boxed{{\displaystyle ◁}}}_{37}^0}={\left(T^{{\boxed{{\displaystyle ◁}}}_1^0}\right)}^{{\sigma }_1}$;

(ii)

$T^{{\boxed{{\displaystyle ◁}}}_{109}^0}={\left(T^{{\boxed{{\displaystyle ◁}}}_{73}^0}\right)}^{{\sigma }_1}$;

(iii)

$T^{{\boxed{{\displaystyle ◁}}}_{181}^0}={\left(T^{{\boxed{{\displaystyle ◁}}}_{145}^0}\right)}^{{\sigma }_1}$.

Proof. 

We give the proof for (i). From Proposition 2, it follows that

$$T^{{\boxed{{\displaystyle ◁}}}_{37}^0}={\left(T^{{\sigma }_1}{\boxed{{\displaystyle ◁}}}_0^{0}T\right)}^{{\sigma }_1}={\left(T{\boxed{{\displaystyle ◁}}}_1^{0}T\right)}^{{\sigma }_1}={\left(T^{{\boxed{{\displaystyle ◁}}}_1^0}\right)}^{{\sigma }_1}.$$

□

Similarly as in the binary setting, we select three of the traces that will play a specific role in what follows, namely the left trace $T^{\mathcal{l}}$, the middle trace $T^m$, and the right trace $T^r$:

(i)

$T^{\mathcal{l}}:=T^{{\boxed{{\displaystyle ◁}}}_1^0}=\{(x,y,z)\in X^3\mid (\forall a\in X)((x,a,y)\in T\Rightarrow (x,a,z)\in T)\}$;

(ii)

$T^m:=T^{{\boxed{{\displaystyle ◁}}}_{73}^0}=\{(x,y,z)\in X^3\mid (\forall a\in X)((x,y,a)\in T\Rightarrow (z,y,a)\in T)\}$;

(iii)

$T^r:=T^{{\boxed{{\displaystyle ◁}}}_{145}^0}=\{(x,y,z)\in X^3\mid (\forall a\in X)((y,a,z)\in T\Rightarrow (x,a,z)\in T)\}$.

The following proposition expresses that some of these traces coincide in the face of symmetry.

Proposition 16. 

For any ternary relation T on X, the following statements hold:

(i)

if T is left symmetric, then $T^{\mathcal{l}}=T^m$;

(ii)

if T is middle symmetric, then $T^r=T^{\mathcal{l}}$;

(iii)

if T is left symmetric, then $T^m=T^r$.

The following theorem shows that the above-defined traces are solutions to relational equations. It extends Theorem 3 to the ternary setting.

Theorem 4. 

For any ternary relation T on X, the following equalities hold:

(i)

$T=T{☐}_0{T}^{\mathcal{l}}=T^{\mathcal{l}}{☐}_{43}T$;

(ii)

$T=T{☐}_{86}{T}^m=T^m{☐}_{129}T$;

(iii)

$T=T{☐}_{172}{T}^r=T^r{☐}_{215}T$.

Proof. 

We give the proof for the first equality of (i). Let $(x,y,z)\in T{☐}_0{T}^{\mathcal{l}}$; then, there exists an element t of X such that $(x,y,t)\in T$ and $(x,t,z)\in T^{\mathcal{l}}$, and thus it follows for any $a\in X$ that $(x,a,t)\in T$ implies $(x,a,z)\in T$, and in particular $(x,y,t)\in T$ implies $(x,y,z)\in T$, and thus $T{☐}_0{T}^{\mathcal{l}}\subseteq T$. Conversely, let $(x,y,z)\in T$, since $T^{\mathcal{l}}$ is left reflexive it holds that $(x,z,z)\in T^{\mathcal{l}}$, and thus $(x,y,z)\in T{☐}_0{T}^{\mathcal{l}}$, and hence $T\subseteq T{☐}_0{T}^{\mathcal{l}}$. □

6.4. Properties of Ternary Relations in Terms of Traces

In this section, we characterize some properties of a ternary relation in terms of its traces. The first proposition characterizes different reflexivity properties and extends Theorem 1 to the ternary setting.

Proposition 17. 

For any ternary relation T on X, the following equivalences hold:

(i)

T is left reflexive ⇔$T^{\mathcal{l}}\subseteq T$;

(ii)

T is middle reflexive ⇔$T^m\subseteq T$;

(iii)

T is right reflexive ⇔$T^r\subseteq T$.

Proof. 

We give the proof for (i). Since $T^{\mathcal{l}}$ is left reflexive, the inclusion $T^{\mathcal{l}}\subseteq T$ implies that T is also left reflexive. Conversely, suppose that T is left reflexive. Let $(x,y,z)\in T^{\mathcal{l}}$, then for any $a\in X$, it holds that $(x,a,y)\in T\Rightarrow (x,a,z)\in T$. In particular, $(x,y,y)\in T\Rightarrow (x,y,z)\in T$, and thus $T^{\mathcal{l}}\subseteq T$. □

The following proposition characterizes different transitivity properties of a ternary relation in terms of its traces. This result extends Theorem 2 to the ternary setting.

Proposition 18. 

For any ternary relation T on X, the following equivalences hold:

(i)

T is left transitive ⇔$T\subseteq T^{\mathcal{l}}$;

(ii)

T is middle transitive ⇔$T\subseteq T^m$;

(iii)

T is right transitive ⇔$T\subseteq T^r$.

Proof. 

We give the proof for (i). Theorem 4 states that $T{☐}_0{T}^{\mathcal{l}}\subseteq T$. If $T\subseteq T^{\mathcal{l}}$, then $T{☐}_{0}T\subseteq T{☐}_0{T}^{\mathcal{l}}\subseteq T$. Thus, T is left transitive. Conversely, let $(x,y,z)\in T$, then for any $a\in X$, the left transitivity of T implies $(x,a,y)\in T\Rightarrow (x,a,z)\in T$. Hence, $(x,y,z)\in T^{\mathcal{l}}$. □

The following corollary follows immediately from Propositions 17 and 18.

Corollary 2. 

For any ternary relation T on X, the following equivalences hold:

(i)

T is left reflexive and left transitive ⇔$T^{\mathcal{l}}=T$;

(ii)

T is middle reflexive and middle transitive ⇔$T^m=T$;

(iii)

T is right reflexive and right transitive ⇔$T^r=T$.

6.5. Ternary Equivalence Relations

In this subsection, we consider formal ternary counterparts of the concept of a binary equivalence relation, i.e., a binary relation that is reflexive, symmetric, and transitive. As each of these properties comes in many flavors, we aim to avoid a combinatorial explosion and select relevant combinations only.

Definition 10. 

A ternary relation T on X is said to be:

(i)

A left ternary equivalence relation if it is left reflexive, left symmetric, and left transitive;

(ii)

A middle ternary equivalence relation if it is middle reflexive, middle symmetric, and middle transitive;

(iii)

A right ternary equivalence relation if it is right reflexive, right symmetric, and right transitive.

The following definition and proposition provide a setting in which ternary equivalence relations naturally arise.

Definition 11. 

With any partition $\mathcal{P}$ of $X^2$, we associate the ternary relations $T_{\mathcal{l}}$, $T_m$ and $T_r$ on X defined as:

(i)

$T_{\mathcal{l}}=\{(x,y,z)\in X^3\mid (\exists \mathcal{C}\in \mathcal{P})((x,y)\in \mathcal{C}\wedge (x,z)\in \mathcal{C})\}$;

(ii)

$T_m=\{(x,y,z)\in X^3\mid (\exists \mathcal{C}\in \mathcal{P})((x,y)\in \mathcal{C}\wedge (y,z)\in \mathcal{C})\}$;

(iii)

$T_r=\{(x,y,z)\in X^3\mid (\exists \mathcal{C}\in \mathcal{P})((x,z)\in \mathcal{C}\wedge (y,z)\in \mathcal{C})\}$.

Proposition 19. 

For any partition $\mathcal{P}$ of $X^2$, the following statements hold:

(i)

$T_{\mathcal{l}}$ is a left ternary equivalence relation;

(ii)

$T_m$ is a middle ternary equivalence relation;

(iii)

$T_r$ is a right ternary equivalence relation.

Proof. 

We give the proof for (i). The left reflexivity and left symmetry of $T_{\mathcal{l}}$ are obvious. Next, we show that $T_{\mathcal{l}}$ is left transitive. Let $(x,y,t),(x,t,z)\in T_{\mathcal{l}}$; then, there exist $\mathcal{C},\mathcal{D}\in \mathcal{P}$ such that $(x,y),(x,t)\in \mathcal{C}$ and $(x,t),(x,z)\in \mathcal{D}$. Since $(x,t)\in \mathcal{C}\cap \mathcal{D}$, it holds that $\mathcal{C}=\mathcal{D}$. Hence, $(x,y)$ and $(x,z)$ belong to the same class, and, thus, $(x,y,z)\in T$. Therefore, $T_{\mathcal{l}}$ is left transitive. □

7. Conclusions

The composition of ternary relations has been a subject of debate within the literature, with various authors proposing definitions relevant to a given specific context. In recent work, we have introduced a comprehensive framework to study the composition of ternary relations, encompassing all possible four-point and five-point compositions. In this paper, we have explored three new types of compositions of ternary relations, inspired by the substitution of the underlying existential quantifier with the universal quantifier, an approach initially introduced by Bandler and Kohout in the binary case. In our study, we have examined these new compositions, showing their key properties, their relationship with the original Bandler–Kohout compositions of binary relations, their role in solving ternary relational equations, and, notably, their significance in defining the traces of ternary relations. Although Doignon’s definition of the traces of a binary relation did not explicitly incorporate the Bandler–Kohout compositions, we have observed a close connection. Leveraging this insight, we have introduced the traces of ternary relations. Finally, we have provided characterizations of several types of ternary equivalence relations.