### Classical Dualities and Formal Concept Analysis

#### Posted by Simon Willerton

What do the algebraic varieties, convex sets, linear subspaces, real numbers, logical theories and extension fields have in common with the formal concepts that I was discussing last time? Well, they can all be constructed in the same way.

Last time I described how if you start of with two sets together with a relation between them then you can turn a handle on a machine and out will pop a partially ordered set of ‘concepts’. Each concept is a pair $(A,B)$ consisting of a subset of each of the two original sets. This results in a duality, or more precisely a Galois correspondence, between certain subsets (the ‘closed’ ones) of the the original sets.

I didn’t realise that many standard dualites in mathematics arise in this way, just starting with two sets and a relation between them. This struck me when John was questioning me about my previous post.

See if you can guess which concepts or dualities emerge from the following relations. The answers are below the fold.

**Algebraic geometry** Take (the underlying set of) $\mathbb{C}^{n}$ and the set of complex polynomials in $n$-variables with the relation that the polynomial vanishes at the point.
$G=\mathbb{C}^{n},\quad M=\mathbb{C}[x_{1},\ldots ,x_{n}],\quad x I p \iff p(x)=0$

**Number theory** Take the set of points in a field $L$ where $L$ is a finite Galois extension $L\supset K$, and the set of field automorphisms of $L$ which fix $K$, with the relation that the automorphism fixes the point.
$G=L,\quad M= \text {Aut}(L;K),\quad x I \phi \iff \phi (x)=x.$

**Linear algebra** Take a vector space and the dual vector space with the relation that the function vanishes at the point.
$G=V,\quad M=V^{\vee },\quad v I f \iff f(v)=0.$

**Logic** Fix a formal language $L$. Take the set of $L$-structures and the set of $L$-sentences with the relation expressing the truth of a sentence with respect to a structure.
$G=\{ L\text {-structures}\} ,\quad M=\{ L\text {-sentences}\} ,\quad s I \phi \iff s\vDash \alpha .$

**Convex geometry** Take the set of points of an affine space $\mathbb{A}$ (e.g. $\mathbb{R}^{n}$) and the set of closed halfspaces in $\mathbb{A}$ with the relation that the point is in the halfspace.
$G=\mathbb{A},\quad M=\{ \text {halfspaces in}\,\mathbb{A}\} ,\quad x I H \iff x\in H.$

**Analysis** Take the set of rational numbers and the set of rational numbers again, with the relation being $\le$.
$G=\mathbb{Q},\quad M=\mathbb{Q},\quad q I q' \iff q\le q.$

[This isn’t what I said I’d talk about this time, but I got distracted!]

### Recap

Let’s just run through what the machine does. Start with sets $G$ and $M$ with a relation $I$ between them. This gives rise to a Galois connection between the partially ordered sets of subsets of $G$ and $M$: $I^{\ast }\colon \mathcal{P}(G)\rightleftarrows \mathcal{P}(M)^{\mathrm{op}}\colon I_{\ast }.$ We then get closure operations on both powersets: $I_{\ast }I^{\ast }\colon \mathcal{P}(G)\to \mathcal{P}(G),\quad I^{\ast }I_{\ast }\colon \mathcal{P}(M)\to \mathcal{P}(M).$ The closed subsets of $G$ are those that are invariant under the closure operation, and the set of closed subsets is denoted $\mathcal{P}_{\mathrm{cl}}(G)$ — in formal concept analysis these are the extents. Similarly, we have $\mathcal{P}_{\mathrm{cl}}(M)$ — in formal concept analysis these are called the intents.

The Galois connection restricts to a Galois correspondence, i.e. a duality, between the closed subsets of $G$ and the closed subsets of $M$. $I^{\ast }\colon \mathcal{P}_{\mathrm{cl}}(G)\cong \mathcal{P}_{\mathrm{cl}}(M)^{\mathrm{op}}\colon I_{\ast }.$

The concepts are then pairs $(A,B)$ consisting of a closed subset of $G$ and the corresponding closed subset of $M$. So the set of concepts is isomorphic to both the set of closed subsets of $G$ and the set of closed subsets of $M$.

### The answers

**Algebraic geometry** Here the concepts are affine varieties. A concept consists of the pair $(X,A)$ where $X\subseteq \mathbb{C}^{n}$ is the set of points of the variety and $A\subseteq \mathbb{C}[x_{1},\dots x_{n}]$ is the ideal of functions vanishing on $X$. This gives the classic duality between affine varieties and radical ideals.

**Number theory** This is, of course, ‘the’ Galois correspondence. The one in Galois theory. The closed subsets of $L$ are the intermediate field extensions between $K$ and $L$ and the closed subsets of the set of automorphisms are the subgroups.

**Linear algebra** The closed sets of $V$ are precisely the linear subsets and the concepts are of the form $(W,W^{\circ })$, where $W^{\circ }$ is the annihilator of $W$.

**Logic** Here concepts are theories. A concept $(S,\alpha )$ consists of $\alpha$ a set of sentences which is closed under logical consequence and $S$ the set of models of the theory. The duality in this case is Lawvere’s adjunction between semantics and syntax.

**Convex geometry** The closed subsets of $\mathbb{A}$ are the closed convex sets, the closure of a set is (the closure of) its convex hull.

**Analysis** The concepts here are Dedekind cuts, i.e. *real* numbers (together with $\pm \infty$)! A concept consists of a pair $(A,B)$ of sets of rational numbers, where $A$ is everything less than or equal to everything in $B$ and $B$ is everything greater than or equal to everything in $A$.

There are undoubtably, other interesting examples.

## Re: Classical Dualities and Formal Concept Analysis

Perhaps you might liven up the nLab Galois connection page now ;). The trouble is, once you start on a page there’s usually more to do on related ones.

Do we have anywhere the idea of Lambek and Scott’s slogan