Mathematical Proof/Methods of Proof/Direct Proof

A constructive proof is the most basic kind of proof there is. It is a proof that starts with a hypothesis, and a person uses a series of logical steps and a list of axioms, to arrive at a conclusion.

Parts of a Theorem

A theorem is a proven statement that was constructed using previously proven statements, such as theorems, or constructed using axioms. Some theorems are very complicated and involved, so we will discuss their different parts.

The Hypothesis

The hypothesis is the "if" statement of a theorem. In a way, it is similar to an axiom because it is assumed to be true in order to prove a theorem. We will consider a simple example.

Theorem 2.1.1. If A and B are sets such that $A\subseteq B$ and $B\subseteq A$, then A=B.

In this theorem, the hypothesis is everything before the word "then." This is a very simple proof. We need to prove that for every x, $x\in A\Leftrightarrow x\in B$. For the purpose of analyzing proofs, we will define $P(x)=x\in A$ and $Q(x)=x\in B$. The most common way to prove an "if and only if" statement is to prove necessity and sufficiency separately

• So we start by showing that $P(x)\Rightarrow Q(x).$ Therefore, we assume that P(x) is true. That is, $x\in A.$ Since we assumed, by hypothesis, that $A\subseteq B,$, we know that $x\in B$, which means that Q(x) is true.

• Now we show that $Q(x)\Rightarrow P(x)$, so we assume that Q(x) is true. This means that $x\in B$. Since we know that $B\subseteq A,$ we know that $x\in A,$ so P(x) is true.

By these two conclusions, we see that $P(x)\Leftrightarrow Q(x).$

Now, by axiom 3, A=B, since $x\in A\Leftrightarrow x\in B.$ This concludes the proof. This is a very trivial proof, but its point was to show how to use a hypothesis or set of hypotheses in order to reach the desired conclusion. This method here is the most common in proving that two sets are equal. You prove that each set is a subset of the other.

The Conclusion

The part of the theorem after the word "then" is called the conclusion. The proof of a theorem is merely the logical connection between the hypothesis and the conclusion. Once you've seen and proved a few theorems, a conclusion is almost predictable. For example, what conclusion would you naturally draw from the following two statements?

1. All Americans are people.
2. All people live on Earth.

These two statements are the hypotheses. To word this as a theorem, we would have "If all Americans are people and all people live on Earth, then all Americans live on Earth." This statement is what most people would call completely obvious and requires no proof. However, to show how this concept is applied in mathematics, we will abstract this theorem and prove it.

Theorem 2.1.2. If $A\subset B$ and $B\subset C$, then $A\subset C$.

To see how this relates to our problem, let A be the set of all Americans, B the set of all people, and C the set of all things that live on Earth.

To show that $A\subset C$, we need to show that $\forall x\in A,x\in C.$ So we suppose $x\in A.$ By hypothesis, $A\subset B,$ so $x\in B.$ Also by hypothesis, $B\subset C$, so $x\in C.$ Since this was true for any arbitrary $x\in A,$ we have shown that $A\subset C.$

The Definition

While a definition is not usually part of a theorem, they are commonly introduced immediately before a theorem, in order to help define the symbols you use or to help prove it.

Definition 2.1.3. If a set A has only finitely many elements, then the order of A, denoted by |A|, is the number of elements in A.

This definition gives meaning to the following theorem.

Theorem 2.1.4. If A and B are finite sets such that A = B, then |A|=|B|.

Here we take advantage of the fact that A is a finite set. Let n be the integer such that |A| = n. Then index the elements of A so that $A=\{x_{1},x_{2},\ldots ,x_{n}\}.$ Now $\forall i=1,2,\ldots ,n$, we have $x_{i}\in B$. So we see that B has at least n elements, that is $|B|\geq n.$ Also, every element of B is in A (by hypothesis), so it follows that there are no more elements in B than there are in A, so $|B|\leq n$, thus |B| = n = |A|, which concludes the proof.

The Given

Sometimes, the first part of a theorem lists what is required in order for a theorem to be proven. Hence, this list is described in the theorem as what is given. This helps readers understand exactly what is the hypothesis and what is the conclusion in a theorem statement. For example, Theorem 2.1.4 can be rewritten so that it lists what is required beforehand.

Theorem 2.1.4. Given finite sets A and B, if A = B, then |A|=|B|.

This statement clearly highlights what the hypothesis is and what the conclusion is, in this example.

Classifying Theorems

There are different terms that mathematicians like to use in stating mathematical results. Theorem is probably the most common and well-known, especially to non-mathematicians. There are, however, a few other related terms used in mathematics. They are all theorems, but have more specific uses.

Lemma

A lemma is a "small theorem." When a result is less profound, more trivial, or boring, it can be called a lemma. A lemma is also used to make the proof of a theorem shorter. That is, if a chunk of a proof can be pulled off and proved separately, then it is called a lemma and the proof of the theorem will say something to the effect of "as proved in the lemma."

For example, the following lemma will help to make the proof of Theorem 2.1.4 more concise.

Lemma 2.1.5. If A and B are finite sets and $A\subset B$ then $|A|\leq |B|$.

As you might guess, this is one motivation for the use of the symbol $\subset$, since it is similar in appearance to <.

Let n = |A|. Then number the elements of A, so $A=\{x_{1},x_{2},\ldots ,x_{n}\}.$ Then for each i from 1 to n we see that $x_{i}\in B$, which means that B has at least n different elements, or that $|B|\geq n=|A|,$ which is what we were trying to prove.

Now if we use this lemma twice on Theorem 2.1.4, we will get a very brief proof. Since $A\subset B$ we know that $|A|\leq |B|.$ Also, since $B\subset A$, we see that $|B|\leq |A|.$ Now we use a fact about numbers, that if $x\leq y$ and $y\leq x$, it must follow that x = y.

Corollary

A corollary is similar to a lemma in that it is usually a small and not as important as a theorem. However, a corollary is usually a result that follows almost immediately from a theorem. Corollaries tend to use a few well-known or established theorems and the primary theorem to prove. This is why corollaries are often found appended after a big theorem.

For example, Let's suppose we proved the theorem that "All people are pigs." Then a corollary would be "People who have heads are pigs." which clearly follows from the first result since "People have heads" is well-known and true (A person without a head would be rather odd, no?). Another, slightly more interesting, corollary would be "People can be sold for bacon when they die." since "bacon comes from pigs" is well-known and true.

So we see that a corollary is something that follows from a preceding theorem with minimal argument to support it. Note that theorems you declare as a corollary may not be so to others, as corollaries are subjective. However, thinking of a corollary as relying on either "common sense" or "obvious" to the reader that it is a direct consequence of the theorem is the proper thought when figuring out what to assign as a corollary.

Exercises

1. Prove that the following sets are equal. Verify it with a truth table or a Venn Diagram. You may assume that A, B, and C are nonempty sets. Also assume that U is the universe.
   1. $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
   2. $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
   3. $A^{c}-B=(A\cup B)^{c}$
   4. $A-B^{c}=A\cap B$
   5. $(A-B)\cup (A\cap C)=A-(B-C)$
2. Prove that if A and B are finite sets then $|A\cup B|\leq |A|+|B|$ and that equality holds when $A\cap B=\varnothing .$

3. Prove that the square of an odd number is an odd number.

Question Hint

Definition An odd number is defined as 2n + 1, where n is a natural number that can also be equal to 0.

Methodology Hint

The n in the form 2n + 1 doesn't have to be a number. It can be an equation.

Something to think about

• We have defined the order or size of a set for a finite set. Would it make sense to define this order for an infinite set? How would you tell whether two infinite sets are the same size?
• If you know that $|A|\leq |B|,$ can you show that $A\subset B?$