Applied algebra, with FCA at the centre

Much of the applied work at algebra20 sits inside, or close to, Formal Concept Analysis. FCA, introduced by Rudolf Wille in the early 1980s (Wille, 1982), is a mathematical theory of how a small table of “objects” and “attributes” gives rise — automatically and canonically — to a hierarchy of concepts. That hierarchy is a lattice, the concept lattice, and it carries all the information that the original table contained, organised so that one can reason about it.

The basic objects

A formal context is a triple $(G, M, I)$ consisting of a set $G$ of objects, a set $M$ of attributes, and a binary relation $I \subseteq G \times M$ that records which objects have which attributes. The data is usually displayed as a cross table — rows for objects, columns for attributes, a cross in cell $(g, m)$ iff $g \mathrel{I} m$.

From this, two “derivation” operators arise. For a set $A \subseteq G$ of objects, define

the attributes shared by every object in $A$. Dually, for $B \subseteq M$, define

These two operators form a Galois connection between subsets of $G$ and subsets of $M$.

Concepts

A formal concept of the context $(G, M, I)$ is a pair $(A, B)$ with $A \subseteq G$, $B \subseteq M$, $A' = B$, and $B' = A$. The set $A$ is the extent (which objects), and $B$ is the intent (which attributes). Order the set of all concepts by inclusion of extents:

The fundamental theorem of concept lattices says that the resulting partially ordered set is a complete lattice — called the concept lattice $\mathfrak{B}(G, M, I)$ — and that every complete lattice arises, up to isomorphism, as the concept lattice of some context.

A worked example

Take five animals and four attributes. The cross table on the left says which animal has which attribute. The diagram on the right is the concept lattice: each node is a concept, and an edge connects a concept to its immediate generalisations above.

Hovering on a concept on the right reveals its extent and its intent. Hovering on a row or column highlights the concepts that contain that object or attribute. The lattice is doing real work: it is the smallest order structure that captures every “if-then” pattern implicit in the table.

Why algebra20 cares

FCA is the place where classical lattice theory most clearly earns its keep in modern data work. A concept lattice is not a visualisation glued onto a dataset — it is the dataset, rearranged into the algebraic structure it always implied. That conviction — that the algebraic content of data is something one can extract, study, and use — sits behind much of what gets written in this section.

The canonical reference for the mathematical machinery is Ganter & Wille (1999); for the wider lattice and order-theoretic background, Davey & Priestley (2002) and Birkhoff (1967).