Using generators and closure properties

Quick description

Suppose that $X$ is some mathematical structure that is generated by some small subset $K$ . (The meaning of "is generated by" depends on what sort of structure $X$ is.) A useful method of proving statements of the form "Every element of $X$ has property $P$ " is to show that every element of $K$ has property $P$ and to show that anything you generate using elements that have property $P$ also has property $P$ .

In this article we concentrate on closure properties that have an algebraic flavour. Another sort of closure is topological closure: this is dealt with in the article Prove the result on a dense subset and then prove that the set where the result holds is closed.

This article could use additional contributions. This article could do with more examples.

Prerequisites

These vary from example to example. Material from a typical mathematics degree course is discussed, but more advanced topics are briefly explained, and links to relevant Wikipedia articles are given.

General discussion

An equivalent way of thinking about what it means for a set $K$ to generate another set $X$ is to say that $X$ is a certain sort of closure of $K$ . More precisely, suppose that you have a way of generating elements of $X$ from other elements (or pairs of elements, or sequences of elements, etc.). A set $Y$ is closed if anything you can generate using elements of $Y$ belongs to $Y$ . Given any set $K$ , the closure of $K$ is the smallest closed set that contains $K$ . It is what you get if you start with $K$ , generate everything you can from $K$ , generate everything you can from $K$ with the new elements you've added, and so on (where in some situations the words "and so on" could refer to a transfinite process). In this language, if you want to prove a statement $P$ about every element of $X$ , it is enough to prove it for every element of a subset $K$ , to show that the set of elements that satisfy $P$ is closed under some process of generating new elements, and to show that the closure of $K$ is $X$ .

This technique can be (and often is) thought of as a generalization of induction. To obtain the usual principle of induction take $X$ to be the set of all positive integers, $K$ to be the set $\{1\}$ , and the operation used to create new elements to be that of replacing a number by its successor. To prove a statement about all positive integers, it is enough to prove it for $\{1\}$ and to prove that if it is true for $n$ then it is true for the successor of $n$ . The principle of induction is the statement that $\mathbb{N}$ is the closure of $\{1\}$ under the successor operation.

Example 1: Möbius maps take circles or straight lines to circles or straight lines

A Möbius map, or Möbius transformation, is a function from $\mathbb{C}$ to $\mathbb{C}$ given by a formula of the form $z\mapsto\frac{az+b}{cz+d}$ , where $a$ , $b$ , $c$ and $d$ are complex numbers with $ad-bc\ne 0$ . An important fact about Möbius maps is that they take circles to circles, at least if one counts a straight line as a degenerate circle (with its centre at $\infty$ ). How does one prove this fact?

Perhaps one could express what a Möbius transformation does in terms of the real and imaginary parts of $z$ , write an equation for a circle, apply the transformation, and try to find an equation for the resulting set. But this feels as though it is going to be very complicated, and if it works it will still have the drawback of giving us no idea why the result is true.

Fortunately, there is a much better approach. The Möbius transformations form a group under composition, and it is obvious that if $S$ and $T$ are two maps that both take circles/lines to circles/lines, then so does $ST$ (since if you do $T$ and then $S$ , you take a circle/line to a circle/line and then to another circle/line). So all we have to do is prove the result for some set of maps that generates the Möbius group.

It is an easy exercise to prove that every Möbius map can be built out of translations, rotations, dilations and the map $z\mapsto 1/z$ (which is called inversion). Note that these are all Möbius maps: a translation is given by the formula $z\mapsto z+w$ , and $z+w=\frac{1z+w}{0z+1}$ . Rotations are of the form $z\mapsto wz$ for some complex number with $|w|=1$ , and dilations are of the form $z\mapsto az$ with $a$ a positive real number. A hint for showing that these maps generate the Möbius group: note that if $c\ne 0$ then $\frac{az+b}{cz+d}=\frac ac+\frac{b-da/c}{cz+d}$ (if $c=0$ then it is even easier).

It is completely obvious that translations, rotations and dilations take circles/lines to circles/lines. The one thing that takes a bit of verification is that inversion works. Even here one can reduce the calculation by conjugating: since we know that rotations preserve circles/lines, it is enough to consider circles centred on the non-negative real axis, and lines that cross the non-negative real axis at right angles. This leaves us with a far simpler calculation than we would have had to face if we had just plunged straight in and tried to investigate the effect of an arbitrary Möbius map on an arbitrary circle/line.

Just to see how this example fits into our general framework, note that we are taking $X$ to be the set of all Möbius maps, $K$ to be the set of all translations, rotations and dilations, and inversion, and we observe that the set of maps with the property we want (namely, taking circles/lines to circles/lines) is closed under composition, and we showed that the closure of $K$ is all of $X$ .

Example 2: all Borel subsets of $[0,1]$ are Lebesgue measurable

This is an example where one is more or less forced to use the method, since the Borel sets are defined via generators and closure properties. The generators are all open intervals, and the operations one can perform are countable unions and countable intersections. That is, the collection of Borel sets is the smallest collection of sets that contains all open intervals and is closed under countable unions and countable intersections.

Let us briefly recall the definition of Lebesgue measure for subsets of $[0,1]$ . (We are confining ourselves to $[0,1]$ just because it is convenient to avoid the minor technicalities needed to discuss sets of infinite measure.) If $U$ is an open subset of $[0,1]$ , then it can be expressed as a countable union of disjoint open intervals. Proof: Define elements $x$ and $y$ of $U$ to be equivalent if every $z$ between $x$ and $y$ also lies in $U$ ; check that the equivalence classes are disjoint open intervals; since every open interval contains a rational, there are countably many of them. The measure of $U$ is then defined to be the sum of the lengths of these open intervals. And now, if $A$ is an arbitrary subset of $[0,1]$ , we define its outer measure to be the infimum over all open sets $U$ that contain $A$ of the measure of $U$ . A set $A$ is Lebesgue measurable if the outer measures of $A$ and $A^c$ add up to 1.

To prove that every Borel set is measurable, one must now prove that if $A_1,A_2,A_3,\dots$ are all measurable, then so is $\bigcup_{n=1}^\infty A_n$ . (Since the complement of a measurable set is obviously measurable, this is enough to do countable intersections as well, so it proves the whole result.) Very roughly, the technique for doing this is to find, for each $A_n$ , an open set $U_n$ containing $A_n$ with measure at most $\epsilon/2^n$ more than the measure of $A_n$ , and a closed set $F_n$ contained in $A_n$ with measure at most $\epsilon/2^n$ less than the measure of $A_n$ , and to argue that the union of the sets $U_n$ has measure at most $2\epsilon$ more than the union of the sets $F_n$ . This does not quite do the job because the union of the $F_n$ is not necessarily closed. However, once one has proved that a countable union of closed sets (or alternatively a countable intersection of open sets) is Lebesgue measurable, then one can approximate it by a closed set (or open set).

We omit the details of this, since the main purpose of this example is to illustrate the range of statements that can be proved using generators and closure properties, rather than to give full details of the proofs. (However, if anybody felt like adding a concise proof, that would of course be fine.)

Comments

Regarding presevation of circles by a mobius map

Fri, 01/05/2009 - 10:43 — Sameed

An even better approach might be to take the Riemann sphere point of view.It is then natural that the Mobius transformations are the rotations of this sphere and the preservation of circles follows from the fact that stereographic projections map circles to circles.

Obviously that proof is not

Fri, 01/05/2009 - 12:47 — gowers

Obviously that proof is not appropriate in this article. But it might be nice to write an account of it, decide what general trick it illustrates, and write a geometry article about that general trick. Then one could link from this article saying that there was an alternative, more conceptual proof.

Post new comment

(Note: commenting is not possible on this snapshot.)