Mathematical Proof/Print version

Table of Contents

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
3. Proof and Computers

• Appendix
  • Answer Key
  • Symbols Used in this Book
  • Glossary

Introduction

If you've ever taken a math class or talked to a mathematician, you know that we don't talk like normal people do--we have our own language that's 2-bit encoded. For example, when a waiter says "Would you like corn or beans with your dinner?", you know that he wants the answer of "corn" or "beans" but not "both". Well, logically, if you ask the question "Would you like corn or beans with your dinner?", the answer could be "yes".

This chapter will acquaint you with logical statements, logical reasoning, and the cryptic language of mathematicians.

Logical Reasoning

As discussed in the introduction, logical statements are different from common English. We will discuss concepts like "or," "and," "if," "only if." (Here I would like to point out that in most mathematical papers it is acceptable to use the term "we" when referring to oneself. This is considered polite by not commanding the audience to do something nor excluding them from the discussion.)

Truth and Statements

A truth statement is one that is either true or false, not neither, and not both. Therefore, the sentence "This sentence is false." is not a truth statement because its truth value cannot be determined. However, the sentence "All people are cows." is a truth statement because its truth value can be determined, and is clearly false, since there are some people that are not cows. In mathematics, normally this phrase is shortened to statement to achieve conciseness and to avoid confusion.

The truth value of a statement is an evaluation of whether the statement is true (sometimes also referred or abbreviated as 1 or T) or false (sometimes referred also as 0 or F). Thus, the truth value of "2 < 3" is true and "4 > 5" is false.

In discussing logic and statements, it is common to use the letters P and Q as variables to denote statements. Throughout this section, this convention will be followed. We will now discuss logical connectors, or conjunctions that connect statements.

Logical Connectors

Or

The connector "or" is used to connect two statements and make a third statement whose truth value is based on the first two. The statement "P or Q" is true if either P or Q is true, or if both of them are true. Therefore, the statement, "The internet is complex or math is exciting." is true, given that either or both statements are true. Another example, the statement "7 > 9 or 2 < 3" is true, because one of the connected statements is true. The only time the statement "P or Q" is false is when both P and Q are false; an example of a statement where both P and Q are false is the following "All people are American or all Americans are tall". Clearly, the statement "All people are American" is false, and is false also the statement "all Americans are tall".

"Or" is sometimes denoted with the symbol $\lor$. So $P\lor Q$ means "P or Q." This is also sometimes referred to as disjunction.

And

"And" is used to connect two statements, just as "or"; however, "P and Q" is only true when both P and Q are true, and false otherwise. The statement "The author of this article likes cheesecake and broccoli." is true since the statements "The author of this article likes cheesecake." and "The author of this article likes broccoli." are both true. Of course, it doesn't mean that I like them together on the same plate or in my mouth at the same time as one might infer.

Another example might be the statement "2<6 and 3<6", which is true, since both statements "2<6" and "3<6" are true. The statement "2<6 and 3>6" is not true since "3>6" is false.

"And" is sometimes denoted as $\land$. $P\land Q$ means "P and Q." This is referred to as conjunction.

Implications and Conditional Statements

This is another class of logical connectors, like "and" and "or." The three implication types are "if" $\Leftarrow$, "only if" $\Rightarrow$, and "if and only if" or "iff" $\Leftrightarrow$. See also Necessary and sufficient conditions. The vast majority of mathematical proofs deal with statements such as $P\Rightarrow Q$ (P only if Q) or $P\Leftrightarrow Q$ (P if and only if Q).

Necessary

To say that "Q is necessary for P" means that P cannot exist without Q. Another way of saying this is "P only if Q" or "if P then Q". The notation for this is $P\Rightarrow Q$ (P implies Q).

The statement "It is necessary for the day to be a sunday if the day is Easter" is true because if it is Easter, then it must be also Sunday. The statement "P only if Q" is false only when P is true and Q is false, because Q is a necessary condition (it must be true) for P to be true.

Sufficient

To say that "P is sufficient for Q" means "P cannot exist without Q" or "if P then Q". The notation for this is $P\Rightarrow Q$. This statement is only false when P is true and Q is false. This is the same statement as $Q\Leftarrow P$, but the roles are reversed; the former, however, is more common.

The interesting thing about an implication (an if-then statement) is that in the case that P is false, $P\Rightarrow Q$ is always true. Thus, "If the world is flat, then the Sun does not exist" is a true statement. This kind of a statement is called vacuously true because Q can be replaced with any statement and the implication is still true. In fact, the mathematician Bertrand Russell boasted, "Give me any false statement and any other statement to prove and I will prove it". Given the statement "1 = 2" he was asked to prove that he was God. "Consider the set $\{Russell,God\}$", he replied, "since 1 = 2, the two elements are one, and therefore Russell = God".

"If" and "only if" statements are called conditional statements. These two are related, in fact they are the converse of each other. Converse simply means to switch the direction of the arrow. (The converse of $P\Rightarrow Q$ is $Q\Rightarrow P$.)

Necessary and Sufficient

To say that "P is necessary and sufficient for Q" means "P is true exactly when Q is true" or "P implies Q and Q implies P". This means that P and Q always have the same truth value—that is, they are both true or both false simultaneously. In mathematical symbols this is expressed as $P\Leftrightarrow Q$. This is referred to as a biconditional. When $P\Leftrightarrow Q$ is a true statement, we say that P and Q are logically equivalent.

Modifiers

We have explored truth statements and logical connectors used to create new statements. We will now look at two more variations of logical statements.

Negation

Negation refers to toggling a truth statement's truth value. The result is not always negative, or false, it is only the opposite of the original. Thus, the negation of "false" is "true." This is denoted by a tilde (~) or the negation symbol $\neg$.

It will be shown below in a truth table that the negation of the statement $P\lor Q$, which is $\neg (P\lor Q)$, is equivalent to $\neg P\land \neg Q$. Thus, to use loose terminology, "not or" is "and" (similarly, "not and" is "or").

Contrapositive

The contrapositive is related to negation. However, it is only defined for a conditional statement. It basically means negate both P and Q and switch the direction of the conditional. That is, the contrapositive of $P\Rightarrow Q$ is $\neg P\Leftarrow \neg Q$; or, equivalently, $\neg Q\Rightarrow \neg P$. It will be shown below that the contrapositive of a statement is equivalent to the statement itself.

Truth Tables

A truth table is helpful in visualizing all of these logical relations. The table is filled in by considering all possible combinations of true and false for P and Q and then filling in the results for the various connectors mentioned above.

The Or and And Table

OR and AND

P	Q	$P\lor Q$	$P\land Q$
T	T	T	T
T	F	T	F
F	T	T	F
F	F	F	F

If, Only if, and If and only if Table

If, only if, if and only if

P	Q	$P\Rightarrow Q$	$P\Leftarrow Q$	$P\Leftrightarrow Q$
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

Note that the $P\Leftrightarrow Q$ column can be obtained from $(P\Rightarrow Q)\land (P\Leftarrow Q)$. Truth tables are very useful in helping beginners understand logical relationships.

Negation and Contrapositive Table

Negation and Contrapositive

P	Q	$\neg P$	$\neg Q$	$P\Rightarrow Q$	$\neg Q\Rightarrow \neg P$
T	T	F	F	T	T
T	F	F	T	F	F
F	T	T	F	T	T
F	F	T	T	T	T

Exercises

In the following exercises, P, Q, R, and S will represent truth statements.

A. Construct the truth tables for the following statements, and give their converse and contrapositive:

1. 1. $\neg P\Rightarrow Q$
   2. $P\Rightarrow \neg Q$
   3. $(P\lor Q)\Rightarrow R$
   4. $(P\land Q)\Rightarrow (R\lor S)$
   5. $(P\Rightarrow Q)\Leftarrow (R\Rightarrow S)$

B. Negate the following statements:

1. 1. $P\land Q$
   2. $(P\lor Q)\land (R\land S)$
   3. $(P\land \neg Q)\lor (\neg R\lor S)$

Notation

While a comprehensive list of notation is included in the appendix, that is meant mostly as a reference tool to refresh the reader of what notation means. This section is to introduce the notation to the reader and explain its usage.

Basic Set Theory

This is not meant to be a comprehensive or rigorous definition of set theory. We will define a minimal amount of set-theoretical objects, so that the concept of mathematical thinking can be understood. In this book, we will use capital letters for sets and lowercase letters for elements of sets. This convention is not to discourage creativity or to bore your socks off, but to avoid confusion.

Axioms

An axiom is something that is assumed, or believed to be true. It is where mathematical proof starts; you cannot prove the axioms, you merely believe them and use them to prove other things. There are different sets of axioms, the most current and widely-used being Zermelo–Fraenkel set theory. I will give a list of axioms here that will suffice for the studies in this book.

1. A set exists. (A set, for our purposes, will be a collection of objects that we will call elements. A set is said to contain its elements, and the elements are said to be contained in the set.)
2. An empty set exists. This set will be denoted as $\varnothing$ and will contain no elements.
3. Two sets are equal if and only if they contain the same elements.
4. If $A$ and $B$ are sets, then there is a set containing only the elements of $A$ and $B$. This is called the union of $A$ and $B$.
5. If $A$ is a set and $P(x)$ is a truth statement defined for all $x$ contained in $A$, then there is a set $B$ so that $x$ is in $B$ whenever $P(x)$ is true.
6. The set of counting numbers $(1,2,3,\dots )$ exists; or, an infinite set exists.

Some of these are worded rather formally, which is a tendency for mathematicians. First of all, let's explain why we need these axioms.

The first axiom says "a set exists." So you might ask—don't we know that it exists? Can't we just define it to exist? The answer is, yes, and that's why it's an axiom. Axioms are supposed to be self-evident truths. Now that we've established the fact that sets exist, why would we want one with no elements? Well, the empty set turns out to be both a very useful and a very annoying set. You'll learn to be good friends with the empty set by the end of the text.

Axiom 3 could be considered a definition, rather than an axiom, of what we mean when we say that two sets are equal. Axiom 4 just says that if we have two sets then we can get a new set with all of those elements in it. For example, the set of all people and all dogs.

The fifth axiom is probably the most confusing. All it says is that if we have a set and we want to pick out certain elements, we can do that. For example, out of the set of all integers, we can choose the ones that are even, or the ones that are positive, or the ones that are perfect squares.

Finally, the infinity axiom is nice because we will do lots of things with infinite sets.

Definitions

As mentioned above, a set will be a collection of elements. For example, let $A$ be the set of all cheesecakes, and let $B$ be the set of all things that are chocolate. Mathematically, this would be denoted as:

$A=\{x|x{\mbox{ is a cheesecake}}\}$
$B=\{x|x{\mbox{ is chocolate}}\}$

The vertical bar | is read "such that". We can select elements in that way by using Axiom 5 from above. In the case of $A$, the predicate (truth statement) $P(x)$ used to select elements is:

$P(x)\ :\ x{\mbox{ is a cheesecake}}$

Note that we have implicitly assumed the existence of a universal set of all elements over which we are making a selection. In the example above, this universal set could be the set of all pastries. In general, if a universal set is not specified, we shall assume that we are talking about the real numbers $\mathbb {R}$. Thus, $C=\{x|x>2\}$ can be read as: "$C$ is the set of all real numbers strictly greater than $2$."

To say that $x$ is an element of $A$ is equivalent to saying that $A$ contains $x$. These concepts are notated mathematically by $x\in A$ (x belongs to the set A) and $A\ni x$. If $x$ is not a member of $A$ then we write $x\notin A$ (x does not belong to the set A).

The union of $A$ and $B$ is defined in axiom 4. It consists of all the elements in $A$ and $B$ and is denoted $A\cup B$. We can also use the | to say

$A\cup B=\{x|x\in A{\mbox{ or }}x\in B\}=\{x|x{\mbox{ is a cheesecake or is chocolate}}\}$

The intersection of $A$ and $B$ is the set containing all things that are in both $A$ and $B$. The notation for this is $A\cap B$.

$A\cap B=\{x|x\in A{\mbox{ and }}x\in B\}=\{x|x{\mbox{ is a chocolate cheesecake}}\}$

If $A\cap B=\varnothing$ then $A$ and $B$ are said to be disjoint. This means that there is nothing that is in both sets. For example, if $A$ is the set of all even integers and $B$ is the set of all odd integers, then they are disjoint.

Notice that the logical connectors $\lor ,\land$ coincide with the set operators $\cup ,\cap$. This is deliberate, since the concepts are related. This is obvious when the two symbols are juxtaposed:

$A\cup B=\{x|(x\in A)\lor (x\in B)\}$
$A\cap B=\{x|(x\in A)\land (x\in B)\}$

Quantifiers

Quantifiers are used to establish what elements are currently being discussed. They are like adjectives in English—they tell how much or what kind of thing we're talking about.

For All

The most common quantifier is for all. This is written mathematically as $\forall$. It is also "for each" or "for every." It is used to make statements like "All humans have eyeballs." That is, if $H$ is the set of all humans and $E$ is the set of all things with eyeballs, then

$\forall x\in H,x\in E$

which is read "For all $x$ in $H$, $x$ is in $E$." This introduces a special relationship between sets that is called a subset. In this case, $H$ is a subset of $E$ since every element of $H$ is also in $E$. (For the sake of the logical argument, just assume there aren't any people without eyeballs.) We write this as

$H\subset E.$ 

This notation, $A\subset B$, is ambiguous because some authors use it to mean just a subset, while others use it to mean a proper subset (meaning there is an element of $B$ that is not in $A$, and thus $A$ and $B$ are not equal) and use $A\subseteq B$ to denote that $A$ is a subset of $B$. In this book we will go with the convention that $A\subset B$ could mean that $A$ is a proper subset of $B$ or that $A$ = $B$, and we will use $A\subsetneq B$ when we wish to emphasize that $A\neq B$.

There Exists

This is probably as common as for all and is equally useful. Its mathematical symbol is $\exists$. It is almost always followed by a "such that" statement. For example, "There exists a computer that has 8GB of RAM." $\forall$ and $\exists$ are often used in pairs, such as, "Everyone has a mother.", or, worded logically, "For each human, there exists a mother for that human.". Let H be the set of all humans and M be the set of all mothers. Then we have

$\forall h\in H,\exists m\in M{\mbox{ such that }}m{\mbox{ is the mother of }}h.$

or, when $H$ and $M$ are understood,

$\forall h,\exists m{\mbox{ such that }}m{\mbox{ is the mother of }}h.$

This quantifier is also read as there is or there are. To signify that there is only one of something, we say "There exists a unique..." and place an exclamation point after the exists symbol: $\exists !$.

In the same way that "not and" gives "or", "not for all" gives "there exists." That is, the opposite of the statement "All cheesecakes are chocolate." is "There is a cheesecake that is not chocolate." In logical terms,

$\lnot (\forall x\in A,P(x)){\mbox{ is equivalent to }}\exists x\in A:\lnot P(x).$

The above statement is read "the negation of 'For all x in A, P(x) is true.' is 'There is an x in A such that P(x) is false."

Such That

As we have seen, such that can be used in at least two cases: in conjunction with there exists and in picking out elements of a set. Of course, if you think about it, these two are really the same application because the statement "there exists" gives you the set of all things that exist, and the such that statement decreases the size of that set to focus just on the things in which you are interested. Such that is normally denoted as a colon(:) or as a vertical bar (|), and sometimes as "s.t."

Without Loss of Generality

This is a very helpful phrase in making proofs more concise and less redundant. For example, assume we have two integers x and y and that we know one of them is odd and one of them is even. Instead of trying to do two different parallel proofs, one where we assume that x is even and y is odd and another where we assume that y is even and x is odd, we simply say "Without loss of generality, assume x is even." Then we continue with the proof. This is done since the exact same argument applies if y actually was the even number, all we have to do is relabel x and y.

The Universe

Now, we're not going to begin a discussion of astronomy. In mathematics, the universe is overall, the biggest set that your discussion is referring to. For example, if the universe is not restricted, then the set of all things would truly be the set containing every single thing. However, if your universe is the set of all things on Earth, then the "set of all things" would not include Jupiter, since Jupiter is not on Earth.

Difference

In arithmetic, difference means the distance between two numbers—how far apart they are on the number line. In set theory, difference means something slightly different, but the same notation is used. ($A-B$ denotes the difference of A and B.) The difference is the set of all things that are in A that are not in B.

$A-B=\{x\in A|x\notin B\}=\{x|x\in A\land x\notin B\}$

In normal English, we use this concept when we say things like "Everyone with no demerits gets an A in this course."

Complement

A Venn Diagram of A, B, and U.

The complement of a set contains everything that is not in the original set. This definition only makes sense when a universe is understood. The complement is usually denoted by $A^{c}$. If U is the universe, then the complement of A is defined to be $A^{c}=U-A$.

The diagram to the right is a Venn diagram. A Venn diagram shows the relationships of sets. Note that in the figure, U is the universe, and A and B are sets in U. The blue portion is the complement of $A\cup B$. This is a general drawing, since it is not known whether there are elements in A and B. If $A\cap B$ is known to be empty, then they may be drawn disjoint.

The complement of a set is essentially the same as the negation of a statement. That is,

if $A=\{x|P(x)\}$, then 
$A^{c}=\{x|\lnot P(x)\}$.  

Thus, complements are used when saying what something is not.

Exercises

1. Express the following statements in terms of sets, using difference or complement.
   1. All people that have two legs.
   2. All mythological creatures that are not Greek.
   3. All pudding pies that have no cream on top.
2. Draw a Venn Diagram to illustrate the following.
   1. $A\cap B\cap C$
   2. $A\cup B-C$
   3. $(A^{c}\cap B^{c})\cup C$
   4. $A\cap (B\cup C)$
   5. $A-(U-B)$
3. Negate the following statements.
   1. $\forall x\in A,\exists y\in B:P(x,y)$
   2. All quick, brown foxes jump over some lazy dog.

Methods of Proof

There are many different ways to prove things in mathematics. This chapter will introduce some of those methods.

Constructive 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?$

Proof by Contrapositive

The contrapositive of a statement negates the conclusion as well as the hypothesis. It is logically equivalent to the original statement asserted. Often it is easier to prove the contrapositive than the original statement. This section will demonstrate this fact.

The Concept

The idea of the contrapositive is proving the statement "There is no x such that P(x) is false." as opposed to "P(x) is true for every x."

This is not to be confused with a Proof by Contradiction. If we are trying to prove the statement $P\Rightarrow Q$, we can do it constructively, by assuming that P is true and showing that the logical conclusion is that Q is also true. The contrapositive of this statement is $\lnot Q\Rightarrow \lnot P$, so we assume that Q is false and show that the logical conclusion is that P is also false. However, in a proof by contradiction, we assume that P is true and Q is false and arrive at some sort of illogical statement such as "1=2."

A proof revisited

The most basic example would be to redo a proof given in the last section. We proved Theorem 2.1.4 to be true by the constructive method. Now we can prove the same result using the contrapositive method. For ease of reading, I will change the wording of the theorem.

Theorem 2.2.1 (also Theorem 2.1.4). If A and B are finite sets and $|A|\neq |B|$, then $A\neq B$.

The wording is probably more natural in the 2.1.4 version, but this shows how the proof is to be done. We assume that we have two finite sets A and B and that they do not have the same number of elements. So let $n=|A|$ and $m=|B|$. Then, number the elements in A and B, so $A=\{a_{1},a_{2},\ldots ,a_{n}\}$ and $B=\{b_{1},b_{2},\ldots ,b_{m}\}$. Since $n\neq m$, either $n<m$ or $m<n$. Without loss of generality, we assume that $n<m$. Consider the set $B-A$. Since A has only n elements, we can take out at most n elements from B, leaving at least m-n elements in B-A. This shows that there is at least one element in B that is not in A, therefore $B\neq A$.

Arithmetic

I'm sure we all know how to do arithmetic already, but mathematicians like to be "rigorous." That means that we like to have clear definitions of everything we use.

Axiom 7. The numbers 0 and 1 exist.

Definition 2.2.2. The operator + is defined so that 1+0=1 and $\{1,1+1,1+1+1,1+1+1+1,\ldots \}$ is an infinite set. We write the elements of this set as $1,2,3,4,\ldots$ and define $n+m=(1+1+\cdots (n{\mbox{ times}}))+(1+1+\cdots (m{\mbox{ times}}))=(1+1+\cdots (n+m{\mbox{ times}}))$.

Definition 2.2.3. The operator $\cdot$ is defined so that $1\cdot 0=0,$ $1\cdot 1=1$ and $n\cdot 1=1+1+\cdots (n{\mbox{ times}}).$ We also define $n\cdot m=m+m+m+\cdots (n{\mbox{ times}}).$

The above definitions are just formalities. We know what numbers are and how they work. This is just a mathematical definition. Notice that only integer multiplication has been defined. Now we need one more definition to prove the following theorem.

Definition 2.2.4. An integer is said to be even if it is a multiple of two. That is, 'n' is even if n = 2k for some integer k. If this is not true, then it is said to be odd. The property of whether a number is even or odd is its parity.

Theorem 2.2.5. If x and y are integers such that $x+y$ is odd, then $x\neq y.$

To prove this by contrapositive, we assume that $x=y$ and show that $x+y$ is even. If $x=y$, then $x+y=x+x$, which by Definition 2.2.3 is $2\cdot x$, so $x+y$ is a multiple of 2 and is therefore even.

Biconditionals

Proofs by contrapositive are very helpful in proving biconditional statements. Recall that a biconditional is of the form $P\Leftrightarrow Q$ (P if and only if Q). To prove a biconditional we need to prove that $P\Rightarrow Q$ and $Q\Rightarrow P.$ However, if we use the contrapositive, we can show $P\Rightarrow Q$ and $\lnot P\Rightarrow \lnot Q.$

More Arithmetic

Prime numbers are very interesting in number theory, but also in arithmetic. In fact, the Fundamental Theorem of Arithmetic has to do with primes. Here we will not give a proof, just a statement of the theorem.

Definition 2.2.6. A prime number is a positive integer that has no multiple other than 1 and itself. A number that is not prime is called composite.

Theorem 2.2.7 (Fundamental Theorem of Arithmetic). Every integer has a unique factorization of primes, excluding reorderings.

This theorem will be very useful in the proof of the next theorem.

Theorem 2.2.8. An integer n is even if and only if its square $n^{2}=n\cdot n$ is even.

Proof

• First we do a constructive proof. Suppose that n is an even integer. Then by defintion of even, $n=2\cdot k$ for some integer k. Then $n^{2}=(2k)^{2}=2k\cdot 2k=2(k\cdot 2\cdot k)$. Since $k\cdot 2\cdot k$ is an integer because it is the product of integers, we see that $n^{2}$ is even. This shows the "only-if" part of the theorem.
• To show the "if" part, we use a proof by contrapositive. Assume that n is not even, or that n is odd. Let $n=a_{1}^{k_{1}}\cdot a_{2}^{k_{2}}\cdots a_{m}^{k_{m}}$ be the prime factorization of n. Then none of the $a_{i}$ are 2 for any i. We consider the square $n^{2}=a_{1}^{2k_{1}}\cdots a_{m}^{2k_{m}}$ and notice that there are no multiples that are equal to 2, so we conclude that $n^{2}$ is odd. This proves the theorem.

Exercises

1. Prove the following by contrapositive:
   1. An integer n is even if and only if n+1 is odd.
   2. If n and m have the same parity then n+m is even.

Proof by Contradiction

The method of proof by contradiction is to assume that a statement is not true and then to show that that assumption leads to a contradiction. In the case of trying to prove $P\Rightarrow Q$ , this is equivalent to assuming that $P\land \lnot Q$ That is, to assume that $P$ is true and $Q$ is false. This is known by its latin reductio ad absurdum (reduction to absurdity), since it ends with a statement that cannot be true.

Square root of 2

A good example of this is by proving that ${\sqrt {2}}$ is irrational. Proving this directly (via constructive proof) would probably be very difficult (if not impossible). However, by contradiction we have a fairly simple proof.

Proposition 2.3.1. ${\sqrt {2}}\notin \mathbb {Q}$

Proof: Assume ${\sqrt {2}}$ is rational. Then ${\sqrt {2}}={\frac {a}{b}}$ , where $a$ and $b$ are relatively prime integers (a and b have no common factors). and $b\neq 0$ . So

$2={\frac {a^{2}}{b^{2}}}$

$2b^{2}=a^{2}$

But since $a^{2}$ is even, $a$ must be even as well, since the square of an odd number is also odd. Then we have $a=2a_{1}$, or $2b^{2}=4a_{1}^{2},$ so $b^{2}=2a_{1}^{2}$ .

The same argument can now be applied to $b$ to find $2b_{1}=b$ . However, this contradicts the original assumption that a and b are relatively prime, and the above is impossible. Therefore, we must conclude that ${\sqrt {2}}$ is irrational.

Of course, we now note that there was nothing in this proof that was special about 2, except the fact that it was prime. That's what allowed us to say that $a$ was even since we knew that $a^{2}$ was even. Note that this would not work for 4 (mainly because ${\sqrt {4}}=2\in \mathbb {Q}$) because $4|a^{2}$ does not imply that $4|a$ .

More Thoughts

In English, the procedure is this: Assert that a statement is false, and then prove yourself wrong. (Thereby proving the original statement was true.) This is a form of Modus Tollens.

For many students, the method of proof by contradiction is a tremendous gift and a trojan horse, both of which follow from how strong the method is. In fact, the apt reader might have already noticed that both the constructive method and contrapositive method can be derived from that of contradiction.

Assume	Prove	Contradiction
$P\land \lnot Q\ which\ implies\ P$	$Q\ (from\ P\ only)$	$Q\land \lnot Q$
$P\land \lnot Q\ which\ implies\ \lnot Q$	$\lnot P\ (from\ \lnot Q\ only)$	$P\land \lnot P$

However, its reach goes farther than even that, since the contradiction can be anything. Even if we ignore the criticisms from constuctivism, this broad scope hides what you lose; namely, you lose well-defined direction and conclusion, both of which have to be replaced with intuition.

Lastly, even in nonconstructive company, using the method in the first row of the table above is considered bad form (that is, proving something by pseudo-constructive proof), since the proof-by-contradiction part of it is nothing more than excess baggage.

---

Proof by Induction

The beauty of induction is that it allows a theorem to be proven true where an infinite number of cases exist without exploring each case individually. Induction is analogous to an infinite row of dominoes with each domino standing on its end. If you want to make all the dominoes fall, you can either:

1. push on the first one, wait to see what happens, and then check each domino afterwards (which may take a long time if there's an infinite number of dominoes!)
2. or you can prove that if any domino falls, then it will cause the domino after it to fall. (i.e. if the first one falls then the second one will fall, and if the second one falls then the third one will fall, etc.)

Induction, essentially, is the methodology outlined in point 2.

Parts of Induction

Induction is composed of three parts:

1. The Base Case (in the domino analogy, this shows the first domino will fall)
2. The Induction Hypothesis (in the domino analogy, we assume that a particular domino will fall)
3. The Inductive Step (in the domino analogy, we prove that the domino we assume will fall will cause the next domino to fall)

Weak Induction

Weak induction is used to show that a given property holds for all members of a countable inductive set, this usually is used for the set of natural numbers.

Weak induction for proving a statement $P(n)$ (that depends on $n$) relies on two steps:

• $P(n)$ is true for a certain base step. Usually the base case is $n=1$ or $n=0$

• $P(k)\to P(k+1)$. That is, if $P(k)$ is true, then $P(k+1)$ is true.

If these two properties hold, one may induce that the property holds for all elements in the set in question. Returning to the example, if you are sure that you called your neighbor, and you knew that everyone who was called in turn called his/her neighbor, then you would be guaranteed that everyone on the block had been called (assuming you had a linear block, or that it curved around nicely).

Examples

The first example of a proof by induction is always 'the sum of the first n terms:'

Theorem 2.4.1. For any fixed $n\in \mathbb {N} ,$ $\sum _{i=1}^{n}{i}={\frac {n(n+1)}{2}}$

Proof

• Base step: $1={\frac {1\cdot 2}{2}}$ , therefore the base case holds.

• Inductive step: Assume that $\sum _{i=0}^{n}i={\frac {n(n+1)}{2}}$ . Consider $\sum _{i=1}^{n+1}i$ .

${\begin{aligned}\sum _{i=1}^{n+1}i&=\sum _{i=1}^{n}i+(n+1)={\frac {n(n+1)}{2}}+n+1\\&=\left({\frac {n}{2}}+1\right)(n+1)\\&={\frac {(n+1)(n+2)}{2}}\\&={\frac {(n+1){\big (}(n+1)+1{\big )}}{2}}\end{aligned}}$

So the inductive case holds. Now by induction we see that the theorem is true.

Reverse Induction

Reverse induction is a method of using an inductive step that uses a negative in the inductive step. It is a minor variant of weak induction. The process still applies only to countable sets, generally the set of whole numbers or integers, and will frequently stop at 1 or 0, rather than working for all positive numbers.

Reverse induction works in the following case.

• The property holds for a given value, say $M$ .

• Given that the property holds for a given case, say $n=k+1$ , Show that the property holds for $n=k$ .

Then the property holds for all values $n\leq M$.

Reverse induction is also usable in the general case : "to establish the validity of a sequence of propositions $P(n)\ (n\geq 1)$ , it is enough to establish the following

(a) $P(n)$ is valid for infinitely many $n$ .

(b) If $P(n+1)$ is valid, then so is $P(n)$ .

It can be the case that we can easily prove $P(1)$ and if $P$ for $n=m$ so $P$ for $n=2m$ . In this case we have (a) for the infinitely many $n=2^{k}\ (k\geq 0)$ .

Strong Induction

In weak induction, for the inductive step, we only required that for a given $n$ , its immediate predecessor $n-1$ satisfies the theorem (i.e., $P(n-1)$ is true). In strong induction, we require that not only the immediate predecessor, but all predecessors of $n$ satisfy the theorem. The variation in the inductive step is:

• If $P(k)$ is true for all $k<n$ , then $P(n)$ is true.

The reason this is called strong induction is fairly obvious — the hypothesis in the inductive step is much stronger than the hypothesis is in the case of weak induction. Of course, for finite induction it turns out to be the same hypothesis, but in the case of transfinite sets, weak induction is not even well-defined, since some sets have elements that do not have an immediate predecessor.

Transfinite Induction

Used in proving theorems involving transfinite cardinals. This technique is used in set theory to prove properties of cardinals, since there is rarely another way to go about it.

Inductive Set

We first define the notion of a well-ordered set. A set $X$ is well-ordered if there is a total order $<$ on $X$ and that whenever $Y\subset X$ is non-empty, there is a least-element in $Y$ . That is, $\exists p\in Y$ such that $p<q\ \forall q\in Y$ .

An inductive set is a set $A\subset X$ such that the following hold:

1. $\alpha \in A$ (where $\alpha$ is the least element of $X$)
2. If $\beta \in A$ then $\forall \gamma \in X$ such that $\beta <\gamma ,\gamma \in A$

Of course, you look at that and say "Wait a minute. That means that $A=X$!" And, of course you'd be right. That's exactly why induction works. The principle of induction is the theorem that says:

Theorem 2.4.2. If $X$ is a non-empty well-ordered set and $A\subset X$ is an inductive subset of $X$ then $A=X$ .

The proof of this theorem is left as a very simple exercise. Here we note that the set of natural numbers is clearly well-ordered with the normal order that you are familiar with, so $\mathbb {N}$ is an inductive set. If you accept the axiom of choice, then it follows that every set can be well-ordered.

Exercises

Prove for every positive integer: $1+\cdots +n={\frac {n(n+1)}{2}}$

First, we show that it holds for $n=1$ .

$1={\frac {1(1+1)}{2}}$

Suppose the identiy holds for some number $n=k$ , then

$1+\cdots +k={\frac {k(k+1)}{2}}$

We aim to show that

$1+\cdots +(k+1)={\frac {(k+1)(k+2)}{2}}$

it follows that

${\begin{aligned}(1+\cdots +k)+(k+1)&={\frac {k(k+1)}{2}}+(k+1)\\&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\end{aligned}}$

which is what we have set out to show. Since the identity holds for 1, it also holds for 2 and since it holds for 3 and so on.

Prove for every positive integer: $1^{2}+\cdots +n^{2}={\frac {n(n+1)(2n+1)}{6}}$

First, we show that this statement holds for $n=1$ .

$1^{2}={\frac {1(1+1)(2+1)}{6}}$

Assume that the equation holds for $n=k$ . Then,

$1^{2}+\cdots +k^{2}={\frac {k(k+1)(2k+1)}{6}}$

We aim to show that

$1^{2}+\cdots +(k+1)^{2}={\frac {(k+1)(k+2)(2k+3)}{6}}$

it follows that

${\begin{aligned}(1^{2}+\cdots +k^{2})+(k+1)^{2}&={\frac {k(k+1)(2k+1)}{6}}+(k+1)^{2}\\&={\frac {k(k+1)(2k+1)+6(k+1)^{2}}{6}}\\&={\frac {(k+1){\big [}k(2k+1)+6(k+1){\big ]}}{6}}\\&={\frac {(k+1)(2k^{2}+k+6k+6)}{6}}\\&={\frac {(k+1)(2k^{2}+7k+6)}{6}}\\&={\frac {(k+1)(k+2)(2k+3)}{6}}\end{aligned}}$

which is what we set out to prove. By mathematical induction, the formula holds for all positive integers.

Prove for every positive integer: $1^{3}+\cdots +n^{3}=\left({\frac {n(n+1)}{2}}\right)^{2}$

First, we show that this statement holds for $n=1$ .

${\begin{aligned}1^{3}=1\\\left({\frac {1(1+1)}{2}}\right)^{2}=1\end{aligned}}$

Suppose it's true for $n=k$ . Then,

$1^{3}+\cdots +k^{3}=\left({\frac {k(k+1)}{2}}\right)^{2}$

it follows that

${\begin{aligned}(1^{3}+\cdots +k^{3})+(k+1)^{3}&=\left({\frac {k(k+1)}{2}}\right)^{2}+(k+1)^{3}\\&=(k+1)^{2}\left(\left({\frac {k}{2}}\right)^{2}+(k+1)\right)\\&={\frac {(k+1)^{2}(k^{2}+4k+4)}{4}}\\&=\left({\frac {(k+1)(k+2)}{2}}\right)^{2}\end{aligned}}$

We have shown that if it's true for $n=k$ then it's also true for $n=k+1$ . Now it's true for 1 (clear). Therefore it's true for all integers.

Show that $n!>2^{n}$ for $n\geq 4$

The claim is true for $n=4$ .

$4!>2^{4}\ \Rightarrow \ 24>16$

Now suppose it's true for $n=k\geq 4$ . Then,

$k!>2^{k}$

it follows that

${\begin{aligned}(k+1)k!&>(k+1)2^{k}>2^{k+1}\\(k+1)!&>2^{k+1}\end{aligned}}$

We have shown that if for $n=k$ then it's also true for $n=k+1$ . Since it's true for 4 , it's true for all integers $n\geq 4$ .

Prove for every positive integer: $2+4+6+\cdots +2n=n(n+1)$

First, we show that this statement holds for $n=1$ .

$2=1(1+1)$

Assume that the equation holds for $n=k$ . Then,

$2+4+6+\cdots +2k=k(k+1)$

We aim to show that

$2+4+6+\cdots +2(k+1)=(k+1)(k+2)$

it follows that

${\begin{aligned}(2+4+6+\cdots +2k)+2(k+1)&=k(k+1)+2(k+1)\\&=(k+1)(k+2)\end{aligned}}$

which is what we set out to prove. By mathematical induction, the formula holds for all positive integers.

Prove for every positive integer: $1+4+7+\cdots +(3n-2)={\frac {n(3n-1)}{2}}$

First, we show that this statement holds for $n=1$ .

$1={\frac {1(3-1)}{2}}$

Assume that the equation holds for $n=k$ . Then,

$1+4+7+\cdots +(3k-2)={\frac {k(3k-1)}{2}}$

We aim to show that

$1+4+7+\cdots +{\bigl (}3(k+1)-2{\bigr )}={\frac {(k+1)(3k+2)}{2}}$

it follows that

${\begin{aligned}{\big (}1+4+7+\cdots +(3k-2){\big )}+{\big (}3(k+1)-2{\big )}&={\frac {k(3k-1)}{2}}+(3k+1)\\&={\frac {(3k^{2}-k+6k+2)}{2}}\\&={\frac {(3k^{2}+5k+2)}{2}}\\&={\frac {(k+1)(3k+2)}{2}}\end{aligned}}$

which is what we set out to prove. By mathematical induction, the formula holds for all positive integers.

Prove for every positive integer: $2+7+12+\cdots +(5n-3)={\frac {n(5n-1)}{2}}$

First, we show that this statement holds for $n=1$ .

$2={\frac {1(5-1)}{2}}$

Assume that the equation holds for $n=k$ . Then,

$2+7+12+\cdots +(5k-3)={\frac {k(5k-1)}{2}}$

We aim to show that

$2+7+12+\cdots +{\bigl (}5(k+1)-3{\bigr )}={\frac {(k+1){\bigl (}5(k+1)-1{\bigr )}}{2}}$

it follows that

${\begin{aligned}{\big (}2+7+12+\cdots +(5k-3){\big )}+{\big (}5(k+1)-3{\big )}&={\frac {k(5k-1)}{2}}+{\big (}5(k+1)-3{\big )}\\&={\frac {k(5k-1)+2{\big (}5(k+1)-3{\big )}}{2}}\\&={\frac {5k^{2}-k+10k+4}{2}}\\&={\frac {5k^{2}+9k+4}{2}}={\frac {(k+1)(5k+4)}{2}}\\&={\frac {(k+1){\bigl (}5(k+1)-3{\bigr )}}{2}}\end{aligned}}$

which is what we set out to prove. By mathematical induction, the formula holds for all positive integers.

Prove for every positive integer: $1+2\cdot 2+2^{2}\cdot 3+\cdots +2^{n-1}n=2^{n}(n-1)+1$

First, we show that this statement holds for $n=1$ .

$1=2^{1}(1-1)+1$

Assume that the equation holds for $n=k$ . Then,

$1+2\cdot 2+2^{2}\cdot 3+\cdots +2^{k-1}k=2^{k}(k-1)+1$

We aim to show that

$1+2\cdot 2+2^{2}\cdot 3+\cdots +2^{k}(k+1)=2^{k+1}k+1$

it follows that

${\begin{aligned}(1+2\cdot 2+2^{2}\cdot 3+\cdots +2^{k-1}k)+2^{k}(k+1)&=2^{k}(k-1)+1+2^{k}(k+1)\\&=2^{k}(k+1+k-1)+1\\&=2^{k}(2k)+1\\&=2^{k+1}k+1\end{aligned}}$

which is what we set out to prove. By mathematical induction, the formula holds for all positive integers.

Prove for every positive integer: ${\frac {1}{1\cdot 2}}+\cdots +{\frac {1}{n(n+1)}}={\frac {n}{n+1}}$

First, we show that this statement holds for $n=1$ .

${\frac {1}{1\cdot 2}}={\frac {1}{1+1}}$

Assume that the equation holds for $n=k$ . Then,

${\frac {1}{1\cdot 2}}+\cdots +{\frac {1}{k(k+1)}}={\frac {k}{k+1}}$

We aim to show that

${\frac {1}{1\cdot 2}}+\cdots +{\frac {1}{(k+1)(k+2)}}={\frac {k+1}{k+2}}$

it follows that

${\begin{aligned}{\frac {1}{1\cdot 2}}+\cdots +{\frac {1}{k(k+1)}}+{\frac {1}{(k+1)(k+2)}}&={\frac {k}{k+1}}+{\frac {1}{(k+1)(k+2)}}\\&={\frac {1}{k+1}}\left(k+{\frac {1}{k+2}}\right)\\&={\frac {1}{k+1}}\left({\frac {k(k+2)+1}{k+2}}\right)\\&={\frac {1}{k+1}}\left({\frac {k^{2}+2k+1}{k+2}}\right)\\&={\frac {(k+1)^{2}}{(k+1)(k+2)}}\\&={\frac {k+1}{k+2}}\end{aligned}}$

which is what we set out to prove. By mathematical induction, the formula holds for all positive integers.

This problem can be solved without mathematical induction. We note that

${\frac {1}{n(n+1)}}={\frac {1}{n}}-{\frac {1}{n+1}}$

Then, the question can be paraphrased as

${\frac {1}{1}}-{\frac {1}{2}}+{\frac {1}{2}}-{\frac {1}{3}}+\cdots +{\frac {1}{n-1}}-{\frac {1}{n}}+{\frac {1}{n}}-{\frac {1}{n+1}}={\frac {n}{n+1}}$

which simplfies to

$1-{\frac {1}{n+1}}={\frac {n}{n+1}}$

Prove for every positive integer: $a+\cdots +a^{n}={\frac {a(a^{n}-1)}{a-1}}:a\neq 0$

First, we show that this statement holds for $n=1$ .

$a={\frac {a(a^{1}-1)}{a-1}}$

Assume that the equation holds for $n=k$ . Then,

$a+\cdots +a^{k}={\frac {a(a^{k}-1)}{a-1}}$

We aim to show that

$a+\cdots +a^{k+1}={\frac {a(a^{k+1}-1)}{a-1}}$

it follows that

${\begin{aligned}(a+\cdots +a^{k})+a^{k+1}&={\frac {a(a^{k}-1)}{a-1}}+a^{k+1}\\&={\frac {a(a^{k}-1)+a^{k+1}(a-1)}{a-1}}\\&={\frac {a{\big [}a^{k}-1+a^{k}(a-1){\big ]}}{a-1}}\\&={\frac {a{\big [}a^{k}-1+a\cdot a^{k}-a^{k}{\big ]}}{a-1}}\\&={\frac {a(a^{k+1}-1)}{a-1}}\end{aligned}}$

which is what we set out to prove. By mathematical induction, the formula holds for all positive integers.

This can also be proven using the sum formula for a geometric series.

Prove for every positive integer: $(1+\cdots +n^{5})+(1+\cdots +n^{7})=2\left({\frac {n(n+1)}{2}}\right)^{4}$

First, we show that this statement holds for $n=1$ .

$1+1=2\left({\frac {1(1+1)}{2}}\right)^{4}=2$

Assume that the equation holds for $n=k$ . Then,

$(1+\cdots +k^{5})+(1+\cdots +k^{7})=2\left({\frac {k(k+1)}{2}}\right)^{4}$

We aim to show that

${\bigl (}1+\cdots +(k+1)^{5}{\bigr )}+{\bigl (}1+\cdots +(k+1)^{7}{\bigr )}=2\left({\frac {(k+1)(k+2)}{2}}\right)^{4}$

it follows that

${\begin{aligned}(1+\cdots +k^{5})+(k+1)^{5}+(1+\cdots +k^{7})+(k+1)^{7}&=2\left({\frac {k(k+1)}{2}}\right)^{4}+(k+1)^{5}+(k+1)^{7}\\&={\frac {(k+1)^{4}{\big [}k^{4}+8(k+1)+8(k+1)^{3}{\big ]}}{8}}\\&={\frac {(k+1)^{4}{\big [}k^{4}+8(k+1){\big (}1+(k+1)^{2}{\big )}{\big ]}}{8}}\\&={\frac {(k+1)^{4}{\big [}k^{4}+8(k+1)(k^{2}+2k+2){\big ]}}{8}}\\&={\frac {(k+1)^{4}(k^{4}+8k^{3}+24k^{2}+32k+16)}{8}}\\&={\frac {(k+1)^{4}(k+2)^{4}}{8}}\\&=2\left({\frac {(k+1)(k+2)}{2}}\right)^{4}\end{aligned}}$

which is what we set out to prove. By mathematical induction, the formula holds for all positive integers.

Prove for every positive integer: $(1+x)^{n}\geq 1+nx:x\geq -1$ (the so called Bernoulli's inequality)

First, we show that this statement holds for $n=1$ .

$(1+x)^{1}\geq 1+x$ because $(1+x)^{1}=1+1\cdot x$

Assume that the equation holds for $n=k$ . Then,

$(1+x)^{k}\geq 1+kx$

We aim to show that

$(1+x)^{k+1}\geq 1+(k+1)x$

Multyplying $(1+x)$ by both sides, (desn't alter the sign of the inequality because $x\geq -1$ , and so $x+1\geq 0$)

${\begin{aligned}(1+x)^{k+1}&\geq (1+kx)(1+x)\\&=1+kx+x+kx^{2}\\&=1+(k+1)x+kx^{2}\\&\geq 1+(k+1)x\end{aligned}}$

The last step relies on the fact that $kx^{2}\geq 0$ , since $k\geq 0,x^{2}\geq 0$ .

By mathematical induction, the formula holds for all positive integers.

Prove for every positive integer: $1^{3}+\cdots +(n-1)^{3}<{\frac {n^{4}}{4}}<1^{3}+\cdots +n^{3}$

First, we show that this statement holds for $n=1,2$ .

${\begin{aligned}(1-1)^{3}&<{\frac {1^{4}}{4}}<1^{3}\iff 0<{\frac {1}{4}}<1\\(1-1)^{3}+1^{3}&<{\frac {2^{4}}{4}}<1^{3}+2^{3}\iff 1<4<9\end{aligned}}$

Assume that the inequality holds for $n=k$ . Then,

$1^{3}+\cdots +(k-1)^{3}<{\frac {k^{4}}{4}}<1^{3}+\cdots +k^{3}$

We aim to show that

$1^{3}+\cdots +k^{3}<{\frac {(k+1)^{4}}{4}}<1^{3}+\cdots +(k+1)^{3}$

We know that

${\bigl (}1^{3}+\cdots +(k-1)^{3}{\bigr )}+k^{3}<{\frac {k^{4}}{4}}+k^{3}$

Now we need to show that

${\frac {k^{4}}{4}}+k^{3}<{\frac {(k+1)^{4}}{4}}$

it follows that

${\begin{aligned}{\frac {k^{4}}{4}}+k^{3}<{\frac {(k+1)^{4}}{4}}&\iff {\frac {k^{3}(k+1)}{4}}<{\frac {k^{4}+4k^{3}+6k^{2}+4k+1}{4}}\\&\iff 0<{\frac {6k^{2}+4k+1}{4}}\end{aligned}}$

The last statement is clearly true ($k>0$). Therefore,

$1^{3}+\cdots +k^{3}<{\frac {k^{4}}{4}}+k^{3}<{\frac {(k+1)^{4}}{4}}$

Now we show that

${\frac {(k+1)^{4}}{4}}<1^{3}+\cdots +(k+1)^{3}$

We know that

${\frac {k^{4}}{4}}+(k+1)^{3}<(1^{3}+\cdots +k^{3})+(k+1)^{3}$

Now we need to show that

${\frac {(k+1)^{4}}{4}}<{\frac {k^{4}}{4}}+(k+1)^{3}$

it follows that

${\begin{aligned}{\frac {(k+1)^{4}}{4}}<{\frac {k^{4}}{4}}+(k+1)^{3}&\iff {\frac {k^{4}+4k^{3}+6k^{2}+4k+1}{4}}<{\frac {k^{4}+4(k^{3}+3k^{2}+3k+1)}{4}}\\&\iff {\frac {k^{4}+4k^{3}+6k^{2}+4k+1}{4}}<{\frac {k^{4}+4k^{3}+12k^{2}+12k+4}{4}}\\&\iff 0<{\frac {6k^{2}+8k+3}{4}}\end{aligned}}$

The last statement is clearly true ($k>0$). Therefore,

${\frac {(k+1)^{4}}{4}}<1^{3}+\cdots +(k+1)^{3}$

Combining both inequalities we proved, we get the one we needed for the inductive step.

$1^{3}+\cdots +k^{3}<{\frac {(k+1)^{4}}{4}}<1^{3}+\cdots +(k+1)^{3}$

and by mathematical induction, the formula holds for all positive integers.

Prove for every positive integer: $1+\cdots +{\frac {1}{\sqrt {n}}}\leq 2{\sqrt {n}}-1$ (Hard)

First, we show that this statement holds for $n=1$ .

$1\leq 2{\sqrt {1}}-1$ because $1\leq 1$

Assume that the inequality holds for $n=k$ . Then,

$1+\cdots +{\frac {1}{\sqrt {k}}}\leq 2{\sqrt {k}}-1$

We aim to show that

$1+\cdots +{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k+1}}-1$

We know that

$\left(1+\cdots +{\frac {1}{\sqrt {k}}}\right)+{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1$

Now we need to show that

$2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1\leq 2{\sqrt {k+1}}-1$

it follows that

${\begin{aligned}2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1\leq 2{\sqrt {k+1}}-1&\iff 2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k+1}}\\&\iff 2{\sqrt {k(k+1)}}+1\leq 2(k+1)\\&\iff 2{\sqrt {k(k+1)}}\leq 2k+1\\&\iff 2^{2}{\sqrt {k(k+1)}}^{2}\leq {(2k+1)}^{2}\\&\iff 4k^{2}+4k\leq 4k^{2}+4k+1\\&\iff 0\leq 1\end{aligned}}$

The last statement is clearly true. Therefore,

$1+\cdots +{\frac {1}{\sqrt {k}}}+{\frac {1}{\sqrt {k+1}}}\leq 2{\sqrt {k}}+{\frac {1}{\sqrt {k+1}}}-1\leq 2{\sqrt {k+1}}-1$

and by mathematical induction, the formula holds for all positive integers.

Prove for every positive integer: 3 is a factor of $n^{3}-n+3$

First, we show that this statement is true for $n=1$. For $n=1$

$1^{3}-1+3=3$, and 3 is a factor of 3.

Since we have shown the base case to be true, we assume that the statement is true for $n=k$ where $k\in \mathbb {Z^{+}}$.

$k^{3}-k+3=3w$ where $w\in \mathbb {Z^{+}}$ (in other words, the expression is divisible by 3 for any positive integer).

Given that the base case was true for $n=1$ and the statement is assumed to be true for $n=k$, it must also be true for $n=k+1$ which we attempt to prove now:

${\begin{aligned}3z&=(k+1)^{3}-(k+1)+3\\&=k^{3}+3k^{2}+3k+1-k-1+3\\&=[k^{3}-k+3]+3k^{2}+3k\\&=3w+3k^{2}+3k\\&=3(w+k^{2}+k)\\z&=w+k^{2}+k\end{aligned}}$

Therefore, the statement is true for $n=k+1$ based on the assumption that $n=k$ is true, and so by mathematical induction, the statement is true for all positive integers.

Prove for every positive integer: 9 is a factor of $10^{n+1}+3\cdot 10^{n}+5$

No Solutions Available

Prove for every positive integer: 4 is a factor of $5^{n}-1$

First we show that this statement holds for $n=1,2$. For n=1,

$5^{1}-1=4$, and 4 is a factor of 4.

For n=2,

$5^{2}-1=24$, and 4 is a factor of 24.

Therefore, the base case holds. Now we assume that the equation above, $f(n)$ holds for n=k, and attempt to prove that the equation holds for n=k+1.

${\begin{aligned}f(k+1)&=5^{k+1}-1\\&=5(5^{k})-1\\&=5(5^{k}-1)-1+5\\&=5(5^{k}-1)+4\\&=5(f(k))+4\end{aligned}}$

By our inductive hypothesis above, 4 is a factor of f(k), and 4 is a factor of 4, so we know that 4 must also be a factor of $5(f(k))+4$. By mathematical induction, this equation holds for all positive integers.

Prove for every positive integer: $x-y$ is a factor of $x^{n}-y^{n}$

No Solutions Available

Prove for every positive integer: 2304 is a factor of $7^{2n}-48n-1$

No Solutions Available

Find $n_{0}\in \mathbb {N}$ such that the inequality $n^{2}<2^{n}$ holds for all $n\geq n_{0}$ , and give a proof by induction.

First, we show that this statement holds for $n=n_{0}=5$ .

$5^{2}=25<32=2^{5}$

Assume that the inequality holds for $n=k$ where $k\geq 5$ . Then,

${\begin{aligned}(k+1)^{2}&=k^{2}+2k+1\\&<k^{2}+2k+k\quad ({\text{since}}\ k>1)\\&=k^{2}+3k\\&=k(k+3)\\&<k(k+k)\quad ({\text{since}}\ k>3)\\&=k(2k)\\&=2k^{2}\\&<2\cdot 2^{k}\quad ({\text{by induction hypothesis}})\\&=2^{k+1}\end{aligned}}$ .

We have shown that if for $n=k$ then it's also true for $n=k+1$ . Since it's true for $n_{0}=5$ , it's true for all integers $n\geq n_{0}$ .

Counterexamples

A proof by counterexample is not technically a proof. It is merely a way of showing that a given statement cannot possibly be correct by showing an instance that contradicts a universal statement. For example, if you are trying to prove the statement "All cheesecakes are baked in Alaska." and you did not know whether to prove it by contrapositive or contradiction, all I would have to do is bake a cheesecake right in front of you here in Texas and then you would know that your efforts had been in vain.

Consider the following statement:

Every set is countable.

Of course a counterexample to this would be the interval from $[0,1]\subset \mathbb {R}$. To show that this interval isn't countable, we assume that it is, so then there is a bijective function $f:\mathbb {N} \rightarrow \mathbb {R}$ since $f$ is bijective we may write the elements of $[0,1]$ in a list here we write the numbers in $[0,1]$ in their decimal expansions.

$f(1)=.b_{(1,1)}b_{(1,2)}b_{(1,3)}b_{(1,4)}\ldots$

$f(2)=.b_{(2,1)}b_{(2,2)}b_{(2,3)}b_{(2,4)}\ldots$

$f(3)=.b_{(3,1)}b_{(3,2)}b_{(3,3)}b_{(3,4)}\ldots$

$\vdots$

For the purposes of the proof, we need each real number to be uniquely defined by a decimal. This is of course true in almost all cases (take .01, for instance... it's equal to .00999999999...). In fact, the cases when it's not true are exactly the cases when the decimal ends in a string of zeros, or "terminates" (a separate proof would be needed for this, but for now accept it as true). Therefore, let the decimals all be in "nonterminating form," so that there's another bijection between the decimal expansions and the real numbers.

Now let $a_{i}=0$ if $b_{(i,i)}$ is odd and 1 if $b_{(i,i)}$ is even. Now I claim that $x=.a_{1}a_{2}a_{3}a_{4}\ldots$ is not listed here. To show this suppose it were then for some $n\in \mathbb {Z} ,f(n)=.b_{(n,1)}b_{(b,2)}\ldots b_{(n,n)}\ldots$ but $a_{n}=0$ if $b_{(n,n)}$ is odd and $a_{n}=1$ if $b_{(n,n)}$, this is not possible so we conclude that $.a_{1}a_{2}a_{3}a_{4}\ldots$ is not in the list, this shows we may not have a surjection from $\mathbb {N} \rightarrow \mathbb {R}$

Although this is a counterexample, we still had to PROVE that it was in fact a counterexample and in doing so used both a proof by contradiction (this was the overall method of the proof) by a construction (of $x=.a_{1}a_{2}a_{3}a_{4}$). Although there may be more then one counterexample to any given false claim, you must always provide by a proof or argument that your counterexample works.

Computer Proofs

== The Curry-Howard Correspondance ==

The Curry-Howard correspondence establish a close relationship between computer programs and mathematical proofs.

Appendix

Answer Key

Logical Reasoning

1.1, Logical Reasoning.

These are the answers to the exercises in section 1.1, Logical Reasoning

1. Truth tables

1. $\lnot P\Rightarrow Q$

P	Q	$\lnot P$	$\lnot P\Rightarrow Q$
T	T	F	T
T	F	F	T
F	T	T	T
F	F	T	F

2. $P\Rightarrow \lnot Q$

P	Q	$\lnot Q$	$P\Rightarrow \lnot Q$
T	T	F	F
T	F	T	T
F	T	F	T
F	F	T	T

3. $(P\lor Q)\Rightarrow R$

P	Q	R	$P\lor Q$	$(P\lor Q)\Rightarrow R$
T	T	T	T	T
T	T	F	T	F
T	F	T	T	T
T	F	F	T	F
F	T	T	T	T
F	T	F	T	F
F	F	T	F	T
F	F	F	F	T

4. $(P\land Q)\Rightarrow (R\lor S)$

P	Q	R	S	$P\land Q$	$R\lor S$	$(P\land Q)\Rightarrow (R\lor S)$
T	T	T	T	T	T	T
T	T	T	F	T	T	T
T	T	F	T	T	T	T
T	T	F	F	T	F	F
T	F	T	T	F	T	T
T	F	T	F	F	T	T
T	F	F	T	F	T	T
T	F	F	F	F	F	T
F	T	T	T	F	T	T
F	T	T	F	F	T	T
F	T	F	T	F	T	T
F	T	F	F	F	F	T
F	F	T	T	F	T	T
F	F	T	F	F	T	T
F	F	F	T	F	T	T
F	F	F	F	F	F	T

5. $(P\Rightarrow Q)\Leftarrow (R\Rightarrow S)$

P	Q	R	S	$P\Rightarrow Q$	$R\Rightarrow S$	$(P\Rightarrow Q)\Leftarrow (R\Rightarrow S)$
T	T	T	T	T	T	T
T	T	T	F	T	F	T
T	T	F	T	T	T	T
T	T	F	F	T	T	T
T	F	T	T	F	T	F
T	F	T	F	F	F	T
T	F	F	T	F	T	F
T	F	F	F	F	T	F
F	T	T	T	T	T	T
F	T	T	F	T	F	T
F	T	F	T	T	T	T
F	T	F	F	T	T	T
F	F	T	T	T	T	T
F	F	T	F	T	F	T
F	F	F	T	T	T	T
F	F	F	F	T	T	T

2. Negated statements

1. $\lnot P\lor \lnot Q$
2. $(\lnot P\land \lnot Q)\lor (\lnot R\lor \lnot S)$
3. $(\lnot P\lor Q)\land (R\land \lnot S)$

Notation

These are the answers to the exercises in section 1.2, Notation

1. Use set theory notation
   1. $P\cap L$, where P is the set of all people and L is the set of all things with two legs.
   2. $M-G$, where M is the set of all mythological creatures and G is the set of all things that are Greek.
   3. $A\cap B-C$, where A is the set of all pies, B is the set of all things with pudding in them, and C is the set of all things with cream on the top.
2. Venn Diagrams
3. Negated statements
   1. $\exists x\in A:\forall y\in B,\lnot P(x,y).$
   2. There is a quick, brown fox that does not jump over any lazy dog.

Symbols Used in this Book

This is a list of all the mathematical symbols used in this book.

---

$[a,b]$

Closed interval notation. Signifies the set of all numbers between a and b (a and b included)

---

$\lor$

A logical "or" connector. A truth statement whose truth value is true if either of the two given statements is true and false if they are both false. $P\lor Q$

---

$\land$

A logical "and" connector. A truth statement whose truth value is true only if both of the two given statements is true and false otherwise. $P\land Q$

---

$\lnot$

A logical "not" unary operator. A truth statement whose value is opposite of the given statement. $\lnot P$

---

{ }

Set delimiters. A set may be defined explicitly (e.g. $A=\{1,2,3,4\}$), or pseudo-explicitly by giving a pattern (e.g. $B=\{2,4,6,8,\ldots \}$. It may also be defined with a given rule (e.g. $C=\{x|P(x)\}$, the set of all x such that P(x) is true).

---

$\in$

The "element of" binary operator. This shows element inclusion in a set. If x is an element of A we write $x\in A.$

---

$\subset$

The "set inclusion" or "subset" binary operator. If all the elements of A are in B, then we say that A is a subset of B and write $A\subset B.$ Note that in this book, $A\subset B$ when $A=B.$

---

$\cup$

The union of two sets. A set containing all elements of two given sets. $A\cup B=\{x|(x\in A)\lor (x\in B)\}.$

---

$\cap$

The intersection of two sets. A set containing all the elements that are in both of two given sets. $A\cap B=\{x|(x\in A)\land (x\in B)\}.$

Glossary

---

This glossary is mostly just for a quick reminder of terms learned in the book and is not meant to be comprehensive or rigorous. Please visit Wikipedia or Wiktionary for more detail.

A

Back to top

Arithmetic

The science of addition and multiplication (subtraction and division are included, since they are the inverse operations of addition and multiplication). Proof by Contrapositive

Axiom

A self-evident truth. It is the foundation of logical reasoning. A statement that is accepted as true without proof, which may be assumed in proving that other things are true.Notation

B

Back to top

Basis

A collection ${\mathcal {B}}$ of open sets in a set $X$ such that the intersection of any two open sets in $X$ contains a set $B\in {\mathcal {B}}.$ Proof by Contradiction

C

Back to top

Closed set

The complement of an open set in a topological space. Proof by Contradiction

Conclusion

The result of a given conditional statement. (The "then" clause of a theorem.) This is also sometimes referred to as the result. Constructive Proof

Conditional statement

An "if" or an "only-if" statement. It is conditional because its truth value is determined by the truth value of two other statements. Logical Reasoning

Contrapositive

The converse and negation of a conditional. The contrapositive of $P\Rightarrow Q$ is $\lnot Q\Rightarrow \lnot P$. Logical Reasoning

Converse

The "reverse" of a conditional statement. The converse of $P\Rightarrow Q$ is $P\Leftarrow Q$. Logical Reasoning

Corollary

That which follows, usually without any necessary argument, from a given result. Constructive Proof

D

Back to top

Divisor

See factor.

Divide

An integer n divides an integer m, if n is a factor of m, equivalently, if m is a multiple of n, or, equivalently, if there's a integer k such that $n*k=m$. Proof by Contrapositive

E

Back to top

Element

One of the objects in a set. Notation

Equivalent

See Logically Equivalent.

F

Back to top

Factor

An integer that divides a given integer. (e.g. 3 is a factor of 6.) This is the "opposite" of multiple. Proof by Contrapositive

L

Back to top

Lemma

A result whose proof is fairly simple or one that is used to simplify or break down a larger argument. Constructive Proof

Logcially Equivalent

Two statements that are simultaneously true or simultaneously false are logically equivalent. Logical Reasoning

M

Back to top

Multiple

An integer obtained by multiplying two integers together. (e.g. 4 is a mulitple of 2). This is the "opposite" of factor. Proof by Contrapositive

N

Back to top

Negation

The opposite of a truth statement. The negation of true is false and vice-versa. Logical Reasoning

O

Back to top

Open set

A set that is an element of a topology $\tau$ defined on a set $X.$ Proof by Contradiction

R

Back to top

Result

A lemma, theorem, or corollary. A statement of "if-then" that has been proven to be true. Also, the conclusion of such a statement. Constructive Proof

S

Back to top

Set

A collection of items, or elements. Notation

Statement

See Truth Statement.

T

Back to top

Theorem

A main result. Usually the proof is somewhat involved and the result is interesting and useful. Constructive Proof

Topological Space

A set $X$ together with a topology $\tau$ that satisfy the topology axioms. Proof by Contradiction

Topology

A collection of subsets of a given set that satisfy the topology axioms. Proof by Contradiction

Truth Statement

A statement whose truth value can be determined. Therefore, it is either true or false. Logical Reasoning

Truth Value

The assessment of whether a statement is true or false. Logical Reasoning

License

GNU Free Documentation License

Version 1.3, 3 November 2008 Copyright (C) 2000, 2001, 2002, 2007, 2008 Free Software Foundation, Inc. <http://fsf.org/>

Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.

0. PREAMBLE

The purpose of this License is to make a manual, textbook, or other functional and useful document "free" in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a way to get credit for their work, while not being considered responsible for modifications made by others.

This License is a kind of "copyleft", which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software.

We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference.

1. APPLICABILITY AND DEFINITIONS

This License applies to any manual or other work, in any medium, that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License. Such a notice grants a world-wide, royalty-free license, unlimited in duration, to use that work under the conditions stated herein. The "Document", below, refers to any such manual or work. Any member of the public is a licensee, and is addressed as "you". You accept the license if you copy, modify or distribute the work in a way requiring permission under copyright law.

A "Modified Version" of the Document means any work containing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language.

A "Secondary Section" is a named appendix or a front-matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document's overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (Thus, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connection with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them.

The "Invariant Sections" are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, in the notice that says that the Document is released under this License. If a section does not fit the above definition of Secondary then it is not allowed to be designated as Invariant. The Document may contain zero Invariant Sections. If the Document does not identify any Invariant Sections then there are none.

The "Cover Texts" are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License. A Front-Cover Text may be at most 5 words, and a Back-Cover Text may be at most 25 words.

A "Transparent" copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, that is suitable for revising the document straightforwardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup, or absence of markup, has been arranged to thwart or discourage subsequent modification by readers is not Transparent. An image format is not Transparent if used for any substantial amount of text. A copy that is not "Transparent" is called "Opaque".

Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format, SGML or XML using a publicly available DTD, and standard-conforming simple HTML, PostScript or PDF designed for human modification. Examples of transparent image formats include PNG, XCF and JPG. Opaque formats include proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML, PostScript or PDF produced by some word processors for output purposes only.

The "Title Page" means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, "Title Page" means the text near the most prominent appearance of the work's title, preceding the beginning of the body of the text.

The "publisher" means any person or entity that distributes copies of the Document to the public.

A section "Entitled XYZ" means a named subunit of the Document whose title either is precisely XYZ or contains XYZ in parentheses following text that translates XYZ in another language. (Here XYZ stands for a specific section name mentioned below, such as "Acknowledgements", "Dedications", "Endorsements", or "History".) To "Preserve the Title" of such a section when you modify the Document means that it remains a section "Entitled XYZ" according to this definition.

The Document may include Warranty Disclaimers next to the notice which states that this License applies to the Document. These Warranty Disclaimers are considered to be included by reference in this License, but only as regards disclaiming warranties: any other implication that these Warranty Disclaimers may have is void and has no effect on the meaning of this License.

2. VERBATIM COPYING

You may copy and distribute the Document in any medium, either commercially or noncommercially, provided that this License, the copyright notices, and the license notice saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use technical measures to obstruct or control the reading or further copying of the copies you make or distribute. However, you may accept compensation in exchange for copies. If you distribute a large enough number of copies you must also follow the conditions in section 3.

You may also lend copies, under the same conditions stated above, and you may publicly display copies.

3. COPYING IN QUANTITY

If you publish printed copies (or copies in media that commonly have printed covers) of the Document, numbering more than 100, and the Document's license notice requires Cover Texts, you must enclose the copies in covers that carry, clearly and legibly, all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on the back cover. Both covers must also clearly and legibly identify you as the publisher of these copies. The front cover must present the full title with all words of the title equally prominent and visible. You may add other material on the covers in addition. Copying with changes limited to the covers, as long as they preserve the title of the Document and satisfy these conditions, can be treated as verbatim copying in other respects.

If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages.

If you publish or distribute Opaque copies of the Document numbering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a computer-network location from which the general network-using public has access to download using public-standard network protocols a complete Transparent copy of the Document, free of added material. If you use the latter option, you must take reasonably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public.

It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document.

4. MODIFICATIONS

You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above, provided that you release the Modified Version under precisely this License, with the Modified Version filling the role of the Document, thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it. In addition, you must do these things in the Modified Version:

1. Use in the Title Page (and on the covers, if any) a title distinct from that of the Document, and from those of previous versions (which should, if there were any, be listed in the History section of the Document). You may use the same title as a previous version if the original publisher of that version gives permission.
2. List on the Title Page, as authors, one or more persons or entities responsible for authorship of the modifications in the Modified Version, together with at least five of the principal authors of the Document (all of its principal authors, if it has fewer than five), unless they release you from this requirement.
3. State on the Title page the name of the publisher of the Modified Version, as the publisher.
4. Preserve all the copyright notices of the Document.
5. Add an appropriate copyright notice for your modifications adjacent to the other copyright notices.
6. Include, immediately after the copyright notices, a license notice giving the public permission to use the Modified Version under the terms of this License, in the form shown in the Addendum below.
7. Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Document's license notice.
8. Include an unaltered copy of this License.
9. Preserve the section Entitled "History", Preserve its Title, and add to it an item stating at least the title, year, new authors, and publisher of the Modified Version as given on the Title Page. If there is no section Entitled "History" in the Document, create one stating the title, year, authors, and publisher of the Document as given on its Title Page, then add an item describing the Modified Version as stated in the previous sentence.
10. Preserve the network location, if any, given in the Document for public access to a Transparent copy of the Document, and likewise the network locations given in the Document for previous versions it was based on. These may be placed in the "History" section. You may omit a network location for a work that was published at least four years before the Document itself, or if the original publisher of the version it refers to gives permission.
11. For any section Entitled "Acknowledgements" or "Dedications", Preserve the Title of the section, and preserve in the section all the substance and tone of each of the contributor acknowledgements and/or dedications given therein.
12. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the equivalent are not considered part of the section titles.
13. Delete any section Entitled "Endorsements". Such a section may not be included in the Modified version.
14. Do not retitle any existing section to be Entitled "Endorsements" or to conflict in title with any Invariant Section.
15. Preserve any Warranty Disclaimers.

If the Modified Version includes new front-matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version's license notice. These titles must be distinct from any other section titles.

You may add a section Entitled "Endorsements", provided it contains nothing but endorsements of your Modified Version by various parties—for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard.

You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one.

The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version.

5. COMBINING DOCUMENTS

You may combine the Document with other documents released under this License, under the terms defined in section 4 above for modified versions, provided that you include in the combination all of the Invariant Sections of all of the original documents, unmodified, and list them all as Invariant Sections of your combined work in its license notice, and that you preserve all their Warranty Disclaimers.

The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work.

In the combination, you must combine any sections Entitled "History" in the various original documents, forming one section Entitled "History"; likewise combine any sections Entitled "Acknowledgements", and any sections Entitled "Dedications". You must delete all sections Entitled "Endorsements".

6. COLLECTIONS OF DOCUMENTS

You may make a collection consisting of the Document and other documents released under this License, and replace the individual copies of this License in the various documents with a single copy that is included in the collection, provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects.

You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document.

7. AGGREGATION WITH INDEPENDENT WORKS

A compilation of the Document or its derivatives with other separate and independent documents or works, in or on a volume of a storage or distribution medium, is called an "aggregate" if the copyright resulting from the compilation is not used to limit the legal rights of the compilation's users beyond what the individual works permit. When the Document is included in an aggregate, this License does not apply to the other works in the aggregate which are not themselves derivative works of the Document.

If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one half of the entire aggregate, the Document's Cover Texts may be placed on covers that bracket the Document within the aggregate, or the electronic equivalent of covers if the Document is in electronic form. Otherwise they must appear on printed covers that bracket the whole aggregate.

8. TRANSLATION

Translation is considered a kind of modification, so you may distribute translations of the Document under the terms of section 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addition to the original versions of these Invariant Sections. You may include a translation of this License, and all the license notices in the Document, and any Warranty Disclaimers, provided that you also include the original English version of this License and the original versions of those notices and disclaimers. In case of a disagreement between the translation and the original version of this License or a notice or disclaimer, the original version will prevail.

If a section in the Document is Entitled "Acknowledgements", "Dedications", or "History", the requirement (section 4) to Preserve its Title (section 1) will typically require changing the actual title.

9. TERMINATION

You may not copy, modify, sublicense, or distribute the Document except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense, or distribute it is void, and will automatically terminate your rights under this License.

However, if you cease all violation of this License, then your license from a particular copyright holder is reinstated (a) provisionally, unless and until the copyright holder explicitly and finally terminates your license, and (b) permanently, if the copyright holder fails to notify you of the violation by some reasonable means prior to 60 days after the cessation.

Moreover, your license from a particular copyright holder is reinstated permanently if the copyright holder notifies you of the violation by some reasonable means, this is the first time you have received notice of violation of this License (for any work) from that copyright holder, and you cure the violation prior to 30 days after your receipt of the notice.

Termination of your rights under this section does not terminate the licenses of parties who have received copies or rights from you under this License. If your rights have been terminated and not permanently reinstated, receipt of a copy of some or all of the same material does not give you any rights to use it.

10. FUTURE REVISIONS OF THIS LICENSE

The Free Software Foundation may publish new, revised versions of the GNU Free Documentation License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. See http://www.gnu.org/copyleft/.

Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License "or any later version" applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation. If the Document specifies that a proxy can decide which future versions of this License can be used, that proxy's public statement of acceptance of a version permanently authorizes you to choose that version for the Document.

11. RELICENSING

"Massive Multiauthor Collaboration Site" (or "MMC Site") means any World Wide Web server that publishes copyrightable works and also provides prominent facilities for anybody to edit those works. A public wiki that anybody can edit is an example of such a server. A "Massive Multiauthor Collaboration" (or "MMC") contained in the site means any set of copyrightable works thus published on the MMC site.

"CC-BY-SA" means the Creative Commons Attribution-Share Alike 3.0 license published by Creative Commons Corporation, a not-for-profit corporation with a principal place of business in San Francisco, California, as well as future copyleft versions of that license published by that same organization.

"Incorporate" means to publish or republish a Document, in whole or in part, as part of another Document.

An MMC is "eligible for relicensing" if it is licensed under this License, and if all works that were first published under this License somewhere other than this MMC, and subsequently incorporated in whole or in part into the MMC, (1) had no cover texts or invariant sections, and (2) were thus incorporated prior to November 1, 2008.

The operator of an MMC Site may republish an MMC contained in the site under CC-BY-SA on the same site at any time before August 1, 2009, provided the MMC is eligible for relicensing.

How to use this License for your documents

To use this License in a document you have written, include a copy of the License in the document and put the following copyright and license notices just after the title page:

Copyright (c) YEAR YOUR NAME.

Permission is granted to copy, distribute and/or modify this document

under the terms of the GNU Free Documentation License, Version 1.3

or any later version published by the Free Software Foundation;

with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.

A copy of the license is included in the section entitled "GNU

Free Documentation License".

If you have Invariant Sections, Front-Cover Texts and Back-Cover Texts, replace the "with...Texts." line with this:

with the Invariant Sections being LIST THEIR TITLES, with the

Front-Cover Texts being LIST, and with the Back-Cover Texts being LIST.

If you have Invariant Sections without Cover Texts, or some other combination of the three, merge those two alternatives to suit the situation.

If your document contains nontrivial examples of program code, we recommend releasing these examples in parallel under your choice of free software license, such as the GNU General Public License, to permit their use in free software.