Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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)(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) n\mathbb{C}^{n} and the set of complex polynomials in nn-variables with the relation that the polynomial vanishes at the point. G= n,M=[x 1,,x n],xIpp(x)=0 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 LL where LL is a finite Galois extension LKL\supset K, and the set of field automorphisms of LL which fix KK, with the relation that the automorphism fixes the point. G=L,M=Aut(L;K),xIϕϕ(x)=x. 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,M=V ,vIff(v)=0. G=V,\quad M=V^{\vee },\quad v I f \iff f(v)=0.

Logic Fix a formal language LL. Take the set of LL-structures and the set of LL-sentences with the relation expressing the truth of a sentence with respect to a structure. G={L-structures},M={L-sentences},sIϕsα. 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.  n\mathbb{R}^{n}) and the set of closed halfspaces in 𝔸\mathbb{A} with the relation that the point is in the halfspace. G=𝔸,M={halfspaces in𝔸},xIHxH. 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=,M=,qIqqq. 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 GG and MM with a relation II between them. This gives rise to a Galois connection between the partially ordered sets of subsets of GG and MM: I *:𝒫(G)𝒫(M) op:I *. I^{\ast }\colon \mathcal{P}(G)\rightleftarrows \mathcal{P}(M)^{\mathrm{op}}\colon I_{\ast }. We then get closure operations on both powersets: I *I *:𝒫(G)𝒫(G),I *I *:𝒫(M)𝒫(M). 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 GG are those that are invariant under the closure operation, and the set of closed subsets is denoted 𝒫 cl(G)\mathcal{P}_{\mathrm{cl}}(G) — in formal concept analysis these are the extents. Similarly, we have 𝒫 cl(M)\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 GG and the closed subsets of MM. I *:𝒫 cl(G)𝒫 cl(M) op:I *. 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)(A,B) consisting of a closed subset of GG and the corresponding closed subset of MM. So the set of concepts is isomorphic to both the set of closed subsets of GG and the set of closed subsets of MM.

The answers

Algebraic geometry Here the concepts are affine varieties. A concept consists of the pair (X,A)(X,A) where X nX\subseteq \mathbb{C}^{n} is the set of points of the variety and A[x 1,x n]A\subseteq \mathbb{C}[x_{1},\dots x_{n}] is the ideal of functions vanishing on XX. 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 LL are the intermediate field extensions between KK and LL and the closed subsets of the set of automorphisms are the subgroups.

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

Logic Here concepts are theories. A concept (S,α)(S,\alpha ) consists of α\alpha a set of sentences which is closed under logical consequence and SS 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)(A,B) of sets of rational numbers, where AA is everything less than or equal to everything in BB and BB is everything greater than or equal to everything in AA.

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

5 Comments & 1 Trackback

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
Read the post Galois Correspondences and Enriched Adjunctions
Weblog: The n-Category Café
Excerpt: Translate from category theory to order theory
Tracked: February 5, 2014 11:14 PM

Post a New Comment