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 ${\displaystyle \lor }$. So ${\displaystyle 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 ${\displaystyle \land }$. ${\displaystyle P\land Q}$ means "P and Q." This is referred to as conjunction.

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 ${\displaystyle 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 ${\displaystyle P\Rightarrow Q}$. This statement is only false when P is true and Q is false. This is the same statement as ${\displaystyle 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, ${\displaystyle 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 ${\displaystyle \{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 ${\displaystyle P\Rightarrow Q}$ is ${\displaystyle 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 ${\displaystyle P\Leftrightarrow Q}$. This is referred to as a biconditional. When ${\displaystyle P\Leftrightarrow Q}$ is a true statement, we say that P and Q are logically equivalent.

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 ${\displaystyle \neg }$.

It will be shown below in a truth table that the negation of the statement ${\displaystyle P\lor Q}$, which is ${\displaystyle \neg (P\lor Q)}$, is equivalent to ${\displaystyle \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 ${\displaystyle P\Rightarrow Q}$ is ${\displaystyle \neg P\Leftarrow \neg Q}$; or, equivalently, ${\displaystyle \neg Q\Rightarrow \neg P}$. It will be shown below that the contrapositive of a statement is equivalent to the statement itself.

The Or and And Table

OR and AND

P	Q	${\displaystyle P\lor Q}$	${\displaystyle 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	${\displaystyle P\Rightarrow Q}$	${\displaystyle P\Leftarrow Q}$	${\displaystyle 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 ${\displaystyle P\Leftrightarrow Q}$ column can be obtained from ${\displaystyle (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	${\displaystyle \neg P}$	${\displaystyle \neg Q}$	${\displaystyle P\Rightarrow Q}$	${\displaystyle \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

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 ${\displaystyle \varnothing }$ and will contain no elements.
3. Two sets are equal if and only if they contain the same elements.
4. If ${\displaystyle A}$ and ${\displaystyle B}$ are sets, then there is a set containing only the elements of ${\displaystyle A}$ and ${\displaystyle B}$. This is called the union of ${\displaystyle A}$ and ${\displaystyle B}$.
5. If ${\displaystyle A}$ is a set and ${\displaystyle P(x)}$ is a truth statement defined for all ${\displaystyle x}$ contained in ${\displaystyle A}$, then there is a set ${\displaystyle B}$ so that ${\displaystyle x}$ is in ${\displaystyle B}$ whenever ${\displaystyle P(x)}$ is true.
6. The set of counting numbers ${\displaystyle (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 ${\displaystyle A}$ be the set of all cheesecakes, and let ${\displaystyle B}$ be the set of all things that are chocolate. Mathematically, this would be denoted as:

${\displaystyle A=\{x|x{\mbox{ is a cheesecake}}\}}$
${\displaystyle 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 ${\displaystyle A}$, the predicate (truth statement) ${\displaystyle P(x)}$ used to select elements is:

${\displaystyle 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 ${\displaystyle \mathbb {R} }$. Thus, ${\displaystyle C=\{x|x>2\}}$ can be read as: "${\displaystyle C}$ is the set of all real numbers strictly greater than ${\displaystyle 2}$."

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

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

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

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

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

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

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

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

For All

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

${\displaystyle \forall x\in H,x\in E}$

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

${\displaystyle H\subset E.}$ 

This notation, ${\displaystyle 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 ${\displaystyle B}$ that is not in ${\displaystyle A}$, and thus ${\displaystyle A}$ and ${\displaystyle B}$ are not equal) and use ${\displaystyle A\subseteq B}$ to denote that ${\displaystyle A}$ is a subset of ${\displaystyle B}$. In this book we will go with the convention that ${\displaystyle A\subset B}$ could mean that ${\displaystyle A}$ is a proper subset of ${\displaystyle B}$ or that ${\displaystyle A}$ = ${\displaystyle B}$, and we will use ${\displaystyle A\subsetneq B}$ when we wish to emphasize that ${\displaystyle A\neq B}$.

There Exists

This is probably as common as for all and is equally useful. Its mathematical symbol is ${\displaystyle \exists }$. It is almost always followed by a "such that" statement. For example, "There exists a computer that has 8GB of RAM." ${\displaystyle \forall }$ and ${\displaystyle \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

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

or, when ${\displaystyle H}$ and ${\displaystyle M}$ are understood,

${\displaystyle \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: ${\displaystyle \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,

${\displaystyle \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.

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. (${\displaystyle 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.

${\displaystyle 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 ${\displaystyle A^{c}}$. If U is the universe, then the complement of A is defined to be ${\displaystyle 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 ${\displaystyle A\cup B}$. This is a general drawing, since it is not known whether there are elements in A and B. If ${\displaystyle 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 ${\displaystyle A=\{x|P(x)\}}$, then 
${\displaystyle A^{c}=\{x|\lnot P(x)\}}$.  

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

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 ${\displaystyle A\subseteq B}$ and ${\displaystyle 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, ${\displaystyle x\in A\Leftrightarrow x\in B}$. For the purpose of analyzing proofs, we will define ${\displaystyle P(x)=x\in A}$ and ${\displaystyle 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 ${\displaystyle P(x)\Rightarrow Q(x).}$ Therefore, we assume that P(x) is true. That is, ${\displaystyle x\in A.}$ Since we assumed, by hypothesis, that ${\displaystyle A\subseteq B,}$, we know that ${\displaystyle x\in B}$, which means that Q(x) is true.

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

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

Now, by axiom 3, A=B, since ${\displaystyle 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 ${\displaystyle A\subset B}$ and ${\displaystyle B\subset C}$, then ${\displaystyle 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 ${\displaystyle A\subset C}$, we need to show that ${\displaystyle \forall x\in A,x\in C.}$ So we suppose ${\displaystyle x\in A.}$ By hypothesis, ${\displaystyle A\subset B,}$ so ${\displaystyle x\in B.}$ Also by hypothesis, ${\displaystyle B\subset C}$, so ${\displaystyle x\in C.}$ Since this was true for any arbitrary ${\displaystyle x\in A,}$ we have shown that ${\displaystyle 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 ${\displaystyle A=\{x_{1},x_{2},\ldots ,x_{n}\}.}$ Now ${\displaystyle \forall i=1,2,\ldots ,n}$, we have ${\displaystyle x_{i}\in B}$. So we see that B has at least n elements, that is ${\displaystyle |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 ${\displaystyle |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.

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 ${\displaystyle A\subset B}$ then ${\displaystyle |A|\leq |B|}$.

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

Let n = |A|. Then number the elements of A, so ${\displaystyle A=\{x_{1},x_{2},\ldots ,x_{n}\}.}$ Then for each i from 1 to n we see that ${\displaystyle x_{i}\in B}$, which means that B has at least n different elements, or that ${\displaystyle |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 ${\displaystyle A\subset B}$ we know that ${\displaystyle |A|\leq |B|.}$ Also, since ${\displaystyle B\subset A}$, we see that ${\displaystyle |B|\leq |A|.}$ Now we use a fact about numbers, that if ${\displaystyle x\leq y}$ and ${\displaystyle 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.

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 ${\displaystyle |A|\leq |B|,}$ can you show that ${\displaystyle A\subset B?}$

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 ${\displaystyle |A|\neq |B|}$, then ${\displaystyle 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 ${\displaystyle n=|A|}$ and ${\displaystyle m=|B|}$. Then, number the elements in A and B, so ${\displaystyle A=\{a_{1},a_{2},\ldots ,a_{n}\}}$ and ${\displaystyle B=\{b_{1},b_{2},\ldots ,b_{m}\}}$. Since ${\displaystyle n\neq m}$, either ${\displaystyle n<m}$ or ${\displaystyle m<n}$. Without loss of generality, we assume that ${\displaystyle n<m}$. Consider the set ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \{1,1+1,1+1+1,1+1+1+1,\ldots \}}$ is an infinite set. We write the elements of this set as ${\displaystyle 1,2,3,4,\ldots }$ and define ${\displaystyle 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 ${\displaystyle \cdot }$ is defined so that ${\displaystyle 1\cdot 0=0,}$ ${\displaystyle 1\cdot 1=1}$ and ${\displaystyle n\cdot 1=1+1+\cdots (n{\mbox{ times}}).}$ We also define ${\displaystyle 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 ${\displaystyle x+y}$ is odd, then ${\displaystyle x\neq y.}$

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

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 ${\displaystyle 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, ${\displaystyle n=2\cdot k}$ for some integer k. Then ${\displaystyle n^{2}=(2k)^{2}=2k\cdot 2k=2(k\cdot 2\cdot k)}$. Since ${\displaystyle k\cdot 2\cdot k}$ is an integer because it is the product of integers, we see that ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle a_{i}}$ are 2 for any i. We consider the square ${\displaystyle 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 ${\displaystyle n^{2}}$ is odd. This proves the theorem.

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 ${\displaystyle n\in \mathbb {N} ,}$ ${\displaystyle \sum _{i=1}^{n}{i}={\frac {n(n+1)}{2}}}$

Proof

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

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

${\displaystyle {\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.