Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

While trying to unify the (mostly linearly) ordered attributes from Statistical classification with the binary attributes from formal concept analysis, I came across an interesting section in the wikipedia article on the Dedekind–MacNeille completion:

If $O$ is any finite set of objects, and $A$ is any finite set of binary attributes for the objects in $O$, then one may form a partial order of height two in which the elements of the partial order are the objects and attributes, and in which $x \leq y$ when $x$ is an object that has attribute $y$. For a partial order defined in this way, the Dedekind–MacNeille completion of $S$ is known as a concept lattice, and it plays a central role in the field of formal concept analysis.

While this seems to point to an easy way to use the Dedekind–MacNeille completion to achieve the desired unification, the statement made in this section is not completely true1. However, essentially the same statement can also be found in the wikipedia article on Formal concept analysis:

It may be viewed as the Dedekind–MacNeille completion of a partially ordered set of height two in which the elements of the partial order are the objects and attributes of M and in which two elements x and y satisfy x ≤ y exactly when x is an object that has attribute y.

Question: Where does this statement come from, and how must it be modified to express a "really correct" relation between concept lattice and Dedekind–MacNeille completion?

1. The completion will contain each single object (and each single attribute), but the concept lattice only contains a concept for an object, if its attributes differ from all other objects. In other words, in the concept lattice, similar objects and similar attributes are merged together into a single concept, but the Dedekind–MacNeille completion won't merge anything.

share|cite|improve this question
up vote 0 down vote accepted

A well known relation between context lattice and Dedekind-MacNeille completion is described for example in section 7.8 of Hilary A. Priestley's ‘Ordered sets and complete lattices: a primer for computer science’, in “Algebraic and Co-algebraic Methods in the Mathematics of Program Construction (Oxford, 2000)”, Lecture Notes in Comput. Sci. 2297 (2002), 21–78.:

Taking a poset $P$ rather than a complete lattice $L$, $\mathcal B(P,P,R_\leq)$, or more conveniently its image under $\pi_1$ (recall 7.5) yields the Dedekind-MacNeille completion of $P$.

I found out that both wikipedia sections where written by the same author on the same day. I asked the author which source he used for these sections. He referred me to a source for the above well known relation, but added that he is not sure whether he used a source at all. However, if I interpret this answer in the sense that the cited wikipedia sections are an (over)simplified version of a basic theorem on concept lattices, then I would rather take the second part of theorem 1 from Ganter and Wille's Applied Lattice Theory: Formal Concept Analysis instead:

Theorem 1 (The basic theorem on concept lattices) The concept lattice $\mathcal B(G, M, I)$ is a complete lattice in which infimum and supremum are given by: $\land_{t\in T}(A_t,B_t)=\left(\bigcap_{t\in T}A_t,\left(\bigcup_{t_in T}B_t\right)''\right)$ and $\lor_{t\in T}(A_t,B_t)=\left(\left(\bigcup_{t_in T}A_t\right)'', \bigcap_{t\in T}B_t\right)$.

A complete lattice $L$ is isomorphic to $\mathcal B(G, M, I)$ if and only if there are mappings $\tilde\gamma:G\mapsto L$ and $\tilde\mu:M\mapsto L$ such that $\tilde\gamma(G)$ is supremum-dense in $L$, $\tilde\mu(M)$ is infimum-dense in $L$ and $gIm$ is equivalent to $\tilde\gamma g\leq \tilde\mu m$ for all $g \in G$ and all $m \in M$. In particular: $L \tilde=\mathcal B(L, L, \leq)$

I think I basically solved the problem now. 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.

Let's take the poset $P=G\cup M$ in which two elements $x$ and $y$ satisfy $x \leq y$ exactly when $x$ is an object that has attribute $y$, as in the cited wikipedia sections above. If we take $\mathcal B(P,P,R_{\tilde <})$ instead of the Dedekind-MacNeille completion, then we really end up with (a complete lattice isomorphic to) the concept lattice $\mathcal B(G,M,I)$. But what is the relation between $\mathcal B(P,P,R_\leq)$ and $\mathcal B(P,P,R_{\tilde <})$? It's not hard to check that $R_{\tilde <} \subset R_\leq$ is a closed subrelation. Hence we can apply

Theorem 3 $S$ is a complete sublattice of $\mathcal B(G, M, I)$ if and only if $S=\mathcal B(G, M, J)$ for some closed subrelation $J\subset I$.

from Ganter and Wille's Applied Lattice Theory: Formal Concept Analysis introductory paper. So the concept lattice is a complete sublattice of the Dedekind-MacNeille completion of the poset constructed in the cited wikipedia sections.

Ganter and Wille's Applied Lattice Theory: Formal Concept Analysis also explains many valued contexts and a contextual scaling procedure to transform it into a "one-valued" context. This provides a pragmatic unification of the attributes from statistical classification with the (binary) attributes from formal context analysis.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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