An analysis of three types of partially-known formal concepts

Abstract

Formal concept analysis with an incomplete context has received much attention recently, where an object is known to have one set of attributes and not have another set of attributes; for the rest of attributes, it is unknown if the object has or does not have them. This has led to a notion called partially-known formal concepts in a framework of three-way concept analysis with interval sets. The intent and/or extent of a partially-known concept may no longer be a set but an interval set. Depending on the set or interval set representation of the intent and extent, there are three different forms of partially-known formal concepts, namely SE-ISI (i.e., set extent and interval-set intent) formal concept, ISE-SI (i.e., interval-set extent and set intent) formal concept and ISE-ISI (i.e., interval-set extent and interval-set intent) formal concept. Although these three forms of partially-known formal concepts have been identified and proposed, their structures and relationships have not been fully investigated. The main objective of this paper is to provide such a study. We adopt a possible-world semantics of an incomplete formal context, i.e., an incomplete formal context is viewed as the family of all its possible completions. This enables us to systematically study the structures of the three different forms of partially-known formal concepts and their relationships. To be consistent with the possible-world semantics, we interpret a partially-known formal concept as the family of formal concepts in completions of an incomplete formal context. In addition to presenting theorems to summarize our results, we use an example to illustrate the main ideas.

Appendix: Proofs

Proof of Proposition 1

2. If $[\underline{O_{1}},\overline{O_{1}}]\preccurlyeq [\underline{O_{2}},\overline{O_{2}}]$, it follows that $\underline{O_{1}}\subseteq \underline{O_{2}}$ and $\overline{O_{1}}\subseteq \overline{O_{2}}$. Based on property (1) of the operator i, we obtain $\underline{ i}(\underline{O_{2}})\subseteq \underline{ i}(\underline{O_{1}})$ and $\overline{ i}(\overline{O_{2}})\subseteq \overline{ i}(\overline{O_{1}})$. Thus, $\underline{ i}(\underline{O_{2}})\cap \overline{ i}(\overline{O_{2}})\subseteq \underline{ i}(\underline{O_{1}})\cap \overline{ i} (\overline{O_{1}})$. That is, $\langle \underline{ i},\overline{ i} \rangle ([\underline{O_{2}},\overline{O_{2}}])\subseteq \langle \underline{ i},\overline{ i} \rangle ([\underline{O_{1}},\overline{O_{1}}])$. The part of attribute interval set can be proved similarly.

3. Based on property (2) of the operators i and e, we can get $O\subseteq \underline{ e}(\underline{ i}(O))$ and $O\subseteq \overline{ e}(\overline{ i}(O))$. Hence, $O\subseteq \underline{ e}(\underline{ i}(O))\cap \overline{ e}(\overline{ i}(O)).$ That is, $O\subseteq \langle \underline{ e},\overline{ e} \rangle ([\underline{ i},\overline{ i}](O))$. The second part can be proved similarly.

4. According to property (2) of the operators i and e, we obtain $\underline{O_{1}}\subseteq \underline{ e}(\underline{ i}(O_{1}))$ and $\overline{O_{1}}\subseteq \overline{ e}(\overline{ i}(\overline{O_{1}}))$. It is obvious that $\underline{O_{1}}\subseteq \underline{ e}(\underline{ i}(\underline{O_{1}}))\cup \underline{ e}(\overline{ i}(\overline{O_{1}}))$ and $\overline{O_{1}}\subseteq \overline{ e}(\underline{ i}(\underline{O_{1}}))\cup \overline{ e}(\overline{ i}(\overline{O_{1}}))$. Also, based on property (6) of the operator e, we can get $\underline{ e}(\underline{ i}(\underline{O_{1}}))\cup \underline{ e}(\overline{ i}(\overline{O_{1}}))\subseteq \underline{ e}(\underline{ i}(\underline{O_{1}})\cap \overline{ i}(\overline{O_{1}}))$ and $\overline{ e}(\underline{ i}(\underline{O_{1}}))\cup \overline{ e}(\overline{ i}(\overline{O_{1}}))\subseteq \overline{ e}(\underline{ i}(\underline{O_{1}})\cap \overline{ i}(\overline{O_{1}}))$. Thus, $\underline{O_{1}}\subseteq \underline{ e}(\underline{ i}(\underline{O_{1}})\cap \overline{ i}(\overline{O_{1}}))$ and $\overline{O_{1}}\subseteq \overline{ e}(\underline{ i}(\underline{O_{1}})\cap \overline{ i}(\overline{O_{1}}))$. Since $[\underline{ e},\overline{ e}](\langle \underline{ i},\overline{ i} \rangle ([\underline{O_{1}},\overline{O_{1}}]))=[\underline{ e}(\underline{ i}(\underline{O_{1}})\cap \overline{ i}(\overline{O_{1}})), \overline{ e}(\underline{ i}(\underline{O_{1}})\cap \overline{ i}(\overline{O_{1}}))]$, based on the definition of the partial order on interval set, we can get $[\underline{O_{1}},\overline{O_{1}}]\preccurlyeq [\underline{ e},\overline{ e}](\langle \underline{ i},\overline{ i} \rangle ([\underline{O_{1}},\overline{O_{1}}]))$. The rest part can be proved similarly.

5. By (4), we know $[\underline{ i},\overline{ i}](O)\preccurlyeq [\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e} \rangle ([\underline{ i},\overline{ i}](O)))$. Based on (1) and (3), it follows $[\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e} \rangle ([\underline{ i},\overline{ i}](O)))\preccurlyeq [\underline{ i},\overline{ i}](O)$. Thus $[\underline{ i},\overline{ i}](O)=[\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e} \rangle ([\underline{ i},\overline{ i}](O)))$. The rest part can be proved similarly.

6. By (3), we know $\langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}},\overline{O_{1}}])\subseteq \langle \underline{ i},\overline{ i}\rangle ([ \underline{ e},\overline{ e}] (\langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}}$, $\overline{O_{1}}])))$. Based on (2) and 4), it follows $\langle \underline{ i},\overline{ i}\rangle ([ \underline{ e},\overline{ e}] (\langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}}$, $\overline{O_{1}}])))\subseteq \langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}},\overline{O_{1}}])$. Thus $\langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}},\overline{O_{1}}])=\langle \underline{ i},\overline{ i}\rangle ([ \underline{ e}$, $\overline{ e}] (\langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}},\overline{O_{1}}])))$. The reset part can be proved similarly.

7. From the definition of the operator $[\underline{ i},\overline{ i}]$, we get $[\underline{ i},\overline{ i}]([\underline{O_{1}},\overline{O_{1}}])\sqcap [\underline{ i},\overline{ i}]([\underline{O_{2}},\overline{O_{2}}])=[\underline{ i}(\underline{O_{1}}),\overline{ i} (\overline{O_{1}})]\sqcap [\underline{ i}(\underline{O_{2}})$, $\overline{ i}(\overline{O_{2}})]$. According to the intersection of interval sets, it follows $[\underline{ i}(\underline{O_{1}}),\overline{ i}(\overline{O_{1}})]\sqcap [\underline{ i}(\underline{O_{2}}),\overline{ i}(\overline{O_{2}})]= [\underline{ i}(\underline{O_{1}})\cap \underline{ i}(\underline{O_{2}}),\overline{ i}(\overline{O_{1}})$ $\cap \overline{ i}(\overline{O_{2}})]$. By property (5) of operator i, we can get $[\underline{ i}(\underline{O_{1}})\cap \underline{ i}(\underline{O_{2}}),\overline{ i}(\overline{O_{1}}) \cap \overline{ i}(\overline{O_{2}})]= [\underline{ i}(\underline{O_{1}}\cup \underline{O_{2}}),\overline{ i}(\overline{O_{1}}\cup \overline{O_{2}})]$. Because of the definition of the operator $[\underline{ i},\overline{ i}]$, we have $[\underline{ i}(\underline{O_{1}}\cup \underline{O_{2}}),\overline{ i}(\overline{O_{1}}\cup \overline{O_{2}})]=[\underline{ i},\overline{ i}]([\underline{O_{1}}\cup \underline{O_{2}},\overline{O_{1}}\cup \overline{O_{2}}])$. According to the union of interval sets, it follows $[\underline{ i},\overline{ i}]([\underline{O_{1}}\cup \underline{O_{2}},\overline{O_{1}}\cup \overline{O_{2}}])= [\underline{ i},\overline{ i}]([\underline{O_{1}},\overline{O_{1}}]\sqcup [\underline{O_{2}},\overline{O_{2}}])$. Thus $[\underline{ i},\overline{ i}]([\underline{O_{1}},\overline{O_{1}}])\sqcap [\underline{ i},\overline{ i}]([\underline{O_{2}},\overline{O_{2}}])= [\underline{ i},\overline{ i}]([\underline{O_{1}},\overline{O_{1}}]\sqcup [\underline{O_{2}},\overline{O_{2}}])$. The rest part can be proved similarly.

8. According to the union of interval sets, it follows $\langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}},\overline{O_{1}}]\sqcup [\underline{O_{2}},\overline{O_{2}}])=\langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}}\cup \underline{O_{2}}, \overline{O_{1}}\cup \overline{O_{2}}])$. Because of the definition of operator $\langle \underline{ i},\overline{ i}\rangle$, we have $\langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}}\cup \underline{O_{2}}, \overline{O_{1}}\cup \overline{O_{2}}])=\underline{ i}(\underline{O_{1}}\cup \underline{O_{2}})\cap \overline{ i}(\overline{O_{1}} \cup \overline{O_{2}})$. By property 5) of the operator i, it follows $\underline{ i}(\underline{O_{1}}\cup \underline{O_{2}})\cap \overline{ i}(\overline{O_{1}}\cup \overline{O_{2}})= \underline{ i}(\underline{O_{1}})\cap \underline{ i}(\underline{O_{2}})\cap (\overline{ i}(\overline{O_{1}}) \cap \overline{ i}(\overline{O_{2}}))= \underline{ i}(\underline{O_{1}})\cap (\overline{ i}(\overline{O_{1}}))\cap (\underline{ i}(\underline{O_{2}}) \cap \overline{ i}(\overline{O_{2}}))$. Based on the definition of operator $\langle \underline{ i},\overline{ i}\rangle$, it follows $(\underline{ i}(\underline{O_{1}})\cap (\overline{ i}(\overline{O_{1}}))\cap (\underline{ i}(\underline{O_{2}}) \cap \overline{ i}(\overline{O_{2}}))= \langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}},\overline{O_{1}}])\cap \langle \underline{ i},\overline{ i}\rangle ([\underline{O_{2}},\overline{O_{2}}])$. Thus $\langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}},\overline{O_{1}}]\sqcup [\underline{O_{2}},\overline{O_{2}}])=\langle \underline{ i},\overline{ i}\rangle ([\underline{O_{1}},\overline{O_{1}}])\cap \langle \underline{ i},\overline{ i}\rangle ([\underline{O_{2}},\overline{O_{2}}])$. The rest part can be proved similarly. $\square$

Proof of Theorem 3

(A) We only prove the infimum part and the supermum part can be proved dually. Now, we prove that $(O_{1}\cap O_{2}, [\underline{ i},\underline{ i}](\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$ is an SE-ISI concept. By 8) of Proposition 1, it follows that $\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}]$ $\sqcup [\underline{A_{2}},\overline{A_{2}}])=\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}])\cap \langle \underline{ e},\overline{ e}\rangle ([\underline{A_{2}},\overline{A_{2}}])$. Since $(O_{1}$, $[\underline{A_{1}},\overline{A_{1}}])$ and $(O_{2},[\underline{A_{2}},\overline{A_{2}}])$ are SE-ISI concepts, it follows that $\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}])=O_{1}$ and $\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{2}},\overline{A_{2}}])=O_{2}$. Thus $\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}])\cap \langle \underline{ e},\overline{ e}\rangle ([\underline{A_{2}},\overline{A_{2}}])=O_{1}\cap O_{2}$. Hence, we can get $[\underline{ i},\overline{ i}](O_{1}\cap O_{2})=[\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}]))$. Then by 6) of Proposition 1, it follows that $\langle \underline{ e},\overline{ e}\rangle ([\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))=\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])$. According to 8) of Proposition 1, we have $\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])=\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}])\cap \langle \underline{ e},\overline{ e}\rangle ([\underline{A_{2}}$, $\overline{A_{2}}])$. Since, $(O_{1},[\underline{A_{1}},\overline{A_{1}}])$ and $(O_{2},[\underline{A_{2}},\overline{A_{2}}])$ are SE-ISI concepts, it follows that $\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}])=O_{1}$ and $\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{2}},\overline{A_{2}}])=O_{2}$. Thus $\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}])\cap \langle \underline{ e},\overline{ e}\rangle ([\underline{A_{2}}$, $\overline{A_{2}}])=O_{1}\cap O_{2}$. Hence, we can get $\langle \underline{ e},\overline{ e}\rangle ([\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}}$, $\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))=O_{1}\cap O_{2}$.

Then, we prove that $(O_{1}\cap O_{2}, [\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$ is the infimum of SE-ISI concepts $(O_{1},[\underline{A_{1}}$, $\overline{A_{1}}])$ and $(O_{2},[\underline{A_{2}},\overline{A_{2}}])$. Since $O_{1}\cap O_{2}\subseteq O_{1}$ and $O_{1}\cap O_{2}\subseteq O_{2}$, $(O_{1}\cap O_{2}, [\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))\preccurlyeq _\mathrm{{SE-ISI}}(O_{1},[\underline{A_{1}},\overline{A_{1}}])$ and $(O_{1}\cap O_{2}, [\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$ $\preccurlyeq _\mathrm{{SE-ISI}}(O_{2},[\underline{A_{2}},\overline{A_{2}}])$ hold. Hence $(O_{1}\cap O_{2}, [\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e}\rangle$ $([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$ is the lower bound of two SE-ISI concepts ${(O_{1},[\underline{A_{1}},\overline{A_{1}}])}$ and ${(O_{2},[\underline{A_{2}},\overline{A_{2}}])}$. If there is any SE-ISI concept $(O_{i},[\underline{A_{i}},\overline{A_{i}}])$ that is the lower bound of $(O_{1},[\underline{A_{1}},\overline{A_{1}}])$ and $(O_{2},[\underline{A_{2}},\overline{A_{2}}])$, then the formulas $(O_{i},[\underline{A_{i}},\overline{A_{i}}])\preccurlyeq _\mathrm{{SE-ISI}}(O_{1},[\underline{A_{1}},\overline{A_{1}}])$ and $(O_{i},[\underline{A_{i}}$, $\overline{A_{i}}])\preccurlyeq _\mathrm{{SE-ISI}}(O_{2},[\underline{A_{2}},\overline{A_{2}}])$ hold. Thus $O_{i}\subseteq O_{1}$ and $O_{i}\subseteq O_{2}$ hold. Hence $O_{i}\subseteq O_{1}\cap O_{2}$. That is, $(O_{i},[\underline{A_{i}},\overline{A_{i}}])$ $\preccurlyeq _\mathrm{{SE-ISI}}(O_{1}\cap O_{2}, [\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$. Thus $(O_{1}\cap O_{2}, [\underline{ i},\overline{ i}](\langle \underline{ e},\overline{ e}\rangle ([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$ is the infimum of SE-ISI concepts $(O_{1},[\underline{A_{1}},\overline{A_{1}}])$ and $(O_{2},[\underline{A_{2}},\overline{A_{2}}])$.

(B) Since ISE-SI concepts and SE-ISI concepts are dual to each other. The results of (B) can be proved dually to (A).

(C) We only prove the infimum part and the supermum part can be proved dually. Now, we prove that $([\underline{O_{1}},\overline{O_{1}}]\sqcap [\underline{O_{2}},\overline{O_{2}}],[\underline{ i},\overline{ i}]([\underline{ e},\overline{ e}]([\underline{A_{1}},$ $\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$ is an ISE-ISI concept. Since $([\underline{O_{1}}, \overline{O_{1}}],$ $[\underline{A_{1}}, \overline{A_{1}}])$ and $([\underline{O_{2}}, \overline{O_{2}}], [\underline{A_{2}}, \overline{A_{2}}])$ are ISE-ISI concepts, it is obvious that $(\underline{O_{1}},\underline{A_{1}})$ and $(\underline{O_{2}},\underline{A_{2}})$ are formal concepts in least completion ${\mathbb {K}}_{*}$. Thus according to the way of computing the infimum of formal concepts in a complete formal context, $(\underline{O_{1}}\cap \underline{O_{2}},\underline{ i}(\underline{ e}(\underline{A_{1}}\cup \underline{A_{2}})))$ is the infimum of formal concepts $(\underline{O_{1}},\underline{A_{1}})$ and $(\underline{O_{2}},\underline{A_{2}})$. Hence $(\underline{O_{1}}\cap \underline{O_{2}},\underline{ i}(\underline{ e}(\underline{A_{1}}\cup \underline{A_{2}})))$ is a formal concept in context ${\mathbb {K}}_{*}$. Similarly, since $([\underline{O_{1}}, \overline{O_{1}}], [\underline{A_{1}}, \overline{A_{1}}])$ and $([\underline{O_{2}}, \overline{O_{2}}],$ $[\underline{A_{2}}, \overline{A_{2}}])$ are ISE-ISI formal concepts, it is obvious that $(\overline{O_{1}},\overline{A_{1}})$ and $(\overline{O_{2}},\overline{A_{2}})$ are formal concepts in greatest completion ${\mathbb {K}}^{*}$. Thus according to the way of computing the infimum of formal concepts in a complete formal context, $(\overline{O_{1}}\cap \overline{O_{2}},\overline{ i}(\overline{ e}(\overline{A_{1}}\cup \overline{A_{2}})))$ is the infimum of concepts $(\overline{O_{1}},\overline{A_{1}})$ and $(\overline{O_{2}},\overline{A_{2}})$. Hence $(\overline{O_{1}}\cap \overline{O_{2}},\overline{ i}(\overline{ e}(\overline{A_{1}}\cup \overline{A_{2}})))$ is a formal concept in context ${\mathbb {K}}^{*}$. Also, since $\underline{O_{1}}\subseteq \overline{O_{1}}$ and $\underline{O_{2}}\subseteq \overline{O_{2}}$, we can get $\underline{O_{1}}\cap \underline{O_{2}}\subseteq \overline{O_{1}}\cap \overline{O_{2}}$. Thus $([\underline{O_{1}}\cap \underline{O_{2}},\overline{O_{1}}\cap \overline{O_{2}}],[\underline{ i}(\underline{ e}(\underline{A_{1}}\cup \underline{A_{2}})),\overline{ i}(\overline{ e}(\overline{A_{1}}\cup \overline{A_{2}}))])$ is an ISE-ISI concept. That is, $([\underline{O_{1}},\overline{O_{1}}]\sqcap [\underline{O_{2}},\overline{O_{2}}],[\underline{ i},\overline{ i}]([\underline{ e},\overline{ e}]([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$ is an ISE-ISI concept.

Then, we prove that $([\underline{O_{1}},\overline{O_{1}}]\sqcap [\underline{O_{2}},\overline{O_{2}}],[\underline{ i},\overline{ i}]([\underline{ e},\overline{ e}]$ $([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$ is the infimum of ISE-ISI concepts $([\underline{O_{1}}, \overline{O_{1}}], [\underline{A_{1}}, \overline{A_{1}}])$ and $([\underline{O_{2}}, \overline{O_{2}}], [\underline{A_{2}}, \overline{A_{2}}])$. Since the formulas $[\underline{O_{1}},\overline{O_{1}}]\sqcap [\underline{O_{2}},\overline{O_{2}}]\preccurlyeq [\underline{O_{1}},\overline{O_{1}}]$ and $[\underline{O_{1}},\overline{O_{1}}]\sqcap [\underline{O_{2}},\overline{O_{2}}]\preccurlyeq [\underline{O_{2}},\overline{O_{2}}]$ hold, it is obviously that $([\underline{O_{1}},\overline{O_{1}}]\sqcap [\underline{O_{2}},\overline{O_{2}}],[\underline{ i},\overline{ i}]([\underline{ e},\overline{ e}]([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$ is the lower bound of ISE-ISI concepts $([\underline{O_{1}}, \overline{O_{1}}], [\underline{A_{1}}, \overline{A_{1}}])$ and $([\underline{O_{2}}, \overline{O_{2}}],$ $[\underline{A_{2}}, \overline{A_{2}}])$. If there is any ISE-ISI concept $([\underline{O_{i}},\overline{O_{i}}],[\underline{A_{i}},$ $\overline{A_{i}}])$ that is the lower bound of ISE-ISI concepts $([\underline{O_{1}}, \overline{O_{1}}],$ $[\underline{A_{1}}, \overline{A_{1}}])$ and $([\underline{O_{2}}, \overline{O_{2}}], [\underline{A_{2}}, \overline{A_{2}}])$, the formula $[\underline{O_{i}},\overline{O_{i}}]\preccurlyeq [\underline{O_{1}}, \overline{O_{1}}]$ and $[\underline{O_{i}},\overline{O_{i}}]\preccurlyeq [\underline{O_{2}}, \overline{O_{2}}]$ hold. Thus $[\underline{O_{i}},\overline{O_{i}}]\preccurlyeq [\underline{O_{1}}, \overline{O_{1}}]\sqcap [\underline{O_{2}}, \overline{O_{2}}]$. That is, $([\underline{O_{i}},\overline{O_{i}}],[\underline{A_{i}},\overline{A_{i}}])\preccurlyeq _\mathrm{{ISE-ISI}}([\underline{O_{1}},\overline{O_{1}}]\sqcap [\underline{O_{2}},\overline{O_{2}}],[\underline{ i},\overline{ i}]([\underline{ e},\overline{ e}]([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$. Thus $([\underline{O_{1}},\overline{O_{1}}]\sqcap [\underline{O_{2}},\overline{O_{2}}],[\underline{ i},\overline{ i}]([\underline{ e},\overline{ e}]([\underline{A_{1}},\overline{A_{1}}]\sqcup [\underline{A_{2}},\overline{A_{2}}])))$ is the infimum of ISE-ISI concepts $([\underline{O_{1}}, \overline{O_{1}}], [\underline{A_{1}}, \overline{A_{1}}])$ and $([\underline{O_{2}}, \overline{O_{2}}], [\underline{A_{2}}, \overline{A_{2}}])$. $\square$

Proof of Theorem 4

Sufficiency. First, we prove that if $(O,[A_{1},A_{2}])$ is an SE-ISI concept and the condition $O=\underline{ e}(A_{1})$ holds, then there exists an ISE-ISI concept $([\underline{ e}(A_{1}),\overline{ e}(A_{2})],[A_{1},A_{2}])$ having the same intent as $(O,[A_{1},A_{2}])$. If $(O,[A_{1},A_{2}])$ is an SE-ISI concept, then we have $\underline{ i}(O)=A_{1}$, $\overline{ i}(O)=A_{2}$ and $\underline{ e}(A_{1})\bigcap \overline{ e}(A_{2})=O$. Thus we obtain $O\subseteq \underline{ e}(A_{1})$ and $O\subseteq \overline{ e}(A_{2})$. Hence $\underline{ i}(\underline{ e}(A_{1}))\subseteq \underline{ i}(O)$ and $\overline{ i}(\overline{ e}(A_{2}))\subseteq \overline{ i}(O)$. That is, $\underline{ i}(\underline{ e}(A_{1}))\subseteq A_{1}$ and $\overline{ i}(\overline{ e}(A_{2}))\subseteq A_{2}$. Because we also know $A_{1}\subseteq \underline{ i}(\underline{ e}(A_{1}))$ and $A_{2}\subseteq \overline{ i}(\overline{ e}(A_{2}))$, we can get $A_{1}=\underline{ i}(\underline{ e}(A_{1}))$ and $A_{2}=\overline{ i}(\overline{ e}(A_{2}))$. Thus $(\underline{ e}(A_{1}),A_{1})$ is an SE-SI concept in the least completion ${\mathbb {K}}_{*}$ and $(\overline{ e}(A_{2}),A_{2})$ is an SE-SI concept in the greatest completion ${\mathbb {K}}^{*}$. Since $O=\underline{ e}(A_{1})\bigcap \overline{ e}(A_{2})$ and the condition $O=\underline{ e}(A_{1})$ holds, it is obviously $\underline{ e}(A_{1})=O\subseteq \overline{ e}(A_{2})$. Hence $([\underline{ e}(A_{1}),\overline{ e}(A_{2})],[A_{1},A_{2}])$ is an ISE-ISI concept.

Then, we prove that if $([O_{1},O_{2}],[A_{1},A_{2}])$ is an ISE-ISI concept and the condition $\overline{ i}(O_{1})=A_{2}$ holds, there exists an SE-ISI concept $(O_{1},[A_{1},A_{2}])$ having the same intent as $([O_{1},O_{2}],[A_{1},A_{2}])$. Since $([O_{1}, O_{2}],[A_{1}, A_{2}])$ is an ISE-ISI concept, we have $\underline{ i}(O_{1})=A_{1}$, $\underline{ e}(A_{1})=O_{1}$, $\overline{ e}(A_{2})=O_{2}$ and $O_{1}\subseteq O_{2}$. Thus $\underline{ e}(A_{1})\bigcap \overline{ e}(A_{2})=O_{1}\bigcap O_{2}=O_{1}$. Also, since the condition $\overline{ i}(O_{1})=A_{2}$ holds, according to the definition of SE-ISI concept, $(O_{1},[A_{1},A_{2}])$ is an SE-ISI concept.

Necessity. Suppose $O\ne \underline{ e}(A_{1})$. Since $([\underline{ e}(A_{1}),\overline{ e}(A_{2})],$ $[A_{1},A_{2}])$ is an ISE-ISI concept, we have $\underline{ e}(A_{1})\subseteq \overline{ e}(A_{2})$. Hence $\underline{ e}(A_{1})\bigcap \overline{ e}(A_{2})=\underline{ e}(A_{1})\ne O$ which contradicts the condition that $(O,[A_{1},A_{2}])$ is an SE-ISI concept. Thus we have $O=\underline{ e}(A_{1})$. If $(O,[A_{1}, A_{2}])$ is an SE-ISI concept, from the definition of SE-ISI concept, it is easy to get $\overline{i}(O)=A_{2}.$ Because we have proved $O=\underline{ e}(A_{1})=O_{1}$, we can get $\overline{i}(O_{1})=A_{2}$. $\square$

Proof of Theorem 7

Since $([\underline{O},\overline{O}],[\underline{A},\overline{A}])=\{(O,A)|O\in [\underline{O},\overline{O}], A\in [\underline{A},\overline{A}]\}$ is an ISE-ISI concept, we have that $(\underline{O},\underline{A})$ is the lower bound of $([\underline{O},\overline{O}],[\underline{A},\overline{A}])$ and it is also an SE-SI concept in least completion $\mathbb {K_{*}}$. Because of $(O_{1},A_{1})\in ([\underline{O},\overline{O}],[\underline{A},\overline{A}])$, we know $\underline{O}\subseteq O_{1}$ and $\underline{A}\subseteq A_{1}$. Since $(O_{1},A_{1})$ is also an SE-SI concept of least completion $\mathbb {K_{*}}$, based on the property of the SE-SI concept, if $\underline{O}\subseteq O_{1}$ holds, then we can obtain $A_{1}\subseteq \underline{A}$, and if $\underline{A}\subseteq A_{1}$ holds, then we can get $O_{1}\subseteq \underline{O}$. Thus $A_{1}=\underline{A}$ and $O_{1}=\underline{O}$. That is, $(O_{1},A_{1})=(\underline{O},\underline{A})$. The last part of this theorem can be proved similarly. $\square$

Proof of Theorem 8

Necessity. If (O, A) is an SE-SI concept in completion $\mathbb {K}$, then we have $e_{\mathbb {K}}(A)=O$. Since $\underline{ e}(A)\subseteq e_{\mathbb {K}}(A)=O$, we obtain $\underline{ e}(A)\subseteq O$.

Sufficiency. We show that this is indeed the case by constructing a completion $\mathbb {K} =(O\!B, AT, \mathbf{I_{\mathbb {K}}})$ as $\mathbf{I_{\mathbb {K}}}=\mathbf{I_*} \cup (O \times A)$, where $\mathbf{I_*}$ is the binary relation of the least completion $\mathbb {K_{*}}$. The completion $\mathbb {K}$ is obtained by changing all ? into $+$ for object-attribute pairs in $O\times A$ and changing all ? into − for all object-attribute pairs in $(O\!B - O)\times (AT - A)$. It is obvious that $O\subseteq e_{\mathbb {K}}(A)$.

In the following, we prove that $O= e_{\mathbb {K}}(A)$. Suppose $O\subset e_{\mathbb {K}}(A)$, there must exist an object $o\in e_{\mathbb {K}}(A)\setminus O$. Thus we have $o\in \underline{ e}(A)$ that contradicts the condition $\underline{ e}(A)\subseteq O$. Hence the equation $O= e_{\mathbb {K}}(A)$ holds.

Now we prove $i_{\mathbb {K}}(O)=A$. Based on the definition of the completion $\mathbb {K}$, $A\subseteq i_{\mathbb {K}}(O)$. Suppose $A\subset i_{\mathbb {K}}(O)$, there must exist an attribute $a\in i_{\mathbb {K}}(O)\setminus A$. Thus we have $a\in \underline{ i}(O)=\underline{A}$ that contradicts the condition $\underline{A}\subseteq A$. Hence $i_{\mathbb {K}}(O)=A$ holds. Thus we obtain that (O, A) is an SE-SI concept in completion $\mathbb {K}$. $\square$

Proof of Theorem 9

If (O, A) is an SE-SI concept in the least completion $\mathbb {K_{*}}$, we have $\underline{ i}(O)=A$ and $\underline{ e}(A)=O$. Since $O\subseteq \overline{ e}(\overline{ i}(O))$ holds, we obtain $\underline{ e}(A)\bigcap \overline{ e}(\overline{ i}(O))=O\bigcap \overline{ e}(\overline{ i}(O))=O$. Thus $(O,(A,\overline{ i}(O)))$ is an SE-ISI concept in the incomplete context $\mathbb {IK}$. Similarly, the later part can be proved. $\square$