Tricki

## 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 " into a single arbitrary .

All this means is that if you are trying to prove then you begin by writing "Let ," and you then try to prove that , perhaps ending by writing, "Since 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 be a prime and let be a group of order .'' You then proceed as though were a fixed number.

#### Method 2: Induction

If the statement is equivalent to a statement of the form " " 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 be a positive integer and suppose that every positive integer less than 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 by writing a single proof for a variable . 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 is continuous, then we are asked to prove that for every and every there exists such that if then . If we start by writing "Let be a real number and let ", then the problem becomes one of proving the existence of a positive number with a certain property. Of course, this property depends on and , as does . Another way of thinking of the problem as an existence problem is to say that we are trying to find a function of two variables and such that whenever and are real numbers with we have .

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 for an abstract element of a set , then all is not necessarily lost: you may be able to classify the elements of and prove for each one.

For example, if your statement is of the form "Every finite simple group has property " then you may find that 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 be a finite simple group," and continuing with "By the classification of finite simple groups, 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 " ", where is some mathematical structure and and are two properties that 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.