# A Framework for the Approximation of Relations

Piero Pagliani

► To cite this version:

Piero Pagliani. A Framework for the Approximation of Relations. 4th International Conference on Intelligence Science (ICIS), Feb 2021, Durgapur, India. pp.49-65, 10.1007/978-3-030-74826-5_5 hal-03741721

HAL Id: hal-03741721

https://inria.hal.science/hal-03741721v1

Submitted on 1 Aug 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A framework for the approximation of relations

Piero Pagliani

pier.pagliani@gmail.com

**Abstract.** The paper proposes a foundation to the approximation of relations by means of relations. We discuss necessary, possible and sufficient approximations and show their links with other topics, such as refinement and simulation. The operators introduced in the paper has been tested on computers.

## 1 Introduction

Given a subset $X$ of a universe $U$, approximation techniques are required when for some reason the membership in $X$ of an arbitrary element $a$ of $U$ is not sharply decidable. Generally speaking, the disorienting factor is that $a$ is perceived within a contour, $C(a)$, of other elements of $U$. We use the terms “to perceive” to refer to any modality of acquiring and transforming uninterpreted data into interpreted pieces of information. To this end Rough Set Theory provides a pair of approximation operators: an element $a$ belongs to the lower approximation of $X$, if $C(a) \subseteq X$, while $a$ belongs to the upper approximation of $X$ if $C(a) \cap X \neq \emptyset$. The relations $\subseteq$ and $\cap$ are decided by the classical 0, 1-characteristic function (other possibilities are studied in the literature, such as fuzzy membership functions).

Rough Set Theory provides a 1-tier (Boolean) approximation mechanism. In a $n$-tier mechanism, any element $a'$ of $C_n(a)$ comes with its own contour $C_{n-1}(a')$, so that one can put that $a$ belongs to the $n$-lower approximation of $X$ if all or a sufficient number of the elements of its contour belong to the $n-1$ lower approximation of $X$, and so on. If $n=2$, for instance, one definition would prescribe that $a$ belongs to the 2-strict lower approximation of $X$ if $\forall a' \in C_2(a), C_1(a') \subseteq X$. A more general situation is given when the inclusion between a contour $C_2(a)$ and another contour $C_1(b)$ has to be decided for $a$ and $b$ belonging to different spaces dynamically linked in some way $\varphi$. Eventually, different criteria $\psi$ can be applied to decide inclusion, besides the classical one. We call this pattern pseudo-continuity because if $C_1(b)$ and $C_2(a)$ are topological open sets, the inclusion is the identity map and $\psi$ is the preimage $f^{-1}$ of some function $f$, it represents the usual notion of “continuity”:

<figure><img src="image_2.png" /><figcaption>Pseudo-continuity: the contour $C_2(a)$ is $\psi$-included in the contour $C_1(\varphi(a))$</figcaption></figure>

In addition, in the expression $C(a) \subseteq X$, $a$ belongs to the set of inputs of the perception process, while $C(a)$ is a subset of the outputs, as well as $X$. This is a subtle distinction is evident when $X$ is the output of another perception process. The proposed approach deals with the above considerations from a basic point of view.

## 2 Formalizing the problem

We assume that contours are the results of the application of sequences of constructors. A constructor maps an element (formally a singleton) onto a set of elements connected to it by a binary relation $R$. If $R \subseteq A \times B$, $A$ is called the domain of $R$, $dom(R)$, and $B$ the range, $ran(R)$. If $A = B$ then $R$ is called an endorelation or a homogeneous relation, otherwise it is called heterogeneous. If $X \subseteq A$, then $R(X) = \{b : \exists a \in X \wedge \langle a, b \rangle \in R\}$ is called the R-neighbourhood of $X$. If $X = \{x\}$ we write $R(x)$ instead of $R(\{x\})$. Thus, $\langle a, b \rangle \in R$ is also written $b \in R(a)$. R-neighbourhoods are the most elementary instances of 1-element
sequence. In (generalized) Rough Set Theory, the contours are given by an endorelation R on a universe A. Given X ⊆ A, the 1-tier lower approximation of X via R, (lR)(X), is the set of elements a of A such that R(a) is classically included in X: (lR)(X) = {a : R(a) ⊆ X} (or (lR)(X) = ⋃ {Y : R(Y) ⊆ X} since neighbourhood formation is additive). In this definition both the result (lR)(X) and X are subsets of A. But we have seen that there is a subtlety: (lR)(X) is a subset of A qua domain of R, while X is a subset of A qua range of R. The difference is hidden because R is an endorelation and because, literally speaking, X is a datum (meaning: what is given to our perception). Such an elusive difference stands out if R ⊆ A × B, for A ≠ B. Now (lR)(X) is a subset of A, while X is a subset of B. To overcome the problem one could change the definition as follows: (lR)∗(X) = ⋃ {R(a) : R(a) ⊆ X}. Incidentally, when R is an endorelation, (lR)(X) = (lR)∗(X) if and only if R is a preorder. If A ≠ B we maintain that the approximating set should be a subset of the domain of R while the approximated set is a subset of the range.

Moreover, we consider X not as a datum but as the result of some other perception mechanism. The most general situation is described by the relational schema

$$RS = (R \subseteq A \times B, Q \subseteq C \times D, W \subseteq A \times C, Z \subseteq B \times D)$$

which we call “Vitruvian” after Leonardo. We claim that this is sufficiently general a framework, because a number of additional situations can be accommodated in it.

<figure><img src="image_3.png" /></figure>

The present study deals with three main situations:

A) We have to find a subrelation R* ⊆ R which is coherent with the input-output processing of the reference relation Q, which runs parallel to R, according to a criterion with parameters in W and Z which provides a subset X of dom(R). We set R* = R ↕_X (R restricted to X), and call this task: unilateral approximation of relations.

B) The relation R is unknown. We have to reconstruct it according to a criterion with parameters in W, Z and Q. This task will be called reconstruction of relations.

C) The relation R is known and we have to approximate it with a relation R* by means of a criterion which provides simultaneously the inputs and the outputs of R*. We call this task bilateral approximation of relations.

We shall introduce a number of elementary operators described as follows:

**Specifications:** A formula made up of logical and set-theoretic operators. If any set-theoretical expression of the type X ⊆ Y is expressed by the first order formula ∀x(x ∈ X = ⇒ x ∈ Y) the term pre-specification is used.

**Pseudocodes:** The translation of a specification into a formula made up of operations on relations. It is a sort of high level description of the computing procedure.

**Procedures:** The translation of a pseudocode into a formula whose ingredients are only operations which can be performed as manipulations of Boolean matrices.

## 2.1 Operations on binary relations

We assume that the reader is familiar with the usual properties of binary relations.

In order to manipulate relations it is important the cardinalities of their domains and ranges. We say that R is of type A×B, written R : A×B, when the domain has cardinality |A| and the range |B|. It is assumed that when |dom(R)| = |dom(Q)| then dom(R) and dom(Q) are linked by an implicit 1-1 function so that the two domains can be identified with each other. Similarly for the ranges. This way the performability of an operation depends just on the cardinalities of the dimensions and not on the names of the elements and there is no need to distinguish between R ⊆ A × B and R : A × B. Therefore, R ⊆ A × B and Z ⊆ C × A will mean either that dom(R) = ran(Z), or that |dom(R)| = |ran(Z)| while on B and Z there are no special assumptions, and so on).

**Definition 1.** Let A, B, C be three sets. In what follows, a* is a dummy element of A and b* a dummy element of B and so on (that is, they represent any element of the set they belong to). Let R ⊆ A × B:
1. $\neg, \cap$ and $\cup$ are the usual set-theoretic operations. $R^\sim$ denotes the converse of $R$: $R^\sim := \{\langle y, x \rangle : \langle x, y \rangle \in R\}$. $1_{A \times B}$ is the top element of the set of relations of that type. $0_{A \times B} = -1_{A \times B}$ is the bottom element.

2. Let $X \subseteq A$. Then $R(X) = \{b : \exists x (x \in X \land \langle x, b \rangle \in R)\}$ - the Peirce product of $R$ and $X$, or $R$-neighbourhood of $X$, or $R$-granule of $X$

3. If $Q \subseteq B \times C$, then $R \otimes Q := \{\langle a, c \rangle : \exists b \in B(\langle a, b \rangle \in R \land \langle b, c \rangle \in Q)\}$ - the right composition of $R$ with $Q$. $Q(R(X)) = (R \otimes Q)(X)$ and $(R \otimes Q)^\sim = Q^\sim \otimes R^\sim$.

4. $Id_A := \{\langle a, a \rangle : a \in A\}$ (same for $Id_B$). If $R \subseteq A \times A$, we eventually write $Id_R$ instead of $Id_A$ and call it the identity or diagonal of $R$.

5. If $X \subseteq A$ then $X_A := \{\langle a, a \rangle : a \in X\}$ is called a test of $X$. It is a way to represent sets as relations. Therefore, $Id_A \cap Q$ is the test $X_A$ where $X = \{a : \langle a, a \rangle \in Q\}$.

6. Let $a^*$ and $b^*$ be dummy elements of $A$, resp. $B$. If $X \subseteq A$, then $X_R^\leftarrow := \{\langle a, b^* \rangle : a \in X \land b^* \in B\}$ is called the $R$-right cylinder of $X$. It is the relational embedding of $X$ in $R$. If $Y \subseteq B$, then $Y_R^\leftarrow := \{\langle a^*, y \rangle : y \in Y \land a^* \in A\}$ is the $R$-left cylinder of $Y$. It is the relational embedding of $Y$ in $R$.

If $A$ provides the dummy elements $a^*$ of a cylinder, then it will be also denoted by $A^*$. Therefore, $X_R^\leftarrow(B^*) = X_R^\leftarrow(b^*) = X$. Symmetrically, $Y_R^\leftarrow(A^*) = Y_R^\leftarrow(a^*) = Y$.

7. Given $R \subseteq A \times B$ and $Z \subseteq A \times C$ the right residual of $R$ and $Z$ id defined as

$$R \to Z = \{\langle b, c \rangle : \forall a(\langle a, b \rangle \in R \implies \langle a, c \rangle \in Z)\} = \{\langle b, c \rangle : R^\sim(b) \subseteq Z^\sim(c)\} \quad (1)$$

It is the largest relation $K : B \times C$ such that $R \otimes K \subseteq Z$:

$$R \otimes K \subseteq Z \quad \text{iff} \quad K \subseteq R \to Z. \quad (2)$$

If $R \subseteq A \times B$ and $W \subseteq C \times B$ the left residual of $R$ and $W$ is

$$W \leftarrow R = \{\langle c, a \rangle : \forall b(\langle a, b \rangle \in R \implies \langle c, b \rangle \in W)\} = \{\langle c, a \rangle : R(a) \subseteq W(c)\} \quad (3)$$

It is the largest relation $K : C \times A$ such that $K \otimes R \subseteq W$:

$$K \otimes R \subseteq W \quad \text{iff} \quad K \subseteq W \leftarrow R. \quad (4)$$

The above operations are usually presented within some algebraic structure (see [1]). But the carriers of these algebras consists of endorelations, while in our study we are interested mainly in heterogeneous relations. The following results can be easily proved (see [8]):

**Lemma 1.** Given $R \subseteq A \times B$, $W \subseteq A \times C$, $Q \subseteq C \times D$ and $Z \subseteq B \times D$:

(a) $R \to W = -(R^\sim \otimes -W)$

(b) $Q \leftarrow Z = -(-Q \otimes Z^\sim)$

(c) $R \to W = -R^\sim \leftarrow -W^\sim$

(d) $Q \leftarrow Z = -Q^\sim \to -Z^\sim$

**Corollary 1.** Let $R, W, Q$ and $Z$ be as above. Then:

(a) $(R \to W)^\sim = W^\sim \leftarrow R^\sim$

(b) $(Q \leftarrow Z)^\sim = Z^\sim \to Q^\sim$

(c) $Z \to (R \to W) = (R \otimes Z) \to W$

(d) $(Q \leftarrow Z) \leftarrow R = Q \leftarrow (R \otimes Z)$

**Corollary 2.** Given $R \subseteq A \times B$, $R \to R$ and $R^\sim \leftarrow R^\sim$ are preorders on $B$, $R^\sim \to R^\sim$ and $R \leftarrow R$ are preorders on $A$.

## 2.2 Perception constructors

Now we introduce three pairs of operators which are defined by means of a binary relation.

**Definition 2.** Let $R \subseteq A \times B$ be a binary relation, $X \subseteq A$, $Y \subseteq B$. The operators decorated with $\to$ transform subsets of $\wp(A)$ into subsets of $\wp(b)$, the operators decorated with $\leftarrow$ go the other way around. Then:

1. $\langle \to \rangle(X) = \{b : \exists a (a \in X \land \langle a, b \rangle \in R)\} = R(X)$ - the right possibility of $X$.

2. $\langle \leftarrow \rangle(Y) = \{a : \exists b (b \in Y \land \langle a, b \rangle \in R)\} = R^\sim(Y)$ - the left possibility of $Y$.

3. $\langle \to \rangle(X) = \{b : \forall a (a \in X \implies a \in X)\} = R \to X$ - the right necessity of $X$.

4. $\langle \leftarrow \rangle(Y) = \{a : \forall b (a \in X \implies b \in Y)\} = Y \leftarrow R$ - the left necessity of $Y$.

5. $\langle \to \rangle(X) = \{b : \forall a (a \in X \implies \langle a, b \rangle \in R)\} = X \to R$ - the right sufficiency of $X$.

6. $\langle \leftarrow \rangle(Y) = \{a : \forall b (b \in Y \implies \langle a, b \rangle \in R)\} = R \leftarrow Y$ - the left sufficiency of $Y$.
The above terminology is after Kripke models for modal logic and the basic logical readings of $A(x) \Rightarrow B(x)$: "in order to be $A$ it is necessary to be $B$" or "it is sufficient to be $A$ in order to be $B$". If $R$ is left total, $[\leftarrow]_R(Y) \subseteq \langle\leftarrow\rangle_R(Y)$. If $R$ is right total, $[\rightarrow]_R(X) \subseteq \langle\rightarrow\rangle_R(X)$.

We call the operators $\langle\bullet\rangle$, $[\bullet]$ and $[[\bullet]]$ constructors, where $\bullet$ is either $\rightarrow$ or $\leftarrow$. Left (resp. right) operators will be collectively denoted with $op^{\leftarrow}$ (resp. $op^{\rightarrow}$), eventually with the index "R". If $X = \{x\}$ we shall write $op(x)$ instead of $op(\{x\})$. The $\leftarrow$ decorated constructors "extensional" will be called "extensional" and the $\rightarrow$ decorated ones "intensional".

For a historical account of the above constructors in Rough Set Theory see [9]. For their connections with pointless topology and Intuitionistic Formal Spaces (see [10]). However, they were long known in Category Theory as examples of Galois Adjunctions (see [3]). This important and useful fact will be explained in the next Section.

Depending on the context, if $op_R$ is one of the above constructors, by extension we consider $op_R$ as a relation $dom(R) \times ran(R)$ defined as $\{\langle a, b \rangle : a \in dom(R) \wedge b \in op_R(a)\}$.

## 2.3 Perception constructors and Galois adjunctions

**Definition 3 (Galois adjunctions).** Let $O$ and $O'$ be two pre-ordered sets with order $\leq$, resp. $\leq'$ and $\sigma: O \mapsto O'$ and $\iota: O' \mapsto O$ be two maps such that for all $p \in O$ and $p' \in O'$

$$ \iota(p') \leq p \quad \text{iff} \quad p' \leq' \sigma(p) \qquad (5) $$

then $\sigma$ is called the upper adjoint of $\iota$ and $\iota$ is called the lower adjoint of $\sigma$. This fact is denoted by $O' \dashv\sigma O$ and we say that the pair $(\iota, \sigma)$ forms a Galois adjunction or an axiality.

From, (2) and (4) one immediately has that $\mathfrak{R}_{\text{ran}} \dashv^{\otimes R, \leftarrow R} \mathfrak{R}_{\text{ran}}$ and $\mathfrak{R}_{\text{dom}} \dashv^{\otimes R, \rightarrow R} \mathfrak{R}_{\text{dom}}$, where $\mathfrak{R}_{\text{ran}}$ ($\mathfrak{R}_{\text{dom}}$) is the set of relations with same range (domain), for $R \otimes (-) = R \otimes (-)$, $\rightarrow_R(-) = R \rightarrow (-)$, $(-) \otimes_R R = (-) \otimes R$ and $(-) \leftarrow_R R = (-) \leftarrow R$.

The contravariant version, i.e. $\iota(p') \geq p$ iff $p' \leq' \sigma(p)$ is called a Galois connection and $(\iota, \sigma)$ a polarity. Galois connections from binary relations were introduced in [6] and applied to data analysis in Formal Concept Analysis (FCA) (see [12]). Galois adjunctions have been introduced in classical Rough Set Theory in [4] with the name "dual Galois connections".

In what follows the decorations $\uparrow$ and $\downarrow$ inside the constructors denote opposite directions.

**Lemma 2.** For any relation $R$, $R' \subseteq A \times B$, $R \subseteq R'$, $X \subseteq A$, $Y \subseteq B$, for $D, D' \in \wp(A)$ or $\wp(B)$ with $D \subseteq D'$ and $a \in A$, $b \in B$:

$$ \wp(B) \dashv^{(\uparrow), [\downarrow]} \wp(A); \wp(B) \dashv [[\uparrow]][[\downarrow]] \wp(A)^{op}; \text{ If } \dashv^{\downarrow, \downarrow} \text{ then } \downarrow\downarrow \downarrow = \downarrow \text{ and } \downarrow\downarrow \downarrow\downarrow = \downarrow\downarrow \qquad (6) $$

$$ \langle\bullet\rangle(D) \subseteq \langle\bullet\rangle(D') \text{ and } [\bullet](D) \subseteq [\bullet](D'); D \subseteq D' \text{ implies } [[\bullet]](D') \subseteq [[\bullet]](D). \qquad (7) $$

$$ \langle\bullet\rangle \text{ and } [[\bullet]] \text{ are monotone in } R: \langle\bullet\rangle_R(D) \subseteq \langle\bullet\rangle_{R'}(D) \text{ and } [[\bullet]]_R(D) \subseteq [[\bullet]]_{R'}(D). \qquad (8) $$

$$ [\bullet] \text{ is antitone in } R: [\bullet]_{R'}(D) \subseteq [\bullet]_R(D). \qquad (9) $$

$$ \text{If } D = \{d\} \text{ then } [[\bullet]](D) = \langle\bullet\rangle(D) \qquad (10) $$

$$ b \in \langle\rightarrow\rangle(X) \text{ iff } R^-(b) \cap X \neq \emptyset, \quad a \in \langle\leftarrow\rangle(Y) \text{ iff } R(a) \cap Y \neq \emptyset \qquad (11) $$

$$ b \in [\rightarrow](X) \text{ iff } R^-(b) \subseteq X, \quad a \in [\leftarrow](Y) \text{ iff } R(a) \subseteq Y \qquad (12) $$

$$ b \in [[\rightarrow]](X) \text{ iff } X \subseteq R^-(b), \quad a \in [[\leftarrow]](Y) \text{ iff } Y \subseteq R(a) \qquad (13) $$

where $\wp(X)^{op}$ is $\wp(X)$ with reverse inclusion order.

**Proof.** Let us prove (6) (for the complete proof see [8]). Probably the most general proof comes from the fact that in Topos Theory, given a relation $R$, there are arrows which correspond (internally) to the constructors $\langle\bullet\rangle_R$ and $[\bullet]_R$ in the category of sets and total functions (see, for instance, [3], ch. 15). Together with the classical striking observation by William Lawvere in [5] that $\exists$ and $\forall$ are adjoint functors (via the intermediation of a substitution function), it is possible to prove the adjunction properties for the constructors. However, the set-theoretic proof is elementary: in view of (12) and additivity of Pierce products, $\langle\rightarrow\rangle(X) \subseteq Y$ iff $R(X) \subseteq Y$ iff $X \subseteq [\leftarrow](Y)$.
### 3 Approximating heterogeneous relations

The main topic of the paper is the lower approximation of relations organized in a Vitruvian schema by means of the pseudo-continuity pattern. Different modes of pseudo-continuity are definable by different concatenations of perception constructors, which we call sequences. A sequence $C_R^X$ is an algebraic combination of relations starting with a constructor defined by the relation $R$, with input in $dom(R)$ and output in the set $X$.

*Example 1.* The following Vitruvian schema $RS$ will be used throughout the paper:

<table><thead><tr><th></th><th></th><th></th><th></th><th></th><th colspan="2">D</th><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td></td><td>l</td><td></td><td>0</td><td>0</td><td>1</td></tr><tr><td></td><td>0</td><td>1</td><td>0</td><td>1</td><td></td><td>i</td><td></td><td>0</td><td>1</td><td>1</td></tr><tr><td></td><td>1</td><td>0</td><td>0</td><td>1</td><td></td><td>h</td><td></td><td>1</td><td>0</td><td>1</td></tr><tr><th>C</th><th>λ</th><th>κ</th><th>ι</th><th>θ</th><th colspan="2">Q / Z</th><th></th><th>a</th><th>b</th><th>c</th><th>B</th></tr><tr><td></td><td></td><td></td><td></td><td></td><td colspan="2">α</td><td></td><td>1</td><td>0</td><td>1</td><td></td></tr><tr><td></td><td>0</td><td>0</td><td>0</td><td>1</td><td colspan="2">β</td><td></td><td>0</td><td>0</td><td>1</td><td></td></tr><tr><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td colspan="2">γ</td><td></td><td>1</td><td>1</td><td>0</td><td></td></tr><tr><td></td><td>0</td><td>1</td><td>1</td><td>1</td><td colspan="2">δ</td><td></td><td>0</td><td>1</td><td>1</td><td></td></tr><tr><td></td><td>0</td><td>1</td><td>0</td><td>0</td><td colspan="2">A</td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

### 4 Unilateral lower approximation operators

The overall idea is to identify a subset $X$ of elements of $dom(R)$ whose outputs through $R$ are coherent with those of their counterparts in $dom(Q)$, according to a given criterion $\rho$. The restriction of $R$ to $X$, $R|_{X}:= X_A \otimes R$, represents the approximation of $R$ as it is reflected by $Q$ according to $\rho$. If $dom(R) \neq dom(Q)$ a criterion which compares $R$ and $Q$ by connecting their domains using $W$ will be called nominal, generic otherwise. Both of them can be existentially or universally quantified on $C$. These operators will output subsets of $dom(R) \times dom(R)$, say $R^-$, which will be transformed by means of the operation $Id_A \cap R^-$ into a test $X_A$ where $X$ is the set of elements $a \in A$ for which the criterion $\rho$ holds. If $app(X) = \{\langle a, a \rangle\dots\}$ we shall write $a \in app(X)$ instead of $\langle a, a \rangle \in app(X)$, for app an approximation operator. Now, for any formula $X \subseteq Y$ a question arises as to for how many elements of $X$ or how many elements of $Y$ does the inclusion hold. The possible answers are: 1) at least one, 2) at least all, 3) at most all. Therefore the operators will be classified on the basis of their modal characters: necessity, possibility, sufficiency.

**Definition 4.** Suppose $R \subseteq A \times B$, $X \subseteq A$ and $Y \subseteq B$:

<table><thead><tr><th>Definition</th><th>Denotation</th><th>Definition</th><th>Denotation</th></tr></thead><tbody><tr><td>$X \subseteq [\leftarrow]_R(Y)$</td><td>$X \subseteq_{[\leftarrow]_R} Y$<br>necessary inclusion</td><td>$[\rightarrow]_R(X) \subseteq Y$</td><td>$X \subseteq_{[\rightarrow]_R} Y$<br>inverse necessary inclusion</td></tr><tr><td>$X \subseteq \langle\leftarrow\rangle_R(Y)$</td><td>$X \subseteq_{\langle\leftarrow\rangle_R} Y$<br>possible inclusion</td><td>$\langle\rightarrow\rangle_R(X) \subseteq Y$</td><td>$X \subseteq_{\langle\rightarrow\rangle_R} Y$<br>inverse possible inclusion</td></tr><tr><td>$X \subseteq [[\leftarrow]]_R(Y)$</td><td>$X \subseteq_{[[\leftarrow]]_R} Y$<br>sufficient inclusion</td><td>$[[\rightarrow]]_R(X) \subseteq Y$</td><td>$X \subseteq_{[[\rightarrow]]_R} Y$<br>inverse sufficient inclusion</td></tr></tbody></table>

The following equivalences hold because of adjunction or connection relations:

$$ (1) \quad X \subseteq_{[\leftarrow]_R} Y \equiv X \subseteq_{\langle\rightarrow\rangle_R} Y. $$

$$ (2) \quad X \subseteq_{[[\leftarrow]]_R} Y \equiv Y \subseteq_{[[\rightarrow]]_R} X. $$

For $S \subseteq B \times A$ symmetric modalized inclusions can be defined, such as $X \subseteq [\rightarrow]_S(Y)$, that is, $X \subseteq_{[-]_S} Y$ (co-necessary inclusion). From now on we shall deal just with inclusions decorated by $R$. Thus, by default the subscript of the constructors will be $R$.
**Lemma 3.**

<table><tr><td>(a) X &sub; [←] Y iff R(X) &sub; Y</td><td>(b) X &sub; [→] Y iff &forall;b(R~(b) &sub; X &rarr; b &isin; Y)</td></tr><tr><td>(c) X &sub; &lt;←&gt; Y iff X &sub; R~(Y)</td><td>(d) X &sub; &lt;→&gt; Y iff R(X) &sub; Y</td></tr><tr><td>(e) X &sub; [[←]] Y iff Y &sub; &cap;{R(a)}<sub>a&isin;X</sub></td><td>(f) X &sub; [[→]] Y iff &forall;b(X &sub; R~(b)) &rarr; b &isin; Y</td></tr></table>

*Proof.* (a): By adjunction $X &sub; [←](Y)$ iff $\langle→\rangle(X) &sub; Y$ which in turn is trivially equivalent by definition to $R(X) &sub; Y$. (b): Because $b &isin; [→](Y)$ iff $R~(b) &sub; X$. (c): By definition. (d): By definition or because by adjunction it is equivalent to (a). (e): $X &sub; [[←]](Y)$ iff $\forall a &isin; X, Y &sub; R(a)$ iff $Y &sub; &cap;{R(a)}<sub>a&isin;X</sub>$. (f): By reversing the inclusion of (b).

As to the comparative strength of the above modalized inclusions, see [8], where also the isotone and antitone behaviours of the modalized inclusion operators are discussed.

**Coding the modalized inclusions.** In what follows we shall deal only with 1-element sequences so that contours are simply relational neighbourhoods. The following lemma exhibits the skeleton of the pseudo-codes of the approximation operators we will discuss:

**Lemma 4.** Let RS be as above. Then:

$$R(a) \subseteq_{[\leftarrow]_Z} Q(c) \quad \text{iff} \quad \langle c, a \rangle \in (Q \leftarrow Z) \leftarrow R \qquad (14)$$

$$R(a) \subseteq_{\langle\leftarrow\rangle_Z} Q(c) \quad \text{iff} \quad \langle c, a \rangle \in (Q \otimes Z^\sim) \leftarrow R \qquad (15)$$

$$R(a) \subseteq_{[[\leftarrow]]_Z} Q(c) \quad \text{iff} \quad \langle c, a \rangle \in (Q \sim \rightarrow Z^\sim) \leftarrow R \qquad (16)$$

$$R(a) \subseteq^{[\rightarrow]_Z} Q(c) \quad \text{iff} \quad \langle c, a \rangle \in Q \leftarrow (R \leftarrow Z^\sim) \qquad (17)$$

$$R(a) \subseteq_{\langle\rightarrow\rangle_Z} Q(c) \quad \text{iff} \quad \langle c, a \rangle \in (Q \leftarrow Z) \leftarrow R \qquad (18)$$

$$R(a) \subseteq^{[[\rightarrow]]_Z} Q(c) \quad \text{iff} \quad \langle c, a \rangle \in Q \leftarrow (R \sim \rightarrow Z) \qquad (19)$$

*Proof.* We prove just (14): $R(a) \subseteq_{[\leftarrow]_Z} Q(c)$ iff $\forall b (b \in R(a) \implies (Z(b) \subseteq Q(c)))$. From (3) this holds iff $R(a) \subseteq (Q \leftarrow Z)(c)$ iff $\langle c, a \rangle \in (Q \leftarrow Z) \leftarrow R$.

## 4.1 Nominal unilateral lower approximation operators

The philosophy of nominalization suggests applying the quantifiers only to C, through $W(a)$, because its meaning is “for all possible C- avatar of a ...”. We obtain 12 approximation operators, which produce subsets of the domain of R.

### Specifications

**Definition 5.** Let RS be as above.

$$(\lnunQ)_{W,Z}(R) := \{a : \forall c \in W(a) \implies (R(a) \subseteq_{[\leftarrow]_Z} Q(c))\} \qquad (20)$$

$$(\lnupQ)_{W,Z}(R) := \{a : \forall c \in W(a) \implies R(a) \subseteq_{\langle\leftarrow\rangle_Z} Q(c)\} \qquad (21)$$

$$(\lnusQ)_{W,Z}(R) := \{a : \forall c \in W(a) \implies (R(a) \subseteq_{[[\leftarrow]]_Z} Q(c))\} \qquad (22)$$

$$(\linunQ)_{W,Z}(R) := \{a : \forall c \in W(a) \implies (R(a) \subseteq^{[\rightarrow]_Z} Q(c))\} \qquad (23)$$

$$(\lnenQ)_{W,Z}(R) := \{a : \exists c \in W(a) \wedge (R(a) \subseteq_{[\leftarrow]_Z} Q(c))\} \qquad (24)$$

$$(\lnepQ)_{W,Z}(R) := \{a : \exists c \in W(a) \wedge (R(a) \subseteq_{\langle\leftarrow\rangle_Z} Q(c))\} \qquad (25)$$

$$(\lnesQ)_{W,Z}(R) := \{a : \exists c \in W(a) \wedge (R(a) \subseteq_{[[\leftarrow]]_Z} Q(c))\} \qquad (26)$$

$$(\linepQ)_{W,Z}(R) := \{a : \exists c \in W(a) \wedge R(a) \subseteq^{\langle\rightarrow\rangle_Z} Q(c)\} \qquad (27)$$

The naming rule is the following: “l” stands for “lower”; before Q we have: “n” for “necessary”, p for “possible” and “s” for “sufficient”. The “n” after the “l” stands for “nominal”, “i” for “inverse”, “u” for “universal” and “e” for “existential”. The term “direct” is not used either in the names or in the acronyms. Here are two examples:

($\lnunQ)_{W,Z}(R)$ (direct) nominal universal necessary lower approximation of R via Q.

($\linepQ)_{W,Z}(R)$ inverse nominal existential possible lower approximation of R via Q.
Notice, for example, that since $X \subseteq Y \land X \subseteq Y'$ if and only if $X \subseteq Y \land Y'$ one has that $a \in (\lnunQ)_{W,Z}(R)$ if and only if $Z(R(a)) \subseteq \bigcap \{Q(c)\}_{c \in W(a)}$. The existential version of this operator fulfils the same relation but relaxed to single results of $Q$. This situation is illustrated by the picture on the right where the existential pattern is indicated by $\exists$ and the universal one by $\forall$.

<figure><img src="image_4.png" /></figure>

The restriction of $R$ to $X \subseteq A$ is defined as $R \upharpoonright_X = \{a \in X \land \langle a, b \rangle \in R\}$. In view of Definition 2 and Lemma 2, the following sample reading is straightforward:

If $X = (\lnunQ)_{W,Z}(R)$ then $\langle a, b \rangle \in R \upharpoonright_X \text{ iff } Z(R(a)) \subseteq Q(c)$, any $c \in W(a)$

From Lemma 4 the pseudo-codes can be easily derived:

**Theorem 1.**

$$ (\lnunQ)_{W,Z}(R) = (Id_A \cap (W \sim \rightarrow (Q \leftarrow Z) \leftarrow R))(A) \qquad (28) $$

$$ (LnupQ)_{W,Z}(R) = (Id_A \cap (W \sim \rightarrow (Q \otimes Z) \leftarrow R))(A) \qquad (29) $$

$$ (lnusQ)_{W,Z}(R) = (Id_A \cap (W \sim \rightarrow (Q \sim \rightarrow Z \sim \leftarrow R))(A) \qquad (30) $$

$$ (linunQ)_{W,Z}(R) = (Id_A \cap (W \sim \rightarrow Q \leftarrow (R \leftarrow Z \sim)))(A) \qquad (31) $$

$$ (lnenQ)_{W,Z}(R) = (Id_A \cap (W \otimes ((Q \leftarrow Z) \leftarrow R)))(A) \qquad (32) $$

$$ (lnepQ)_{W,Z}(R) = (Id_A \cap (W \otimes ((Q \otimes Z) \leftarrow R)))(A) \qquad (33) $$

$$ (lnesQ)_{W,Z}(R) = (Id_A \cap (W \otimes (Q \sim \rightarrow Z \sim \leftarrow R))(A) \qquad (34) $$

$$ (linepQ)_{W,Z}(R) = (Id_A \cap (W \otimes ((Q \leftarrow Z) \leftarrow R))(A) \qquad (35) $$

*Proof.* We give just one example (straightforward consequence of Lemma 4):

$$ \begin{aligned} (\lnunQ)_{W,Z}(R) &= \{\langle a, a \rangle : \forall c (c \in W(a) \implies (R(a) \subseteq_{[-]_Z} Q(c))) \} \\ &= \{\langle a, a \rangle; \forall c (\langle a, c \rangle \in W \implies \langle c, a \rangle \in (Q \leftarrow Z) \leftarrow R) \} \\ &= \{\langle a, a \rangle : \langle a, a \rangle \in W \sim \rightarrow ((Q \leftarrow Z) \leftarrow R) \} \\ &= Id_A \cap (W \sim \rightarrow ((Q \leftarrow Z) \leftarrow R)) \end{aligned} $$

The $\exists \forall$ definition of nominal existential lower approximation operators is a strong requirement: a single element must fit different paths. The weaker requirement $\forall \exists$ is provided by inverse inclusion operators applied to the composition of $W$ and $Q$, which we call $\Pi$-operators (after the arithmetical hierarchy) or *infix existential operators*:

$$ \begin{aligned} R(a) \subseteq_{W}^{\overrightarrow{opZ}} Q(c) \quad \text{iff} \quad & \forall d (d \in \overrightarrow{opZ}(R(a)) \implies \exists c (c \in W(a) \land d \in Q(c))) \\ & \text{iff} \quad R(a) \subseteq_{\overrightarrow{opZ}}^{\overrightarrow{opZ}} Q(W(a)) \end{aligned} \qquad (36) $$

An interesting example is: $(ilinepQ)_{W,Z}(R) := \{a : R(a) \subseteq_{W}^{\leftarrow} Q(c)\}$ whose pseudo-code is $\{a : \langle a, a \rangle \in (W \otimes Q) \leftarrow (R \otimes Z)\}$. By adjointness it coincides with $(ilnenQ)_{W,Z}(R) = \{a : R(a) \subseteq_{W}^{\leftarrow} Q(c)\} := \{a : R(a) \subseteq_{[-]_Z} Q(W(a))\} = \{a : \forall b (b \in R(a) \implies Z(b) \subseteq Q(W(a)))\}$.

In turn, $(ilnesQ)_{W,Z}(R) := \{a : R(a) \subseteq_{W}^{\overrightarrow{[\overrightarrow{-}]_Z}} Q(c)\} = \{a : R(a) \subseteq_{\overrightarrow{[\overrightarrow{-}]_Z}} Q(W(a))\}$ which is equal to $(lnusQ)_{W,Z}(R)$. Finally, $(ilnepQ)_{W,Z}(R) = \{a : R(a) \subseteq (W \otimes Q \otimes Z)\}(a) = \{a : \langle a, a \rangle \in (W \otimes Q \otimes Z) \leftarrow R\}$. It is a simple operator which states that $R(a)$ is a subset of the complete tour of $a$ along the Vitruvian schema. This kind of existential operators exhibit interesting geometric patterns which are part of the link between the present theory of approximation of relations and Process Algebra.

## 4.2 Generic unilateral lower approximation operators

Let $RS$ be as above. The generic versions of the above approximation operators are obtained by substituting "$\forall c(...$" and "$\exists c(...$" for $\forall c(c \in W(a) \implies ...)$ and, respectively, $\exists c(c \in W(a) \land ...)$". Their names are the same as their corresponding nominal companions, with $n$ (nominal) replaced by $g$ (generic). For instance $(lgunQ)_{Z}(R) := \{a : \forall c(R(a) \subseteq_{[-]_Z} Q(c))\}$. Hence the relation $W$ does not play any role and can be replaced with $\mathbf{1}_{A \times C}$ and $\mathbf{1}_{C \times A}$. Therefore, one obtains $(lgunQ)_{Z}(R) = (Id_A \cap (\mathbf{1}_{C \times A} \rightarrow ((Q \leftarrow Z) \leftarrow R))(A)$.
## 4.3 Computing procedure

The outputs of the above operators are tests $X_A$ for $X \subseteq A$, that is, they are subsets of the diagonal of $A \times A$, while the actual inclusions are provided by the basic equations (14), (15) and (16), which form what we call the inner part of the core formulas of the operators, which, in turn, are the expressions on the right of “$Id_A \cap$”. Note that the pseudo-codes and specifications of the main core formulas are (for nominal operators):

$$W \sim \rightarrow (Q \leftarrow Z) \leftarrow R = \{\langle a, a' \rangle : \forall c \in W(a) \Rightarrow (R(a') \subseteq_{[\leftarrow]_Z} Q(c))\}$$

$$W \sim \rightarrow (Q \otimes Z \sim) \leftarrow R = \{\langle a', a \rangle : \forall c \in W(a) \Rightarrow (R(a') \subseteq_{\langle \leftarrow \rangle_Z} Q(c))\}$$

$$(R \sim \rightarrow Z \leftarrow Q) \leftarrow W = \{\langle a', a \rangle : \forall c \in W(a) \Rightarrow (R(a') \subseteq_{[[\leftarrow]]_Z} Q(c))\}$$

$$((R \otimes Z) \leftarrow Q) \leftarrow W = \{\langle a', a \rangle : \forall c \in W(a) \Rightarrow (R(a') \subseteq_{[[\leftarrow]]^R} Q(c))\}$$

This explains why one has to select the elements of the form $\langle x, x \rangle$ out of the results of the core formulas, by applying $Id_A \cap$.

Now we show step by step the computing procedure of a lower approximation operator, illustrated using the relational schema of Example 1. Consider $(lnunQ)_{W,Z}(R)$.

1) Pseudo-code: $W \sim \rightarrow (Q \leftarrow Z) \leftarrow R$.

2) Procedure: $-(W \otimes -Q \otimes Z \sim \otimes R \sim)$.

3) Checking the type of the relational expression:

$$\begin{array}{c|cccccc}
W & \otimes & Q & \otimes & Z^{\sim} & \otimes & R^{\sim} \\
\hline
A \times C & \otimes & C \times D & \otimes & D \times B & \otimes & B \times A \\
\hline
& A \times D & & \otimes & D \times A & & \\
\hline
& & & & A \times A & &
\end{array}$$

The steps of computation run as follows:

$$\begin{array}{c|ccc|ccc|ccc}
W \otimes -Q & h & i & l & W \otimes -Q \otimes Z^{\sim} & a & b & c & W \otimes -Q \otimes Z^{\sim} \otimes R^{\sim} & \alpha & \beta & \gamma & \delta \\
\hline
\alpha & 0 & 0 & 0 & \alpha & 0 & 0 & 0 & \alpha & 0 & 0 & 0 & 0 \\
\beta & 1 & 1 & 0 & \beta & 1 & 1 & 1 & \beta & 1 & 1 & 1 & 1 \\
\gamma & 1 & 1 & 0 & \gamma & 1 & 1 & 1 & \gamma & 1 & 1 & 1 & 1 \\
\delta & 1 & 0 & 0 & \delta & 1 & 0 & 1 & \delta & 1 & 1 & 1 & 1 \\
\hline
-(W \otimes -Q \otimes Z^{\sim} \otimes R^{\sim}) & \alpha & \beta & \gamma & \delta & \alpha & \beta & \gamma & \delta & \alpha & \beta & \gamma & \delta \\
\hline
\alpha & & 1 & 1 & 1 & 1 & & & & \alpha & & & \\
\beta & & 0 & 0 & 0 & 0 & & & & \beta & & & \\
\gamma & & 0 & 0 & 0 & 0 & & & & \gamma & & & \\
\delta & & 0 & 0 & 0 & 0 & & & & \delta & & & \\
\hline
\end{array}$$

It follows that $(lnunQ)_{W,Z}(R) = \{a\}$.

## 4.4 Unilateral upper approximation operators

Unilateral upper approximation operators are given by considering “$R(a) \subseteq$” as a function $F$ with “$op(Q(c))$” its argument $X$ and tacking its dual $-(F(-X))$. Let us see some results:

### Definition 6.

1. $(unupQ)_{W,Z}(R) := \{a : \forall c \in W(a) \Rightarrow R(a) \cap_{\langle \leftarrow \rangle_Z} Q(c) \neq \emptyset\}$

2. $(unusQ)_{W,Z}(R) := \{a : \forall c \in W(a) \Rightarrow R(a) \cap_{[[\leftarrow]]_Z} Q(c) \neq \emptyset\}$

3. $(unepQ)_{W,Z}(R) := \{a : \exists c \in W(a) \wedge R(a) \cap_{\langle \leftarrow \rangle_Z} Q(c) \neq \emptyset\}$

4. $(uinupQ)_{W,Z}(R) := \{a : \forall c \in W(a) \Rightarrow R(a) \cap_{\langle \rightarrow \rangle_Z} Q(c) \neq \emptyset\}$

5. $(uinusQ)_{W,Z}(R) := \{a : \forall c \in W(a) \Rightarrow R(a) \cap_{[[\rightarrow]]_Z} Q(c) \neq \emptyset\}$

6. $(uinepQ)_{W,Z}(R) := \{a : \exists c \in W(a) \wedge R(a) \cap_{\langle \rightarrow \rangle_Z} Q(c) \neq \emptyset\}$

7. $(uinesQ)_{W,Z}(R) := \{a : \exists c \in W(a) \wedge R(a) \cap_{[[\rightarrow]]^R} Q(c) \neq \emptyset\}$

We present the pseudo-codes of the upper approximation operators in a slightly different way: instead of setting $Id_A \cap core\ formula$ and project the result on the domain $A$, we state “$\{a : \langle a, a \rangle \in core\ formula\}$”.

### Lemma 5.

$$(a) (unupQ)_{W,Z}(R) = \{a : \langle a, a \rangle \in (R \otimes Z \otimes Q^{\sim}) \leftarrow W\}$$
$$ (b) \ (unusQ)_{W,Z}(R) = \{a : \langle a, a \rangle \in ((R \otimes (Z \leftarrow Q))) \leftarrow W \} $$

$$ (c) \ (unepQ)_{W,Z}(R) = \{a : \langle a, a \rangle \in R \otimes Z \otimes Q \sim \otimes W \sim \} $$

$$ (d) \ (uinupQ)_{W,Z}(R) = (unupQ)_{W,Z}(R) $$

$$ (e) \ (uinusQ)_{W,Z}(R) = \{a : \langle a, a \rangle \in ((R \sim \rightarrow Z) \otimes Q \sim)) \leftarrow W \} $$

$$ (f) \ (uinepQ)_{W,Z}(R) = (unepQ)_{W,Z}(R) $$

$$ (g) \ (uinesQ)_{W,Z}(R) = \{a : \langle a, a \rangle \in ((R \sim \rightarrow Z) \otimes Q \sim \otimes W \sim) \} $$

## 4.5 The injective cases

By “injective case” we intend when the connections between A and C or B and D are given by possibly partial injective functions $\varphi: A \mapsto C$ and, respectively, $\psi: B \mapsto D$. We consider as domains or ranges of R and Q the images and pre-images of these functions. We can get rid of the functions, therefore, by renaming any element $c \in C$ with the unique member of its pre-image $\varphi^{-1}(c)$ or $\psi^{-1}(d)$. Thus $\varphi$ or $\psi$ can be substituted by the identity relations $Id_A$, respectively $Id_B$ and we write $A =_{Id} C$ or $B =_{Id} D$.

The resulting approximation operators depend on a cancellation rule which is detailed in [8] and which can be described as follows: one or both the parameters W and Z can be deleted according to the fact that for any $R_1$ and $R_2$ of the appropriate type $R_1 \otimes Id = R_1$ and $Id \otimes R_2 = R_2$ (cf. Definition 1.(4)) and $Id \sim = Id$. On the contrary, $R_1 \otimes -Id \neq R_1$ and $-Id \otimes R_2 \neq R_2$. There are three possible situations:

### B =$_{Id} D$ and Z = $Id_B$: deleting Z

One result of the cancellation rule is, for instance:

$$ \begin{aligned} (lnunQ)_W(R) &= (lnupQ)_W(R) = (linunQ)_W(R) = (linupQ)_W(R) = \\ &= (Id_A \cap (W \sim \rightarrow Q \leftarrow R))(A) \tag{37} \\ &= \{a : \forall c \in W(a) \implies (R(a) \subseteq Q(c))\} = \{a : W(a) \subseteq [[\leftarrow]]_Q R(a)\} \end{aligned} $$

### A =$_{Id} C$ and W = $Id_A$: deleting W

In nominal operators the parameter W can be freely cancelled because it appears always as the premise of a residuation or as an argument of a composition. For instance:

$$ \begin{aligned} (lnunQ)_Z(R) &= (lnenQ)_Z(Q) = (linupQ)_Z(R) = (lnenQ)_Z(R) = (linepQ)_Z(R) \\ &= (Id_A \cap ((Q \leftarrow Z) \leftarrow R))(A) = \{a : R(a) \subseteq [[\leftarrow]]_Z Q(a)\} \end{aligned} \tag{38} $$

Generic approximation operators do not use the parameter W and remain unchanged.

**2-tier approximations.** Consider now two relations $R \subseteq A \times B$ and $Z \subseteq B \times D$. An element $a$ of A belongs to the 2-strict lower approximation of a set $X \subseteq D$ if for all elements $b \in R(a)$, $Z(b) \subseteq X$. Since neighbourhoods are additive, this leads to the set $\{a : Z(R(a)) \subseteq X\}$. It follows from (38) and Lemma 3 that if $X = Q(x)$ for some relation $Q$ with range $D$, the 2-strict lower approximation is given by $(lnunQ)_Z(R)$ and its equivalent fellows.

*Example 2.* In our sample relational frame, $Z(R(\alpha)) = Z(R(\beta)) = Z(R(\gamma)) = Z(R(\delta)) = \{h, i, l\}$. Hence, an element of A belongs to the 2-strict lower approximation of $Q(\theta)$ only.

A =$_{Id} C$ and B =$_{Id} D$: deleting W and Z When $RS = (R \subseteq A \times B, W = Id_A, Q \subseteq A \times B, Z = Id_B)$ we simply have:

$$ \begin{aligned} (lnunQ)(R) &= (lnupQ)(R) = (lnenQ)(R) = (lnepQ)(R) = (lgunQ)(R) = (genQ)(R) \\ &= \{a : R(a) \subseteq Q(a)\} = (Id_A \cap (Q \leftarrow R))(A) \end{aligned} $$

The “generic” operators are computed as in the case of the deletion of Z but without the use of the normalizing parameters $1_{A \times C}$ and $1_{C \times A}$.

## 5 Reconstruction of a relation

If we are not given the relation $R$, we can reconstruct it by postulating that the elements of A and B are related by $R$ if their $W$ and, respectively, $Z$ counterparts are related by $Q$:

$$ \{\langle a, b \rangle : \forall c, d \in W(a) \wedge d \in Z(b) \implies d \in Q(c)\} \tag{39} $$
From (39) we obtain:

$$ \{\langle a, b \rangle : \forall c(c \in W(a) \implies (Z(b) \subseteq Q(c)))\} = W \rightsquigarrow Q \leftarrow Z \qquad (40) $$

The pseudo-code of (40) is the converse of (16) with $R$ replaced by $W$, $Z$ by $Q$ and $Q$ by $Z$. This story teaches three things. First, it brings to the notion of a lower sufficient reconstruction of $R$ via $W$ and $Z$ as lateral relations and $Q$ as “reference” relation:

$$ (\mathrm{lsrWZ})_Q(R) := \{\langle a, b \rangle : W(a) \subseteq [[\leftarrow]]_Q Z(b)\} \qquad (41) $$

Second, let us set the following binary hyper-relation:

$$ H_{WZ} = \{\langle\langle a, b \rangle, \langle c, d \rangle\rangle : \langle a, c \rangle \in W \wedge \langle b, d \rangle \in Z\} \qquad (42) $$

then (39) is equivalent to $\{\langle a, b \rangle : H_{WZ}(\langle a, b \rangle) \subseteq Q\}$. So $(\mathrm{lsrWZ})_Q(R)$ is a sort of lower approximation. Actually, it is a generalisation/specialisation of the classical approach to rough relations proposed in [11] because it takes into account arbitrary but binary relations. Third, it is evident that $(\mathrm{lsrWZ})_Q(R)$ is the part of the core formula of $(\mathrm{lnunQ})_{W,Z}(R)$ which is on the left of $\leftarrow R$. This observation suggests that when $R$ is detachable from the core formula of a nominal approximation operator, a kind of reconstruction is obtained. We say that a relation $R$ is detachable from a formula $F(R, W, Z, Q)$ if the remaining part is still computable (that is, the types of the remaining part are coherent). Let us examine the seven independent results, including $(\mathrm{lsrWZ})_Q(R)$.

From $(\mathrm{lnupQ})_{W,Z}(R)$ one obtains $W \rightsquigarrow (Q \otimes Z) = \{\langle a, b \rangle : \forall c(c \in W(a) \implies \exists d(d \in Z(b) \wedge d \in Q(c)))\}$. Its converse pseudo-code, $(Z \otimes Q) \leftarrow W$, is an instance of (15), that is, a possibility inclusion. Hence we set the following definition:

$$ \textit{Lower possible reconstruction of } R: (\mathrm{lprWZ})_Q(R) := \{\langle a, b \rangle : W(a) \subseteq [[\leftarrow]]_Q Z(b)\} $$

From $(\mathrm{lnusQ})_{W,Z}(R)$ one obtains $W \rightsquigarrow (Q \rightsquigarrow Z) = \{\langle a, b \rangle : \forall d \exists c(c \in W(a) \wedge d \in Q(c) \implies d \in Z(b))\}$. Its converse formulation $(Z \leftarrow Q) \leftarrow W$ is equivalent to $Z \leftarrow (W \otimes Q)$. From (14) it turns out to be a necessity inclusion, so that we define:

$$ \textit{Lower necessary reconstruction of } R: (\mathrm{lnrWZ})_Q(R) := \{\langle a, b \rangle : W(a) \subseteq [[\leftarrow]]_Q Z(b)\} $$

From $(\mathrm{lnenQ})_{W,Z}(R)$ let us detach $W \otimes (Q \leftarrow Z) = \{\langle a, b \rangle : \exists c(c \in W(a) \wedge \forall d(d \in Z(b) \implies d \in Q(c)))\}$. It is an instance of a sufficient intersection so that we define:

$$ \textit{Upper sufficiency reconstruction of } R: (\mathrm{usrWZ})_Q(R) := \{\langle a, b \rangle : W(a) \cap [[\leftarrow]]_Q Z(b) \neq \emptyset\} $$

From $(\mathrm{lnesQ})_{W,Z}(R)$ one obtains $W \otimes (Q \rightsquigarrow Z) = \{\langle a, b \rangle : \exists c(c \in W(a) \wedge \forall d(d \in Q(d) \implies b \in Z(d)))\}$. It is an instance of a necessary intersection, therefore we define:

$$ \textit{Upper necessary reconstruction of } R: (\mathrm{unrWZ})_Q(R) := \{\langle a, b \rangle : W(a) \cap [[\leftarrow]]_Q Z(b) \neq \emptyset\} $$

In turn, $(\mathrm{ilnenQ})_{W,Z}(R)$ gives $(W \otimes Q) \leftarrow Z = \{\langle a, b \rangle : \forall d(d \in Z(b) \implies \exists c(c \in W(a) \wedge d \in Q(c)))\}$. Thus a sort of co-possible inclusion is obtained and we set:

$$ \textit{Lower co-possible reconstruction of } R: (\mathrm{lcprZW})_Q(R) := \{\langle a, b \rangle : Z(b) \subseteq [[\to]]_Q W(a)\} $$

Notice the use of the co-inclusion operator $\subseteq_{\leftarrow}^Q$.

Other reconstructions are definable by detaching $R \otimes$ from upper approximations, with some surprises. For instance, if $R \otimes$ is detached from the core formula of $(\mathrm{unepQ})_{W,Z}(R)$ or $(\mathrm{uinepQ})_{W,Z}(R)$, or $R \to$ is detached from the core formula of $(\mathrm{uinesQ})_{W,Z}(R)$ then one obtains $Z \otimes Q \rightsquigarrow W \rightsquigarrow$ which is of type $B \times C$. We transpose it and define:

$$ (\mathrm{dirWZ})_Q(R) = W \otimes Q \otimes Z = \{\langle a, b \rangle : W(a) \cap [[\to]]_Q Z(b) \neq \emptyset\} \qquad (43) $$

Therefore, $(\mathrm{dirWZ})_Q(R)$ can be called inverse possible reconstruction of $R$. $(\mathrm{dirWZ})_Q(R)$ is also obtained by detaching $\leftarrow R$ from $(\mathrm{ilnenQ})_{W,Z}(R)$ and $(\mathrm{lprWZ})_Q(R)$ can be obtained by detachment of $R \otimes$ from $(\mathrm{unupQ})_{W,Z}(R)$ (or $(\mathrm{uinupQ})_{W,Z}(R)$) and so on.

We shall see that the above reconstruction operators are linked to Process Algebra.

**Approximation of cylinders.** The above machinery can be used to approximate sets
represented by cylinders in a homogeneous relational framework. Thus, assume we are given the relational schema $(W \subseteq A \times A, Z \subseteq A \times A, Q \subseteq A \times A)$. By replacing $Q(a)$ by a set in guise of a cylinder one obtains $\{a : \forall a'(a' \in W(a) \implies (Z(a') \subseteq X))\} = ((X_Q \leftarrow Z) \leftarrow W)(a^*)$ If $Q = W = Z := R$ for $R$ a preorder, the above formula turns into:

$$((X_R \leftarrow R) \leftarrow R)(a^*) = (X_R \leftarrow R)(a^*) = (lR)(X) \qquad (44)$$

Thus, the usual approximations of sets are recovered (for other ways see [8] and cfr. [7]).

## 5.1 Bilateral approximation of a relation with reference relation

Let us just mention the topic. Given the complete relational schema $RS$ the purpose is to approximate the relation $R$ by procedures which output ordered pairs $(a, b) \in A \times B$, with the aid of the reference relation $Q$. It is natural to combine in some way the expressions “$\langle a, b \rangle \in R$” and “$\langle c, d \rangle \in Q$” through formulas in $W$ and $Z$. An immediate solution is the combination of “$\langle a, b \rangle \in R$” with some kind of reconstruction of $R$ itself. For instance:

$$\{\langle a, b \rangle : \langle a, b \rangle \in R \wedge \langle a, b \rangle \in (l sr W Z)_Q(R)\} = R \cap W \sim \to Q \leftarrow Z$$

## 5.2 Refinement and Simulation

Simulation is a relation $R \subseteq F(W, Z, Q)$, where $F(W, Z, Q)$ is an algebraic combination of the arguments. Let us consider the following types of simulation (see for instance [2]):

A) **Strong simulation.** It is defined as $W \sim \otimes R \otimes Z \subseteq Q$. Applying (4) after (2) we obtain $R \otimes Z \subseteq W \sim \to Q$ and finally $R \subseteq W \sim \to Q \leftarrow Z$. Therefore, from (41) strong simulation states that $R \subseteq (l sr W Z)_Q(R)$, that is, $R$ must be a refinement of its own sufficiency lower reconstruction. Since $Id_A \otimes R = R$ the condition states that $Id_A \otimes R \subseteq W \sim \to Q \leftarrow Z$ which is equivalent to $Id_A \subseteq (W \sim \to Q \leftarrow Z) \leftarrow R$. Otherwise stated: $R$ strongly simulates $Q$ iff $\forall a \in A, a \in (lnunQ)_{W,Z}(R)$.

B) **Down simulation:** $W \sim \otimes R \subseteq Q \otimes Z \sim$. It transforms into $R \subseteq (lprWZ)_Q(R)$. It follows that $R$ down simulates $Q$ iff $\forall a \in A, a \in (lnupQ)_{W,Z}(R)$.

C) **Up simulation:** $R \otimes Z \subseteq W \otimes Q$. Hence, $R \subseteq (lcprZW)_Q(R)$. As a consequence: $R$ up simulates $Q$ iff $\forall a \in A, a \in (ilnenQ)_{W,Z}(R)$.

D) **Weak simulation:** $R \subseteq W \otimes Q \otimes Z \sim$. It is immediate that $R \subseteq (dirWZ)_Q(R)$. Thus: $R$ weakly simulates $Q$ iff $\forall a \in A, a \in (lnepQ)_{W,Z}(R)$.

Only the cited works are reported. For a more comprehensive bibliography see [8]

## References

1. Brink C., Britz K., Schmidt R. A.: Peirce algebras. Formal Aspects of Computing, 6(3), 1994, pp. 339-358.

2. Fokkinga M.: A Summary of Refinement Theory. September 1994, Unregistered Technical Report, University of Twente, Enschede, Netherlands.

3. Goldblatt R.: Topoi: The Categorial Analysis of Logic. North-Holland, 1984.

4. Järvinen, J.: Knowledge Representation and Rough Sets. PhD Dissertation, University of Turku, 1999.

5. Lawvere F. W.: Adjointness in foundations. Dialectica, 23(3/4), 1969, pp. 281-296.

6. Ore, O.: Galois Connexions. Trans. of AMS, 55, 1944, pp. 493-531.

7. Pagliani P.: Modalizing Relations by means of Relations: a general framework for two basic approaches to Knowledge Discovery in Database. In Proc. of the IPMU 98, July, 6-10, 1998. "LaSorbonne, Paris, France, pp. 1175-1182.

8. Pagliani, P.: A foreword to a general theory of approximation of relations. A coronavirus paper. 2020. Published at www.academia.edu and www.researchgate.net

9. Pagliani P., Chakraborty M. K.: A Geometry of Approximation. Springer-Verlag, Trends in Logic, 27. 2008.

10. Sambin G.: Intuitionistic formal spaces - a first communication. In: Skordev D. (ed.) Mathematical logic and its applications, 1987, pp. 187-204. Plenum Press.

11. Skowron A., Stepaniuk J.: Approximation of relations. In: Ziarko, W.P. (ed.) Rough Sets, Fuzzy Sets and Knowledge Discovery, 1994, pp. 161-166. Springer.

12. Wille, R.: Restructuring lattice theory. In: I. Rival (ed.): Ordered Sets. NATO ASI Series, 83, 1982, pp. 445-470. Reidel.