Proving "for all" statements

a repository of mathematical know-how

Proving "for all" statements

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]

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|Convert "every $x$" into a single arbitrary $x$]] [cut] Quick description || 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. [/cut]

Method 2: [[Induction front page|Induction]] [cut] Quick description || 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." [/cut]

Method 3: [[Using classification results|Classification]] [cut] Quick description || 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. This page is an annotated index of Tricki articles about different classification theorems and how they can be used. [/cut]

Method 4: [[Prove the result for some cases and deduce it for the rest]] [cut] Quick description || It is often possible to establish a result for all objects in a collection by first establishing it for certain cases and then deducing the general result from these cases. This page gives links to various techniques of this general kind. [/cut]

[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, there are some universal problems that do not convert so easily into existence problems, and there are also problems that are not naturally thought of as beginning with either an existential quantifier or a universal one, so the Tricki will not be devoted solely to existence problems.

=== Different styles of "for all" problem ===

This following pages are about universal statements of different common types.

[[Deducing one property from another]] [cut] Quick description || 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. [/cut]

[note article incomplete] It would be good to have more categories of problem and some kind of conclusion to this article. [/note]

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.

Proving "for all" statements

Recent articles

Active forum topics

Recent comments