A formal context in formal concept analysis is a triple $K = (G, M, I)$ where $G$ is a set of objects, $M$ is a set of attributes and the binary relation $I \subset G \times M$ shows which objects possess which attributes. By single sorted case, I refer to the situation that $G=M$. One example of this situation is the fact that for a poset $P$, the concept lattice $\mathcal B(P,P,R_\leq)$ yields the Dedekind-MacNeille completion of $P$.

The concrete construction which I want to better understand is closely related to this example: For a given partial order $\leq$, define the relation $\tilde <$ via $x\tilde<y$ if and only if $x\leq y$ and $y\not \leq x$ or $x$ is a bottom element or $y$ is a top element. I want to understand the relation between $\mathcal B(P,P,R_\leq)$ and $\mathcal B(P,P,R_{\tilde<})$, as well as what happens to the relation between $P$ and $\mathcal B(P,P,R_{\tilde<})$ when I iterate this construction.

I noticed that $R_{\tilde<}$ is still a transitive relation, and that the binary relation $I$ will probably be transitive for all instances of the single sorted case of interest to me. Hence my question is whether the single sorted case of formal concept analysis been investigated already (especially with a transitive incidence relation).

Additional remark The single sorted case is a special case of the general theory, but the general theory should be embeddable in the single sorted case via $K'=(V, V, \imath_{V\times V}(I))$ with $V:=G \uplus M$ where $\imath_{V\times V}(I)$ interprets the relation $I \subset G \times M$ as a relation on $V\times V$. The incidence relation $\imath_{V\times V}(I)$ is transitive, but fails to be a partial order. On second thought, the embedding would also work with $V:=G \cup M$, but the incidence relation $\imath_{V\times V}(I)$ can fail to be transitive in this case.


There are several approches for defining formal contexts of the form $\mathbb K(V,V,J)$ where $V=G\dot ∪M$ and $I∪I^{-1}⊆J$. Some of them are described in [1][2].

If you chose $I∪I^{-1}=J$, then the result is rather trivial: You get two oppositely ordered lattices side by side linked just by $0$ and $1$. Maybe you have something different in mind which I can't deduce from your Edit so far.

We can describe the position of a concept $(A,A^{≤})$ by its supremum irreducibles below and the infimum irreducibles above it. Thus, you can take any concept of $(A,B)∈\mathfrak B(G,M,≤)$. If $at(G)$ are the objects that generate the atoms of the concept lattice $\mathfrak B(G,M,≤)$ and $coat(M)$ are the attributes that generate the coatoms of the lattice, then $(A,B)$ corresponds to the concept $\bigl(A∩at(G),B∩coat(M)\bigr)$ regarding $\tilde <$. So you have a subcontext. Whenever you remove an irreducible the corresponding chain is shortened by $1$. Francesco Kriegel has discussed this process in his diploma thesis. The aspect of adding a chain is partly considered in this article.

For FCA there is no difference whether you consider preordered sets (reflexive and transitive relations) or ordered sets.[3]

[1] Ganter, B.; Wille, R. “Formal Concept Analysis”, Mathematical foundations, Springer

[2] Ganter, B.; Wille, R. “Formale Begriffsanalyse”, Mathematische Grundlagen, Springer

[3] The only difference can be discussed looking at the context: When it is not clarified it the “order” relation is just a preorder. On the other hand the formal concepts consist of two sets so it doesn't matter wheter your relation is antisymmetric.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.