Using generators and closure properties

a repository of mathematical know-how

Using generators and closure properties

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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]].

[note contributions wanted] This article could do with more examples. [/note]

[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|M\"obius maps take circles or straight lines to circles or straight lines]

A ''M\"obius map'', or ''[[w:Möbius_transformation|M\"obius 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\"obius 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\"obius 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\"obius 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\"obius group.

It is an easy exercise to prove that every M\"obius 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\"obius 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\"obius 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\"obius 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\"obius 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|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 [[w:Borel_algebra|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 [[w:Lebesgue_measure|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 [add] 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.}} [/add] 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.)

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Using generators and closure properties

Recent articles

Active forum topics

Recent comments