Galois Connections

Posté par alpheccar le29 Oct 2005 à 10:51 CEST

I propose you a very small overview of Galois connections. But first, I need to answer the question : why in English ? I have realized that more and more people coming to this site are foreigners not reading French. So, I decided to write some texts in English assuming that people who can understand complex scientific texts can also read English. The other scientific texts (for grand public) and the ones about philosophy of freedom will still be written in French.

Galois Theory

I hope that my not so good English will not prevent people from understanding what I mean.

So, let’s start our journey in Galois theory. This theory was born thanks to attempts to solve the following question : does it exist a general method to solve algebraic equations of degree ≥5 . By general, I mean a formula built from the arithmetical operators (-,+,* and /) and the square root operation. The answer is no and is related to consideration of symmetries.

Let’s take a simple example: the equation x^2-a has two solutions : √a > and −√a  . We see that there is a symmetry on the set of solutions. We can exchange the roots and the equation is not changed. If I replace each solution by its opposite one then I still get the same set of solutions. More generally, we can study the symmetries of the set of solutions of an equation and also the symmetries that we can get from numbers built using the arithmetical operators and the square root one. We discover that the most general equation of degree 5 has a group of symmetry which cannot be reproduced using square root and the arithmetical operators. That’s the reason why we cannot generate the solutions of an equation of degree 5 using the standard algebraic operators. They don’t have the same symmetry properties.

What we have introduced here is the set of symmetries acting on K=Q(√a)   without changing k=Q  (the operators are behaving as the identity one when acting on Q). It is the Galois group of K/k  : Gal(K/k)   . This Galois group is not only related to fields. The Galois group Gal(K/k)   of a big thing K containing a smaller thing k is the set of symmetries of the big thing K fixing everything in the little one.

The more elements you want to fix with your symmetry group, the smaller your symmetry group. Gal(K/k)  gives the symmetry group fixing k while acting on K-k. If you want to fix more elements than in k then you’ll get less symmetries than in Gal(K/k)  . And, if you want to fix everything (the whole K) then you get only one symmetry : Identity. The only way to fix everything is to change nothing.

Galois Connection

Definition

In the previous example, we have a connection between two worlds : field extensions and groups. It is called a Galois connection because it is the first known instance of that kind of connection. More generally, a Galois connection is related to the idea of order and not to the idea of fields or groups. An order can be an inclusion relation where you start from a small set which is contained in a bigger one etc... But, you can use any order relation.

Assume you have two worlds A and B. In the world A you use the order relation < to compare elements. In the word B, you use a different order relation : {. Then, assume you have a way to pass from the word A to B (using f) and a way to come back from B to A using g. We have a Galois connection when:

So, we have two different views of the same problem. Looking at the problem in world A is equivalent to looking at the problem in world B because we have a Galois connection between both words. (There are different equivalent definitions where the order is changed when passing from one world to the other).

Floor and Ceil functions

An example of a Galois connection is given by the operations floor and ceil for rounding. floor(x) rounding to the largest integer smaller or equal to x (example:floor(3.2)=3) and ceil(x) rounding to the smaller integer higher or equal to x (example:ceil(3.2)=4).

Consider the two worlds : integer and real.

The f function is the embeding of integers inside reals.

The g function is the floor one. We have:

• f(a)≤b  if and only if a≤floor(b) 
• a≤b  if and only if a≤floor(b) 

And we have a dual definition for function ceil.

Floor is an adjoint to the function of embedding of the integers inside reals. It is part of a Galois connection between reals and integers !

Galois Theory Revisited

Let’s look again at the Galois Theory : one of the first examples of Galois Connection. If we have a set X of elements and S a subset of a group of transformations of the elements, we define two functions L and R. LX is the subgroup of G fixing all elements of X. And RS is the set of elements fixed by all group transformations in S. The two worlds are : the subsets of elements ordered by the inclusion relation and the subsets of the group ordered by the inclusion relation. L and R form a Galois connection !

Existential and universal quantifiers

We define:

and we define also:

P*  represents the “exist” quantifier with a set operator. P#  represents the “forall” operator.

Now, we have, if the inclusion order is ≤ :

So, P*  has a left and right adjoints : the existential and universal quantifiers. And we have again examples of Galois connections.

Galois Concept

Another interesting example of Galois connection is the idea of concept and the lattice of concepts in formal concept analysis.

A concept is an unit of thoughts consisting of two parts : the extension and the intension of the concept. The extension is the set of objects belonging to the concept. The intention comprise all attributes valid for the objects under consideration. So, we define a formal context K=(G,M,I)  where G is the set of objects, M the set of attributes and I a binary relation between the set of attributes and the set of objects. gIm  means the object g has attribute m.

So, what is a formal concept ? It is a pair (A,B)  where B is the set of attributes from M which apply to each object in A. And A is the set of all objects of G to which each attribute of B applies.

A is called the extend of the concept and B is the intent of the concept.

A concept where A is a single object is an object concept. A concept where B is a single attribute is an attribute concept.

Now, let’s define an order relation on the set of formal concepts. (A1,B1)≤(A2,B2)   if and only if A1  is a subset of A2  or (that’s equivalent) B2  is a subset of B1 .

We say that (A1,B1)  is a subconcept and (A2,B2)  a superconcept.

This order relation on the set of concepts is such that we get a lattice (in French : treilli or espace réticulé). I won’t define what is a lattice here because I’ll write something about lattices on my blog in a future text.

A central notion of the formal concept analysis is the idea of Galois connection between the two set of items named objects and attributes (or similarly : extend and intent) : if one makes larger a set of one type then the other set gets smaller. This duality also means that we have a duality between syntax and semantic ... but that’s another story.

Conclusion

The idea of Galois Connection is one of the most important in mathematics and it can be found everywhere. It is not related to the Galois Theory, which is “just” the first example of a Galois connection between field extensions and symmetry groups. Galois connection is related to the idea of order.

Pas de tags