Mathematical Proof/Methods of Proof/Constructive Proof

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search
Mathematical Proof
  1. Introduction
    1. Logical Reasoning
    2. Notation
  2. Methods of Proof
    1. Constructive Proof
    2. Proof by Contrapositive
    3. Proof by Contradiction
    4. Proof by Induction
    5. Counterexamples

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.

Contents

[edit] Parts of a Theorem

A Theorem is a proven statement that was constructed using an axiom. Some theorems are very complicated and involved, so we will discuss their different parts.

[edit] 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 is a subset of the other.

[edit] 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.

[edit] Definition

While a definition is not usually part of a theorem, they are commonly introduced immediately before a theorem, in order to make the theorem make sense or to help in proving 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, x_i\in B so we see that B has at least n elements, that is |B|\ge n. Also, every element of B is in A, so it follows that there are no more elements in B than there are in A, so |B|\le n, thus |B| = n = |A|, which concludes the proof.

[edit] Pseudo 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 couple other main terms used in the mathematical world. For lack of a better term, I have lumped them together in the category of psuedo-theorems, since they are like theorems, but are different.

[edit] 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|\le |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|\ge 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|\le |B|. Also, since B\subset A, we see that |B|\le |A|. Now we use a fact about numbers, that if x\le y and y\le x, it must follow that x = y.

[edit] Corollary

A corollary is similar to a lemma in that it is usually a small or not-quite-so-Earth-shattering as a theorem. However, a corollary is a result that follows almost immediately from a theorem.

Assume that we had proved the theorem that "All people are pigs." Then a corollary would be "People who have two legs are pigs." which clearly follows from the first result. A slightly more interesting corollary would be "People can be sold for bacon when they die." since it is common knowledge that bacon comes from pigs.

So we see that a corollary is something that follows from a preceding theorem with minimal argument to support it. It is either "common sense" or "obvious" to the reader that it is a direct consequence of the theorem.

[edit] 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|\le|A|+|B| and that equality holds when A\cap B =\varnothing.

[edit] 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|\le |B|, can you show that A\subset B?
Answers | Next section
Retrieved from "http://en.wikibooks.org/wiki/Mathematical_Proof/Methods_of_Proof/Constructive_Proof"