Methodology of Proof -- an example

DEEP DOWN, all theorems are of the form IF A THEN B. They may be expressed in some other way, such as ALL A ARE B or LET A BE TRUE. THEN B IS TRUE, but the goal in each case is to get from the assumptions -- the A part -- to the conclusions -- the B part. To prove a theorem, you combine the assumptions with definitions and other theorems and show that the conclusion is always true. The hard part is figuring out what definitions and other theorems to use. Definitions and theorems let you convert statements to other statements; by stringing these definitions and theorems together you can convert the statements of A into the statements of B. This constitutes a proof. For instance:

Theorem 1   Let $x$ be a number greater than or equal to $4$. Then $2^x \geq x^2$.

This theorem converts the statement ``a number $x$ is greater than or equal to $4$'' to ``for this number, $2^x \geq x^2$. We can use it in the proof of another theorem, like so:

Theorem 2   Let $x$ be the sum of four squares, $a^2 + b^2 + c^2 + d^2$ where $a$, $b$, $c$, and $d$ are positive integers. Then $2^x \geq x^2$.

If we can prove that $x$ is of necessity greater than or equal to $4$ (by noting, for instance, that $a$, $b$, $c$, and $d$ are at least $1$, and thus their sum is thus at least $4$), then we can convert the assumption of our theorem from ``$x$ is the sum of four positive squares'' to ``$x$ is at least $4$.'' Then we can use the first proof to convert the statement ``$x$ is at least $4$'' to ``$2^x \geq x^2$.'' This completes our proof.

Often, we use definitions to expand out mathematical shorthand before we can start applying proofs. For instance, if an assumption is ``$x$ is prime,'' we might need to convert it to ``$x$ has exactly two positive divisors'' before continuing with the proof. If you are at a loss for how to start a proof, convert all the terms in the assumptions to their definitions.

Here is a theorem that can be proved using these techniques.

Theorem 3   Let $S$ be a finite subset of some infinite set $U$. Let $T$ be the complement of $S$. Prove $T$ is infinite.

Intuitively, this is saying that if you have an infinite supply of something, and you take a finite amount of it away, you are left with an infinite amount. This last sentence may seem obvious, but it is not a proof. To obtain a rigorous proof, we must get from the assumptions to the conclusion through theorems and definitions. We identify the assumptions: ``$S$ is a finite subset of an infinite set. It has a complement $T$.'' A good start is to expand the definitions in the assuption.

Definition 1   A set $S$ is finite if there exists a number $N$ such that the number of elements in $S$ (denoted $\vert S\vert$) is less than $N$. If no such $N$ exists, then $S$ is infinite.

Note that you give me the set $S$ before I try to figure out the number $N$. Thus, if any number $N$ exists that is bigger than $\vert S\vert$, I will be sure to find it, since I know what $S$ is. This ordering concern (``first we have $S$, then we find $N$'') is important with statements such as ``there exists'' or ``for all.''

Definition 2   If $S$ and $T$ are both subsets of some set $U$, $T$ is the complement of $S$ (under $U$) if $S \cup T = U$ and $S \cap T$ is $\emptyset$.

Now we use our definitions to convert our assumptions:

Original statement	New statement
$S$ is finite	There is a number $N$ such that $\vert S\vert < N$
$U$ is infinite	There is no number $M$ such that $\vert U\vert < M$
$T$ is the complement of $S$	$S \cup T = U$ and $S \cap T$ is $\emptyset$

We're still stuck, so we have to apply one of the proof methods which will be discussed in the next sections, which let you work backwards from the conclusion -- the B part -- to help prove the theorem. In particular, we need the common proof technique of proof by contrapositive: We assume that the result is false, and show that as a result, the assumptions must be false as well. But the assumptions are never false (by assumption!) so the theorem must be true.

In this case, we assume the result is false, that is that $T$ is in fact finite. Then, applying a definition, there is a number $P$ such that $\vert T\vert < P$. Since we know that $S \cup T = U$ and $S \cap T$ is $\emptyset$, we know $\vert S\vert + \vert T\vert = \vert U\vert$ (if you don't know this, then you can prove it on its own before you try to include it into this proof). But we know $\vert S\vert < N$ and $\vert T\vert < P$, so $\vert S\vert + \vert T\vert < N+P$; that is, $\vert U\vert < N+P$. But we have just violated the second assumption, that there is no number such that $\vert U\vert$ is less than it. The only weak link in our chain of deduction is that $T$ is finite, so that claim must be wrong. Since the contradiction is wrong, the theorem must be true. We write this up in a more terse, mathematical form.

Proof: We know that $S \cup T = U$ and $S$ and $T$ are disjoint, so $\vert S\vert + \vert T\vert = \vert U\vert$. Since $S$ is finite, $\vert S\vert < N$ for some $N$, and since $U$ is infinite, $\vert U\vert \geq M$ for all $M$. So assume $T$ is finite, that is, for some $P$, $\vert T\vert < P$. Then $\vert S\vert + \vert T\vert < N+P$, or, substituting, $\vert U\vert < N+P$. But this contradicts our claim that $\vert U\vert \geq M$ for all $M$.

That box is how I indicate the end of a proof. I am limited in what symbol I used by the fonts on my computer, but in general unlimited creativity is allowed here.