## September 12, 2013

### 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.$

### 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$.

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.

Posted at September 12, 2013 2:13 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2657

### 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

Many equivalence and duality theorems in mathematics arise as an equivalence of fixed subcategories induced by a pair of adjoint functors?

Posted by: David Corfield on September 13, 2013 9:51 AM | Permalink | Reply to this

### Re: Classical Dualities and Formal Concept Analysis

Well, we have a variant of Lambek and Scott’s slogan (from their book “Introduction to higher order categorical logic”).

Many equivalence and duality theorems in mathematics arise as an isomorphism of fixed posets induced by a Galois connection which comes from a relation.

The point is that there is often a simple binary relation underpinning the equivalence/duality.

If it isn’t clear now then the relationship between Galois connections and adjunctions will be made clear in a later post.

I notice that in their book (which I hadn’t looked at previously) they have the convex set example, which is nice as I don’t recall seeing it written down before.

I’ll not take up the offer to add to the nlab page, but I will encourage anyone else to add this material to the nlab page.

Posted by: Simon Willerton on September 16, 2013 12:42 PM | Permalink | Reply to this

### Re: Classical Dualities and Formal Concept Analysis

Cool! It’s nice how you reduced so many famous dualities to something very simple about a pair of sets with a relation between them.

Of course the notion of ‘concept’ can also be obtained by dualizing the lesser-known notion of ‘ncept’.

Posted by: John Baez on September 17, 2013 10:18 AM | Permalink | Reply to this

### Re: Classical Dualities and Formal Concept Analysis

Just as the style of your joke can be otained by dualizing the lesser known humour known as rny.

Posted by: Simon Willerton on September 17, 2013 5:12 PM | Permalink | Reply to this

### Re: Classical Dualities and Formal Concept Analysis

Don’t we need to first define 1-cepts and 2-cepts before we handle the general case of n-cepts?

Posted by: Charles G Waldman on September 18, 2013 6:14 PM | Permalink | Reply to this