Universal constructions

Quick description

Suppose you are asked to prove that a mathematical object $X$ of a certain type can be found that satisfies some property $P$ . It quite often happens that there is a partial order on the given kinds of objects such that if $X$ is less than $Y$ and $X$ has property $P$ , then so does $Y$ . If that is the case, then one can look for objects that are maximal in this partial order. And of course the same is true if we replace "less than" and "maximal" by "greater than" and "minimal".

This article is very far from finished: eventually there needs to be a rather large set of examples taken from all over mathematics (and not just algebra).

Example 1

Let $G$ be a group with two generators $a$ and $b$ . This means that every element of $G$ can be written as a product of powers of $a$ and $b$ . (In other words, all elements of $G$ are things like $a^5b^2a^{-3}ba$ .) Define the length of a product such as $ab^3a^{-5}b^4$ to be the sum of the absolute values of the powers of $a$ and $b$ (so the product $ab^3a^{-5}b^4$ has length 13, for example), and define the ball of radius $k$ about the identity to be the set of all elements that can be expressed as a product of length at most $k$ .

Now some products can be equal to others. For example, the group $\mathbb{Z}^2$ is generated by the two elements $a=(1,0)$ and $b=(0,1)$ . Using multiplicative notation, we then find that $ab^3a^{-5}b^4=a^{-4}b^7=(-4,7)$ . In this group, the ball of radius $k$ about the identity consists of all points $(m,n)$ such that $|m|+|n|\leq k$ . From this it follows that the size of the ball of radius $k$ is roughly $2k^2$ when $k$ is large.

Is it possible for the size of the ball of radius $k$ to grow much more rapidly than this as $k$ tends to infinity? This is not a very difficult question once one knows the right way of thinking about it. And the right way springs from the observation that if we want to define a group with two generators $a$ and $b$ in such a way that the size of the ball of $k$ increases as rapidly as possible, then we want as few as possible of the products involving $a$ and $b$ to be equal.

We can make this idea more precise as follows. Suppose that $G$ is a group generated by two elements $u$ and $v$ , and $H$ is a group generated by two elements $a$ and $b$ . Suppose also that there is a homomorphism from G to H (meaning a map $\phi$ from $G$ to $H$ such that $\phi(g_1g_2)=\phi(g_1)\phi(g_2)$ for every pair of elements $g_1,g_2\in G$ ) such that $\phi(u)=a$ and $\phi(v)=b$ . Then the ball of radius $k$ in $G$ is at least as big as the ball of radius $k$ in $H$ . Why? Because if two products are equal in $G$ then the corresponding products are equal in $H$ . For example, if we know that $uv^3u^{-1}=v^5u^2v$ , then $\phi(uv^3u^{-1})=\phi(v^5u^2v)$ , and since $\phi$ is a homomorphism that tells us that $\phi(u)\phi(v)^3\phi(u)^{-1}=\phi(v)^5\phi(u)^2\phi(v)$ , which in turn tells us that $ab^3a^{-1}=b^5a^2b$ .

The structures we are considering here are of the form $(G,u,v)$ , where $G$ is a group and $u$ and $v$ are generators of $G$ . Let us write $(G,u,v)\geq(H,a,b)$ if there is a homomorphism $G\rightarrow H$ such that $\phi(u)=a$ and $\phi(v)=b$ . It is easy to check that if $G\geq H$ and $H\geq G$ then $G$ and $H$ are isomorphic. It is also easy to check that if $G\geq H$ and $H\geq K$ then $G\geq K$ . Therefore, we have a (which basically means an ordering like "is a subset of" where not every pair of objects can be compared) on these structures. We have just shown that if $G\geq H$ then the ball of radius $k$ in $G$ is at least as big as the ball of radius $k$ in $H$ .

Therefore, If we are looking for an example where the ball of radius $k$ is big, then it makes sense to try to choose $G$ to be maximal in this partial order – if we can, that is. And it turns out that we can. The free group on two generators $a$ and $b$ is defined (loosely) as the group where the only products that are equal are those that are forced to be equal by the group axioms: for example, $abb^{-1}a$ is equal to $a^2$ , since the group axioms allow us to cancel $bb^{-1}$ . It is intuitively clear, and not that hard to prove rigorously, that the free group $F$ on two generators $r$ and $s$ has the following universal property: given any group $G$ with two generators $u$ and $v$ there is a homomorphism from $F$ to $G$ such that $r$ maps to $u$ and $s$ maps to $v$ . The homomorphism takes a word such as $rs^{-3}r^4sr$ and simply maps it to the corresponding word $uv^{-3}u^4vu$ . One must check that this is well-defined. Why might it not be? Well, there would be a problem if two products involving $u$ and $v$ were equal but the corresponding products involving $r$ and $s$ were different. But this cannot happen, since the only equalities in $F$ are the ones forced by the group axioms, so if two products in $F$ are equal then the corresponding products in $G$ are equal.

It follows from the discussion above that the ball of radius $k$ in the free group is as big as it can possibly be. Since there are $2^k$ products that are made out of just $r$ and $s$ and not their inverses, and since no cancellation is possible in such a product, the ball of radius $k$ in the free group on two generators has size at least $2^k$ . That is, it is possible for the size of the ball of radius $k$ to grow exponentially in $k$ rather than polynomially as it did in $\mathbb{Z}^2$ .

The rate of growth of the ball of radius $k$ is a very important parameter of an infinite group and is and has been the subject of a great deal of research.

Example 2

Is there an ordered field that does not satisfy the Archimedean property? That is, is there an ordered field that contains a positive element $x$ such that $x<1/n$ for every positive integer $n$ (where a positive integer $n$ is defined to be one of the field elements $1$ , $1+1$ , $1+1+1$ , etc.)?

To answer this question, let us try to build a minimal example. It is a nice exercise to prove that every ordered field contains a copy of the rationals, so let us start with the rationals and try to extend them in a minimal way.

Since we know that an ordered field that does not satisfy the Archimedean property must (by definition) contain a positive $x$ such that $x<1/n$ for every $n$ , and since no rational number has this property, we are forced to adjoin a new element with the property. Let us call it $x$ .

Since we are going for a minimal example, our next aim is to put into our field only what we are forced to put in by the field and order axioms. To be more accurate, we use closure properties of fields to determine what else we must add, and we use other field axioms and order axioms to determine how the field operations and order properties behave on our new elements.

For instance, since fields are closed under multiplication, $x^2$ must also be an element of our field, and the order axioms imply that it will be positive and smaller than $x$ , and therefore not equal to $x$ or any rational. Similarly, $3+x$ will be smaller than any real number that is greater than $3$ . If one explores consequences of this kind, one finds that the elements that are forced to belong to the field are all elements of the form $P(x)/Q(x)$ where $P$ and $Q$ are polynomials and $Q$ is not the zero polynomial. And of course if $PS=QR$ then $P(x)/Q(x)$ and $R(x)/S(x)$ are the same element. As for the ordering, we can work it out as follows. We say that $P(x)$ is positive if the leading coefficient of $P$ is positive, and otherwise it is negative. And $P(x)/Q(x)$ is positive if $P$ and $Q$ have the same sign. And finally, $P(x)/Q(x)$ is less than $R(x)/S(x)$ if $R(x)/S(x)-P(x)/Q(x)$ is positive. It is not too hard to check that this is a well-defined ordering that gives us an ordered field, and that the entire ordered field was indeed determined by minimality and the one fact that $x$ is smaller than any constant polynomial. So now we have our ordered field in which the Archimedean property is false. Let us call it $\mathbb{Q}[x]$ .

Here is a more formal "universal property" that this construction satisfies: if $\mathbb{F}$ is any ordered field that fails the Archimedean property and $y$ is any positive element of $\mathbb{F}$ that is smaller than every $1/n$ , then there is a unique field embedding from $\mathbb{Q}[x]$ to $\mathbb{F}$ that takes $x$ to $y$ . This gives us a precise sense in which our example is "smallest".

A similar method can be used to construct a smallest ordered field that contains $\mathbb{R}$ and does not satisfy the Archimedean property. This field is discussed for a different reason in an article on demonstrating that certain approaches to certain problems cannot work, where it appears as Example 3.

Example 3

Every normed space is contained in a Banach space. That is, to be slightly pedantic about it, for every normed space $Y$ there exists a Banach space $X$ that has a subspace isometric to $Y$ .

How do we prove this? Well, if $X_1$ is a Banach space that contains $Y$ and $X_2$ is a Banach space that contains $X_1$ , then $X_2$ is a Banach space that contains $Y$ . So the philosophy behind universal constructions tells us that it makes sense to aim for a minimal example of a Banach space that contains $Y$ . The result turns out to be unique, and it is called the completion of $Y$ (the smallest space that "makes $Y$ complete").

Let's assume then that we have a Banach space $X$ that contains $Y$ , and see what $X$ is forced to contain. Of course, we will eventually have to prove that it is possible for a Banach space to contain $Y$ , or our argument will be circular, but for now our aim is to describe what a minimal example would be like if there is an example.

A completely obvious condition that $X$ will have to satisfy is this: if $y_1,y_2,y_3,\dots$ is a Cauchy sequence, then it must converge to a limit in $X$ . If it didn't then $X$ wouldn't be complete. So a natural idea would be to adjoin to $Y$ an extra element for each Cauchy sequence $y_1,y_2,y_3,\dots$ that does not converge in $Y$ . That way, we would "force" the sequence to converge in the bigger space.

However, we are being a little hasty here. If we adjoin an extra element in order to make one sequence converge, there may be some good news and some bad news. The good news is that we may make other sequences converge at the same time, and the bad news is that we may create new Cauchy sequences that do not converge. Let us think about these two possibilities in turn.

Suppose that $y_1,y_2,y_3,\dots$ is a Cauchy sequence in $Y$ , and that $y_1',y_2',y_3',\dots$ is another Cauchy sequence. When would we expect them to converge to the same limit? A neat answer is this: form the sequence $y_1,y_1',y_2,y_2',y_3,y_3',\dots$ . If that sequence is also Cauchy, then we want it to converge to a limit, and that limit will have to be the limit of both the $y_n$ and the $y_n'$ . Conversely, if the interwoven sequence is not Cauchy, then we know that the two original sequences cannot tend to the same limit in any space, and in particular in our minimal space $X$ .

Let us define two Cauchy sequences that do not converge in $Y$ to be equivalent if the sequence formed by interweaving them is Cauchy. The remarks of the previous paragraph imply that we would be in trouble if this relation was not an equivalence relation, but it is not hard to check that it is one. So now let us adjoin to $Y$ a whole lot of new elements, one for each equivalence class of nonconvergent Cauchy sequences.

There is more that we have to do, however. We can't just adjoin elements unless we say how to add them, multiply them by scalars, and define their norms. In each case it is obvious what to do: for example, if $y_1,y_2,y_3,\dots$ is a Cauchy sequence that doesn't converge, and $x$ is the corresponding adjoined element, then we define $\|x\|$ to be the limit of $\|y_n\|$ as $n\rightarrow\infty$ . And in each case, we must check that what we do is well-defined: here we need to know that if we had taken an equivalent sequence, we would have ended up with the same definition of $\|x\|$ . And in each case, the verification that the definition is well-defined is a very straightforward exercise.

What this proves, if we do all the routine verifications, is that $Y$ can be embedded into a larger normed space $X$ in such a way that every Cauchy sequence in $Y$ has a limit in $X$ . But does every Cauchy sequence in $X$ have a limit in $X$ ? If it didn't, then we would have to repeat the process of adjoining new elements, but it turns out that it does. Indeed, suppose that $x_1,x_2,x_3,\dots$ is a Cauchy sequence in $X$ . Then each $x_n$ is close to some $y_n$ in $Y$ . If $\|y_n-x_n\|$ tends to $0$ then the sequence $y_1,y_2,y_3,\dots$ is a Cauchy sequence in $Y$ , so it has a limit in $X$ , and this is the limit of the $x_n$ as well.

The universal property that $X$ has is that if $Y$ is isometric to a subspace $U$ of a complete normed space $Z$ , then there is a closed subspace $V$ of $Z$ such that $U\subset V$ and $X$ is isomorphic to $V$ .

A very similar argument proves that every metric space can be embedded in a minimal way into a complete metric space. Again the resulting space is called the completion.