Tricki
a repository of mathematical know-how

Revision of Proving universal statements from Sun, 07/12/2008 - 22:18

Quick description

This page is an index of general methods for proving statements that begin with a universal quantifier. It needs to be improved and expanded, and the not yet active linked articles need to be written.

Method 1: Convert "every x" into a single arbitrary x.

All this means is that if you are trying to prove \forall x\in X\ P(x) then you begin by writing "Let x\in X," and you then try to prove that P(x), perhaps ending by writing, "Since x was arbitrary, the proof is complete." For example, if you are asked to prove that every group of prime order is cyclic, then you begin by writing ``Let p be a prime and let G be a group of order p.'' You then proceed as though p were a fixed number.

Method 2: Induction

If the statement is equivalent to a statement of the form " \forall n\in\mathbb{N}\ P(n)" then consider using induction in one of its various forms. For example, the statement "Every positive integer can be written as a product of primes" can be proved by starting with the line "Let n be a positive integer and suppose that every positive integer less than n can be written as a product of primes."

Induction is discussed in vastly more detail here.

General discussion

Note that induction is a special case of method 1: in both cases we avoid having to write out a separate proof for every x by writing a single proof for a variable x. Because of this, every statement that begins with a string of quantifiers can be made to feel as though what it needs is a proof of existence. For example, if we are asked to prove from first principles that the function f(x)=x^2 is continuous, then we are asked to prove that for every x and every \epsilon>0 there exists \delta>0 such that if |y-x|<\delta then |y^2-x^2|<\epsilon. If we start by writing "Let x be a real number and let \epsilon>0", then the problem becomes one of proving the existence of a positive number \delta with a certain property. Of course, this property depends on x and \epsilon, as does \delta. Another way of thinking of the problem as an existence problem is to say that we are trying to find a function \delta of two variables x and \epsilon such that whenever y and x are real numbers with |y-x|<\delta(x,\epsilon) we have |y^2-x^2|<\epsilon.

For this reason, the Tricki will concentrate far more on proofs of existence than on proofs of "for all" statements. However, let us mention universal problems that do not convert so easily into existence problems, and also problems that are not naturally thought of as beginning with either an existential quantifier or a universal one. In the first category are problems that are susceptible to the next method.

Method 3: Classification

If you find it hard to prove the statement P(x) for an abstract element x of a set X, then all is not necessarily lost: you may be able to classify the elements of X and prove P(x) for each one.

For example, if your statement is of the form "Every finite simple group has property Q," then you may find that Q does not follow straightforwardly from the simplicity assumption, but that it can be checked for any group that belongs to one of the infinite families of finite simple groups, and also for all the 26 sporadic groups. One could regard such a proof as starting with the line "Let G be a finite simple group," and continuing with "By the classification of finite simple groups, G must be one of the following groups." But the first of these two lines is not terribly helpful.

Different styles of "for all" problem

This part of the article is an attempt to classify universal statements into different common types.

Deducing one property from another

Many mathematical theorems take the form " \forall X\ P(X)\Rightarrow Q(X)", where X is some mathematical structure and P and Q are two properties that X can have. For instance, "Every group of prime order is cyclic" comes into this category. There is no single method for proving all statements of this kind, but this article is a page with links to articles about solving various classes of them.