## Archive for February, 2009

I am converting my posts about monads into a PDF file, using LaTeX. It is available here. I am already projecting the title of the next posts, so you already know what comes next…

A large class of monads is actually derived from operads: basic examples form monads in the category of sets and associate to a set X a set TX of abstract “terms” made of elements of X. For example, the monad of vector spaces I mentioned in the previous post is such a monad, and associates to a set the abstract linear combinations of its elements.

Operads are a generic structure giving a more precise definition of these terms. An operad is an abstract set of operations of various arities (an ugly word to precise the number or arguments taken by an operation: a ternary operation is said to have arity three), subject to relations between them or their compositions. For example, the operad of vector spaces consists of two basic operations: sum and product by scalars (which are actually infinitely many operations), which are tied by distributivity, commutativity and associativity among other relations. An example of operation in this operad is $(x,y,z) to 2x+3y+z$, which is a ternary operation.
(more…)

### Monads in mathematics 1 : examples

Category theory studies in an abstract way how structures and constructions of mathematics are related. A category is a collection of (mathematical) objects. Usually, interesting categories contain objects sharing the same properties (there is a category of sets, a category of groups, a category of rings, and so on). A category need also have a definition of arrows, which often correspond to the usual definition of functions, maps or morphisms. But it is possible to define categories having more complicated arrows. A (not so) stupid non-trivial category is the opposite category Cop of a given category C, which has arrows going the other way.

A monad M on a category C is a functor: it associates to any object X in C another object MX of C in a so-called functorial way, which means that any arrow $X to Y$ should give rise to an arrow $MX to MY$. But in order to call M a monad, we require several other properties: there should be natural transformations $X to MX$ (so that $X to MX to MY$ and $X to Y to MY$ are the same, which can be expressed by a commutative square), and $MMX to MX$ such that $MX to MMX to MX$ is the identity (notice that there are two ways to obtain an arrow $MX to MMX$). MacLane in Categories for the Working Mathematician gives a good account of the theory along with a bit of history and references.

Most examples of monads arising in mathematics are derived from two concepts: operads, which combine monads with much richer structure (but correspond to really tangible examples), and adjunctions (a framework in which monads can actually fit). I should write about these later, and concentrate on examples. Monads are also used in computer science, because they model a construction scheme which is widely spread. The programming language Haskell formulates many concepts in the language of monads. Marco Maggesi wrote a small introduction to monads (in Italian), which covers monads appearing in Haskell. (more…)

### Rational approximations of √2

Introducing undergraduates to rational approximations of √2 can be an opportunity to insidiously tell them about many parts of mathematics they certainly don’t want to hear about. In a less pessimistic way, I would say this is a nice way to illustrate the use of several theories in abstract mathematics.

First, you may want to tell them it is not a rational number, which could be easy, unless they never heard about factoring integers.

Then, you could use classical sequences from high school classes: it is easy to check that iterating $u_{n+1} = \frac{u_n+2}{u_n+1}$ converges to ±√2, and setting $U_n = \frac{u_n-\sqrt 2}{u_n+\sqrt 2}$ they will even be able to give an explicit formula with a geometric sequence. There is of course a well-known algorithm which speeds up considerably the computation : Newton’s method. This can be illustrated geometrically by drawing the graph of a function having √2 as a root (for example $x \mapsto x^2-2$):

1. take a rough approximation, such as x=1
2. imagine the function is affine (replacing the graph by its tangent)
3. use the approximation of the function to calculate an approximation of the solution
4. use this newly found rough solution to iterate from step 1

This method requires iterating $v_{n+1} = \frac 1 2 (v_n + 2/v_n)$, and converges considerably faster. Both methods yield sequences of rational numbers converging to √2, so should be considered as methods to obtain fractional numbers giving good approximations of √2. (more…)

### Laver tables and “unprovable” statements

Laver tables are combinatorial objets whose definition is surprisingly simple. However, they do have somewhat weird properties, which come from their relationship with questions of set theorists (namely, how do elementary embeddings of models of set theory behave). It also have connections with braid group theory, which I do not know. The Wikipedia article gives the basic facts, a survey by Patrick Dehornoy will give relevant bibliography, and friends of mine wrote an undergraduate thesis on the subject (in French).

The most basic definition of Laver tables is the Cayley table of a self-distributive binary operation. This means we define an exotic operation $\star$ on a set of numbers, and fill a square table with the outcomes of this operation. The required property of this operation is $a \star (b \star c) = (a \star b) \star (a \star c)$. This operation does not share properties with our usual operations, which are often associative of commutative. Suppose the set of numbers is $\{0, 1, ..., n-1\}$ and that 1 acts on the right by shifts : $i \star 1 = i+1$ and $(n-1) \star 1 = 0$. (more…)

### Ten constructions of the cohomology of varieties

When talking about “the” cohomology of mathematical objects, we do not always explicitly mention which cohomology is used, because it is obvious (in cases there is only one possible definition), or because we really don’t care (since as we will see, it is frequent that different definitions lead to equivalent results). The case of differentiable manifolds or algebraic varieties is particularly impressive, since there were a lot of equivalent cohomology theories defined during last century in order to simplify proofs or allow generalisations. Most cohomology theories, if not all, are defined as the cohomology of a complex : i.e. a sequence of vector spaces or modules $(V_n)$ with a boundary map $d$. The kernel of $d$ is called the set of cycles, while the images by $d$ are called boundaries : the cohomology $H^n$ is then the quotient of cycles in $V_n$ by the subspace of boundaries.

Classical topologists, for example, will use preferably (see MacLane, Homology or the book of Allen Hatcher) :

• simplicial (co)homology : it is defined for a triangulated space, i.e. the manifold is cut by curves, surfaces, etc. which make it isomorphic to a sort of polyhedron (a complex); simplicial homology describe non-triviality (holes) in the combinatorial structure of this polyhedron; here the boundary map is really the boundary map.
• singular (co)homology : a more abstract version of simplicial homology; now we consider the set of all possible simplexes (curves, polygons, polyhedra, and their generalisations…) drawn on the manifold; this definition was given by Eilenberg; I don’t know who first defined simplicial homology, but MacLane mentions that Poincaré and Noether gaves important contributions to this theory.

Then come sheaves, which were explicitly defined by Leray (tales for young mathematicians help remember that Leray made considerable efforts as a prisoner in concentration camps to focus his work on especially “useless” subjects to avoid helping Nazis). (more…)

### Saying QED in different languages

I was wondering whether it would be easy to know how to say “QED” in whatever language I could think of… Well, it seems (not so unexpectedly after all) that Wikipedia was the right tool to use : so starting from the QED article (not the quantum electrodynamics one !) of the English Wikipedia, the language list allows to switch to the version of the same article in many other idioms ! Ever wondered how Icelanders ended their proofs ?

From this investigation it comes out that

• in English, as you probably know, the phrase QED, for quod erat demonstrandum is used, following the tradition of Latin-speaking (or rather Latin-writing) mathematicians. I guess that people used to write mathematics in Latin for quite a long time, maybe even quite recently. It seems that many people, not only English-speaking still use it, even though it was wiped out by generalised use of LaTeX and the ∎ (U+220E) symbol.