Algebras of derivation operators

The derivation operators constitute the building blocks of concept lattices and thus deserve distinctive notations. Subject to a formal context concerning the object set ${\displaystyle G}$ and attribute set ${\displaystyle M}$,

${\displaystyle I\ :\ {\begin{array}{l}X\subseteq G\mapsto \ X^{I}=\lbrace m\in M\mid gRm,\ \forall g\in X\rbrace \subseteq M\\Y\subseteq M\mapsto \ Y^{I}=\lbrace g\in G\mid gRm,\ \forall m\in Y\rbrace \subseteq G\end{array}},}$

${\displaystyle \Box \ :\ {\begin{array}{l}X\subseteq G\mapsto \ X^{\Box }=\lbrace m\in M\mid \forall g\in G,gRm\implies g\in X\rbrace \subseteq M\\Y\subseteq M\mapsto \ Y^{\Box }=\lbrace g\in G\mid \forall m\in M,gRm\implies m\in Y\rbrace \subseteq G\end{array}},}$

${\textstyle \Diamond \ :\ {\begin{array}{c}X\subseteq G\mapsto \ X^{\Diamond }=\lbrace m\in M\mid \exists g\in G,(gRm,\ g\in X)\rbrace \subseteq M\\Y\subseteq M\mapsto \ Y^{\Diamond }=\lbrace g\in G\mid \exists m\in M,(gRm,\ m\in Y)\rbrace \subseteq G\end{array}}}$

are considered as different modal operators^[7][8] (Sufficiency, Necessity and Possibility, respectively) that generalise the FCA. For notations, ${\displaystyle I}$, the operator adopted in the standard FCA,^[1][2][3] follows Bernhard Ganter [de]^[10] and R. Wille;^[1] ${\displaystyle \Box {\mbox{ and }}\Diamond }$ as well as ${\displaystyle R}$ follows Y. Y. Yao.^[9] By ${\displaystyle gRm}$, i.e., ${\displaystyle (g,m)\in R}$ the object ${\displaystyle g}$ carries the attribute ${\textstyle m}$ as its property, which is also referred to as ${\displaystyle g\in m^{R}}$ where ${\displaystyle m^{R}}$ is the set of all objects carrying the attribute ${\textstyle m}$.

With ${\displaystyle X,X_{1},X_{2}\subseteq G{\mbox{ and }}X^{c}:=G\backslash X}$ it is straightforward to check that

${\displaystyle X^{III}=X^{I},\quad {\begin{array}{c}X^{\Box \Diamond \Box }=X^{\Box }\\X^{\Diamond \Box \Diamond }=X^{\Diamond }\end{array}},\quad {\begin{array}{c}X^{c\Box c}=X^{\Diamond }\\X^{c\Diamond c}=X^{\Box }\end{array}},}$ ${\displaystyle X_{1}\subseteq X_{2}\iff (X_{2})^{I}\subseteq (X_{1})^{I},\quad {\begin{array}{c}X_{1}\subseteq X_{2}\iff (X_{1})^{\Box }\subseteq (X_{2})^{\Box }\\X_{1}\subseteq X_{2}\iff (X_{1})^{\Diamond }\subseteq (X_{2})^{\Diamond }\end{array}},}$

where the same relations hold if given in terms of ${\displaystyle Y,Y_{1},Y_{2}\subseteq M{\mbox{ and }}Y^{c}:=M\backslash Y}$.

Two Galois lattices

(1) ${\displaystyle X\subseteq Y^{I}}$ ${\displaystyle \iff Y\subseteq X^{I}}$, (2) ${\displaystyle Y^{\Diamond }\subseteq X}$ ${\displaystyle \iff Y\subseteq X^{\Box }}$

${\displaystyle (X_{1},Y_{1})_{fcl}\leq (X_{2},Y_{2})_{fcl}}$ entails ${\textstyle X_{1}\subseteq X_{2}}$ and ${\textstyle Y_{2}\subseteq Y_{1}}$
since ${\displaystyle X_{1}\subseteq X_{2}}$ iff ${\displaystyle Y_{2}=X_{2}^{I}\subseteq X_{1}^{I}=Y_{1}}$, and ${\displaystyle Y_{2}\subseteq Y_{1}}$ iff ${\displaystyle X_{1}=Y_{1}^{I}\subseteq Y_{2}^{I}=X_{2}}$.

${\displaystyle (X_{1},Y_{1})_{rsl}\leq (X_{2},Y_{2})_{rsl}}$ entails ${\textstyle X_{1}\subseteq X_{2}}$ and ${\textstyle Y_{1}\subseteq Y_{2}}$
since ${\displaystyle X_{1}\subseteq X_{2}}$ iff ${\displaystyle Y_{1}=X_{1}^{\Box }\subseteq X_{2}^{\Box }=Y_{2}}$, and ${\displaystyle Y_{1}\subseteq Y_{2}}$ iff ${\displaystyle X_{1}=Y_{1}^{\Diamond }\subseteq Y_{2}^{\Diamond }=X_{2}}$.

Two types of informative implications

The consideration of the attribute set-to-set implication ${\textstyle A{\stackrel {\scriptscriptstyle fcl}{\rightarrow }}B}$ (${\displaystyle A,B\subseteq M}$) via FCL has an intuitive interpretation:^[6] every object possessing all the attributes in ${\displaystyle A}$ possesses all the attributes in ${\displaystyle B}$, in other words ${\displaystyle A^{I}\subseteq B^{I}}$. Alternatively, one may consider ${\textstyle A{\stackrel {\scriptscriptstyle rsl}{\rightarrow }}B}$ based on the RSL in a similar manner:^[4] the set of all objects carrying any of the attributes in ${\displaystyle A}$ is contained in the set of all objects carrying any of the attributes in ${\displaystyle B}$, in other words ${\displaystyle A^{\Diamond }\subseteq B^{\Diamond }}$. It is apparent that ${\textstyle A{\stackrel {\scriptscriptstyle fcl}{\rightarrow }}B}$ and ${\textstyle A{\stackrel {\scriptscriptstyle rsl}{\rightarrow }}B}$ relate different pairs of attribute sets and are incapable of expressing each other.

Extension of formal context

For every formal context one may acquire its extended version deduced in the sense of completing a truth-value table. It is instructive to explicitly label the object/attribute dependence for the formal context,^[4] say, ${\displaystyle F(G,M):=(G,M,I)}$ rather than ${\displaystyle \mathbb {K}$ :=(G,M,I)}  since one may have to investigate more than one formal contexts. As is illustrated in Table 1, ${\displaystyle F_{\scriptscriptstyle 3BS}(G,M)}$ can be employed to deduce the extended version ${\displaystyle F_{\scriptscriptstyle 3BS}^{\ast }(G,M^{\ast })}$, where ${\textstyle M^{\ast }}$ is the set of all attributes constructed out of elements in ${\textstyle M}$ by means of Boolean operations. Note that ${\displaystyle F_{\scriptscriptstyle 3BS}(G,M)}$ includes three columns reflecting the use of ${\textstyle M=\{a,b,c\}}$ and ${\displaystyle F_{1}(G,M_{1})}$ the attribute set ${\textstyle M_{1}=\{a\ {\bf {or}}\ b,b\ {\bf {or}}\ c,c\ {\bf {or}}\ a\}}$.

Observations based on mathematical facts

${\displaystyle (X,Y)_{fcl}}$ can be understood as ${\displaystyle (X,\mu )_{fcl}}$ with ${\textstyle \mu =\prod Y}$ (the conjunction of all elements in ${\displaystyle Y}$),${\displaystyle \ {\begin{smallmatrix}\prod X^{I}=\mu \\\mu ^{R}=X\end{smallmatrix}}}$ plays the role of ${\displaystyle {\begin{smallmatrix}X^{I}=Y\\Y^{I}=X\end{smallmatrix}}}$ since ${\textstyle Y^{I}=(\prod Y)^{R}=\mu ^{R}\subseteq G}$.

${\displaystyle (X,Y)_{rsl}}$ can be understood as ${\displaystyle (X,\mu )_{rsl}}$ with ${\textstyle \mu =\sum Y}$ (the disjunction of all elements in ${\displaystyle Y}$),${\displaystyle \ {\begin{smallmatrix}\sum X^{\Box }=\mu \\\mu ^{R}=X\end{smallmatrix}}}$ plays the role of ${\displaystyle {\begin{smallmatrix}X^{\Box }=Y\\Y^{\Diamond }=X\end{smallmatrix}}}$ since ${\textstyle Y^{\Diamond }=(\sum Y)^{R}=\mu ^{R}\subseteq G}$.

${\displaystyle (X_{1},\mu _{1})_{fcl}\leq (X_{2},\mu _{2})_{fcl}}$ and ${\displaystyle (X_{1},\mu _{1})_{rsl}\leq (X_{2},\mu _{2})_{rsl}}$, both are implemented by ${\textstyle X_{1}\subseteq X_{2}}$${\textstyle \iff }$${\textstyle \mu _{1}\leq \mu _{2}}$.

 ${\displaystyle \mu _{1}\rightarrow \mu _{2}}$ serves as the general form of implication relations available from the formal context, which holds for any pair of ${\textstyle \mu _{1},\mu _{2}\in M^{\ast }}$ fulfilling ${\displaystyle \mu _{1}^{R}\subseteq \mu _{2}^{R}}$.

${\textstyle A{\stackrel {\scriptscriptstyle fcl}{\rightarrow }}B}$ can be interpreted as ${\displaystyle \mu _{1}\rightarrow \mu _{2}}$ with ${\textstyle \mu _{1}=\prod A}$ and ${\textstyle \mu _{2}=\prod B}$,
${\textstyle A{\stackrel {\scriptscriptstyle rsl}{\rightarrow }}B}$ can be interpreted as ${\displaystyle \mu _{1}\rightarrow \mu _{2}}$ with ${\textstyle \mu _{1}=\sum A}$ and ${\textstyle \mu _{2}=\sum B}$,

Lattice of 3-tuple concepts with double Galois connection

When extended to ${\textstyle F^{\ast }(G,M^{\ast })}$, the algebras of derivation operators remain formally unchanged, apart from the generalisation from ${\textstyle m\in M}$ to ${\textstyle \mu \in M^{\ast }}$ which is signified in terms of^[4] the replacements ${\displaystyle I{\mbox{ by }}I^{\ast }}$, ${\displaystyle \Box {\mbox{ by }}\Box ^{\ast }}$ and ${\displaystyle \Diamond {\mbox{ by }}\Diamond ^{\ast }}$. The concepts under consideration become then ${\textstyle (X,Y)_{fcl}^{\ast }}$ and ${\textstyle (X,Y)_{rsl}^{\ast }}$, where ${\displaystyle X\subseteq G}$ and ${\displaystyle Y\subseteq M^{\ast }}$, which are constructions allowable by the two Galois connections ${\textstyle X\subseteq Y^{I^{\ast }}\iff Y\subseteq X^{I^{\ast }}}$and ${\textstyle Y^{\Diamond ^{\ast }}\subseteq X\iff Y\subseteq X^{\Box ^{\ast }}}$, respectively. Henceforth,

${\textstyle X^{I^{\ast }}=Y}$ and ${\textstyle Y^{I^{\ast }}=X}$ for ${\textstyle (X,Y)_{fcl}^{\ast }}$, ${\textstyle X^{\Box ^{\ast }}=Y}$ and ${\textstyle Y^{\Diamond ^{\ast }}=X}$ for ${\textstyle (X,Y)_{rsl}^{\ast }}$.

The extents for the two concepts now coincide exactly. All the attributes in ${\textstyle M^{\ast }}$ are listed in the formal context ${\textstyle F^{\ast }(G,M^{\ast })}$, each contributes a common extent for FCL and RSL. Furthermore, the collection of these common extents ${\textstyle E_{F}:=\{\mu ^{R}\mid \mu \in M^{\ast }\}}$ amounts to ${\textstyle \{\bigcup _{k\in J}D_{k}\mid J\subseteq \{1\ldots n_{F}\}\}}$ which exhausts all the possible unions of the minimal object sets discernible by the formal context. Note that each ${\displaystyle D_{k}}$ collects objects of the same property, see Table 2. One may then join ${\textstyle (X,Y)_{fcl}^{\ast }}$ and ${\textstyle (X,Y)_{rsl}^{\ast }}$ into a 3-tuple with common extent:

 ${\textstyle (X,Y^{fcl\ast },Y^{rsl\ast })}$ where ${\textstyle X^{I^{\ast }}=Y^{fcl\ast }}$, ${\textstyle X^{\Box ^{\ast }}={Y^{rsl\ast }}}$ and ${\textstyle {Y^{fcl\ast }}^{I^{\ast }}={Y^{rsl\ast }}^{\Diamond ^{\ast }}=X}$.

Note that ${\textstyle Y^{fcl\ast }{\mbox{ and }}Y^{rsl\ast }}$are introduced in order to differentiate the two intents. Clearly, the number of these 3-tuples equals the cardinality of set of common extent which counts ${\textstyle |E_{F}|=2^{n_{F}}}$. Moreover, ${\textstyle (X,Y^{fcl\ast },Y^{rsl\ast })}$ manifests well-defined ordering. For ${\textstyle X_{1},X_{2}\in E_{F}\subseteq G\ }$, where ${\textstyle {Y_{1}^{fcl\ast }},{Y_{2}^{fcl\ast }}\subset M^{\ast }}$and ${\textstyle {Y_{1}^{rsl\ast }},{Y_{2}^{rsl\ast }}\subset M^{\ast }}$,

${\textstyle (X_{1},{Y_{1}^{fcl\ast }},{Y_{1}^{rsl\ast }})\leq (X_{2},{Y_{2}^{fcl\ast }},{Y_{2}^{rsl\ast }})}$ iff ${\textstyle X_{1}\subseteq X_{2}}$ and ${\textstyle {Y_{2}^{fcl\ast }}\subseteq {Y_{1}^{fcl\ast }}}$ and ${\textstyle {Y_{1}^{rsl\ast }}\subseteq {Y_{2}^{rsl\ast }}}$.

Emergence of the GCL

While it is generically impossible to determine ${\textstyle Y^{fcl\ast }{\mbox{ and }}Y^{rsl\ast }}$ subject to ${\textstyle X\in E_{F}\subseteq G}$, the structure of concept hierarchy need not rely on these intents directly. An efficient way^[4] to implement the concept hierarchy for ${\textstyle (X,Y^{fcl\ast },Y^{rsl\ast })}$ is to consider intents in terms of single attributes. Let henceforth ${\textstyle \eta (X):=\prod Y^{fcl\ast }}$ and ${\textstyle \rho (X):=\sum Y^{rsl\ast }}$. Upon introducing ${\textstyle [X]_{F}:=\{\mu \in M^{\ast }\mid \mu ^{R}=X\}}$ it is straightforward to check that ${\textstyle \prod [X]_{F}=\prod Y^{fcl\ast }}$ and ${\textstyle \sum [X]_{F}=\sum Y^{rsl\ast }}$, ${\textstyle \forall X\in E_{F}}$. Therefore, ${\textstyle [X]_{F}\equiv [\eta (X),\rho (X)]=\{\mu \in M^{\ast }\mid \eta (X)\leq \mu \leq \rho (X)\}}$, which is a closed interval bounded from below by ${\textstyle \eta (X)}$ and from above by ${\textstyle \rho (X)}$ since ${\displaystyle \forall \mu \ \mu ^{R}=X\implies \eta (X)\leq \mu \leq \rho (X)}$. Moreover,

${\textstyle \forall X_{1}\forall X_{2}\in E_{F}\ X_{1}\neq X_{2}}$ iff ${\textstyle [X_{1}]_{F}\cap [X_{2}]_{F}=\emptyset }$, ${\textstyle X_{1}\subset X_{2}}$ iff ${\textstyle \eta (X_{1})<\eta (X_{2})}$ iff ${\textstyle \rho (X_{1})<\rho (X_{2})}$.

In addition, ${\textstyle \bigcup _{X\in E_{F}}[X]_{F}=M^{\ast }}$ which means that the collection of intents ${\textstyle [X]_{F}}$ in fact exhausts all the generalised attributes ${\textstyle M^{\ast }}$in comparison to ${\textstyle \bigcup _{X\in E_{F}}X=G}$. Then, the GCL enters as the lattice structure ${\textstyle \Gamma _{F}:=(L_{F},\wedge ,\vee )}$ based on the formal context via ${\textstyle F^{\ast }(G,M^{\ast })}$:

• The collection of all the general concepts ${\textstyle L_{F}=\{(X,[X]_{F})\mid \ X\in E_{F}\}}$ constitutes the poset ${\textstyle (L_{F},\leq )}$ ordered as

${\textstyle l_{1}:=(X_{1},[X_{1}]_{F})\leq l_{2}:=(X_{2},[X_{2}]_{F})}$ iff ${\textstyle X_{1}\subseteq X_{2}}$ and ${\textstyle \eta (X_{1})\leq \eta (X_{2})}$ and ${\textstyle \rho (X_{2})\leq \rho (X_{2})}$.

• Both ${\displaystyle \wedge }$ (meet) and ${\displaystyle \vee }$ (join) operations are applicable for finding further lattice points:

${\displaystyle l_{1}\wedge l_{2}=\left(X_{1}\cap X_{2},[X_{1}\cap X_{2}]_{F}\right)\in L_{F}}$, where ${\textstyle [X_{1}\cap X_{2}]_{F}=[\eta (X_{1}\cap X_{2}),\rho (X_{1}\cap X_{2})]=[\eta (X_{1})\cdot \eta (X_{2}),\rho (X_{1})\cdot \rho (X_{2})],}$

${\textstyle l_{1}\vee l_{2}=\left(X_{1}\cup X_{2},[X_{1}\cup X_{2}]_{F}\right)\in L_{F}}$, where${\textstyle [X_{1}\cup X_{2}]_{F}=[\eta (X_{1}\cup X_{2}),\rho (X_{1}\cup X_{2})]=[\eta (X_{1})+\eta (X_{2}),\rho (X_{1})+\rho (X_{2})].}$

• The GCL appears to be a complete lattice since both ${\textstyle l_{sup}}$ and ${\textstyle l_{inf}}$ can be found in ${\textstyle L_{F}}$:

${\textstyle l_{sup}=\bigvee _{l\in L_{F}}l=(G,[G]_{F})=(G,[\eta (G),{\bf {1}}])}$, ${\textstyle l_{inf}=\bigwedge _{l\in L_{F}}l=(\emptyset ,[\emptyset ]_{F})=(\emptyset ,[{\bf {0}},\rho (\emptyset )])}$.

Manageable general lattice

The construction for FCL was known to count on efficient algorithms,^[11][12] not to mention the construction for RSL which did not receive much attention yet. Intriguingly, though the GCL furnishes the general structure on which both the FCL and RSL can be rediscovered, the GCL can be acquired via simple readout.

Information content of a formal context

${\textstyle \forall \mu \in M^{\ast }\ \mu \rightarrow \mu \cdot 1_{\eta }}$, which can be restated as ${\textstyle \forall \mu \in M^{\ast }\ \mu +0_{\rho }\rightarrow \mu }$,

${\textstyle \mu _{1}\rightarrow \mu _{2}}$ is allowed by the formal context iff ${\textstyle \mu _{1}\cdot 1_{\eta }\leq \mu _{2}\cdot 1_{\eta }}$ (or ${\textstyle \mu _{1}+0_{\rho }\leq \mu _{2}+0_{\rho }}$).