Tricki
a repository of mathematical know-how

Make use of special cases and transitivity

Quick description

To establish a result for all objects X, it sometimes suffices to establish it for some relatively simple special cases from which the full result can more straightforwardly be deduced. A typical situation might be that one wants to show that two collections of objects X and Y are 'equivalent'; the easiest way to do so might be to show that they are both 'equivalent' to a third, simple collection of objects Z.

Note iconContributions wanted This article could use additional contributions. More examples needed.

Prerequisites

Complex numbers for an example, and the idea of an equivalence relation to set things in context.

Example 1: Möbius transformations and triples of points

A Möbius map, or Möbius transformation, is a function from \C to \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. Such maps form a group under composition, as discussed in an example in the article Using generators and closure properties. We will consider Möbius transformations acting on complex numbers, as well as on the special symbol \infty; indeed, they act on the Riemann sphere \C \cup \{ \infty \}.

Consider the collection of triples (x,y,z) of distinct points in \C \cup \{ \infty \}. It turns out that any such triple of points can be mapped to any other triple (x',y',z') of distinct points by a Möbius transformation. If one attempts to show this directly by finding suitable values for a,b,c,d by substitution, however, the algebra quickly gets quite messy. This is where the technique of this article comes in: if the triple (x,y,z) is supposed to be mappable to any other triple (x',y',z'), then one must certainly be able to map it to the simple triple (0,1,\infty). But if one can do that for any triple (x,y,z), then to show that (x,y,z) can be mapped to (x',y',z') in general one can simply take the composition of a map that takes (x,y,z) to (0,1,\infty) with the inverse of one that takes (x',y',z') to (0,1,\infty). Thus once one has established that all triples are 'equivalent' to the simple case (0,1,\infty), one is done. Furthermore, establishing this last fact is relatively simple, by virtue of having chosen a simple representative.

General discussion

In the above example, there was a natural choice for the 'simple special case' for which it sufficed to establish the result. A choice of such an object may not always be so obvious, but can often be found after a little thought. The technique can also be applied in situations where the notion of 'equivalence' is slightly more rough, not actually being an equivalence relation but just a transitive relation, meaning that if X is related to Y and Y is related to Z, then X is related to Z.

Comments

Inline comments

The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.

Equivalence needed

Olof, it seems to me that if you have one simple special case S, say, that's related to everything, and want to show that X is related to Y, then you'll need both symmetry and transitivity, since you get X related to S by symmetry and then X related to Y by transitivity. So it seems rather unlikely that there will be interesting examples where the relation is not an equivalence relation. Do you have any?

Perhaps

The remark stems from a previous version of the article, in which I had included Lebesgue's proof of the Weierstrass approximation theorem as an example of the technique, and I think the following is what I had in mind.

Define a relation ~ on collections of functions [a,b] \to \R, saying that A ~ B if and only if any function in A can be uniformly approximated arbitrarily well by a function in B. Weierstrass approximation is the statement that if

  • X is the collection of continuous functions on [a,b] and
  • Y is the collection of polynomials on [a,b],

then X ~ Y. Lebesgue's proof proceeds via the intermediate collection Z, the collection of piecewise linear functions on [a,b]. Now, ~ is not a symmetric relation in general, which is why I made that remark.

That said, I guess ~ is an equivalence relation if one restricts it to just the collections X, Y and Z, though one does not really need to know this. (One only needs the transitivity, which follows from the unrestricted version of the relation.)

Actually, having re-read the quick description of the article, I now see why this is an issue: I wrote "show that they are both 'equivalent' to a third", whereas I was thinking "show that X ~ Z and Z ~ Y for some Z".

So either the quick description should be changed, or that remark should go. I'm not sure if there are interesting examples where ~ is not be an equivalence relation restricted to X, Y and Z, and even if they are, perhaps this article should be restricted to dealing with equivalence relations. I'll leave things as they are for a while in case someone else has an idea.

[The Weierstrass example is now in the article Prove the result on a dense subset and then prove that the set where the result holds is closed.]