FCA foundations

This section is essentially based on the article by Bernhard Ganter [Gant2000].

The set language model of formal concept analysis assumes a formal context (G, M, I), consisting of the sets G and M and a binary relation I ⊆ G x M. The elements of G become objects, those of M are called characteristics, and ( g, m) ∈ I the "the object g has the feature m" is read. Relation I is also called the incidence relation of the context. For A ⊆ G and B ⊆ M we define

• A^I := {m ∈ M | (g, m) ∈ I for all g ∈ A}
• B^I := {g ∈ G | (g, m) ∈ I for all m ∈ B}

A formal concept of the context (G, M, I) is a pair FCC = (A, B) with A ⊆ G, B ⊆ M, A^I = B and B^I = A. A is called the extension and B the content of the concept (A, B). The set ℬ(G, M, I) of all such terms, ordered by

• (A₁, B₁) ≤ (A₂, B₂): ⇐ ⇒ (A₁ ⊆ A₂) (⇐ ⇒ B₁ ⊇ B₂ ),

is a complete lattice and is called the concept lattice of (G, M, I). In this concept lattice, every formal concept is supremum of object concepts and infimum of property concepts. The mathematical structure of a concept lattice can be represented by a line diagram. The smaller circles represent the formal terms of the associated formal context and the ascending stretches represent the sub-concept-superordinate concept relationship. In particular, the underlying context can be reconstructed from the line diagram [Will2008]

It is important to understand how the terminology in formal concept analysis corresponds to that in ontologies. In principle, the upper and lower terms represented by nodes in the line diagrams can be traced back to subset relationships. In the rarest of cases, they form a subclass / superclass relationship. This is not the case even when the objects represent classes and the features represent their attributes, as in the water ontology example.