concept lattice

Let $G$ and $M$ be sets whose elements we call objects and attributes respectively. Let $I\subseteq G\times M$. We say that object $g\in G$ has attribute $m\in M$ iff $(g,m)\in I$. The triple $(G,M,I)$ is called a context. For any set $X\subseteq G$ of objects, define

$$X^{\prime }:=\{m\in M\mid (x,m)\in I\text{ for all }x\in G\}.$$

In other words, $X^{\prime }$ is the set of all attributes that are common to all objects in $X$. Similarly, for any set $Y\subseteq M$ of attributes, set

$$Y^{\prime }:=\{g\in G\mid (g,y)\in I\text{ for all }y\in M\}.$$

In other words, $Y^{\prime }$ is the set of all objects having all the attributes in $M$. We call a pair $(X,Y)\subseteq G\times M$ a concept of the context $(G,M,I)$ provided that

$$X^{\prime }=Y\mathit{\hspace{1em}}\text{and}\mathit{\hspace{1em}}{Y}^{\prime }=X.$$

If $(X,Y)$ is a concept, then $X$ is called the extent of the concept and $Y$ the intent of the concept.

Given a context $(G,M,I)$. Let $𝔹(G,M,I)$ be the set of all concepts of $(G,M,I)$. Define a binary relation $\le$ on $𝔹(G,M,I)$ by $(X_1,Y_1)\le (X_2,Y_2)$ iff $X_1\subseteq X_2$. Then $\le$ makes $𝔹(G,M,I)$ a lattice, and in fact a complete lattice. $𝔹(G,M,I)$ together with $\le$ is called the concept latice of the context $(G,M,I)$.